數(shù)據(jù)因果一致性研究綜述

田俊峰，王彥骉，何欣楓，張俊濤，楊萬(wàn)賀，龐亞南

（1.河北大學(xué)網(wǎng)絡(luò)空間安全與計(jì)算機(jī)學(xué)院，河北 保定 071002；2.河北省高可信信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，河北 保定 071002）

1 引言

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

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

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

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

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

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

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

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

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

2 副本間的時(shí)鐘同步

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

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

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

2.1 物理時(shí)鐘

物理時(shí)鐘方案使用單向標(biāo)量來(lái)檢查依賴(lài)關(guān)系，通過(guò)提供因果一致性的快照，來(lái)保證用戶(hù)寫(xiě)入事件滿(mǎn)足原子性，從而避免寫(xiě)入等待沖突。當(dāng)副本處理新的用戶(hù)操作時(shí)，依據(jù)當(dāng)前副本的物理時(shí)鐘為該操作分配一個(gè)時(shí)間戳t，若用戶(hù)操作與其余操作間存在先后順序，則前者的時(shí)間戳一定小于后者。并且當(dāng)副本的物理時(shí)鐘為T(mén) 時(shí)，副本中存儲(chǔ)的所有時(shí)間戳小于或等于T 的數(shù)據(jù)條目對(duì)用戶(hù)都是可查詢(xún)的。

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

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

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

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

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

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

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

2.2 邏輯時(shí)鐘

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

2.3 混合邏輯時(shí)鐘

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

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

2.4 小結(jié)

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

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

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

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

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

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

3.1 完全地理復(fù)制策略

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

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

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

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

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

3.2 局部地理復(fù)制策略

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 小結(jié)

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

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

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

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

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

4 客戶(hù)端和服務(wù)端操作的約束

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

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

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

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

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

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

圖2 PUT 過(guò)程

圖3 GET 過(guò)程

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

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

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

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

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

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

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

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

4.3 小結(jié)

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

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

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

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

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

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

5 操作事務(wù)的序列化

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

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

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

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

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

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

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

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

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

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

6 未來(lái)研究展望

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

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

①單純的物理時(shí)鐘同步方法僅需對(duì)時(shí)間戳標(biāo)量進(jìn)行校驗(yàn)，混合邏輯時(shí)鐘除了對(duì)物理時(shí)鐘進(jìn)行校驗(yàn)外還需要對(duì)邏輯時(shí)鐘進(jìn)行校驗(yàn)，造成一定的性能開(kāi)銷(xiāo)。

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

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

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

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

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

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

①結(jié)合時(shí)鐘同步方法對(duì)副本的最新?tīng)顟B(tài)進(jìn)行標(biāo)識(shí)、用戶(hù)發(fā)送請(qǐng)求與處理請(qǐng)求過(guò)程中都對(duì)依賴(lài)集進(jìn)行更新均有較大的性能開(kāi)銷(xiāo)，因此未來(lái)研究重點(diǎn)要著重于設(shè)計(jì)低時(shí)延、低開(kāi)銷(xiāo)的因果一致性協(xié)議。

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

③在安全風(fēng)險(xiǎn)方面，尚未提出對(duì)因果一致性存儲(chǔ)的身份認(rèn)證、權(quán)限控制以及結(jié)合數(shù)據(jù)完整性約束的方案，復(fù)雜的云環(huán)境導(dǎo)致目前的數(shù)據(jù)因果一致性方案實(shí)用性較差，未來(lái)工作應(yīng)多關(guān)注于安全約束下的因果一致性研究。

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

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

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

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