典型分布式系統(tǒng)分析：Dynamo

本文是典型分布式系統(tǒng)分析系列的第四篇，主要介紹 Dynamo，一個(gè)在 Amazon 公司內(nèi)部使用的去中心化的、高可用的分布式 key-value 存儲(chǔ)系統(tǒng)。

在典型分布式系統(tǒng)分析系列的第一篇 MapReduce 中提出了本系列主要關(guān)心的問題：

系統(tǒng)在性能、可擴(kuò)展性、可用性、一致性之間的衡量，特別是CAP
系統(tǒng)的水平擴(kuò)展是如何實(shí)現(xiàn)的，是如何分片的
系統(tǒng)的元數(shù)據(jù)服務(wù)器的性能、可用性
系統(tǒng)的副本控制協(xié)議，是中心化還是去中心化
對于中心化副本控制協(xié)議，中心是如何選舉的
系統(tǒng)還用到了哪些協(xié)議、理論、算法

本文的核心目的也是對這些問題進(jìn)行解答。

本文地址：http://www.rzrgm.cn/xybaby/p/13944662.html

Dynamo簡介

Dynamo 與之前分析過的 Bigtable，或者筆者使用最多的 NoSql MongoDB 的最大區(qū)別，我認(rèn)為是去中心化（decentralized）。在 Dynamo 中使用的各種技術(shù)，如 Vector Clock、Consistent Hash、Gossip 等，一定程度上來說都是因?yàn)槿ブ行幕?/p>

這里所謂的去中心化，就是在副本集（replicaset）中沒有中心節(jié)點(diǎn)，所有節(jié)點(diǎn)的地位是平等的，大家都可以接受更新請求，相互通過協(xié)商達(dá)成數(shù)據(jù)的一致。其優(yōu)點(diǎn)在于可用性分廠強(qiáng)，但一致性比較弱，基本上都是最終一致性（eventually-consistent），因此，可以說是在 CAP 中選擇了 A - Availability。

而去中心化的對立面 -- 中心化，已經(jīng)在文章帶著問題學(xué)習(xí)分布式系統(tǒng)之中心化復(fù)制集中做了詳細(xì)介紹，簡而言之，副本集的更新由一個(gè)中心節(jié)點(diǎn)（Leader、Primary）來執(zhí)行，最大程度保障一致性，如果中心節(jié)點(diǎn)故障，即使有主從切換，也常常導(dǎo)致數(shù)十秒的不可用，因此，可以說是在 CAP 中選擇了 C - Consistency 。

如何在一致性與可用性之間權(quán)衡，這取決于具體的業(yè)務(wù)需求與應(yīng)用場景。Dynamo 是在 Amazon 內(nèi)部使用的一個(gè)分布式 KV 存儲(chǔ)系統(tǒng)，而 Amazon 作為一個(gè)電商網(wǎng)站，高可用是必須的，“always-on”。即使偶爾出現(xiàn)了數(shù)據(jù)不一致的情況，業(yè)務(wù)也是可以接受的，而且相對來說也比較好處理不一致，比如論文中提到購物車的例子。

這里需要注意的是，Dynamo 和 DynamDB 是兩個(gè)不同的東西。前者是 Amazon 內(nèi)部使用的kv存儲(chǔ)，在07年的論文 Dynamo: Amazon's Highly Available Key-value Store 面世；而后者是 AWS 提供的 NoSql 數(shù)據(jù)存儲(chǔ)服務(wù)，始于2012。

Dynamo詳解

有意思的是，在論文中，并不存在一張所謂的架構(gòu)圖，只有一張表，介紹了Dynamo使用的一些通用技術(shù)：

focuses on the core distributed systems techniques used in Dynamo: partitioning, replication, versioning, membership, failure handling and scaling.

The main contribution of this work for the research community is the evaluation of how different techniques can be combined to
provide a single highly-available system.

正是通過組合這些廣為人知（well-known）的技術(shù)，實(shí)現(xiàn)了這么一個(gè)高可用的存儲(chǔ)系統(tǒng)。

接下里就具體看看在 Dynamo 中是如何應(yīng)用這些技術(shù)解決相關(guān)的問題。

Consistent hash

Dynamo 采用了一致性哈希（consistent hash）作為數(shù)據(jù)分片（data partition）方式，之前在帶著問題學(xué)習(xí)分布式系統(tǒng)之?dāng)?shù)據(jù)分片已經(jīng)介紹過不同的數(shù)據(jù)分片方式，也包括一致性哈希。簡而言之，Consistent hash：

是分布式哈希表（DHT， distribution hash table）的一種具體實(shí)現(xiàn)
元數(shù)據(jù)（數(shù)據(jù)到存儲(chǔ)節(jié)點(diǎn)的映射關(guān)系）較少
在存儲(chǔ)節(jié)點(diǎn)加入、退出集群時(shí)，對集群的影響較小
通過引入虛擬節(jié)點(diǎn)（virtual node），能充分利用存儲(chǔ)節(jié)點(diǎn)的異構(gòu)信息

一般來說，partition 和 replication 是兩個(gè)獨(dú)立的問題，只不過在 Dynamo 中，二者都是基于 consistent hash。

假設(shè)副本集數(shù)量為 N，那么一個(gè) key 首先映射到對應(yīng)的 node（virtual node），這個(gè)節(jié)點(diǎn)被稱之為 coordinator，然后被復(fù)制到這個(gè)coordinator順時(shí)針的 N - 1 個(gè)節(jié)點(diǎn)上，這就引入了另一個(gè)概念 preference list，即一個(gè) key 應(yīng)該被存儲(chǔ)的節(jié)點(diǎn)列表。

如上圖所示， Key K 對應(yīng)的 coordinator 為 node B，與此同時(shí)，Node C, D 也會(huì)存儲(chǔ) key K 的數(shù)據(jù)，即其 preference list 為 [B、C、D...]

有兩點(diǎn)需要注意：

上述的 node 都是虛擬節(jié)點(diǎn)，那么為了容錯(cuò)，preference list 應(yīng)該是不同的物理節(jié)點(diǎn)，因此可能跳過環(huán)上的某些虛擬節(jié)點(diǎn)
副本集為 N 時(shí)，preference list 的長度會(huì)大于 N，這也是為了達(dá)到"always writeable“的目標(biāo)，后面介紹sloppy quorum 和 hinted handoff 會(huì)再提及。

Object versioning（vector clock）

在去中心化副本集中，每個(gè)節(jié)點(diǎn)都可以接受數(shù)據(jù)的讀寫，可能是因?yàn)槟承?client 無法連接上 coordinator，也可能是為了負(fù)載均衡。如果多個(gè)節(jié)點(diǎn)并發(fā)接受寫操作，那么可以使用對象版本化（object versioning）來維護(hù)不同節(jié)點(diǎn)上數(shù)據(jù)的一致性視圖。在 Dynamo 中，則是使用了向量時(shí)鐘 vector clock 來確定寫操作之間的順序。

vector clock 為每個(gè)節(jié)點(diǎn)記錄一個(gè)遞增的序號，該節(jié)點(diǎn)每次操作的時(shí)候，其序號加 1，節(jié)點(diǎn)間同步數(shù)據(jù)、以及從節(jié)點(diǎn)讀取數(shù)據(jù)時(shí)，也會(huì)攜帶對應(yīng)的版本號。

如上圖所示，副本集由Sx, Sy, Sz三個(gè)節(jié)點(diǎn)組成，開始的時(shí)候序號都為0，接下來對某個(gè) key 有以下操作:

節(jié)點(diǎn)Sx接受寫操作，value 為 D1，對應(yīng)的 vector clock 為[Sx, 1]
節(jié)點(diǎn)Sx再次接受寫操作，value 變?yōu)?D2，對應(yīng)的 vector clock 為[Sx, 2]
該數(shù)據(jù)（連同 vector clock）被復(fù)制到了節(jié)點(diǎn) Sy，Sz
同時(shí)發(fā)生了一下兩個(gè)操作
- 節(jié)點(diǎn) Sy 接受寫操作，value 變?yōu)?D3，對應(yīng)的 vector clock 為 ([Sx, 2], [Sy, 1])
- 節(jié)點(diǎn) Sz 接受寫操作，value 變?yōu)?D4，對應(yīng)的 vector clock 為 ([Sx, 2], [Sz, 1])
Sy、Sz 將數(shù)據(jù)同步到 Sx，D3、D4 對應(yīng)的版本號不具備偏序關(guān)系（所謂的偏序關(guān)系，即A向量中的每一維都與大于等于B向量的相應(yīng)維），那么就沒法確定這個(gè) key 對應(yīng)的 value 應(yīng)該是 D3，還是 D4，因此這兩個(gè)值都會(huì)被存下。

Both versions of the data must be kept and presented to a client (upon a read) for semantic reconciliation.

直到在Sx上發(fā)生了讀操作，讀操作的返回值就應(yīng)該是就是 D3、D4 的列表，客戶端決定如何處理沖突，然后將沖突解決后的值 D5 寫到Sx，向量時(shí)鐘為 [(Sx, 3), (Sy, 1), (Sz, 1)]。此時(shí)D5 與 D3、D4 間顯然有了偏序關(guān)系。

但在上述第六步，如果在節(jié)點(diǎn) Sy 上同時(shí)也發(fā)生 “讀數(shù)據(jù) -- 沖突解決” 的過程，寫入D6 [(Sx, 3), (Sy, 2), (Sz, 1)]，那么D5、D6又會(huì)沖突。

由上可以看到，vector clock 會(huì)自動(dòng)合并有偏序關(guān)系的沖突。但邏輯上并發(fā)時(shí)，vector clock 就無能為力，這時(shí)如何解決沖突就面臨兩個(gè)問題

第一：在何時(shí)解決沖突？

是在寫數(shù)據(jù)的時(shí)候，還是讀數(shù)據(jù)的時(shí)候。與眾不同的是，Dynamo 選擇了在讀數(shù)據(jù)的時(shí)候來解決沖突，以保證永遠(yuǎn)可寫（always writeable）。當(dāng)然，只有在讀數(shù)據(jù)的時(shí)候才來處理沖突，也可能導(dǎo)致數(shù)據(jù)長期處于沖突狀態(tài) -- 如果遲遲沒有應(yīng)用來讀數(shù)據(jù)的話。

第二：誰來解決沖突？

是由系統(tǒng)（及Dynamo自身）還是由應(yīng)用？系統(tǒng)缺乏必要的業(yè)務(wù)信息，很難在復(fù)雜的情況下做出合適的選擇，因此只能執(zhí)行一些簡單粗暴的策略，比如 last write win，而這又依賴于 global time，需要配合NTP 一同使用。Dynamo 則是交由應(yīng)用開發(fā)人員來處理沖突，因?yàn)榫唧w的應(yīng)用顯然更清楚怎么處理特定環(huán)境下的沖突。

那這是否增加了開發(fā)人員的負(fù)擔(dān)？在Amazon的技術(shù)架構(gòu)中，一直都是堅(jiān)持去中心化、面向服務(wù)的設(shè)計(jì)，“Design for failure ” 的設(shè)計(jì)原則已經(jīng)成為了系統(tǒng)架構(gòu)的基本原則，因此這對 Amazon 的程序來說并沒有額外的復(fù)雜度。

Quorum

Quorum 是一套非常簡單的副本管理機(jī)制，簡而言之，N 個(gè)副本中，每次寫入要求 W 個(gè)副本成功，每次讀取從 R 個(gè)副本讀取，只要 W+R > N，就能保證讀取到最新寫入的數(shù)據(jù)。

這個(gè)機(jī)制很直觀，高中的時(shí)候就學(xué)過，W 和 R 之間一定會(huì)有交集。

當(dāng)然，在工程實(shí)踐中也不是只操作 W 或 R 個(gè)節(jié)點(diǎn)，而是只需等到 W 或 R 個(gè)節(jié)點(diǎn)的返回即可，比如在 Dynamo 中，操作都會(huì)發(fā)給 preference list 中的前 N 個(gè)活躍的節(jié)點(diǎn)。

Dynamo 中，允許通過配置 R、W、N 參數(shù)，使得應(yīng)用可以綜合考慮可用性、一致性、性能、成本等因素，選擇最適合具體業(yè)務(wù)的組合方式。這點(diǎn)在Cassandra、Mongodb中也都有相關(guān)體現(xiàn)。

不過需要注意的是，DDIA 中指出，即使使用了 quorum，保證了 W+R > N，也還是會(huì)有一些 Corner case 使得讀到過時(shí)的數(shù)據(jù)（stale data）

在不同的節(jié)點(diǎn)并發(fā)寫，發(fā)生了沖突，如果系統(tǒng)自動(dòng)處理沖突，使用了類似 LWW（Last Write Win）的仲裁機(jī)制，由于不同節(jié)點(diǎn)上的時(shí)鐘漂移，可能會(huì)出現(xiàn)不一致的情況
大多分布式存儲(chǔ)，并沒有隔離性 Isolation，因此讀寫并發(fā)時(shí)，可能讀到正在寫入的數(shù)據(jù)
如果寫失敗，即成功寫入的數(shù)量少于 W，已經(jīng)寫入的節(jié)點(diǎn)也不會(huì)回滾。
還有一種情況，就是 Dynamo 中采用的 Sloppy quorum

Sloppy quorum and hinted handoff

前面提到了preference list，即一個(gè) key 在環(huán)中的存儲(chǔ)位置列表，雖然副本集數(shù)量為 N，但 preference list 的長度一般會(huì)超過 N，這是為了保證 “always writable”。比如N=3，W=2 的情況，如果此時(shí)有2個(gè)節(jié)點(diǎn)臨時(shí)故障，那么按照嚴(yán)格（strict） quorum，是無法寫入成功的，但在松散（sloppy） quorum下，就可以將數(shù)據(jù)寫入到一個(gè)臨時(shí)節(jié)點(diǎn)。在 Dynamo 中，這個(gè)臨時(shí)節(jié)點(diǎn)就會(huì)加入到 preference list 的尾端，其實(shí)就是一致性哈希環(huán)上下一個(gè)本來沒有該分片的節(jié)點(diǎn)。

當(dāng)然，這個(gè)臨時(shí)節(jié)點(diǎn)知道這份數(shù)據(jù)理論上應(yīng)該存在的位置，因此會(huì)暫存到特殊位置。

The replica sent to temp node will have a hint in its metadata that suggests which node was the intended recipient of the replica

等到數(shù)據(jù)的原節(jié)點(diǎn)（home node）恢復(fù)之后，在將數(shù)據(jù)打包發(fā)生獲取，這個(gè)過程稱之為 hinted handoff

因此，sloppy quorums不是傳統(tǒng)意義上的Quorum，即使?jié)M足 W+R > N，也不能保證讀到最新的數(shù)據(jù)，只是提供更好的寫可用性。

Replica synchronization

hinted handoff 只能解決節(jié)點(diǎn)的臨時(shí)故障，考慮這么一個(gè)場景，臨時(shí)節(jié)點(diǎn)在將數(shù)據(jù)前一會(huì) home node 之前，臨時(shí)節(jié)點(diǎn)也故障了，那么home node 中的數(shù)據(jù)就與副本集中的其他節(jié)點(diǎn)數(shù)據(jù)不一致了，這個(gè)時(shí)候就需要先找出哪些數(shù)據(jù)不一致，然后同步這部分?jǐn)?shù)據(jù)。

由于寫入的 keys 可能在環(huán)中的任意位置，那么如何找出哪些地方不一致，從而減少磁盤IO、以及網(wǎng)絡(luò)傳輸?shù)臄?shù)據(jù)量，Dynamo 中使用了Merkle Tree。

在 Merkle Tree學(xué)習(xí) 這篇文章中，有比較清晰易懂的介紹，這里只簡單總結(jié)一下要點(diǎn)：

每個(gè)葉子節(jié)點(diǎn)對應(yīng)一個(gè)data block，并記錄其hash值，非葉子節(jié)點(diǎn)記錄其所有子節(jié)點(diǎn)的hash值
從根節(jié)點(diǎn)開始比較，如果hash值一致，就表示這兩棵樹一致，否則分別比對左右子樹
一致遞歸，直到葉子節(jié)點(diǎn)，只需拷貝不一致的葉子節(jié)點(diǎn)

具體 Dynamo 是如何應(yīng)用 Merkle Tree 的呢

物理節(jié)點(diǎn)為每個(gè)虛擬節(jié)點(diǎn)維護(hù)一棵獨(dú)立的 Merkle Tree
比較時(shí)，就按照 Merkle Tree 的作法，從根節(jié)點(diǎn)開始比較

Merkle Tree 加速了比對操作，但構(gòu)建一棵 Merkle Tree 也是較為耗時(shí)的過程，那么在加入或刪除節(jié)點(diǎn)的時(shí)候，某個(gè) virtual node 所維護(hù)的 key range 就會(huì)發(fā)生變化，那么就需要重新構(gòu)建這根 Merkle Tree。

節(jié)點(diǎn)加入、刪除的影響不止于此，比如在增加節(jié)點(diǎn)時(shí)，需要遷移一部分 key range，這就需要對原節(jié)點(diǎn)的存儲(chǔ)文件進(jìn)行掃描，找出這部分 keys , 然后發(fā)送到目標(biāo)節(jié)點(diǎn)，這會(huì)帶來巨量的IO操作（當(dāng)然，這高度依賴存儲(chǔ)引擎對文件的組織形式）。這些操作是會(huì)影響到線上服務(wù)的，因此只能在后臺緩慢執(zhí)行，效率很低，論文中提到上線一臺節(jié)點(diǎn)需要花費(fèi)幾乎一整天時(shí)間。

Advanced partition scheme

問題的本質(zhì)，在于數(shù)據(jù)的 partition 依賴于 virtual node 的位置，兩個(gè)相鄰virtual node 之間的 key range 就是一個(gè) partition，而每一個(gè)partition 對應(yīng)一個(gè)存儲(chǔ)單元。這就是論文中說到的

The fundamental issue with this strategy is that the schemes for data partitioning and data placement are intertwined.

data placement 就是指 data 的存放形式，其實(shí)就是 virtual node 在哈希環(huán)上的位置。

那么解決方案就是解耦 partitioning 和 placement，即數(shù)據(jù)的 partition 不再依賴 virtual node 在環(huán)上的絕對位置。

在Dynamo 中，改進(jìn)方案如下：將hash環(huán)等分為 Q 份，當(dāng)然 Q 遠(yuǎn)大于節(jié)點(diǎn)的數(shù)量，每個(gè)節(jié)點(diǎn)均為 Q/S 份partition（S 為節(jié)點(diǎn)數(shù)量），當(dāng)節(jié)點(diǎn)增刪時(shí)，只需要調(diào)整partition到節(jié)點(diǎn)的映射關(guān)系。

這就解決了前提提到的兩個(gè)問題：

節(jié)點(diǎn)增刪時(shí)，數(shù)據(jù)的轉(zhuǎn)移以 partition 為單位，可以直接以文件為單位，無需掃描文件再發(fā)送，實(shí)現(xiàn) zero copy，更加高效
一個(gè) partition 就是一個(gè) Merkle Tree，因此也無需重建 Merkle Tree

這種方案跟 redis cluter 的方案很像，redis cluter也是先劃分為 16384 個(gè)slot，根據(jù)節(jié)點(diǎn)數(shù)量大致均等的slot分配到不同的節(jié)點(diǎn)。

Failure Detection

有意思的是，Dynamo 認(rèn)為節(jié)點(diǎn)的故障是短時(shí)的、可恢復(fù)的，因此不會(huì)采取過激的自動(dòng)容錯(cuò)，即不會(huì)主動(dòng)進(jìn)行數(shù)據(jù)的遷移以實(shí)現(xiàn) rebalance。因此，Dynamo 才用顯式機(jī)制（explicit mechanism），通過管理員手動(dòng)操作，向集群中增刪節(jié)點(diǎn)。

A node outage rarely signifies a permanent departure and therefore should not result in rebalancing of the partition assignment or repair of the unreachable replicas.

這與另外一些系統(tǒng)不一樣，如果過半的節(jié)點(diǎn)認(rèn)為某個(gè)節(jié)點(diǎn)不可用，那么這個(gè)節(jié)點(diǎn)就會(huì)被踢出集群，接下來執(zhí)行容錯(cuò)邏輯。當(dāng)然，自動(dòng)容錯(cuò)是復(fù)雜的，要讓過半節(jié)點(diǎn)達(dá)成某個(gè)節(jié)點(diǎn)不可用的共識也是復(fù)雜的過程。

也許會(huì)有疑問，那 Dynamo 這種做法就不能及時(shí)響應(yīng)故障了？會(huì)不會(huì)導(dǎo)致不可用、甚至丟數(shù)據(jù)？其實(shí)之前提到，Dynamo有 Sloppy quorum 和 hinted handoff 機(jī)制，即使對故障的響應(yīng)有所滯后也是不會(huì)有問題的。

因此，Dynamo的故障檢測是很簡單的，點(diǎn)對點(diǎn)，A 訪問不到 B，A 就可以單方面認(rèn)為 B 故障了。一個(gè)例子，假設(shè)A在一次數(shù)據(jù)寫入中充當(dāng)Coordinator，需要操作到B，訪問不了B，那么就會(huì)在Preference list中找一個(gè)節(jié)點(diǎn)（如D）來存儲(chǔ)B的內(nèi)容。

Membership

在Dynamo中，并沒有一個(gè)元數(shù)據(jù)服務(wù)器（metadata server）來管理集群的元數(shù)據(jù)：比如partition對節(jié)點(diǎn)的映射關(guān)心。當(dāng)管理員手動(dòng)將節(jié)點(diǎn)加入、移除hash環(huán)后，首先這個(gè)映射關(guān)系需要發(fā)生變化，其次hash環(huán)上的所有節(jié)點(diǎn)都要知道變動(dòng)后的映射關(guān)系（從而也就知道了節(jié)點(diǎn)的增刪），達(dá)成一致性視圖。Dynamo使用了Gossip-Based協(xié)議來同步這些信息。

Gossip 協(xié)議這篇文章對Gossip協(xié)議有詳細(xì)的介紹，這里就不再贅述的。不過后面有時(shí)間可以看看 Gossip 在redis cluster中的具體實(shí)現(xiàn)。

Summary

回答文章開頭的問題

系統(tǒng)在性能、可擴(kuò)展性、可用性、一致性之間的衡量，特別是CAP

犧牲一致性，追求高可用

系統(tǒng)的水平擴(kuò)展是如何實(shí)現(xiàn)的，是如何分片的

使用一致性hash，先將整個(gè) hash ring 均為為Q 分，然后均等分配到節(jié)點(diǎn)

系統(tǒng)的元數(shù)據(jù)服務(wù)器的性能、可用性

無額外的元數(shù)據(jù)服務(wù)器，元數(shù)據(jù)通過Gossip 協(xié)議在節(jié)點(diǎn)間廣播

系統(tǒng)的副本控制協(xié)議，是中心化還是去中心化

去中心化

對于中心化副本控制協(xié)議，中心是如何選舉的

無

系統(tǒng)還用到了哪些協(xié)議、理論、算法

Quorum、 Merkle Tree、Gossip

在論文中介紹 Merkle Tree 時(shí)，用到了術(shù)語 anti-entropy，翻譯一下為反熵，讀書時(shí)應(yīng)該學(xué)習(xí)過熵這個(gè)概念，不過現(xiàn)在已經(jīng)忘光了。不嚴(yán)謹(jǐn)?shù)慕忉尀?熵為混亂程度，反熵就是區(qū)域穩(wěn)定、一致，gossip 也就是一個(gè) anti-entropy protocol。

非常有同感的一句話: 系統(tǒng)的可靠性和伸縮性取決于如何管理應(yīng)用相關(guān)的狀態(tài)