Two-phase commit(http://en.wikipedia.org/wiki/Two-phase_commit_protocol)是分布式事務最基礎的協議，Three-phase commit(http://en.wikipedia.org/wiki/Three-phase_commit_protocol)主要解決Two-phase commit中協調者宕機問題。
Two-phase commit的算法實現 (from <<Distributed System: Principles and Paradigms>>)：
協調者(Coordinator)：
write START_2PC to local log;
multicast VOTE_REQUEST to all participants;
while not all votes have been collected {
wait for any incoming vote;
if timeout {
write GLOBAL_ABORT to local log;
multicast GLOBAL_ABORT to all participants;
exit;
}
record vote;
}
if all participants sent VOTE_COMMIT and coordinator votes COMMIT {
write GLOBAL_COMMIT to local log;
multicast GLOBAL_COMMIT to all participants;
} else {
write GLOBAL_ABORT to local log;
multicast GLOBAL_ABORT to all participants;
}
參與者(Participants)
write INIT to local log;
wait for VOTE_REQUEST from coordinator;
if timeout {
write VOTE_ABORT to local log;
exit;
}
if participant votes COMMIT {
write VOTE_COMMIT to local log;
send VOTE_COMMIT to coordinator;
wait for DECISION from coordinator;
if timeout {
multicast DECISION_REQUEST to other participants;
wait until DECISION is received; /* remain blocked*/
write DECISION to local log;
}
if DECISION == GLOBAL_COMMIT
write GLOBAL_COMMIT to local log;
else if DECISION == GLOBAL_ABORT
write GLOBAL_ABORT to local log;
} else {
write VOTE_ABORT to local log;
send VOTE_ABORT to coordinator;
}
另外，每個參與者維護一個線程專門處理其它參與者的DECISION_REQUEST請求，處理線程流程如下：
while true {
wait until any incoming DECISION_REQUEST is received;
read most recently recorded STATE from the local log;
if STATE == GLOBAL_COMMIT
send GLOBAL_COMMIT to requesting participant;
else if STATE == INIT or STATE == GLOBAL_ABORT;
send GLOBAL_ABORT to requesting participant;
else
skip; /* participant remains blocked */
}
從上述的協調者與參與者的流程可以看出，如果所有參與者VOTE_COMMIT后協調者宕機，這個時候每個參與者都無法單獨決定全局事務的最終結果(GLOBAL_COMMIT還是GLOBAL_ABORT)，也無法從其它參與者獲取，整個事務一直阻塞到協調者恢復；如果協調者出現類似磁盤壞這種永久性錯誤，該事務將成為被永久遺棄的孤兒。問題的解決有如下思路：
1. 協調者持久化數據定期備份。為了防止協調者出現永久性錯誤，這是一種代價最小的解決方法，不容易引入bug，但是事務被阻塞的時間可能特別長，比較適合銀行這種正確性高于一切的系統。
2. Three-phase Commit。這是理論上的一種方法，實現起來復雜且效率低。思路如下：假設參與者機器不可能出現超過一半同時宕機的情況，如果協調者宕機，我們需要從活著的超過一半的參與者中得出事務的全局結果。由于不可能知道已經宕機的參與者的狀態，所以引入一個新的參與者狀態PRECOMMIT，參與者成功執行一個事務需要經過INIT, READY, PRECOMMIT，最后到COMMIT狀態；如果至少有一個參與者處于PRECOMMIT或者COMMIT，事務成功；如果至少一個參與者處于INIT或者ABORT，事務失敗；如果所有的參與者都處于READY(至少一半參與者活著)，事務失敗，即使原先宕機的參與者恢復后處于PRECOMMIT狀態，也會因為有其它參與者處于ABORT狀態而回滾。PRECOMMIT狀態的引入給了宕機的參與者回滾機會，所以Three-phase commit在超過一半的參與者活著的時候是不阻塞的。不過，Three-phase Commit只能算是是理論上的探索，效率低并且沒有解決網絡分區問題。
3. Paxos解決協調者單點問題。Jim Gray和Lamport合作了一篇論文講這個方法，很適合互聯網公司的超大規模集群，Google的Megastore事務就是這樣實現的，不過問題在于Paxos和Two-phase Commit都不簡單，需要有比較靠譜（代碼質量高）的小團隊設計和編碼才行。后續的blog將詳細闡述該方法。
總之，分布式事務只能是系統開發者的烏托邦式理想，Two-phase commit的介入將導致涉及多臺機器的事務之間完全串行，沒有代價的分布式事務是不存在的。
前面我的一篇文章http://hi.baidu.com/knuthocean/blog/item/12bb9f3dea0e400abba1673c.html引用了對Google App Engine工程師關于Bigtable/Megastore replication的文章。當時留下了很多疑問，比如：為什么Google Bigtable 是按照column family級別而不是按行執行replication的？今天重新思考了Bigtable replication問題，有如下體會：
1. Bigtable/GFS的設計屬于分層設計，和文件系統/數據庫分層設計原理一致，通過系統隔離解決工程上的問題。這種分層設計帶來了兩個問題，一個是性能問題，另外一個就是Replication問題。由于存儲節點和服務節點可能不在一臺機器，理論上總是存在性能問題，這就要求我們在加載/遷移Bigtable子表(Bigtable tablet)的時候考慮本地化因素；另外，GFS有自己的replication機制保證存儲的可靠性，Bigtable通過分離服務節點和存儲節點獲得了很大的靈活性，且Bigtable的宕機恢復時間可以做到很短。對于很多對實時性要求不是特別高的應用Bigtable由于服務節點同時只有一個，既節約資源又避免了單點問題。然后，Bigtable tablet服務過于靈活導致replication做起來極其困難。比如，tablet的分裂和合并機制導致多個tablet(一個只寫，其它只讀)服務同一段范圍的數據變得幾乎不可能。
2. Google replication分為兩種機制，基于客戶端和基于Tablet Server。分述如下：
2-1). 基于客戶端的replication。這種機制比較簡單，實現如下：客戶端讀/寫操作均為異步操作，每個寫操作都嘗試寫兩個Bigtable集群，任何一個寫成功就返回用戶，客戶端維護一個retry list，不斷重試失敗的寫操作。讀操作發到兩個集群，任何一個集群讀取成功均可。然后，這樣做有兩個問題：
a. 客戶端不可靠，可能因為各種問題，包括程序問題退出，retry list丟失導致兩個集群的數據不一致；
b. 多個客戶端并發操作時無法保證順序性。集群A收到的寫操作可能是"DEL item; PUT item"；集群B的可能是"PUT item; DEL item"。
2-2). 基于Tablet Server的replication。這種機制實現較為復雜，目的是為了保證讀服務，寫操作的延時仍然可能比較長。兩個集群，一個為主集群，提供讀/寫服務；一個為slave集群，提供只讀服務，兩個集群維持最終一致性。對于一般的讀操作，盡量讀取主集群，如果主集群不可以訪問則讀取slave集群；對于寫操作，首先將寫操作提交到主集群的Tablet Server，主集群的Tablet Server維護slave集群的元數據信息，并維護一個后臺線程不斷地將積攢的用戶表格寫操作提交到slave集群進行日志回放(group commit)。對于一般的tablet遷移，操作邏輯和Bigtable論文中的完全一致；主集群如果發生了機器宕機，則除了回放commit log外，還需要完成宕機的Tablet Server遺留的后臺備份任務。之所以要按照column family級別而不是按行復制，是為了提高壓縮率從而提高備份效率。如果主集群寫操作日志的壓縮率大于備份數據的壓縮率，則可能出現備份不及時，待備份數據越來越多的問題。
假設集群A為主集群，集群B是集群A的備份，集群切換時先停止集群A的寫服務，將集群A余下的備份任務備份到集群B后切換到集群B；如果集群A不可訪問的時間不可預知，可以選擇直接切換到集群B，這樣會帶來一致性問題。且由于Bigtable是按列復制的，最后寫入的一些行的事務性無法保證。不過由于寫操作數據還是保存在集群A的，所以用戶可以知道丟了哪些數據，很多應用可以通過重新執行A集群遺留的寫操作進行災難恢復。Google的App Engine也提供了這種查詢及重做丟失的寫操作的工具。
想法不成熟，有問題聯系：knuthocean@163.com
負載平衡策略
Dynamo的負載平衡取決于如何給每臺機器分配虛擬節點號。由于集群環境的異構性，每臺物理機器包含多個虛擬節點。一般有如下兩種分配節點號的方法：
1. 隨機分配。每臺物理節點加入時根據其配置情況隨機分配S個Token(節點號)。這種方法的負載平衡效果還是不錯的，因為自然界的數據大致是比較隨機的，雖然可能出現某段范圍的數據特別多的情況（如baidu, sina等域名下的網頁特別多），但是只要切分足夠細，即S足夠大，負載還是比較均衡的。這個方法的問題是可控性較差，新節點加入/離開系統時，集群中的原有節點都需要掃描所有的數據從而找出屬于新節點的數據，Merkle Tree也需要全部更新；另外，增量歸檔/備份變得幾乎不可能。
2. 數據范圍等分+隨機分配。為了解決方法1的問題，首先將數據的Hash空間等分為Q = N * S份 (N=機器個數，S=每臺機器的虛擬節點數），然后每臺機器隨機選擇S個分割點作為Token。和方法1一樣，這種方法的負載也比較均衡，且每臺機器都可以對屬于每個范圍的數據維護一個邏輯上的Merkle Tree，新節點加入/離開時只需掃描部分數據進行同步，并更新這部分數據對應的邏輯Merkle Tree，增量歸檔也變得簡單。該方法的一個問題是對機器規模需要做出比較合適的預估，隨著業務量的增長，可能需要重新對數據進行劃分。
不管采用哪種方法，Dynamo的負載平衡效果還是值得擔心的。
客戶端緩存及前后臺任務資源分配
客戶端緩存機器信息可以減少一次在DHT中定位目標機器的網絡交互。由于客戶端數量不可控，這里緩存采用客戶端pull的方式更新，Dynamo中每隔10s或者讀/寫操作發現緩存信息不一致時客戶端更新一次緩存信息。
Dynamo中同步操作、寫操作重試等后臺任務較多，為了不影響正常的讀寫服務，需要對后臺任務能夠使用的資源做出限制。Dynamo中維護一個資源授權系統。該系統將整個機器的資源切分成多個片，監控60s內的磁盤讀寫響應時間，事務超時時間及鎖沖突情況，根據監控信息算出機器負載從而動態調整分配給后臺任務的資源片個數。
Dynamo的優點
1. 設計簡單，組合利用P2P的各種成熟技術，模塊劃分好，代碼復用程度高。
2. 分布式邏輯與單機存儲引擎邏輯基本隔離。很多公司有自己的單機存儲引擎，可以借鑒Dynamo的思想加入分布式功能。
3. NWR策略可以根據應用自由調整，這個思想已經被Google借鑒到其下一代存儲基礎設施中。
4. 設計上天然沒有單點，且基本沒有對系統時鐘一致性的依賴。而在Google的單Master設計中，Master是單點，需要引入復雜的分布式鎖機制來解決，且Lease機制需要對機器間時鐘同步做出假設。
Dynamo的缺陷
1. 負載平衡相比單Master設計較不可控；負載平衡策略一般需要預估機器規模，不能無縫地適應業務動態增長。
2. 系統的擴展性較差。由于增加機器需要給機器分配DHT算法所需的編號，操作復雜度較高，且每臺機器存儲了整個集群的機器信息及數據文件的Merkle Tree信息，機器最大規模只能到幾千臺。
3. 數據一致性問題。多個客戶端的寫操作有順序問題，而在GFS中可以通過只允許Append操作得到一個比較好的一致性模型。
4. 數據存儲不是有序，無法執行Mapreduce；Mapreduce是目前允許機器故障，具有強擴展性的最好的并行計算模型，且有開源的Hadoop可以直接使用，Dynamo由于數據存儲依賴Hash無法直接執行Mapreduce任務。