羅 軍，王 宏，李文生

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

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

羅 軍，王 宏，李文生

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

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

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

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

1.1 CAP理論

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

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

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

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

CAP理論指出，一個(gè)分布式系統(tǒng)不可能同時(shí)滿足一致性、可用性和分區(qū)容錯(cuò)性這三個(gè)特性，最多只能滿足兩個(gè)[3-4]。對(duì)于分布式數(shù)據(jù)庫(kù)系統(tǒng)，由于分區(qū)容錯(cuò)性是基本要求，因此設(shè)計(jì)NoSQL系統(tǒng)，就需要在一致性和可用性之間找一個(gè)平衡點(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ù)庫(kù)通常選擇放棄強(qiáng)一致性，用最終一致性的思想設(shè)計(jì)分布式系統(tǒng)[5]，從而使得系統(tǒng)可以達(dá)到很高的可用性和擴(kuò)展性。

1.2 最終一致性

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

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

2 問(wèn)題描述

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

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

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

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

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

t4：假設(shè)m2還未到A、C的時(shí)候，即t4時(shí)刻，系統(tǒng)收到寫請(qǐng)求Q3并指定C執(zhí)行此請(qǐng)求，C執(zhí)行后的數(shù)據(jù)為D3，接著發(fā)送m3到A、B。此時(shí)，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)過(guò)分析，發(fā)現(xiàn)整個(gè)過(guò)程存在三個(gè)主要問(wèn)題：（1）數(shù)據(jù)同步過(guò)程中發(fā)生了舊數(shù)據(jù)覆蓋新數(shù)據(jù)的情況，同步信息到達(dá)的先后順序影響了數(shù)據(jù)的正確性。t5時(shí)刻，m2到達(dá)C結(jié)點(diǎn)，因?yàn)闊o(wú)法分辨新舊，D2錯(cuò)誤覆蓋了D3。（2）各結(jié)點(diǎn)數(shù)據(jù)沒(méi)有實(shí)現(xiàn)最終一致性。t6時(shí)刻，A、B、C的數(shù)據(jù)分別為D3、D3、D2。（3）不一致窗口內(nèi)的讀請(qǐng)求無(wú)法處理。t4時(shí)刻，結(jié)點(diǎn)的數(shù)據(jù)分別是D1、D2、D3，此時(shí)的讀操作將無(wú)法返回?cái)?shù)據(jù)并且一直處于等待狀態(tài)，直到各結(jié)點(diǎn)數(shù)據(jù)一致。

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

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

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

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

3.1 形式化定義

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

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

定義3對(duì)于版本向量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 沖突檢測(cè)和處理方案

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

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

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

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

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

②比較Tj與Ti，如果Tj的時(shí)間晚于Ti的時(shí)間，表明 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ù)，反之，對(duì)不一致的數(shù)據(jù)采取兩兩比較的方法，返回最新的數(shù)據(jù)，比較的規(guī)則如下：

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

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

3.3 沖突檢測(cè)和處理過(guò)程描述

為了對(duì)比分析，同樣采用上面的例子。基于向量時(shí)鐘模型的解決方案為數(shù)據(jù)標(biāo)識(shí)了版本信息，最終一致性的全過(guò)程如圖2所示（清晰起見(jiàn)，圖內(nèi)省略了數(shù)據(jù)的時(shí)間戳）。

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

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

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一次。同時(shí)，記錄時(shí)間戳t1并向其他結(jié)點(diǎn)發(fā)送更新信息m1。

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

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

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

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

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

3.4 方案討論

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

4 對(duì)比分析

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

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

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

5 結(jié)束語(yǔ)

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

[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í)時(shí)內(nèi)存數(shù)據(jù)庫(kù)的全局一致性模糊備份策略[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)，候麗敏.抽象事件的時(shí)間戳[J].電子學(xué)報(bào)，1999，27（11）：44-46.

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

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

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ù)庫(kù)及其辦公系統(tǒng)自動(dòng)化、語(yǔ)義網(wǎng)與知識(shí)管理系統(tǒng)；王宏（1987—），男，碩士生。E-mail：wanghong9909@qq.com

2012-02-24

2012-07-12

1002-8331（2013）23-0100-03