田俊峰，楊萬賀，龐亞南，張俊濤

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

1 引言

云存儲是當(dāng)今互聯(lián)網(wǎng)服務(wù)的重要組成部分[1]。為了給用戶提供高效率和可擴(kuò)展的服務(wù)，云存儲采取分布式數(shù)據(jù)存儲方式，將數(shù)據(jù)中心部署在不同位置實(shí)現(xiàn)大數(shù)據(jù)存儲，數(shù)據(jù)中心之間的數(shù)據(jù)一致性成為保證數(shù)據(jù)可用的關(guān)鍵[2]。

數(shù)據(jù)一致性一般分為強(qiáng)一致性和弱一致性[3]。在理想情況下，對任何數(shù)據(jù)的更新在其所有副本中立即可見稱為強(qiáng)一致性。強(qiáng)一致性雖然有簡單的語義，但是引發(fā)了高時(shí)延和不允許網(wǎng)絡(luò)分區(qū)現(xiàn)象；多個(gè)節(jié)點(diǎn)的狀態(tài)沒有充分同步但仍可以處理讀寫操作稱為弱一致性。弱一致性對數(shù)據(jù)的及時(shí)更新沒有要求，難以為用戶提供最新的數(shù)據(jù)[4]。因果一致性是介于強(qiáng)一致性和弱一致性中間的協(xié)議[5]，既可以有效解決高時(shí)延和網(wǎng)絡(luò)分區(qū)等問題，也能保證數(shù)據(jù)的及時(shí)更新。

目前，基于因果一致性協(xié)議的模型成為構(gòu)建地理復(fù)制數(shù)據(jù)存儲中有吸引力的模型[6]。在地理復(fù)制數(shù)據(jù)存儲中，分布在不同地理位置的數(shù)據(jù)中心通過網(wǎng)絡(luò)時(shí)鐘協(xié)議（NTP,network time protocol）更新當(dāng)前的節(jié)點(diǎn)時(shí)鐘，不同數(shù)據(jù)中心利用數(shù)據(jù)復(fù)制策略完成數(shù)據(jù)同步[7]。Agrawal 等[8]對分布式存儲系統(tǒng)中的數(shù)據(jù)復(fù)制策略進(jìn)行了分類，詳細(xì)闡述了地理復(fù)制模型中的數(shù)據(jù)一致性方法，數(shù)據(jù)復(fù)制策略分為完全復(fù)制策略和部分復(fù)制策略。

基于完全復(fù)制策略的因果一致性模型要求每個(gè)數(shù)據(jù)中心都存儲完整的數(shù)據(jù)集，本地?cái)?shù)據(jù)中心寫入數(shù)據(jù)需要向其他所有遠(yuǎn)程數(shù)據(jù)中心同步數(shù)據(jù)[9]。例如，文獻(xiàn)[10]模型在完全復(fù)制策略的基礎(chǔ)上，僅依靠單一標(biāo)量時(shí)間戳實(shí)現(xiàn)對因果關(guān)系的追蹤。文獻(xiàn)[11]提出通用穩(wěn)定向量和混合邏輯時(shí)鐘相結(jié)合的全局穩(wěn)定策略，提高了模型的吞吐量。文獻(xiàn)[12]提出數(shù)據(jù)中心穩(wěn)定向量和混合邏輯時(shí)鐘相結(jié)合的全局穩(wěn)定策略，解決了操作時(shí)延問題，降低了數(shù)據(jù)的更新可見時(shí)延。但數(shù)據(jù)中心穩(wěn)定向量中的條目包含所有數(shù)據(jù)中心，增加了元數(shù)據(jù)開銷，數(shù)據(jù)中心之間的同步開銷大。

隨著數(shù)據(jù)中心存儲的數(shù)據(jù)量迅速增長，為降低數(shù)據(jù)中心之間的同步開銷，基于部分復(fù)制策略的因果一致性模型得到了廣泛應(yīng)用[13]?；诓糠謴?fù)制策略的因果一致性模型要求每個(gè)數(shù)據(jù)中心存儲完整數(shù)據(jù)集的子集，本地?cái)?shù)據(jù)中心寫入數(shù)據(jù)僅需向部分遠(yuǎn)程數(shù)據(jù)中心同步新數(shù)據(jù)。文獻(xiàn)[14]模型中的每個(gè)數(shù)據(jù)中心都設(shè)置序列化器，利用時(shí)間戳對操作進(jìn)行序列化，實(shí)現(xiàn)了操作的高并發(fā)性，并降低了操作時(shí)延。但是，該模型取消了數(shù)據(jù)中心之間的全局穩(wěn)定。文獻(xiàn)[15]模型利用共享樹表示數(shù)據(jù)中心之間的拓?fù)潢P(guān)系和部分元數(shù)據(jù)作為標(biāo)簽，數(shù)據(jù)中心之間的所有更新操作都通過共享樹和標(biāo)簽實(shí)現(xiàn)，提高了數(shù)據(jù)的可見性和系統(tǒng)的吞吐量，但是造成了數(shù)據(jù)中心之間的元數(shù)據(jù)傳播開銷。Xiang 等[16]提出的模型是對數(shù)據(jù)中心之間的全局穩(wěn)定方法進(jìn)行擴(kuò)展，利用全局穩(wěn)定時(shí)間戳和物理時(shí)鐘的全局穩(wěn)定策略實(shí)現(xiàn)模型的全局穩(wěn)定性。該模型降低了元數(shù)據(jù)開銷，提高了系統(tǒng)的吞吐量，但會產(chǎn)生操作時(shí)延，從而造成較高的更新可見時(shí)延。

為了有效降低操作時(shí)延并權(quán)衡元數(shù)據(jù)傳播開銷和遠(yuǎn)程更新可見性能，本文提出一種基于共享圖和部分復(fù)制策略的分布式存儲因果一致性模型（CCSGPR,causal consistent model for distributed data stores based on shared graph and partial replication strategy），利用共享圖表述數(shù)據(jù)中心之間的拓?fù)潢P(guān)系，通過共享穩(wěn)定向量和混合邏輯時(shí)鐘相結(jié)合的全局穩(wěn)定策略實(shí)現(xiàn)因果一致性。本文主要工作如下。

1) CCSGPR 使用部分復(fù)制策略實(shí)現(xiàn)分布式數(shù)據(jù)存儲，每個(gè)數(shù)據(jù)中心存放完整數(shù)據(jù)集的子集，利用共享圖表示數(shù)據(jù)中心之間的鄰接關(guān)系，元數(shù)據(jù)通過同步消息和心跳信息傳播，僅需在有鄰接關(guān)系的部分?jǐn)?shù)據(jù)中心傳播，降低元數(shù)據(jù)傳播開銷和數(shù)據(jù)遠(yuǎn)程更新可見時(shí)延。

2) 提出一種全局穩(wěn)定策略，該策略使用混合邏輯時(shí)鐘標(biāo)記操作的時(shí)間戳，可為新數(shù)據(jù)標(biāo)記滿足因果依賴關(guān)系的混合邏輯時(shí)間戳，避免寫入數(shù)據(jù)操作時(shí)延。同時(shí)，在混合邏輯時(shí)鐘的基礎(chǔ)上提出了共享穩(wěn)定向量，該向量僅由2 個(gè)時(shí)間戳構(gòu)成，這降低了元數(shù)據(jù)開銷，通過選取遠(yuǎn)程數(shù)據(jù)中心中時(shí)間戳的最小值為遠(yuǎn)程更新穩(wěn)定的界限，避免讀取數(shù)據(jù)操作時(shí)延。

2 背景介紹

2.1 基于部分復(fù)制策略的分布式模型

分布式模型采取多版本鍵值存儲方式，一個(gè)鍵對應(yīng)一個(gè)版本鏈，版本鏈包含鍵的多個(gè)版本，每個(gè)版本又包括鍵對應(yīng)的值和元數(shù)據(jù)，寫（PUT）操作會為鍵的版本鏈增加一個(gè)新版本，模型定期處理版本鏈中的舊版本[17]，數(shù)據(jù)存放在不同的數(shù)據(jù)中心，用戶可以在不同的數(shù)據(jù)中心完成數(shù)據(jù)的寫入、更新或下載[18]?；诓糠謴?fù)制策略的分布式模型如圖1 所示。由圖1 可知，完整數(shù)據(jù)集被分為m個(gè)子集，每個(gè)數(shù)據(jù)中心存儲完整數(shù)據(jù)集的子集；每個(gè)數(shù)據(jù)中心由n個(gè)分區(qū)（服務(wù)器）構(gòu)成，所存儲的數(shù)據(jù)子集根據(jù)哈希函數(shù)按鍵分配到n個(gè)分區(qū)。服務(wù)器完成寫入數(shù)據(jù)操作后，為對應(yīng)的鍵創(chuàng)建一個(gè)新版本，新版本僅需同步到部分?jǐn)?shù)據(jù)中心，數(shù)據(jù)中心之間通過點(diǎn)對點(diǎn)FIFO（first in first out）通道進(jìn)行通信。

基于部分復(fù)制策略的分布式模型包含以下2 個(gè)基本操作。

1) PUT→(k,v)。PUT 操作將值v賦給鍵k標(biāo)識的數(shù)據(jù)。若鍵k標(biāo)識的數(shù)據(jù)存在，創(chuàng)建一個(gè)值為v的新版本；否則，創(chuàng)建一個(gè)鍵為k且初始值為v的新數(shù)據(jù)。

圖1 基于部分復(fù)制策略的分布式模型

2) val←GET（k）。GET 操作返回鍵k標(biāo)識的數(shù)據(jù)的值v，返回的值v需滿足因果一致性。

2.2 因果一致性

因果一致性根據(jù) 2 個(gè)操作之間的happens-before 關(guān)系[19]定義，要求服務(wù)器返回的值與因果關(guān)系定義的順序一致。對于2 個(gè)任意操作a1和a2，若滿足以下條件，稱a1因果依賴于a2，記作a1→a2。

1)a1和a2是同一線程中的操作，a1發(fā)生在a2之前。

2)a1為寫數(shù)據(jù)操作，a2為讀數(shù)據(jù)操作，且a2讀a1寫的值。

3) 存在其他操作a3，其中a1→a3，a3→a2。

定義1數(shù)據(jù)穩(wěn)定性。若鍵k標(biāo)識的數(shù)據(jù)可以被客戶端c讀取，且該數(shù)據(jù)的依賴項(xiàng)也可被客戶端c讀取，則稱該數(shù)據(jù)具有穩(wěn)定性。

定義2全局穩(wěn)定性。分布式存儲模型劃定一個(gè)時(shí)間戳界限，該時(shí)間戳范圍內(nèi)的所有數(shù)據(jù)都具有穩(wěn)定性，則稱分布式存儲模型在該時(shí)間戳具有全局穩(wěn)定性。

定義3更新可見時(shí)延。鍵k標(biāo)識的數(shù)據(jù)在其原始數(shù)據(jù)中心寫入的時(shí)刻到該數(shù)據(jù)在此數(shù)據(jù)中心具有穩(wěn)定性的時(shí)刻間隔稱為更新可見時(shí)延。

定義4并發(fā)操作。存在2 個(gè)操作a1和a2，若a1既不因果依賴于a2，a2也不因果依賴于a1，則稱a1和a2為并發(fā)操作。

定義5沖突操作及其處理規(guī)則。若a1和a2是對鍵k標(biāo)識的同一數(shù)據(jù)進(jìn)行并發(fā)寫操作，則稱a1和a2為沖突操作。沖突操作造成鍵k標(biāo)識的同一數(shù)據(jù)產(chǎn)生2 個(gè)相互沖突的版本，相互沖突的版本按照不同的順序同步到遠(yuǎn)程數(shù)據(jù)中心，這會造成數(shù)據(jù)中心之間的不一致性問題?；诓糠謴?fù)制策略的分布式模型使用最后更新為準(zhǔn)（last-writer-wins）規(guī)則[20]處理數(shù)據(jù)的沖突操作。該規(guī)則規(guī)定，對于鍵k標(biāo)識的同一數(shù)據(jù)的2 個(gè)寫入操作，規(guī)定時(shí)間戳大的操作為后發(fā)生的，從而寫入的值為時(shí)間戳大的操作所確定的值，若2 個(gè)操作的時(shí)間戳相等，則通過數(shù)據(jù)的寫入數(shù)據(jù)中心ID 來解決沖突。

3 共享圖

共享圖（shared graph）是無權(quán)無向圖，由頂點(diǎn)的有窮非空集合和頂點(diǎn)之間邊的集合組成，記作Gs=（Vs,Es），其中Vs={1,2,3,...,n}為頂點(diǎn)集合；Es為邊的集合，包含實(shí)線邊和虛線邊2 種，實(shí)線邊集合記作E1（Gs），虛線邊集合記作E2（Gs）。CCSGPR使用共享圖表述分布式結(jié)構(gòu)，頂點(diǎn)i∈Vs代表數(shù)據(jù)中心i；若數(shù)據(jù)中心i和數(shù)據(jù)中心j存在共享鍵，則存在實(shí)線邊（i,j）∈E1（Gs），若存在客戶端c可以訪問數(shù)據(jù)中心i和數(shù)據(jù)中心j，則存在虛線邊（i,j）∈E2（Gs）。

Ni表示與數(shù)據(jù)中心i存在實(shí)線連接的數(shù)據(jù)中心集合；Pi表示與數(shù)據(jù)中心i存在虛線連接的數(shù)據(jù)中心集合；Ki表示存儲在數(shù)據(jù)中心i的鍵的集合；Kij=Ki∩Kj表示數(shù)據(jù)中心i和數(shù)據(jù)中心j的共享鍵。數(shù)據(jù)中心鄰接關(guān)系的共享圖如圖2 所示。由圖2 可知，共享圖Gs由i、V1、V2、V3、V4、V5頂點(diǎn)組成，2 個(gè)數(shù)據(jù)中心的共享鍵標(biāo)記在圖中的實(shí)線邊上，存在客戶端c可以訪問數(shù)據(jù)中心i、V2、V3和V5，因此，頂點(diǎn)i、V2、V3和V5之間存在虛線邊，如Ni={V1,V4}，Pi={V2,V3,V5}，。

圖2 數(shù)據(jù)中心鄰接關(guān)系的共享圖

在部分復(fù)制數(shù)據(jù)存儲中，每個(gè)數(shù)據(jù)中心只存放完整數(shù)據(jù)集的任意子集，本文利用共享圖表述數(shù)據(jù)中心之間的鄰接關(guān)系，取消數(shù)據(jù)中心之間額外的同步開銷，本地?cái)?shù)據(jù)中心i寫入新數(shù)據(jù)僅需向Ni集合中其他遠(yuǎn)程數(shù)據(jù)中心發(fā)送數(shù)據(jù)同步消息和心跳信息，若數(shù)據(jù)中心i存儲的子集不包含待讀取的數(shù)據(jù)，則向Pi集合中其他數(shù)據(jù)中心發(fā)送遷移操作。元數(shù)據(jù)利用數(shù)據(jù)同步消息和心跳信息實(shí)現(xiàn)傳播，通過共享圖拓?fù)浣Y(jié)構(gòu)，元數(shù)據(jù)不需要傳播到所有的數(shù)據(jù)中心，同時(shí)，允許不同數(shù)據(jù)中心的服務(wù)器之間直接傳播數(shù)據(jù)同步消息和心跳信息，降低元數(shù)據(jù)同步開銷，以提供高吞吐量并降低遠(yuǎn)程更新可見時(shí)延。

4 全局穩(wěn)定策略

目前，基于部分復(fù)制策略的因果一致性模型取消了傳統(tǒng)的依賴項(xiàng)檢查信息，通過NTP 實(shí)現(xiàn)服務(wù)器的同步，并利用全局穩(wěn)定時(shí)間戳（GST,global stable timestamp）和物理時(shí)鐘相結(jié)合的全局穩(wěn)定策略實(shí)現(xiàn)模型的全局穩(wěn)定性（見2.2 節(jié)的定義2）。

較目前的因果一致性模型，CCSGPR 提出了一種共享穩(wěn)定向量和混合邏輯時(shí)鐘相結(jié)合的全局穩(wěn)定策略。首先，CCSGPR 用混合邏輯時(shí)鐘（HLC,hybrid logical clock）代替物理時(shí)鐘來跟蹤時(shí)間的進(jìn)展，完成時(shí)間戳的更新?；旌线壿嫊r(shí)鐘結(jié)合了物理時(shí)鐘和邏輯時(shí)鐘[21]，其時(shí)間戳t由一個(gè)物理組件t.p和一個(gè)邏輯組件t.l 組成，記作，其中t.p 是操作發(fā)生的物理時(shí)鐘值，t.l 是追蹤因果關(guān)系的計(jì)數(shù)器。因此，混合邏輯時(shí)鐘充分發(fā)揮了兩者的優(yōu)勢，既包含物理時(shí)鐘自發(fā)遞增的優(yōu)點(diǎn)，也包含邏輯時(shí)鐘易追蹤因果關(guān)系的優(yōu)點(diǎn)。在分布式模型中，由于距離差異等原因會造成節(jié)點(diǎn)之間存在一定的時(shí)鐘偏差，存在2個(gè)PUT操作e1和e2，若e1“happens-before”e2，則e2因果依賴e1，受時(shí)鐘偏差的影響，e2的時(shí)間戳小于e1的時(shí)間戳。為保證上述PUT 操作滿足因果性，使用物理時(shí)鐘的因果一致性模型發(fā)生操作阻塞，等待e2的物理時(shí)鐘超過e1的時(shí)間戳，造成PUT 操作時(shí)延。CCSGPR 中e2不需要阻塞等待，直接完成操作并為e2標(biāo)記te1.p

其次，記某數(shù)據(jù)的寫入時(shí)間戳為t，因果一致性模型全局穩(wěn)定的界限為T，規(guī)定僅當(dāng)t

CCSGPR 在共享圖拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上，利用混合邏輯時(shí)鐘有效避免了寫操作時(shí)延，同時(shí)，共享穩(wěn)定向量僅包含2 個(gè)時(shí)間戳，其根據(jù)選取最小值的原則，避免了讀取操作時(shí)延，降低了元數(shù)據(jù)開銷和數(shù)據(jù)中心之間的同步開銷。

5 CCSGPR 協(xié)議

CCSGPR 協(xié)議是在分布式存儲中穩(wěn)定運(yùn)行的通信協(xié)議，在操作滿足因果一致性要求的前提下，為用戶提供安全快速的寫入、查詢和存儲服務(wù)。

5.1 元數(shù)據(jù)

圖3 CCSGPR 中數(shù)據(jù)中心之間的心跳同步

元數(shù)據(jù)是描述數(shù)據(jù)屬性的信息，用來支持歷史數(shù)據(jù)、資源查找、文件記錄、指示存儲位置等功能，元數(shù)據(jù)開銷和效率是衡量系統(tǒng)性能的重要指標(biāo)，如Facebook 中，元數(shù)據(jù)比數(shù)據(jù)本身大，大型元數(shù)據(jù)會增加通信和存儲開銷[22]。分布式模型中，采取多版本鍵值存儲方式，用d表示元組，該元組包括，其中，k是標(biāo)識鍵唯一的ID；v是鍵對應(yīng)的值；ut 是鍵的更新時(shí)間，即該數(shù)據(jù)的寫入時(shí)間戳；sr 是d的源副本，即創(chuàng)建d的數(shù)據(jù)中心ID。

客戶端c維持SSVc，SSVc僅由2 個(gè)時(shí)間戳組成。客戶端c還維持依賴向量（DV,dependency vector）DVc，存儲遠(yuǎn)程數(shù)據(jù)中心的依賴項(xiàng)，以保證后續(xù)操作滿足因果一致性。

5.2 操作

CCSGPR 協(xié)議中包含6 個(gè)基本操作：GET 操作、PUT 操作、數(shù)據(jù)同步操作、更新共享穩(wěn)定向量操作、心跳機(jī)制操作和遷移操作。

5.2.1 GET 操作

客戶端c發(fā)起讀取數(shù)據(jù)操作，存儲該數(shù)據(jù)的服務(wù)器響應(yīng)操作，如算法1 所示。其具體流程如下，客戶端c發(fā)起請求，其中k為待讀取數(shù)據(jù)的鍵，服務(wù)器接收到請求后，為確保安裝最新快照使用SSVc更新。服務(wù)器選擇鍵k的版本鏈中最新數(shù)據(jù)的版本，其中版本是本地?cái)?shù)據(jù)中心寫入或遠(yuǎn)程數(shù)據(jù)中心寫入且更新時(shí)間戳小于中的時(shí)間戳。服務(wù)器把最新、鍵k對應(yīng)版本的值v、源副本sr 和鍵k對應(yīng)版本的更新時(shí)間戳ut 以GETREPLY 消息格式返回客戶端c。客戶端c接收GETREPLY 消息后，通過maxDV算法用更新時(shí)間戳ut 和源副本sr 更新DVc，用更新SSVc。

算法1數(shù)據(jù)中心m中客戶端c的操作

5.2.2 PUT 操作

客戶端c發(fā)起寫數(shù)據(jù)操作，服務(wù)器響應(yīng)寫操作，如算法2 所示。其具體流程為，客戶端c發(fā)起請求，其中k為待寫入數(shù)據(jù)的鍵，v為鍵對應(yīng)的值，DVc為依賴向量，記錄客戶端c的依賴項(xiàng)。服務(wù)器接收寫數(shù)據(jù)請求后，用DVc值更新，使用update clock 算法（算法3 中的update clock on PUT 算法）更新，保證PUT操作滿足因果關(guān)系。服務(wù)器為數(shù)據(jù)k的版本鏈中創(chuàng)建一個(gè)新版本，該版本的鍵為k，鍵對應(yīng)的值為v，鍵對應(yīng)的更新時(shí)間戳ut 為，鍵對應(yīng)的源副本sr 為該數(shù)據(jù)中心的ID。服務(wù)器把最新、鍵k對應(yīng)的更新時(shí)間戳ut 和源副本sr 以PUTREPLY 消息格式返回客戶端c。同理，客戶端c接收PUTREPLY 消息后，通過maxDV 算法用更新時(shí)間戳ut 和源副本sr 更新DVc，用更新SSVc。

算法2服務(wù)器響應(yīng)客戶端c的請求操作

5.2.3 數(shù)據(jù)同步操作

分布式存儲系統(tǒng)由不同節(jié)點(diǎn)（數(shù)據(jù)中心）協(xié)同為用戶提供存儲、查詢服務(wù)的平臺，所以服務(wù)器完成PUT 操作后，其他數(shù)據(jù)中心要同步最新數(shù)據(jù)，即本地?cái)?shù)據(jù)中心i寫入新數(shù)據(jù)后，需向Ni集合中的數(shù)據(jù)中心發(fā)送同步數(shù)據(jù)信息。服務(wù)器間的數(shù)據(jù)同步如圖4 所示。由圖4 可知，數(shù)據(jù)中心i中的服務(wù)器發(fā)送Replicate 消息到其他數(shù)據(jù)中心（算法2 中的Replicate 算法），Ni集合中的數(shù)據(jù)中心接收Replicate消息后，服務(wù)器將數(shù)據(jù)的新版本增加到該數(shù)據(jù)的版本鏈中，更新其PV 中服務(wù)器對應(yīng)的條目，即設(shè)置，完成服務(wù)器間的數(shù)據(jù)同步。

圖4 服務(wù)器間的數(shù)據(jù)同步

5.2.4 更新共享穩(wěn)定向量操作

一個(gè)數(shù)據(jù)中心內(nèi)的服務(wù)器定期更新全局穩(wěn)定向量SSV，規(guī)定每過θ時(shí)間間隔（θ的具體時(shí)間在仿真實(shí)驗(yàn)中設(shè)置），服務(wù)器之間彼此共享其分區(qū)向量PV，并計(jì)算SSV 為所有服務(wù)器的分區(qū)向量PV中的最小值（算法3 的更新共享穩(wěn)定向量算法），從而確保該數(shù)據(jù)中心數(shù)據(jù)穩(wěn)定界限內(nèi)的數(shù)據(jù)在所有服務(wù)器內(nèi)可讀。

5.2.5 心跳機(jī)制操作

算法3服務(wù)器的時(shí)鐘管理和心跳機(jī)制操作

5.2.6 遷移操作

如算法2 所示，客戶端c發(fā)起讀取數(shù)據(jù)操作，數(shù)據(jù)中心m作為響應(yīng)客戶端c操作的本地?cái)?shù)據(jù)中心，若數(shù)據(jù)中心m存儲的數(shù)據(jù)子集不包含待讀取的數(shù)據(jù)，則根據(jù)共享圖表示的數(shù)據(jù)中心之間的鄰接關(guān)系，向Pm集合中其他數(shù)據(jù)中心發(fā)送遷移操作，完成讀取數(shù)據(jù)操作。其具體流程為，數(shù)據(jù)中心m的服務(wù)器向Pm集合中的數(shù)據(jù)中心發(fā)送遷移操作請求，包括數(shù)據(jù)中心的ID 和；數(shù)據(jù)中心i中的服務(wù)器響應(yīng)遷移操作請求，更新其共享穩(wěn)定向量，完成遷移操作。

6 仿真實(shí)驗(yàn)與結(jié)果分析

6.1 對比分析

本節(jié)對現(xiàn)有的因果一致性模型進(jìn)行對比分析，表1 為各因果一致性模型的比較。文獻(xiàn)[10]模型和文獻(xiàn)[11]模型基于完全復(fù)制策略，較文獻(xiàn)[10]模型，文獻(xiàn)[11]模型使用混合邏輯時(shí)鐘與通用穩(wěn)定向量相結(jié)合的全局穩(wěn)定策略，降低了操作時(shí)延，但增加了元數(shù)據(jù)開銷。文獻(xiàn)[10]模型和文獻(xiàn)[16]模型都使用物理時(shí)鐘與全局穩(wěn)定時(shí)間戳相結(jié)合的全局穩(wěn)定策略，較文獻(xiàn)[10]模型，文獻(xiàn)[16]模型使用部分復(fù)制策略，有效降低了遠(yuǎn)程更新可見時(shí)延，但操作時(shí)延仍然較高。CCSGPR 基于部分復(fù)制策略，使用混合邏輯時(shí)鐘與共享穩(wěn)定向量相結(jié)合的全局穩(wěn)定策略，在保證元數(shù)據(jù)開銷小的基礎(chǔ)上，有效降低了操作時(shí)延，定量對比結(jié)果詳見以下實(shí)驗(yàn)內(nèi)容。

6.2 仿真實(shí)驗(yàn)設(shè)置

CCSGPR 使用Java 實(shí)現(xiàn)，采用Berkeley DB 進(jìn)行鍵值數(shù)據(jù)的存儲和檢索。Berkeley DB 數(shù)據(jù)庫是以key-value 為結(jié)構(gòu)的嵌入式數(shù)據(jù)庫，既有關(guān)系型數(shù)據(jù)庫中的完整 ACID（Atomicity,Consistency,Isolation,Durability）事務(wù)語義支持，也提供NoSQL中簡單的數(shù)據(jù)庫編程接口。為驗(yàn)證本文所提方法的有效性，在數(shù)據(jù)一致性HBU-Cluster 平臺上實(shí)現(xiàn)分布式鍵值存儲仿真實(shí)驗(yàn)，并與經(jīng)典的基于完全復(fù)制策略文獻(xiàn)[11]模型和基于部分復(fù)制策略文獻(xiàn)[16]模型進(jìn)行實(shí)驗(yàn)對比。數(shù)據(jù)一致性HBU-Cluster 平臺是項(xiàng)目組為因果一致性測試設(shè)計(jì)的仿真平臺，該平臺為分布式鍵值存儲管理框架，使用Google 的Protocol Buffer將數(shù)據(jù)因果一致性協(xié)議結(jié)構(gòu)化，并集成Yahoo的YCSB（Yahoo! Cloud Serving Benchmark）基準(zhǔn)測試模塊作為性能測試工具。仿真實(shí)驗(yàn)中服務(wù)器的配置是Windows10 x64，Intel Core i5-4590，3.3 GHz，16.00 GB 內(nèi)存，256 GB 固態(tài)磁盤存儲。根據(jù)現(xiàn)有模型的性能測試，仿真實(shí)驗(yàn)采取傳統(tǒng)的測試方法從模型吞吐量、操作響應(yīng)時(shí)間和遠(yuǎn)程更新可見時(shí)延3 個(gè)方面進(jìn)行定性對比。

根據(jù)實(shí)際基于Internet 的應(yīng)用設(shè)置，在仿真實(shí)驗(yàn)中設(shè)置默認(rèn)參數(shù)如下：數(shù)據(jù)中心數(shù)目為4，分區(qū)數(shù)目為6，讀寫比例為3:1?？蛻舳艘罁?jù)uniform 記錄選擇策略訪問分區(qū)數(shù)據(jù)，服務(wù)器之間采取NTP同步方法，每次實(shí)驗(yàn)前都同步時(shí)鐘。CCSGPR 中的混合邏輯時(shí)間戳使用64 位編碼，其中48 位設(shè)置為物理部分，16 位設(shè)置為邏輯部分，通過這些設(shè)置，混合時(shí)間戳可以編碼多達(dá)216個(gè)邏輯事件，可以跟蹤到微秒的物理時(shí)間，有效避免了由于邏輯部分已經(jīng)達(dá)到最大值，但又必須增加其邏輯部分以保證因果一致性導(dǎo)致分區(qū)發(fā)生的阻塞等待。規(guī)定分區(qū)之間每5 ms 交換分區(qū)向量PV，若分區(qū)在1 ms 內(nèi)未接收更新數(shù)據(jù)操作和同步數(shù)據(jù)操作，則該分區(qū)接收心跳信息。

6.3 吞吐量

吞吐量是單位時(shí)間內(nèi)模型更新鍵值的總量，是衡量模型性能的一項(xiàng)重要指標(biāo)。本節(jié)實(shí)驗(yàn)采取分別增加數(shù)據(jù)中心和分區(qū)數(shù)目的傳統(tǒng)實(shí)驗(yàn)方式評估模型的吞吐量性能。

首先，分析數(shù)據(jù)中心數(shù)對模型吞吐量的影響，控制分區(qū)變量，設(shè)置每個(gè)數(shù)據(jù)中心的分區(qū)數(shù)為6，客戶端向本地?cái)?shù)據(jù)中心發(fā)送讀寫請求，數(shù)據(jù)中心之間定期同步數(shù)據(jù)。圖5(a)描述了數(shù)據(jù)中心數(shù)2～12 所對應(yīng)吞吐量的變化情況，隨著數(shù)據(jù)中心數(shù)的增加，文獻(xiàn)[11]模型的吞吐量變化明顯，而文獻(xiàn)[16]模型和CCSGPR模型的吞吐量變化較小。其原因是文獻(xiàn)[11]模型基于完全復(fù)制策略，數(shù)據(jù)中心增加導(dǎo)致數(shù)據(jù)同步開銷增大，從而降低了模型的吞吐量。文獻(xiàn)[16]模型和CCSGPR 基于部分復(fù)制策略，僅模型中的部分?jǐn)?shù)據(jù)中心同步數(shù)據(jù)，模型的吞吐量變化不大。當(dāng)數(shù)據(jù)中心數(shù)為8 時(shí)，CCSGPR 比文獻(xiàn)[11]模型提高了23.47%的吞吐量性能，比文獻(xiàn)[16]模型提高了14.43%。與文獻(xiàn)[11]模型相比，文獻(xiàn)[16]模型和CCSGPR 使用部分復(fù)制策略，提高了模型的吞吐量。與文獻(xiàn)[16]模型相比，CCSGPR 的全局穩(wěn)定策略中使用混合邏輯時(shí)鐘避免了操作時(shí)延，實(shí)現(xiàn)了更高的吞吐量。

表1 不同因果一致性模型的比較

其次，分析分區(qū)數(shù)對模型吞吐量的影響，控制數(shù)據(jù)中心數(shù)變量，設(shè)置數(shù)據(jù)中心數(shù)為4，改變數(shù)據(jù)中心的分區(qū)數(shù)量。圖5(b)描述了分區(qū)數(shù)2～32 對應(yīng)吞吐量的變化情況，隨著分區(qū)數(shù)的增加，模型的吞吐量呈上升趨勢，吞吐量性能提高了18.93%。與文獻(xiàn)[11]模型和文獻(xiàn)[16]模型比，CCSGPR 利用共享圖表述數(shù)據(jù)中心之間的鄰接關(guān)系，其分區(qū)向量PV 僅存儲具有鄰接關(guān)系的部分?jǐn)?shù)據(jù)中心元數(shù)據(jù)，元數(shù)據(jù)通過同步消息傳播，降低了元數(shù)據(jù)開銷，實(shí)現(xiàn)了吞吐量的提升。

6.4 操作響應(yīng)時(shí)間

根據(jù)傳統(tǒng)測試操作響應(yīng)時(shí)間的實(shí)驗(yàn)方式，本節(jié)實(shí)驗(yàn)分兩部分來測量模型操作的響應(yīng)時(shí)間，第一部分分區(qū)之間不設(shè)置時(shí)鐘偏差，通過改變數(shù)據(jù)中心分區(qū)數(shù)的方式觀察模型操作響應(yīng)時(shí)間的變化情況；第二部分在一臺物理設(shè)備上部署2 個(gè)虛擬服務(wù)器，以循環(huán)方式發(fā)送2 000 個(gè)操作請求，人為地控制服務(wù)器之間的時(shí)鐘偏差值，準(zhǔn)確分析服務(wù)器之間的時(shí)鐘偏差對操作響應(yīng)時(shí)間的影響。

圖5 不同數(shù)據(jù)中心數(shù)和不同分區(qū)數(shù)的吞吐量

圖6 不同分區(qū)數(shù)和不同時(shí)鐘偏差的操作響應(yīng)時(shí)間

圖6(a)描述了模型中操作響應(yīng)時(shí)間隨分區(qū)數(shù)的變化情況，圖6(b)描述了模型中操作響應(yīng)時(shí)間隨分區(qū)之間的時(shí)鐘偏差值的變化情況。隨著分區(qū)數(shù)和分區(qū)之間的時(shí)鐘偏差值的增加，模型的操作響應(yīng)時(shí)間也會增加，與文獻(xiàn)[11]模型和CCSGPR 相比，文獻(xiàn)[16]模型的全局穩(wěn)定策略中使用物理時(shí)鐘，受分區(qū)之間的時(shí)鐘偏差影響大，產(chǎn)生了較高的操作時(shí)延。文獻(xiàn)[11]模型和CCSGPR 的全局穩(wěn)定策略中使用混合邏輯時(shí)鐘，當(dāng)分區(qū)之間存在時(shí)鐘偏差時(shí)，可為操作提供符合因果依賴關(guān)系的時(shí)間戳，有效避免了操作時(shí)延。與文獻(xiàn)[11]模型比，CCSGPR 的分區(qū)向量中僅同步共享圖Ni集合中的數(shù)據(jù)中心所對應(yīng)分區(qū)的元數(shù)據(jù)，受分區(qū)總數(shù)目變化影響較小，其共享穩(wěn)定向量規(guī)定選取遠(yuǎn)程數(shù)據(jù)中心中時(shí)間戳的最小值，劃定數(shù)據(jù)可讀的下限，降低了11.72%操作響應(yīng)時(shí)間。

6.5 遠(yuǎn)程更新可見時(shí)延

遠(yuǎn)程更新可見性時(shí)延指的是本地?cái)?shù)據(jù)中心寫入的數(shù)據(jù)同步到遠(yuǎn)程數(shù)據(jù)中心的時(shí)間間隔，在衡量模型性能中也占據(jù)著重要地位，即使只有幾毫秒的時(shí)延，也會導(dǎo)致讀取錯誤的過時(shí)數(shù)據(jù)而造成異常。

遠(yuǎn)程更新可見性時(shí)延是由服務(wù)器接收的最小時(shí)鐘值決定，首先通過人為地控制服務(wù)器之間的時(shí)鐘偏差值的方式，分析時(shí)鐘偏差對遠(yuǎn)程更新可見時(shí)延的影響。其次服務(wù)器之間不設(shè)置時(shí)鐘偏差，增加模型中數(shù)據(jù)中心數(shù)目，觀察遠(yuǎn)程更新可見時(shí)延的變化情況。

圖7(a)描述了遠(yuǎn)程更新可見時(shí)延隨時(shí)鐘偏差值的變化情況，圖7(b)描述了遠(yuǎn)程更新可見時(shí)延隨數(shù)據(jù)中心數(shù)目的變化情況。結(jié)果表明，遠(yuǎn)程更新可見性時(shí)延受服務(wù)器之間的時(shí)鐘偏差影響，隨時(shí)鐘偏差值呈線性增長，其節(jié)點(diǎn)接收心跳信息值的數(shù)量隨數(shù)據(jù)中心數(shù)線性增加，遠(yuǎn)程更新可見時(shí)延也會增加。與文獻(xiàn)[11]模型比，文獻(xiàn)[16]模型和CCSGPR 基于部分復(fù)制策略，遠(yuǎn)程更新僅在部分?jǐn)?shù)據(jù)中心之間同步，降低了遠(yuǎn)程更新可見時(shí)延。較文獻(xiàn)[16]模型，CCSGPR 降低了28.57%的遠(yuǎn)程更新可見時(shí)延。文獻(xiàn)[11]模型中使用通用穩(wěn)定向量UST，一個(gè)數(shù)據(jù)中心對應(yīng)向量中的一個(gè)時(shí)間戳，遠(yuǎn)程更新規(guī)定所有遠(yuǎn)程數(shù)據(jù)中心都完成同步才可見，模型的遠(yuǎn)程更新可見性時(shí)延取決于本地?cái)?shù)據(jù)中心同步到所有遠(yuǎn)程數(shù)據(jù)中心的時(shí)間，受數(shù)據(jù)中心數(shù)影響較大。文獻(xiàn)[16]模型中使用全局穩(wěn)定時(shí)間戳GST，模型的遠(yuǎn)程更新可見性時(shí)延取決于本地?cái)?shù)據(jù)中心（即數(shù)據(jù)寫入的數(shù)據(jù)中心）同步到其時(shí)延最大的數(shù)據(jù)中心的時(shí)間，數(shù)據(jù)中心數(shù)的增加會產(chǎn)生更小的全局穩(wěn)定時(shí)間戳，從而造成遠(yuǎn)程更新可見時(shí)延增加。CCSGPR 中使用SSV，向量中僅包括本地?cái)?shù)據(jù)中心的時(shí)間戳t1和遠(yuǎn)程數(shù)據(jù)中心的時(shí)間戳t2，模型的遠(yuǎn)程更新可見性時(shí)延取決于本地?cái)?shù)據(jù)中心i與共享圖Ni集合中數(shù)據(jù)中心同步的時(shí)間。由于CCSGPR 模型其SSV 中遠(yuǎn)程數(shù)據(jù)中心時(shí)間戳t2的選取最小值原則，隨著數(shù)據(jù)中心數(shù)的增大，CCSGPR 的遠(yuǎn)程更新可見時(shí)延會略高于文獻(xiàn)[16]模型。

圖7 不同時(shí)鐘偏差和不同數(shù)據(jù)中心數(shù)的遠(yuǎn)程更新可見時(shí)延

7 結(jié)束語

本文提出了基于共享圖和部分復(fù)制策略的分布式存儲因果一致性模型CCSGPR，該模型以部分復(fù)制策略為前提，利用共享圖表示數(shù)據(jù)中心間的鄰接關(guān)系。此外，利用混合邏輯時(shí)鐘標(biāo)記符合因果關(guān)系的時(shí)間戳，共享穩(wěn)定向量選取遠(yuǎn)程數(shù)據(jù)中心心跳時(shí)間戳的最小值作為數(shù)據(jù)穩(wěn)定的下限，以降低操作時(shí)延。通過數(shù)據(jù)一致性平臺對CCSGPR 進(jìn)行吞吐量、操作響應(yīng)時(shí)間和遠(yuǎn)程更新可見時(shí)延驗(yàn)證，在降低操作響應(yīng)時(shí)間的同時(shí)，權(quán)衡了遠(yuǎn)程更新可見性能和元數(shù)據(jù)開銷。但CCSGPR 未考慮敏感數(shù)據(jù)惡意篡改等安全問題，實(shí)現(xiàn)可信約束下的分布式存儲因果一致性模型是未來要做的工作。