DYNAMO

按分散式系統常用的哈希演演算法切分數據，分放在不同的node上。Read操作時，也是根據key的哈希值尋找對應的node。Dynamo使用了Consistent Hashing演演算法，node對應的不再是一個確定的hash值，而是一個hash值範圍，key的hash值落在這個範圍內，則順時針沿ring找，碰到的第一個node即為所需。

Dynamo對Consistent Hashing演演算法的改進在於：它放在環上作為一個node的是一組機器（而不是memcached把一台機器作為node），這一組機器是通過同步機制保證數據一致的。

以上圖為例，node1其實包含了多台機器，在一個node里宕了一台機或增加一台機，並不影響整個Dynamo對key的尋找。

如果一個ring內的訪問量大了，則可以在兩個node間加入一個新node以緩解壓力，這時會影響到其後繼node的hash範圍，需要調整數據。假設一個ring中原本只有node2、node3、node4，在加入新的node1之後，原先從node2查詢的部分key將改為從node1查詢，node1和node2中的數據就需要調整，主要是node1從node2中提取出屬於它的數據，這樣做需要選取性能壓力不高的時候。

Dynamo的一個node中的同步是由client端來“解決”的，使用所謂的（N,R,W）模型，其中，N表示node中機器的總數，R表示一個讀請求需要的機器參與總數，W代表一個寫請求需要的機器參與總數，這些值由client端配置。

例如，一個node有5台機器（N=5），client發出寫請求——廣播到5台機，如果收到3個“寫完成”的返回消息，即認為寫成功（W=3）；client發出讀請求——還是廣播到5台機，如果收到2個“讀完成”的返回消息，即認為讀成功（R=2）。對於數據十分重要的應用（如金融），配置可以為(5, 5, 5)，即要求node中所有機器的寫都成功；而對於數據讀寫訪問量極高的應用，配置可以為（5, 1, 1）。

通常W不等於N，於是，在某些情況下一個node內的機器上的數據可能會有不一致，這時Dynamo是通過將多個Read的返回結果“合併”來得出最終結果的，使用了所謂Object Version和Vector clock的技術，即跟蹤一個Object在不同機器上的版本變化，以確保當多個Read請求結果返回不一致時，能夠根據其版本信息得出正確的結果。 Dynamo的這種做法是一種折衷，即為了同時保證讀和寫的效率，寫操作不要求絕對同步，而把不同步可能產生的後果推給了讀操作。

Dynamo的一個node中一台機器建有一個Merkle Tree，當兩台機器不一致時（如一台機器宕機一段時間），通過這個tree結構，可以快速定位不一致的Object來恢複數據。Merkle Tree又叫Hash Tree，它把key分成幾個range，每個range算出一個hash值，作為葉子，再一層層合併計算上去，這樣，從root開始比較hash值，就可以快速找到哪幾段range中的hash值變化了。

Dynamo的意思是發電機，顧名思義，這一整套的方案都像發電機一樣，源源不斷地提供服務，永不間斷。以下內容看上去有點教條，但基本上如果你要理解原理，這每一項都是必須知道的。

CAP原則

先來看歷史，Eric A.Brewer教授，Inktomi公司的創始人，也是berkeley大學的計算機教授，Inktomi是雅虎搜索2013年的台端技術核心支持。最主要的是，他們（Inktomi公司）在最早的時間裡，開始研究分佈計算。CAP原則的提出，可以追溯到2000年的時候（可以想象有多麼早！），Brewer教授在一次談話中，基於他運作Inktomi以及在伯克利大學里的經驗，總結出了CAP原則（文末參考資料中有其演講資料鏈接）。圖一是來自Brewer教授當年所畫的圖：

圖一：CAP原則當年的PPT

Consistency（一致性）：即數據一致性，簡單的說，就是數據複製到了N台機器，如果有更新，要N機器的數據是一起更新的。

Availability（可用性）：好的響應性能，此項意思主要就是速度。

Partition tolerance（分區容錯性）：這裡是說好的分區方法，體現具體一點，簡單地可理解為是節點的可擴展性。

定理：任何分散式系統只可同時滿足二點，沒法三者兼顧。

忠告：架構師不要將精力浪費在如何設計能滿足三者的完美分散式系統，而是應該進行取捨。

DHT——分散式哈希表

DHT（Distributed Hash Table，分散式哈希表），它是一種分散式存儲定址方法的統稱。就像普通的哈希表，裡面保存了key與value的對應關係，一般都能根據一個key去對應到相應的節點，從而得到相對應的value。

這裡隨帶一提，在DHT演演算法中，一致性哈希作為第一個實用的演演算法，在大多數系統中都使用了它。一致性哈希基本解決了在P2P環境中最為關鍵的問題——如何在動態的網路拓撲中分佈存儲和路由。每個節點僅需維護少量相鄰節點的信息，並且在節點加入/退出系統時，僅有相關的少量節點參與到拓撲的維護中。至於一致性哈希的細節就不在這裡詳細說了，要指明的一點是，在Dynamo的數據分區方式之後，其實內部已然是一個對一致性哈希的改造了。

有了上面一章里的兩個基礎介紹之後，我們開始進入Dynamo的世界。

Dynamo的數據分區與作用

在Dynamo的實現中提到一個關鍵的東西，就是數據分區。假設我們的數據的key的範圍是0到2的64次方（不用懷疑你的數據量會超過它，正常甚至變態情況下你都是超不過的，甚至像伏地魔等其他類Dynamo系統是使用的2的32次方），然後設置一個常數，比如說1000，將我們的key的範圍分成1000份。然後再將這1000份key的範圍均勻分配到所有的節點（s個節點），這樣每個節點負責的分區數就是1000/s份分區。

如圖二，假設我們有A、B、C三台機器，然後將我們的分區定義了12個。

圖二：三個節點分12個區的數據的情況

因為數據是均勻離散到這個環上的（有人開始會認為數據的key是從1、2、3、4……這樣子一直下去的，其實不是的，哈希計算出來的值，都是一個離散的結果），所以我們每個分區的數據量是大致相等的。從圖上我們可以得出，每台機器都分到了三個分區里的數據，並且因為分區是均勻的，在分區數量是相當大的時候，數據的分佈會更加的均勻，與此同時，負載也被均勻地分開了（當然了，如果硬要說你的負載還是只集中在一個分區里，那就不是在這裡要討論的問題了，有可能是你的哈希函數是不是有什麼樣的問題了）。

為什麼要進行這樣的分佈呢，分佈的好處在於，在有新機器加入的時候，只需要替換原有分區即可，如圖三所示：

圖三：加入一個新的節點D的情況

同樣是圖二里的情況，12個分區分到ABC三個節點，圖三中就是再進入了一個新的節點D，從圖上的重新分佈情況可以得出，所有節點裡只需要轉移四分之一的數據到新來的節點即可，同時，新節點的負載也伴隨分區的轉移而轉移了（這裡的12個分區太少了，如果是1200個分區甚至是12000個分區的話，這個結論就是正確的了，12個分區只為演示用）。

從Dynamo的NRW看CAP法則

在Dynamo系統中，第一次提出來了NRW的方法。

N：複製的次數；

R：讀數據的最小節點數；

W：寫成功的最小分區數。

這三個數的具體作用是用來靈活地調整Dynamo系統的可用性與一致性。

舉個例子來說，如果R=1的話，表示最少只需要去一個節點讀數據即可。讀到即返回，這時是可用性是很高的，但並不能保證數據的一致性，如果說W同時為1的話，那可用性更新是最高的一種情況。但這時完全不能保障數據的一致性，因為在可供複製的N個節點裡，只需要寫成功一次就返回了。也就意味著，有可能在讀的這一次並沒有真正讀到需要的數據（一致性相當的不好）。如果W=R=N=3的話，也就是說，每次寫的時候，都保證所有要複製的點都寫成功，讀的時候也是都讀到，這樣子讀出來的數據一定是正確的，但是其性能大打折扣，也就是說，數據的一致性非常的高，但系統的可用性卻非常低了。如果R+W>N能夠保證我們“讀我們所寫”，Dynamo推薦使用322的組合。

Dynamo系統的數據分區讓整個網路的可擴展性其實是一個固定值（你分了多少區，實際上網路里擴展節點的上限就是這個數），通過NRW來達到另外兩個方向上的調整。

Dynamo的一些增加可用性的補救

針對一些經常可能出現的問題，Dynamo還提供了一些解決的方法。

第一個是hinted handoff數據的加入：在一個節點出現臨時性故障時，數據會自動進入列表中的下一個節點進行寫操作，並標記為handoff數據，在收到通知需要原節點恢復時重新把數據推回去。這能使系統的寫入成功大大提升。

第二個是向量時鐘來做版本控制：用一個向量（比如說[a,1]表示這個數據在a節點第一次寫入）來標記數據的版本，這樣在有版本衝突的時候，可以追溯到出現問題的地方。這可以使數據的最終一致成為可能。（Cassandra未用vector clock，而只用client timestamps也達到了同樣效果。）

第三個是Merkle tree來提速數據變動時的查找：使用Merkle tree為數據建立索引，只要任意數據有變動，都將快速反饋出來。

第四個是Gossip協議：一種通訊協議，目標是讓節點與節點之間通信，省略中心節點的存在，使網路達到去中心化。提高系統的可用性。