Dynamo 是 Amazon 公司的一個(gè)分布式存儲(chǔ)引擎。 那么這個(gè)什么引擎又是什么?
首先，假設(shè)一個(gè)場(chǎng)景，你的網(wǎng)站要存儲(chǔ)用戶登陸的IP。這個(gè)問題怎么解決呢?傳統(tǒng)的方法是用數(shù)據(jù)庫(kù)。數(shù)據(jù)庫(kù)提供了方便的操作接口，復(fù)雜的查詢能力以及事物的保證。
好，現(xiàn)在假設(shè)大家都很喜歡你的網(wǎng)站，訪問的人越來越多。一個(gè)數(shù)據(jù)庫(kù)已經(jīng)處理不過來了。于是你安裝了3臺(tái)數(shù)據(jù)庫(kù)主機(jī)，把用戶分成了三類(男人，女人，IT人;總是有某種方法把用戶分成數(shù)目大致差不多的幾個(gè)部分吧)。
每次訪問的時(shí)候，先看用戶屬于哪一類，然后直接訪問存儲(chǔ)那類用戶數(shù)據(jù)的數(shù)據(jù)庫(kù)。于是處理能力增加了三倍。這個(gè)時(shí)候你已經(jīng)實(shí)現(xiàn)了一個(gè)分布式的存儲(chǔ)引 擎，Dynamo 就是一個(gè)類似的東西。只是它的可靠性，可用性等方面更好一點(diǎn)而已。下面我們看看那個(gè)簡(jiǎn)單的分布式存儲(chǔ)系統(tǒng)有什么不方便的地方，而Dynamo是如何解決 的。
簡(jiǎn)單分布式系統(tǒng)實(shí)現(xiàn)云存儲(chǔ)可能存在的問題先列舉一下簡(jiǎn)單的分布式系統(tǒng)可能存在的問題吧：
1 很難擴(kuò)容 ：如果現(xiàn)在業(yè)務(wù)發(fā)展迅速，3臺(tái)主機(jī)撐不住了，需要加到5臺(tái)主機(jī)，那要如何處理呢?首先要更改分類方法，把用戶分成5類，然后重新遷移已經(jīng)存在的數(shù)據(jù)。你要在網(wǎng)站上貼個(gè)條子，“系統(tǒng)維護(hù)中”，然后開始偉大的遷移工程，等到終于遷移完成，發(fā)現(xiàn)其實(shí)3臺(tái)也不用了，用戶都走光了。
2 數(shù)據(jù)可靠性 無法保證：有一天，發(fā)現(xiàn)有一臺(tái)數(shù)據(jù)庫(kù)服務(wù)器的硬盤壞了，這下麻煩就來了，本來網(wǎng)站就不賺錢，沒用什么高檔機(jī)器，只有一個(gè)定期的增量備份而已。經(jīng)過一天復(fù)雜的恢復(fù)工作，你還要對(duì)部分用戶說，麻煩你們把做過的事情再做一遍啊。
3 單點(diǎn)問題 ：負(fù)責(zé)把用戶分類，然后決定使用哪個(gè)數(shù)據(jù)服務(wù)器的那臺(tái)主機(jī)是網(wǎng)站的命根子啊，它如果宕機(jī)，所有的數(shù)據(jù)都不能訪問了，它如果滿負(fù)荷了，增加數(shù)據(jù)服務(wù)器也不會(huì)對(duì)整體性能有幫助。我好像看到一臺(tái)貼滿著驅(qū)邪保平安符咒的pc server。
這幾個(gè)問題，看似不大，解決起來還真的不容易呢。尤其是想到自己的網(wǎng)站也許有一天也會(huì)和google有一樣多的用戶(可能因?yàn)槟闶翘觳呕蛘遟oogle快倒閉了)。現(xiàn)在我們看看 Dynnamo 是怎么解決的吧。

http://hi.baidu.com/beibeiboo/blog/item/71654029e81001f498250a0f.html Dynamo虛節(jié)點(diǎn)思想解決擴(kuò)容問題
Dynamo虛節(jié)點(diǎn)思想解決擴(kuò)容問題，這個(gè)問題實(shí)際上是數(shù)據(jù)分布方式的問題(怎么分組)。最簡(jiǎn)單最容易想到的就是根據(jù)資源數(shù)目對(duì)數(shù)據(jù)進(jìn)行哈希分布，比如算 出一個(gè)哈希值，然后對(duì)資源數(shù)取模。這種簡(jiǎn)單處理的結(jié)果就是當(dāng)資源數(shù)變化的時(shí)候，每個(gè)數(shù)據(jù)重新取模后，其分布方式都可能變化，從而需要遷移大量的數(shù)據(jù)。
舉個(gè)簡(jiǎn)單的例子來說明一下，假設(shè)我的數(shù)據(jù)是自然數(shù)(1-20)，資源現(xiàn)在是三臺(tái)主機(jī)(A，B，C)，采用取模分配方式，那么分配后A主機(jī)的數(shù)據(jù)為 (1，4，7，10，13，16，19)，B為(2，5，8，11，14，17，20) C(3，6，9，12，15，18) 現(xiàn)在增加一臺(tái)主機(jī)D，重新分布后的結(jié)果是A(1，5，9，13，17) B(2，6，10，14，18) C(3，7，11，15，19) D(4，8，12，15，20) 。
可以看到，有大量的數(shù)據(jù)需要從一臺(tái)主機(jī)遷移到另外一臺(tái)主機(jī)。這個(gè)遷移過程是很消耗性能的。需要找到一種方式來盡可能減少對(duì)現(xiàn)存數(shù)據(jù)的影響(沒有影響當(dāng)然也不可能，那說明新添加的主機(jī)沒有數(shù)據(jù))。 
Dynamo 采用的是 consistent hashing 來解決這個(gè)問題的。 那么我們先來了解一下什么是consistent hashing。先想象一個(gè)圓，或者你自己的手表表面，把它看成是一個(gè)首尾相接的數(shù)軸，現(xiàn)在我們的數(shù)據(jù)，自然數(shù)，已經(jīng)分布到這個(gè)圓上了，我們可以把我們的資源采用某種方式，隨機(jī)的分布到這個(gè)圓上(圖1-1)。 【虎.無名：和使用memcached技術(shù)類似，在節(jié)點(diǎn)變更時(shí)提高命中率 。】
現(xiàn)在我們讓每一個(gè)資源負(fù)責(zé)它和上一個(gè)資源之間的數(shù)據(jù)，就是說A來負(fù)責(zé)區(qū)間(C，A]，B來負(fù)責(zé)區(qū)間(A，B]，C負(fù)責(zé)區(qū)間(B，C]。采用這種策略，當(dāng)我 們?cè)黾右粋€(gè)資源主機(jī)的時(shí)候，比如D，那么我們只需要影響新節(jié)點(diǎn)相鄰的節(jié)點(diǎn)A所負(fù)責(zé)的范圍(只需要將A中(C，D]這個(gè)區(qū)間的數(shù)據(jù)遷移到D上)就可以了。
因?yàn)橘Y源節(jié)點(diǎn)是隨機(jī)分布到數(shù)據(jù)圓上的，所以當(dāng)資源節(jié)點(diǎn)的數(shù)量足夠多的時(shí)候，可以認(rèn)為每個(gè)節(jié)點(diǎn)的負(fù)載基本是均衡的。這是原始的consistent hashing 。
Dynamo并沒有采用這個(gè)模型。這個(gè)理想的理論模型跟現(xiàn)實(shí)之間有一個(gè)問題，在這個(gè)理論模型上，每個(gè)資源節(jié)點(diǎn)的能力是一樣的。 我的意思是，他們有相同的cpu，內(nèi)存，硬盤等，也就是有相同的處理能力。可現(xiàn)實(shí)世界，我們使用的資源卻各有不同，新買的n核機(jī)器和老的奔騰主機(jī)一起為了節(jié)約成本而合作。如果只是這么簡(jiǎn)單的把機(jī)器直接分布上去，性能高的機(jī)器得不到充分利用，性能低的機(jī)器處理不過來。
這個(gè)問題怎么解決呢?Dynamo 使用的方法是虛節(jié)點(diǎn) 。把上面的A B C等都想象成一個(gè)邏輯上的節(jié)點(diǎn)。一臺(tái)真實(shí)的物理節(jié)點(diǎn)可能會(huì)包含幾個(gè)虛節(jié)點(diǎn)(邏輯節(jié)點(diǎn))，也可能只包含一個(gè)，看機(jī)器的性能而定 。
等等，好像我們的網(wǎng)站還沒發(fā)展成 google 呢，我們能使用的硬件資源還不多，比如就4臺(tái)主機(jī)。這個(gè)時(shí)候采用上面的方式，把資源隨機(jī)分布上去，幾乎一定會(huì)不均衡。這要怎么辦呢?我們可以把那個(gè)數(shù)據(jù)圓分成Q等份(每一個(gè)等份就是一個(gè)虛節(jié)點(diǎn))，這個(gè)Q要遠(yuǎn)大于我們的資源數(shù) 。
現(xiàn)在假設(shè)我們有S個(gè)資源，那么每個(gè)資源就承擔(dān)Q/S個(gè)等份。 當(dāng)一個(gè)資源節(jié)點(diǎn)離開系統(tǒng)的時(shí)候，它所負(fù)責(zé)的等份要重新均分到其他資源節(jié)點(diǎn)上，一個(gè)新節(jié)點(diǎn)加入的時(shí)候，要從其他的節(jié)點(diǎn)”偷”到一定數(shù)額的等份。
這個(gè)策略下，當(dāng)一個(gè)節(jié)點(diǎn)離開系統(tǒng)的時(shí)候，雖然需要影響到很多節(jié)點(diǎn)，但是注意，遷移的數(shù)據(jù)總量只是離開那個(gè)節(jié)點(diǎn)的數(shù)據(jù)量。 同樣，一個(gè)新節(jié)點(diǎn)的加入，遷移的數(shù)據(jù)總量也只是一個(gè)新節(jié)點(diǎn)的數(shù)據(jù)量。 之所以有這個(gè)效果是因?yàn)?strong>Q的存在，使得增加和減少機(jī)器的時(shí)候不需要對(duì)已有的數(shù)據(jù)做重新哈希 。這個(gè)策略的要求是Q>>S (其實(shí)還有存儲(chǔ)備份的問題，現(xiàn)在還沒介紹到，假設(shè)每個(gè)數(shù)據(jù)存儲(chǔ)N個(gè)備份 則要滿足Q>>S*N )。如果業(yè)務(wù)快速發(fā)展，使得不斷的增加主機(jī)，從而導(dǎo)致Q不再滿足Q>>S，那么這個(gè)策略將不斷的退化。

http://hi.baidu.com/beibeiboo/blog/item/c04eed0ad4aac41594ca6b0e.html Dynamo的三點(diǎn)備份模型
第二個(gè)問題是數(shù)據(jù)可靠性，因?yàn)槲覀兪褂玫氖橇畠r(jià)的pc機(jī)，硬盤損毀或者是其他原因?qū)е碌闹鳈C(jī)不可用是很經(jīng)常的事情。
做這樣一個(gè)估算，假設(shè)一臺(tái)pc機(jī)平均三年就會(huì)有一次失效，不可用。那么當(dāng)一個(gè)一千臺(tái)機(jī)器的集群，基本上每天都有機(jī)器壞掉，所以某主機(jī)不可用是常態(tài)，系統(tǒng)必須可以在這樣的情況下繼續(xù)提供服務(wù) (哦 雖然你的網(wǎng)站現(xiàn)在剛剛只需要4臺(tái)主機(jī)，可是別忘了，它要成長(zhǎng)成為google的)。
當(dāng)然，廉價(jià)pc的好處就是便宜。所以我們可以增加系統(tǒng)中數(shù)據(jù)的備份來使得系統(tǒng)在某臺(tái)機(jī)器掛掉的時(shí)候仍舊可用。大家最先想到的方案可能就是對(duì)每個(gè)節(jié)點(diǎn)，建立一個(gè)備份節(jié)點(diǎn)，如果主節(jié)點(diǎn)壞掉了，備份節(jié)點(diǎn)可以立刻頂上去(雙機(jī)熱備)。
但是仔細(xì)想一下，這個(gè)方案是讓人不放心的。因?yàn)楫?dāng)一主一備中的某一臺(tái)機(jī)器壞掉，另外一臺(tái)就成了一個(gè)單點(diǎn)運(yùn)行的節(jié)點(diǎn)。這個(gè)時(shí)候另外一個(gè)節(jié)點(diǎn)一旦發(fā)生錯(cuò)誤，服務(wù)就變得不可用，數(shù)據(jù)也有可能丟失。在一個(gè)要求高可靠性的系統(tǒng)上，這是不可忍受的。
我們剛剛估算了一個(gè)大的集群每天都有機(jī)器掛掉。而這種錯(cuò)誤，一定要人工介入才能解決。想想系統(tǒng)管理員每天在機(jī)房里更換主機(jī)的情景以及其他不可預(yù)料情況(系統(tǒng)管理員休假或者新買的主機(jī)沒按時(shí)到貨等)，再想想系統(tǒng)每天都有節(jié)點(diǎn)在單點(diǎn)運(yùn)行，真的是很可怕的事情。
事實(shí)上，一般工業(yè)界認(rèn)為比較安全的備份數(shù)應(yīng)該是3份。 好，那么我們看看做這個(gè)備份的時(shí)候需要注意的問題。首先，如何選擇備份節(jié)點(diǎn)。我們可以簡(jiǎn)單的選擇順序上的后兩個(gè)節(jié)點(diǎn)為備份節(jié)點(diǎn)，比如存在節(jié)點(diǎn)A的數(shù)據(jù)，備份到節(jié)點(diǎn)B和C。但是當(dāng)我們前面引入了虛節(jié)點(diǎn)的概念的時(shí)候就要注意了，有可能C節(jié)點(diǎn)和A節(jié)點(diǎn)在同一臺(tái)物理機(jī)器上，這個(gè)時(shí)候就不能選擇C做為A的備份了 。
下一個(gè)問題，當(dāng)一個(gè)節(jié)點(diǎn)離開系統(tǒng)的時(shí)候，比如宕機(jī)，這個(gè)節(jié)點(diǎn)上存儲(chǔ)的信息需要繼續(xù)備份到其它節(jié)點(diǎn)上。雖然節(jié)點(diǎn)離開了系統(tǒng)，但是因?yàn)閭浞莸拇嬖冢覀兺ㄟ^其他節(jié)點(diǎn)可以恢復(fù)出本節(jié)點(diǎn)的所有信息，因?yàn)樵摴?jié)點(diǎn)的離開，這部分信息的備份數(shù)會(huì)比要求的備份數(shù)少一，所以需要把這部分?jǐn)?shù)據(jù)做再備份 。同樣，當(dāng)一個(gè)節(jié)點(diǎn)加入系統(tǒng)，從其他節(jié)點(diǎn)偷了數(shù)據(jù)后，其他節(jié)點(diǎn)也需要相應(yīng)減少備份數(shù)。而一個(gè)節(jié)點(diǎn)如果只是暫時(shí)性的不可達(dá)，也就是失效一個(gè)很短的時(shí)間(這種情況是最常發(fā)生的)，那么需要其他節(jié)點(diǎn)暫時(shí)接管這個(gè)節(jié)點(diǎn)的工作，在其可用的時(shí)候，把數(shù)據(jù)增量傳送回該節(jié)點(diǎn) 。

http://hi.baidu.com/beibeiboo/blog/item/c3dda333d0713049ac4b5f0d.html 2009-12-02 22:38 NWR模型與同步和異步備份
在設(shè)計(jì)上述需求的解決方案的時(shí)候，還要考慮一個(gè)問題，各個(gè)節(jié)點(diǎn)間數(shù)據(jù)備份是同步還是異步。 假設(shè)我們要求寫請(qǐng)求總是盡可能的成功，那么我們的策略是寫任何一個(gè)節(jié)點(diǎn)成功就認(rèn)為成功。節(jié)點(diǎn)之間的數(shù)據(jù)通過異步形式達(dá)成一致，這個(gè)時(shí)候讀請(qǐng)求可能讀不到最新寫進(jìn)去的信息。
比如我們一個(gè)數(shù)據(jù)在A B C 三個(gè)節(jié)點(diǎn)各存一份(系統(tǒng)中有三個(gè)備份的時(shí)候，下面的討論都是基于這個(gè)假設(shè)的)，那么當(dāng)寫A成功后，另外一個(gè)進(jìn)程從節(jié)點(diǎn)C讀數(shù)據(jù)，這個(gè)時(shí)候C還沒收到最新的數(shù)據(jù)，只能給讀請(qǐng)求一個(gè)較老的版本。這個(gè)可能會(huì)帶來大問題;同樣，如果我們希望讀請(qǐng)求總能讀到正確的數(shù)據(jù)，那我們的策略是寫的時(shí)候要等A B C三個(gè)節(jié)點(diǎn)都寫成功了才認(rèn)為寫成功 。這個(gè)時(shí)候?qū)懻?qǐng)求可能要耗較多的時(shí)間，甚至根本不能完成(如果有節(jié)點(diǎn)不可達(dá))也就是說，系統(tǒng)的一致性，可靠性，原子性，隔離性的問題(ACID)是無法同時(shí)達(dá)到的。只能在其中做出取舍 。
Dynamo 的處理方式是把這個(gè)選擇權(quán)交給用戶，這就是它的N W R模型。N代表N個(gè)備份，W代表要寫入至少W份才認(rèn)為成功，R表示至少讀取R個(gè)備份。配置的時(shí)候要求W+R > N。 因?yàn)閃+R > N， 所以 R > N-W 這個(gè)是什么意思呢?就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的倍數(shù)的差值要大 。也就是說，每次讀取，都至少讀取到一個(gè)最新的版本。從而不會(huì)讀到一份舊數(shù)據(jù)。 當(dāng)我們需要高可寫的環(huán)境的時(shí)候(例如，amazon的購(gòu)物車的添加請(qǐng)求應(yīng)該是永遠(yuǎn)不被拒絕的)我們可以配置W = 1 如果N=3 那么R = 3。 這個(gè)時(shí)候只要寫任何節(jié)點(diǎn)成功就認(rèn)為成功，但是讀的時(shí)候必須從所有的節(jié)點(diǎn)都讀出數(shù)據(jù)。 如果我們要求讀的高效率，我們可以配置 W=N R=1。這個(gè)時(shí)候任何一個(gè)節(jié)點(diǎn)讀成功就認(rèn)為成功，但是寫的時(shí)候必須寫所有三個(gè)節(jié)點(diǎn)成功才認(rèn)為成功 。
大家注意，一個(gè)操作的耗時(shí)是幾個(gè)并行操作中最慢一個(gè)的耗時(shí)。比如R=3的時(shí)候，實(shí)際上是向三個(gè)節(jié)點(diǎn)同時(shí)發(fā)了讀請(qǐng)求，要三個(gè)節(jié)點(diǎn)都返回結(jié)果才能認(rèn)為成功。 假設(shè)某個(gè)節(jié)點(diǎn)的響應(yīng)很慢，它就會(huì)嚴(yán)重拖累一個(gè)讀操作的響應(yīng)速度。

http://hi.baidu.com/beibeiboo/blog/item/94b44cd35dd8570a3bf3cf03.html 2009-12-02 22:33 vector clock算法保證版本信息
解決數(shù)據(jù)版本問題 
這里我們需要討論一下數(shù)據(jù)版本問題，這個(gè)問題不僅僅存在于分布式系統(tǒng)，只是分布式系統(tǒng)的一些要求使得這個(gè)問題更復(fù)雜。 先 看個(gè)簡(jiǎn)單的例子，用戶x對(duì)key1做了一次寫入操作，我們?cè)O(shè)值是數(shù)字3。然后用戶y讀取了key1，這個(gè)時(shí)候用戶y知道的值是3。然后用戶x對(duì)值做了一 個(gè)+1操作，將新值寫入，現(xiàn)在key1的值是4了。而用戶y也做了一次+1操作，然后寫入，因?yàn)橛脩魕讀到的值是3，y不知道這個(gè)值現(xiàn)在已經(jīng)變化了，結(jié)果 按照語義本應(yīng)該是5的值，現(xiàn)在還是4。
解決這個(gè)問題常用的方法是設(shè)置一個(gè)版本值。用戶x第一次寫入key1 值3的時(shí)候，產(chǎn)生一個(gè)版本設(shè)為v1。用戶y讀取的信息中包括版本編號(hào)v1。當(dāng)x做了加1把值4寫入的時(shí)候，告訴server自己拿到的是版本v1，要在 v1的基礎(chǔ)上把值改成4。server發(fā)現(xiàn)自己保存的版本的確是v1所以就同意這個(gè)寫入，并且把版本改成v2。 這個(gè)時(shí)候y也要寫入4，并且宣稱自己是在版本v1上做的修改。
但是因?yàn)閟erver發(fā)現(xiàn)自己手里已經(jīng)是版本v2了，所以server就拒絕y的寫入請(qǐng)求，告訴y，版本錯(cuò)誤。 這個(gè)算法在版本沖突的時(shí)候經(jīng)常被使用。但是剛才我們描述的分布式系統(tǒng)不能簡(jiǎn)單采用這個(gè)方式來實(shí)現(xiàn)。
假設(shè)我們?cè)O(shè)置了N=3 W=1。現(xiàn)在x寫入key1 值3，這個(gè)請(qǐng)求被節(jié)點(diǎn)A處理，生成了v1版本的數(shù)據(jù)。然后x用戶又在版本v1上進(jìn)行了一次key1值4的寫操作，這個(gè)請(qǐng)求這次是節(jié)點(diǎn)C處理的。但是節(jié)點(diǎn)C 還沒有收到上一個(gè)A接收的版本(數(shù)據(jù)備份是異步進(jìn)行的)如果按照上面的算法，他應(yīng)該拒絕這個(gè)請(qǐng)求，因?yàn)樗涣私獍姹緑1的信息。但是實(shí)際上是不可以拒絕的，因?yàn)槿绻鸆拒絕了寫請(qǐng)求，實(shí)際上W=1這個(gè)配置，這個(gè)服務(wù)器向客戶做出的承諾將被打破，從而使得系統(tǒng)的行為退化成W=N的形式。 那么C接收了這個(gè)請(qǐng)求，就可能產(chǎn)生前面提到的不一致性。如何解決這個(gè)問題呢?
Dynamo 的方法是保留所有這些版本，用vector clock記錄版本信息。當(dāng)讀取操作發(fā)生的時(shí)候返回多個(gè)版本，由客戶端的業(yè)務(wù)層來解決這個(gè)沖突合并各個(gè)版本。當(dāng)然客戶端也可以選擇最簡(jiǎn)單的策略，就是最近一次的寫覆蓋以前的寫。
vector clock算法保證版本信息 
這里又引入了一個(gè)vector clock算法，這里簡(jiǎn)單介紹一下。可以把這個(gè)vector clock想象成每個(gè)節(jié)點(diǎn)都記錄自己的版本信息，而一個(gè)數(shù)據(jù)，包含所有這些版本信息。來看一個(gè)例子：假設(shè)一個(gè)寫請(qǐng)求，第一次被節(jié)點(diǎn)A處理了。節(jié)點(diǎn)A會(huì)增加 一個(gè)版本信息(A，1)。我們把這個(gè)時(shí)候的數(shù)據(jù)記做D1(A，1)。 然后另外一個(gè)對(duì)同樣key(這一段討論都是針對(duì)同樣的key的)的請(qǐng)求還是被A處理了于是有D2(A，2)。
這個(gè)時(shí)候，D2是可以覆蓋D1的，不會(huì)有沖突產(chǎn)生。現(xiàn)在我們假設(shè)D2傳播到了所有節(jié)點(diǎn)(B和C)，B和C收到的數(shù)據(jù)不是從客戶產(chǎn)生的，而是別人復(fù)制給他們 的，所以他們不產(chǎn)生新的版本信息，所以現(xiàn)在B和C都持有數(shù)據(jù)D2(A，2)。好，繼續(xù)，又一個(gè)請(qǐng)求，被B處理了，生成數(shù)據(jù)D3(A，2;B，1)，因?yàn)檫@ 是一個(gè)新版本的數(shù)據(jù)，被B處理，所以要增加B的版本信息。
假設(shè)D3沒有傳播到C的時(shí)候又一個(gè)請(qǐng)求被C處理記做D4(A，2;C，1)。假設(shè)在這些版本沒有傳播開來以前，有一個(gè)讀取操作，我們要記得，我們的W=1 那么R=N=3，所以R會(huì)從所有三個(gè)節(jié)點(diǎn)上讀，在這個(gè)例子中將讀到三個(gè)版本。A上的D2(A，2);B上的D3(A，2;B，1);C上的D4(A，2; C，1)這個(gè)時(shí)候可以判斷出，D2已經(jīng)是舊版本，可以舍棄，但是D3和D4都是新版本，需要應(yīng)用自己去合并。
如果需要高可寫性，就要處理這種合并問題。好假設(shè)應(yīng)用完成了沖入解決，這里就是合并D3和D4版本，然后重新做了寫入，假設(shè)是B處理這個(gè)請(qǐng)求，于是有 D5(A，2;B，2;C，1);這個(gè)版本將可以覆蓋掉D1-D4那四個(gè)版本。這個(gè)例子只舉了一個(gè)客戶的請(qǐng)求在被不同節(jié)點(diǎn)處理時(shí)候的情況， 而且每次寫更新都是可接受的，大家可以自己更深入的演算一下幾個(gè)并發(fā)客戶的情況，以及用一個(gè)舊版本做更新的情況。
上面問題看似好像可以通過在三個(gè)節(jié)點(diǎn)里選擇一個(gè)主節(jié)點(diǎn)來解決，所有的讀取和寫入都從主節(jié)點(diǎn)來進(jìn)行。但是這樣就違背了W=1這個(gè)約定，實(shí)際上還是退化到W=N的情況了。所以如果系統(tǒng)不需要很大的彈性，W=N為所有應(yīng)用都接受，那么系統(tǒng)的設(shè)計(jì)上可以得到很大的簡(jiǎn)化。 Dynamo為了給出充分的彈性而被設(shè)計(jì)成完全的對(duì)等集群(peer to peer)，網(wǎng)絡(luò)中的任何一個(gè)節(jié)點(diǎn)都不是特殊的 。
解決單點(diǎn)故障問題 
最后還有一個(gè)單點(diǎn)故障的問題，這個(gè)問題的解決要求系統(tǒng)構(gòu)建的時(shí)候是完全分布式，不存在一個(gè)核心的 。 例如傳統(tǒng)的存儲(chǔ)系統(tǒng)里面往往存在一個(gè)中心節(jié)點(diǎn)，這個(gè)單點(diǎn)的存在使得系統(tǒng)在這一點(diǎn)上變得很脆弱。解決方法就是讓系統(tǒng)的每個(gè)節(jié)點(diǎn)都可以承擔(dān)起所有需要的功能。 這個(gè)問題的解決涉及到事情比較多，以亞馬遜平臺(tái)的Dynamo分布式存儲(chǔ)引擎來說，有Seed節(jié)點(diǎn)的概念，不過本文我們暫時(shí)不做過多剖析。

http://storage.it168.com/a2009/1013/757/000000757579_3.shtml 詳細(xì)解析Dynamo存儲(chǔ)引擎
NWR模型與同步和異步備份 
在設(shè)計(jì)上述需求的解決方案的時(shí)候，還要考慮一個(gè)問題，各個(gè)節(jié)點(diǎn)間數(shù)據(jù)備份是同步還是異步。假設(shè)我們要求寫請(qǐng)求總是盡可能的成功，那么我們的策略是寫任何一個(gè)節(jié)點(diǎn)成功就認(rèn)為成功。節(jié)點(diǎn)之間的數(shù)據(jù)通過異步形式達(dá)成一致，這個(gè)時(shí)候讀請(qǐng)求可能讀不到最新寫進(jìn)去的信息。
比如我們一個(gè)數(shù)據(jù)在A B C 三個(gè)節(jié)點(diǎn)各存一份(系統(tǒng)中有三個(gè)備份的時(shí)候，下面的討論都是基于這個(gè)假設(shè)的)，那么當(dāng)寫A成功后，另外一個(gè)進(jìn)程從節(jié)點(diǎn)C讀數(shù)據(jù)，這個(gè)時(shí)候C還沒收到最新的 數(shù)據(jù)，只能給讀請(qǐng)求一個(gè)較老的版本。這個(gè)可能會(huì)帶來大問題;同樣，如果我們希望讀請(qǐng)求總能讀到正確的數(shù)據(jù)，那我們的策略是寫的時(shí)候要等A B C三個(gè)節(jié)點(diǎn)都寫成功了才認(rèn)為寫成功。這個(gè)時(shí)候?qū)懻?qǐng)求可能要耗較多的時(shí)間，甚至根本不能完成(如果有節(jié)點(diǎn)不可達(dá))也就是說，系統(tǒng)的一致性，可靠性，原子性，隔離性的問題(ACID)是無法同時(shí)達(dá)到的。只能在其中做出取舍 。
Dynamo 的處理方式是把這個(gè)選擇權(quán)交給用戶，這就是它的N W R模型。N代表N個(gè)備份，W代表要寫入至少W份才認(rèn)為成功，R表示至少讀取R個(gè)備份。配置的時(shí)候要求W+R > N 。 因?yàn)閃+R > N， 所以 R > N-W 這個(gè)是什么意思呢?就是讀取的份數(shù)一定要比總備份數(shù)減去確保寫成功的倍數(shù)的差值要大。
也就是說，每次讀取，都至少讀取到一個(gè)最新的版本。從而不會(huì)讀到一份舊數(shù)據(jù)。當(dāng)我們需要高可寫的環(huán)境的時(shí)候(例如，amazon的購(gòu)物車的添加請(qǐng)求應(yīng)該是 永遠(yuǎn)不被拒絕的)我們可以配置W = 1 如果N=3 那么R = 3。 這個(gè)時(shí)候只要寫任何節(jié)點(diǎn)成功就認(rèn)為成功，但是讀的時(shí)候必須從所有的節(jié)點(diǎn)都讀出數(shù)據(jù)。如果我們要求讀的高效率，我們可以配置 W=N R=1。這個(gè)時(shí)候任何一個(gè)節(jié)點(diǎn)讀成功就認(rèn)為成功，但是寫的時(shí)候必須寫所有三個(gè)節(jié)點(diǎn)成功才認(rèn)為成功。
大家注意，一個(gè)操作的耗時(shí)是幾個(gè)并行操作中最慢一個(gè)的耗時(shí)。比如R=3的時(shí)候，實(shí)際上是向三個(gè)節(jié)點(diǎn)同時(shí)發(fā)了讀請(qǐng)求，要三個(gè)節(jié)點(diǎn)都返回結(jié)果才能認(rèn)為成功。假設(shè)某個(gè)節(jié)點(diǎn)的響應(yīng)很慢，它就會(huì)嚴(yán)重拖累一個(gè)讀操作的響應(yīng)速度。

http://www.dbanotes.net/techmemo/amazon_dynamo.html Amazon 的 Dynamo 架構(gòu)
作者: Fenng | 可以轉(zhuǎn)載, 但必須以超鏈接形式標(biāo)明文章原始出處和作者信息及版權(quán)聲明.

http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html Amazon Dynamo 這個(gè)高可用、可擴(kuò)展存儲(chǔ)體系 支撐了Amazon 不少核心服務(wù).

先看一個(gè)示意圖:

從上圖可以看出，Amazon 的架構(gòu)是完全的分布式，去中心化。存儲(chǔ)層也做到了分布式 。

Dynamo 概述

Dynamo 的可擴(kuò)展性和可用性采用的都比較成熟的技術(shù)，數(shù)據(jù)分區(qū) 并用改進(jìn)的一致性哈希(consistent hashing)方式進(jìn)行復(fù)制，利用數(shù)據(jù)對(duì)象的版本化實(shí)現(xiàn)一致性。復(fù)制時(shí)因?yàn)楦庐a(chǎn)生的一致性問題的維護(hù)采取類似 quorum 的機(jī)制以及去中心化的復(fù)制同步協(xié)議。 Dynamo 是完全去中心化的系統(tǒng)，人工管理工作很小。

強(qiáng)調(diào)一下 Dynamo 的”額外”特點(diǎn)：
1) 總是可寫 
2) 可以根據(jù)應(yīng)用類型優(yōu)化

關(guān)鍵詞

Key : Key 唯一代表一個(gè)數(shù)據(jù)對(duì)象，對(duì)該數(shù)據(jù)對(duì)象的讀寫操通過 Key 來完成.
節(jié)點(diǎn)(node) ：通常是一臺(tái)自帶硬盤的主機(jī)。每個(gè)節(jié)點(diǎn)有三個(gè) Java 寫的組件：請(qǐng)求協(xié)調(diào)器(request coordination)、成員與失敗檢測(cè)、本地持久引擎(local persistence engine)
實(shí)例(instance) ；每個(gè)實(shí)例由一組節(jié)點(diǎn)組成，從應(yīng)用的角度看，實(shí)例提供 IO 能力。一個(gè)實(shí)例上的節(jié)點(diǎn)可能位于不同的數(shù)據(jù)中心內(nèi), 這樣一個(gè)數(shù)據(jù)中心出問題也不會(huì)導(dǎo)致數(shù)據(jù)丟失。

上面提到的本地持久引擎支持不同的存儲(chǔ)引擎 。Dynamo 上最主要的引擎是 Berkeley Database Transactional Data Store(存儲(chǔ)處理數(shù)百K的對(duì)象更為適合），其他還有 BDB Java Edition、MySQL 以及 一致性內(nèi)存 Cache 等等。

三個(gè)關(guān)鍵參數(shù) (N,R,W)

第一個(gè)關(guān)鍵參數(shù)是 N，這個(gè) N 指的是數(shù)據(jù)對(duì)象將被復(fù)制到 N 臺(tái)主機(jī)上，N 在 Dynamo 實(shí)例級(jí)別配置，協(xié)調(diào)器將負(fù)責(zé)把數(shù)據(jù)復(fù)制到 N-1 個(gè)節(jié)點(diǎn)上。N 的典型值設(shè)置為 3.

復(fù)制中的一致性，采用類似于 Quorum 系統(tǒng)的一致性協(xié)議實(shí)現(xiàn)。這個(gè)協(xié)議有兩個(gè)關(guān)鍵值：R 與 W。R 代表一次成功的讀取操作中最小參與節(jié)點(diǎn)數(shù)量，W 代表一次成功的寫操作中最小參與節(jié)點(diǎn)數(shù)量。R + W>N ，則會(huì)產(chǎn)生類似 quorum 的效果。該模型中的讀(寫)延遲由最慢的 R(W)復(fù)制決定，為得到比較小的延遲，R 和 W 有的時(shí)候的和又設(shè)置比 N 小。

(N,R,W) 的值典型設(shè)置為 (3, 2 ,2),兼顧性能與可用性。R 和 W 直接影響性能、擴(kuò)展性、一致性，如果 W 設(shè)置 為 1，則一個(gè)實(shí)例中只要有一個(gè)節(jié)點(diǎn)可用，也不會(huì)影響寫操作，如果 R 設(shè)置為 1 ，只要有一個(gè)節(jié)點(diǎn)可用，也不會(huì)影響讀請(qǐng)求，R 和 W 值過小則影響一致性，過大也不好，這兩個(gè)值要平衡。對(duì)于這套系統(tǒng)的典型的 SLA 要求 99.9% 的讀寫操作在 300ms 內(nèi)完成。

–待續(xù)– 更多閱讀：Dynamo學(xué)習(xí) — http://donghao.org/2008/10/dynamoni.html

http://www.allthingsdistributed.com/2007/10/amazons_dynamo.html 論文：網(wǎng)頁版

4.System Architecture

The architecture of a storage system that needs to operate in a production setting is complex. In addition to the actual data persistence component, the system needs to have scalable and robust solutions for load balancing, membership and failure detection, failure recovery, replica synchronization, overload handling, state transfer, concurrency and job scheduling, request marshalling, request routing, system monitoring and alarming, and configuration management. Describing the details of each of the solutions is not possible, so this paper focuses on the core distributed systems techniques used in Dynamo: partitioning, replication, versioning, membership, failure handling and scaling. Table 1 presents a summary of the list of techniques Dynamo uses and their respective advantages.

Table 1: Summary of techniques used in Dynamo and their advantages.