Amazon Dynamo是分布式的key-value系統，最近閱讀了Dynamo最初的論文《Dynamo: Amazon's Highly Available Key-value Store》，本文想聊一聊它的去中心化（decentralization）。既有閱讀相關材料后對其實現的理解，也有自己的思考，其中如有不正確言論歡迎指出。

中心節點

通常，我們見到的分布式存儲結構都是具備中心（總控）節點的，比如Google File System（GFS），包括了中心的Master和數據節點Chunck Server；再比如HDFS，包括了中心的Name Node和數據節點Data Node。下面就以這兩者為例來說明設置中心節點遇到的問題和解決。

中心節點通常包含了存儲單元的分布信息，存儲內容的元信息，“一致性”是分布式系統的核心內容，而在處理一致性問題上，引入中心節點可以帶來莫大的好處，但是，也容易引發問題：

• 單點故障：這個問題的解決主要靠熱備，比如GFS就靠Shadow Master。而HDFS情況比較復雜，在Hadoop 2.0以前靠的是Secondary NameNode，它不是真正的HA（High Availability），它只是階段性的合并edits和fsimage，以縮短集群啟動的時間，因此在Name Node出問題的時候，它既不能保證立即提供服務，也不能保證數據的完整性；現在HDFS為保證Name Node的HA，做法就很多了，包括了（1）shared image或者是（2）data replication的方法，這篇文章有系統的介紹。

（上圖來自《HDFS HA: 高可靠性分布式存儲系統解決方案的歷史演進》）

• 擴展性，我們可以按照這樣的思路來解決這個問題：
  • 中心節點包括了兩個基本職責，一個是文件系統的維護，它需要知道每個數據節點上的哪塊空間存放了哪些數據；還有一個是對于數據請求的調度。這兩個是可以拆開來的。
  • 把單Master變成Multi-master，Master之間可以用不同的方式實現數據同步，這個方法的好處在于Master的水平擴展變得容易，問題還是在于一致性，如果不同的Master要操縱同一個數據節點上同一片數據，需要有專門的方式來處理沖突。
  • 對于元文件信息量較大時會比較麻煩，比如HDFS上都是小文件，文件數量眾多，存儲效率低（這是HDFS不適宜的一個使用例子，在這篇文章里面我提到過），Name Node的內存消耗大。要么就不要這么用，GFS就比較適用于存放大文件；要么就從存儲架構上解決，軟件系統一個通用的辦法是引入新的一個層，比如在Name Node和Data Node之間引入一個區域自治的層，這一層每一個節點分別自治管理一部分Data Node，而都從屬于Name Node。

有趣的是，整個互聯網就可以看做是一個巨大的分布式系統，經過了實踐檢驗，我們可以認為它的的確確是去中心化的，但它也并不是每個維度都“去中心”，比如域名服務器，***域名服務器就是一個中心節點。因此如果僅僅是為了分布式，而粗暴地把中心節點去掉不是明智的，當然，Dynamo做了嘗試，下面我列出了一些去掉中心節點后帶來的問題，和它的解決辦法。

Dynamo的去中心化

在上面提到了的Dynamo 2007年的論文中，就直白地強調了去中心化是Dynamo設計的一條重要原則：

Decentralization: An extension of symmetry, the design should favor decentralized peer-to-peer techniques over centralized control. In the past, centralized control has resulted in outages and the goal is to avoid it as much as possible. This leads to a simpler, more scalable, and more available system.

Dynamo的設計者已經意識到了中心化系統帶來的問題，包括服務中斷，因此要盡可能避免。其它還包括的設計原則有：

• Incremental scalability，增量擴展，減少對系統的影響；
• Symmetry，對稱性，節點之間都是對等的；
• Heterogeneity，多相性（不知道怎么翻譯更好），系統的擴展性可以按不同的比例落實到不同類型和能力的硬件上面去。

下圖來自該論文，列出了遇到的問題和解決問題采用的技術，這是Dynamo設計的核心，而其中的大部分問題都是和去中心化相關的：

下面逐條敘述：

Partioning

采用一致性Hash（Consistent Hashing）來解決節點增加和水平擴展的問題，帶來的好處和設計原則中的增量擴展是一致的。它本身已經不是一個新話題了，介紹它的材料互聯網上有很多，在此不贅述。Dynamo的實現上有兩點特別需要指出：

• 每一臺物理設備都根據不同的能力折合成不同數量的虛擬節點數目；
• 每份數據都被映射到整個hash環上面的多個節點，從而形成replication，保證可用性。

High availablity for writes

采用向量時鐘（Vector Clock）來處理一致性問題，向量時鐘實際上是一個(node,counter)對的列表，如下圖：

D1寫入，發生在節點Sx，形成向量時鐘[Sx,1]，Sx又發生一次寫，于是counter增加1，變成了[Sx,2]，之后基于它發生了D3和D4兩次寫入，于是出現了兩個版本，([Sx,2],[Sy,1])和([Sx,2],[Sz,1])，在D5的時候協調，協調成Sy先于Sz發生，counter再加1。這里的協調有兩種方式：

• last write wins，依賴于節點時鐘，但是時鐘之間無法做到絕對一致
• 客戶端來決定

Handling temporary failures

Sloppy Quorum：草率的法定人數（這個不知道如何翻譯），這里有一個有名的NWR機制，其中：

• N表示復制的數據備份數量，
• W表示同步確認成功的寫操作的副本數（剩下N-W的寫操作是異步進行的），
• R表示同步確認成功的讀操作的副本數（每次讀通過比較前面提到的向量時鐘/版本號來確定有效的副本）。

當W+R>N的時候，可以保證強一致性，對于這個定理，分類舉例說明如下：

• 如果W<R，例如W=1，R=2，N=2，那么兩份數據拷貝中，有一份同步寫（有效數據），一份異步寫（可能暫時無效），而有兩份同步讀，所以肯定能讀到一份有效的數據；
• 如果W=R，例如W=1，R=1，N=1，這是最簡單的“單庫模式”，沒有異步寫；
• 如果W>R，例如W=2，R=1，N=2，兩份寫入都是同步寫，因此讀任意一份數據都是有效的。

通過協調N、W、R之間的值，就可以在一致性和可用性之間做tradeoff（CAP理論中P是無法犧牲的，而C和A是可以取舍的），因為W或R是同步的，因此基本上W或R的值越大，Availability就越差。

Hinted Handoff：暗示的轉交，如果寫操作過程中節點A暫時不可用，可以自動將
該節點上的副本轉交到別的節點去，這是為了保證副本總數不減少。而這個轉交的數據會設置一個暗示的標記，等到節點A恢復了，會被重新轉交回A。

Recovering from permanent failures

使用Merkle Tree的反熵（anti-entropy）。Merkle是這樣一種數據結構，非葉子節點提供了多層Hash的功能：

反熵協議是用來幫助副本之間的同步的，使用Merkle的主要優點是每個分支可以獨立地檢查，而不需要下載整個樹或整個數據集。

Membership and failure detection

基于Gossip的成員協議（membership protocol）和故障檢測。Gossip協議本身就是為了去中心化而設計的，雖然無法保證在某個時刻所有節點狀態一致，但可以保證在某個最終的時刻一致。成員協議用于在hash環上增加或減去節點。

關于Dynamo的吐槽

對于Dynamo的去中心化，實在是功過兼備，畢竟引入了上面介紹的一堆復雜的機制，尤其對于數據的一致性問題，更是爭議不小。使用一個Master節點，丟失了中心化，但是一致性的問題就容易解決得多，系統也會更簡單；退一步說，如果要去中心化，但是使用Paxos這樣的協議，來選舉一個“Master”出來，那也能比較簡潔地保證一致性。但是Dynamo***的實現，讓用戶來解決沖突的做法（有時候用戶也沒法確定該用哪個版本），確實有些別扭；而采用絕對時間來解決沖突的方法，則是在機制上有天生的缺陷（時間無法做到絕對同步）。

網上曾經有一篇很火的吐槽《Dynamo: A flawed architecture – Part 1》，抱怨了一些Dynamo的問題，新浪的Tim Yang寫了一篇文章簡單翻譯了一下，我就不再贅述，大致上抱怨的問題包括：

1. 一致性方面，Dynamo沒有辦法保證避免臟讀；
2. Quorum機制中只是R+W>N在遇到節點不可用的時候，并不能保證強一致性；
3. Hinted Handoff機制在跨IDC的情況下，會因為異地傳輸開銷而性能低下；
4. 災難恢復方面，某一個IDC掛掉的時候，沒人可以計算到底丟了多少數據；
5. 論文里面一些自相矛盾的地方，一個是對節點對等的描述，一個是對最終一致的描述；
6. Dynamo給用戶造成了誤導，以為一直是在CAP的C和A中必須做一個取舍，其實單節點中心就可以同時做到CA；
7. Dynamo宣稱去中心化，但是并沒有完全做到，比如交換機故障造成網絡分片的時候，服務就不可用了。

這篇文章的標題寫著part 1，只可惜part 2沒有出現。這篇文章引起了不少爭議，作者后來自己寫了一篇《Dynamo – Part I: a followup and re-rebuttals》來回應，文章結尾總結了一下他對Dynamo的觀點：

• 盡量去避免臟讀；
• 不受控的臟讀任何時候都不可接受，即便在災難發生的時候——就算數據丟失也比它要好得多，大多數情況下，管理員會關閉部分或者全部的服務，而不是去用丟失或者損壞的數據來響應用戶
• 一個數據中心內的網絡分片要避免，在一個數據中心內考慮P（partition tolerance）是不合理的；
• 中心化并不意味著低Availability，高可用的服務是可能的，雖然說scalability可能會成為問題；
• 開發設計的對稱性并不能很好適應硬件和網絡的非對稱性；
• 數據中心一致性、高可用性和擴展性是可以同時達到的，只要在一個數據中心里面（也就是說P被放棄的時候），BigTable+GFS，HBase+HDFS，甚至Oracle RAC都是很好的例子；
• Dynamo的讀寫即便在一個數據中心內也會引起臟讀；
• 誰也不知道臟讀避免的時間邊界在哪里；
• 跨數據中心的情況下，沒法跟蹤有多少數據待更新，而災難恢復的時候，也沒法知道有多少數據丟失。

淘寶日照博客中的一篇文章，也談到了Dynamo設計上的一些問題，特別是對于一致性和分區容忍性上面精彩的吐槽，推薦閱讀。

原文鏈接：http://www.raychase.net/2396