為什么要讀這篇論文梧乘？
數(shù)據(jù)庫里的最終一致性澎迎，寫任一副本（上一章spanner 講了讀任一副本）
和BAYOU一樣，有沖突消解策略选调。支持地理分散的（多數(shù)據(jù)中心）
一個讓人耳目一新的設計夹供。
他是一個真實的系統(tǒng)：用來支持購物車的服務在AMAZON。
比PNUTS, Spanner, FB Mysql 更加可靠仁堪，同時也一致性級別也比他們低哮洽。
Canssandra 受他啟發(fā)。
他們的目標是： 99.9 的延遲少于300MS弦聂，同時容忍數(shù)據(jù)中心的災難問題鸟辅，永遠可寫。
數(shù)據(jù)放在哪莺葫？
整個系統(tǒng)在一個特定的環(huán)形運算空間剔桨，我們稱為Ring。運算空間的大小可自己定義徙融，例如洒缀，該空間范圍取值為[0, 2**32 - 1]，而之所以稱為環(huán)形空間是當超出該值后繼續(xù)歸零。
對存儲系統(tǒng)中的每個節(jié)點的特征值在該空間內(nèi)進行運算树绩，例如萨脑，取節(jié)點的特征為其IP地址，對其ip地址進行hash運算饺饭，然后在運算空間內(nèi)取模渤早，得到其在環(huán)形運算空間上的值。如上圖瘫俊，A~G每個節(jié)點根據(jù)其運算得到的值而位于該Ring上的不同位置。
寫入對象數(shù)據(jù)時扛芽，首先根據(jù)對象key(一般是對象名)在運算空間內(nèi)計算其特征值川尖，然后在該Ring上沿著順時針方向查找與其特征值最接近的節(jié)點叮喳。例如上圖的對象K馍悟，計算其特征值位于A、B節(jié)點之間侵状，根據(jù)規(guī)則壹将，那K應該被存儲在節(jié)點B上诽俯。
這種方法看似完美承粤，一次計算即可得出其存儲節(jié)點最終位置辛臊。但可能帶來以下的致命問題：
- 新增一個節(jié)點彻舰，原本存儲在Ring上與其相鄰節(jié)點的數(shù)據(jù)現(xiàn)在落在了該新增節(jié)點上，那勢必需要進行數(shù)據(jù)遷移白群；
- 移除一個節(jié)點帜慢，那原本由該節(jié)點負責的數(shù)據(jù)接下來要由其相鄰節(jié)點負責唯卖，也會帶來數(shù)據(jù)的遷移拜轨。
由于計算式數(shù)據(jù)定位的天然特性胯甩，數(shù)據(jù)遷移的問題根本無法避免。但是上面的方案的問題是數(shù)據(jù)遷移發(fā)生在兩個相鄰節(jié)點之間皆串，如果每個節(jié)點存儲的數(shù)據(jù)量很大恶复，那數(shù)據(jù)遷移帶來的壓力勢必會影響參與遷移的節(jié)點正常的請求谤牡，導致不可用翅萤。
既然無法避免腊满，那就盡量緩解碳蛋。Dynamo設計中引入了虛擬節(jié)點（partition）肃弟。所謂的虛擬節(jié)點其實就是在一個物理節(jié)點（如上面的A/B/C/D）上虛擬出多個邏輯節(jié)點。例如A-1壁公、A-2紊册、A-3 ……囊陡，將這些虛擬節(jié)點參與環(huán)形運算空間的計算撞反，如下圖：
上圖中每個物理節(jié)點虛擬出了兩個邏輯節(jié)點搪花，定位時撮竿，首先根據(jù)對象key計算其所在的虛擬節(jié)點髓需，最后查表知道該虛擬節(jié)點位于的物理節(jié)點僚匆。相當于是一個二級映射函數(shù)咧擂。
這樣做法的好處時，在新增或者移除節(jié)點時攻臀，會有更多的節(jié)點參與到數(shù)據(jù)遷移過程中刨啸，提升遷移效率善已，但是卻無法從根本上避免數(shù)據(jù)遷移离例。
從理論分析就知道數(shù)據(jù)遷移過程參與的節(jié)點更多了，效率自然就提升了耀盗。
而物理節(jié)點如何劃分虛擬節(jié)點舌厨，個人感覺根據(jù)實際的使用場景來決定。例如揉燃，jedis就使用虛擬ip(真實ip后加上節(jié)點編號)你雌。
在存儲系統(tǒng)中肴颊，物理節(jié)點其實抽象的是磁盤，虛擬節(jié)點其實就是代表了磁盤上的某個目錄（經(jīng)常稱之為Partition）竟宋。而一般虛擬節(jié)點的數(shù)目固定丘侠，為2**N個。這樣逐样，對象key與虛擬節(jié)點的映射關系就可以保持固定蜗字，改變的是虛擬節(jié)點至物理節(jié)點的映射關系打肝。
這種二級映射帶來的好處是：
- 一級映射時增加節(jié)點移動的數(shù)據(jù)單位是單個對象，掃描計算哪些對象需要移動時代價太大挪捕；
- 二級映射時節(jié)點變化只影響虛擬節(jié)點的情況粗梭，新增或者移除節(jié)點(磁盤設備)時只需要遷移虛擬節(jié)點的數(shù)據(jù)即可，管理的成本大大減少级零。
引入虛擬節(jié)點后断医，典型的數(shù)據(jù)定位流程是：
- 根據(jù)對象名計算MD5，并取MD5的低N位得到虛擬節(jié)點編號（這也是為什么虛擬節(jié)點數(shù)目最好選擇2的N次方的原因）奏纪；
- 查表獲得虛擬節(jié)點所在的物理節(jié)點
一致性HASH的好處有可以自然的均衡孩锡，同時不需要一個MASTER去集中化管理，避免了單點的諸多問題亥贸。
壞處就是很難去主動控制數(shù)據(jù)的存放比如有一個KEY特別火爆躬窜，就很難調(diào)整。其次節(jié)點加入和離開炕置，都需要SHIFT DATA荣挨。而這DATA也是RANDOM（論文之后提到了優(yōu)化手段。）
容錯
如果一個節(jié)點暫時不可用朴摊，那么數(shù)據(jù)會被臨時存放到另一個節(jié)點默垄，同時會有一個handoff機制來保證，當節(jié)點恢復后甚纲。數(shù)據(jù)又會被送回來口锭。
所謂的HandOff機制是對Dynamo可用性的進一步提升手段。如同我們上面說到介杆，正常情況下鹃操，客戶的寫入數(shù)據(jù)會被復制到ring上的N個節(jié)點。但是一旦出現(xiàn)異常時春哨，寫入的節(jié)點不可達荆隘，這時候可能就會出錯，如下：
假如數(shù)據(jù)應該被寫入至節(jié)點A并復制到B和C赴背，但是此時假如A節(jié)點異常椰拒，可能就會導致數(shù)據(jù)不可寫。
Dynamo的做法是引入Handoff節(jié)點凰荚，例如這里的D作為A的Handoff燃观，A節(jié)點不可寫的時候，數(shù)據(jù)會被寫入D便瑟，但是在D上這些數(shù)據(jù)會被存儲在特殊位置并且有元數(shù)據(jù)信息描述該數(shù)據(jù)的原始位置（A）缆毁。一旦D檢測到A節(jié)點恢復，就會將該本來不屬于自己的數(shù)據(jù)遷移至原本的位置（A）胳徽。
如果節(jié)點長期不可用的話积锅。就會需要創(chuàng)建一個新的副本來復制這個節(jié)點全部的數(shù)據(jù)爽彤。這時需要ADMIN手動去下線上線節(jié)點。Dynamo本身是把所有失敗都當做臨時的缚陷。
如何實現(xiàn)永遠可寫适篙？
沒有MASTER，所以只要找到一個活的節(jié)點箫爷，就可以確保先寫到這個節(jié)點上嚷节。如果有失敗發(fā)生，為了確保數(shù)據(jù)的可持久性虎锚。那么就需要sloppy quorums硫痰。 同時還需要沖突消解策略。
sloppy quorum
quorum的目標有3個窜护。1. 不要在沒響應的節(jié)點上阻塞效斑。 2. 寫應該不會失敗 3. 讀有很大概率看到最新的寫。
一共發(fā)送N個請求柱徙，同步等待R個讀缓屠，W個寫，根據(jù)鴿籠原理护侮，會至少在一個SERVER上有交集敌完。同時可以減少長尾效應，以及容忍一些節(jié)點失效羊初。
這里的N是N個再preference list里的可達節(jié)點滨溉。每個節(jié)點都會去發(fā)送PING看他的后繼者是否還在。 "sloppy" quorum因為節(jié)點可能在可達的問題上不一致长赞，所以讀和寫可能不一定有交集晦攒。
流程是，當coordinator 收到寫請求涧卵，他會發(fā)送同樣的寫請求給N個可達的節(jié)點并行的勤家。然后等待W個寫。同樣如果是讀請求柳恐，同樣的寫請求給N個可達的節(jié)點并行的。然后等待R個讀的結果回來热幔。開始驗證版本乐设，如果有版本沖突，則會把多個版本沖突的結果返回給客戶端绎巨。
如果里面失敗很瘋狂近尚，讀可能看不到最新的寫。
除了上述的HandOff機制场勤，后臺還有一個"merkle tree" sync的程序戈锻，去同步不一樣的KEY RANGE歼跟。
同時最終一致性是怎么來的呢？ 因為要接受多個寫在任一副本上格遭，那么在失效情況下就會有分叉的副本哈街。所以需要允許讀到?jīng)_突的或者過期的數(shù)據(jù)。這個沖突和過期拒迅，會被修復骚秦。其中客戶端會顯示的合并沖突，這個合并策略由客戶端提供璧微。如果數(shù)據(jù)有幾個副本落后作箍，會在讀時進行修復。
什么時候R/W沒有交集呢前硫？當R + W > N
N=3 R=2 W=2
shopping cart, starts out empty ""
preference list n1, n2, n3, n4
client 1 wants to add item X
get() from n1, n2, yields ""
n1 and n2 fail
put("X") goes to n3, n4
n1, n2 revive
client 2 wants to get Y
get() from n1, n2 yields ""
reply client ""
then get() receive n3,n4 yield "X" with higher version, repair n1,n2
什么時候會發(fā)生版本沖突呢胞得？
N=3 R=2 W=2
shopping cart, starts out empty ""
preference list n1, n2, n3, n4
client 1 wants to add item X
get() from n1, n2, yields ""
n1 and n2 fail
put("X") goes to n3, n4
n1, n2 revive
client 3 wants to add Y
get() from n1, n2 yields ""
put("Y") to n1, n2
client 3 wants to display cart
get() from n1, n3 yields two values!
"X" and "Y"
neither supersedes the other -- the put()s conflicted
客戶端收到了多個版本的讀的值之后，比如是購物車服務屹电，可能會使用union的方式來merge, 然后把MERGE的結果寫回DYNAMO
API：
- get(k) may return multiple versions, along with "context"
- put(k, v, context)
版本向量
如何在多個數(shù)據(jù)副本之間判斷誰的數(shù)據(jù)更新懒震？
Dynamo使用向量時鐘來解決該問題。簡單來說嗤详，接受客戶端寫請求的副本會為該數(shù)據(jù)的本次更新增加一個邏輯時間戳争占，該時間戳為一個二元組<updater, version>
updater：更新的執(zhí)行者
version：本次更新的版本號
例如，A本地對象object的當前版本為<A, 1>咧七，接下來A又收到客戶端的對象更新請求抹镊，那么A更新對象數(shù)據(jù)的同時，將其版本修改為<A, 2>苍狰。
假如該對象有另外一個副本位于節(jié)點B办龄，B上該對象的版本依然為<A, 1>，如果客戶端的更新請求沒有發(fā)往A淋昭，而是發(fā)到了B（這是有可能的俐填，因為很可能客戶端和A之間發(fā)生了網(wǎng)絡分區(qū)）。B更新對象數(shù)據(jù)的同時翔忽，更新其版本為<A, 1>, <B, 1>英融，然后將本次更新連同其版本一并發(fā)送至其他副本節(jié)點。
上圖演示了對于一個對象的兩次更新過程歇式，第二次中原來的主副本和客戶端之間出現(xiàn)了網(wǎng)絡不連通的問題驶悟，導致客戶端選擇出了新的主副本。
上圖演示了在主從同步出現(xiàn)延遲的情況下客戶端的連續(xù)數(shù)據(jù)更新導致數(shù)據(jù)版本的沖突問題材失。
客戶端讀數(shù)據(jù)時痕鳍，會根據(jù)R的設置從多個副本中讀出數(shù)據(jù)，然后對比副本數(shù)據(jù)的向量時鐘的版本，選擇最新的數(shù)據(jù)版本返回給客戶端笼呆。但是有可能出現(xiàn)無法合并的情況熊响，例如上面的A節(jié)點上數(shù)據(jù)版本為<A, 2>，B節(jié)點上數(shù)據(jù)版本為<A, 1>, <B, 1>诗赌。遇到這種情況汗茄，只能交給應用去選擇合并了。
再考慮下面這種并發(fā)更新的情況：
系統(tǒng)當前是三副本境肾，某個partition的三個副本分別為Sx剔难，Sy，Sz奥喻，且R=2偶宫， W=2。按照下面的順序進行數(shù)據(jù)更新：
- 數(shù)據(jù)在Sx節(jié)點寫入环鲤，產(chǎn)生數(shù)據(jù)的新版本為<Sx, 1>纯趋，并同步至Sy，Sz冷离；
- 數(shù)據(jù)在Sx節(jié)點更新吵冒，產(chǎn)生數(shù)據(jù)新版本為<Sx，2>西剥，并同步至Sy痹栖，Sz；
- 截止目前瞭空，Sx揪阿，Sy，Sz三個節(jié)點的數(shù)據(jù)版本均為<Sx, 2>咆畏，數(shù)據(jù)處于一致狀態(tài)南捂；
- 由于某種原因，A客戶端選擇了Sy節(jié)點對數(shù)據(jù)進行更新旧找，而此時A客戶端看到的數(shù)據(jù)版本為<Sx, 2>溺健，因此，A向Sy節(jié)點發(fā)送數(shù)據(jù)更新請求钮蛛，且指明本次更新的版本為<Sx, 2>鞭缭，Sy節(jié)點收到更新請求后，選擇更新本地數(shù)據(jù)的版本為<Sx, 2>愿卒，<Sy, 1>缚去；
- 在4進行的過程中，客戶端B選擇了Sz節(jié)點對數(shù)據(jù)進行更新琼开，此時B客戶端看到的數(shù)據(jù)版本也是<Sx, 2>，于是B給Sz發(fā)送請求更新對象的<Sx, 2>的版本數(shù)據(jù)枕荞。Sz同樣更新本地的數(shù)據(jù)以及版本為<Sx, 2>, <Sz, 1>柜候；
- 接下來數(shù)據(jù)主從同步的過程中搞动，無論是Sy將自己的數(shù)據(jù)同步至Sz，還是Sz將數(shù)據(jù)同步至Sy渣刷，都會發(fā)現(xiàn)他們之間的數(shù)據(jù)其實是存在沖突的鹦肿，而且存儲系統(tǒng)自身是無法解決這種沖突的，于是辅柴，繼續(xù)保存這種沖突數(shù)據(jù)箩溃，但是在Sy(或者Sz)向Sx同步數(shù)據(jù)的時候是沒問題的，因為通過向量時鐘比對發(fā)現(xiàn)Sx的版本無論比Sy還是Sz都要更新掂帧涣旨；
- 接下來，客戶端發(fā)起對數(shù)據(jù)的讀請求股冗，因為存在沖突霹陡，沖突的版本都會被發(fā)送至客戶端，于是客戶端看到的數(shù)據(jù)版本是{<Sx, 2>, <Sy, 1>}和{<Sx, 2>, <Sz, 1>}止状。接下來應用程序根據(jù)自己的業(yè)務邏輯嘗試去解決沖突烹棉，例如，最終選擇了{<Sx, 2>, <Sy, 1>}作為最終的數(shù)據(jù)怯疤，那接下來會將自己的協(xié)調(diào)結果寫到某個副本（假如選擇Sx寫入）上浆洗，需要注意的是，客戶端指定更新的版本為<Sx, 2>, <Sy, 1>, <Sz, 1>集峦，而Sx收到請求后伏社，會將對象的版本更新為<Sx, 3>,<Sy, 1>, <Sz, 1>。如此這樣少梁，接下來Sx將新版本的數(shù)據(jù)推送到其他副本的時候洛口，就不會在出現(xiàn)沖突了，因為無論是Sy節(jié)點上的<Sx, 2>, <Sy, 1>還是Sz節(jié)點上的<Sx, 2>, <Sz, 1>均落后于Sx上的當前版本凯沪，大家又達成了數(shù)據(jù)一致性
如何節(jié)點很多第焰，版本向量只會越來越大？
是的妨马，但是這個變大的過程很緩慢挺举，因為KEY基本上是被固定的N個節(jié)點服務的。
Dynamo會刪除LRU的ENTRY烘跺，當VV 超過10個元素湘纵。
這樣會帶來不必要的merge,
put@b: [b:4]
put@a: [a:3, b:4]
forget b:4: [a:3]
now, if you sync w/ [b:4], looks like a merge is required
忘記最舊的是聰明的，因為如果忘記新的話滤淳，會造成最近的版本區(qū)別會被消除梧喷。可能造成了錯誤的包含關系，而丟失了更新铺敌。比如有個新的 [c : 1, a : 10]被抹除成了 [a : 10], 那邊有個[a : 11],這樣結果就以[a : 11]為準了汇歹，丟失了C的這個更新。
讓CLIENT 做MERGE也不是萬能的偿凭。比如是個計數(shù)器产弹，要在X上加2，B 加了1次1弯囊，C加了一次1. 其實應該就是,2痰哨。如果客戶端看到2個不同的版本都是1，就以為是1就錯了匾嘱。
一個問題
Suppose Dynamo server S1 is perfectly healthy with a working network connection. By mistake, an administrator instructs server S2 to remove S1 using the mechanisms described in 4.8.1 and 4.9. It takes a while for the membership change to propagate from S2 to the rest of the system (including S1), so for a while some clients and servers will think that S1 is still part of the system. Will Dynamo operate correctly in this situation? Why, or why not?
被刪除的server S1, 可能會丟失一些PUT斤斧，在GET的時候，同時加入的SERVER可能會丟失一些PUT奄毡，因為那時不知道coordinator折欠。當然加入的SERVER也會服務GET()在還沒有完全初始化好的時候。Quorum 會使得get 可以看到最新的數(shù)據(jù)吼过，盡管有一些是舊的锐秦。同時副本的SYNC也會修復這些舊數(shù)據(jù)的GET。所以大概率Dynamo還是會做正確的事盗忱。
如何解決KEY RANGE隨機變化造成的性能問題
在原先的版本里雖然引入virtual node但是當有節(jié)點加入的時候酱床，還是隨機散到這個環(huán)上，所以要分過去的KEY RANGE 也是隨機趟佃，大概率不得不掃描原來NODE上的整個KEY RANGE 把要分過去的數(shù)據(jù)給找出來扇谣。策略2把整個環(huán)的區(qū)域等分成Q分，因為Q非常大闲昭，所以每個節(jié)點可能會擁有很多分KEY RANGE的文件罐寨。Q遠大于 T（每個節(jié)點的TOKEN數(shù)） * S（系統(tǒng)中節(jié)點數(shù)）。 現(xiàn)在因為KEY RANGE 固定了序矩，所以可以每個RANGE存一份文件鸯绿。然后以RANGE的最右側 向后順時針找到的NODE，就是負責存這個RANGE文件的NODE簸淀。此時TOKEN還是隨機分配瓶蝴，隨機散的了，只是RANGE被固定住了租幕。所以再發(fā)送數(shù)據(jù)的時候舷手，會把整個文件發(fā)過去了。上面解決了傳輸?shù)膯栴}劲绪，但是因為TOKEN隨機撒男窟，可能有些TOKEN拿到200個文件盆赤，有些只拿到2個文件，會不均勻蝎宇。同時節(jié)點出去進來也會不均勻弟劲。
那么策略3就是TOKEN也不隨機散了祷安。每個節(jié)點比如Q為100姥芥， S為5. 那么每個節(jié)點就有20個TOKEN，是均勻的防止在100個環(huán)上的等比例切分的點上的汇鞭。這樣把不均勻的問題也給解決了凉唐。
總結
Dynamo 有最終一致性，需要CLIENT來消解寫沖突霍骄，同時在失敗的情況下系統(tǒng)依然可以寫台囱。
這個模型因為會延遲讀和需要客戶端提供MERGE，在某些場景上不太適合读整。
是一種得到高可用并且不阻塞在WAN上的好方式簿训。
但是最終一致性在存儲系統(tǒng)上是否是好的，還有爭議米间。
FAQ
Q：Dynamo 如何從一個節(jié)點的永久的失效里恢復强品，Merkle trees反熵是什么？
A：在本文中屈糊，反熵是同步兩個副本的核心的榛。 為了確定兩個副本之間的區(qū)別，Dynamo遍歷了兩個副本的Merkle Tree逻锐。 如果root節(jié)點匹配夫晌，則Dynamo不會下降該分支。 如果樹中的一個節(jié)點不匹配昧诱，則將新版本的分支復制到舊版本晓淀。 使用Merkle樹使作者只能復制樹中不同的部分。最小化了同步時需要轉(zhuǎn)移的數(shù)據(jù)量盏档，減少了逆熵過程中 讀取磁盤的次數(shù)凶掰。 維基百科上有一張圖片來說明：https://en.wikipedia.org/wiki/Merkle_tree。
這種方案的缺點是：每當有節(jié)點加入或離開系統(tǒng)時妆丘，一些 key range 會變锄俄，因此對應的 tree 需要重新計算。采用了上面提到的策略3之后會解決這個問題勺拣。
Q : Dynamo 會使用DHT來scale嗎奶赠？
A ：現(xiàn)在，人們已經(jīng)非常了解如何構建可擴展到大量節(jié)點的DHT药有，甚至是O（1）DHT（例如毅戈，請參見http://www.news.cs.nyu.edu/~jinyang/pub/nsdi05-accordion.pdf）苹丸。 所描述的Dynamo解決方案是具有良好可伸縮性的O（1）DHT。 我認為作者認為苇经，一旦他們實際遇到縮放問題赘理，他們將使用文獻中的解決方案。
Q : 什么是gossip-based protocol?
A : 任何不具有掌握系統(tǒng)中所有參與者的 master的系統(tǒng)扇单，通常都會有一個協(xié)議來查找其他成員商模。 通常將此類協(xié)議稱為八卦協(xié)議，因為參與者需要八卦（從其他節(jié)點收集信息）來確定誰是系統(tǒng)的一部分蜘澜。 更一般地施流，八卦是指通過成對的計算機交換他們知道的信息而在整個系統(tǒng)中傳播的信息。 您可以從Wikipedia了解更多有關八卦協(xié)議的信息：https：//en.wikipedia.org/wiki/Gossip_protocol鄙信。
