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