?? 程式員必讀書籍！！！豆瓣評分9.7 ???? 好評如潮

?? 讀書筆記Xmind分享 ???? 讀書筆記 | 資料密集型應用系統設計 | 思維導圖?? ?口令: vP5C

?? 品質讀物"Go"????《資料密集型應用系統設計》

?? 關鍵詞匯 : 資料模型 / 資料存盤 / 事務 / 分布式

?? 歡迎關注 : 大摩羯先生

第一部分 資料系統基礎

第1章 可靠、可擴展與可維護的應用系統

背景

• 應用都屬于資料密集型，而非計算密集型

• 核心在于資料量、資料的復雜度及資料的快速多變性

應用構建模塊

資料庫

持久化資料

1. MySQL等關系型資料庫
2. Hive/Clickhouse等大資料存盤

高速快取

快取熱點資料/操作復雜資料以供加快訪問

1. 應用記憶體一級快取
2. Redis、Memcache等二級快取

索引

通過冗余存盤、異構資料結構來加快檢索

1. ES倒排索引
2. MySQL索引

流式處理

持續發送訊息至另一個行程，處理采用異步方式

1. 基于RMQ可靠訊息傳遞
2. 基于Kafka流式資料傳遞

批處理

定期處理大量的累積資料

認識資料系統

資料庫、佇列、高速快取等都可以認為是“資料系統”

設計資料系統或資料服務時，三個棘手問題

• 可靠性

  出現例外時，系統可以繼續正常運轉

• 可擴展性

  隨著資料規模、流量、復雜性增長，能夠以合理的方式來匹配

• 可維護性

  現有功能維護&新功能迭代、新老人員交替

第2章 資料模型與查詢語言

背景

應用構建是一層一層疊加“資料模型”來構建的

關系模型&檔案模型

• SQL

  資料被組織成關系，即表

  每個關系都是元組的無序集合，即行

• RDBMS

  事務處理

  批處理

• NoSQL

  • 1. 比關系資料庫有更好的拓展性，支持超大資料集或超高寫入吞吐量
  • 2. 大多數免費、開源
  • 3. 關系模型不能很好支持一些特定查詢
  • 4. 突破關系模式限制性，期望更動態和表達力的資料模型

• 物件-關系不匹配

  開發語言，普遍面向物件編程

  關系型資料庫需要ORM映射轉化

  關系模型的靈活性較差，非關系型可以更豐富的表達邏輯關系，如JSON、XML

• 多對一與多對多關系

  維護關系ID而非純文本字串

  • 1. 避免批量復制、更新帶來的消耗
  • 2. 容易維護
  • 3. 避免帶來資料不一致問題
  • 4. 符合資料庫規范思想，消除重復

• 檔案模型并不適合表達多對一的關系

  • 一些資料系統不支持聯結join這種操作，需要從資料層轉移到應用層

• 優缺點對比

  • 關系資料庫

    • 依賴所使用的資料結構，強在聯結操作、多對一、多對多關系的簡潔表達

    • 高度關聯資料

  • 檔案資料庫

    • 模式靈活性，區域性帶來較好性能

    • 無模式

    • 資料結構是隱式的，讀取時才解釋

    • 一般為xml、json、二進制變體等結構化資料

    • 類似檔案結構，即一系列關系資料，適合使用檔案資料庫，一次完成加載

    • 局限性在于嵌套層次的訪問路徑，不能直接參考檔案中的嵌套項

    • 對于聯結支持不足

    • 適合一對多，無關系，不適合多對多關系的資料模型

資料查詢語言

宣告式

• 宣告式語言只需要指定所需資料模式、結果滿足條件、資料轉換（排序、分組、聚合），而不需要關心具體實作程序和細節

• 比命令式API更加簡潔和容易使用，隱蔽了內部實作細節

• 例如資料庫系統的查詢優化器會決定采取哪些索引和聯結，以及用何種順序來執行查詢的各個陳述句

命令式

• 命令式語言告訴計算機以特定順序執行某些操作，可以完全推理整個程序，逐行遍歷代碼、評估相關條件、更新對應的變數等

MapReduce

• 既不是宣告式查詢語言，也不是一個完全命令式的查詢API

• 它介于兩者之間，查詢邏輯用代碼實作，基于許多函式式編程語言中的map

• MapReduce是一個相當底層的編程模型，用于計算集群上分布執行

圖狀資料模型

例子

• 社交網路

  頂點是人，邊表示與其他人的關系

• WEB圖

  頂點是網頁，邊表示與其他頁面的HTML鏈接

• 公路/鐵路網

  頂點是交叉路口，邊表示他們之間的公路或鐵路線

小結

資料模型演程序序

• 層次模型

  像一顆大樹，不利于表示多對多關系

• 關系模型

  檔案資料庫

  圖資料庫

第3章 資料存盤與檢索

資料庫核心：資料結構

• 索引

  • 優點：加快檢索

  • 缺點：增加寫入成本，影響性能

• 種類

  • 聚集索引

    索引中直接保存行資料

  • 非聚集索引

    存盤行資料的參考，需要再到實際存盤行資料的索引上檢索，回表查詢

• 覆寫索引

  檢索資料就在索引上存盤

• 多列索引

• 哈希索引

  • 優點：訪問快

  • 缺點：記憶體占用、哈希沖突的解決、隨機IO訪問、區間查詢效率不高不能高效范圍查詢

• 全文搜索、模糊索引

• 倒排表

  • Lucene是Elasticsearch和Solr的索引引擎

  • Key記錄詞條，Value記錄包含該詞條的檔案ID

    布隆過濾器

  • 避免頻繁無效操作

    SSTables（Sorted String Table） 排序字串表

  • 要求每個鍵在每個段檔案中只能出現一次

  • 合并后的鍵是有序的

  • LSM Tree（Log Structured Merge Tree）

    一種分層、有序、面向磁盤的資料結構 其核心思想是充分利用磁盤的順序寫性能要遠高于隨機寫性能這一特性，將批量的隨機寫轉換為一次性的順序寫

    參考 https://segmentfault.com/a/1190000040752799

  • CURD

    • 新增

      追加一條新記錄

    • 更新

      追加一條新記錄

    • 洗掉

      追加一條洗掉記錄

• B-Tree

  • 將資料庫分解成固定大小的塊或頁，一般為4KB

  • 頁是內部讀寫的最小單元

  • 這種資料結構的設計更接近底層硬體，因為硬碟也是以固定大小的塊排列

  • 資料更新策略

  • 預寫日志（WAL）+ 覆寫頁

    重做日志

    僅支持追加修改的檔案，每個B-Tree修改必須先更新WAL然后再修改樹本身的頁， 當資料庫崩潰后需要恢復時，該日志用于將B+Tree恢復到最近一致的狀態

  • 寫時復制

    修改的頁被寫入不同的位置，樹中頁的新版本創建后指向新的位置

    這是類似一種快照隔離、可重復讀的設計思想

  • B+Tree

    增加頁的額外指標來指向同層級左、右兄弟頁，不用跳回父一級頁

• 追加日志檔案的實作

  • 重要問題

    • 1. 檔案格式，更快更簡單的方法是使用二進制格式
    • 2. 洗掉記錄，進行洗掉的特殊標記
    • 3. 崩潰恢復， 先寫日志，通過日志來恢復和回放
    • 4. 部分寫入問題， 追加日志進行校驗和保證完整性
    • 5. 并發控制， 嚴格的先后順序追加，一個寫執行緒，多個讀執行緒

  • 追加式設計優點

    • 1.磁盤寫入友好， 追加和分段合并主要是順序寫，比隨機寫入快，特別是在旋轉式磁性硬碟上

    • 2.并發、崩潰恢復友好， 不必擔心錯寫問題

    • 3.避免碎片化， 根據規則進行舊分段合并，避免磁盤碎片化，提高利用率

• 事務處理與分析處理

  • 事務屬性

    ACID 原子性、一致性、隔離性、持久性

• OLTP&OLAP

  • 資料倉庫

    不影響OLTP業務

    一般數倉是OLTP系統的只讀副本

    資料轉換，提取-轉換-加載

  • 列式存盤

    按列進行資料聚合存盤

    列存盤壓縮

    同一列資料型別一致，便于進行壓縮

    列存盤排序

    縮小資料范圍

    利于進行列壓縮

    隨機性大，不容易真正進行壓縮

    列存盤寫入

    寫入相對困難

  • LSM-Tree解決方案

    位圖索引 & 游程編碼

    Clickhouse，Cassandra，Hbase

聚合

COUNT、SUM、AVG、MIN、MAX

物化視圖，其實就是預先查詢好，根據業務資料的更新來連鎖更新，將計算前置

小結

• 1. OLTP面向用戶，業務查詢、事務請求多，資料量小，對性能要求高
• 2. OLAP面向資料決策用戶，請求量低，但資料查詢量大
• 3. OLTP主要存盤引擎

  • ① 日志結構流派

    只允許追加式更新檔案和洗掉過時的檔案，但不會修改已寫入的檔案

    BitCask、SSTables、LSM-Tree、LevelDB、Cassandra、HBase、Lucene

  • ② 原地更新流派

    將磁盤視為可覆寫的一組固定大小的頁，貼近硬體磁盤結構的設計

    B-Tree、InnoDB

第4章 資料編碼與演化

資料編碼格式

• 編碼資料格式

  JSON、XML、protobuf、Thrift、Avro

• 資料存盤、通信場景

  Rest、RPC、訊息傳遞

• 編碼&解碼、序列化&反序列化

  語言的特定格式問題

• 不同語言之間格式的差異和通信

  為了在相同物件型別中恢復資料，解碼程序需要能夠實體化任意的類，這個程序存在一些安全問題，容易遭到惡意攻擊

  缺乏資料變更帶來的向前、向后兼容問題

  效率問題，比如Java內置序列化性能較差、編碼臃腫

  第三方序列化的問題

  數字編碼的模糊之處

  XML、CSV無法區分數字和由數字組成的字串

  JSON區分字串和數字，但不區分整數、浮點數，并且不指定精度

  JSON、XML對Unicode字串支持友好

  不支持二進制字串，通過Base64將二進制資料編碼為文本來解決這個限制

• 二進制編碼

  結構緊湊，效率高，節省空間

  可讀性差

• JSON的二進制編碼

  • MessagePack，二進制編碼

  • Thrift、protobuf

    欄位標簽和模式演化

    欄位位置、標簽記錄

    資料型別和模式演化

    精度丟失風險

  • Avro

    讀模式

    寫模式

  延伸閱讀《深入理解序列化和反序列化》https://book.douban.com/subject/35303133/

資料流模式

• 通過資料庫

• 通過服務呼叫

  • 遠程呼叫的問題

    • 1. 網路請求是不可預測的，遠程服務回應慢、網路問題丟失等
    • 2. 超時情況的處理
    • 3. 重試帶來的冪等處理
    • 4. 較大物件的傳輸問題
    • 5. 不同行程語言服務的資料轉換問題

  • RPC的資料編碼和演化

    Thrift、gRPC和Avro RPC可以根據各自編碼格式的兼容性規則進行演化

    在SOAP中，請求和回應是用XML模式指定的

    Restful API通常使用JSON用于回應

• 通過訊息佇列

  • 訊息佇列比RPC的優點

    1. 系統間的緩沖區，如果接收方系統過載或不可用，可以暫時存盤，提高系統整體可用性

    2. 自動將訊息重新發送到之前崩潰的系統，防止訊息丟失

    3. 發送方不需要知道接收方IP、埠資訊等

    4. 支持一條訊息同時發給多個接收方

    5. 發送方、接收方分離，解耦

  • 訊息佇列比RPC的差異

    通信是異步的

    不關心回應結果

    不強制特定資料格式

    訊息佇列產品 RabbitMQ、ActiveMQ、Kafka

小結

• 編程語言自身支持的序列化僅限自身語言中使用，無法跨語言使用，且缺乏向前、向后兼容

• JSON、XML、CSV等文本格式非常普遍，主要特定資料型別的兼容支持問題

• 二進制編碼格式支持使用清晰定義來進行向前、向后兼容性的變更且可以進行緊湊、高效的編碼，但是對閱讀不友好

第二部分 分布式資料系統

分布式部署

目的

• 擴展性

  突破單機能力

• 容錯與高可用性

  避免單機帶來的故障、破壞問題

• 延遲考慮

  就近部署，提高回應效率

第5章 資料復制

資料復制的方式

• 主從復制

  • 主從復制原理

    • 1. 指定某一個副本為主副本（主節點），當寫資料時，寫請求由主節點來處理并把新資料寫入主節點
    • 2. 其他副本則全部稱為從副本（從節點），主副本寫入本地存盤后將資料更改通過復制的日志或更改流發送給所有從副本，然后從節點嚴格保持和主節點一樣的寫入順序寫入到從節點本地
    • 3. 客戶端讀取資料時可以從主節點、從節點上進行，但是只有主節點接受寫請求

  • 資料復制的問題

    • 同步or異步

      • 同步復制

        同步復制的優點是，確保副本之間資料一致性

        同步復制的缺點是，延時高，如果出現節點故障，寫入將阻塞且始終無法成功

      • 半同步

        至少有兩個節點擁有最新的資料副本（即主節點和一個同步從節點）

      • 全異步復制

        主節點一直可以回應寫請求，吞吐性好，但是從節點可能遠遠落后主節點，也可能會有資料不一致、持久性問題

        不靠譜較為折中的設計，但是應用也比較廣泛

    • 處理失敗副本

      • 從節點失效

        重啟后追趕主節點最新資料

      • 主節點失效

        1. 確認主節點失效

           一般基于超時機制，節點之間頻繁地相互發送心跳存活訊息， 如果發現某一個節點在一段時間內沒有回應則認為該節點失效

        2. 選舉新的主節點

           通過共識機制來投票選舉

           候選節點最好與原主節點的資料差異最小，這樣可以最小化資料丟失風險

        3. 重新配置系統使新主節點生效

           請求路由控制

           多副本的一致性

      • 增加新的從節點

        1. 在某個時間點對主節點的資料副本產生一個一致性快照，這樣不會長時間鎖定整個資料庫

        2. 將此快照拷貝到新的從節點

        3. 從節點從拷貝來的資料中追趕主節點的最新資料同步

實作

MySQL、SQL Server、Oracle

MongoDB

Kafka、RabbitMQ

• 復制日志的實作

• 基于陳述句的復制

  記錄每個寫請求并將陳述句作為日志發送給從節點

  • 問題

    非確定性函式，如時間函式、亂數函式不同副本可能產生不同結果

    副作用的陳述句，觸發器、存盤程序、用戶自定義函式等，也可能產生不同結果

    自增列，所有副本必須按照完全相同順序執行，否則會產生不同結果

    如果存在多個并發執行的事務時，會有很大限制

• 基于預寫日志（WAL）復制

  • 適用

    日志結構存盤引擎、采用覆寫寫磁盤+預寫日志的存盤引擎都適合此類復制方式

  • 缺點

    復制方案和存盤引擎緊密耦合，如果資料存盤結構、存盤引擎變化則會有很大影響和改變

  • 實作

    PostgreSQL、Oracle、MySQL

• 基于行的邏輯日志復制

  • 復制和存盤引擎采用不同的日志格式，復制和存盤引擎邏輯剝離

  • 關系資料庫的邏輯日志一般指的是一系列記錄來描述資料表行級別的寫請求

    對于行插入，日志包含所有相關列的新值

    對于行洗掉，日志里有足夠的資訊來唯一標識已洗掉的行，通常是靠主鍵

    對于行更新，日志包含足夠的資訊來唯一標識更新的行，以及所有的新值

    如果一條事務涉及多行的修改，會產生多條日志記錄

    實作

    • MySQL使用基于二進制日志binlog進行復制

    • 基于觸發器的復制

      可以考慮基于應用層代碼邏輯實作和控制

多主節點復制

• 特點

  多主節點接收寫操作，復制流程類似

  每個主節點同時也扮演其他主節點的從節點角色

  通常多主節點之間資料同步是異步復制

• 適用場景

  一個資料中心使用多主節點基本沒有太大意義，其復雜性已經超過所能帶來的好處

  適合多資料中心

  適合應用與網路斷開后繼續作業的場景，如IM多端資料同步、檔案協作編輯

  多主主從復制 vs 單主主從復制

• 性能

  容忍資料中心失效

  容忍網路問題

• 問題

  處理多主的寫沖突，實作收斂沖突解決的方式

  • 1. 給每個寫入分配唯一的ID，例如一個時間戳，一個足夠長的亂數，一個UUID或者一個基于鍵-值的哈希，挑選最高ID的寫入作為勝利者，并將其他寫入丟棄
  • 2. 為每個副本分配一個唯一的ID，并制定規則，例如序號高德副本寫入始終優先于序號低的副本
  • 3. 以某種方式將這些值合并在一起，如5-7，A-C

  • 4. 保留所有沖突資訊，交給用戶事后解決

       寫入時檢查

       讀取時檢查

多主節點模型的拓撲結構

多節點容錯性更好

多節點資料通信傳播復雜性增加

多節點資料復制覆寫問題

時間戳無法保證副本時鐘

版本向量控制

無主節點復制

放棄選擇主節點，允許任何副本直接處理客戶端請求完成寫處理

問題

• 多副本寫入性能

• 大部分ack

• 失效節點恢復上線后進行資料追趕修復

• 最后寫入者獲勝 last write win - LWW

實作

• Cassandra

復制滯后問題

• 滿足最終一致性

  寫主，讀從分攤壓力

• 追求一致性

  寫后讀

  讀寫均在主節點

• 單調讀

  用戶資料讀取固定在一個副本執行

  基于用戶ID、IP的哈希方法

  比強一致性弱，但比最終一致性強的保證

• 順序一致讀

  順序寫入，不能產生亂序情況，包含資料背景關系順序，還有資料自身更新順序

  解決方案是，具有因果順序關系的寫入都交給一個磁區副本來完成，但是效率和穩定性有損失

第6章 資料磁區

資料磁區與資料復制

每個磁區在多個節點都存有副本

鍵-值資料的磁區

磁區的目的是將海量資料平均分攤到不同磁區節點

• 分攤不均勻的情況叫做資料傾斜，導致部分磁區效率性能嚴重下降

• 熱點資料也會導致系統資源使用不均勻，過于集中于部分磁區出現問題

基于關鍵字區間磁區

• 指定一段段連續區間范圍（最小值、最大值、時間戳）

• 這些區間不一定非要均勻分布，因為資料本身就可能不均勻

基于關鍵字哈希值磁區

一個好的哈希函式可以處理資料傾斜并使其均勻分布，哈希能夠解決資料分布均勻的問題，但是也破壞了連續性資料的區間特性

一致性哈希

哈希磁區的熱點，資料傾斜問題

• 需要在切分鍵上增加亂數或取模后綴進行再次rehash來打散

• 需要額外維護元資料來映射打散資料，還需要負責聚合這些資料

基于混合鍵磁區

鍵的一部分標識磁區，另一部分用來記錄排序后的順序

磁區與二級索引

基于檔案磁區的二級索引（本地索引）

• 寫資料時，按切分鍵（如用戶ID）來路由到不同磁區，并在各自磁區內構建二級索引（如性別-用戶ID關系）

• 讀資料時，如果使用到二級索引進行檢索，會同時查詢所有磁區中的二級索引拿到符合條件的資料然后做聚合回傳

實作

MongoDB、Cassandra、Elasticsearch

• 基于詞條的二級索引磁區（全域索引）

  • 構建全域索引，但是這個全域索引不僅僅存盤在某個單點上，而是根據索引檢索值路由到不同磁區上

  • 優點：客戶端只需要對包含詞條索引的磁區發出一次請求，不需要遍歷所有磁區即可拿到索引命中的資料，效率更高

  • 不足：寫入速度較慢且非常復雜，主要是因為單個檔案更新時，可能需要涉及多個二級索引的更新，而這些二級索引可能在不同磁區節點上，造成寫放大問題；且這個更新程序一般都是異步的，不會立刻反應在檢索上

• 磁區再平衡

動態再平衡策略

為什么不用取模

• 節點樹變化，資料到磁區節點的路由關系變化，需要重新遷移進行再平衡，成本巨大

• 固定數量的磁區

• 創建遠超實際節點數的磁區數，然后為每個節點分配多個磁區，比如10節點集群，每個節點分配100個邏輯磁區

實作

Elasticsearch

• 動態磁區

  • 每個磁區只屬于一個節點，每個節點可以管理多個磁區

  • 如果一個節點中資料量過大，會被限制磁區大小，避免傾斜

• 按節點比例磁區

  • 自動與手動再平衡操作

  • 維護成本，可操作維護性

• 請求路由

• 服務發現問題

• 處理策略

  • 1. 允許客戶端鏈接任意節點，如果節點恰好擁有所請求的磁區，則直接處理該請求，否則會將請求轉發到下一個合適的節點來處理
  • 2. 所有的客戶端請求都發送到一個路由層，由路由層負責請求轉發到對應的磁區節點上，路由層不處理業務，只負責請求分發
  • 3. 客戶端感知磁區和節點分配關系，客戶端可以直接鏈接到目標磁區節點，不需要任何中介

• 并行查詢執行

第7章 事務

深入理解事務

事務有其優勢，也有自身局限性

ACID的含義

原子性（Atomicity）、一致性（Consistency）、隔離性（Isolation）、持久性（Durability）

BASE的含義

基本可用性（Basically Available）、軟狀態（Soft state）、最終一致性（Eventual consistency）

單物件、多物件事務操作

修改多個物件的整體一致性、隔離性等

單物件寫入

修改單個物件的原子性、隔離性等

多物件事務的必要性

• 關系資料模型中，外鍵關系要求資料更新必須聯動

• 檔案資料模型中，由于缺少join功能支持，需要同時維護反范式多物件來更新

• 對于帶有二級索引的資料庫，需要維護事實表和二級索引的更新

處理錯誤和中止

• 支持安全的重試機制才是中止流程的重點

• 考慮回傳客戶端失敗，但是重試執行成功導致的回應結果與實際資料狀態不一致情況

• 重試需要設定次數上限，例如指數回退，避免給系統負載帶來超負荷壓力

• 由臨時性故障引起的重試才有意義，永久性故障、錯誤導致的重試毫無意義

• 重試考慮冪等問題，避免重復

• 充分考慮重試的持久驅動，驅動行程也出現例外則再無可重試驅動力

弱隔離級別

• 并發問題 / 競爭條件

  多個不同事務同時讀取或操作同一資料

• 弱隔離的目的

  提高性能，也要避免并發競態帶來的問題

• 讀-提交

  最基本的事務隔離級別，提高兩個保證

  • 1. 讀資料庫時，只能看到已成功提交的資料，防止“臟讀”
  • 2. 寫資料庫時，只會覆寫已成功提交的資料，防止”臟寫”

• 實作讀-提交

  • 防止臟寫：對訪問資料物件上鎖（如行級鎖）保證同一時間一個事務進行事務操作

  • 防止臟讀：多版本快照提供非鎖定讀的支持，可以讀已提交事務的最新資料，也可以讀最舊的資料

快照級別隔離與可重復讀

實作 PostgreSQL、MySQL的InnoDB存盤引擎、SQL Server、Oracle

• 實作快照級別隔離

  • 寫鎖防止臟寫

  • 讀不需要加鎖，是非阻塞的讀

  • 多版本并發控制 MVCC（Multi-Version Concurrency Control）

    記錄多個事務在不同時間點的資料物件提交版本

    唯一、單調遞增的事務ID（txid）

• 一致性快照的可見性規則

  • 1. 每筆事務開始時，其他進行中的事務對自身不可見
  • 2. 所有中止事務做的修改對自身不可見
  • 3. 較晚事務ID（晚于當前事務）所做的修改對自身不可見
  • 4. 其他所有的寫入都對應用查詢可見

• 索引與快照級別隔離

  • 追加式的B-Tree，每個寫入事務都會創建一個新的B-Tree root，代表該時刻資料庫的一致性快照

  • 查詢根據特定快照B-Tree來實作隔離

  • 需要后臺行程來執行壓縮和垃圾回收

• 防止更新丟失

  • 寫事務并發帶來的問題

  • 解決方案

    • 原子寫操作

      單執行緒，順序寫入

    • 顯式加鎖

      FOR UPDATE

    • 原子比較更新和設定 CAS（compare and set）

      Update Table set content=2 where id = 1 and content=1

    • 多副本的沖突解決和復制

      多主節點或者無主節點中多副本，天然支持多個并發寫，通常以異步方式來同步更新，因此也會出現多個最新的資料副本情況 該場景下加鎖、原子比較不適用

      解決方案是保留多個沖突版本，由應用層邏輯解決，或者依靠特定的資料結構來解決，合并多版本

      最后寫入獲勝（LWW）

      容易丟失更新，但是是多數多副本資料庫的默認配置

寫傾斜與幻讀

定義寫傾斜

• 原因

  多個事務讀取同一個資料物件，然后更新其中一部分或各自更新不同物件，造成寫傾斜

  涉及多個物件，單物件的原子操作不起作用

  對參與原子操作的物件進行加鎖

• 總結

  由于有了不同隔離級別下支持的多版本非鎖定讀，拿到非鎖定讀資料只是整個事務操作的一步，且這個資料在事務外還會進行變化，那就導致整體事務操作的原子性不可控，背離初衷產生一些問題

  幻讀

  物體化沖突

  將競態條件建立在可操作物件上進行加鎖

串行化

最強的隔離級別

通過避免并發的方式解決并發問題

• 采用存盤程序封裝事務

  • 優點

  • 缺點

    語意丑陋、過時，缺乏函式庫支持

    管理、除錯、測驗困難，不易監控和應用層集成

    糟糕的存盤程序會給資料庫性能帶來極大影響

兩階段加鎖（2PL，tow-phase locking），比較標準的串行化方式

讀鎖定

寫鎖定

謂詞鎖

百度什么是“謂詞”？

 數理邏輯中表示一個個體的性質和兩個或兩個以上個體間關系的詞

 謂詞鎖不屬于某個特定物件，而是面向某些特殊的搜索條件命中的物件，這里的代表可以是范圍查詢回傳的行資料

索引區間鎖（next-key locking）

• 謂詞鎖性能不佳，事務中存在許多鎖，檢測匹配鎖就變得非常耗時

• 索引區間鎖是對謂詞鎖的簡化和優化，它是對保護物件進行擴大化，優化可以理解為是把一條條具體明細鎖變成了范圍區間鎖，效率是大大提升的

• 目的是有效防止寫傾斜、幻讀問題

• 當沒有合適的索引（即沒有合適的加鎖物件）進行區間鎖施加，會退化成鎖表操作

可串行化的快照隔離（Serializable Snapshot Isolation，SSI ）

樂觀并發控制

第8章 分布式系統挑戰

故障與部分失效

不可靠的網路

網路問題

• 1. 請求可能在節點轉發中丟失
• 2. 請求可能在某個佇列中等待，無法馬上發送
• 3. 遠程接受節點可能已經宕機失效
• 4. 遠程接收節點可能暫時無法回應（GC、負載過高等）
• 5. 遠程接收節點已經完成處理請求，但回復訊息在回傳程序中丟失
• 6. 遠程接收節點已經完成處理請求，但是回復訊息超時回傳，發送方無法處理

不可靠的時鐘

時鐘和計時的重要性

• 測量持續時間

• 記錄業務時間節點

• 特定時間觸發業務

單調時鐘與墻上時鐘

• 墻上時鐘，根據某個日歷回傳當前的日期與時間

• 服務器與NTP服務同步

• 單調時鐘，保證總是向前計數，不會出現回撥現象

• 單調時鐘適合測量持續時間段

知識，真相與謊言

拜占庭將軍問題

第9章 一致性與共識

一致性保證

強一致性

弱一致性

最終一致性

可線性化（原子一致性、強一致性）

多副本下資料讀取結果在任何時刻都保持一致

對客戶端來說就像只有一個資料副本一樣

可線性化 vs 可串行化

• 可線性化

  • 讀寫單個物件的最新值保證

• 可串行化

  • 一般指事務隔離級別

  • 線性化的依賴條件

    加鎖與主節點選舉

    主節點選舉程序進行加鎖保證線性化

    如使用Zookeeper

  • 約束與唯一性保證

    資料庫唯一索引

  • 跨通道的時間依賴

    如訊息佇列中訊息的順序性

  • 實作線性化系統

    主從復制（部分支持線性化）

    主節點復制到從節點滿足線性化

共識演算法（可線性化）

通過共識協議防止多副本資料不一致，包含Zookeeper，etcd等

共識演算法就是基于強一致性來實作，一定是可線性化的

• 多主復制（不可線性化）

  由于在多個節點執行并發寫入，資料異步復制到其他節點，因此寫入有可能出現沖突

• 無主復制（可能不可線性化）

  需要讀取多個節點資料，但是無法確定節點資料間的差異

• CAP理論

  • 一致性(C)、可用性(A)、磁區容錯性(P)，系統只能同時滿足兩個特性

  • P 是客觀存在的，無法避免的，在P不能滿足時，只能選擇可用性(A)或者一致性(C)

  • 關于CAP理論對于分布式系統設計有重要指導作用，它已被更精確的研究成果所取代

順序保證

事實證明，排序、可線性化與共識之間存在著聯系

順序與因果關系

• 因果關系對所發生的事件施加了某種排序

• 發送訊息先于收到訊息

• 問題出現在答案之前

• 如果系統服從因果關系所規定的的順序，則稱之為因果一致性

• 快照隔離提供了因果一致性，因為事務在資料讀取時可以按照事件發生的順序進行選擇

• 因果順序并非全序

全序和偏序的差異體現在不同資料一致性模型

• 可線性化

  在一個可線性化的系統中，存在全序操作關系，能指出哪個操作在先，哪個在后

• 因果關系

  兩個非并發的操作一定存在因果關系（前后次序），否則不可排序

  實作可線性化是要保持因果關系

  單調遞增序列號排序

• 非因果序列發生器

  奇偶遞增，A：1，3，5  B：2，4，6

  時間戳遞增，最后寫獲勝

  按區間分配遞增序列，A：1-1000 B：1001-2000

  Lamport時間戳

  全序關系廣播

  利用明確的順序關系

分布式事務與共識

需要集群節點達成一致的場景

• 主節點選舉

• 原子事務提交

  • 兩階段提交 2PC（two-phase commit）

    • 1. 啟動一個分布式事務時，向協調者請求全域唯一的事務ID
    • 2. 協調者向每個參與者發送執行事務的一階段準備請求

    • 3. 參與者回傳是否要提交的反饋、投票，協調者記錄投票結果

         投票不可反悔、不可更改

    • 4. 協調者按照結果通知所有參與者二階段完成或者取消請求

  • 三階段提交 3PC

    分布式事務概念

    資料庫內部的分布式事務

    MySQL Cluster的NDB存盤引擎

  • 異構分布式事務

    存在兩種及以上不同的參與者實作技術

    資料庫 、快取、訊息佇列等

    Exactly-once訊息處理

    XA交易

       并不是網路協議，而是與事務協調者進行通信的API
    
       停頓時仍持有鎖
    
       當有節點不能正常作業時，仍持有鎖阻止其他事務進行并發操作
    

    從故障中恢復

       通過恢復日志、人為處理等方式
    

    分布式事務的限制

       協調者不支持資料復制，意味著單點運行，本身就不是高可用
    
       協調者需要依賴日志進行中斷事務的恢復和保證
    
       2PC并不是完備的事務提交保證機制，需要考慮它的例外場景帶來的問題
    

  • 支持容錯的共識

    共識演算法的性質

       協商一致性
    
           所有節點都接受相同的協議
    
       誠實性
    
           所有節點不能反悔，對一項提議不能有兩次決定
    
       合法性
    
           如果決定了某個值，則一定是由某個節點提議的
    
       可終止性
    
       節點如果不崩潰最終一定可以達成協議
    

  • 共識演算法

  VSR、Paxos、Raft、Zab

  • 全序關系廣播

    訊息按照相同的順序發送到所有節點，有且只有一次

    相當于持續的多輪共識

    由于協商一致性，所有節點決定以相同的順序發送相同的訊息

    由于誠實性，訊息不會改變

    由于合法性，訊息不會被破壞和造假

    由于可終止性，訊息不會丟失

  • 主從復制與共識

    主節點寫入，同步給從節點，是滿足共識的，這里主節點相當于獨裁者角色

    但是分布式場景下，選主程序中要避免出現多主

    世紀編號（epoch number）

    保證每個是世代里，主節點是唯一確定的

    更高編號將獲勝

  • 共識的局限性

    投票程序是一個同步復制程序，節點資料復制大部分是異步的，故障切換時有資料丟失風險

    共識體系需要嚴格的節點數才能運行，因此會引入投票限制的節點部署代價

    共識體系中節點不能動態添加、洗掉，否則會影響選舉結果甚至出現問題

    共識體系依賴超時機制來檢測節點失效，超時時間的配置和網路情況對故障切換和感知有很大影響

  • 成員與協調服務

    Zookeeper、ETCD、Consul

    保存少量、可完全載入記憶體（最終要寫入磁盤以支持持久性）的資料設計

    采用容錯的全序廣播演算法在所有節點上復制這些資料從而實作高可靠

    適用場景

       節點任務分配
    
       作業調度
    
       負載平衡
    
       服務發現
    
       成員服務
    

第三部分 派生資料

第10章 批處理系統

第11章 流處理系統

第12章 資料系統的未來

本文由博客一文多發平臺 OpenWrite 發布！

標籤：其他

上一篇：用ACDSee查看Office檔案？No！有中文解決方案嗎？暫未發現！

下一篇：Monodraw for Mac (ASCII碼設計編輯工具)