分布式鍵值系統(tǒng)Amazon Dynamo簡介

• • Dynamo采用的技術(shù)
  • • 虛擬節(jié)點
    • Gossip協(xié)議
    • NRW
    • Vector Clock
    • 讀寫流程
  • 參考鏈接

---

Dynamo采用的技術(shù)

問題采用的技術(shù)

數(shù)據(jù)分布	改進的一致性哈希（DHT），采用了虛擬節(jié)點技術(shù)
復(fù)制協(xié)議	復(fù)制寫協(xié)議（Replicated-write protocal，NRW參數(shù)可調(diào)）
數(shù)據(jù)沖突處理	向量時鐘
臨時故障處理	數(shù)據(jù)回傳機制（Hinted handoff）
永久故障的恢復(fù)	Merkle哈希樹，簡單講就是二叉樹的復(fù)制
成員資格及錯誤檢測	基于Gossip的成員資格和錯誤檢測協(xié)議

虛擬節(jié)點

虛擬節(jié)點的分配有如下兩種方式：

隨機分配

• 該方法可以保證負載分配的比較平均，但是這個方法的問題是可控性較差，新節(jié)點加入、離開系統(tǒng)時，急群眾的原有節(jié)點都需要掃描所有的數(shù)據(jù)從而找出新節(jié)點的書絕，Merkle樹也要全部更新；另外增量歸檔、備份變得幾乎不可能。

數(shù)據(jù)范圍等分+隨機分配

• 將數(shù)據(jù)的哈希空間等分為$Q=N?S$份（N=機器個數(shù)，S=每臺機器的虛擬節(jié)點數(shù)），然后每臺機器隨機選擇S個分割點作為Token，每臺機器對各個數(shù)據(jù)范圍分別維護一顆Merkle樹。新節(jié)點的加入和離開只需要對涉及到的部分進行數(shù)據(jù)同步。

Gossip協(xié)議

執(zhí)行過程：

Gossip 過程是由種子節(jié)點發(fā)起，當一個種子節(jié)點有狀態(tài)需要更新到網(wǎng)絡(luò)中的其他節(jié)點時，它會隨機的選擇周圍幾個節(jié)點散播消息，收到消息的節(jié)點也會重復(fù)該過程，直至最終網(wǎng)絡(luò)中所有的節(jié)點都收到了消息。這個過程可能需要一定的時間，由于不能保證某個時刻所有節(jié)點都收到消息，但是理論上最終所有節(jié)點都會收到消息，因此它是一個最終一致性協(xié)議。

Dynamo通過Gossip干了如下幾件事情：

系統(tǒng)中的每個節(jié)點都會定期（比如1s）通過Gossip協(xié)議同其他節(jié)點交換集群信息，并相互更新各自落后的節(jié)點版本信息，如果發(fā)現(xiàn)某個節(jié)點很長時間都沒有狀態(tài)更新，則認為該節(jié)點已經(jīng)下線了。

如果某節(jié)點a重啟，其他持有節(jié)點a數(shù)據(jù)副本的節(jié)點能通過Gossip協(xié)議發(fā)現(xiàn)，并將副本數(shù)據(jù)歸還節(jié)點a，這種機制叫做數(shù)據(jù)回傳（Hinted Handoff）

NRW

類似Quorum中的$W+R>N$，只不過這三個參數(shù)的取值可以根據(jù)實際的需求調(diào)整，并不一定要滿足大于。由此導(dǎo)致的問題是，在Dynamo這樣的P2P集群中，由于每個節(jié)點存儲的集群信息有所不同，可能出現(xiàn)同一條記錄被多個節(jié)點同時更新的情況，無法保證多節(jié)點之間的更新順序。因此Dynamo引入了向量時鐘（Vector Clock）的技術(shù)手段嘗試解決沖突。

NRW對節(jié)點失效的保證性也和一般的一致性協(xié)議如Raft、paxos不同。$W+R>N$僅保證了當存在不超過一臺機器故障時，至少能夠讀到一份有效數(shù)據(jù)。

NRW還導(dǎo)致了一個問題，假設(shè)N=3，W=2，R=2，如果部分寫操作已經(jīng)返回客戶端成功了但是沒用完全同步到所有的副本，會導(dǎo)致三個副本之間的數(shù)據(jù)都不一致。因此要Dynamo啟動修復(fù)任務(wù)，該任務(wù)會合并各個副本中的數(shù)據(jù)并更新過期的副本，從而使得副本間保持一致。

Vector Clock

每個節(jié)點對每個對象的操作用向量時鐘[nodes, counter]表示，出現(xiàn)沖突之后需要解決，最常見的沖突解決方式有兩種：

通過客戶端邏輯解決

通過時鐘“l(fā)ast write wins”解決，這種方式依賴集群內(nèi)節(jié)點之間的時鐘同步算法，不保證完全準確。

Dynamo只能保證最終一致性，如果多個節(jié)點之間的更新順序不一致，客戶端可能讀不到期望結(jié)的結(jié)果。多客戶端并發(fā)操作也很難預(yù)測操作結(jié)果。

Dynamo最大的問題應(yīng)該就是，犧牲了一致性，但是沒有換來什么好處。

讀寫流程

Amazon Dynamo采用P2P架構(gòu)，因此各Replica間不存在主節(jié)點，讀寫操作的時候：

客戶端首先通過DHT找到所有的副本，其中一個副本作為協(xié)調(diào)者

客戶端把IO請求發(fā)往協(xié)調(diào)者，協(xié)調(diào)者并發(fā)地向所有副本發(fā)送讀寫請求。同時協(xié)調(diào)者也將IO向本地發(fā)起請求

其他副本成功響應(yīng)的個數(shù)滿足W/R之后，協(xié)調(diào)者回復(fù)客戶端成功，但是仍會繼續(xù)等待或者重試，直到所有的副本都響應(yīng)成功。

讀過程中，如果發(fā)生沖突，需要自己解決沖突或?qū)_突返回給客戶端。

讀操作成功之后，對應(yīng)的狀態(tài)機不會立即銷毀（可能只有R個節(jié)點返回了），協(xié)調(diào)者會等待一小段時間，這段時間內(nèi)可能還有一些節(jié)點會返回過期的數(shù)據(jù)，協(xié)調(diào)者將更新這些節(jié)點的數(shù)據(jù)到最新版本，這個過程稱為讀取修復(fù)。

參考鏈接

• 《大規(guī)模分布式存儲系統(tǒng) 原理解析與架構(gòu)實戰(zhàn)》 楊傳輝

總結(jié)

以上是生活随笔為你收集整理的分布式键值系统Amazon Dynamo简介的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。