本博客在http://doc001.com/同步更新娃循。
本文主要內(nèi)容翻譯自MySQL開發(fā)者Ulf Wendel在PHP Submmit 2013上所做的報(bào)告「Scaling database to million of nodes」丧没。翻譯過程中沒有全盤照搬原PPT，按照自己的理解進(jìn)行了部分改寫输枯。水平有限骇塘，如有錯(cuò)誤和疏漏羊壹，歡迎指正卫袒。
本文是系列的第二篇，本系列所有文章如下：
- 百萬節(jié)點(diǎn)數(shù)據(jù)庫擴(kuò)展之道(2): NoSQL理論與Amazon Dynamo
NoSQL理論基礎(chǔ)
CAP猜想
CAP猜想由Eric Brewer于2000年提出篙悯，其主要結(jié)論是蚁阳，在一個(gè)分布式系統(tǒng)中存在無法同時(shí)滿足的三個(gè)保證：連續(xù)性(consistency)、可用性(availability)鸽照、分區(qū)容忍(partition tolerance)螺捐。
大規(guī)模分布式系統(tǒng)中，節(jié)點(diǎn)數(shù)量眾多，節(jié)點(diǎn)上下線頻繁定血，分區(qū)容忍是避免管理紊亂的基礎(chǔ)赔癌。而從用戶體驗(yàn)來講，互聯(lián)網(wǎng)服務(wù)又希望是一直可用的澜沟。因此灾票，一致性往往成為犧牲對(duì)象。
CAP之一致性
一致性要求分布式系統(tǒng)的所有節(jié)點(diǎn)在同一時(shí)刻看到相同的數(shù)據(jù)茫虽，這意味著：
- 手段：同一數(shù)據(jù)的副本進(jìn)行更新時(shí)刊苍，以預(yù)先協(xié)商的順序執(zhí)行
- 持久性：所有已向用戶確認(rèn)的更新永遠(yuǎn)不會(huì)丟失
注意區(qū)分ACID的一致性和CAP的一致性。ACID中的一致性指的是數(shù)據(jù)始終處于有效狀態(tài)濒析，CAP的一致性指的是數(shù)據(jù)是一樣的正什。
CAP之可用性
可用性意味著，請(qǐng)求不論成功還是失敗号杏，都得到確切的回復(fù):
- 手段：即使副本崩潰/失去響應(yīng)婴氮，也不會(huì)中斷服務(wù)
- 性能：如果數(shù)據(jù)源失效，及時(shí)告知客戶端馒索，不讓其傻等
- Brewer的原始表述是「幾乎都能得到回復(fù)」
CAP之分區(qū)容忍
如果一個(gè)分布式系統(tǒng)是分區(qū)容忍的，那么任意數(shù)量的消息丟失或任意部分的系統(tǒng)失效都不影響系統(tǒng)正常工作名船。
在一個(gè)數(shù)據(jù)中心內(nèi)部绰上，機(jī)架內(nèi)核機(jī)架間的網(wǎng)絡(luò)分區(qū)很少發(fā)生，但是廣域網(wǎng)(例如互聯(lián)網(wǎng))的網(wǎng)絡(luò)分區(qū)現(xiàn)象非常普遍渠驼。
在上圖的網(wǎng)絡(luò)分區(qū)示例中蜈块，我們無法保證一個(gè)客戶端能夠觀察到另外一個(gè)分區(qū)的客戶端更新。我們能做的最佳措施是緩存所有的更新迷扇，在分區(qū)結(jié)束后重新發(fā)送它們百揭，最終選取合適的時(shí)機(jī)合并數(shù)據(jù)。
CAP定理
CAP猜想在2002年被Gibert和Lynch證明蜓席，成為CAP定理器一。
BASE
關(guān)于CAP的討論催生了BASE理論。BASE推薦使用弱一致模型厨内。BASE的含義是：
- 基本可用(Base Available)：可以偶爾不可用
- 軟狀態(tài)(Soft-state)：不遵循ACID祈秕，就像緩存一樣
- 最終一致(Eventual-consistency)：有一定的不一致窗口期，但最終達(dá)到一致狀態(tài)
早期的NoSQL趨勢(shì)
CAP和BASE奠定了NoSQL的理論基礎(chǔ)雏胃，促使人們變得更為實(shí)際请毛，不再去試圖發(fā)明一個(gè)完美的系統(tǒng)，而是針對(duì)業(yè)務(wù)的特定需求構(gòu)建現(xiàn)實(shí)可用的解決方案瞭亮。
早期的NoSQL存在兩個(gè)不同的方向方仿，則兩個(gè)方向的代表系統(tǒng)分別是Amazon Dynamo和Google Bigtable。
Amazon Dynamo等系統(tǒng)使用分布式哈希表(distributed hash table，DHT)組織節(jié)點(diǎn)仙蚜，專注于CAP中的AP此洲。
Google Bigtable及其克隆滿足一致性、分區(qū)容忍鳍征，實(shí)際的可用性也非常高(盡管master節(jié)點(diǎn)存在單節(jié)點(diǎn)故障隱患)黍翎。此類系統(tǒng)專注于CAP中的C(A)P。
接下來將對(duì)NoSQL領(lǐng)域的重要系統(tǒng)進(jìn)行介紹艳丛。
Amazon Dynamo
分布式哈希表
P2P文件共享系統(tǒng)使用覆蓋網(wǎng)(overlay network)提供服務(wù)匣掸。所謂覆蓋網(wǎng)絡(luò)是指建立在其它網(wǎng)絡(luò)上的虛擬網(wǎng)絡(luò)，主要指應(yīng)用層網(wǎng)絡(luò)氮双。例如碰酝，互聯(lián)網(wǎng)本身就是建立在底層物理網(wǎng)絡(luò)上的覆蓋網(wǎng)絡(luò)。在P2P文件系統(tǒng)中戴差，覆蓋網(wǎng)絡(luò)就是由那些共享文件的客戶端組成送爸。
不光是P2P系統(tǒng)，任何一個(gè)多節(jié)點(diǎn)協(xié)作的系統(tǒng)所需要的解決的一個(gè)核心問題就是路由問題暖释，即怎樣才能從一堆節(jié)點(diǎn)中找到應(yīng)該負(fù)責(zé)處理某個(gè)請(qǐng)求的那個(gè)特點(diǎn)節(jié)點(diǎn)袭厂。使用中心節(jié)點(diǎn)是最簡單的方法，但是當(dāng)系統(tǒng)規(guī)模達(dá)到一定程度之后球匕，中心節(jié)點(diǎn)的負(fù)擔(dān)會(huì)很重纹磺，且容易導(dǎo)致單節(jié)點(diǎn)故障。
對(duì)于這個(gè)問題亮曹，P2P系統(tǒng)給出的答案就是DHT橄杨。DHT將鍵值空間映射到分布式的節(jié)點(diǎn)集合上，每一個(gè)節(jié)點(diǎn)負(fù)責(zé)維護(hù)鍵值空間的一個(gè)子集照卦。路由協(xié)議保證從任意一個(gè)節(jié)點(diǎn)出發(fā)式矫，都能夠找到負(fù)責(zé)指定鍵值的節(jié)點(diǎn)，整個(gè)路由過程是完全去中心化的役耕。
著名的DHT包括CAN采转、Pastry、Chord瞬痘、Kademlia氏义，它們的區(qū)別在于鍵值空間的形態(tài)。CAN是一個(gè)多維笛卡爾空間图云，Pastry是一個(gè)路由表惯悠，Chord是一個(gè)環(huán)，Kademlia是一個(gè)二叉樹竣况。有興趣的讀者可以參閱相關(guān)論文克婶。
這些DHT中最優(yōu)美筒严、簡潔的莫過于Chord，它成為了Dynamo的不二選擇情萤。
Chord：概述
Chord將網(wǎng)絡(luò)中的節(jié)點(diǎn)組織成一個(gè)協(xié)作的在線內(nèi)存系統(tǒng)鸭蛙。客戶端通過兩個(gè)最基本的API——put()和get()——來存儲(chǔ)和獲取數(shù)據(jù)筋岛。嚴(yán)格地講娶视，其實(shí)只有一種操作，那就是loopup(key)：根據(jù)指定的鍵值查找對(duì)應(yīng)的(存儲(chǔ))網(wǎng)絡(luò)節(jié)點(diǎn)睁宰。搜索操作的時(shí)間復(fù)雜度是O(log n)肪获，其中n是節(jié)點(diǎn)的數(shù)量。
Chord是高度可擴(kuò)展的柒傻，所使用的鍵值映射方法能夠確保鍵值均勻地分布到節(jié)點(diǎn)上孝赫，達(dá)到很好地負(fù)載均衡。Chord是完全去中心化的红符，(幾乎)沒有特殊的節(jié)點(diǎn)青柄，因而不存在單節(jié)點(diǎn)故障。更令人興奮的是预侯，Chord能夠主動(dòng)處理節(jié)點(diǎn)加入致开、失敗等網(wǎng)絡(luò)拓?fù)渥兓?/p>
參見學(xué)術(shù)論文Chord: A scalable peer-to-peer lookup service for internet applications
Chord：虛擬環(huán)(virtual ring)
每一個(gè)數(shù)據(jù)根據(jù)其內(nèi)容、所有者等信息計(jì)算出一個(gè)原始鍵值萎馅。該原始鍵值進(jìn)一步被Chord映射為一個(gè)哈希鍵值双戳。默認(rèn)的算法是SHA1。SHA1返回一個(gè)160bit的哈希鍵值校坑，因此鍵值空間總共有2^160-1個(gè)可用值拣技。如此大的鍵值空間能夠有效地減少?zèng)_撞概率千诬。鍵值空間被組織成一個(gè)虛擬環(huán)耍目，按照順時(shí)針方向排序。
Chord：節(jié)點(diǎn)映射
在Chord中徐绑，每一個(gè)節(jié)點(diǎn)也被映射到和鍵值空間相同的虛擬環(huán)上邪驮。節(jié)點(diǎn)進(jìn)行映射的原始鍵值需要能夠區(qū)分出不同的節(jié)點(diǎn)，例如節(jié)點(diǎn)的IP地址就不失為一個(gè)好的選擇傲茄。映射哈希函數(shù)的選擇非常重要毅访，一個(gè)好的哈希函數(shù)應(yīng)該使節(jié)點(diǎn)均勻地分布在環(huán)上。
在Chord中盘榨，數(shù)據(jù)是這樣被分配到每一個(gè)節(jié)點(diǎn)進(jìn)行管理的喻粹。對(duì)于一個(gè)鍵值k，沿著虛擬環(huán)順時(shí)針方向(包括k所在位置)找到的第一個(gè)節(jié)點(diǎn)草巡，稱之為它的后繼節(jié)點(diǎn)守呜，記作successor(k)。鍵值k被分配給其后繼節(jié)點(diǎn)進(jìn)行管理，即每個(gè)節(jié)點(diǎn)負(fù)責(zé)管理(上一個(gè)節(jié)點(diǎn)位置查乒，本節(jié)點(diǎn)位置]的鍵值范圍弥喉。
原PPT認(rèn)為「每一個(gè)節(jié)點(diǎn)負(fù)責(zé)管理[本節(jié)點(diǎn)位置,下一個(gè)節(jié)點(diǎn)位置)的鍵值范圍÷昶」經(jīng)查閱Chord原文修正由境。
Chord：搜索
如果每一個(gè)節(jié)點(diǎn)只知道自己的前驅(qū)節(jié)點(diǎn)(逆時(shí)針方向鄰居)和后繼節(jié)點(diǎn)(順時(shí)針方向鄰居)。僅僅通過這兩個(gè)節(jié)點(diǎn)在Chord中搜索指定的鍵值蓖议，平均需要n/2跳(n是節(jié)點(diǎn)總數(shù))虏杰，太低效了！
Chord通過查找表(lookup table)來加速搜索過程拒担。如果鍵值空間為m bit嘹屯，那么每一個(gè)節(jié)點(diǎn)的查找表包含m個(gè)finger pointer。節(jié)點(diǎn)n查找表的第i項(xiàng)s是「順時(shí)針方向上與n的距離不小于$2^{i-1}$」的第一個(gè)節(jié)點(diǎn)从撼，即：
$s=successor((n+2^{i-1}) mod 2^m)$州弟，其中$1<=i<=m$。
在查找過程中低零，一個(gè)節(jié)點(diǎn)根據(jù)查找表婆翔，選擇離鍵值最近的后繼finger pointer作為下一跳節(jié)點(diǎn)，每次可以將搜索空間減半掏婶。整個(gè)過程類似于二分查找啃奴。
通過緩存查詢結(jié)果可以進(jìn)一步加速查找過程。
Chord：副本
數(shù)據(jù)如果只存儲(chǔ)在一個(gè)節(jié)點(diǎn)上雄妥，該節(jié)點(diǎn)下線可能造成數(shù)據(jù)丟失最蕾。為此，Chord為同一數(shù)據(jù)維護(hù)$N=log(2^m)$個(gè)副本老厌。鍵值k的數(shù)據(jù)會(huì)被其后繼的N個(gè)節(jié)點(diǎn)(即successor(k)和其后的N-1個(gè)節(jié)點(diǎn))保存瘟则。
Chord：分區(qū)
Chord不限制所有的節(jié)點(diǎn)都要在一個(gè)位置，事實(shí)上枝秤，該理論原本就是為地理分布的P2P應(yīng)用準(zhǔn)備的醋拧。不論節(jié)點(diǎn)是位于同一機(jī)房內(nèi)，還是不同機(jī)房間淀弹，網(wǎng)絡(luò)故障都可能導(dǎo)致虛擬環(huán)的分區(qū)丹壕。分區(qū)后，Chord的節(jié)點(diǎn)加入退出機(jī)制導(dǎo)致每個(gè)分區(qū)的節(jié)點(diǎn)形成新的虛擬環(huán)薇溃。新虛擬環(huán)的形成過程完全是自動(dòng)的菌赖，無需運(yùn)維人員參與。
假設(shè)有一個(gè)虛擬環(huán)沐序，其部分節(jié)點(diǎn)在歐洲數(shù)據(jù)中心琉用，部分在亞洲數(shù)據(jù)中心忿峻。如果兩個(gè)數(shù)據(jù)中心之間的網(wǎng)絡(luò)連接中斷，Chord會(huì)在每個(gè)數(shù)據(jù)中心形成新的虛擬環(huán)辕羽。
過了一段時(shí)間后逛尚，歐洲數(shù)據(jù)中心和亞洲數(shù)據(jù)中心的通信恢復(fù)，這個(gè)時(shí)候兩個(gè)虛擬環(huán)需要合并刁愿。我們可以指定一些特殊的地標(biāo)節(jié)點(diǎn)绰寞。無地標(biāo)節(jié)點(diǎn)的環(huán)中的所有節(jié)點(diǎn)首先離開它們所在的環(huán)，再重新加入到地標(biāo)節(jié)點(diǎn)所在環(huán)铣口。一段時(shí)間后滤钱，整個(gè)系統(tǒng)又只剩下唯一的一個(gè)虛擬環(huán)。
Chord表現(xiàn)強(qiáng)大的節(jié)點(diǎn)管理能力脑题，能夠在沒有中心節(jié)點(diǎn)參與的情況下件缸，自動(dòng)處理網(wǎng)絡(luò)中的節(jié)點(diǎn)故障。Chord的查找效率也很高叔遂，能夠輕易擴(kuò)展到很大規(guī)模他炊。這些特點(diǎn)是Amazon Dynamo選擇Chord的原因。
Amazon Dynamo：風(fēng)險(xiǎn)
Amazon Dynamo選擇Chord作為整個(gè)系統(tǒng)的基礎(chǔ)已艰。
有時(shí)候痊末，Dynamo表現(xiàn)出來的行為可能會(huì)使開發(fā)者困惑。前面提到哩掺，Chord會(huì)為鍵值k維護(hù)多個(gè)副本凿叠，Dynamo的情況也是類似。現(xiàn)在嚼吞，一個(gè)副本節(jié)點(diǎn)a失去了響應(yīng)盒件。用戶通過put()操作提交了一個(gè)新的數(shù)據(jù)d，該數(shù)據(jù)在保存的時(shí)候跳過了節(jié)點(diǎn)a舱禽。過了一段時(shí)間炒刁，節(jié)點(diǎn)a重新上線。在節(jié)點(diǎn)a同步完數(shù)據(jù)之前呢蔫，用戶查詢數(shù)據(jù)d切心，而a節(jié)點(diǎn)恰好負(fù)責(zé)處理這次查詢飒筑。由于a節(jié)點(diǎn)沒有數(shù)據(jù)d片吊，從用戶角度看，就好像系統(tǒng)把數(shù)據(jù)d丟了协屡。
為了降低這種風(fēng)險(xiǎn)俏脊，Dynamo后臺(tái)修復(fù)進(jìn)程會(huì)負(fù)責(zé)不斷地將數(shù)據(jù)遷移到正確地節(jié)點(diǎn)上。
Amazon Dynamo：最終一致
Dynamo中的副本數(shù)量N是可以配置的肤晓。其中爷贫，每個(gè)鍵值的直接后繼是鍵值的協(xié)調(diào)者认然。
為了加快put()操作的回復(fù)速度，協(xié)調(diào)者使用異步方式同步修改漫萄。經(jīng)過一段時(shí)間后卷员，所有副本上的鍵值才會(huì)被更新到最新版本。在這段同步時(shí)間內(nèi)腾务，客戶端有可能根本看不到鍵值毕骡，也有可能會(huì)讀到鍵值的舊版本。
也就是說岩瘦，Dynamo是一個(gè)弱一致的系統(tǒng)未巫，僅僅保證數(shù)據(jù)的最終一致性。
Amazon Dynamo：法定人數(shù)
Dynamo為每個(gè)寫操作配置法定人數(shù)W(W<=N)启昧。該值的含義是叙凡，一個(gè)寫操作只有成功更新了W個(gè)副本，才會(huì)被認(rèn)為操作成功密末。
同樣握爷，讀操作也有讀法定人數(shù)R(R<=N)，這是一個(gè)讀操作需要讀取的副本數(shù)量严里。
顯然饼拍，W、R值越低田炭，操作的速度越快师抄。
舉一個(gè)簡單地例子，如下圖所示教硫。假設(shè)Dynamo設(shè)置副本數(shù)量N=4叨吮，那么每個(gè)寫操作需要異步復(fù)制到4個(gè)副本；W設(shè)為2瞬矩，那么一個(gè)寫操作只有收到兩個(gè)確認(rèn)才認(rèn)為操作成功茶鉴；R設(shè)為1，那么讀操作在讀取到一個(gè)副本后就立刻返回【坝茫現(xiàn)在涵叮，進(jìn)行一次put()操作，緊接著立刻進(jìn)行一次get()操作伞插。負(fù)責(zé)響應(yīng)get()操作的節(jié)點(diǎn)恰好還未能完成更新割粮。顯然，這次get()操作得到了一個(gè)過時(shí)的數(shù)據(jù)媚污。即使我們將R增大到2舀瓢，還是可能會(huì)發(fā)生這種狀況。
那么耗美，怎樣設(shè)置R和W的值才能保證讀操作總能讀到最新的數(shù)據(jù)呢京髓？答案是航缀，R + W > N。
R + W > N能夠保證讀操作和寫操作有節(jié)點(diǎn)交集堰怨。也就是芥玉，至少有一個(gè)節(jié)點(diǎn)會(huì)被讀操作和寫操作同時(shí)操作到。
R + W > N并不意味著強(qiáng)一致性备图》煽考慮一個(gè)金融系統(tǒng)，一個(gè)用戶的賬戶中有1塊錢诬烹，N = 4, R = 3, W = 2≡曳常現(xiàn)在用戶的賬戶余額增加1，寫操作作用到前兩個(gè)副本C0和C1绞吁，這兩個(gè)副本的賬戶余額變?yōu)?幢痘。操作完成后C0和C1系統(tǒng)同時(shí)下線了，后兩個(gè)副本C2家破、C3尚未應(yīng)用更新颜说。緊接著用戶取出了1塊錢，操作作用到C2汰聋、C3副本上门粪，這兩個(gè)副本的賬戶余額變?yōu)?。C0烹困、C1又重新上線玄妈，這時(shí)用戶查詢到的賬戶余額是兩個(gè)沖突值0、2髓梅。哪一個(gè)值是正確的拟蜻？兩個(gè)值都不正確！
Dynamo并不負(fù)責(zé)處理這種沖突枯饿，而是把這個(gè)燙手山芋丟給了客戶端酝锅。下面將會(huì)講到。
Amazon Dynamo：向量鐘(vector clock)
哪種機(jī)制適用于Dynamo檢測(cè)數(shù)據(jù)的最新版本呢奢方？首先搔扁，讓我們看一下傳統(tǒng)的方案：
-
時(shí)鐘
大部分情況下，時(shí)間戳作為版本號(hào)并不是第一選擇蟋字。云計(jì)算環(huán)境中既有虛擬機(jī)又有物理主機(jī)稿蹲，很難期望這些機(jī)器的時(shí)鐘是完全同步的。如果這些時(shí)鐘不同步愉老，時(shí)間戳很容易導(dǎo)致紊亂场绿。
當(dāng)然剖效，如果你像Google一樣壕一樣屌嫉入，可以使用原子鐘和GPS來提供精確的時(shí)間同步(參見Google Spanner)焰盗。
版本號(hào)
在使用版本號(hào)的系統(tǒng)中，每應(yīng)用一次更新咒林，版本號(hào)就會(huì)遞增熬拒。有兩種方式來實(shí)現(xiàn)版本號(hào)遞增：第一種方式，是由一臺(tái)服務(wù)器完成所有的更新操作垫竞；第二種方式澎粟，是由一個(gè)全局、單一的服務(wù)器產(chǎn)生遞增序列欢瞪。不管哪種方式活烙，都存在單節(jié)點(diǎn)故障隱患。
對(duì)于Dynamo這樣的P2P系統(tǒng)遣鼓，引入一個(gè)負(fù)責(zé)更新或產(chǎn)生時(shí)間戳的節(jié)點(diǎn)合呐，違背去中心化的原則犀盟。
Dynamo給出的解決方案是向量鐘。每一個(gè)節(jié)點(diǎn)為其管理的每一個(gè)數(shù)據(jù)副本維持一個(gè)向量鐘。
考慮這樣一個(gè)場(chǎng)景咙咽，一個(gè)數(shù)據(jù)有3個(gè)副本N0、N1脯颜、N2悠汽。我們?cè)贜0上進(jìn)行了一次更新操作，同時(shí)缸棵，操作被復(fù)制到N1舟茶。N0在更新時(shí)遞增了向量鐘里的版本號(hào)，該向量鐘隨著被修改的數(shù)據(jù)一同被發(fā)送給其它節(jié)點(diǎn)堵第。當(dāng)其它節(jié)點(diǎn)接收到更新稚晚，逐項(xiàng)對(duì)比本地向量鐘和待更新數(shù)據(jù)的向量鐘。如果待更新數(shù)據(jù)的向量鐘的每一項(xiàng)都不小于本地向量鐘型诚，那么數(shù)據(jù)無沖突客燕，新的值可以被接受。Dynamo并不會(huì)貿(mào)然假定數(shù)據(jù)的沖突合并準(zhǔn)則狰贯，而是保留全部的沖突數(shù)據(jù)也搓，等待客戶端處理。
原文是 “If all version stamps are lower than the local ones, there's no conflict. Then, the new value is accepted and the local vector clock is updated.” 應(yīng)該是一個(gè)書寫錯(cuò)誤涵紊。
原文沒有描述向量鐘的具體格式傍妒，給出的示例也是一個(gè)簡化版本。因此摸柄，根據(jù)Dynamo論文稍作補(bǔ)充颤练。
向量鐘記錄同一對(duì)象不同版本間的因果關(guān)系，實(shí)際上是一個(gè)(node,counter)列表(即(節(jié)點(diǎn)驱负，計(jì)數(shù)器)列表)嗦玖。如果第一個(gè)向量鐘每一個(gè)計(jì)數(shù)器都小于第二個(gè)向量鐘對(duì)應(yīng)的計(jì)數(shù)器患雇，那么第二個(gè)向量鐘是由第一個(gè)修改而來的(第一個(gè)是第二個(gè)的祖先)，可以被忽略宇挫；否則苛吱，這兩個(gè)向量鐘是沖突的，需要協(xié)調(diào)器瘪。一個(gè)客戶端更新數(shù)據(jù)時(shí)翠储，必須指定它更新的是哪個(gè)版本，這個(gè)版本由更早的讀操作獲取橡疼。
下圖給出一個(gè)例子援所。一個(gè)客戶端寫了一個(gè)新數(shù)據(jù)。節(jié)點(diǎn)Sx處理了這個(gè)請(qǐng)求欣除，創(chuàng)建了數(shù)據(jù)的向量鐘[(Sx,1)]任斋。緊接著，客戶端又更新了數(shù)據(jù)耻涛，又是Sx處理了這次更新废酷，向量鐘變?yōu)閇(Sx,2)]。[(Sx,2)]可以安全地覆蓋[(Sx,1)]抹缕，當(dāng)然這時(shí)候其它的副本可能還沒看到這次修改澈蟆，它們的向量鐘仍然是[(Sx,1)]。兩個(gè)客戶端同時(shí)進(jìn)行了第二次更新卓研，這兩個(gè)更新分別被Sy趴俘、Sz處理了，Sy奏赘、Sz的向量鐘變?yōu)閇(Sx,2),(Sy,1)]和[(Sx,2),(Sz,1)]寥闪。實(shí)際上，這時(shí)候出現(xiàn)了兩個(gè)沖突的數(shù)據(jù)版本磨淌，Dynamo并不能決定哪個(gè)數(shù)據(jù)是正確地疲憋，所以這兩個(gè)版本都被保存下來。接下來梁只，某個(gè)客戶端同時(shí)讀到了這兩個(gè)版本的數(shù)據(jù)缚柳，可以合寫作[(Sx,2),(Sy,1),(Sz,1)]。它進(jìn)行了數(shù)據(jù)合并搪锣，處理了沖突秋忙，提交了新的數(shù)據(jù)版本[(Sx,3),(Sy,1),(Sz,1)]。這個(gè)版本可以安全地覆蓋之前的所有舊數(shù)據(jù)构舟。
Riak
Dynamo不是一個(gè)開源系統(tǒng)灰追，而Riak是一個(gè)按照Dynamo論文設(shè)計(jì)的開源分布式鍵值數(shù)據(jù)庫，使用Apache License 2.0協(xié)議發(fā)布。單個(gè)Riak節(jié)點(diǎn)據(jù)稱每秒能夠處理數(shù)萬請(qǐng)求弹澎∑酉拢考慮到Dynamo的論文已經(jīng)展示了單集群擴(kuò)展到數(shù)百節(jié)點(diǎn)的能力，類似設(shè)計(jì)的Riak也應(yīng)該能夠做到這一點(diǎn)裁奇。
Riak背后的公司是Basho Technologies桐猬，其中一位創(chuàng)始人就是Eric Brewer麦撵。
Riak的主要特點(diǎn)概括如下：
- 鍵值存儲(chǔ)刽肠，按照Dynamo論文構(gòu)建
- REST風(fēng)格API、Google Protobuf API
- 客戶端支持Java免胃、Python音五、Perl、PHP羔沙、.NET等
- 支持存儲(chǔ)各類數(shù)據(jù)躺涝，包括JSON、XML扼雏、文本坚嗜、圖片等
- 2.0版本有強(qiáng)一致性選項(xiàng)
- 集群搜索
- MapReduce、全文搜索(基于Solr)
- 二級(jí)索引(內(nèi)存诗充、LevelDB引擎)
- 存儲(chǔ)引擎插件
- Bitcast苍蔬、內(nèi)存、LevelDB
Riak 2.0引入了「無沖突復(fù)制的數(shù)據(jù)類型CRDT」(conflict-free replicated data type蝴蜓，CRDT)來處理數(shù)據(jù)沖突碟绑，簡化系統(tǒng)使用。
CRDT是一類抽象數(shù)據(jù)類型(abstract data type)茎匠，它們能夠自行解決數(shù)據(jù)沖突格仲，并達(dá)到最終一致狀態(tài)。換一種說法就是：你可以在這類數(shù)據(jù)類型上隨時(shí)進(jìn)行任何允許的操作诵冒，而不用去擔(dān)心數(shù)據(jù)沖突凯肋，數(shù)據(jù)沖突的處理將由節(jié)點(diǎn)/副本完成。
CRDT背后的把戲其實(shí)很簡單汽馋，這些數(shù)據(jù)類型要么操作是可以交換的否过，要么明確規(guī)定了沖突情況下應(yīng)該遵循的規(guī)則。例如惭蟋，Riak的沖突合并規(guī)則就是「加操作優(yōu)先」苗桂。
Riak 2.0提供的CRDT包括計(jì)數(shù)器、集合告组、map煤伟、寄存器、flag等。
舉一個(gè)例子便锨。假設(shè)你在兩個(gè)節(jié)點(diǎn)/副本上保存有一個(gè)集合{a}围辙。兩個(gè)節(jié)點(diǎn)被分區(qū)后，變成了兩個(gè)數(shù)據(jù)版本放案，分別為{a}姚建、{}。怎樣合并沖突呢吱殉？首先要明白掸冤，導(dǎo)致這種情況的原因有兩個(gè)，要么在分區(qū)前兩個(gè)集合都是空的友雳，要么在分區(qū)后其中一個(gè)集合的元素被移走了稿湿。Riak通過比較副本維護(hù)的向量鐘能夠區(qū)分這兩種情況。在這個(gè)例子中押赊，第二種情況才是正確的饺藤。
原PPT的這個(gè)例子沒有很好地體現(xiàn)CRDT，根據(jù)Dynamo論文的描述流礁，有{{N0,0},{N1,1}} > {{N0,0},{N1,0}}涕俗，兩個(gè)數(shù)據(jù)其實(shí)沒有沖突，只是一個(gè)較舊而已神帅。
Dynamo及類似系統(tǒng)總結(jié)
在CAP語境下再姑，Dynamo是一個(gè)極端的AP系統(tǒng)的例子。
Dynamo能夠工作在高度不穩(wěn)定的網(wǎng)絡(luò)環(huán)境下枕稀，使用高度不穩(wěn)定的硬件提供無限的存儲(chǔ)空間询刹。整個(gè)系統(tǒng)是完全去中心化的，所有的數(shù)據(jù)都有多個(gè)副本萎坷。由于沒有確保一致性凹联，系統(tǒng)的響應(yīng)速度很快。系統(tǒng)具備無限擴(kuò)展的能力哆档。系統(tǒng)最大的缺陷在于需要客戶端來修復(fù)不一致數(shù)據(jù)蔽挠。
Dynamo的數(shù)據(jù)模型具備以下特點(diǎn)：
- 以字符串為鍵，二進(jìn)制數(shù)據(jù)為值的鍵值存儲(chǔ)
- 提供很少的抽象數(shù)據(jù)類型瓜浸，多數(shù)是BLOB對(duì)象
- 不同的鍵之間的聯(lián)系很弱
- 搜索速度取決于鍵值查找速度和批處理策略
- 分片(sharding)澳淑、垂直分區(qū)(vertical partitioning)
Dynamo適用場(chǎng)景：
- 簡單的模式
- 簡單的ad-hoc查詢
- 擴(kuò)展性、可用性是必要需求
Dynamo不適用場(chǎng)景：
- 事務(wù)
- 范圍掃描
未完待續(xù)...
下一部分將介紹另外一種重要的NoSQL插佛，Google Bigtable杠巡，參見：
