基于向量時鐘模型的NoSQL最終一致性的研究

羅 軍，王 宏，李文生

重慶大學 計算機學院，重慶 400044

基于向量時鐘模型的NoSQL最終一致性的研究

羅 軍，王 宏，李文生

重慶大學 計算機學院，重慶 400044

隨著Web 2.0時代的到來和云計算的興起，傳統關系數據庫在應付web2.0網站，特別是超大規模和高并發SNS類型的網站時越發顯得力不從心，暴露了很多難以克服的問題，NoSQL則由于本身的特點得到了迅速發展。NoSQL（Not Only SQL）是對不同于傳統關系數據庫的數據庫管理系統的統稱，它以模式自由的方式存儲數據，提供了新型的訪問接口，并在擴展性、可用性、靈活性等方面有了很大提高[1]。

作為衡量NoSQL數據庫性能的重要指標，最終一致性對NoSQL的應用與發展起著重要作用。因此，如何提高NoSQL數據庫最終一致性的性能，值得做深入的研究。

1 NoSQL數據庫最終一致性的基本原理

1.1 CAP理論

CAP理論是NoSQL的重要理論基礎之一，該理論首先把分布式系統的三個特性做了如下歸納[2-4]：

（1）一致性（Consistency）：分布式系統中的所有數據備份，同一時刻是否具有同樣的值。

（2）可用性（Availability）：系統隨時都可以進行讀寫操作，即每一個操作總是能夠在確定的時間內返回。

（3）分區容錯性（Partition Tolerance）：當集群中的部分結點發生故障，集群是否還能作為一個邏輯整體提供服務。

CAP理論指出，一個分布式系統不可能同時滿足一致性、可用性和分區容錯性這三個特性，最多只能滿足兩個[3-4]。對于分布式數據庫系統，由于分區容錯性是基本要求，因此設計NoSQL系統，就需要在一致性和可用性之間找一個平衡點。如果側重點在一致性，就必須處理因為系統不可用而導致的寫操作失敗的情況；若側重點在可用性，就要考慮讀操作不能讀到寫操作寫入的最新值。因此，系統的關注點不同，相應采用的策略也不一樣。

NoSQL數據庫通常選擇放棄強一致性，用最終一致性的思想設計分布式系統[5]，從而使得系統可以達到很高的可用性和擴展性。

1.2 最終一致性

最終一致性是指，在分布式數據庫中各結點的數據，不要求每一時刻都嚴格保持一致，只保證最終一致即可[6]。具體表現為，當分布式數據庫接到一個寫請求時，只選擇結點中的一個或幾個（通常在系統設計時確定）執行此操作，然后由這些結點向其他結點發送更新信息（每個結點有一個協調器，負責在數據變化時向其余結點發送同步信息），進而實現所有結點的一致，這就使系統具有了高可用性。然而，強一致性要求所有結點都執行此操作直到每個結點都成功后該寫請求才返回成功，因此任何一個結點出了問題都將導致請求失敗進而降低系統的可用性，這也印證了CAP理論的表述。

對于最終一致性，定義從更新發生時刻到所有結點都異步更新成功的時刻之間的時間段為不一致窗口[5]。不一致窗口是衡量最終一致性的重要性能指標，它直接反映了系統內數據達成一致的時間。不一致窗口的大小依賴于以下幾個因素：數據同步方案、系統負載、交互延遲、副本個數等[6]。

2 問題描述

為了理解方便，設某NoSQL數據庫由3個結點A、B、C構成，規定執行寫請求的結點數為1。對于系統內某個數據，圖1描述了隨著時間推移，三個結點的數據變化情況，其中Di為數據狀態，mi為數據的更新信息，Qi為請求（清晰起見，圖中未顯示），圖中每個時刻具體情況的描述如下。

t0：初始時刻，A、B、C的數據同為D0。

t1：系統收到寫請求Q1，由于設定執行寫請求的結點數為1，因此假定A結點被系統指定執行此請求，執行后數據為D1，同時，A的協調器向其他結點發送更新信息m1，此時A的數據與B、C的不同。

t2：B、C收到m1并將數據修改為D1，此時各結點數據一致。t1與t2的時間間隔就是不一致窗口。

t3：系統收到寫請求Q2并指定B執行此請求，B將數據D1修改為D2，同時發送m2到A、C結點。

t4：假設m2還未到A、C的時候，即t4時刻，系統收到寫請求Q3并指定C執行此請求，C執行后的數據為D3，接著發送m3到A、B。此時，A、B、C的數據分別是D1、D2、D3。

t5：m2到達A、C，將A、C的數據修改為D2，顯然，C結點最新的數據D3被D2覆蓋了。

t6：m3到達A、B，將A、B的數據修改為D3。

經過分析，發現整個過程存在三個主要問題：（1）數據同步過程中發生了舊數據覆蓋新數據的情況，同步信息到達的先后順序影響了數據的正確性。t5時刻，m2到達C結點，因為無法分辨新舊，D2錯誤覆蓋了D3。（2）各結點數據沒有實現最終一致性。t6時刻，A、B、C的數據分別為D3、D3、D2。（3）不一致窗口內的讀請求無法處理。t4時刻，結點的數據分別是D1、D2、D3，此時的讀操作將無法返回數據并且一直處于等待狀態，直到各結點數據一致。

對于同步過程中數據的錯誤覆蓋，試想在NoSQL多結點、高并發讀寫數據的情況下，同步信息的到達將更難以預料和控制，這就導致不一致窗口的持續變大以及數據的混亂[7]，嚴重影響最終一致性，并且，對于不一致窗口內的讀請求無法處理的情況，目前也沒有更好的辦法。

圖1 結點的數據流程圖

3 基于向量時鐘模型的最終一致性解決方案

向量時鐘模型的基本思想是：為數據引入版本的概念，各結點不只保存數據的值，還有數據的版本信息。版本信息包括版本向量[8]和時間戳[9]，版本向量是一個n維向量，它反映了數據在各個結點被修改的次數[10]，時間戳用以在向量間無直接關系時比較先后順序[9]。此外，模型還定義了一個“祖先-后代”關系，用來在版本向量不一致時比較其是否存在直接的先后順序。對比于已有的向量時鐘模型，該模型不僅能夠判斷兩個具有因果關系的事件的順序，又能對全局中任意兩個事件（無因果關系的）的順序進行判斷。

3.1 形式化定義

定義1（數據的版本向量）設系統結點數為N，對于一份數據，定義第i個結點持有的版本向量Vi為：

定義2對于版本向量Vi=(a1，a2，…，ak，…，an)，定義Vi[k]為第k個結點對數據的修改次數，值為ak。

定義3對于版本向量Vi和Vj，?k∈(1，2，…，n)，都有Vi[k]≤Vj[k]，則稱Vi標志的數據為Vj標志數據的“祖先”，Vj標志的數據為Vi標志數據的“后代”。

3.2 沖突檢測和處理方案

基于向量時鐘模型的解決方案的核心思想是：當數據不一致時，首先比較版本向量間是否互為“祖先-后代”關系，如果存在，則“后代”標識的數據較新，如果不存在，則通過比較時間戳的時間先后判別數據順序，最后做一些版本合并的工作。

通過對NoSQL最終一致性全過程的分析，歸納出三類主要的操作：結點的寫操作、同步信息到達后的操作、讀操作。定義每類操作的具體規則如下：

（1）結點的寫操作。對于結點i，執行寫操作時，記錄當前時間戳Tnow，更新Vi及Ti：

（2）同步信息到達后的操作。對于同步信息發送方的j結點及接收同步信息的i結點：

①判斷Vj是否是Vi的“后代”，若是，說明 j結點的數據是在i結點的基礎上修改的新版本，因此將Vj及Tj代替Vi和Ti，比較結束，反之，執行②。

②比較Tj與Ti，如果Tj的時間晚于Ti的時間，表明 j的數據比i的數據新，因此將 j的數據及Tj替換i的數據和Ti，然后執行③，反之，直接執行③。

③比較Vi[j]和Vj[j]的大小，大的直接替換Vi[j]。

（3）讀操作。首先讀取所有結點的數據，若數據一致，則返回此數據，反之，對不一致的數據采取兩兩比較的方法，返回最新的數據，比較的規則如下：

①判斷Vj和Vi是否互為“祖先-后代”關系，若是，則“后代”標識的數據較新，比較結束，反之，執行②。

②比較Tj與Ti的時間，選出較新的時間戳標識的數據，比較結束。

3.3 沖突檢測和處理過程描述

為了對比分析，同樣采用上面的例子。基于向量時鐘模型的解決方案為數據標識了版本信息，最終一致性的全過程如圖2所示（清晰起見，圖內省略了數據的時間戳）。

圖2 基于向量時鐘模型的結點數據流程圖

t0：各結點擁有數據，版本向量（0，0，0）表示數據沒有被任何結點修改過。

t1：A結點執行Q1，根據結點寫操作的規則，執行后數據為 D(1，0，0)，版本向量（1，0，0）表示數據在A結點被修改了

1一次。同時，記錄時間戳t1并向其他結點發送更新信息m1。

t2：B、C收到m1，根據同步信息到達后的操作規則，首先檢查數據是否是的“后代”，由定義3知，是的后代，因此將數據修改為，同時將時間戳t1代替t0。

t3：B結點執行寫請求Q2，將修改為，記錄時間戳t2，同時，向A、C結點發送m2。

t4：m2還沒有到A、C的t4時刻，C結點處理了Q3請求，將修改記錄時間戳t3，同時發送 m3到A、B。此刻，A、B、C的數據分別是、)、。

t5：m2到達A、C。對于A結點，由于新數據是的“后代”，因此用D2和t2替換原數據D1和t1；對于C，原本持有數據，由于與不存在“祖先-后代”關系，于是比較t2和t3，由于t3比t2新，所以D3新于D2，因此D2不會覆蓋D3，由于更新信息的發送方是B，比較V2[2]和V3[2]的大小，最終得出處理沖突后的數據為，版本向量（1，1，1）標識此數據在三個結點各被修改一次，判斷正確。

t6：m3到達A、B，由上所述，更改后A、B數據都為，此時，系統達到了最終一致性，三個結點都持有最新的數據，并且版本向量（1，1，1）客觀反應了數據在各結點的修改次數。

3.4 方案討論

向量時鐘模型的特點在于為數據加入了版本信息，當數據不一致時可以根據版本信息做出正確判斷從而避免數據沖突，提升了最終一致性的性能。同時，該方案也存在著不足，首先，版本信息的引入導致系統需要額外的存儲空間，當結點數量很多時，對系統的存儲空間提出了更高要求，另外，隨著時間推移，版本向量將逐漸增大，因此需要定時地將向量清空到初始狀態，何時以及如何清空也有待于進一步研究。

4 對比分析

由于兩種方案在t5前的時刻各結點對應的數據相同，因此列出t5和t6時刻的數據狀態對比如表1。對比分析表明，基于向量時鐘模型的方案解決了原方案的問題：（1）避免了數據錯誤覆蓋。t5時刻，C結點數據為，而原方案的數據則是 D2，顯然正確反映了數據的值及被修改的信息。（2）系統實現了最終一致性。t6時刻，各結點的數據都為。（3）不一致窗口內的讀請求返回較新數據。t4時刻，結點數據各不相同，此時有讀請求到達，將對A、B、C兩兩做比較，最終返回D3給用戶。

表1 數據狀態對比表

為了便于理解問題的所在，采用了一個簡單的實例分析了一致性的全過程，可以得出結論，在NoSQL多結點、高并發讀寫的復雜情況下，基于向量時鐘模型的最終一致性解決方案由于定義了版本信息及沖突處理方案，能夠有效解決最終一致性過程中遇到的問題。

5 結束語

研究了NoSQL數據庫的最終一致性，分析了最終一致性方案存在的問題，提出了一種基于向量時鐘的最終一致性模型，并給出沖突檢測和處理方案。對比分析表明，方案很好地解決了問題，在NoSQL的設計過程中具有較好的應用價值。

[1]Neal L.Will NoSQL databases live up to their promise?[J]. Computer，2010，43（2）：12-14.

[2]Johannes E.SQL databases v.NoSQL databases[J].Communications of the ACM，2010，53（4）：10-11.

[3]Rabi P P，Manas R P，Suresh C S.RDBMS to NoSQL：reviewing some next-generation non-relational database’s[J].International Journal of Advanced Engineering Sciences and Technologies，2011，11（1）：15-30.

[4]Xiang Peng，Hou Ruichun，Zhou Zhiming.Cache and consistency in NoSQL[J].Computer Science and Information Technology，2010，6（3）：117-120.

[5]成汝震，尚志恩，劉宏忠，等.分布式系統數據一致性處理的研究[J].計算機科學，2001，28（8）：69-71.

[6]肖迎元，劉云生，鄧華鋒.適合分布式實時內存數據庫的全局一致性模糊備份策略[J].計算機科學，2006，33（8）：151-154.

[7]Leslie L.Time，clocks，and the ordering of events in a distributed system[J].Communicationsofthe ACM，1978，21（7）：558-565.

[8]Martin H.Using vector clocks to visualize communication flow[J].IEEE Computer Society，2010，42（10）：241-247.

[9]董宏，孫永強，候麗敏.抽象事件的時間戳[J].電子學報，1999，27（11）：44-46.

[10]董宏，孫永強.抽象事件的完備邏輯時鐘[J].軟件學報，1999，10（11）：1169-1173.

LUO Jun,WANG Hong,LI Wensheng

College of Computer Science,Chongqing University,Chongqing 400044,China

Eventual consistency is an important indicator when measuring the performance of NoSQL database,it has a significant influence in the development of NoSQL.In order to solve the problems of eventual consistency,this paper proposes a model based on vector clocks.The model adds a version to data.By importing vector and timestamp,it can mark data with the version. Furthermore,a solution of solving conflicts is presented.By comparative analysis,the solution improves the performance of eventual consistency and has a good application value in the design process of NoSQL database.

NoSQL database;eventual consistency;vector clocks;timestamp

最終一致性作為衡量NoSQL數據庫性能的重要指標，對NoSQL的應用與發展起著重要作用。針對最終一致性解決方案存在的問題，提出基于向量時鐘的最終一致性模型。模型為數據加入了版本的概念，通過版本向量和時間戳的引入，為數據標識了版本信息，同時給出了沖突檢測和處理方案。對比分析表明，方案很好地解決了問題，提高了最終一致性的性能，在NoSQL數據庫的設計過程中具有較好的應用價值。

NoSQL數據庫；最終一致性；向量時鐘；時間戳

A

TP392

10.3778/j.issn.1002-8331.1202-0462

LUO Jun,WANG Hong,LI Wensheng.Research on eventual consistency of NoSQL database based on vector clocks model. Computer Engineering and Applications,2013,49（23）：100-102.

羅軍（1961—），男，副教授，主要研究領域為數據庫及其辦公系統自動化、語義網與知識管理系統；王宏（1987—），男，碩士生。E-mail：wanghong9909@qq.com

2012-02-24

2012-07-12

1002-8331（2013）23-0100-03