異常處理
Dynamo中把異常分為兩種類型，臨時(shí)性的異常和永久性異常。服務(wù)器程序運(yùn)行時(shí)一般通過類似supervise的監(jiān)控daemon啟動(dòng)，出現(xiàn)core dump等異常情況時(shí)自動(dòng)重啟。這種異常是臨時(shí)性的，其它異常如硬盤報(bào)修或機(jī)器報(bào)廢等由于其持續(xù)時(shí)間太長(zhǎng)，稱之為永久性的?；仡橠ynamo的設(shè)計(jì)，一份數(shù)據(jù)被寫到N, N+1, ... N+K-1這K臺(tái)機(jī)器上，如果機(jī)器N+i (0 <= i <= K-1)宕機(jī)，原本寫入該機(jī)器的數(shù)據(jù)轉(zhuǎn)移到機(jī)器N+K，機(jī)器N+K定時(shí)ping機(jī)器N+i，如果在指定的時(shí)間T內(nèi)N+i重新提供服務(wù)，機(jī)器N+K將啟動(dòng)傳輸任務(wù)將暫存的數(shù)據(jù)發(fā)送給機(jī)器N+i；如果超過了時(shí)間T機(jī)器N+i還是處于宕機(jī)狀態(tài)，這種異常被認(rèn)為是永久性的，這時(shí)需要借助Merkle Tree機(jī)制進(jìn)行數(shù)據(jù)同步。這里的問題在于時(shí)間T的選擇，所以Dynamo的開發(fā)人員后來(lái)干脆把所有程序檢測(cè)出來(lái)的異常認(rèn)為是臨時(shí)性的，并提供給管理員一個(gè)utility工具，用來(lái)顯示指定一臺(tái)機(jī)器永久性下線。由于數(shù)據(jù)被存儲(chǔ)了K份，一臺(tái)機(jī)器下線將導(dǎo)致后續(xù)的K臺(tái)機(jī)器出現(xiàn)數(shù)據(jù)不一致的情況。這是因?yàn)樵緦儆跈C(jī)器N的數(shù)據(jù)由于機(jī)器下線可能被臨時(shí)寫入機(jī)器N+1, ... N+K。如果機(jī)器N出現(xiàn)永久性異常，后續(xù)的K臺(tái)機(jī)器都需要服務(wù)它的部分?jǐn)?shù)據(jù)，這時(shí)它們都需要選擇冗余機(jī)器中較為空閑的一臺(tái)進(jìn)行同步。Merkle Tree同步的原理很簡(jiǎn)單，每個(gè)非葉子節(jié)點(diǎn)對(duì)應(yīng)多個(gè)文件，為其所有子節(jié)點(diǎn)值組合以后的Hash值，葉子節(jié)點(diǎn)對(duì)應(yīng)單個(gè)數(shù)據(jù)文件，為文件內(nèi)容的Hash值。這樣，任何一個(gè)數(shù)據(jù)文件不匹配都將導(dǎo)致從該文件對(duì)應(yīng)的葉子節(jié)點(diǎn)到根節(jié)點(diǎn)的所有節(jié)點(diǎn)值不同。每臺(tái)機(jī)器維護(hù)K棵Merkle Tree，機(jī)器同步時(shí)首先傳輸Merkle Tree信息，并且只需要同步從根到葉子的所有節(jié)點(diǎn)值均不相同的文件。
讀/寫流程
客戶端的讀/寫請(qǐng)求首先傳輸?shù)骄彺娴囊慌_(tái)機(jī)器，根據(jù)預(yù)先配置的K、W和R值，對(duì)于寫請(qǐng)求，根據(jù)DHT算法計(jì)算出數(shù)據(jù)所屬的節(jié)點(diǎn)后直接寫入后續(xù)的K個(gè)節(jié)點(diǎn)，等到W個(gè)節(jié)點(diǎn)返回成功時(shí)返回客戶端，如果寫請(qǐng)求失敗將加入retry_list不斷重試。如果某臺(tái)機(jī)器發(fā)生了臨時(shí)性異常，將數(shù)據(jù)寫入后續(xù)的備用機(jī)器并在備用機(jī)器中記錄臨時(shí)異常的機(jī)器信息。對(duì)于讀請(qǐng)求，根據(jù)DHT算法計(jì)算出數(shù)據(jù)所屬節(jié)點(diǎn)后根據(jù)負(fù)載策略選擇R個(gè)節(jié)點(diǎn)，從中讀取R份數(shù)據(jù)，如果數(shù)據(jù)一致，直接返回客戶端；如果數(shù)據(jù)不一致，采用vector clock的方法解決沖突。Dynamo系統(tǒng)默認(rèn)的策略是選擇最新的數(shù)據(jù)，當(dāng)然用戶也可以自定義沖突處理方法。每個(gè)寫入系統(tǒng)的<key, value>對(duì)都記錄一個(gè)vector lock信息，vector lock就是一系列<機(jī)器節(jié)點(diǎn)號(hào), 版本號(hào)/時(shí)間戳>對(duì)，記錄每臺(tái)機(jī)器對(duì)該數(shù)據(jù)的最新更新版本信息。如下圖：
讀取時(shí)進(jìn)行沖突解決，如果一臺(tái)機(jī)器讀到的數(shù)據(jù)的vector lock記錄的所有版本信息都小于另一臺(tái)機(jī)器，直接返回vector lock較大的數(shù)據(jù)；如果二者是平行版本，根據(jù)時(shí)間戳選擇最新的數(shù)據(jù)或者通過用戶自定義策略解決沖突。讀請(qǐng)求除了返回?cái)?shù)據(jù)<key, value>值以外還返回vector lock信息，后續(xù)的寫操作需要帶上該信息。
問題1：垃圾數(shù)據(jù)如何回收？
Dynamo的垃圾回收機(jī)制主要依賴每個(gè)節(jié)點(diǎn)上的存儲(chǔ)引擎，如Berkely db存儲(chǔ)引擎，merge-dump存儲(chǔ)引擎等。其它操作，如Merkle Tree同步產(chǎn)生的垃圾文件回收可以和底層存儲(chǔ)引擎配合完成。
問題2：Dynamo有沒有可能丟數(shù)據(jù)？
關(guān)鍵在于K, W, R的設(shè)置。假設(shè)一個(gè)讀敏感應(yīng)用設(shè)置K=3, W=3, R=1，待處理的數(shù)據(jù)原本屬于節(jié)點(diǎn)A, B, C，節(jié)點(diǎn)B出現(xiàn)臨時(shí)性故障的過程中由節(jié)點(diǎn)D代替。在節(jié)點(diǎn)B出現(xiàn)故障到節(jié)點(diǎn)B同步完成節(jié)點(diǎn)D暫存的修改這段時(shí)間內(nèi)，如果讀請(qǐng)求落入節(jié)點(diǎn)B或者D都將出現(xiàn)丟數(shù)據(jù)的問題。這里需要適當(dāng)處理下，對(duì)于B節(jié)點(diǎn)下線的情況，由于其它機(jī)器要么緩存了B節(jié)點(diǎn)已下線信息，要么讀取時(shí)將發(fā)現(xiàn)B節(jié)點(diǎn)處于下線狀態(tài)，這是只需要將請(qǐng)求轉(zhuǎn)發(fā)其它節(jié)點(diǎn)即可；對(duì)于B節(jié)點(diǎn)上線情況，可以等到B節(jié)點(diǎn)完全同步以后才開始提供讀服務(wù)。對(duì)于設(shè)置W<K的應(yīng)用，Dynamo讀取時(shí)需要解決沖突，可能丟數(shù)據(jù)?？傊?，Dynamo中可以保證讀取的機(jī)器都是有效的（處于正常服務(wù)狀態(tài)），但W != K時(shí)不保證所有的有效機(jī)器均同步了所有更新操作。
問題3：Dynamo的寫入數(shù)據(jù)有沒有順序問題？
假設(shè)要寫入兩條數(shù)據(jù)"add item"和"delete item"，如果寫入的順序不同，將導(dǎo)致完全不同的結(jié)果。如果設(shè)置W=K，對(duì)于同一個(gè)客戶端，由于寫入所有的機(jī)器以后才返回，可以保證順序；而多個(gè)客戶端的寫操作可能被不同的節(jié)點(diǎn)處理，不能保證順序性。如果設(shè)置W < K，Dynamo不保證順序性。
問題4：沖突解決后是否需要將結(jié)果值更新存儲(chǔ)節(jié)點(diǎn)？
讀操作解決沖突后不需要將結(jié)果值更新存儲(chǔ)節(jié)點(diǎn)。產(chǎn)生沖突的情況一般有機(jī)器下線或者多個(gè)客戶端導(dǎo)致的順序問題。機(jī)器下線時(shí)retry_list中的操作將丟失，某些節(jié)點(diǎn)不能獲取所有的更新操作。對(duì)于機(jī)器暫時(shí)性或者永久性的異常，Dynamo中內(nèi)部都有同步機(jī)制進(jìn)行處理，但是對(duì)于retry_list中的操作丟失或者多個(gè)客戶端引發(fā)的順序問題，Dynamo內(nèi)部根本無(wú)法分辨數(shù)據(jù)是否正確。唯一的沖突解決機(jī)器在讀操作，Dynamo可以設(shè)計(jì)成讀操作將沖突解決結(jié)果值更新存儲(chǔ)節(jié)點(diǎn)，但是這樣會(huì)使讀操作變得復(fù)雜和不高效。所以，比較好的做法是每個(gè)寫操作都帶上讀操作返回的多個(gè)版本數(shù)據(jù)，寫操作將沖突處理的結(jié)果更新存儲(chǔ)節(jié)點(diǎn)。