田俊峰，王彥骉，何欣楓，張俊濤，楊萬賀，龐亞南

（1.河北大學網(wǎng)絡空間安全與計算機學院，河北 保定 071002；2.河北省高可信信息系統(tǒng)重點實驗室，河北 保定 071002）

1 引言

云存儲是當今世界互聯(lián)網(wǎng)服務的重要組成部分，云服務商將數(shù)據(jù)中心分別部署在不同的地方，為用戶提供可擴展的計算、存儲等服務[1]。分布式云存儲的典型應用之一就是大數(shù)據(jù)存儲，數(shù)據(jù)一致性則是大數(shù)據(jù)存儲中的基本課題之一。

基于地理復制策略設計分布式云存儲系統(tǒng)時，數(shù)據(jù)一致性協(xié)議的設計是基本課題之一[2]。數(shù)據(jù)一致性理論來自Brewer[3]提出的CAP 定理，其包括3個方面：一致性（consistency），可用性（availability），分區(qū)容忍性（partition tolerance）。其中，一致性指同一個數(shù)據(jù)在集群中的所有節(jié)點，同一時刻可供查詢的值是否一致；可用性指集群中一部分節(jié)點故障后，集群整體是否還能繼續(xù)處理客戶端的更新請求；分區(qū)容忍性指系統(tǒng)應確保在部分網(wǎng)絡出現(xiàn)異常的情況下仍能正常使用，除非網(wǎng)絡整體癱瘓。

隨著云存儲的不斷普及與應用，安全問題已成為制約其進一步發(fā)展的重要因素[4]。在云存儲平臺中，病毒、木馬、黑客入侵等不安全因素的存在難免會對用戶的操作結果一致性產生影響，例如，用戶寫入與查詢數(shù)據(jù)過程中，服務器主副節(jié)點的數(shù)據(jù)可能會因節(jié)點存在不安全因素被篡改，影響數(shù)據(jù)一致性操作結果的可信性；節(jié)點間同步新數(shù)據(jù)過程中，節(jié)點與節(jié)點間、節(jié)點內分區(qū)間可能由于信道不可信造成同步數(shù)據(jù)被竊聽、篡改、阻礙或時延，造成節(jié)點間數(shù)據(jù)無法正確同步。

當前數(shù)據(jù)一致性方面的研究都是基于理想環(huán)境的，對環(huán)境中的不安全因素疏于考慮。在可信云平臺日漸成熟的情況下，如何分析研究可信環(huán)境下的數(shù)據(jù)一致性問題具有重要的理論意義和應用價值。對政企用戶、云服務商來說，數(shù)據(jù)一致性是數(shù)據(jù)安全的基本保障之一，而科學技術部發(fā)布的“云計算和大數(shù)據(jù)”等重點專項2018 年度項目的基礎研究類的創(chuàng)新鏈也包含“大規(guī)模分布式可擴展的數(shù)據(jù)存儲”和“數(shù)據(jù)副本一致性”，說明數(shù)據(jù)一致性對大數(shù)據(jù)安全、國民經(jīng)濟發(fā)展，乃至國防安全都是至關重要的。

數(shù)據(jù)一致性一般分為強一致性和弱一致性[5]。強一致性要求所有數(shù)據(jù)項的本地更新都立刻在其他副本中可見，對副本中數(shù)據(jù)的及時更新有著極高的要求[6]，而且該模型的實現(xiàn)要求極高的性能開銷。弱一致性只要求不同節(jié)點中數(shù)據(jù)最終一致，對數(shù)據(jù)的及時更新沒有任何要求，難以為用戶提供最新的數(shù)據(jù)[7]。相比于強、弱一致性的局限性，因果一致性屬于一種中間一致性模型，該模型不僅能提供數(shù)據(jù)的及時更新，在因果依賴性的影響可見時，也能保障用戶事件的因果序。

在關系型數(shù)據(jù)庫中，數(shù)據(jù)一致性是指事務執(zhí)行的結果必須是使數(shù)據(jù)庫從一個一致性狀態(tài)變到另一個一致性狀態(tài)，而數(shù)據(jù)因果一致性主要應用于判別非關系數(shù)據(jù)庫中操作數(shù)據(jù)條目的前后順序，即通過對CAP 定理的權衡，在為用戶提供數(shù)據(jù)存儲的同時，保障同一客戶端或進程對數(shù)據(jù)的操作有序。而不對同客戶端或線程的數(shù)據(jù)操作順序有任何要求。非關系型數(shù)據(jù)庫，即NoSQL（not only SQL）指的是基于CAP 定理提供鍵值存儲服務的鍵值存儲數(shù)據(jù)庫，例如Redis、Mongo DB、MICA[8]等。

影響數(shù)據(jù)因果一致性的因素有很多。首先，云服務供應商（CSP,cloud service provider）通常將不同的存儲節(jié)點分布在不同的地理位置，但節(jié)點間數(shù)據(jù)更新的共識則依賴于節(jié)點間時鐘與狀態(tài)的及時同步。此外，節(jié)點內部數(shù)據(jù)復制的策略、客戶端與服務端對一致性元數(shù)據(jù)的操作以及用戶操作事務的序列化等方面都對分布式云存儲中數(shù)據(jù)因果一致性有著不容忽視的影響。數(shù)據(jù)因果一致性的4 個主要方面如圖1 所示。

圖1 數(shù)據(jù)因果一致性的4 個主要方面

本文通過介紹分布式云存儲環(huán)境下因果一致性協(xié)議中節(jié)點間時鐘同步方法、節(jié)點存儲數(shù)據(jù)的存取與用戶操作事務的序列化相關的研究進展，分析并對比經(jīng)典方案的特點、適用范圍，以及在及時更新和性能方面的權衡，對已有工作的優(yōu)點和局限性進行討論，進而指出數(shù)據(jù)因果一致性未來的發(fā)展趨勢和后續(xù)研究方向。

2 副本間的時鐘同步

傳統(tǒng)的單點存儲系統(tǒng)或網(wǎng)絡存儲系統(tǒng)等都無法同時滿足大數(shù)據(jù)存儲在性能、可擴展性和經(jīng)濟成本等方面的要求。目前，構建于大量廉價商用硬件之上的云存儲系統(tǒng)一般通過增加存儲副本來提升性能、降低成本，因此，副本云存儲系統(tǒng)在大數(shù)據(jù)的存儲管理中得到了極其廣泛的應用[9]。CSP 通常將為用戶提供服務的存儲副本分布在世界各地，以滿足不同地點用戶的需求。各個數(shù)據(jù)中心之間的時鐘同步一般采用網(wǎng)絡時間協(xié)議（NTP,network time protocol,）同步本地物理時鐘，這就面臨著一個嚴峻的問題——時鐘異常。

時鐘異常指的是不同副本之間進行時鐘同步時，不同地理位置的副本在通信過程中由于距離差異產生的一定通信時延，使發(fā)送請求到收到回復所用的響應時間有所不同，從而造成各個副本時間不同步、NTP 漂移等。而在分布式系統(tǒng)中，數(shù)據(jù)一致性服務對客戶端和服務端間的低開銷網(wǎng)絡通信有著極高的要求。若用戶在當前客戶端發(fā)送了帶有本地時間戳的查詢請求，而數(shù)據(jù)中心的穩(wěn)定時間小于請求中的時間戳，從而造成查詢失敗，影響因果一致性系統(tǒng)的可用性。

在使用當前副本的時鐘作為判斷用戶操作順序的因果一致性方案中，依據(jù)副本同步的網(wǎng)絡時間為條目分配的時間戳是系統(tǒng)判別用戶操作因果序的唯一依據(jù)，目前有2 種常見的時鐘同步方法，一種是單純地使用物理時鐘，另一種是混合邏輯時鐘。

2.1 物理時鐘

物理時鐘方案使用單向標量來檢查依賴關系，通過提供因果一致性的快照，來保證用戶寫入事件滿足原子性，從而避免寫入等待沖突。當副本處理新的用戶操作時，依據(jù)當前副本的物理時鐘為該操作分配一個時間戳t，若用戶操作與其余操作間存在先后順序，則前者的時間戳一定小于后者。并且當副本的物理時鐘為T 時，副本中存儲的所有時間戳小于或等于T 的數(shù)據(jù)條目對用戶都是可查詢的。

在使用物理時鐘時還面臨著一個嚴峻的問題——查詢放大。單個最終用戶請求在服務器中可能會轉化為許多因果關系的內部查詢，這種現(xiàn)象被稱為查詢放大[10]，尤其在服務提供商為成千上萬個用戶提供并發(fā)服務時，查詢放大的現(xiàn)象更加明顯。例如微博、Facebook 等社交系統(tǒng)中，查詢放大可能導致多達數(shù)千個針對單個最終用戶請求的內部查詢，即使系統(tǒng)中出現(xiàn)極其輕微的時鐘偏差問題，大量內部查詢累積的查詢時延也會極大地影響客戶端查詢結果中的因果一致性。

在某些情況下，在客戶端寫入新的條目時可能需要等待，如果客戶端讀取寫一個時間戳t 的鍵，則客戶端調用的任何未來寫入（PUT）操作都必須具有高于t 的時間戳，因此，客戶端需要將它已經(jīng)讀/寫的最后值的時間戳t 與PUT 操作一起發(fā)送。在寫入新值之前，接收此請求的分區(qū)將等待，直到其物理時鐘高于t。這種情況造成的時延即為客戶端的操作等待時延，在時鐘漂移或網(wǎng)絡環(huán)境造成同步不及時的方案中，操作等待時延情況尤其明顯。

在實際應用中，副本間同步的物理時鐘只能單調遞增，不能倒退回之前的某個狀態(tài)。例如，在一個由2 個數(shù)據(jù)中心A 和B 組成的系統(tǒng)中，假設2個數(shù)據(jù)中心的全局穩(wěn)定時間（GST,global stable time）都是3，這意味著2 個數(shù)據(jù)中心時間戳小于3的所有值都是可供用戶查詢的。另一種情況是假設數(shù)據(jù)中心A 中一臺服務器的物理時鐘后退到2，此時，如果客戶端在該服務器上寫入新值，該寫入操作無法在副本中進行處理，因為具有時間戳2的版本尚未到達數(shù)據(jù)中心B，但其物理時鐘為3，高于2，不同副本間就會產生矛盾，從而影響客戶端的正常服務。

GentleRain[11]為構建具有因果一致的分布式數(shù)據(jù)存儲提供了一種全新的設計模型，該模型消除了依賴項檢查消息以提高吞吐量，在通過NTP 服務器更新的物理時鐘基礎上，僅使用一個單向向量，即全局穩(wěn)定時間，來滿足用戶對因果序的要求，減少了系統(tǒng)的存儲和通信管理費用。但它的正確性都依賴于單調遞增的物理時鐘，分區(qū)之間的時鐘偏移很容易造成PUT 操作等待時間的增加，若客戶端在t時刻寫入一個鍵，則接收PUT 請求的分區(qū)需一直等待至其物理時鐘高于t，才能寫入最新值。此外，在服務器執(zhí)行完本地更新后將其發(fā)送到遠程數(shù)據(jù)中心進行異步復制的過程中，遠程客戶端需等待遠程數(shù)據(jù)中心的GST 大于本地時間戳才能查詢到該更新，這導致了系統(tǒng)中更新可見性時延的增加。

2013 年，Du 等[12]對分區(qū)數(shù)據(jù)存儲的快照隔離技術進行了研究與討論，提出了Clock-SI 模型。該模型并不是從當前系統(tǒng)中使用的集中式時間戳權限中獲取快照和提交時間戳，而是基于單純的物理時鐘進行更新。用戶通過讀取其原始分區(qū)的時鐘來獲取其快照時間戳，并在所有分區(qū)上提供與之一致的快照。與使用集中式時間戳權限相比，Clock-SI具有可用性和性能優(yōu)勢，避免了單點故障和系統(tǒng)潛在的性能瓶頸，提高了吞吐量。2016 年，Tomsic等[13]提出的PhysiCS-NMSI 方案解決了SI 在系統(tǒng)可擴展性方面的瓶頸，該方案的創(chuàng)新之處在于使用松散同步的物理時鐘來實現(xiàn)強一致性和因果一致的快照，并使用單個標量來編碼因果關系，其提交協(xié)議能有效保證用戶操作的原子性，并能避免用戶寫入沖突。

2014 年，Du 等[14]提出的Clock-RSM 是一種狀態(tài)復制因果一致性協(xié)議，該協(xié)議通過在每個分區(qū)使用松散的物理時鐘對系統(tǒng)中發(fā)出的請求進行完全排序，為跨數(shù)據(jù)中心提供了一種低時延的一致復制方案。它避免了Multi-Paxos 機制中需要單一領導者及Mencius 機制中存在時延提交的問題。但是，在同步過程中，分區(qū)之間若存在時鐘偏移，物理時鐘的特性會導致系統(tǒng)寫入或更新時產生較長的響應時間。

在分布式虛擬系統(tǒng)（DVE,distributed virtual environment）中，維護事件執(zhí)行時間的一致性是為系統(tǒng)中的所有副本提供統(tǒng)一視圖的核心元素。然而，由于網(wǎng)絡內消息傳輸時延的波動，一些事件不能在發(fā)送副本設定的預期時間內執(zhí)行，特別是當用戶事件之間因果關系較復雜時，會嚴重影響用戶在虛擬環(huán)境中的交互體驗。針對該場景，Lyu 等[15]于2017 年設計了一種基于事件之間相關因果關系的新時間戳一致性控制方案。其原理是通過在傳統(tǒng)的時間戳一致性控制方法中引入相關的因果事件檢測機制，確保可以以正確的順序處理具有因果關系的事件。通過實驗表明，該方案可以大大降低因果違規(guī)的發(fā)生概率，提高虛擬環(huán)境系統(tǒng)的可用性。

2.2 邏輯時鐘

由于不同機器上的物理時鐘通常情況下很難同步，這會導致無法區(qū)分在分布式云存儲系統(tǒng)中多個副本的事件時序。Lamport[16]在1978 年率先給出了分布式云存儲系統(tǒng)中事件發(fā)生時序問題的解決方案，提出了邏輯時鐘的概念。對于任意事件a 和b，如果a→b（“→”表示a 先于b 發(fā)生），那么C(a)＜C(b)，反之不然，因為有可能是并發(fā)事件。其中C(a)和C(b)分別表示事件a 和b 發(fā)生的時鐘狀態(tài)，即時間戳。如果C(a)=C(b)，則事件a 和b 肯定不是因果關系，所以它們之間的先后關系其實并不會影響結果，只需要通過一種確定的方式來定義它們之間的先后關系就能得到全序關系。因此，Lamport 邏輯時鐘只保證因果關系（偏序）的正確性，不保證絕對時序的正確性。該時鐘方法解決的關鍵問題是約束副本間的交互要在事件的發(fā)生順序上達成一致，而不是對于時間達成一致。邏輯時鐘就是基于此思想提出的，指的是分布式系統(tǒng)中用于區(qū)分事件發(fā)生順序的時間機制。

2.3 混合邏輯時鐘

由于邏輯時鐘不能通過C(a)和C(b)的大小推出事件a 和b 發(fā)生的先后順序，從而在使用時導致很多困擾。針對此問題，Kulkarni 等[17]提出了一種時鐘同步方法——混合邏輯時鐘（HLC,hybrid logical clock）。HLC 結合了邏輯時鐘和物理時鐘，并充分發(fā)揮了兩者的優(yōu)勢。HLC 在時間戳格式中設計了2 個分量，第一個是本地物理時鐘，第二個是邏輯關系，在提供寫入實際時間的基礎上也能提供因果序的分辨依據(jù)。

2016 年，為了改進讀寫操作響應時間過長的問題，Roohitavaf 等[18]對原GentleRain 模型進行了改進，通過使用HLC 代替物理時鐘，降低時鐘漂移對系統(tǒng)的影響，同時避免產生額外的處理開銷，即GentleRain+模型。然而，在數(shù)據(jù)中心之間的同步過程中，仍采用物理時鐘作為當前最新條目的指示器，這導致在一些慢副本存在的情況下，系統(tǒng)會產生較高的更新可見性時延。為了解決上述方案的缺陷，隨后Roohitavaf等[19]提出了CausalSpartan 模型。該模型使用HLC 作為客戶端與服務端間讀寫操作、集群副本間同步狀態(tài)的時鐘依據(jù)，結合分區(qū)間的穩(wěn)定狀態(tài)，極好地解決了因時鐘漂移與大量數(shù)據(jù)的重復讀寫造成的查詢放大情況下的時延問題。此外，類似于CausalSpartan 的Okapi 模型[20]也使用混合邏輯時鐘判別操作之間的因果序，并利用一個二元組——全局穩(wěn)定向量，追蹤當前分區(qū)最新條目與穩(wěn)定狀態(tài)。但是，該模型限制所有副本都同步更新完成后才允許查詢，因此無法避免較高的更新等待時延。

2.4 小結

時鐘同步方法基于NTP 對副本中的時間進行同步，是分布式存儲中實現(xiàn)數(shù)據(jù)一致性的重要依據(jù)。安全性方面，無論是單向標量物理時鐘還是混合邏輯時鐘，均無法避免非法第三方針對時間的攻擊，例如中間人攻擊等。

此外，在網(wǎng)絡與信息傳輸領域中的數(shù)據(jù)一致性方面，Liu 等[21]近期設計出一種實用而高效的因果一致性網(wǎng)絡領域實現(xiàn)策略——后綴因果一致性策略，采用Lamport 時間戳標記每個數(shù)據(jù)分組，每個交換機都更新該時間戳，以反映與數(shù)據(jù)分組匹配的規(guī)則。該策略通過一種管理時間戳的新方法，限制每個網(wǎng)絡更新必須涉及的交換機數(shù)量，減少了更新過程中的分組丟失，在一定程度上解決了數(shù)據(jù)傳輸過程中難以保障因果一致性的問題。

最終一致性也是分布式地理復制系統(tǒng)中的一種流行一致性模型，雖然可以提供高性能和可用性，但它可能會導致異常。會話保證方法可以消除其中的一部分異常。2019 年，Roohitavaf 等[22]對會話保證進行了改進，能夠避免在具有大量分區(qū)的系統(tǒng)中出現(xiàn)的級聯(lián)減速問題，即慢副本產生的一系列副作用；同時配合使用混合邏輯時鐘來消除寫入操作的時延，以滿足會話保證的需要。與最終一致性相比，此方案進行會話保證的開銷幾乎可以忽略不計。

3 基于地理位置的數(shù)據(jù)復制策略

分布在不同地理位置的存儲副本除了需要依據(jù)NTP 更新當前的副本時鐘外，副本之間存儲的數(shù)據(jù)也要定期進行同步。

數(shù)據(jù)復制策略包括完全地理復制和局部地理復制兩類策略。完全地理復制策略將數(shù)據(jù)存儲副本分布在其余地理位置，防止在某個副本出現(xiàn)宕機或自然災害時無法提供服務等意外情況。局部地理復制策略則規(guī)定不同副本存儲整體數(shù)據(jù)的任意子集，并且通過優(yōu)化副本之間連接方式來提供保障及時更新的數(shù)據(jù)因果一致性存儲服務。

3.1 完全地理復制策略

基于完全地理復制的策略在性能與成本之間的權衡上選擇了性能，不僅能為數(shù)據(jù)提供容災保障，更能提供高效、穩(wěn)定的因果一致性元數(shù)據(jù)存取服務。

Almeida等[23]在2013年對分布式數(shù)據(jù)庫存儲中性能、容錯和可擴展性3 個方面屬性進行了研究，并提出利用鏈復制的新變體，實現(xiàn)了較強的因果一致性的方案，該方案能夠利用多個副本的存在來均衡負載的讀取請求。與最終一致性系統(tǒng)相比，該方案避免了線性化的瓶頸，同時提供了更有競爭力的性能。與其他的因果一致性解決方案相比，鏈復制的變體能夠更有效地處理元數(shù)據(jù)信息編碼操作之間的因果依賴關系。

2015 年，Agrawal 等[24]對分布式存儲系統(tǒng)中的數(shù)據(jù)復制方法進行了詳細分類，提出了地理復制模型中的數(shù)據(jù)一致性方法。例如張倩[25]對副本間復制數(shù)據(jù)的方式進行了分析，提出一種基于網(wǎng)格來更新副本時間戳的數(shù)據(jù)復制和選擇策略，以及2 種實現(xiàn)可靠多播的方法和錯誤處理方法。顯式一致性是Valter 等[26]為地理復制服務的應用程序提出的一種一致性方案，該方案基于應用程序屬性定義，加強了最終的一致性，并保留應用程序定義的特定不變量，只要維護指定的不變量，就可以自由地對不同副本的執(zhí)行操作重新排序。

劉鑫偉[27]在2016 年提出一種基于讀寫比例的動態(tài)副本一致性策略。該方案使用定時器定時統(tǒng)計當前系統(tǒng)中的讀寫操作數(shù)，通過對寫操作的異步更新約束可以大大降低寫操作時延。

雖然基于完全地理復制策略能很大地簡化因果一致性協(xié)議的設計難度，但是該策略要求很高的存儲、帶寬和硬件成本。為了降低成本，部分學者提出了局部地理復制策略。

3.2 局部地理復制策略

局部地理復制策略中，不同的副本均作為獨立單元，每個副本存儲用戶數(shù)據(jù)的任意子集。但不同子集之間的數(shù)據(jù)如何定時同步更新，當前用戶如何對其余位置的副本數(shù)據(jù)完成存取操作都是局部地理復制策略亟待解決的問題。

在線存儲服務能夠在處于不同地理位置的數(shù)據(jù)中心之間分發(fā)和復制狀態(tài)，并將用戶請求定向到最近或負載最少的站點。雖然有效地確保了低時延響應，但是這種方法與保持副本一致是相互矛盾的，2012 年提出的紅藍一致性模型[28]則解決了此問題，該模型允許強一致操作（紅色）和最終一致操作（藍色）共存，使用一種陰影概念使系統(tǒng)能夠最大限度地使用藍色操作以及標記方法，精確確定某些操作應該分配哪個一致性級別，因此在不犧牲一致性的前提下，該方案明顯提升了地理復制策略的性能。

2012 年提出的顯式因果一致性[29]概念則對現(xiàn)有因果一致性系統(tǒng)中數(shù)據(jù)復制策略的更新可見性時延和吞吐量之間的關系進行了權衡，該類方案并不對所有潛在的因果關系進行追蹤，只主張追蹤一些相對重要數(shù)據(jù)的因果關系。顯式因果關系作為因果關系圖的一個子集，大大降低了因果關系圖的程度和深度，改善了系統(tǒng)可伸縮性的問題。采用顯式因果關系追蹤事件的一致性，減少了每次寫入操作的依賴項數(shù)量，加快了更新傳播復制的速度。

2015 年，Shen 等[30]對Full-Track 算法中更新可見性時延與因果一致性之間的關系進行了討論，并對Full-Track 算法本地日志大小和隨更新消息發(fā)送的控制消息數(shù)量進行了進一步的優(yōu)化，得到Algorithm Opt-Track 算法。同時給出了Opt-Track的一個特例，即完全復制共享內存系統(tǒng)中最優(yōu)的算法Opt-Track-crp。該算法不僅能最快地更新本地副本，而且在本地日志和更新消息中使用的控制信息的數(shù)量上也是最優(yōu)的。但是由于使用的是物理時鐘，可能會產生時鐘漂移，從而影響系統(tǒng)的性能。

此外，Hsu 等[31]對Approx-Opt-Track 算法進行了性能分析，使用仿真來分析初始credits 值與元數(shù)據(jù)大小之間的權衡關系，得到了與Opt-Track 相比，Approx-Opt-Track 在保證因果一致性的基礎上能降低性能開銷的結論。并在2018 年提出了近似因果一致性[32]的概念，以一些可能違反因果一致性的行為為代價減小元數(shù)據(jù)存儲規(guī)模。

Crain 等[33]首次提出支持部分復制的因果一致性協(xié)議，并在完全復制的情況下提供與完全復制協(xié)議相同的性能，同時最小化依賴項元數(shù)據(jù)并在部分復制情況下進行檢查，這些機制對于支持因果一致性的許多協(xié)議都是通用的。盡管此協(xié)議有助于降低在先前協(xié)議中實現(xiàn)部分復制的一些成本，但它并不能完全解決問題。由于協(xié)議使用的依賴關系表示不夠準確，可能導致錯誤的依賴關系，并且可能導致讀取過時數(shù)據(jù)。

在基于異步的SDN 傳播更新規(guī)則時，屬性的強度與由不同操作引起的復雜依賴關系之間的權衡問題，從根本上限制了SDN 的更新傳播速度。為解決此問題，F(xiàn)orster 等[34]于2016 年提出了相應的解決方案，通過構建及應用所有更新的最小依賴結構，增加了允許并發(fā)更新的數(shù)量。同時，為滿足高可用性要求，該方案避免了在鏈路狀態(tài)路由協(xié)議收斂期間丟失數(shù)據(jù)分組，并允許在一次更新中更新來自不同等級的副本。

CausalSpartan[19]方案則將用戶發(fā)出的更新請求定義為復制數(shù)據(jù)消息，與其余副本同步用戶最新的寫入/查詢（PUT/GET）操作。若當前副本在一段時間內沒有任何客戶端的讀寫操作，則將當前副本的時鐘以及最新數(shù)據(jù)封裝為狀態(tài)消息，與其余副本同步。2017 年提出的使用基于共享樹的元數(shù)據(jù)傳播技術的Saturn 模型[35]，通過管理小塊元數(shù)據(jù)即標簽，不僅加快了消息在拓撲網(wǎng)絡中的傳播速度，也能充分利用部分地理復制的成本優(yōu)勢。

針對不同數(shù)據(jù)中心的副本同步造成的性能損失，Blotter 模型[36]對弱一致性進行了約束：讀取操作只能在本地數(shù)據(jù)中心上運行，并通過精簡的消息更新操作將事務更新到副本的一個子集。在相同代碼的基礎上，Blotter 模型在數(shù)據(jù)中心規(guī)模上具有較低的開銷，同時降低了系統(tǒng)時延并提升了性能。

投機性事務復制（STR,speculative transaction replication）是一種用于部分復制地理分布數(shù)據(jù)存儲的新型投機性事務協(xié)議[37]，通過使用松散同步時鐘，避免了集中的問題。STR 通過遵循一個新的并發(fā)標準投機性快照隔離（SPSI,speculative snapshot isolation），避免了投機導致的并發(fā)異常。除了保證已提交事務的快照隔離（SI,snapshot isolation）之外，SPSI 還允許正在執(zhí)行的事務讀取在啟動前保存的數(shù)據(jù)條目，并在原子性操作約束的前提下追蹤同一副本在啟動前預保存的非沖突事務間的關系。

2018 年，Xiang 等[38]提出的部分地理復制因果一致性方案對全局穩(wěn)定方法進行了擴展，規(guī)定其中每個服務器可以存儲數(shù)據(jù)的任意子集，并且允許客戶端與服務器的任何子集進行通信，為用戶元數(shù)據(jù)提供因果一致性保障。該方案中運用到的算法極大地提高了遠程服務器中數(shù)據(jù)更新在本地可見的速度，降低了遠程更新可見時延。但是，其時間戳使用物理時鐘的方式會造成一些額外的寫入與查詢操作時延。

通過依賴時間戳對更新進行序列化的Eunomia方案[39]中，每個單獨的分區(qū)都可以為每個更新分配時間戳，而不需要與其他的分區(qū)或者Eunomia 進行同步協(xié)調，在實現(xiàn)了高并發(fā)性的同時降低了操作時延。該方案使用局部地理復制策略與局部穩(wěn)定方法解決了吞吐量和可見性時延之間的矛盾，但是在使用Eunomia 服務時，各個副本每次復制的都是完整的對象集，這就導致其不能充分利用局部地理復制策略的優(yōu)勢。

Fouto 等[40]提出基于局部地理復制策略實現(xiàn)的因果一致性方案，允許每個數(shù)據(jù)中心復制整個數(shù)據(jù)庫的不同部分。該方案使執(zhí)行操作獲得最大并行性，提高了系統(tǒng)的性能。同時，該方案通過平衡本地操作和遠程操作的方式權衡了系統(tǒng)吞吐量和數(shù)據(jù)的更新可見時延。

Karma 方案[41]的提出解決了由于擴展規(guī)模造成的可用性和時延問題，并且具有部分復制策略的成本優(yōu)勢。與之前靜態(tài)地將客戶端綁定到其關聯(lián)DC（或環(huán)）的因果一致性方案不同，Karma 允許基于可用性或時延為客戶端選擇任何副本提供服務。同時，Karma 是第一個在持久性DC 級別存儲緩存和副本之間集成因果一致性的方法。通過實驗表明，Karma 的成本遠低于完全復制的因果存儲方案，并且以相似的成本提供比上述部分復制擴展更高的可用性和更好的性能。

Xiang 等[42]受到復制共享內存系統(tǒng)（如時延復制）的啟發(fā)提出以副本為中心的因果一致性模型，副本i 發(fā)出的更新被認為與以前在該副本上應用的任何更新有因果關系，不論客戶端是否讀取之前更新的寄存器。該方案的提出解決了部分復制策略在共享寄存器的復制靈活性和跟蹤因果關系的元數(shù)據(jù)開銷之間的權衡問題。直觀地說，每個副本維護一個邊緣索引向量時間戳，該時間戳保存“共享圖”中邊緣子集的計數(shù)器，該圖描述了寄存器在副本之間如何共享。Xiang 等證明了時間戳是最優(yōu)的，分享的子集圖邊緣跟蹤的正確性是必要的。

Kalavadia 等[43]使用一種自適應分區(qū)方法，通過在副本之間復制最頻繁的模式，使系統(tǒng)適應工作負載的變化。當新三元組或屬性被添加到系統(tǒng)中時，該方案還可以通過利用主-客體連接來確保新三元組在適當分區(qū)中的適當位置，從而適應這種情況。Kalavadia 等根據(jù)現(xiàn)有的靜態(tài)分區(qū)方案，對該自適應分區(qū)方法的性能進行了評估，分析了系統(tǒng)對線性查詢、星型查詢、管理查詢、隨機查詢等不同查詢類型的性能。該方案提升了自適應分區(qū)方法的可擴展性，可根據(jù)不同的動態(tài)類別進行調整，并通過最小化副本間通信實現(xiàn)了更快的查詢執(zhí)行。雖然用于自適應分區(qū)的算法執(zhí)行時間大于靜態(tài)分區(qū)，但是對于縮放數(shù)據(jù)的靜態(tài)分區(qū)，查詢執(zhí)行時間的增長速度要快得多。與靜態(tài)分區(qū)相比，自適應分區(qū)在查詢類型上的平均速度提高了60%。

3.3 小結

數(shù)據(jù)復制策略是分布式存儲系統(tǒng)維護數(shù)據(jù)正確性的重要手段，本節(jié)綜述了地理復制方案中2 種主要的策略，即完全地理復制策略和局部地理復制策略，隨后介紹了使用該2 種策略的研究方案，其中存在的一些局限性介紹如下。

1)使用完全地理復制策略雖然有著較高的成本支出，但能提供穩(wěn)定、高效的數(shù)據(jù)一致性存儲。現(xiàn)有研究方案中副本間同步大多采用心跳機制，每次間隔固定的時間與其余副本同步當前副本最新狀態(tài)。在實際的云環(huán)境中，高效的存取服務意味著更高的性能開銷，所以心跳機制的間隔時間與性能之間的權衡問題是一個值得研究的問題。

2)局部地理復制策略中每個副本僅存儲整體數(shù)據(jù)的子集，節(jié)約了成本，但對高效的副本連接、狀態(tài)更新方式有較高的要求，所以該策略對通信、時鐘同步的性能以及系統(tǒng)吞吐量有著較高的要求。

3)副本間復制策略往往是根據(jù)分布式集群的拓撲結構，基于心跳機制，定時向相鄰副本發(fā)送更新。但該方法在副本拓撲結構非常復雜時容易造成較高的通信開銷，尤其是完全地理復制策略中，若短時間內用戶請求大量更新，在整體分布式環(huán)境中就會生成指數(shù)級的更新通信。

區(qū)塊鏈技術是一種基于拜占庭容錯（PBFT,practical Byzantine fault tolerance）機制的共識算法[44]，與數(shù)據(jù)一致性方案中副本數(shù)據(jù)復制策略方式類似，副本間對存儲的一致性數(shù)據(jù)子集進行同步的目標是使分布存儲環(huán)境內不同副本的狀態(tài)能夠達成共識。目前提出或改進的數(shù)據(jù)復制策略來滿足數(shù)據(jù)一致性的方案均存在一定的性能開銷或降低一致性約束的代價，因此借鑒優(yōu)秀的共識機制，例如區(qū)塊鏈、HashGraph 等改進副本間更新數(shù)據(jù)和達成共識的方式是數(shù)據(jù)一致性未來研究的重要方向之一。

4 客戶端和服務端操作的約束

分布式副本中存儲的因果一致性元數(shù)據(jù)，除了鍵值（K-V）條目之外，還應包含幾個屬性，例如操作時間戳、因果一致性的依賴集等。用戶對數(shù)據(jù)的操作包含2 個過程，即元數(shù)據(jù)的封裝與分析。用戶向服務副本寫入數(shù)據(jù)過程即為元數(shù)據(jù)的封裝過程，服務端對元數(shù)據(jù)進行處理后對該數(shù)據(jù)條目進行存儲。用戶向服務端查詢數(shù)據(jù)即為元數(shù)據(jù)的分析過程，除了對元數(shù)據(jù)的因果一致性進行校驗外，還要返回K-V 條目及其依賴集。

部分協(xié)議除了處理用戶的讀寫請求之外，還進行不同副本之間的狀態(tài)更新，以期達成副本最新狀態(tài)的共識，從而為如何處理用戶讀寫請求作為判斷依據(jù)。更新的結果為在每個副本維護的一組向量，即副本穩(wěn)定狀態(tài)，該向量包含副本最新時間戳或最新條目等分量，在副本穩(wěn)定狀態(tài)的時刻或之前，所有寫入的數(shù)據(jù)條目對用戶都是可查詢的。目前針對客戶端與服務端操作進行約束的方案包括兩類：設置副本穩(wěn)定狀態(tài)方案，未設置副本穩(wěn)定狀態(tài)方案。

4.1 設置副本穩(wěn)定狀態(tài)

GentleRain+[18]基于GentleRain，使用其中單調的物理時鐘作為分配操作時間戳的依據(jù)，在存在時鐘偏移的情況下依然能提供正確的因果一致性服務。該模型中副本間最新狀態(tài)是依據(jù)副本中的物理時鐘進行判別的，雖然能提供正確的存取服務，但無法避免時鐘漂移等風險造成的寫入、更新時延。同樣使用物理時鐘判別因果序的還有樂觀的因果一致性（OCC,optimistic causal consistency）[2]協(xié)議，該協(xié)議中遠程數(shù)據(jù)中心的更新可以立即對本地數(shù)據(jù)中心中的客戶端可見。OCC為每個服務器都配備了一個物理時鐘用來提供單調增加的時間戳，以此來傳遞不同副本間的因果一致性。

為了提升在分區(qū)之間存在時鐘時延和查詢放大的情況下數(shù)據(jù)因果一致性方案的性能表現(xiàn)，2017年提出的CasusalSpartan 模型[19]定義了全新的分區(qū)穩(wěn)定向量（DSV,data center stable vector），在分區(qū)中單個查詢被放大成許多個內部查詢的情況下，能為用戶提供可靠的寫入和查詢服務，降低了客戶端的更新等待時間。

圖2 和圖3 分別為CausalSpartan 模型和Okapi模型中的PUT 和GET 操作。CasusalSpartan 模型中在客戶端設計了一組客戶端數(shù)據(jù)的依賴集時間向量，用戶向服務端發(fā)送讀寫請求時都將該向量作為客戶端依賴依據(jù)；同時，依據(jù)服務端響應消息更新本地數(shù)據(jù)時，更新該向量。此外，CasusalSpartan模型中還對服務端與其余副本更新狀態(tài)的消息進行了劃分，即復制消息和狀態(tài)消息。但該模型是在理想情況下實現(xiàn)的，并未提出對第三方篡改等風險的應對策略。

圖2 PUT 過程

圖3 GET 過程

與CasusalSpartan 模型類似，Okapi 模型[20]使用了HLC 和全局穩(wěn)定向量（GSV,global stable vector）的因果一致性協(xié)議，該協(xié)議設定一個GSV 來追蹤當前分區(qū)最新條目的時間戳。與CasusalSpartan模型相似的是，它們都對客戶端、服務端中數(shù)據(jù)的處理步驟進行了約束，但Okapi 模型中提出了一個滿足多項查詢的方法，允許用戶在查詢請求向量中發(fā)送多個鍵K{k1,k2,…,kn}值，并且在服務端對其處理，同時返回K 對應的值V{v1,v2,…,vn}及其對應的依賴集。但該模型要求，只有所有副本都同步完用戶更新后，才允許用戶查詢，這個約束造成Okapi的更新可見性時延變得很高。

在分區(qū)間設置副本穩(wěn)定狀態(tài)的目的是為分布式環(huán)境中不同副本的數(shù)據(jù)一致性約束提供判別依據(jù)，即保證分布式系統(tǒng)集群中所有節(jié)點的數(shù)據(jù)同步一致并且能夠對某個提案達成共識。區(qū)塊鏈共識算法結合密碼學技術，可以保證交易的可追溯性、不可篡改性、不可否認性和不可偽造性[45]，如工作量證明（PoW,proof of work）、權益證明（PoS,proof of stake）等均為傳統(tǒng)的區(qū)塊鏈數(shù)據(jù)一致性共識算法。2013 年8 月，比特股（Bitshares）項目基于PoS 算法提出了授權股份證明算法（DPoS,delegated proof of stake），該算法的基本思路類似于“董事會決策”，即系統(tǒng)中每個節(jié)點可以將其持有的股份權益作為選票授予一個代表，獲得票數(shù)最多且愿意成為代表的前N 個節(jié)點將進入“董事會”，按照既定的時間表輪流對交易進行打包結算并且簽署（即生產）新區(qū)塊。此外，2016 年提出的Bitcoin-NG[46]將時間切分為不同的時間段，在每一個時間段上由一個領導者負責生成區(qū)塊并將交易打包，并引入了2 種不同的區(qū)塊——用于選舉領導者的關鍵區(qū)塊和包含交易數(shù)據(jù)的微區(qū)塊，進而保障不同角色區(qū)塊之間的數(shù)據(jù)一致性共識。

基于拜占庭容錯的共識算法也是共識算法研究中的熱點問題，如 CDBFT（credit-delegated Byzantine fault tolerance）[47]依據(jù)信用情況為區(qū)塊分配是否可信的身份，并定期執(zhí)行身份檢查。該算法可以長期保持節(jié)點的良好信用狀態(tài)，從而提高消除惡意節(jié)點、提高系統(tǒng)節(jié)點間達成數(shù)據(jù)一致性共識的效率。

近年來，針對區(qū)塊鏈共識算法的改進研究越來越深入，其中較有代表性的是基于有向無環(huán)圖（DAG,directed acyclic graph）、HashGraph 的分布式賬本技術。2020 年，高政風等[48]對基于DAG 的分布式賬本共識機制進行了研究，并將其分為3 類，1)通過最大權重子樹選舉主鏈的主干鏈DAG 共識協(xié)議；2)每個節(jié)點均維護一條本地信息鏈的平行鏈DAG 共識協(xié)議；3)基于投票機制達成共識的樸素DAG 共識協(xié)議。

采用心跳機制、副本狀態(tài)時間戳更新等方法在分布式數(shù)據(jù)一致性方案中設置副本穩(wěn)定狀態(tài)，不僅能夠降低時間開銷，而且能為節(jié)點間共識提供判別依據(jù)。借鑒主鏈、平行鏈DAG 分布式賬本共識算法及區(qū)塊鏈算法改進數(shù)據(jù)一致性共識機制、副本狀態(tài)同步及數(shù)據(jù)更新過程是分布式數(shù)據(jù)一致性未來的重要研究方向之一。

4.2 未設置副本穩(wěn)定狀態(tài)

對于副本是否穩(wěn)定的判別方法除了在每個副本維護穩(wěn)定狀態(tài)變量外，還可以持續(xù)跟蹤用戶讀取的值來更新分區(qū)狀態(tài)，如2011 年提出的COPS[49]模型與2013 年提出的Orbe[50]模型，當客戶端為某個鍵寫入新的值時，模型就會將客戶端讀過的所有值都視為該客戶端正在寫入的新值的因果依賴關系。而每個副本中存在多個分區(qū)，所以每個分區(qū)都要發(fā)送同步請求到其他分區(qū)來檢查依賴關系。這種明確的依賴關系跟蹤對于同步消息中的消息復雜度要求極高，導致分區(qū)間通信開銷很大。

為本地對象的讀取和更新提供即時且一致的響應的典型方案還有2015 年提出的SwiftCloud 模型[51]，不僅能在保證因果一致性的前提下支持客戶端的快速讀寫，而且能夠保證服務器端有較高的吞吐量。此外，該模型還減小了元數(shù)據(jù)的規(guī)模，在3個數(shù)據(jù)中心的情況下，其連接的客戶端可以很容易地擴展到上千臺。但是該模型只適用于理想環(huán)境中，并未對實際應用中需要面對的身份認證、數(shù)據(jù)篡改等安全風險提出相應的保護機制。2018 年，Roohitavaf 等[52]對副本中鍵值條目的可查詢狀態(tài)與數(shù)據(jù)一致性的關系進行了研究，并提出一種對數(shù)據(jù)條目的向量與副本所在分組進行動態(tài)跟蹤的方案，這種靈活性使應用程序能夠在不同的目標之間自由權衡，并為不同的應用程序提供不同的視圖，從而使每個應用程序獲得最佳性能。

4.3 小結

對用戶操作與副本中的同步時鐘方法進行優(yōu)化，是降低時延、解決時間同步風險的高效方法。而針對數(shù)據(jù)因果一致性中客戶端、服務端處理數(shù)據(jù)的步驟進行約束，是提升性能、降低查詢放大等情況造成的時延的重要手段。本節(jié)通過對是否標識副本穩(wěn)定狀態(tài)的不同研究方案進行綜述，總結了現(xiàn)有經(jīng)典方案中對客戶端、服務端進行約束以保證因果一致性的幾種方法，但其中存在一定的局限性，介紹如下。

1)設計客戶端、服務端保障因果一致性的操作步驟是降低操作時延、更新等待時間的必要手段。但在一致性元數(shù)據(jù)封裝與分析過程中增加操作步驟無疑會帶來更高的性能開銷，結合身份認證、時鐘方法優(yōu)化客戶端與服務端間的操作是一個值得研究的課題。

2)服務器副本間同步最新狀態(tài)過程中，除了最新寫入的數(shù)據(jù)條目外，還應包含副本最新時鐘信息，因此相比于單純地使用時鐘信息做額外副本狀態(tài)信息的方案，同時處理數(shù)據(jù)與時鐘狀態(tài)的方案會有較高的性能消耗。如何在服務端之間同步數(shù)據(jù)過程中對副本狀態(tài)進行標識是數(shù)據(jù)因果一致性研究中的熱點課題。

3)對客戶端、服務端之間存取數(shù)據(jù)的步驟進行數(shù)據(jù)因果一致性約束，是針對數(shù)據(jù)處理過程中的細粒度操作。但該類方案在實際的云環(huán)境中存在數(shù)據(jù)篡改、身份冒用等風險時無法提供數(shù)據(jù)完整性保障，例如CausalSpartan、Okapi 等方案中，客戶端依據(jù)收到的響應消息更新自身依賴集，該響應消息作為唯一依據(jù)，無法保證傳遞消息內容是否完整，因此客戶端、服務端也就不能提供準確可靠的因果一致性存取服務。

4)與區(qū)塊鏈共識算法在區(qū)塊鏈接、同步的過程中采用不同機制進行同步以達成共識的過程相似，數(shù)據(jù)因果一致性模型中對數(shù)據(jù)副本進行同步為用戶數(shù)據(jù)及其因果序提供一致性約束，也是為了在分布式集群中將不同副本同步為一個共識形態(tài)。但區(qū)塊鏈共識機制往往是基于更高風險的復雜環(huán)境，需使用密碼學加密并提供工作量或權益等證明機制以降低安全風險，而現(xiàn)有的數(shù)據(jù)一致性研究方案中鮮有對因果一致性提出安全保障的方案。但實際的云環(huán)境中存在大量病毒、非法第三方等不安全因素。因此，應考慮風險環(huán)境、用戶操作不可信等因素，對客戶端、副本進行安全認證，例如結合密碼學、可信認證、身份認證機制等設計安全約束。

目前的研究成果大多專注于降低性能開銷與操作時延，但存在完整性、安全等方面的局限性，如用戶一般將關鍵數(shù)據(jù)分散地存儲在云存儲節(jié)點上，而存儲節(jié)點可能遭到破壞或者竊聽，在實際應用中，由于云存儲用戶不會在本地保存副本，就失去了對數(shù)據(jù)的直接管理和控制。分布式存儲數(shù)據(jù)主要面臨數(shù)據(jù)破壞、云服務商惡意隱瞞以及用戶隱私泄露等安全威脅，對用戶數(shù)據(jù)、云服務商的一致性約束造成影響。對客戶端、服務端的因果一致性操作進行序列化也是為處理用戶請求的過程設計因果一致性約束的方法之一，具體在第5 節(jié)中進行介紹。

5 操作事務的序列化

分布式存儲系統(tǒng)中，用戶的讀寫操作、客戶端的讀寫操作必須由系統(tǒng)分配一個序列來執(zhí)行。當一個客戶端對一個數(shù)據(jù)條目進行了更新或者寫入操作時，其余的客戶端同時來讀取這個條目，就會造成該條目的更新查詢丟失問題。若數(shù)據(jù)條目在被處理的過程中分布式系統(tǒng)設置鎖機制，只對當前客戶端提供讀寫權限，即對分布式存儲系統(tǒng)的操作事務進行序列化，就可避免丟失更新或臟數(shù)據(jù)等風險的出現(xiàn)。

2015 年，事務存儲器的概念由Dziuma 等[53]首次提出，規(guī)定用戶只能讀取已處理事務寫完的數(shù)據(jù)條目。數(shù)據(jù)一致性一直是分布式存儲系統(tǒng)中的一個熱點話題，設計一致性約束下的事務序列化模型尤其重要。Viotti 等[54]劃分和總結了事務型數(shù)據(jù)庫和非事務型數(shù)據(jù)庫中的數(shù)據(jù)一致性定義。RedBlue[55]一致性模型將操作集分為強一致性和弱一致性這2種情形，約束強操作、增加弱操作空間，并使不同類型的操作選擇不同的一致性級別，從而降低系統(tǒng)時延。Andrea 等[56]通過設計一個保證一致性操作的原子可見性的框架，規(guī)定某一事務的全部更新必須對其他副本明顯可見。

為使事務性存儲系統(tǒng)開銷更小，2018 年，Zhang等[57]提出一個消除復制協(xié)議中一致性的新方法，同時仍然為應用程序提供分布式事務的強一致性，即不一致復制的事務應用程序協(xié)議（TAPIR,transactional application protocol for inconsistent replication），這是第一個使用新型復制協(xié)議的事務協(xié)議，稱為不一致復制，它提供了非一致性下的容錯性。該方案通過僅在事務協(xié)議中強制執(zhí)行強一致性的約束，可以在單次查詢操作中提交分布式事務并在沒有中央?yún)f(xié)調者的情況下對其進行排序。與傳統(tǒng)系統(tǒng)相比，TAPIR 能提供更低的時延和更好的吞吐量。

為在上述所提方法的基礎上實現(xiàn)一種高可用的事務協(xié)議，Cure 模型[58]通過一個交互式的事務接口來保證因果一致性和支持CRDT（conflictfree replicated data type），在保持高度可用性的同時實現(xiàn)了最強大的語義。此外，它采用了存有每個數(shù)據(jù)中心條目的矢量時鐘，實現(xiàn)了對因果一致性更準確的追蹤，雖降低了更新可見性時延，但是由于需要管理大量元數(shù)據(jù)而增加了計算和存儲開銷，進一步犧牲了吞吐量。為確保事務的原子可見性，Bailis 等[59]提出了一種新的數(shù)據(jù)一致性事務讀取模型——原子讀取隔離模型。該模型保證事務更新完成后才對其余事務可見，但在系統(tǒng)中存在較高爭用請求的情況下，模型會造成額外的性能開銷。

為解決只讀事務算法的性能和可見性時延之間存在的權衡問題，SNOW（Strict serializability,Non-blocking operations,One-response from each shard,and compatibility with conflicting Write transactions）定理[60]指出，只讀事務算法不可能提供所有4 個理想的屬性：嚴格的串行性、非阻塞操作、每個切分只有一次響應以及與沖突寫事務的兼容性。其中與性能相關的屬性是嚴格的串行性（一致性的最強形式）和與沖突寫事務的兼容性（表明系統(tǒng)中還有哪些其他類型的事務）。該方案雖然使用其他3 個屬性不可能實現(xiàn)嚴格的串行化，但是可以實現(xiàn)一個稍微弱一些的一致性模型，稱為流程順序串行化，并將其定義為SNOW 最優(yōu)性，作為檢查現(xiàn)有系統(tǒng)并確定其只讀事務的時延是否可以改進的強有力依據(jù)。Saturn[35]是一種依靠元數(shù)據(jù)來傳遞因果序的數(shù)據(jù)一致性協(xié)議，該協(xié)議向每個數(shù)據(jù)中心提供一個追蹤因果一致性的序列化標簽。此外，它還使用了一組合作的序列化器件來加快標簽在拓撲網(wǎng)絡中的傳播速度，使在地理上彼此接近的2 個數(shù)據(jù)中心之間快速地建立起元路徑傳播路徑。此協(xié)議在保證吞吐量的前提下也能實現(xiàn)良好的更新可見性，同時可以充分利用部分地理復制的成本優(yōu)勢。

為允許應用程序通過分片有效地在復制站點內實現(xiàn)擴展，Wren[61]模型在保證因果一致性的同時，通過為每個數(shù)據(jù)中心安裝一個快照實現(xiàn)了事務的非阻塞讀操作，該快照是由本地數(shù)據(jù)中心的每個分區(qū)安裝的一個新的因果快照和一個客戶端緩存組成。該模型不考慮系統(tǒng)的規(guī)模，而僅僅使用2 個標量時間戳來跟蹤因果性，一個時間戳跟蹤本地項的依賴關系，另一個時間戳跟蹤遠程項的依賴關系。與之前的設計相比，2 個標量時間戳大大提高了存取效率和可擴展性。但是，由于時間戳的選取問題，增加了更新可見時延。

2018 年，Didona 等[62]指出“時延最優(yōu)”只讀事務會在寫操作上帶來額外的開銷，這種開銷非常高，甚至在以讀為主的工作負載中也降低性能表現(xiàn)。并且提出了實現(xiàn)“近似時延最優(yōu)”的只讀事務協(xié)議，但不會增加由時延最優(yōu)協(xié)議引起的任何開銷。該協(xié)議是非阻塞的，并且針對單條數(shù)據(jù)條目、需要兩輪客戶端和服務器之間的通信。但該協(xié)議中時延最優(yōu)的只讀事務對寫施加的額外開銷是固有的不可避免的，并且這種開銷隨著客戶端數(shù)量的增加而呈線性增長趨勢。

為減少時鐘偏移對現(xiàn)有的事務模型造成的影響，Roohitavaf 等[63]在CausalSpartan 模型的基礎上設計了CausalSpartanX 模型，該模型提供了一種非阻塞的因果一致性只讀事務，只需要在客戶端和服務器之間進行一輪通信，并且與事務無關分區(qū)的慢化也不會影響事務的響應時間。無論讀寫事務是否涉及慢副本，這種改進都非常有意義，能有效地降低響應時間和時延。

操作事務的序列化方案參考了關系型數(shù)據(jù)庫中事務的原子性，在用戶批量的請求到達服務端請求處理時，對操作進行原子性約束，并進行序列化。本節(jié)對不同方案中將事務序列化來保障數(shù)據(jù)因果一致性的方法進行了綜述，與在客戶端、服務端設計滿足因果一致性約束操作的方案類似，在事務的序列化研究方案中大多集中于對數(shù)據(jù)一致性與性能之間的權衡問題上，對實際環(huán)境中的安全風險鮮有考慮。

在相關技術方面也有商業(yè)化產品面市，如滿足數(shù)據(jù)一致性約束的商業(yè)化數(shù)據(jù)庫產品之一MongoDB，其中設計了讀寫鎖機制來保障，即通過寫關注（write concern）、讀關注（read concern）和讀優(yōu)先（read preference）機制來為用戶操作的事務提供序列化約束。MongoDB 客戶端利用會話的概念捕獲因果關系，并將操作時間戳作為判別因果序的依據(jù)，不同客戶端也可以共享其余客戶端的因果序令牌，從而為不同線程中的副本和用戶提供高效的因果一致性約束。

6 未來研究展望

本文主要圍繞數(shù)據(jù)因果一致性的最新研究內容展開綜述，介紹了近年來具有代表性的因果一致性模型。通過分析可以看出，現(xiàn)有數(shù)據(jù)存儲中對因果一致性的保障仍然存在一些不足，未來的科研工作可以更多地關注以下幾點。

1)因果一致性時鐘同步方法中，使用物理時鐘容易受到時鐘異常的影響，但混合邏輯時鐘結合了物理時鐘和邏輯時鐘兩者，主要的局限性介紹如下。

①單純的物理時鐘同步方法僅需對時間戳標量進行校驗，混合邏輯時鐘除了對物理時鐘進行校驗外還需要對邏輯時鐘進行校驗，造成一定的性能開銷。

② 若因果一致性協(xié)議單純依靠時鐘來分辨因果序，在系統(tǒng)中存在病毒、身份驗證信息漏洞等風險時，NTP 可能會被破壞，從而影響系統(tǒng)可用性。針對時鐘同步過程中的安全風險，結合密碼學設計時間戳信息可信傳輸、時鐘信息的安全驗證等方法應是未來研究工作的重要方向之一。

③雖然HLC 減小了與真實時鐘間的差距，但混合邏輯時鐘中單純依據(jù)邏輯時鐘修正物理環(huán)境中的漂移具有一定的不確定性。結合更多時鐘依賴向量、更安全的時鐘信息約束來保證分區(qū)間時鐘同步的準確性應是未來研究的關鍵方向之一。

2)基于地理位置的復制策略中，完全地理復制要求較高的成本，而局部地理復制策略則對通信、性能開銷有著極高的要求，兩者的局限性介紹如下。

①局部地理復制策略中每個副本僅存儲整體數(shù)據(jù)的子集，副本之間只能通過優(yōu)化的拓撲結構及與高頻率的更新和轉發(fā)來保證數(shù)據(jù)因果一致性。因此，對局部復制策略的優(yōu)化研究還有很大的研究空間，如對副本數(shù)據(jù)子集更新規(guī)模與數(shù)據(jù)更新間隔之間的權衡，結合數(shù)據(jù)操作事務的序列化方案優(yōu)化事務的原子性約束。

② 心跳機制的間隔、副本數(shù)據(jù)復制消息的內容關乎分布式存儲系統(tǒng)的更新可見速度，因此，基于實際環(huán)境中不同用戶的需求，對副本數(shù)據(jù)復制消息內容和心跳機制進行優(yōu)化，為分布式存儲設計更高效、低性能的因果一致性約束，應是未來研究的關鍵。

3)對客戶端操作、服務端處理操作的過程進行約束的方案是從通信與元數(shù)據(jù)格式轉換的角度對數(shù)據(jù)因果一致性提供操作保障的。但該類方案通常從發(fā)送請求與處理請求的角度出發(fā)，存在以下幾個方面的局限性。

①結合時鐘同步方法對副本的最新狀態(tài)進行標識、用戶發(fā)送請求與處理請求過程中都對依賴集進行更新均有較大的性能開銷，因此未來研究重點要著重于設計低時延、低開銷的因果一致性協(xié)議。

② 現(xiàn)有研究方案極少對實際環(huán)境中的安全風險進行討論，后續(xù)研究的重點應集中在結合密碼技術、可信認證機制對副本、客戶端的操作設計安全約束等方面。

③在安全風險方面，尚未提出對因果一致性存儲的身份認證、權限控制以及結合數(shù)據(jù)完整性約束的方案，復雜的云環(huán)境導致目前的數(shù)據(jù)因果一致性方案實用性較差，未來工作應多關注于安全約束下的因果一致性研究。

4)依據(jù)CAP 定理對事務進行序列化的方案通過對數(shù)據(jù)庫操作事務進行約束，為分布式存儲系統(tǒng)中副本與客戶端的操作提供了數(shù)據(jù)因果一致性的保障，但對事務的完整驗證、完全和部分地理復制策略中數(shù)據(jù)操作事務提供不同程度的一致性約束等工作有待進一步深入。

綜上，為全面降低分布式存儲中的操作時延、更新時延、成本和性能開銷，提升因果一致性存儲的安全程度，應該將優(yōu)化時鐘同步方法，為數(shù)據(jù)同步、元數(shù)據(jù)存取事務和副本狀態(tài)同步方法設計安全約束等方面的研究方法進行結合。目前研究通常專注于數(shù)據(jù)因果一致性中某個特定的需求，例如性能、成本，并為此提出大量的優(yōu)化方案。然而，針對每個需求分別提出的優(yōu)化方案在實際應用中的可行性較差，而且在單獨部署的同時也極有可能引入額外的安全風險。因此，未來研究的首要任務是設計全面完整的安全解決方案，以滿足實際云存儲面臨的多樣需求。

7 結束語

低廉的存儲成本與高效的通信傳輸促使大數(shù)據(jù)存儲產業(yè)蓬勃發(fā)展給大數(shù)據(jù)存儲環(huán)境中的時鐘同步、數(shù)據(jù)復制及事務序列化技術也帶來了特有的性能和安全問題。特別是時鐘同步方法、元數(shù)據(jù)存取間的因果一致性約束，引起了人們對數(shù)據(jù)因果一致性的普遍關注。通過深入分析與對比可知，數(shù)據(jù)因果一致性工作在國內外已取得較好的研究成果，但是仍有許多遺留問題尚待探討，需要綜合考慮多種因素，不斷優(yōu)化數(shù)據(jù)存取、同步策略，加強安全約束。本文重點介紹了分布式數(shù)據(jù)存儲中4 類影響數(shù)據(jù)因果一致性的影響因素及其特點，然后分別圍繞時鐘同步、數(shù)據(jù)復制、元數(shù)據(jù)存取和事務序列化展開綜述，以期能夠為數(shù)據(jù)因果一致性的未來研究做出一些有益的探索。