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

中心節(jié)點(diǎn)

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

中心節(jié)點(diǎn)通常包含了存儲(chǔ)單元的分布信息，存儲(chǔ)內(nèi)容的元信息，“一致性”是分布式系統(tǒng)的核心內(nèi)容，而在處理一致性問題上，引入中心節(jié)點(diǎn)可以帶來莫大的好處，但是，也容易引發(fā)問題：

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

（上圖來自《HDFS HA: 高可靠性分布式存儲(chǔ)系統(tǒng)解決方案的歷史演進(jìn)》）

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

有趣的是，整個(gè)互聯(lián)網(wǎng)就可以看做是一個(gè)巨大的分布式系統(tǒng)，經(jīng)過了實(shí)踐檢驗(yàn)，我們可以認(rèn)為它的的確確是去中心化的，但它也并不是每個(gè)維度都“去中心”，比如域名服務(wù)器，***域名服務(wù)器就是一個(gè)中心節(jié)點(diǎn)。因此如果僅僅是為了分布式，而粗暴地把中心節(jié)點(diǎn)去掉不是明智的，當(dāng)然，Dynamo做了嘗試，下面我列出了一些去掉中心節(jié)點(diǎn)后帶來的問題，和它的解決辦法。

Dynamo的去中心化

在上面提到了的Dynamo 2007年的論文中，就直白地強(qiáng)調(diào)了去中心化是Dynamo設(shè)計(jì)的一條重要原則：

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的設(shè)計(jì)者已經(jīng)意識(shí)到了中心化系統(tǒng)帶來的問題，包括服務(wù)中斷，因此要盡可能避免。其它還包括的設(shè)計(jì)原則有：

• Incremental scalability，增量擴(kuò)展，減少對(duì)系統(tǒng)的影響；
• Symmetry，對(duì)稱性，節(jié)點(diǎn)之間都是對(duì)等的；
• Heterogeneity，多相性（不知道怎么翻譯更好），系統(tǒng)的擴(kuò)展性可以按不同的比例落實(shí)到不同類型和能力的硬件上面去。

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

下面逐條敘述：

Partioning

采用一致性Hash（Consistent Hashing）來解決節(jié)點(diǎn)增加和水平擴(kuò)展的問題，帶來的好處和設(shè)計(jì)原則中的增量擴(kuò)展是一致的。它本身已經(jīng)不是一個(gè)新話題了，介紹它的材料互聯(lián)網(wǎng)上有很多，在此不贅述。Dynamo的實(shí)現(xiàn)上有兩點(diǎn)特別需要指出：

• 每一臺(tái)物理設(shè)備都根據(jù)不同的能力折合成不同數(shù)量的虛擬節(jié)點(diǎn)數(shù)目；
• 每份數(shù)據(jù)都被映射到整個(gè)hash環(huán)上面的多個(gè)節(jié)點(diǎn)，從而形成replication，保證可用性。

High availablity for writes

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

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

• last write wins，依賴于節(jié)點(diǎn)時(shí)鐘，但是時(shí)鐘之間無法做到絕對(duì)一致
• 客戶端來決定

Handling temporary failures

Sloppy Quorum：草率的法定人數(shù)（這個(gè)不知道如何翻譯），這里有一個(gè)有名的NWR機(jī)制，其中：

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

當(dāng)W+R>N的時(shí)候，可以保證強(qiáng)一致性，對(duì)于這個(gè)定理，分類舉例說明如下：

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

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

Hinted Handoff：暗示的轉(zhuǎn)交，如果寫操作過程中節(jié)點(diǎn)A暫時(shí)不可用，可以自動(dòng)將
該節(jié)點(diǎn)上的副本轉(zhuǎn)交到別的節(jié)點(diǎn)去，這是為了保證副本總數(shù)不減少。而這個(gè)轉(zhuǎn)交的數(shù)據(jù)會(huì)設(shè)置一個(gè)暗示的標(biāo)記，等到節(jié)點(diǎn)A恢復(fù)了，會(huì)被重新轉(zhuǎn)交回A。

Recovering from permanent failures

使用Merkle Tree的反熵（anti-entropy）。Merkle是這樣一種數(shù)據(jù)結(jié)構(gòu)，非葉子節(jié)點(diǎn)提供了多層Hash的功能：

反熵協(xié)議是用來幫助副本之間的同步的，使用Merkle的主要優(yōu)點(diǎn)是每個(gè)分支可以獨(dú)立地檢查，而不需要下載整個(gè)樹或整個(gè)數(shù)據(jù)集。

Membership and failure detection

基于Gossip的成員協(xié)議（membership protocol）和故障檢測。Gossip協(xié)議本身就是為了去中心化而設(shè)計(jì)的，雖然無法保證在某個(gè)時(shí)刻所有節(jié)點(diǎn)狀態(tài)一致，但可以保證在某個(gè)最終的時(shí)刻一致。成員協(xié)議用于在hash環(huán)上增加或減去節(jié)點(diǎn)。

關(guān)于Dynamo的吐槽

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

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

1. 一致性方面，Dynamo沒有辦法保證避免臟讀；
2. Quorum機(jī)制中只是R+W>N在遇到節(jié)點(diǎn)不可用的時(shí)候，并不能保證強(qiáng)一致性；
3. Hinted Handoff機(jī)制在跨IDC的情況下，會(huì)因?yàn)楫惖貍鬏旈_銷而性能低下；
4. 災(zāi)難恢復(fù)方面，某一個(gè)IDC掛掉的時(shí)候，沒人可以計(jì)算到底丟了多少數(shù)據(jù)；
5. 論文里面一些自相矛盾的地方，一個(gè)是對(duì)節(jié)點(diǎn)對(duì)等的描述，一個(gè)是對(duì)最終一致的描述；
6. Dynamo給用戶造成了誤導(dǎo)，以為一直是在CAP的C和A中必須做一個(gè)取舍，其實(shí)單節(jié)點(diǎn)中心就可以同時(shí)做到CA；
7. Dynamo宣稱去中心化，但是并沒有完全做到，比如交換機(jī)故障造成網(wǎng)絡(luò)分片的時(shí)候，服務(wù)就不可用了。

這篇文章的標(biāo)題寫著part 1，只可惜part 2沒有出現(xiàn)。這篇文章引起了不少爭議，作者后來自己寫了一篇《Dynamo – Part I: a followup and re-rebuttals》來回應(yīng)，文章結(jié)尾總結(jié)了一下他對(duì)Dynamo的觀點(diǎn)：

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

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

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