一種基于HashGraph的NoSQL型分布式存儲因果一致性模型

田俊峰 王彥骉

(河北大學(xué)網(wǎng)絡(luò)空間安全與計算機學(xué)院 河北保定 071002)

(河北省高可信信息系統(tǒng)重點實驗室(河北大學(xué)) 河北保定 071002)

分布式云存儲是新一代數(shù)字時代發(fā)展的重要基石，公有云服務(wù)商的數(shù)據(jù)中心部署在不同的地方，為用戶提供可擴展的計算、存儲等服務(wù)[1].然而在提供高速、便捷服務(wù)的同時，保障分布式副本之間的數(shù)據(jù)一致性、因果一致性就成了比較嚴峻的問題.在理想的環(huán)境中下，副本中所有元數(shù)據(jù)的即時更新在其他節(jié)點中都立即可見，這種模型稱為強一致性.但在分布式存儲環(huán)境下，不犧牲一定的可用性和性能幾乎無法實現(xiàn)；即使在沒有對數(shù)據(jù)進行分區(qū)、分塊存儲，強一致性的實現(xiàn)也有著極高的性能成本.例如Guerraoui等人[2]基于增量更新提出的ICG(incremental con-sistency guarantees for replicated objects)方案，在犧牲通信開銷和查詢正確度的前提下提高了強一致性的操作延遲.

因此，許多系統(tǒng)使用最終一致性來保障用戶數(shù)據(jù)安全，例如亞馬遜的Dynamo[3]存儲平臺.該平臺對用戶數(shù)據(jù)可用性做出的唯一保障就是要求用戶更新最終實現(xiàn)一致；為了確保多個副本都收斂到相同的數(shù)據(jù)狀態(tài)，最終一致性的系統(tǒng)通常使用某種規(guī)則在多個差異的副本狀態(tài)中選擇一個作為最終穩(wěn)定狀態(tài)[4].

在Twitter、微博等社交軟件或大型網(wǎng)站應(yīng)用中，最終一致性是最常見的數(shù)據(jù)一致性約束，其次便是因果一致性，如MongoDB數(shù)據(jù)庫就是典型的因果一致性數(shù)據(jù)存儲產(chǎn)品.因果一致性是一種中間一致性模型，該模型只在系統(tǒng)要求可見的因果依賴性時，才要求保障記錄用戶事件的元數(shù)據(jù)的因果序.因果序就是前后2個用戶事件之間一種有依賴性要求的發(fā)生順序，有2個來源，一個是同一客戶端中有前后順序的更新，另一個是不同客戶端中對同一個值的2次更新[5].為了實現(xiàn)數(shù)據(jù)因果一致性約束，分布式云存儲模型需要提供驗證因果一致性依賴關(guān)系的數(shù)據(jù)存取規(guī)則.具體來說，若用戶要求某些元數(shù)據(jù)的因果依賴性不可見，那么系統(tǒng)中須保留一個對用戶透明的變量.對于由多臺機器組成的多節(jié)點數(shù)據(jù)分區(qū)來說，對因果依賴關(guān)系的校驗就成了較難的問題.

1 相關(guān)工作和主要工作

1.1 相關(guān)工作

因果一致性可以在客戶端與服務(wù)端分別實現(xiàn)，例如Zawirski等人[6]提出的客戶端一致性方案.現(xiàn)有的工作中，在服務(wù)端實現(xiàn)因果一致性的解決方案都有較大性能開銷，例如Lloyd等人[7]在2011年提出的COPS(clusters of order-preserving servers)模型，Du等人[8]在2013年提出的Orbe模型是較早的因果一致性數(shù)據(jù)存儲模型.該類模型會對用戶當(dāng)前讀取的值保持跟蹤，當(dāng)客戶端寫入某個新的鍵值時，系統(tǒng)中對客戶端正在寫入的新值因果依賴關(guān)系定義為：該客戶端讀取過的所有值.在分區(qū)同步消息中，這種明確的因果依賴關(guān)系校驗機制要求極高的消息復(fù)雜度，導(dǎo)致分區(qū)間通信開銷很大.

1) 近年來多數(shù)的成熟研究方案采用物理時鐘方法對元數(shù)據(jù)和分區(qū)狀態(tài)進行同步，如GentleRain是Du等人[9]在2014年提出的方案，依賴物理時鐘的緊密同步、分區(qū)之間定期地進行通信來保障用戶數(shù)據(jù)的因果序、正確性和系統(tǒng)性能.但該模型依賴于同步單調(diào)的物理時鐘，若底層協(xié)議如網(wǎng)絡(luò)時鐘協(xié)議(network time protocol, NTP)出現(xiàn)異常(例如時鐘偏移)，就會導(dǎo)致GentleRain對PUT(用戶向服務(wù)端寫入新的數(shù)據(jù))操作進行延遲等待.

2016年Tomsic等人[10]提出的PhysiCS-NMSI是一種使用了物理時鐘，但對時鐘的穩(wěn)定性沒有要求的數(shù)據(jù)因果一致性模型.該模型也使用一個單向的標量對數(shù)據(jù)依賴關(guān)系進行檢查，并且提供數(shù)據(jù)因果一致性快照，保障用戶寫入事件操作的原子性，從而避免PUT等待、操作沖突等問題.

2) 混合邏輯時鐘 (hybrid logical clocks, HLC)是Kulkarni等人[11]在2014年提出的一種基于物理時鐘和邏輯時鐘的時鐘同步方法，用于在分布式存儲系統(tǒng)中檢查因果依賴關(guān)系.該方法在物理時鐘基礎(chǔ)上，用1組向量來表示用戶數(shù)據(jù)條目的時間戳，優(yōu)化了傳統(tǒng)的物理時鐘方法造成的PUT等待等缺陷.Okapi是Didona等人[12]在2017年提出的一種使用了混合邏輯時鐘和全局穩(wěn)定向量(global stable vector, GSV)的因果一致性模型，類似于文獻[9]中的全局穩(wěn)定時間(global stable time, GST)，該模型設(shè)定一個狀態(tài)值來校驗和追蹤當(dāng)前分區(qū)最新條目、及其時間戳，時間戳不小于該狀態(tài)值的元數(shù)據(jù)條目才被允許寫入到分區(qū)內(nèi).該系統(tǒng)要求用戶的查詢操作須約束在所有節(jié)點都同步完用戶更新之后，因此這個約束會大量增加Okapi的更新可見性延遲，甚至超過GentleRain.

Roohitavaf等人[13]在2017年提出了Causal-Spartan模型，基于混合邏輯時鐘(HLC)和數(shù)據(jù)中心穩(wěn)定向量(data center stable vectors, DSV)保障用戶元數(shù)據(jù)的數(shù)據(jù)因果一致性，可提升在分區(qū)之間存在時鐘偏移、查詢放大的情況下的性能表現(xiàn).而且提出了分區(qū)穩(wěn)定向量的概念，若副本分區(qū)中單個查詢被放大成大量內(nèi)部查詢，不僅提升了寫入和查詢服務(wù)的可靠性，還降低了客戶端操作更新等待時間.但由于副本分區(qū)穩(wěn)定向量包含數(shù)據(jù)中心所有條目，大大增加了分區(qū)之間同步數(shù)據(jù)的通信成本.此外，在服務(wù)器收到用戶請求的更新后，子節(jié)點之間、父節(jié)點之間、以及父節(jié)點和子節(jié)點之間對數(shù)據(jù)、狀態(tài)和時鐘進行同步，以期滿足因果依賴性約束的過程也會耗費較長時間.

1.2 主要工作

為解決時鐘偏移和查詢放大造成的用戶PUT等待時間過長的問題，本文在混合邏輯時鐘和數(shù)據(jù)中心穩(wěn)定向量的基礎(chǔ)上，結(jié)合HashGraph的原理，提出了一種使用部分穩(wěn)定向量和依賴集簽名的因果一致性模型Causal-Pdh(causal consistency using partDSVand Hash of dependency series)，如圖1所示，主要貢獻有3個方面：

1) 寫入操作中，服務(wù)端在發(fā)給客戶端的PUT響應(yīng)消息中，根據(jù)本地最新依賴集計算服務(wù)端依賴集簽名(Hash of dependency series,HDS)，然后發(fā)送給客戶端，客戶端根據(jù)響應(yīng)消息更新本地依賴集后，也在本地計算客戶端HDS，然后與收到的服務(wù)端HDS進行驗證，為寫入數(shù)據(jù)的過程提供完整性約束.

Fig. 1 Entity flow diagram model of Causal-Pdh圖1 Causal-Pdh協(xié)議的實體流圖模型

2) 查詢操作中，服務(wù)端在收到客戶端查詢請求后，計算本地DSV對應(yīng)的HDS，然后將客戶端請求對應(yīng)的partDSV，serverHDS發(fā)送給客戶端，客戶端更新本地依賴集后計算HDS，并與收到的服務(wù)端HDS驗證.證明在分區(qū)存在時鐘偏移與用戶查詢放大的情況下，請求響應(yīng)時間有明顯減少.

3)借鑒HashGraph的思想，數(shù)據(jù)中心之間隨機同步本地最新穩(wěn)定向量與對應(yīng)的HDS，分區(qū)之間對數(shù)據(jù)中心最新狀態(tài)、時鐘進行同步共享，各副本、分區(qū)同時驗證收到的HDS簽名與本地最新數(shù)據(jù)、狀態(tài)對應(yīng)的HDS簽名.用戶更新后，所有數(shù)據(jù)中心間、副本間同步數(shù)據(jù)達成數(shù)據(jù)因果一致性共識所需的時間明顯降低.

2 分布式系統(tǒng)因果一致性原理

隨著數(shù)據(jù)量的爆發(fā)式增長以及應(yīng)用負載的快速增加，傳統(tǒng)數(shù)據(jù)庫所采用的單一服務(wù)器模式，越來越難以應(yīng)對當(dāng)今應(yīng)用對數(shù)據(jù)存儲的需求[4].分布式云存儲服務(wù)提供商通常利用一定的通信技術(shù),將文件分布到物理位置獨立的服務(wù)器中，最終提供相應(yīng)的接口給用戶端上傳、下載或更新[14]，從而降低響應(yīng)來自不同地理位置的用戶請求所需的時間.實際應(yīng)用中，分布式存儲模型的拓撲結(jié)構(gòu)通常設(shè)定為雙層結(jié)構(gòu)，即對數(shù)據(jù)進行分區(qū)存儲，如圖2所示：數(shù)據(jù)中心為父節(jié)點，副本節(jié)點中的分區(qū)為子節(jié)點.例如CausalSpartan模型將用戶元數(shù)據(jù)保存在M個數(shù)據(jù)中心，每個數(shù)據(jù)中心分為N個分區(qū)，該類方案中通常約束每個客戶端只從當(dāng)前所連接的分區(qū)讀寫數(shù)據(jù).

Fig. 2 Topology scheme of M data centers (N partitions)圖2 有M個數(shù)據(jù)中心(N個分區(qū))的節(jié)點分布方案

由于數(shù)據(jù)中心中存在網(wǎng)絡(luò)分區(qū)，導(dǎo)致分區(qū)間可能由于通信故障造成分區(qū)間同步延遲等問題，但Causal-Pdh模型是在數(shù)據(jù)中心內(nèi)部，即分區(qū)間無網(wǎng)絡(luò)故障的前提下提出的.因此，數(shù)據(jù)中心內(nèi)的分區(qū)可以相互保持網(wǎng)絡(luò)傳輸、時間和數(shù)據(jù)同步.對于每個鍵，均使用鍵值存儲服務(wù)存儲多個版本信息.每個鍵值條目均可進行有2個基本操作：PUT(k,v)和GET(k).其中PUT(k,v)寫入新版本信息，值為v，GET(k)則讀取一條包含鍵k的條目數(shù)據(jù).

2.1 因果關(guān)系

數(shù)據(jù)因果一致性的定義來自于事件之間happens-before關(guān)系.該關(guān)系的定義如定義1～定義3所示:

定義1.happens-before.a和b定義為2個事件，若以下條件成立：1)a和b為2個事件，且a在b之前發(fā)生；2)a是PUT(k,v)操作，b是GET(k)操作，b獲取a寫入的值；3)存在中間事件c使得a在c之前發(fā)生，并且c在b之前發(fā)生；則a與b的關(guān)系可表示為a→b，也就是ahappens-beforeb.

定義2.v1,v2分別是鍵k1,k2對應(yīng)的值，v1與v2可表示為因果關(guān)系，當(dāng)且僅當(dāng)PUT(k2,v2)→PUT(k1,v1)成立時，即表示為“v1depv2”.

定義3.可見性.如果客戶端Client的GET(k)操作返回的是v′，并且v′滿足v′=v或者(vdepv′)，那么鍵k的值v對客戶端Client是可見的.

2.2 因果一致性

定義4.因果一致性.令k1和k2是數(shù)據(jù)中心的2個任意的鍵.令v1是鍵k1的值，v2是鍵k2的值，2個鍵滿足v1depv2.若客戶端Client讀取的v1和v2對客戶端Client是非透明的，那么該數(shù)據(jù)存儲模型滿足“因果一致性”約束.

鍵值存儲數(shù)據(jù)庫中對同一個鍵執(zhí)行寫入操作時，若不同客戶端進行2次寫操作，就通常會發(fā)生沖突，導(dǎo)致數(shù)據(jù)存儲模型失去因果一致性約束.沖突的定義為:

定義5.沖突.v1和v2是鍵k的2個值，當(dāng)且僅當(dāng)(v1depv2)和(v2depv1)同時成立時，v1和v2是沖突的(即2個值不互相依賴于彼此).

2個值間存在沖突，就需要云存儲模型解決或緩解沖突，因此，沖突解決函數(shù)定義為f(v1,v2) .該函數(shù)依據(jù)當(dāng)前協(xié)議中的依賴項判別機制解決用戶操作因果關(guān)系沖突，并且返回v1或v2中的一個作為最終值.若v1和v2不存在沖突關(guān)系，f返回的結(jié)果為v1和v2的最新值，即：如果v1depv2則f(v1，v2)=v1.

3 HashGraph

區(qū)塊鏈是一種去中心數(shù)據(jù)存儲技術(shù)，包含了2種創(chuàng)新技術(shù)：分布式賬本和共識機制，降低了了交易和數(shù)據(jù)的風(fēng)險.在分布式存儲模型中，用戶每次執(zhí)行寫入和查詢操作都作為一次事件，這些事件執(zhí)行的歷史信息在就是下次發(fā)生事件的因果一致性依賴集.如果將區(qū)塊鏈應(yīng)用在分布式存儲中，各個礦區(qū)可比作分布式存儲中各個副本，各個副本中的事件依賴集數(shù)據(jù)就類似于礦區(qū)中存儲的交易記錄；最后共識鏈同步完畢后，所有礦區(qū)都達成了共識，就像各個存儲副本同步完成，滿足了數(shù)據(jù)一致性約束；因此可以用區(qū)塊鏈相關(guān)技術(shù)來改進分布式存儲模型中副本間的數(shù)據(jù)一致性機制.

HashGraph是區(qū)塊鏈技術(shù)的一種改進，其包含2種特殊技術(shù)：八卦閑聊(Gossip about Gossip)和虛擬投票(virtual voting)，是一種提供分布式賬本和共識機制的數(shù)據(jù)結(jié)構(gòu)和一致性算法，而且比區(qū)塊鏈更快速、公平、安全.

3.1 八卦閑聊

八卦閑聊指各個事件節(jié)點定期向相鄰節(jié)點隨機地同步數(shù)據(jù)，即發(fā)送八卦消息：例如圖3中，Alice會和Bob同步她所發(fā)生的的所有事件.同樣Bob也會把他所發(fā)生的都同步給Alice.然后，Alice等節(jié)點均對不同的隨機鄰居事件重復(fù)此操作，所有其他成員也會這樣做.因此，如果單個成員接收到新的信息，它將以指數(shù)級的速度在整個社區(qū)傳播，直到每個成員都收到這一事件.

Fig. 3 Gossip about gossip between adjacent events圖3 相鄰事件之間的八卦閑聊

此外，Alice不僅會知道該事件，她還會確切地知道Bob什么時候知道了這個事件，也就會知道Carol知道Bob收到這個事件的時間.當(dāng)所有成員都有HashGraph的副本時，共識的實現(xiàn)就成為可能.當(dāng)HashGraph圖中事件線隨時間向上發(fā)展時，不同的成員在上部分可能會發(fā)生不同的新事件，但它們很快就會收斂到較低的位置，最后所有的節(jié)點都存儲相同的共識數(shù)據(jù)、事件歷史.

卦閑聊中同步的消息內(nèi)容是：收到的上個事件對應(yīng)的哈希簽名、當(dāng)前要發(fā)送的事件和當(dāng)前事件對應(yīng)的哈希簽名.所有節(jié)點在收到事件同步消息后都將歷史記錄存儲，在發(fā)送下一個事件時，當(dāng)前事件就會變成事件歷史中的上一個事件.所有節(jié)點都保存當(dāng)前HashGraph中其他副本發(fā)生過的事件歷史，為HashGraph提供了快速、可靠的溯源性.Causal-Pdh模型借鑒了HashGraph中節(jié)點進行八卦閑聊的消息格式，添加了HDS作為消息簽名，供客戶端在進行隱式依賴關(guān)系檢查時進行驗證.

3.2 虛擬投票

所有節(jié)點都收到Alice發(fā)送的消息后，記錄事件歷史的賬單就完成了同步.這是因為HashGraph所有節(jié)點都達成共識后，任意副本就知道了“其他所有副本都完成了同步”，同時其他所有節(jié)點也都知道“Bob已經(jīng)完成同步”，最后達成的共識鏈可延伸到全網(wǎng)共識.所有副本同步完成后的結(jié)果就是：大家并沒有在同一位置對事件歷史進行表決，也能公認數(shù)據(jù)同步完成這一事件，從而達成共識.

在分布式數(shù)據(jù)存儲中，模擬HashGraph中完成虛擬投票的結(jié)果，就是所有節(jié)點都同步了用戶存儲的數(shù)據(jù)，并得到當(dāng)前已寫入最新條目的時間戳，用戶可以在查詢操作中檢查數(shù)據(jù)的因果一致性，并檢查相關(guān)數(shù)據(jù)的依賴性.

4 物理時鐘與混合邏輯時鐘

傳統(tǒng)的單點存儲系統(tǒng)或網(wǎng)絡(luò)存儲系統(tǒng)等都無法同時滿足大數(shù)據(jù)存儲在性能、可擴展性和經(jīng)濟成本等方面的要求[15].而構(gòu)建于大量廉價商用硬件之上的分布式存儲系統(tǒng)，不僅可以通過并行訪問提供極高的數(shù)據(jù)存取性能，也可以通過增加存儲節(jié)點增大規(guī)模和降低成本.因此，分布式存儲系統(tǒng)在大數(shù)據(jù)的存儲管理中得到了極為廣泛的應(yīng)用[16].云存儲服務(wù)商通常為用戶提供服務(wù)的數(shù)據(jù)中心分布在世界各地，以滿足不同地點用戶的需求.當(dāng)各個數(shù)據(jù)中心之間使用NTP協(xié)議同步本地物理時鐘時，便面臨著一個嚴峻的問題：時鐘異常.

時鐘異常指的是不同副本在同步時鐘狀態(tài)時，由于距離差異，節(jié)點通信過程中會產(chǎn)生一定的通信時延，從而造成發(fā)送請求到收到回復(fù)所用的響應(yīng)時間也有所不同，造成各個中心時間無法同步、NTP漂移等問題.

4.1 GentleRain與物理時鐘

GentleRain模型除了通過NTP服務(wù)器更新物理時鐘，還定義了一個單向的狀態(tài)向量，即全局穩(wěn)定時間，來滿足因果一致性模型中對事件因果序的約束.該模型在寫入數(shù)據(jù)時，依據(jù)本地時鐘為每個值分配一個時間戳數(shù)據(jù)，同步存儲到條目元數(shù)據(jù)中.當(dāng)副本處理新的用戶操作時，依據(jù)當(dāng)前副本的物理時鐘為該操作分配一個時間戳t，而且當(dāng)副本的物理時鐘為T值時，用戶就可查詢到當(dāng)前副本中存儲的所有時間戳小于等于T的數(shù)據(jù)條目.但該模型在客戶端讀取/寫入一個時間戳t的鍵時，接下來客戶端調(diào)用的任意PUT操作都必須具有高于t的時間戳，因此會在某些操作中需要等待.

混合邏輯時鐘基于物理時鐘，依據(jù)當(dāng)前服務(wù)器本地時間分配事件的時間戳，同時結(jié)合邏輯時鐘能為系統(tǒng)提供檢驗依賴關(guān)系的因果序，Causal-Pdh模型使用了改進后的混合邏輯時鐘，從而避免了出現(xiàn)物理時鐘造成的PUT延遲等問題.

4.2 混合邏輯時鐘

混合邏輯時鐘[11]結(jié)合了邏輯時鐘和物理時鐘，充分發(fā)揮了兩者的優(yōu)勢.事件e的HLC時間戳表示為hlc.e，這是一個元組l.e,c.e.第1個分量l.e是e發(fā)生時本地服務(wù)器網(wǎng)絡(luò)時間信息.c.e是一個有界計數(shù)器，可捕捉事件之間的因果關(guān)系.若時鐘偏移造成2個事件時間戳相同時，僅用l.e無法判別2個事件之間的因果關(guān)系.

具體而言，如果2個事件e和f，使得e在f之前發(fā)生(定義1)，并且l.e=l.f，為了捕獲e和f之間的因果關(guān)系，將c.e設(shè)置為高于c.f的值，雖然c在遞增，如文獻[11]中，c的理論最大值是O(n)，其中n是進程的數(shù)量.而實際上，這個值仍然很小.除HLC時間戳之外，每個進程還維護一個HLC時鐘l.a,c.a.

算法1.HLC[11].

輸入：事件a、當(dāng)前物理時間；

輸出：時間戳l.a,c.a.

① 在收到進程a發(fā)送的消息時:

②l′.a=l.a;

③l.a=max(l′.a;pt.a); /*追蹤最新事件，pt.a是a的物理時間*/

④ if(l.a=l′.a)

c.a=c.a+1; /*追蹤因果序*/

⑤ elsec.a=0;

⑥ end if

⑦ 使用l.a,c.a作為事件的時間戳.

HLC不僅包含邏輯時鐘的優(yōu)點，而且可以追蹤2個事件之間的因果關(guān)系.具體來說，如果e發(fā)生在f之前，那么hlc.e

5 Causal-Pdh協(xié)議

Causal-Pdh協(xié)議是一種可以穩(wěn)定運行在分布式云存儲中的通信協(xié)議，在滿足因果一致性存儲需求的基礎(chǔ)上，為用戶提供安全快速的寫入、查詢和存儲服務(wù)[17].如圖4(a)所示，下劃線內(nèi)容為Causal-Pdh在用戶寫入操作中引入了服務(wù)端HDS作為消息簽名，即在服務(wù)端計算應(yīng)發(fā)送數(shù)據(jù)條目依賴集的Hash校驗值.服務(wù)端在回應(yīng)用戶請求中對應(yīng)的的依賴集時，將簽名附加在消息簽名部分，客戶端在收到響應(yīng)消息后，首先同步依賴集數(shù)據(jù)，然后與收到的服務(wù)端HDS簽名進行校驗.

Fig. 4 PUT and GET operations in Causal-Pdh圖4 Causal-Pdh模型中的PUT和GET操作

其次在圖4(b)中，服務(wù)器收到用戶查詢操作請求后，首先在本地計算HDS簽名，然后將partDSV數(shù)據(jù)和服務(wù)端HDS簽名一起封裝到響應(yīng)消息中.部分依賴集向量partDSV是當(dāng)前服務(wù)端所有依賴項的某個子集，同步到客戶端后供其更新查詢到的條目依賴集，客戶端更新本地穩(wěn)定向量(DSVC)后計算HDS與簽名進行驗證.

分布式存儲系統(tǒng)不同于物理機，而是多個節(jié)點基于不同位置，協(xié)同更新數(shù)據(jù)提供計算或存儲服務(wù)的平臺；因此服務(wù)器在收到用戶寫入數(shù)據(jù)的請求后，要在系統(tǒng)中執(zhí)行分配存儲空間、寫入數(shù)據(jù)、同步各數(shù)據(jù)中心數(shù)據(jù)和狀態(tài)等一系列操作.

Causal-Pdh協(xié)議中最后一步的過程如圖5所示，各分區(qū)將本地已寫入的最新消息與其父節(jié)點同步，并附加HDS作為簽名，父節(jié)點將本地最新DSV隨機與其他數(shù)據(jù)中心同步，并且驗證HDS簽名.借鑒HashGraph中的Gossip about Gossip思想，系統(tǒng)中的DSV消息是隨機發(fā)送到其他節(jié)點的，最近的更新數(shù)據(jù)在系統(tǒng)中呈指數(shù)級擴散，因此完成虛擬投票的速度得到了極大提升.

Fig. 5 Synchronization among data centers in Causal-Pdh圖5 Causal-Pdh模型中各數(shù)據(jù)中心間的同步

DSV是一個多維集合，包括當(dāng)前數(shù)據(jù)中心的時鐘信息，及其存儲的所有數(shù)據(jù)條目，標記當(dāng)前存儲副本的最新穩(wěn)定狀態(tài).Causal-Pdh在數(shù)據(jù)中心穩(wěn)定向量的基礎(chǔ)之上，將GET操作中DSV的內(nèi)容進行了精簡，只發(fā)送partDSV和依賴集更新完之后對應(yīng)的摘要值，partDSV即當(dāng)前數(shù)據(jù)中心DSV的依賴子集；在PUT操作中則附加一個摘要值HDS作為簽名，使得客戶端能在更新本地鍵值鏈后與服務(wù)端的依賴關(guān)系進行驗證.DSV允許數(shù)據(jù)存儲模型在多個客戶端中存在一些慢副本[18]的情況時提供高效、準確的存取服務(wù)，同時降低更新可見性延遲.數(shù)據(jù)副本內(nèi)部分區(qū)之間更新狀態(tài)使用的是與數(shù)據(jù)中心穩(wěn)定向量類似的VV消息(versions vector)，而且是數(shù)據(jù)中心更新DSV的依據(jù)之一，因為副本進行存取操作都會在收到請求之后，詳見5.2節(jié).

5.1 客戶端

客戶端Client與服務(wù)端均同步更新1組數(shù)據(jù)中心ID和HLC時間戳，該組數(shù)據(jù)稱為依賴關(guān)系集，用DS(dependency series)表示，為了區(qū)分客戶端和服務(wù)端間的差別，用DSC標識客戶端依賴關(guān)系集.對于每個數(shù)據(jù)中心i，發(fā)送的的依賴集DSC中最多只有1個條目i,h，其中h指的是客戶端Client可查詢到的最新值的時間戳信息，而這些值是客戶端曾經(jīng)寫入到數(shù)據(jù)中心i中的.

算法2是客戶端PUT和GET操作的算法.在GET操作中，客戶端的請求信息包括請求的鍵及其DSVC.Causal-Pdh協(xié)議結(jié)合HashGraph中的共識機制gossip about gossip，在響應(yīng)消息中附加一個消息的摘要值作為消息簽名，服務(wù)器將所請求鍵的值、返回值的DS、服務(wù)器中的依賴關(guān)系列表partDSV及其簽名HDS一起發(fā)送至客戶端.客戶端收到服務(wù)器回應(yīng)后，首先更新其穩(wěn)定狀態(tài)信息DSV，然后調(diào)用updateDS函數(shù)來更新DSC：對于每個DS的子集i,h，如果在DSC中存在某條目i，h′，則選取h和h′中的最大值作為h′，若不存在則直接將i,h添加到DSC中，最后在客戶端生成依賴集的校驗值，并與收到的簽名信息進行驗證并保存.

對于PUT操作，客戶端將想要寫入的密鑰與期望值及其DSC一起發(fā)送到服務(wù)器.服務(wù)器在發(fā)送響應(yīng)消息時，將此更新使用的時間戳、數(shù)據(jù)中心的ID與依賴集對應(yīng)的摘要值HDS等信息統(tǒng)一封裝進響應(yīng)數(shù)據(jù)中.客戶端可調(diào)用updateDS函數(shù)更新其PUT操作的DSC，最后在更新完成后計算本地依賴集的校驗簽名進行驗證并保存.

算法2.客戶端Client中的操作.

1)GET(k)過程.

輸入：鍵k;

輸出：v,DS,partDSV,HDS.

③DSVC←max(DSVC,DSV); /*根據(jù)數(shù)據(jù)中心最新穩(wěn)定狀態(tài)更新客戶端狀態(tài)*/

⑤DSC←updateDS(i,h,DSC);

/*更新依賴集*/

⑥ end for;

⑦ ifHash(DSC)==HDSreturnv;

/*驗證HDS簽名*/

⑧ elseGET(keyk);

⑨ end if

2)PUT(k,v)過程.

輸入：鍵k、值v;

輸出：ut,sr,HDS.

③DSC←updateDS(sr,ut,DSC); /*收到寫入完成的響應(yīng)后更新本地依賴集*/

④ ifHash(DSC)==HDSreturnv; /*驗證響應(yīng)消息中的HDS簽名*/

⑤ elsePUT(k);

⑥ end if

5.2 服務(wù)端

存儲在服務(wù)端的每條元數(shù)據(jù)，除了鍵值對之外，還包括其他信息，包括該條目存儲的物理地址，鍵值創(chuàng)建的HLC時間戳信息ut，原來所在的副本信息sr，以及數(shù)據(jù)條目的1組依賴關(guān)系DS.

算法3是服務(wù)端中的PUT和GET算法.服務(wù)端在收到GET請求后，首先使用其中的DSVC值更新其狀態(tài)信息DSV，然后根據(jù)請求中鍵在本地檢索最新值，或該鍵在本地數(shù)據(jù)中心可查詢到的所有依賴關(guān)系.檢索到信息后，服務(wù)端對比該鍵的DS與數(shù)據(jù)中心的DSV信息，從而保障準確性.服務(wù)端一般使用沖突解決函數(shù)last_writer_wins解決中心的IDs之間的沖突，來檢索最新狀態(tài)的值，最后參照HashGraph共識機制中事件之間八卦閑聊的核心機制，服務(wù)端統(tǒng)一封裝該鍵、值、及其依賴關(guān)系集、partDSV和HDS校驗信息到查詢響應(yīng)消息中，并向客戶端發(fā)送.

1)GET(k)過程.

輸入：鍵k、dsv;

③ 獲取鍵值鏈中k的最新條目d;

④DS←updateDS(d.sr,d.ut,d.DS);

/*根據(jù)條目d更新依賴集*/

2)PUT(k)過程.

輸入：鍵k、值v、DS;

輸出：d.ut,m.

②dt←maximum value inDS;

③updateHLC(dt);

④ create new itemd;

/*為新的條目分配空間*/

⑥ insertdto key chain ofk; /*將新條目插入到k的版本鏈中*/

⑩ end for

算法4是更新DSV的算法.數(shù)據(jù)中心內(nèi)的分區(qū)會定期對狀態(tài)信息DSV進行更新，每過θ時間間隔，分區(qū)與分區(qū)之間分別共享其VV狀態(tài)信息，并在每次心跳機制更新完后請求狀態(tài)信息DSV作為最新VV狀態(tài).基于HashGraph共識機制，每個父節(jié)點在接收到其子節(jié)點的VV狀態(tài)信息及其vvHDS簽名時，都計算最新的VV條目及其校驗簽名信息發(fā)送到其他子節(jié)點.然后數(shù)據(jù)中心統(tǒng)一封裝最后更新的DSV和簽名校驗信息dsvHDS簽名為DSV消息，隨機發(fā)送給其他對等節(jié)點，從而將最新的狀態(tài)信息和數(shù)據(jù)更新到整體拓撲網(wǎng)絡(luò)中.其余每個節(jié)點在收到DSV時更新其DSV并驗證dsvHDS簽名.算法4包含了心跳機制的算法，基于心跳機制定時發(fā)送心跳消息(heartbeat message)的目的是更新其他父節(jié)點的分區(qū)中相對等的狀態(tài)和數(shù)據(jù)信息，如果數(shù)據(jù)中心在某固定的Δ時間段(心跳機制的時間間隔)內(nèi)未發(fā)送任何數(shù)據(jù)更新的復(fù)制消息(replicate message)，數(shù)據(jù)中心就會向相鄰的其他節(jié)點發(fā)送心跳消息(heartbeat message)，保持時鐘同步的同時提供數(shù)據(jù)更新依據(jù).

輸出：DSV，dsvHDS.

① 每過θ時間間隔,do

③ 每過Δ時間間隔無replicate message,do

/*按照心跳機制同步最新狀態(tài)*/

④updateHCL();

k≠mdo

⑨ checkvvHDS;

⑩ end for

6 實驗測試與分析

Causal-Pdh模型基于Java語言，采用鍵值數(shù)據(jù)庫Berkeley DB存儲和檢索元數(shù)據(jù)信息.該數(shù)據(jù)庫可支持關(guān)系型數(shù)據(jù)庫中最常用的的完整ACID事務(wù)語義，也提供NoSQL中簡單的數(shù)據(jù)庫編程接口[19].實驗在DKVF平臺[20]的基礎(chǔ)上布置和管理分布式副本，作為一個分布式鍵值存儲管理框架，DKVF平臺使用Berkeley db作為數(shù)據(jù)存儲模塊，集成了Google開發(fā)的數(shù)據(jù)結(jié)構(gòu)化協(xié)議Protocol Buffer和Yahoo的性能測試工具YCSB，此外，DKVF平臺還實現(xiàn)了COPS，GentleRain，CausalSpartan等協(xié)議.為了模擬實際環(huán)境中不穩(wěn)定的用戶請求情況，并對不同模型處理高并發(fā)請求的性能進行測試與統(tǒng)計，實驗每次收集的數(shù)據(jù)均是在客戶端和服務(wù)端存取1 000個鍵值信息，并在同樣環(huán)境下進行3次重復(fù)并取得的平均結(jié)果.

實驗中本地服務(wù)器和云服務(wù)器規(guī)格為：本地服務(wù)器運行Windows10 x64，Intel Core i7-6700，3.4 GHz，8 GB內(nèi)存，256 GB固態(tài)磁盤存儲.云服務(wù)器為運行Windows Server 2012的Aliyun ecs.n4.small實例和Tencent cvm實例，1個vCPU，Intel Xeon E5-2622，2.5 GHz，2 GB內(nèi)存，40 GB存儲.

6.1 時鐘偏移對PUT等待時間的影響

為了準確研究時鐘偏移對響應(yīng)時間的影響，須對兩副本之間的時鐘狀態(tài)進行人工管控.但實際環(huán)境中服務(wù)器一般使用NTP協(xié)議進行更新，其時鐘偏差取決于人為控制之外的許多因素.因此為了使結(jié)果更加精確和權(quán)威，實驗在1臺物理機中設(shè)置了2個分布式服務(wù)端，并參照圖5的拓撲結(jié)構(gòu)，為每臺個服務(wù)端分配一個數(shù)據(jù)分區(qū)，不同的是，2個服務(wù)器運行的Causal-Pdh數(shù)據(jù)服務(wù)之間存在一個可變的人為時鐘偏差.實驗還配置了不同的客戶端分別以循環(huán)方式向服務(wù)器發(fā)送PUT請求，依據(jù)不同情況下的時鐘偏差，對PUT操作平均響應(yīng)時間的進行統(tǒng)計.

Fig. 6 PUT response time in the same physical machine and different physical machines圖6 同一物理機和不同物理機中的PUT響應(yīng)時間

圖6(a)顯示，隨著時鐘偏差數(shù)值的遞增，Gentle-Rain中PUT操作的平均響應(yīng)時間呈遞增趨勢，而Causal-Pdh和CausalSpartan中的平均響應(yīng)時間無明顯變化趨勢，與時鐘偏差未表現(xiàn)出明顯函數(shù)關(guān)系.由于Causal-Pdh協(xié)議提出部分穩(wěn)定狀態(tài)的概念partDSV，并使用HDS狀態(tài)信息簽名驗證依賴集消息的完整性，若系統(tǒng)中產(chǎn)生高并發(fā)的讀寫操作，操作的響應(yīng)時間比CausalSpartan協(xié)議的平均降低了20.85%，驗證了1.2節(jié)主要工作1)中提出的完整性約束，可見Causal-Pdh模型較適合應(yīng)用于存在時鐘漂移，或網(wǎng)絡(luò)時鐘同步易出現(xiàn)風(fēng)險的的分布式存儲環(huán)境中.

Fig. 7 Impact of clock offset between partitions on request response time圖7 分區(qū)之間的時鐘偏移對請求響應(yīng)時間造成的影響

圖6(b)是在2臺不同的機器上進行的測試，結(jié)果表明如果不對時鐘信息引入人為設(shè)置的時鐘偏差，僅使用NTP來同步物理時鐘，PUT等待延遲的影響也是可見的.實驗為每個副本內(nèi)分配2個數(shù)據(jù)存儲分區(qū)，客戶端以循環(huán)方式向這些服務(wù)器發(fā)送隨機數(shù)據(jù)的PUT請求.CausalSpartan和Causal-Pdh在無時鐘偏移情況下的響應(yīng)時間都明顯低于Gentle-Rain，這是由于父節(jié)點之間同步數(shù)據(jù)和狀態(tài)時，發(fā)送的依賴集信息DS是一段長度有限的消息，而Hash-Graph中同步所有用戶事件歷史，完成虛擬投票達成共識所需的時間極短，尤其是系統(tǒng)中只有50～100個節(jié)點時，耗費時間可以忽略不計，所以計算消息的摘要作為校驗值不僅沒有造成更大的性能開銷和計算延遲，反而提升了系統(tǒng)性能和響應(yīng)速度.但由于兩者均使用了混合邏輯時鐘HLC作為因果一致性判斷依據(jù)，為用戶時間分配的時間戳信息類似，CausalSpartan與Causal-Pdh協(xié)議的PUT響應(yīng)時間沒有表現(xiàn)出明顯的差異.

6.2 查詢放大對響應(yīng)時間的影響

單個最終用戶請求在服務(wù)器中可能會轉(zhuǎn)化為許多因果關(guān)系的內(nèi)部查詢，這種現(xiàn)象被稱為查詢放大[21]，尤其在數(shù)據(jù)存取服務(wù)商為成千上萬個用戶同時提供高并發(fā)服務(wù)時，查詢放大會更加嚴重.實驗將單個請求在內(nèi)部造成復(fù)雜查詢的數(shù)量定義為查詢放大因子.為了研究實際環(huán)境中的影響，本節(jié)實驗在同一物理機中安裝了2個數(shù)據(jù)副本，避免網(wǎng)絡(luò)通信造成時鐘同步偏移的問題同時分別設(shè)置遞增的人為時鐘偏移，目的是針對查詢放大情況對操作響應(yīng)時間的影響進行精準的定量分析，圖6即為實驗結(jié)果.實驗規(guī)定服務(wù)器以循環(huán)方式向分區(qū)PUT隨機數(shù)據(jù)，是為了模擬實際應(yīng)用中大量用戶向Web應(yīng)用服務(wù)器發(fā)送讀寫請求的場景.

圖7實驗是在數(shù)據(jù)副本之間設(shè)置了人為時鐘偏移，且每個最終請求都包含了幾百個甚至更多的內(nèi)部查詢，實驗結(jié)果顯示，查詢放大情況越嚴重，請求響應(yīng)延遲越明顯.且表格中曲線的增長速度可看作該協(xié)議受查詢放大情況的影響程度，隨著查詢放大情況變得越來越明顯，GentleRain的增長速度明顯高于其余兩者，而CausalSpartan和Causal-Pdh的增長速度明顯較慢.例如，在2個數(shù)據(jù)中心之間存在2 ms時鐘偏差時，GentleRain中查詢放大因子為100時的請求的響應(yīng)時間比CausalSpartan高3倍，比Causal-Pdh高3.5倍.在實際分布式存儲環(huán)境中，時鐘偏移完全可能更大[22].例如，當(dāng)?shù)讓油ㄐ啪W(wǎng)絡(luò)受到不對稱鏈路的影響或服務(wù)商遭受網(wǎng)絡(luò)惡意攻擊影響通信延遲時，時鐘偏差可達100 ms或者更高.在這種情況下，當(dāng)查詢放大因子達到100時，GentleRain的響應(yīng)時間比CausalSpartan和Causal-Pdh高35倍.

由于GentleRain模型容易受到時鐘偏移等異常情況的影響，為了使結(jié)果更加直觀，圖7(b)(c)都只將查詢放大因子小于200時GentleRain的平均響應(yīng)時間放入結(jié)果中.同樣條件下Causal-Pdh模型與CausalSpartan相比，請求響應(yīng)時間平均降低了23.27%.例如時鐘偏移為4 ms，查詢放大因子為200時Causal-Pdh比CausalSpartan的響應(yīng)時間降低了23.37%，而時鐘偏移為8 ms且查詢放大因子為500時則降低了22.02%.由實驗數(shù)據(jù)可見，Causal-Pdh模型借鑒HashGraph中八卦同步機制，隨機與對等節(jié)點同步節(jié)點間更新的數(shù)據(jù)和狀態(tài)，簡化GET操作回應(yīng)消息格式，并且計算校驗值作為消息簽名校驗數(shù)據(jù)完整性，相比于CausalSpartan方案，在降低用戶請求響應(yīng)時間方面是可行的、有效的，同時表明Causal-Pdh模型在查詢放大、時鐘偏差較嚴重或網(wǎng)絡(luò)環(huán)境較差的環(huán)境中會有更優(yōu)秀的表現(xiàn).

圖8(a)是6個數(shù)據(jù)中心8個分區(qū)均使用使用NTP協(xié)議同步，且分區(qū)間不存在人工時鐘偏差時，放大因子對請求響應(yīng)時間的影響.結(jié)果表明了查詢放大對請求響應(yīng)的影響規(guī)律：單個客戶端造成的查詢放大情況越明顯，即查詢放大因子越大，服務(wù)器處理請求所需的響應(yīng)時間就越長.在同樣的實驗環(huán)境中，Causal-Pdh模型的請求響應(yīng)延遲比Causal-Spartan平均降低了37.85%.例如，對于查詢放大因子200，GentleRain的請求響應(yīng)時間比Causal-Spartan高1.64倍，比Causal-Pdh高4.74倍.

吞吐量是客戶端在單位時間內(nèi)更新鍵值的數(shù)目，即客戶端更新鍵值的速度.圖8(b)中結(jié)果顯示，在查詢放大情況越來越嚴重時，不同數(shù)據(jù)一致性存儲模型中客戶端請求的吞吐量在逐漸降低，這是因為服務(wù)端處理查詢請求時，單個客戶端的查詢造成內(nèi)部查詢的次數(shù)越多，服務(wù)端響應(yīng)時間越長，同時客戶端收到更新的速度越慢，吞吐量越低.

Fig. 8 Effect of amplification factor on client request response time圖8 放大因子對客戶端請求響應(yīng)時間的影響

6.3 通信時延對更新可見性延遲的影響

評價分布式數(shù)據(jù)一致性存儲模型的重要指標之一是更新可見性延遲，指的是從客戶端發(fā)送數(shù)據(jù)和狀態(tài)更新請求，到在遠程副本中同步完成，可供其余客戶端查詢的時間延遲.其單位一般在ms級別，但即使短短幾毫秒，對許多用戶和數(shù)據(jù)存取服務(wù)提供商來說也十分重要，因為某單一用戶的查詢可能造成大量不同位置的數(shù)據(jù)查詢；服務(wù)商也同時為數(shù)十萬甚至上百萬個終端用戶提供并發(fā)的數(shù)據(jù)存取服務(wù)，許多用戶的更新可見性延遲最后累計在一起，就會造成很明顯的查詢等待情況，甚至也給服務(wù)器帶來非常大的負載.

實驗基于Casual-Pdh協(xié)議設(shè)計了一個分布式數(shù)據(jù)存儲系統(tǒng)，包含不同位置的3個數(shù)據(jù)中心，將其中2個位置固定不變，通過改變第3個數(shù)據(jù)中心C的地理位置，并收集C到其余數(shù)據(jù)中心A/B的網(wǎng)絡(luò)通信往返時間，從而得到表1中不同模型在分區(qū)間存在較不同的通信時延時的性能表現(xiàn).系統(tǒng)設(shè)定2個客戶端分別對鍵k的值進行循環(huán)讀取，并在數(shù)據(jù)副本C位置發(fā)生改變時，分別讀取到奇數(shù)與偶數(shù)時對該鍵實施遞增操作.數(shù)據(jù)中心A和B的位置固定在河北省保定市，第3個分區(qū)則根據(jù)到保定市的距離不斷遞增的規(guī)則，分別租用云服務(wù)器在北京市，四川省成都市和廣東省廣州市提供服務(wù).由表1結(jié)果可得知，同步不同地理位置的數(shù)據(jù)副本中的數(shù)據(jù)時，往返時間遞增的趨勢主要原因是彼此之間越來越遠的距離.

Table1 RoundtripTime from the Third Replica to the Rest at Different Locations表1 第3個副本在不同位置時的往返時間 ms

更新可見性延遲是從客戶寫入新的更新，到另一客戶端讀取到更新之間的時間間隔.由于在不同地理位置的數(shù)據(jù)中心之間必然存在一定的時鐘偏移，實驗所得結(jié)果是實際更新可見性延遲的一個接近值.

實驗中慢副本指的是某個因為距離過遠造成通信往返時間很長，或者網(wǎng)絡(luò)分區(qū)故障導(dǎo)致與其他節(jié)點通信被延遲的數(shù)據(jù)中心.圖9(a)表明了Causal-Spartan和Causal-Pdh中的更新可見性延遲低于GentleRain.此外，隨著3個數(shù)據(jù)副本間網(wǎng)絡(luò)通信延遲的增加，GentleRain中的更新可見性延遲也在逐漸增加，表明GentleRain在網(wǎng)絡(luò)環(huán)境差、網(wǎng)絡(luò)通信延遲高的環(huán)境中性能會受到一定的影響.但CausalSpartan和Causal-Pdh并未受到影響，這是因為兩者使用DSV指明本地最新的鍵值條目，在通信時延較高、或復(fù)雜網(wǎng)絡(luò)環(huán)境中提升了數(shù)據(jù)中心與慢副本、客戶端與服務(wù)端之間存在造成的更新響應(yīng)速度.

Fig. 9 Impact of update visibility latency and throughput when data center C is in different locations圖9 C在不同位置時對更新可見性延遲和吞吐量的影響

圖9(b)是數(shù)據(jù)中心C在不同地理位置時客戶端請求的吞吐量變化趨勢.由于CausalSpartan和Causal-Pdh都基于HLC使用了DSV標識分區(qū)最新狀態(tài)，客戶端的一些PUT/GET請求可能會在服務(wù)端造成更多的內(nèi)部查詢來判別操作的因果序，所以兩者吞吐量相比GentleRain明顯增加.

6.4 DSV對客戶端吞吐量的影響

Causal-Pdh和CausalSpartan都基于混合邏輯時鐘方法分區(qū)中的用戶事件分配時間戳信息，并且均設(shè)置數(shù)據(jù)中心狀態(tài)向量標識最新數(shù)據(jù)時間，為了直觀地研究兩者各自的影響，實驗在本地環(huán)境中完成，使用DKVF框架管理2個數(shù)據(jù)中心2個分區(qū)，在Casual-Pdh模型中分別單獨使用HLC和DSV的時候，測試了處理收到的不相關(guān)的PUT/GET操作的吞吐量.

圖10表明，如果僅使用數(shù)據(jù)中心穩(wěn)定向量表明在分布式數(shù)據(jù)存儲管理副本的狀態(tài)，基于物理時鐘同步時鐘信息，而且將PUT和GET設(shè)置為相互獨立的操作時，CausalSpartan和Causal-Pdh模型在服務(wù)端中的吞吐量比GentleRain低5%，然而Causal-Pdh和CausalSpartan的吞吐量并無差異，因為兩者均使用DSV標識數(shù)據(jù)副本最新狀態(tài).

時鐘信息的同步只會影響PUT,GET等原子操作的處理時間，因為每個操作均需依據(jù)時鐘數(shù)據(jù)判別因果關(guān)系，因此僅使用物理時鐘作為分區(qū)時間，無分區(qū)穩(wěn)定向量的情況下，CausalSpartan,GentleRain和Causal-Pdh的吞吐量并無明顯差別.

Fig. 10 Throughput of GET/PUT operations in three models圖10 3個模型中GET/PUT操作的吞吐量

7 總 結(jié)

現(xiàn)有的數(shù)據(jù)因果一致性研究成果在分區(qū)間存在網(wǎng)絡(luò)時差的環(huán)境中，一般采用物理時鐘同步時鐘信息容易產(chǎn)生PUT延遲影響性能，而且在慢副本較多的環(huán)境中更新可見性延遲也會明顯提高，影響用戶的實際體驗.在現(xiàn)有成果基礎(chǔ)上，Causal-Pdh降低了CausalSpartan中PUT/GET操作消息的復(fù)雜度，明顯提升了系統(tǒng)在用戶短時間產(chǎn)生大量并發(fā)請求時的響應(yīng)速度.本文引入了HashGraph相關(guān)技術(shù)，重新設(shè)計數(shù)據(jù)中心之間同步最新條目的消息格式，將dsvHDS作為消息簽名，用于驗證同步過程的完整性，此改進有效降低了存在查詢放大和分區(qū)之間發(fā)生時鐘偏移時的PUT操作等待時間.此外，Causal-Pdh借鑒HashGraph中Gossip about Gossip的思想，將數(shù)據(jù)中心之間發(fā)送穩(wěn)定狀態(tài)同步消息的方式改為隨機地向其他節(jié)點同步，有效降低了各個副本同步數(shù)據(jù)和狀態(tài)信息、進行虛擬投票，滿足數(shù)據(jù)因果一致性約束并達成最終共識過程所耗費的時間，并在實驗結(jié)果中驗證了此結(jié)論.