Designing Data-Intensive Applications 讀後心得 (1)

出處: https://www.tenlong.com.tw/products/9781449373320

這本書全面性地介紹分散式系統的概念，看完後可以對此領域有個概觀，日後知道有那些方法/工具可以運用，各自的限制在那。看完覺得很有幫助，這裡簡短地摘要我的理解。

為什麼需要知道分散式系統的概念？

先用別的領域舉例，想像我們需要設計一個 in-memory LRU cache。初步想法是用 hash table 存資料，如此一來可有 O(1) 讀寫效率。接著需要用 queue 記錄存取順序，在 cache 滿的時候可以 O(1) 移除太舊資料。

但是，有個難解的問題: 如何 O(1) 更新 queue 內存取的順序？比方說 cache size = 3，操作順序是: write x, y, z，此時 queue 內順序由舊到新是 x, y, z。若接著 read y，要調整順序為 x, z, y。

似乎不是容易的問題？若熟悉資料結構的效率，如下圖所示:

出處: https://www.bigocheatsheet.com/

可看出支援 O(1) 操作的資料結構其實沒幾個，然後明白適合管理存取記錄的結構是 doubly-linked list，因為刪除任意位置節點的效率是 O(1)。

在這樣的限制下，統合的作法如下:

1. 用 doubly-linked list 節點存 cache value。
2. 在 hash table 裡存 doubly-linked list 節點。
3. 調整存取記錄順序: 先用 hash table 取出節點，將它從 doubly-linked list 內刪除，再重新附加到 list 最後。

於是，全部操作都是 O(1) 了。

類似的情況，了解分散式系統有那些元件以及它們的限制，有助於組合出適合的架構。

分散式系統在解決什麼問題？

基本上是用多台機器搞定一台搞不定的問題。大致上有三種情況，會想分散成多台處理:

• 提升 availability (包含不停機更新服務)。
• 降低 latency (例如 CDN)。
• 提升 throughput。

複製資料到多台 (replication) 時，可同時滿足上述三種需求，困難的是如何維持同步？

Replication、Leader 和 Follower

最簡單也是最常用的作法是只有一個 leader，負責處理全部寫入，然後同步更新到其它 follower。為求效率，leader 不會等 follower 收完資料 (asynchrounous replication)，或是最多只等一個 follower。然後所有 replicas (leader + followers) 可以處理讀取。

leader 將更新的部份用 append-only 的方式寫到 logs 裡，這樣 followers 依序執行即可，方便追踪更新到什麼地方。log 資料格式從 high-level 到 low-level 有三種:

• statements: followers 和 leader 執行一樣的 statements。在有 non-deterministic 結果時會有問題 (例如 statement 內使用 now() 或 rand() 這類函數，不好處理)。題外話，Blockchain 採用這種作法，同步變得很簡單。但產生亂數 (commit and review) 變得費時且要留意許多細節 (這種作法又稱 commitment scheme)。
• logical (row-based) log: 執行後抽象化的資料格式。這種格式還有可供外部系統使用的好處。
• write-ahead log: 接近硬碟儲存格式，看起來更新方式最有效率，缺點是沒彈性，系統升級困難，也不能給外部系統使用。

如果有多種不同服務，像是 database 處理第一線資料，後面還有接 search engine 更新 index。要怎麼維持 single leader？畢竟 database replicas 之間有一個 leader，search engine replicas 之間也有一個 leader。

答案是建立兩者的更新方向: 讓 database 產生更新記錄 (change data capture, CDC)，然後作為 search engine 的輸入。這樣就不用擔心 database 和 search engine 資料不一致的問題。如下圖所示:

書中附圖

只有一個 leader 唯一的缺點是: leader 掛了 ，由誰接手的問題 (failover) 。比方說半自動由 DevOps 手動指定，或是全自動選出新的 leader。

這裡困難的點是在分散式系統裡，無法知道一個節點到底是真的掛了、暫時忙不過來還是網路不通等因素。唯一可行的作法是超時沒反應就當作掛了，另起 leader。全自動沒處理好，可能會有兩個 leader 同時在線服務進而引起 conflicts。

Multiple leader

雖說 single leader failover 有些麻煩，但和 multiple leader 處理 conflicts 的困難相比，還是 single leader 比較簡單。若要用 multiple leader，兩個 leader 又比 ≥ 3 個 leader 簡單，因為 ≥ 3 個時需要思考 topology 怎麼分 (ring? star? all-to-all?)。

發生 conflicts 時，樂觀的想法會用最後更新時間蓋掉「舊」資料，但是多台機器無法同步準確的時間，所以並不可靠。

Leaderless

除 single leader、multiple leader 外，還有 leaderless replication 可選。概念是假設有 n 個節點:

• client 必須寫入 w 個節點才算成功寫入。
• client 必須從 r 個節點讀到資料才算成功讀取。

只要 w + r > n，可保證 client 讀到最新的資料 (用版號區別)。如下圖所示:

書中附圖

這種 w + r > n 的讀寫，稱作 quorum reads/writes。缺點是讀寫都慢，優點是沒什麼特別狀況要處理。沒 leader 就不用擔心 leader 掛了要怎麼處理。

題外話，我喜歡這種「本來無一物，何處惹塵埃」的想法。像「no feature, no bug」也是如此。

Replication 其它問題

除怎麼選新 leader 外，確保 client 會讀到一致的資料，不是簡單的事。無法單靠 replicas 自行處理。得依寫入資料類型各別拆招。

• (例一) 社交網路的個人頁: 只有個人可更改，所以讀自己的個人頁時從 leader 讀，讀其他人個人頁時從 follower 讀。
• (例二) 寫入量不多時，記錄最後更新「時間」，同時各 replicas 也記錄並讓 client 知道他們最後同步到資料的「時間」。藉此選對 replicas。真的不行再從 leader 讀。

注意，在分散式系統裡無法精確地同步時間，要留意對時間需求的精確度。或是用保證遞增的版號識別。

若寫入量太大，單一 leader 無法處理，該怎麼辦呢？或是資料量太大，單一節點裝不下，或是讀取效率不佳，該怎麼辦呢？

Partitioning (Sharding)

只時可用 partitioning，也就是將資料切成沒有交集的 partition，存到不同節點上。

作者提到命名很多，不過 partitioning 最多人提到，所以他用 partitioning 表示這概念:

What we call a partition here is called a shard in MongoDB, Elasticsearch, and SolrCloud; it’s known as a region in HBase, a tablet in Bigtable, a vnode in Cassandra and Riak, and a vBucket in Couchbase. However, partitioning is the most established term, so we’ll stick with that.

首先要明白 partitioning 和 replication 設計上互相獨立，可以有多個 partition，每個 partition 各自作自己的 replication。如下圖所示:

書中附圖

partition 的主要概念是用 primary key 將資料完全分散到不同 partition 處理，主要的問題是:

如何分散？

用 key 或 hash(key) 設互斥範圍給不同 partitions。用 hash 的好處是分佈比較平均。這裡的 hash 不用有密碼學安全性。分得夠散即可。

如何建 secondary index？

• Document-partitioned indexes (local indexes): 各個 partition 自己存自己資料範圍的 secondary index。client 必須和全部 partition 要資料。好處是 database 可保證資料和 index 一致性。
• Term-partititoned indexes (global indexes): partition 存不同的 secondary index，但是存該 index 全部資料。所以 client 只要向一個 partition 發 request。缺點是 database 非同步更新 index，會有從 secondary index 讀到舊資料的風險。

如何將 client request 導向對應的 partition？

如下圖所示，有三種選擇:

許多分散式系統是引入另一個服務作 routing。如下圖所示:

書中附圖

ZooKeeper 是一個支援 linearizability 的 key-value store。優點是它有 high availability、linearizability (任何節點看到的讀寫順序一致)，因此，任何難搞怕有 conflict 的東西都可用它解決 — 例如選出唯一的新 leader。缺點是慢。

小結

看完書上的介紹，其實最佳作法是盡可能用一台機器搞定需求 (scale up)。真有必要再分散 (scale out)。 不要為分散而分散，引入不必要的複雜。

高 C/P 值的演進順序是:

1. 先用一台搞定 (scale up)。
2. 有 high availability / latency / read throughput 需求時增加 replications，採用 single leader + 手動 failover。
3. 有進一步讀或寫 scalability 需求時，使用 partitioning。
4. 不得已要跨節點同步操作時，使用 ZooKeeper 之類的服務搭配相關技巧 (這部份我還需消化，日後補述)。

若只需要用一家 database，可先研究這家 database 如何支援這些基本需求。然後加減看進階需求 (automatic failover、multiple master + conflict resolution、secondary index on partitions、distributed transactions 等)。我猜知名常用的 database 應該都支援吧，只是要知道它採取那種方式實作，比較好掌握可能的限制。

相關文章

• Designing Data-Intensive Applications 讀後心得 (1): 談分散式系統的 replication 和 partitioning。
• Designing Data-Intensive Applications 讀後心得 (2): 談單一節點的 transactions 是什麼。
• Designing Data-Intensive Applications 讀後心得 (3): 談跨節點維持一致資料的方法。
• Designing Data-Intensive Applications 讀後心得 (4): 前三篇挑重點章節講，這篇依章節順序摘要各章內容，大概做個記錄。