?? 程序員必讀書籍Ｍ杀恪９鄙骸棍潘！豆瓣評分9.7 ???? 好評如潮

?? 讀書筆記Xmind分享 ???? 讀書筆記 | 數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計 | 思維導(dǎo)圖?? ?口令: vP5C

?? 品質(zhì)讀物"Go"????《數(shù)據(jù)密集型應(yīng)用系統(tǒng)設(shè)計》

?? 關(guān)鍵詞匯 : 數(shù)據(jù)模型 / 數(shù)據(jù)存儲 / 事務(wù) / 分布式

?? 歡迎關(guān)注 : 大摩羯先生

第一部分 數(shù)據(jù)系統(tǒng)基礎(chǔ)

第1章 可靠溉跃、可擴(kuò)展與可維護(hù)的應(yīng)用系統(tǒng)

背景

• 應(yīng)用都屬于數(shù)據(jù)密集型宪赶，而非計算密集型

• 核心在于數(shù)據(jù)量、數(shù)據(jù)的復(fù)雜度及數(shù)據(jù)的快速多變性

應(yīng)用構(gòu)建模塊

數(shù)據(jù)庫

持久化數(shù)據(jù)

1. MySQL等關(guān)系型數(shù)據(jù)庫
2. Hive/Clickhouse等大數(shù)據(jù)存儲

高速緩存

緩存熱點數(shù)據(jù)/操作復(fù)雜數(shù)據(jù)以供加快訪問

1. 應(yīng)用內(nèi)存一級緩存
2. Redis痒玩、Memcache等二級緩存

索引

通過冗余存儲淳附、異構(gòu)數(shù)據(jù)結(jié)構(gòu)來加快檢索

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

流式處理

持續(xù)發(fā)送消息至另一個進(jìn)程议慰，處理采用異步方式

1. 基于RMQ可靠消息傳遞
2. 基于Kafka流式數(shù)據(jù)傳遞

批處理

定期處理大量的累積數(shù)據(jù)

認(rèn)識數(shù)據(jù)系統(tǒng)

數(shù)據(jù)庫、隊列奴曙、高速緩存等都可以認(rèn)為是“數(shù)據(jù)系統(tǒng)”

設(shè)計數(shù)據(jù)系統(tǒng)或數(shù)據(jù)服務(wù)時别凹，三個棘手問題

• 可靠性

  出現(xiàn)異常時，系統(tǒng)可以繼續(xù)正常運轉(zhuǎn)

• 可擴(kuò)展性

  隨著數(shù)據(jù)規(guī)模洽糟、流量炉菲、復(fù)雜性增長，能夠以合理的方式來匹配

• 可維護(hù)性

  現(xiàn)有功能維護(hù)&新功能迭代坤溃、新老人員交替

第2章 數(shù)據(jù)模型與查詢語言

背景

應(yīng)用構(gòu)建是一層一層疊加“數(shù)據(jù)模型”來構(gòu)建的

關(guān)系模型&文檔模型

• SQL

  數(shù)據(jù)被組織成關(guān)系拍霜，即表

  每個關(guān)系都是元組的無序集合，即行

• RDBMS

  事務(wù)處理

  批處理

• NoSQL

  • 1. 比關(guān)系數(shù)據(jù)庫有更好的拓展性薪介，支持超大數(shù)據(jù)集或超高寫入吞吐量
  • 2. 大多數(shù)免費祠饺、開源
  • 3. 關(guān)系模型不能很好支持一些特定查詢
  • 4. 突破關(guān)系模式限制性，期望更動態(tài)和表達(dá)力的數(shù)據(jù)模型

• 對象-關(guān)系不匹配

  開發(fā)語言昭灵，普遍面向?qū)ο缶幊?/p>

  關(guān)系型數(shù)據(jù)庫需要ORM映射轉(zhuǎn)化

  關(guān)系模型的靈活性較差吠裆，非關(guān)系型可以更豐富的表達(dá)邏輯關(guān)系，如JSON烂完、XML

• 多對一與多對多關(guān)系

  維護(hù)關(guān)系ID而非純文本字符串

  • 1. 避免批量復(fù)制试疙、更新帶來的消耗
  • 2. 容易維護(hù)
  • 3. 避免帶來數(shù)據(jù)不一致問題
  • 4. 符合數(shù)據(jù)庫規(guī)范思想，消除重復(fù)

• 文檔模型并不適合表達(dá)多對一的關(guān)系

  • 一些數(shù)據(jù)系統(tǒng)不支持聯(lián)結(jié)join這種操作抠蚣，需要從數(shù)據(jù)層轉(zhuǎn)移到應(yīng)用層

• 優(yōu)缺點對比

  • 關(guān)系數(shù)據(jù)庫

    • 依賴所使用的數(shù)據(jù)結(jié)構(gòu)祝旷，強(qiáng)在聯(lián)結(jié)操作、多對一嘶窄、多對多關(guān)系的簡潔表達(dá)

    • 高度關(guān)聯(lián)數(shù)據(jù)

  • 文檔數(shù)據(jù)庫

    • 模式靈活性怀跛，局部性帶來較好性能

    • 無模式

    • 數(shù)據(jù)結(jié)構(gòu)是隱式的，讀取時才解釋

    • 一般為xml柄冲、json吻谋、二進(jìn)制變體等結(jié)構(gòu)化數(shù)據(jù)

    • 類似文檔結(jié)構(gòu)，即一系列關(guān)系數(shù)據(jù)现横，適合使用文檔數(shù)據(jù)庫漓拾，一次完成加載

    • 局限性在于嵌套層次的訪問路徑，不能直接引用文檔中的嵌套項

    • 對于聯(lián)結(jié)支持不足

    • 適合一對多戒祠，無關(guān)系骇两，不適合多對多關(guān)系的數(shù)據(jù)模型

數(shù)據(jù)查詢語言

聲明式

• 聲明式語言只需要指定所需數(shù)據(jù)模式、結(jié)果滿足條件姜盈、數(shù)據(jù)轉(zhuǎn)換（排序低千、分組、聚合）馏颂，而不需要關(guān)心具體實現(xiàn)過程和細(xì)節(jié)

• 比命令式API更加簡潔和容易使用示血，隱蔽了內(nèi)部實現(xiàn)細(xì)節(jié)

• 例如數(shù)據(jù)庫系統(tǒng)的查詢優(yōu)化器會決定采取哪些索引和聯(lián)結(jié)棋傍，以及用何種順序來執(zhí)行查詢的各個語句

命令式

• 命令式語言告訴計算機(jī)以特定順序執(zhí)行某些操作，可以完全推理整個過程矾芙，逐行遍歷代碼舍沙、評估相關(guān)條件、更新對應(yīng)的變量等

MapReduce

• 既不是聲明式查詢語言剔宪，也不是一個完全命令式的查詢API

• 它介于兩者之間，查詢邏輯用代碼實現(xiàn)壹无，基于許多函數(shù)式編程語言中的map

• MapReduce是一個相當(dāng)?shù)讓拥木幊棠Ｐ痛腥蓿糜谟嬎慵荷戏植紙?zhí)行

圖狀數(shù)據(jù)模型

例子

• 社交網(wǎng)絡(luò)

  頂點是人，邊表示與其他人的關(guān)系

• WEB圖

  頂點是網(wǎng)頁斗锭，邊表示與其他頁面的HTML鏈接

• 公路/鐵路網(wǎng)

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

小結(jié)

數(shù)據(jù)模型演進(jìn)過程

• 層次模型

  像一顆大樹，不利于表示多對多關(guān)系

• 關(guān)系模型

  文檔數(shù)據(jù)庫

  圖數(shù)據(jù)庫

第3章 數(shù)據(jù)存儲與檢索

數(shù)據(jù)庫核心：數(shù)據(jù)結(jié)構(gòu)

• 索引

  • 優(yōu)點：加快檢索

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

• 種類

  • 聚集索引

    索引中直接保存行數(shù)據(jù)

  • 非聚集索引

    存儲行數(shù)據(jù)的引用帮毁，需要再到實際存儲行數(shù)據(jù)的索引上檢索，回表查詢

• 覆蓋索引

  檢索數(shù)據(jù)就在索引上存儲

• 多列索引

• 哈希索引

  • 優(yōu)點：訪問快

  • 缺點：內(nèi)存占用豺撑、哈希沖突的解決烈疚、隨機(jī)IO訪問、區(qū)間查詢效率不高不能高效范圍查詢

• 全文搜索聪轿、模糊索引

• 倒排表

  • Lucene是Elasticsearch和Solr的索引引擎

  • Key記錄詞條爷肝，Value記錄包含該詞條的文檔ID

    布隆過濾器

  • 避免頻繁無效操作

    SSTables（Sorted String Table） 排序字符串表

  • 要求每個鍵在每個段文件中只能出現(xiàn)一次

  • 合并后的鍵是有序的

  • LSM Tree（Log Structured Merge Tree）

    一種分層、有序陆错、面向磁盤的數(shù)據(jù)結(jié)構(gòu) 其核心思想是充分利用磁盤的順序?qū)懶阅芤h(yuǎn)高于隨機(jī)寫性能這一特性灯抛，將批量的隨機(jī)寫轉(zhuǎn)換為一次性的順序?qū)?/p>

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

  • CURD

    • 新增

      追加一條新記錄

    • 更新

      追加一條新記錄

    • 刪除

      追加一條刪除記錄

• B-Tree

  • 將數(shù)據(jù)庫分解成固定大小的塊或頁，一般為4KB

  • 頁是內(nèi)部讀寫的最小單元

  • 這種數(shù)據(jù)結(jié)構(gòu)的設(shè)計更接近底層硬件音瓷，因為硬盤也是以固定大小的塊排列

  • 數(shù)據(jù)更新策略

  • 預(yù)寫日志（WAL）+ 覆蓋頁

    重做日志

    僅支持追加修改的文件对嚼，每個B-Tree修改必須先更新WAL然后再修改樹本身的頁， 當(dāng)數(shù)據(jù)庫崩潰后需要恢復(fù)時绳慎，該日志用于將B+Tree恢復(fù)到最近一致的狀態(tài)

  • 寫時復(fù)制

    修改的頁被寫入不同的位置纵竖，樹中頁的新版本創(chuàng)建后指向新的位置

    這是類似一種快照隔離、可重復(fù)讀的設(shè)計思想

  • B+Tree

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

• 追加日志文件的實現(xiàn)

  • 重要問題

    • 1. 文件格式。更快更簡單的方法是使用二進(jìn)制格式
    • 2. 刪除記錄声邦。進(jìn)行刪除的特殊標(biāo)記
    • 3. 崩潰恢復(fù)乏奥。 先寫日志，通過日志來恢復(fù)和回放
    • 4. 部分寫入問題亥曹。 追加日志進(jìn)行校驗和保證完整性
    • 5. 并發(fā)控制邓了。 嚴(yán)格的先后順序追加恨诱，一個寫線程，多個讀線程

  • 追加式設(shè)計優(yōu)點

    • 1.磁盤寫入友好骗炉。 追加和分段合并主要是順序?qū)懻毡Γ入S機(jī)寫入快，特別是在旋轉(zhuǎn)式磁性硬盤上

    • 2.并發(fā)句葵、崩潰恢復(fù)友好厕鹃。 不必?fù)?dān)心錯寫問題

    • 3.避免碎片化。 根據(jù)規(guī)則進(jìn)行舊分段合并乍丈，避免磁盤碎片化剂碴，提高利用率

• 事務(wù)處理與分析處理

  • 事務(wù)屬性

    ACID 原子性、一致性轻专、隔離性忆矛、持久性

• OLTP&OLAP

  • 數(shù)據(jù)倉庫

    不影響OLTP業(yè)務(wù)

    一般數(shù)倉是OLTP系統(tǒng)的只讀副本

    數(shù)據(jù)轉(zhuǎn)換，提取-轉(zhuǎn)換-加載

  • 列式存儲

    按列進(jìn)行數(shù)據(jù)聚合存儲

    列存儲壓縮

    同一列數(shù)據(jù)類型一致请垛，便于進(jìn)行壓縮

    列存儲排序

    縮小數(shù)據(jù)范圍

    利于進(jìn)行列壓縮

    隨機(jī)性大催训，不容易真正進(jìn)行壓縮

    列存儲寫入

    寫入相對困難

  • LSM-Tree解決方案

    位圖索引 & 游程編碼

    Clickhouse，Cassandra宗收，Hbase

聚合

COUNT漫拭、SUM、AVG镜雨、MIN嫂侍、MAX

物化視圖，其實就是預(yù)先查詢好荚坞，根據(jù)業(yè)務(wù)數(shù)據(jù)的更新來連鎖更新挑宠，將計算前置

小結(jié)

• 1. OLTP面向用戶，業(yè)務(wù)查詢颓影、事務(wù)請求多各淀，數(shù)據(jù)量小，對性能要求高
• 2. OLAP面向數(shù)據(jù)決策用戶诡挂，請求量低碎浇，但數(shù)據(jù)查詢量大
• 3. OLTP主要存儲引擎

  • ① 日志結(jié)構(gòu)流派

    只允許追加式更新文件和刪除過時的文件，但不會修改已寫入的文件

    BitCask璃俗、SSTables奴璃、LSM-Tree、LevelDB城豁、Cassandra苟穆、HBase、Lucene

  • ② 原地更新流派

    將磁盤視為可覆蓋的一組固定大小的頁，貼近硬件磁盤結(jié)構(gòu)的設(shè)計

    B-Tree雳旅、InnoDB

第4章 數(shù)據(jù)編碼與演化

數(shù)據(jù)編碼格式

• 編碼數(shù)據(jù)格式

  JSON跟磨、XML、protobuf攒盈、Thrift抵拘、Avro

• 數(shù)據(jù)存儲、通信場景

  Rest型豁、RPC僵蛛、消息傳遞

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

  語言的特定格式問題

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

  為了在相同對象類型中恢復(fù)數(shù)據(jù)迎变，解碼過程需要能夠?qū)嵗我獾念惗胀@個過程存在一些安全問題，容易遭到惡意攻擊

  缺乏數(shù)據(jù)變更帶來的向前氏豌、向后兼容問題

  效率問題，比如Java內(nèi)置序列化性能較差热凹、編碼臃腫

  第三方序列化的問題

  數(shù)字編碼的模糊之處

  XML泵喘、CSV無法區(qū)分?jǐn)?shù)字和由數(shù)字組成的字符串

  JSON區(qū)分字符串和數(shù)字，但不區(qū)分整數(shù)般妙、浮點數(shù)纪铺，并且不指定精度

  JSON、XML對Unicode字符串支持友好

  不支持二進(jìn)制字符串碟渺，通過Base64將二進(jìn)制數(shù)據(jù)編碼為文本來解決這個限制

• 二進(jìn)制編碼

  結(jié)構(gòu)緊湊鲜锚，效率高，節(jié)省空間

  可讀性差

• JSON的二進(jìn)制編碼

  • MessagePack苫拍，二進(jìn)制編碼

  • Thrift芜繁、protobuf

    字段標(biāo)簽和模式演化

    字段位置、標(biāo)簽記錄

    數(shù)據(jù)類型和模式演化

    精度丟失風(fēng)險

  • Avro

    讀模式

    寫模式

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

數(shù)據(jù)流模式

• 通過數(shù)據(jù)庫

• 通過服務(wù)調(diào)用

  • 遠(yuǎn)程調(diào)用的問題

    • 1. 網(wǎng)絡(luò)請求是不可預(yù)測的绒极，遠(yuǎn)程服務(wù)響應(yīng)慢骏令、網(wǎng)絡(luò)問題丟失等
    • 2. 超時情況的處理
    • 3. 重試帶來的冪等處理
    • 4. 較大對象的傳輸問題
    • 5. 不同進(jìn)程語言服務(wù)的數(shù)據(jù)轉(zhuǎn)換問題

  • RPC的數(shù)據(jù)編碼和演化

    Thrift、gRPC和Avro RPC可以根據(jù)各自編碼格式的兼容性規(guī)則進(jìn)行演化

    在SOAP中垄提，請求和響應(yīng)是用XML模式指定的

    Restful API通常使用JSON用于響應(yīng)

• 通過消息隊列

  • 消息隊列比RPC的優(yōu)點

    1. 系統(tǒng)間的緩沖區(qū)榔袋，如果接收方系統(tǒng)過載或不可用，可以暫時存儲铡俐，提高系統(tǒng)整體可用性

    2. 自動將消息重新發(fā)送到之前崩潰的系統(tǒng)凰兑，防止消息丟失

    3. 發(fā)送方不需要知道接收方IP、端口信息等

    4. 支持一條消息同時發(fā)給多個接收方

    5. 發(fā)送方审丘、接收方分離吏够，解耦

  • 消息隊列比RPC的差異

    通信是異步的

    不關(guān)心響應(yīng)結(jié)果

    不強(qiáng)制特定數(shù)據(jù)格式

    消息隊列產(chǎn)品 RabbitMQ、ActiveMQ、Kafka

小結(jié)

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

• JSON喉镰、XML旅择、CSV等文本格式非常普遍，主要特定數(shù)據(jù)類型的兼容支持問題

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

第二部分 分布式數(shù)據(jù)系統(tǒng)

分布式部署

目的

• 擴(kuò)展性

  突破單機(jī)能力

• 容錯與高可用性

  避免單機(jī)帶來的故障捺宗、破壞問題

• 延遲考慮

  就近部署柱蟀，提高響應(yīng)效率

第5章 數(shù)據(jù)復(fù)制

數(shù)據(jù)復(fù)制的方式

• 主從復(fù)制

  • 主從復(fù)制原理

    • 1. 指定某一個副本為主副本（主節(jié)點），當(dāng)寫數(shù)據(jù)時蚜厉，寫請求由主節(jié)點來處理并把新數(shù)據(jù)寫入主節(jié)點
    • 2. 其他副本則全部稱為從副本（從節(jié)點）长已，主副本寫入本地存儲后將數(shù)據(jù)更改通過復(fù)制的日志或更改流發(fā)送給所有從副本，然后從節(jié)點嚴(yán)格保持和主節(jié)點一樣的寫入順序?qū)懭氲綇墓?jié)點本地
    • 3. 客戶端讀取數(shù)據(jù)時可以從主節(jié)點昼牛、從節(jié)點上進(jìn)行术瓮，但是只有主節(jié)點接受寫請求

  • 數(shù)據(jù)復(fù)制的問題

    • 同步or異步

      • 同步復(fù)制

        同步復(fù)制的優(yōu)點是，確保副本之間數(shù)據(jù)一致性

        同步復(fù)制的缺點是贰健，延時高胞四，如果出現(xiàn)節(jié)點故障，寫入將阻塞且始終無法成功

      • 半同步

        至少有兩個節(jié)點擁有最新的數(shù)據(jù)副本（即主節(jié)點和一個同步從節(jié)點）

      • 全異步復(fù)制

        主節(jié)點一直可以響應(yīng)寫請求伶椿，吞吐性好辜伟，但是從節(jié)點可能遠(yuǎn)遠(yuǎn)落后主節(jié)點，也可能會有數(shù)據(jù)不一致脊另、持久性問題

        不靠譜較為折中的設(shè)計导狡，但是應(yīng)用也比較廣泛

    • 處理失敗副本

      • 從節(jié)點失效

        重啟后追趕主節(jié)點最新數(shù)據(jù)

      • 主節(jié)點失效

        1. 確認(rèn)主節(jié)點失效

           一般基于超時機(jī)制，節(jié)點之間頻繁地相互發(fā)送心跳存活消息尝蠕， 如果發(fā)現(xiàn)某一個節(jié)點在一段時間內(nèi)沒有響應(yīng)則認(rèn)為該節(jié)點失效

        2. 選舉新的主節(jié)點

           通過共識機(jī)制來投票選舉

           候選節(jié)點最好與原主節(jié)點的數(shù)據(jù)差異最小烘豌，這樣可以最小化數(shù)據(jù)丟失風(fēng)險

        3. 重新配置系統(tǒng)使新主節(jié)點生效

           請求路由控制

           多副本的一致性

      • 增加新的從節(jié)點

        1. 在某個時間點對主節(jié)點的數(shù)據(jù)副本產(chǎn)生一個一致性快照，這樣不會長時間鎖定整個數(shù)據(jù)庫

        2. 將此快照拷貝到新的從節(jié)點

        3. 從節(jié)點從拷貝來的數(shù)據(jù)中追趕主節(jié)點的最新數(shù)據(jù)同步

實現(xiàn)

MySQL看彼、SQL Server廊佩、Oracle

MongoDB

Kafka、RabbitMQ

• 復(fù)制日志的實現(xiàn)

• 基于語句的復(fù)制

  記錄每個寫請求并將語句作為日志發(fā)送給從節(jié)點

  • 問題

    非確定性函數(shù)靖榕，如時間函數(shù)标锄、隨機(jī)數(shù)函數(shù)不同副本可能產(chǎn)生不同結(jié)果

    副作用的語句，觸發(fā)器茁计、存儲過程料皇、用戶自定義函數(shù)等谓松，也可能產(chǎn)生不同結(jié)果

    自增列，所有副本必須按照完全相同順序執(zhí)行践剂，否則會產(chǎn)生不同結(jié)果

    如果存在多個并發(fā)執(zhí)行的事務(wù)時鬼譬，會有很大限制

• 基于預(yù)寫日志（WAL）復(fù)制

  • 適用

    日志結(jié)構(gòu)存儲引擎、采用覆蓋寫磁盤+預(yù)寫日志的存儲引擎都適合此類復(fù)制方式

  • 缺點

    復(fù)制方案和存儲引擎緊密耦合逊脯，如果數(shù)據(jù)存儲結(jié)構(gòu)优质、存儲引擎變化則會有很大影響和改變

  • 實現(xiàn)

    PostgreSQL、Oracle军洼、MySQL

• 基于行的邏輯日志復(fù)制

  • 復(fù)制和存儲引擎采用不同的日志格式巩螃，復(fù)制和存儲引擎邏輯剝離

  • 關(guān)系數(shù)據(jù)庫的邏輯日志一般指的是一系列記錄來描述數(shù)據(jù)表行級別的寫請求

    對于行插入，日志包含所有相關(guān)列的新值

    對于行刪除匕争，日志里有足夠的信息來唯一標(biāo)識已刪除的行避乏，通常是靠主鍵

    對于行更新，日志包含足夠的信息來唯一標(biāo)識更新的行甘桑，以及所有的新值

    如果一條事務(wù)涉及多行的修改拍皮，會產(chǎn)生多條日志記錄

    實現(xiàn)

    • MySQL使用基于二進(jìn)制日志binlog進(jìn)行復(fù)制

    • 基于觸發(fā)器的復(fù)制

      可以考慮基于應(yīng)用層代碼邏輯實現(xiàn)和控制

多主節(jié)點復(fù)制

• 特點

  多主節(jié)點接收寫操作，復(fù)制流程類似

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

  通常多主節(jié)點之間數(shù)據(jù)同步是異步復(fù)制

• 適用場景

  一個數(shù)據(jù)中心使用多主節(jié)點基本沒有太大意義跑杭，其復(fù)雜性已經(jīng)超過所能帶來的好處

  適合多數(shù)據(jù)中心

  適合應(yīng)用與網(wǎng)絡(luò)斷開后繼續(xù)工作的場景春缕，如IM多端數(shù)據(jù)同步、文檔協(xié)作編輯

  多主主從復(fù)制 vs 單主主從復(fù)制

• 性能

  容忍數(shù)據(jù)中心失效

  容忍網(wǎng)絡(luò)問題

• 問題

  處理多主的寫沖突艘蹋，實現(xiàn)收斂沖突解決的方式

  • 1. 給每個寫入分配唯一的ID，例如一個時間戳票灰，一個足夠長的隨機(jī)數(shù)女阀，一個UUID或者一個基于鍵-值的哈希，挑選最高ID的寫入作為勝利者屑迂，并將其他寫入丟棄
  • 2. 為每個副本分配一個唯一的ID浸策，并制定規(guī)則，例如序號高德副本寫入始終優(yōu)先于序號低的副本
  • 3. 以某種方式將這些值合并在一起惹盼，如5-7庸汗，A-C

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

       寫入時檢查

       讀取時檢查

多主節(jié)點模型的拓?fù)浣Y(jié)構(gòu)

多節(jié)點容錯性更好

多節(jié)點數(shù)據(jù)通信傳播復(fù)雜性增加

多節(jié)點數(shù)據(jù)復(fù)制覆蓋問題

時間戳無法保證副本時鐘

版本向量控制

無主節(jié)點復(fù)制

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

問題

• 多副本寫入性能

• 大部分ack

• 失效節(jié)點恢復(fù)上線后進(jìn)行數(shù)據(jù)追趕修復(fù)

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

實現(xiàn)

• Cassandra

復(fù)制滯后問題

• 滿足最終一致性

  寫主蚯舱，讀從分?jǐn)倝毫?/p>

• 追求一致性

  寫后讀

  讀寫均在主節(jié)點

• 單調(diào)讀

  用戶數(shù)據(jù)讀取固定在一個副本執(zhí)行

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

  比強(qiáng)一致性弱掩蛤，但比最終一致性強(qiáng)的保證

• 順序一致讀

  順序?qū)懭胪骰瑁荒墚a(chǎn)生亂序情況，包含數(shù)據(jù)上下文順序揍鸟，還有數(shù)據(jù)自身更新順序

  解決方案是兄裂，具有因果順序關(guān)系的寫入都交給一個分區(qū)副本來完成，但是效率和穩(wěn)定性有損失

第6章 數(shù)據(jù)分區(qū)

數(shù)據(jù)分區(qū)與數(shù)據(jù)復(fù)制

每個分區(qū)在多個節(jié)點都存有副本

鍵-值數(shù)據(jù)的分區(qū)

分區(qū)的目的是將海量數(shù)據(jù)平均分?jǐn)偟讲煌謪^(qū)節(jié)點

• 分?jǐn)偛痪鶆虻那闆r叫做數(shù)據(jù)傾斜，導(dǎo)致部分分區(qū)效率性能嚴(yán)重下降

• 熱點數(shù)據(jù)也會導(dǎo)致系統(tǒng)資源使用不均勻晰奖，過于集中于部分分區(qū)出現(xiàn)問題

基于關(guān)鍵字區(qū)間分區(qū)

• 指定一段段連續(xù)區(qū)間范圍（最小值谈撒、最大值、時間戳）

• 這些區(qū)間不一定非要均勻分布匾南，因為數(shù)據(jù)本身就可能不均勻

基于關(guān)鍵字哈希值分區(qū)

一個好的哈希函數(shù)可以處理數(shù)據(jù)傾斜并使其均勻分布啃匿，哈希能夠解決數(shù)據(jù)分布均勻的問題，但是也破壞了連續(xù)性數(shù)據(jù)的區(qū)間特性

一致性哈希

哈希分區(qū)的熱點午衰，數(shù)據(jù)傾斜問題

• 需要在切分鍵上增加隨機(jī)數(shù)或取模后綴進(jìn)行再次rehash來打散

• 需要額外維護(hù)元數(shù)據(jù)來映射打散數(shù)據(jù)立宜，還需要負(fù)責(zé)聚合這些數(shù)據(jù)

基于混合鍵分區(qū)

鍵的一部分標(biāo)識分區(qū)，另一部分用來記錄排序后的順序

分區(qū)與二級索引

基于文檔分區(qū)的二級索引（本地索引）

• 寫數(shù)據(jù)時臊岸，按切分鍵（如用戶ID）來路由到不同分區(qū)橙数，并在各自分區(qū)內(nèi)構(gòu)建二級索引（如性別-用戶ID關(guān)系）

• 讀數(shù)據(jù)時，如果使用到二級索引進(jìn)行檢索帅戒，會同時查詢所有分區(qū)中的二級索引拿到符合條件的數(shù)據(jù)然后做聚合返回

實現(xiàn)

MongoDB灯帮、Cassandra、Elasticsearch

• 基于詞條的二級索引分區(qū)（全局索引）

  • 構(gòu)建全局索引逻住，但是這個全局索引不僅僅存儲在某個單點上钟哥，而是根據(jù)索引檢索值路由到不同分區(qū)上

  • 優(yōu)點：客戶端只需要對包含詞條索引的分區(qū)發(fā)出一次請求，不需要遍歷所有分區(qū)即可拿到索引命中的數(shù)據(jù)瞎访，效率更高

  • 不足：寫入速度較慢且非常復(fù)雜腻贰，主要是因為單個文檔更新時，可能需要涉及多個二級索引的更新扒秸，而這些二級索引可能在不同分區(qū)節(jié)點上播演，造成寫放大問題；且這個更新過程一般都是異步的伴奥，不會立刻反應(yīng)在檢索上

• 分區(qū)再平衡

動態(tài)再平衡策略

為什么不用取模

• 節(jié)點樹變化写烤，數(shù)據(jù)到分區(qū)節(jié)點的路由關(guān)系變化，需要重新遷移進(jìn)行再平衡拾徙，成本巨大

• 固定數(shù)量的分區(qū)

• 創(chuàng)建遠(yuǎn)超實際節(jié)點數(shù)的分區(qū)數(shù)洲炊，然后為每個節(jié)點分配多個分區(qū)，比如10節(jié)點集群尼啡，每個節(jié)點分配100個邏輯分區(qū)

實現(xiàn)

Elasticsearch

• 動態(tài)分區(qū)

  • 每個分區(qū)只屬于一個節(jié)點暂衡，每個節(jié)點可以管理多個分區(qū)

  • 如果一個節(jié)點中數(shù)據(jù)量過大，會被限制分區(qū)大小崖瞭，避免傾斜

• 按節(jié)點比例分區(qū)

  • 自動與手動再平衡操作

  • 維護(hù)成本古徒，可操作維護(hù)性

• 請求路由

• 服務(wù)發(fā)現(xiàn)問題

• 處理策略

  • 1. 允許客戶端鏈接任意節(jié)點，如果節(jié)點恰好擁有所請求的分區(qū)读恃，則直接處理該請求隧膘，否則會將請求轉(zhuǎn)發(fā)到下一個合適的節(jié)點來處理
  • 2. 所有的客戶端請求都發(fā)送到一個路由層代态，由路由層負(fù)責(zé)請求轉(zhuǎn)發(fā)到對應(yīng)的分區(qū)節(jié)點上。路由層不處理業(yè)務(wù)疹吃，只負(fù)責(zé)請求分發(fā)
  • 3. 客戶端感知分區(qū)和節(jié)點分配關(guān)系蹦疑。客戶端可以直接鏈接到目標(biāo)分區(qū)節(jié)點萨驶，不需要任何中介

• 并行查詢執(zhí)行

第7章 事務(wù)

深入理解事務(wù)

事務(wù)有其優(yōu)勢歉摧，也有自身局限性

ACID的含義

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

BASE的含義

基本可用性（Basically Available）、軟狀態(tài)（Soft state）核畴、最終一致性（Eventual consistency）

單對象膝但、多對象事務(wù)操作

修改多個對象的整體一致性、隔離性等

單對象寫入

修改單個對象的原子性谤草、隔離性等

多對象事務(wù)的必要性

• 關(guān)系數(shù)據(jù)模型中跟束，外鍵關(guān)系要求數(shù)據(jù)更新必須聯(lián)動

• 文檔數(shù)據(jù)模型中，由于缺少join功能支持丑孩，需要同時維護(hù)反范式多對象來更新

• 對于帶有二級索引的數(shù)據(jù)庫冀宴，需要維護(hù)事實表和二級索引的更新

處理錯誤和中止

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

• 考慮返回客戶端失敗，但是重試執(zhí)行成功導(dǎo)致的響應(yīng)結(jié)果與實際數(shù)據(jù)狀態(tài)不一致情況

• 重試需要設(shè)置次數(shù)上限温学，例如指數(shù)回退略贮，避免給系統(tǒng)負(fù)載帶來超負(fù)荷壓力

• 由臨時性故障引起的重試才有意義，永久性故障仗岖、錯誤導(dǎo)致的重試毫無意義

• 重試考慮冪等問題刨肃，避免重復(fù)

• 充分考慮重試的持久驅(qū)動，驅(qū)動進(jìn)程也出現(xiàn)異常則再無可重試驅(qū)動力

弱隔離級別

• 并發(fā)問題 / 競爭條件

  多個不同事務(wù)同時讀取或操作同一數(shù)據(jù)

• 弱隔離的目的

  提高性能箩帚，也要避免并發(fā)競態(tài)帶來的問題

• 讀-提交

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

  • 1. 讀數(shù)據(jù)庫時黄痪，只能看到已成功提交的數(shù)據(jù)紧帕，防止“臟讀”
  • 2. 寫數(shù)據(jù)庫時，只會覆蓋已成功提交的數(shù)據(jù)桅打，防止”臟寫”

• 實現(xiàn)讀-提交

  • 防止臟寫：對訪問數(shù)據(jù)對象上鎖（如行級鎖）保證同一時間一個事務(wù)進(jìn)行事務(wù)操作

  • 防止臟讀：多版本快照提供非鎖定讀的支持是嗜，可以讀已提交事務(wù)的最新數(shù)據(jù)，也可以讀最舊的數(shù)據(jù)

快照級別隔離與可重復(fù)讀

實現(xiàn) PostgreSQL挺尾、MySQL的InnoDB存儲引擎鹅搪、SQL Server迁央、Oracle

• 實現(xiàn)快照級別隔離

  • 寫鎖防止臟寫

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

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

    記錄多個事務(wù)在不同時間點的數(shù)據(jù)對象提交版本

    唯一、單調(diào)遞增的事務(wù)ID（txid）

• 一致性快照的可見性規(guī)則

  • 1. 每筆事務(wù)開始時蔗包，其他進(jìn)行中的事務(wù)對自身不可見
  • 2. 所有中止事務(wù)做的修改對自身不可見
  • 3. 較晚事務(wù)ID（晚于當(dāng)前事務(wù)）所做的修改對自身不可見
  • 4. 其他所有的寫入都對應(yīng)用查詢可見

• 索引與快照級別隔離

  • 追加式的B-Tree，每個寫入事務(wù)都會創(chuàng)建一個新的B-Tree root甫题，代表該時刻數(shù)據(jù)庫的一致性快照

  • 查詢根據(jù)特定快照B-Tree來實現(xiàn)隔離

  • 需要后臺進(jìn)程來執(zhí)行壓縮和垃圾回收

• 防止更新丟失

  • 寫事務(wù)并發(fā)帶來的問題

  • 解決方案

    • 原子寫操作

      單線程馁筐，順序?qū)懭?/p>

    • 顯式加鎖

      FOR UPDATE

    • 原子比較更新和設(shè)置 CAS（compare and set）

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

    • 多副本的沖突解決和復(fù)制

      多主節(jié)點或者無主節(jié)點中多副本，天然支持多個并發(fā)寫坠非，通常以異步方式來同步更新敏沉，因此也會出現(xiàn)多個最新的數(shù)據(jù)副本情況 該場景下加鎖、原子比較不適用

      解決方案是保留多個沖突版本炎码，由應(yīng)用層邏輯解決盟迟，或者依靠特定的數(shù)據(jù)結(jié)構(gòu)來解決，合并多版本

      最后寫入獲勝（LWW）

      容易丟失更新潦闲，但是是多數(shù)多副本數(shù)據(jù)庫的默認(rèn)配置

寫傾斜與幻讀

定義寫傾斜

• 原因

  多個事務(wù)讀取同一個數(shù)據(jù)對象攒菠，然后更新其中一部分或各自更新不同對象，造成寫傾斜

  涉及多個對象矫钓，單對象的原子操作不起作用

  對參與原子操作的對象進(jìn)行加鎖

• 總結(jié)

  由于有了不同隔離級別下支持的多版本非鎖定讀要尔，拿到非鎖定讀數(shù)據(jù)只是整個事務(wù)操作的一步，且這個數(shù)據(jù)在事務(wù)外還會進(jìn)行變化新娜，那就導(dǎo)致整體事務(wù)操作的原子性不可控赵辕，背離初衷產(chǎn)生一些問題

  幻讀

  實體化沖突

  將競態(tài)條件建立在可操作對象上進(jìn)行加鎖

串行化

最強(qiáng)的隔離級別

通過避免并發(fā)的方式解決并發(fā)問題

• 采用存儲過程封裝事務(wù)

  • 優(yōu)點

  • 缺點

    語義丑陋、過時概龄，缺乏函數(shù)庫支持

    管理还惠、調(diào)試、測試?yán)щy私杜，不易監(jiān)控和應(yīng)用層集成

    糟糕的存儲過程會給數(shù)據(jù)庫性能帶來極大影響

兩階段加鎖（2PL蚕键，tow-phase locking），比較標(biāo)準(zhǔn)的串行化方式

讀鎖定

寫鎖定

謂詞鎖

百度什么是“謂詞”衰粹？

 數(shù)理邏輯中表示一個個體的性質(zhì)和兩個或兩個以上個體間關(guān)系的詞

 謂詞鎖不屬于某個特定對象锣光，而是面向某些特殊的搜索條件命中的對象，這里的代表可以是范圍查詢返回的行數(shù)據(jù)

索引區(qū)間鎖（next-key locking）

• 謂詞鎖性能不佳铝耻，事務(wù)中存在許多鎖誊爹，檢測匹配鎖就變得非常耗時

• 索引區(qū)間鎖是對謂詞鎖的簡化和優(yōu)化，它是對保護(hù)對象進(jìn)行擴(kuò)大化瓢捉，優(yōu)化可以理解為是把一條條具體明細(xì)鎖變成了范圍區(qū)間鎖频丘，效率是大大提升的

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

• 當(dāng)沒有合適的索引（即沒有合適的加鎖對象）進(jìn)行區(qū)間鎖施加泡态，會退化成鎖表操作

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

樂觀并發(fā)控制

第8章 分布式系統(tǒng)挑戰(zhàn)

故障與部分失效

不可靠的網(wǎng)絡(luò)

網(wǎng)絡(luò)問題

• 1. 請求可能在節(jié)點轉(zhuǎn)發(fā)中丟失
• 2. 請求可能在某個隊列中等待，無法馬上發(fā)送
• 3. 遠(yuǎn)程接受節(jié)點可能已經(jīng)宕機(jī)失效
• 4. 遠(yuǎn)程接收節(jié)點可能暫時無法響應(yīng)（GC某弦、負(fù)載過高等）
• 5. 遠(yuǎn)程接收節(jié)點已經(jīng)完成處理請求桐汤，但回復(fù)消息在回傳過程中丟失
• 6. 遠(yuǎn)程接收節(jié)點已經(jīng)完成處理請求而克，但是回復(fù)消息超時返回，發(fā)送方無法處理

不可靠的時鐘

時鐘和計時的重要性

• 測量持續(xù)時間

• 記錄業(yè)務(wù)時間節(jié)點

• 特定時間觸發(fā)業(yè)務(wù)

單調(diào)時鐘與墻上時鐘

• 墻上時鐘惊科，根據(jù)某個日歷返回當(dāng)前的日期與時間

• 服務(wù)器與NTP服務(wù)同步

• 單調(diào)時鐘拍摇，保證總是向前計數(shù)，不會出現(xiàn)回?fù)墁F(xiàn)象

• 單調(diào)時鐘適合測量持續(xù)時間段

知識馆截，真相與謊言

拜占庭將軍問題

第9章 一致性與共識

一致性保證

強(qiáng)一致性

弱一致性

最終一致性

可線性化（原子一致性充活、強(qiáng)一致性）

多副本下數(shù)據(jù)讀取結(jié)果在任何時刻都保持一致

對客戶端來說就像只有一個數(shù)據(jù)副本一樣

可線性化 vs 可串行化

• 可線性化

  • 讀寫單個對象的最新值保證

• 可串行化

  • 一般指事務(wù)隔離級別

  • 線性化的依賴條件

    加鎖與主節(jié)點選舉

    主節(jié)點選舉過程進(jìn)行加鎖保證線性化

    如使用Zookeeper

  • 約束與唯一性保證

    數(shù)據(jù)庫唯一索引

  • 跨通道的時間依賴

    如消息隊列中消息的順序性

  • 實現(xiàn)線性化系統(tǒng)

    主從復(fù)制（部分支持線性化）

    主節(jié)點復(fù)制到從節(jié)點滿足線性化

共識算法（可線性化）

通過共識協(xié)議防止多副本數(shù)據(jù)不一致，包含Zookeeper蜡娶，etcd等

共識算法就是基于強(qiáng)一致性來實現(xiàn)混卵，一定是可線性化的

• 多主復(fù)制（不可線性化）

  由于在多個節(jié)點執(zhí)行并發(fā)寫入，數(shù)據(jù)異步復(fù)制到其他節(jié)點窖张，因此寫入有可能出現(xiàn)沖突

• 無主復(fù)制（可能不可線性化）

  需要讀取多個節(jié)點數(shù)據(jù)幕随，但是無法確定節(jié)點數(shù)據(jù)間的差異

• CAP理論

  • 一致性(C)、可用性(A)宿接、分區(qū)容錯性(P)赘淮，系統(tǒng)只能同時滿足兩個特性

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

  • 關(guān)于CAP理論對于分布式系統(tǒng)設(shè)計有重要指導(dǎo)作用，它已被更精確的研究成果所取代

順序保證

事實證明副女，排序蛤高、可線性化與共識之間存在著聯(lián)系

順序與因果關(guān)系

• 因果關(guān)系對所發(fā)生的事件施加了某種排序

• 發(fā)送消息先于收到消息

• 問題出現(xiàn)在答案之前

• 如果系統(tǒng)服從因果關(guān)系所規(guī)定的的順序，則稱之為因果一致性

• 快照隔離提供了因果一致性碑幅，因為事務(wù)在數(shù)據(jù)讀取時可以按照事件發(fā)生的順序進(jìn)行選擇

• 因果順序并非全序

全序和偏序的差異體現(xiàn)在不同數(shù)據(jù)一致性模型

• 可線性化

  在一個可線性化的系統(tǒng)中戴陡，存在全序操作關(guān)系，能指出哪個操作在先沟涨，哪個在后

• 因果關(guān)系

  兩個非并發(fā)的操作一定存在因果關(guān)系（前后次序）恤批，否則不可排序

  實現(xiàn)可線性化是要保持因果關(guān)系

  單調(diào)遞增序列號排序

• 非因果序列發(fā)生器

  奇偶遞增，A：1裹赴，3喜庞，5 B：2，4篮昧，6

  時間戳遞增，最后寫獲勝

  按區(qū)間分配遞增序列笋妥，A：1-1000 B：1001-2000

  Lamport時間戳

  全序關(guān)系廣播

  利用明確的順序關(guān)系

分布式事務(wù)與共識

需要集群節(jié)點達(dá)成一致的場景

• 主節(jié)點選舉

• 原子事務(wù)提交

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

    • 1. 啟動一個分布式事務(wù)時懊昨，向協(xié)調(diào)者請求全局唯一的事務(wù)ID
    • 2. 協(xié)調(diào)者向每個參與者發(fā)送執(zhí)行事務(wù)的一階段準(zhǔn)備請求

    • 3. 參與者返回是否要提交的反饋、投票春宣，協(xié)調(diào)者記錄投票結(jié)果

         投票不可反悔酵颁、不可更改

    • 4. 協(xié)調(diào)者按照結(jié)果通知所有參與者二階段完成或者取消請求

  • 三階段提交 3PC

    分布式事務(wù)概念

    數(shù)據(jù)庫內(nèi)部的分布式事務(wù)

    MySQL Cluster的NDB存儲引擎

  • 異構(gòu)分布式事務(wù)

    存在兩種及以上不同的參與者實現(xiàn)技術(shù)

    數(shù)據(jù)庫 嫉你、緩存、消息隊列等

    Exactly-once消息處理

    XA交易

       并不是網(wǎng)絡(luò)協(xié)議躏惋，而是與事務(wù)協(xié)調(diào)者進(jìn)行通信的API
    
       停頓時仍持有鎖
    
       當(dāng)有節(jié)點不能正常工作時幽污，仍持有鎖阻止其他事務(wù)進(jìn)行并發(fā)操作
    

    從故障中恢復(fù)

       通過恢復(fù)日志、人為處理等方式
    

    分布式事務(wù)的限制

       協(xié)調(diào)者不支持?jǐn)?shù)據(jù)復(fù)制簿姨，意味著單點運行距误，本身就不是高可用
    
       協(xié)調(diào)者需要依賴日志進(jìn)行中斷事務(wù)的恢復(fù)和保證
    
       2PC并不是完備的事務(wù)提交保證機(jī)制，需要考慮它的異常場景帶來的問題
    

  • 支持容錯的共識

    共識算法的性質(zhì)

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

  • 共識算法

  VSR、Paxos域仇、Raft刑然、Zab

  • 全序關(guān)系廣播

    消息按照相同的順序發(fā)送到所有節(jié)點，有且只有一次

    相當(dāng)于持續(xù)的多輪共識

    由于協(xié)商一致性暇务，所有節(jié)點決定以相同的順序發(fā)送相同的消息

    由于誠實性泼掠，消息不會改變

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

    由于可終止性垦细，消息不會丟失

  • 主從復(fù)制與共識

    主節(jié)點寫入择镇，同步給從節(jié)點，是滿足共識的蝠检，這里主節(jié)點相當(dāng)于獨裁者角色

    但是分布式場景下沐鼠，選主過程中要避免出現(xiàn)多主

    世紀(jì)編號（epoch number）

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

    更高編號將獲勝

  • 共識的局限性

    投票過程是一個同步復(fù)制過程叹谁，節(jié)點數(shù)據(jù)復(fù)制大部分是異步的饲梭，故障切換時有數(shù)據(jù)丟失風(fēng)險

    共識體系需要嚴(yán)格的節(jié)點數(shù)才能運行，因此會引入投票限制的節(jié)點部署代價

    共識體系中節(jié)點不能動態(tài)添加焰檩、刪除憔涉，否則會影響選舉結(jié)果甚至出現(xiàn)問題

    共識體系依賴超時機(jī)制來檢測節(jié)點失效，超時時間的配置和網(wǎng)絡(luò)情況對故障切換和感知有很大影響

  • 成員與協(xié)調(diào)服務(wù)

    Zookeeper析苫、ETCD兜叨、Consul

    保存少量、可完全載入內(nèi)存（最終要寫入磁盤以支持持久性）的數(shù)據(jù)設(shè)計

    采用容錯的全序廣播算法在所有節(jié)點上復(fù)制這些數(shù)據(jù)從而實現(xiàn)高可靠

    適用場景

       節(jié)點任務(wù)分配
    
       作業(yè)調(diào)度
    
       負(fù)載平衡
    
       服務(wù)發(fā)現(xiàn)
    
       成員服務(wù)
    

第三部分 派生數(shù)據(jù)

第10章 批處理系統(tǒng)

第11章 流處理系統(tǒng)

第12章 數(shù)據(jù)系統(tǒng)的未來

本文由博客一文多發(fā)平臺 OpenWrite 發(fā)布衩侥！