隨筆檔案

Two-phase commit(http://en.wikipedia.org/wiki/Two-phase_commit_protocol)是分布式事務(wù)最基礎(chǔ)的協(xié)議，Three-phase commit(http://en.wikipedia.org/wiki/Three-phase_commit_protocol)主要解決Two-phase commit中協(xié)調(diào)者宕機問題。

Two-phase commit的算法實現(xiàn) (from <<Distributed System: Principles and Paradigms>>)：

協(xié)調(diào)者(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 */

    }

從上述的協(xié)調(diào)者與參與者的流程可以看出，如果所有參與者VOTE_COMMIT后協(xié)調(diào)者宕機，這個時候每個參與者都無法單獨決定全局事務(wù)的最終結(jié)果(GLOBAL_COMMIT還是GLOBAL_ABORT)，也無法從其它參與者獲取，整個事務(wù)一直阻塞到協(xié)調(diào)者恢復(fù)；如果協(xié)調(diào)者出現(xiàn)類似磁盤壞這種永久性錯誤，該事務(wù)將成為被永久遺棄的孤兒。問題的解決有如下思路：

1. 協(xié)調(diào)者持久化數(shù)據(jù)定期備份。為了防止協(xié)調(diào)者出現(xiàn)永久性錯誤，這是一種代價最小的解決方法，不容易引入bug，但是事務(wù)被阻塞的時間可能特別長，比較適合銀行這種正確性高于一切的系統(tǒng)。

2. Three-phase Commit。這是理論上的一種方法，實現(xiàn)起來復(fù)雜且效率低。思路如下：假設(shè)參與者機器不可能出現(xiàn)超過一半同時宕機的情況，如果協(xié)調(diào)者宕機，我們需要從活著的超過一半的參與者中得出事務(wù)的全局結(jié)果。由于不可能知道已經(jīng)宕機的參與者的狀態(tài)，所以引入一個新的參與者狀態(tài)PRECOMMIT，參與者成功執(zhí)行一個事務(wù)需要經(jīng)過INIT, READY, PRECOMMIT，最后到COMMIT狀態(tài)；如果至少有一個參與者處于PRECOMMIT或者COMMIT，事務(wù)成功；如果至少一個參與者處于INIT或者ABORT，事務(wù)失??；如果所有的參與者都處于READY(至少一半?yún)⑴c者活著)，事務(wù)失敗，即使原先宕機的參與者恢復(fù)后處于PRECOMMIT狀態(tài)，也會因為有其它參與者處于ABORT狀態(tài)而回滾。PRECOMMIT狀態(tài)的引入給了宕機的參與者回滾機會，所以Three-phase commit在超過一半的參與者活著的時候是不阻塞的。不過，Three-phase Commit只能算是是理論上的探索，效率低并且沒有解決網(wǎng)絡(luò)分區(qū)問題。

3. Paxos解決協(xié)調(diào)者單點問題。Jim Gray和Lamport合作了一篇論文講這個方法，很適合互聯(lián)網(wǎng)公司的超大規(guī)模集群，Google的Megastore事務(wù)就是這樣實現(xiàn)的，不過問題在于Paxos和Two-phase Commit都不簡單，需要有比較靠譜（代碼質(zhì)量高）的小團隊設(shè)計和編碼才行。后續(xù)的blog將詳細闡述該方法。

總之，分布式事務(wù)只能是系統(tǒng)開發(fā)者的烏托邦式理想，Two-phase commit的介入將導(dǎo)致涉及多臺機器的事務(wù)之間完全串行，沒有代價的分布式事務(wù)是不存在的。

前面我的一篇文章http://hi.baidu.com/knuthocean/blog/item/12bb9f3dea0e400abba1673c.html引用了對Google App Engine工程師關(guān)于Bigtable/Megastore replication的文章。當(dāng)時留下了很多疑問，比如：為什么Google Bigtable 是按照column family級別而不是按行執(zhí)行replication的？今天重新思考了Bigtable replication問題，有如下體會：

1. Bigtable/GFS的設(shè)計屬于分層設(shè)計，和文件系統(tǒng)/數(shù)據(jù)庫分層設(shè)計原理一致，通過系統(tǒng)隔離解決工程上的問題。這種分層設(shè)計帶來了兩個問題，一個是性能問題，另外一個就是Replication問題。由于存儲節(jié)點和服務(wù)節(jié)點可能不在一臺機器，理論上總是存在性能問題，這就要求我們在加載/遷移Bigtable子表(Bigtable tablet)的時候考慮本地化因素；另外，GFS有自己的replication機制保證存儲的可靠性，Bigtable通過分離服務(wù)節(jié)點和存儲節(jié)點獲得了很大的靈活性，且Bigtable的宕機恢復(fù)時間可以做到很短。對于很多對實時性要求不是特別高的應(yīng)用Bigtable由于服務(wù)節(jié)點同時只有一個，既節(jié)約資源又避免了單點問題。然后，Bigtable tablet服務(wù)過于靈活導(dǎo)致replication做起來極其困難。比如，tablet的分裂和合并機制導(dǎo)致多個tablet(一個只寫，其它只讀)服務(wù)同一段范圍的數(shù)據(jù)變得幾乎不可能。

2. Google replication分為兩種機制，基于客戶端和基于Tablet Server。分述如下：

2-1). 基于客戶端的replication。這種機制比較簡單，實現(xiàn)如下：客戶端讀/寫操作均為異步操作，每個寫操作都嘗試寫兩個Bigtable集群，任何一個寫成功就返回用戶，客戶端維護一個retry list，不斷重試失敗的寫操作。讀操作發(fā)到兩個集群，任何一個集群讀取成功均可。然后，這樣做有兩個問題：

    a. 客戶端不可靠，可能因為各種問題，包括程序問題退出，retry list丟失導(dǎo)致兩個集群的數(shù)據(jù)不一致；

    b. 多個客戶端并發(fā)操作時無法保證順序性。集群A收到的寫操作可能是"DEL item; PUT item"；集群B的可能是"PUT item; DEL item"。

2-2). 基于Tablet Server的replication。這種機制實現(xiàn)較為復(fù)雜，目的是為了保證讀服務(wù)，寫操作的延時仍然可能比較長。兩個集群，一個為主集群，提供讀/寫服務(wù)；一個為slave集群，提供只讀服務(wù)，兩個集群維持最終一致性。對于一般的讀操作，盡量讀取主集群，如果主集群不可以訪問則讀取slave集群；對于寫操作，首先將寫操作提交到主集群的Tablet Server，主集群的Tablet Server維護slave集群的元數(shù)據(jù)信息，并維護一個后臺線程不斷地將積攢的用戶表格寫操作提交到slave集群進行日志回放(group commit)。對于一般的tablet遷移，操作邏輯和Bigtable論文中的完全一致；主集群如果發(fā)生了機器宕機，則除了回放commit log外，還需要完成宕機的Tablet Server遺留的后臺備份任務(wù)。之所以要按照column family級別而不是按行復(fù)制，是為了提高壓縮率從而提高備份效率。如果主集群寫操作日志的壓縮率大于備份數(shù)據(jù)的壓縮率，則可能出現(xiàn)備份不及時，待備份數(shù)據(jù)越來越多的問題。

假設(shè)集群A為主集群，集群B是集群A的備份，集群切換時先停止集群A的寫服務(wù)，將集群A余下的備份任務(wù)備份到集群B后切換到集群B；如果集群A不可訪問的時間不可預(yù)知，可以選擇直接切換到集群B，這樣會帶來一致性問題。且由于Bigtable是按列復(fù)制的，最后寫入的一些行的事務(wù)性無法保證。不過由于寫操作數(shù)據(jù)還是保存在集群A的，所以用戶可以知道丟了哪些數(shù)據(jù)，很多應(yīng)用可以通過重新執(zhí)行A集群遺留的寫操作進行災(zāi)難恢復(fù)。Google的App Engine也提供了這種查詢及重做丟失的寫操作的工具。

想法不成熟，有問題聯(lián)系：knuthocean@163.com

負載平衡策略

Dynamo的負載平衡取決于如何給每臺機器分配虛擬節(jié)點號。由于集群環(huán)境的異構(gòu)性，每臺物理機器包含多個虛擬節(jié)點。一般有如下兩種分配節(jié)點號的方法：

1. 隨機分配。每臺物理節(jié)點加入時根據(jù)其配置情況隨機分配S個Token(節(jié)點號)。這種方法的負載平衡效果還是不錯的，因為自然界的數(shù)據(jù)大致是比較隨機的，雖然可能出現(xiàn)某段范圍的數(shù)據(jù)特別多的情況（如baidu, sina等域名下的網(wǎng)頁特別多），但是只要切分足夠細，即S足夠大，負載還是比較均衡的。這個方法的問題是可控性較差，新節(jié)點加入/離開系統(tǒng)時，集群中的原有節(jié)點都需要掃描所有的數(shù)據(jù)從而找出屬于新節(jié)點的數(shù)據(jù)，Merkle Tree也需要全部更新；另外，增量歸檔/備份變得幾乎不可能。

2. 數(shù)據(jù)范圍等分+隨機分配。為了解決方法1的問題，首先將數(shù)據(jù)的Hash空間等分為Q = N * S份 (N=機器個數(shù)，S=每臺機器的虛擬節(jié)點數(shù)），然后每臺機器隨機選擇S個分割點作為Token。和方法1一樣，這種方法的負載也比較均衡，且每臺機器都可以對屬于每個范圍的數(shù)據(jù)維護一個邏輯上的Merkle Tree，新節(jié)點加入/離開時只需掃描部分數(shù)據(jù)進行同步，并更新這部分數(shù)據(jù)對應(yīng)的邏輯Merkle Tree，增量歸檔也變得簡單。該方法的一個問題是對機器規(guī)模需要做出比較合適的預(yù)估，隨著業(yè)務(wù)量的增長，可能需要重新對數(shù)據(jù)進行劃分。

不管采用哪種方法，Dynamo的負載平衡效果還是值得擔(dān)心的。

客戶端緩存及前后臺任務(wù)資源分配

客戶端緩存機器信息可以減少一次在DHT中定位目標(biāo)機器的網(wǎng)絡(luò)交互。由于客戶端數(shù)量不可控，這里緩存采用客戶端pull的方式更新，Dynamo中每隔10s或者讀/寫操作發(fā)現(xiàn)緩存信息不一致時客戶端更新一次緩存信息。

Dynamo中同步操作、寫操作重試等后臺任務(wù)較多，為了不影響正常的讀寫服務(wù)，需要對后臺任務(wù)能夠使用的資源做出限制。Dynamo中維護一個資源授權(quán)系統(tǒng)。該系統(tǒng)將整個機器的資源切分成多個片，監(jiān)控60s內(nèi)的磁盤讀寫響應(yīng)時間，事務(wù)超時時間及鎖沖突情況，根據(jù)監(jiān)控信息算出機器負載從而動態(tài)調(diào)整分配給后臺任務(wù)的資源片個數(shù)。

Dynamo的優(yōu)點

1. 設(shè)計簡單，組合利用P2P的各種成熟技術(shù)，模塊劃分好，代碼復(fù)用程度高。

2. 分布式邏輯與單機存儲引擎邏輯基本隔離。很多公司有自己的單機存儲引擎，可以借鑒Dynamo的思想加入分布式功能。

3. NWR策略可以根據(jù)應(yīng)用自由調(diào)整，這個思想已經(jīng)被Google借鑒到其下一代存儲基礎(chǔ)設(shè)施中。

4. 設(shè)計上天然沒有單點，且基本沒有對系統(tǒng)時鐘一致性的依賴。而在Google的單Master設(shè)計中，Master是單點，需要引入復(fù)雜的分布式鎖機制來解決，且Lease機制需要對機器間時鐘同步做出假設(shè)。

Dynamo的缺陷

1. 負載平衡相比單Master設(shè)計較不可控；負載平衡策略一般需要預(yù)估機器規(guī)模，不能無縫地適應(yīng)業(yè)務(wù)動態(tài)增長。

2. 系統(tǒng)的擴展性較差。由于增加機器需要給機器分配DHT算法所需的編號，操作復(fù)雜度較高，且每臺機器存儲了整個集群的機器信息及數(shù)據(jù)文件的Merkle Tree信息，機器最大規(guī)模只能到幾千臺。

3. 數(shù)據(jù)一致性問題。多個客戶端的寫操作有順序問題，而在GFS中可以通過只允許Append操作得到一個比較好的一致性模型。

4. 數(shù)據(jù)存儲不是有序，無法執(zhí)行Mapreduce；Mapreduce是目前允許機器故障，具有強擴展性的最好的并行計算模型，且有開源的Hadoop可以直接使用，Dynamo由于數(shù)據(jù)存儲依賴Hash無法直接執(zhí)行Mapreduce任務(wù)。