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

羅 軍，王 宏，李文生

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

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

羅 軍，王 宏，李文生

重慶大學(xué) 計(jì)算機(jī)學(xué)院，重慶 400044

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

作為衡量NoSQL數(shù)據(jù)庫性能的重要指標(biāo)，最終一致性對NoSQL的應(yīng)用與發(fā)展起著重要作用。因此，如何提高NoSQL數(shù)據(jù)庫最終一致性的性能，值得做深入的研究。

1 NoSQL數(shù)據(jù)庫最終一致性的基本原理

1.1 CAP理論

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

（1）一致性（Consistency）：分布式系統(tǒng)中的所有數(shù)據(jù)備份，同一時刻是否具有同樣的值。

（2）可用性（Availability）：系統(tǒng)隨時都可以進(jìn)行讀寫操作，即每一個操作總是能夠在確定的時間內(nèi)返回。

（3）分區(qū)容錯性（Partition Tolerance）：當(dāng)集群中的部分結(jié)點(diǎn)發(fā)生故障，集群是否還能作為一個邏輯整體提供服務(wù)。

CAP理論指出，一個分布式系統(tǒng)不可能同時滿足一致性、可用性和分區(qū)容錯性這三個特性，最多只能滿足兩個[3-4]。對于分布式數(shù)據(jù)庫系統(tǒng)，由于分區(qū)容錯性是基本要求，因此設(shè)計(jì)NoSQL系統(tǒng)，就需要在一致性和可用性之間找一個平衡點(diǎn)。如果側(cè)重點(diǎn)在一致性，就必須處理因?yàn)橄到y(tǒng)不可用而導(dǎo)致的寫操作失敗的情況；若側(cè)重點(diǎn)在可用性，就要考慮讀操作不能讀到寫操作寫入的最新值。因此，系統(tǒng)的關(guān)注點(diǎn)不同，相應(yīng)采用的策略也不一樣。

NoSQL數(shù)據(jù)庫通常選擇放棄強(qiáng)一致性，用最終一致性的思想設(shè)計(jì)分布式系統(tǒng)[5]，從而使得系統(tǒng)可以達(dá)到很高的可用性和擴(kuò)展性。

1.2 最終一致性

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

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

2 問題描述

為了理解方便，設(shè)某NoSQL數(shù)據(jù)庫由3個結(jié)點(diǎn)A、B、C構(gòu)成，規(guī)定執(zhí)行寫請求的結(jié)點(diǎn)數(shù)為1。對于系統(tǒng)內(nèi)某個數(shù)據(jù)，圖1描述了隨著時間推移，三個結(jié)點(diǎn)的數(shù)據(jù)變化情況，其中Di為數(shù)據(jù)狀態(tài)，mi為數(shù)據(jù)的更新信息，Qi為請求（清晰起見，圖中未顯示），圖中每個時刻具體情況的描述如下。

t0：初始時刻，A、B、C的數(shù)據(jù)同為D0。

t1：系統(tǒng)收到寫請求Q1，由于設(shè)定執(zhí)行寫請求的結(jié)點(diǎn)數(shù)為1，因此假定A結(jié)點(diǎn)被系統(tǒng)指定執(zhí)行此請求，執(zhí)行后數(shù)據(jù)為D1，同時，A的協(xié)調(diào)器向其他結(jié)點(diǎn)發(fā)送更新信息m1，此時A的數(shù)據(jù)與B、C的不同。

t2：B、C收到m1并將數(shù)據(jù)修改為D1，此時各結(jié)點(diǎn)數(shù)據(jù)一致。t1與t2的時間間隔就是不一致窗口。

t3：系統(tǒng)收到寫請求Q2并指定B執(zhí)行此請求，B將數(shù)據(jù)D1修改為D2，同時發(fā)送m2到A、C結(jié)點(diǎn)。

t4：假設(shè)m2還未到A、C的時候，即t4時刻，系統(tǒng)收到寫請求Q3并指定C執(zhí)行此請求，C執(zhí)行后的數(shù)據(jù)為D3，接著發(fā)送m3到A、B。此時，A、B、C的數(shù)據(jù)分別是D1、D2、D3。

t5：m2到達(dá)A、C，將A、C的數(shù)據(jù)修改為D2，顯然，C結(jié)點(diǎn)最新的數(shù)據(jù)D3被D2覆蓋了。

t6：m3到達(dá)A、B，將A、B的數(shù)據(jù)修改為D3。

經(jīng)過分析，發(fā)現(xiàn)整個過程存在三個主要問題：（1）數(shù)據(jù)同步過程中發(fā)生了舊數(shù)據(jù)覆蓋新數(shù)據(jù)的情況，同步信息到達(dá)的先后順序影響了數(shù)據(jù)的正確性。t5時刻，m2到達(dá)C結(jié)點(diǎn)，因?yàn)闊o法分辨新舊，D2錯誤覆蓋了D3。（2）各結(jié)點(diǎn)數(shù)據(jù)沒有實(shí)現(xiàn)最終一致性。t6時刻，A、B、C的數(shù)據(jù)分別為D3、D3、D2。（3）不一致窗口內(nèi)的讀請求無法處理。t4時刻，結(jié)點(diǎn)的數(shù)據(jù)分別是D1、D2、D3，此時的讀操作將無法返回?cái)?shù)據(jù)并且一直處于等待狀態(tài)，直到各結(jié)點(diǎn)數(shù)據(jù)一致。

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

圖1 結(jié)點(diǎn)的數(shù)據(jù)流程圖

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

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

3.1 形式化定義

定義1（數(shù)據(jù)的版本向量）設(shè)系統(tǒng)結(jié)點(diǎn)數(shù)為N，對于一份數(shù)據(jù)，定義第i個結(jié)點(diǎn)持有的版本向量Vi為：

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

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

3.2 沖突檢測和處理方案

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

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

（1）結(jié)點(diǎn)的寫操作。對于結(jié)點(diǎn)i，執(zhí)行寫操作時，記錄當(dāng)前時間戳Tnow，更新Vi及Ti：

（2）同步信息到達(dá)后的操作。對于同步信息發(fā)送方的j結(jié)點(diǎn)及接收同步信息的i結(jié)點(diǎn)：

①判斷Vj是否是Vi的“后代”，若是，說明 j結(jié)點(diǎn)的數(shù)據(jù)是在i結(jié)點(diǎn)的基礎(chǔ)上修改的新版本，因此將Vj及Tj代替Vi和Ti，比較結(jié)束，反之，執(zhí)行②。

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

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

（3）讀操作。首先讀取所有結(jié)點(diǎn)的數(shù)據(jù)，若數(shù)據(jù)一致，則返回此數(shù)據(jù)，反之，對不一致的數(shù)據(jù)采取兩兩比較的方法，返回最新的數(shù)據(jù)，比較的規(guī)則如下：

①判斷Vj和Vi是否互為“祖先-后代”關(guān)系，若是，則“后代”標(biāo)識的數(shù)據(jù)較新，比較結(jié)束，反之，執(zhí)行②。

②比較Tj與Ti的時間，選出較新的時間戳標(biāo)識的數(shù)據(jù)，比較結(jié)束。

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

為了對比分析，同樣采用上面的例子?；谙蛄繒r鐘模型的解決方案為數(shù)據(jù)標(biāo)識了版本信息，最終一致性的全過程如圖2所示（清晰起見，圖內(nèi)省略了數(shù)據(jù)的時間戳）。

圖2 基于向量時鐘模型的結(jié)點(diǎn)數(shù)據(jù)流程圖

t0：各結(jié)點(diǎn)擁有數(shù)據(jù)，版本向量（0，0，0）表示數(shù)據(jù)沒有被任何結(jié)點(diǎn)修改過。

t1：A結(jié)點(diǎn)執(zhí)行Q1，根據(jù)結(jié)點(diǎn)寫操作的規(guī)則，執(zhí)行后數(shù)據(jù)為 D(1，0，0)，版本向量（1，0，0）表示數(shù)據(jù)在A結(jié)點(diǎn)被修改了

1一次。同時，記錄時間戳t1并向其他結(jié)點(diǎn)發(fā)送更新信息m1。

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

t3：B結(jié)點(diǎn)執(zhí)行寫請求Q2，將修改為，記錄時間戳t2，同時，向A、C結(jié)點(diǎn)發(fā)送m2。

t4：m2還沒有到A、C的t4時刻，C結(jié)點(diǎn)處理了Q3請求，將修改記錄時間戳t3，同時發(fā)送 m3到A、B。此刻，A、B、C的數(shù)據(jù)分別是、)、。

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

t6：m3到達(dá)A、B，由上所述，更改后A、B數(shù)據(jù)都為，此時，系統(tǒng)達(dá)到了最終一致性，三個結(jié)點(diǎn)都持有最新的數(shù)據(jù)，并且版本向量（1，1，1）客觀反應(yīng)了數(shù)據(jù)在各結(jié)點(diǎn)的修改次數(shù)。

3.4 方案討論

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

4 對比分析

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

表1 數(shù)據(jù)狀態(tài)對比表

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

5 結(jié)束語

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

[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]成汝震，尚志恩，劉宏忠，等.分布式系統(tǒng)數(shù)據(jù)一致性處理的研究[J].計(jì)算機(jī)科學(xué)，2001，28（8）：69-71.

[6]肖迎元，劉云生，鄧華鋒.適合分布式實(shí)時內(nèi)存數(shù)據(jù)庫的全局一致性模糊備份策略[J].計(jì)算機(jī)科學(xué)，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]董宏，孫永強(qiáng)，候麗敏.抽象事件的時間戳[J].電子學(xué)報(bào)，1999，27（11）：44-46.

[10]董宏，孫永強(qiáng).抽象事件的完備邏輯時鐘[J].軟件學(xué)報(bào)，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數(shù)據(jù)庫性能的重要指標(biāo)，對NoSQL的應(yīng)用與發(fā)展起著重要作用。針對最終一致性解決方案存在的問題，提出基于向量時鐘的最終一致性模型。模型為數(shù)據(jù)加入了版本的概念，通過版本向量和時間戳的引入，為數(shù)據(jù)標(biāo)識了版本信息，同時給出了沖突檢測和處理方案。對比分析表明，方案很好地解決了問題，提高了最終一致性的性能，在NoSQL數(shù)據(jù)庫的設(shè)計(jì)過程中具有較好的應(yīng)用價值。

NoSQL數(shù)據(jù)庫；最終一致性；向量時鐘；時間戳

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—），男，副教授，主要研究領(lǐng)域?yàn)閿?shù)據(jù)庫及其辦公系統(tǒng)自動化、語義網(wǎng)與知識管理系統(tǒng)；王宏（1987—），男，碩士生。E-mail：wanghong9909@qq.com

2012-02-24

2012-07-12

1002-8331（2013）23-0100-03