沈佳杰，盧修文,2,3，向 望，趙澤宇，王 新,2,3

(1.復旦大學校園信息化辦公室，上海 200433；2.復旦大學計算機科學技術學院，上海 200433；3.復旦大學上海市智能信息處理重點實驗室，上海 200433)

1 引言

分布式存儲系統(tǒng)[1]廣泛使用讀寫一致性算法來保證數(shù)據(jù)可用性。通過使用特定的協(xié)議，分布式存儲系統(tǒng)保證了用戶讀寫數(shù)據(jù)的一致性。經(jīng)典拜占庭問題[2]存在數(shù)據(jù)篡改[3]的情況，而讀寫一致性問題假定所有節(jié)點都會遵守通信協(xié)議傳輸用戶數(shù)據(jù)[4]。與此同時，通過部署讀寫一致性算法，分布式存儲系統(tǒng)能避免在部分節(jié)點失效情況下出現(xiàn)服務中斷的問題，從而有效提升存儲數(shù)據(jù)的可用性[5]。

然而，讀寫一致性算法通常會帶來較大的網(wǎng)絡通信和存儲開銷[4]，并降低分布式存儲系統(tǒng)中用戶數(shù)據(jù)訪問的能力。開發(fā)人員研發(fā)分布式存儲系統(tǒng)的過程中需部署滿足存儲應用場景需求的讀寫一致性算法，并調(diào)整該算法執(zhí)行機制。但是，根據(jù)應用場景選擇適用的讀寫一致性算法依然具有很大的挑戰(zhàn)性。

首先，各種讀寫一致性算法通常采用不同實現(xiàn)機制，需要綜合分析在目標應用場景中部署特定算法的合理性。其次，由于讀寫一致性算法的數(shù)據(jù)寫入操作性能受到數(shù)據(jù)量和網(wǎng)絡狀態(tài)等多種因素的影響，需適應目標應用場景的讀寫請求特性和網(wǎng)絡條件。最后，部署讀寫一致性算法的過程中需要充分了解不同應用場景的特點，并相應地調(diào)整算法的執(zhí)行機制。

為了幫助開發(fā)人員選擇適合特定應用場景的讀寫一致性算法，本文總結(jié)了主流讀寫一致性算法實現(xiàn)方案，綜述了分布式存儲系統(tǒng)中讀寫一致性算法的實現(xiàn)機制，分析了這些實現(xiàn)機制對數(shù)據(jù)讀寫操作性能的影響，總結(jié)了在各種存儲應用場景中部署讀寫一致性算法需注意的要點，主要包括以下內(nèi)容：

(1)介紹了讀寫一致性算法常見的實現(xiàn)機制。本文總結(jié)了讀寫一致性算法主要的實現(xiàn)方案，并歸納了這些實現(xiàn)方案的優(yōu)缺點，總結(jié)了這些算法適用的應用場景。在此基礎上，本文分析了分布式存儲系統(tǒng)中部署讀寫一致性算法的關鍵問題，總結(jié)了分布式存儲系統(tǒng)中讀寫一致性算法對這些問題的解決方法。

(2)綜述了讀寫一致性算法性能優(yōu)化工作。由于副本和糾刪碼作為主要的數(shù)據(jù)可靠性保障機制被廣泛部署到分布式存儲系統(tǒng)，本文綜述了針對這2種存儲機制構建的讀寫一致性算法，比較了這些算法的存儲開銷、容錯性能和存儲機制等特性。

(3)總結(jié)了在不同數(shù)據(jù)存儲應用場景中部署讀寫一致性算法需注意的要點。在綜述算法實現(xiàn)方案的基礎上，本文分析了單數(shù)據(jù)中心分布式存儲系統(tǒng)和跨數(shù)據(jù)中心云際存儲系統(tǒng)2種經(jīng)典應用場景中制約執(zhí)行效率的因素，展望了未來分布式存儲系統(tǒng)中讀寫一致性算法性能優(yōu)化工作的研究方向，給出了可能的解決方案。

2 讀寫一致性問題及挑戰(zhàn)

本節(jié)將介紹讀寫一致性問題、部署讀寫一致性算法的目標和面臨的挑戰(zhàn)。

2.1 讀寫一致性問題

分布式存儲系統(tǒng)廣泛存在節(jié)點失效和網(wǎng)絡故障，讀寫一致性算法需要保證在部分節(jié)點和網(wǎng)絡功能失效的情況下數(shù)據(jù)的可用性。不同于拜占庭問題[2]存在數(shù)據(jù)篡改[3]的情況，讀寫一致性問題假設分布式存儲系統(tǒng)滿足以下條件：

(1)所有的存儲節(jié)點都有可能出現(xiàn)節(jié)點失效和通信故障，無法保證及時回復通信消息。

(2)所有在線存儲節(jié)點的通信信息都遵守讀寫一致性協(xié)議的規(guī)定。

圖1展示了一個包含4個存儲節(jié)點和3個用戶的讀寫一致性問題示例[4]。

Figure 1 Consensus problem between multiple storage nodes

由于網(wǎng)絡可能無法保證所有節(jié)點的連通性，在圖1中，當存儲節(jié)點斷開連接后，用戶1和用戶2分別向2個存儲節(jié)點返回了更新值x=A和x=B。當用戶3需要讀取變量x的值時，該用戶將無法確定其當前值。

2.2 讀寫一致性算法的目標

為了避免讀寫數(shù)據(jù)不一致的情況，需要部署讀寫一致性算法來保證數(shù)據(jù)的可用性。具體來說，讀寫一致性算法需要滿足以下特性：

(1)可靠性：在存儲節(jié)點未出現(xiàn)拜占庭錯誤的情況下，分布式存儲系統(tǒng)不能回復錯誤信息。

(2)魯棒性：在大部分存儲節(jié)點正常在線并能相互通信的情況下，通過讀寫一致性算法，能保證用戶正常讀寫數(shù)據(jù)。

在此基礎上，開發(fā)人員需要根據(jù)存儲應用場景的需求部署相應的讀寫一致性算法來保證數(shù)據(jù)讀寫操作的性能。

2.3 部署讀寫一致性算法面臨的挑戰(zhàn)

雖然讀寫一致性算法能夠保證數(shù)據(jù)讀寫操作的正確性，研究人員依然需要根據(jù)應用場景選擇合適的讀寫一致性策略。具體來說，部署讀寫一致性算法時將面臨以下挑戰(zhàn)：

(1)為了保證用戶從節(jié)點中讀寫數(shù)據(jù)的正確性，讀寫一致性算法通常要求分布式存儲系統(tǒng)執(zhí)行多次數(shù)據(jù)傳輸操作，以確定存儲節(jié)點的狀態(tài)[3]。這些傳輸操作往往會帶來較大的數(shù)據(jù)讀寫時延，影響其上在線應用對用戶的服務質(zhì)量。

(2)讀寫一致性算法通常需要復雜通信協(xié)議。例如，Raft算法[6]需要選舉主節(jié)點來協(xié)調(diào)存儲節(jié)點共同完成數(shù)據(jù)讀寫操作。在跨數(shù)據(jù)中心場景中，在分布式存儲系統(tǒng)選舉出的主節(jié)點網(wǎng)絡狀態(tài)較差的情況下，主節(jié)點的通信時延會嚴重影響讀寫用戶數(shù)據(jù)的性能[7]。

(3)讀寫一致性算法需要保證存儲數(shù)據(jù)的可靠性。在出現(xiàn)部分存儲節(jié)點失效的情況下，讀寫一致性算法需要保證分布式存儲系統(tǒng)能完成數(shù)據(jù)讀寫操作[5]。因此，讀寫一致性算法需要設計一定的冗余機制，保證分布式存儲系統(tǒng)可以穩(wěn)定地向用戶端設備提供存儲服務。

3 讀寫一致性算法的實現(xiàn)機制

本節(jié)簡述3種類型讀寫一致性算法實現(xiàn)機制。

3.1 基于中心控制的讀寫一致性算法

基于中心控制的讀寫一致性算法[1]部署額外的控制節(jié)點來保證讀寫數(shù)據(jù)的正確性。由于實現(xiàn)較為簡單，該類算法被廣泛部署于分布式存儲系統(tǒng)。例如，HDFS(Hadoop Distributed File System)[1]使用名字節(jié)點(Name Node)和數(shù)據(jù)節(jié)點(Data Node)組成主從結(jié)構。

為了保證讀寫一致性，控制節(jié)點定義主副本(Primacy Replica)和備用副本(Backup Replica)。分布式存儲系統(tǒng)可以根據(jù)主副本所存儲內(nèi)容來確定當前值。即使主副本失效，控制節(jié)點依然能根據(jù)多個備用副本數(shù)據(jù)確定當前值，定義新的主副本，保證數(shù)據(jù)可用性。圖2展示了HDFS存儲系統(tǒng)中3副本數(shù)據(jù)寫入過程[1]。

Figure 2 Write process for three replicas in HDFS

在數(shù)據(jù)寫入過程中，用戶優(yōu)先寫入元數(shù)據(jù)到控制節(jié)點，再更新數(shù)據(jù)節(jié)點中副本內(nèi)容。分布式存儲系統(tǒng)讀取主副本來確定當前存儲數(shù)據(jù)的值。當數(shù)據(jù)失效時，通過讀取備用副本信息和版本信息能夠恢復出失效的主副本數(shù)據(jù)。

基于中心控制的讀寫一致性算法被廣泛應用于早期分布式存儲系統(tǒng)，以保證數(shù)據(jù)讀寫一致性，如HDFS[1]和GFS(Google File System)[8]。由于數(shù)據(jù)讀寫過程需要訪問控制節(jié)點存儲的元數(shù)據(jù)，控制節(jié)點失效往往會嚴重影響存儲服務的可用性。

雖然基于中心控制的讀寫一致性算法能夠保證讀寫數(shù)據(jù)的正確性，但是主副本的存儲節(jié)點往往會成為性能瓶頸，為了保證數(shù)據(jù)寫入的性能，讀寫一致性算法需要引入相應的機制。

此外，基于中心控制的讀寫一致性算法主要通過控制節(jié)點協(xié)調(diào)其他參與節(jié)點來完成數(shù)據(jù)讀寫操作[1]，包括兩階段提交協(xié)議2PC(Two-Phase Commit)[9]和三階段提交協(xié)議3PC(Three-Phase Commit)[10]?；谥行目刂频淖x寫一致性算法依然需要在控制節(jié)點失效時保證分布式存儲系統(tǒng)能夠正確地執(zhí)行數(shù)據(jù)讀寫操作。

3.2 基于消息傳遞的讀寫一致性算法

為了在控制節(jié)點失效的情況下保證分布式存儲系統(tǒng)依然可以有效地完成數(shù)據(jù)讀寫操作，基于消息傳遞的讀寫一致性算法[5]采用存儲節(jié)點投票的方式來將用戶數(shù)據(jù)寫入存儲節(jié)點。

基于消息傳遞的讀寫一致性算法包括3種類型的節(jié)點：提案節(jié)點(Proposer)、仲裁節(jié)點(Acceptor)和學習節(jié)點(Learner)。通過滿足以下3個條件，Paxos算法[5]能保證所有遵守通信協(xié)議的提案(Proposal)執(zhí)行結(jié)果的正確性。

(1)所有提案有唯一的編號。

(2)任意2個提案P1和P2至少有1個相同的仲裁者。

(3)對于任意提案P，如果提案P的投票節(jié)點在之前的提案中同意更新變量值，那么提案P設定的變量值，需要和最近被投過贊成票的提案變量值保持一致。

根據(jù)上述3個條件，Paxos算法可以構建一個讀寫一致性的提案集合。這里使用單個變量實現(xiàn)一個案例來說明Paxos算法的投票過程。

假設存儲系統(tǒng)中存在5個仲裁節(jié)點A、B、C、D和E接收到來自存儲系統(tǒng)中提案節(jié)點的5條提案，提案編號為1,6,13,25和31。

圖3展示了由5個仲裁節(jié)點參與的Paxos投票過程[5]。其中，用黑體字標注的節(jié)點為回復數(shù)據(jù)值成功執(zhí)行的存儲節(jié)點。這5個節(jié)點需要在2個值中選擇1個值，并將其保存到所有節(jié)點。

Figure 3 Message delivery-based consensus algorithms

提案1：第1個提案雖然有4個節(jié)點參與了提案的投票過程，但僅有節(jié)點E確認了提案信息。因此，提案1未成功通過仲裁階段，無法更新存儲節(jié)點的變量值。

提案6：由于投票的節(jié)點在之前沒有投過贊成票，提案6可以選擇不同的變量值。但是，只有節(jié)點A確認了提案信息，少于半數(shù)以上(即3票)，提案6依然沒有通過。

提案13：由于節(jié)點B、C和D之前提案沒有更新過變量值，提案13可以將變量值更新為任意值。本輪節(jié)點B和節(jié)點D確認了該提案，但贊成的票數(shù)依然少于半數(shù)，提案13未通過。

提案25：由于提案節(jié)點收到3個節(jié)點A、C和D的確認信息，提案25是唯一更新變量值成功的提案。其中，節(jié)點A和節(jié)點E分別在提案6和提案1上更新了數(shù)值且提案6的編號更接近提案25的。提案25更新的變量值應當與提案6所更新的變量值相同。

提案31：為了保證所有節(jié)點存儲的變量值都相同，存儲節(jié)點需要與其他節(jié)點同步變量值。提案31將已經(jīng)更新的變量值同步到另外2個節(jié)點。

在上述例子中，通過滿足3個讀寫一致性條件，分布式存儲系統(tǒng)可以實現(xiàn)全局提案集合的讀寫一致性。在實際存儲系統(tǒng)中，提案節(jié)點需要根據(jù)生成的提案編號，保證所有的存儲節(jié)點可以高效地完成相應的數(shù)據(jù)更新操作。

為了簡化數(shù)據(jù)寫入過程，Paxos算法采用以下步驟來完成數(shù)據(jù)寫入過程：

(1)準備階段：提案節(jié)點生成全局唯一的提案編號，向所有的仲裁節(jié)點發(fā)送該編號。仲裁節(jié)點根據(jù)收到的編號信息，判斷是否接受這條提案，相應的處理結(jié)果回復給提案節(jié)點。

(2)仲裁階段：提案節(jié)點向仲裁節(jié)點發(fā)送提案變量值，仲裁節(jié)點接收變量值后返回確認信息。當收到大部分仲裁節(jié)點對變量值更新的確認消息后，提案節(jié)點標記該提案已通過。

(3)學習階段：提案節(jié)點將更新的變量值發(fā)送到?jīng)]有參與到仲裁過程的其他的學習節(jié)點，從而完成所有存儲節(jié)點變量值的更新操作。

通過上述步驟，Paxos算法保證了分布式存儲系統(tǒng)讀寫數(shù)據(jù)的正確性。由于讀寫過程中任一節(jié)點都能夠作為提案節(jié)點發(fā)起寫入操作，Paxos算法能夠有效地避免單個節(jié)點成為性能瓶頸，從而提升數(shù)據(jù)讀寫操作的性能。

圖4展示了Paxos算法執(zhí)行過程示意圖[12]。

Figure 4 Transmission process with Paxos

為了保證全局提案編號的唯一性和有序性，當仲裁節(jié)點收到編號為ir的準備請求后，仲裁節(jié)點將針對接收到的提案作出以下2個承諾：

(1)仲裁節(jié)點不再接收提案編號ip小于或等于當前提案編號的提案請求。

(2)仲裁節(jié)點不再接收提案編號i′r小于當前提案編號ir的準備請求。

雖然基于消息傳遞的讀寫一致性算法可以從理論上保證數(shù)據(jù)讀寫操作的正確性，但是基于消息傳遞的讀寫一致性算法需要較為復雜的通信規(guī)則，往往會增加實現(xiàn)算法的難度，難以保證存儲數(shù)據(jù)的可靠性。因此，如何降低Paxos算法實現(xiàn)的復雜度，成為了保證數(shù)據(jù)讀寫操作可靠性的關鍵問題。

3.3 基于選舉的讀寫一致性算法

基于選舉的讀寫一致性算法[6]通過在在線節(jié)點中確定主節(jié)點的方式來實現(xiàn)在保證讀寫數(shù)據(jù)正確性的前提下降低算法復雜性。這里使用Raft算法[6]作為示例來介紹基于選舉的讀寫一致性算法的執(zhí)行過程。通過從在線從節(jié)點中選舉出主節(jié)點，Raft算法能夠保證主從節(jié)點之間的讀寫數(shù)據(jù)一致性。

圖5展示了Raft算法主從節(jié)點的示意圖[6]。

Figure 5 Leader and followers node in Raft

Raft算法包括以下3種類型的節(jié)點：從節(jié)點、候選節(jié)點和主節(jié)點。

通過在存儲節(jié)點中維護本地狀態(tài)機，Raft算法使用選舉機制來實現(xiàn)每個存儲節(jié)點在從節(jié)點、候選節(jié)點和主節(jié)點3種類型節(jié)點之間的狀態(tài)轉(zhuǎn)換操作。分布式存儲系統(tǒng)需要周期性地執(zhí)行選舉操作來確定主節(jié)點，以協(xié)調(diào)數(shù)據(jù)讀寫操作，從而保證提供持續(xù)的數(shù)據(jù)存儲服務。

圖6展示了Raft算法選舉過程的狀態(tài)機[6]。

Figure 6 State machine of Raft algorithm selection process

由圖6可知，Raft算法中的存儲節(jié)點通過以下狀態(tài)轉(zhuǎn)移規(guī)則切換其狀態(tài)類型。

(1)從節(jié)點：在分布式存儲系統(tǒng)上線時，所有在線節(jié)點以從節(jié)點狀態(tài)等待進入選舉過程。當新的選舉周期開始時，從節(jié)點將成為候選節(jié)點參與讀寫一致性算法主節(jié)點投票選舉過程。

(2)候選節(jié)點：候選節(jié)點收到大多數(shù)節(jié)點的支持票后將成為主節(jié)點。當發(fā)現(xiàn)分布式存儲系統(tǒng)中已經(jīng)存在主節(jié)點或選舉周期過期時，候選節(jié)點將回退成為從節(jié)點等待下一個選舉周期，再次參與主節(jié)點選舉過程。

(3)主節(jié)點：在收到大多數(shù)節(jié)點的支持票時，候選節(jié)點會將自己的狀態(tài)設置為主節(jié)點。為了保證分布式存儲系統(tǒng)主節(jié)點的唯一性，當主節(jié)點在通信過程中發(fā)現(xiàn)存在更高優(yōu)先級的主節(jié)點后，會將自己的狀態(tài)設為從節(jié)點。

每隔一定周期后，分布式存儲系統(tǒng)會重新選舉主節(jié)點，負責協(xié)調(diào)存儲節(jié)點處理用戶端發(fā)出的數(shù)據(jù)讀寫請求。

圖7展示了Raft算法周期示意圖[6]。

Figure 7 Terms of selection process in Raft algorithm

雖然Raft算法可以通過選舉過程確定主節(jié)點來解決讀寫一致性問題，分布式存儲系統(tǒng)依然需要通過讀寫主節(jié)點存儲的內(nèi)容來確定保存在分布式存儲系統(tǒng)中的各個變量的當前值。

Raft算法使用復制狀態(tài)機來保證所有的主從節(jié)點數(shù)據(jù)的一致性。圖8展示了Raft算法日志數(shù)據(jù)提交過程[6]，包括3個存儲節(jié)點和2個變量，變量x和變量y。每一個日志項包括2部分內(nèi)容，提交時的周期值和變量的改變值。這里將3個節(jié)點分別記為主節(jié)點、從節(jié)點1和從節(jié)點2。

Figure 8 Submission process of Raft algorithm log data

在圖8中，使用深淺不同的顏色表示在各個周期中用戶端設備提交的數(shù)據(jù)寫入請求。為了提升Raft算法的執(zhí)行效率，不同于經(jīng)典的兩階段提交算法，狀態(tài)機復制過程中不要求所有在線節(jié)點存儲的日志數(shù)據(jù)都為當前最新版本，僅需保證多數(shù)節(jié)點確認數(shù)據(jù)寫入，即認為存儲系統(tǒng)已提交了變量值。在用戶訪問主節(jié)點存在較大時延的情況下，主節(jié)點會成為整個分布式存儲系統(tǒng)數(shù)據(jù)讀寫操作的性能瓶頸。

3.4 讀寫一致性算法實現(xiàn)機制比較

在部署分布式存儲系統(tǒng)的過程中，開發(fā)人員需要根據(jù)應用場景選擇適合的讀寫一致性算法和性能優(yōu)化方案，調(diào)整讀寫一致性算法的存儲和通信機制來保證數(shù)據(jù)讀寫操作的性能。表1比較了3種類型讀寫一致性算法的實現(xiàn)難度、算法機制和容錯性方面的特點。

Table 1 Comparison of the mechanism of different consensus algorithms

4 讀寫一致性算法性能優(yōu)化方案

本節(jié)主要綜述使用副本和糾刪碼2種常見的數(shù)據(jù)存儲方案的情況下，讀寫一致性算法的實現(xiàn)機制和性能優(yōu)化方案。

4.1 分布式存儲系統(tǒng)的數(shù)據(jù)存儲機制

為了適應不同應用場景的存儲需求，分布式存儲系統(tǒng)往往采用副本和糾刪碼2種數(shù)據(jù)存儲機制來保證存儲數(shù)據(jù)的可靠性。

(1)副本存儲方案：通過將用戶數(shù)據(jù)的多個副本存儲到多個存儲節(jié)點來保證數(shù)據(jù)可靠性。

(2)糾刪碼存儲方案：將用戶數(shù)據(jù)切片生成數(shù)據(jù)分片，編碼數(shù)據(jù)分片生成多個檢驗分片，并將這些分片存儲到多個存儲節(jié)點，從而保證分布式存儲系統(tǒng)的數(shù)據(jù)可靠性。

4.2 基于副本的讀寫一致性算法性能優(yōu)化

為了保證存儲在多個節(jié)點副本數(shù)據(jù)的一致性，研究人員提出了基于消息傳遞的讀寫一致性算法。如Lamport[5]提出了Paxos算法，以保證存儲節(jié)點數(shù)據(jù)的讀寫一致性。文獻[12]介紹了Paxos算法的運行機制。Chandra等[13]討論了證明Paxos算法代碼正確的方法。Lamport[14]提出了異步Paxos算法，通過并行化讀寫數(shù)據(jù)來減小讀寫操作時延。類似工作還有Fast-Paxos[15]、Vertical Paxos[16]、Cheap-Paxos[17]、DPaxos[18]、Flexible Paxos[19]和EPaxos[20]。然而，這些算法需要使用較為復雜的讀寫一致性協(xié)議，通常會產(chǎn)生額外的數(shù)據(jù)傳輸開銷，降低分布式存儲系統(tǒng)數(shù)據(jù)讀寫操作的性能。

為了提升分布式存儲系統(tǒng)讀寫一致性算法的執(zhí)行效率，研究人員提出了多種讀寫一致性算法性能優(yōu)化方案。如Junqueira等[22]提出的ZAB(Zookeeper Atomic Broadcasts)協(xié)議通過廣播機制來保證讀寫性能。讀寫一致性系統(tǒng)組件ZooKeeper[23]使用ZAB協(xié)議來提升讀寫操作的性能[24]。Brenner等[25]提出了SecureKeeper框架，引入因特爾SGX (Software Guard eXtensions)指令集提升ZAB協(xié)議的安全性。Frommgen等[26]提出在ZooKeeper運行過程中切換讀寫一致性算法來保證服務質(zhì)量。史博軒等[27]使用ZooKeeper構建統(tǒng)一信任錨模型。Gray等[28]提出了租約機制Leases方案來提升緩存服務的性能。Moraru等[29]使用Go語言實現(xiàn)了分布式租約機制[30]。Decandia等[31]提出了Dynamo存儲系統(tǒng)，部署了NWR算法[32]來調(diào)整讀寫一致性算法執(zhí)行過程中副本數(shù)量n、寫入副本數(shù)量w和讀取副本數(shù)量r等參數(shù)來適應不同的分布式存儲系統(tǒng)應用場景。王華進等[32]分析了NWR算法在不同參數(shù)情況下隊列解析開銷和數(shù)據(jù)寫入時延。Huang等[33]使用排隊論分析可能導致Cassandra數(shù)據(jù)庫短時間數(shù)據(jù)不一致的原因。朱濤等[34]總結(jié)了讀寫一致性算法和數(shù)據(jù)可用性的關系。Wang等[35]通過測試HBase[36]和Cassandra[37]2種常用數(shù)據(jù)庫系統(tǒng)來分析副本數(shù)據(jù)對數(shù)據(jù)讀寫操作性能的影響。類似工作還有Scatter[38]、ZooNet[39]、COPS(Clusters of Order-Preserving Servers)[40]、WPaxos[41]、Spanner-RSS(Spanner Regular Sequential Serializability)[42]、PaxosLease[43]和Volume leases[44]等。

為了提升存儲系統(tǒng)軟件的可靠性，研究人員使用多種方法來降低基于消息傳遞的讀寫一致性算法的實現(xiàn)復雜度。如Lamport等[45]使用了可重設置狀態(tài)機來實現(xiàn)讀寫一致性算法，并證明了其算法的正確性。Ongaro等[6]提出了Raft算法來實現(xiàn)主節(jié)點選舉和主從節(jié)點數(shù)據(jù)同步過程。Lampson[4]分別總結(jié)了Paxos在經(jīng)典讀寫一致性問題、磁盤讀寫一致性問題和拜占庭讀寫一致性問題場景的案例。這些讀寫一致性機制也被部署到了ZooKeeper[23]和Chubby[46]等分布式讀寫一致性管理系統(tǒng)中。

在此基礎上，研究人員針對各種分布式存儲系統(tǒng)應用場景提出了相應的讀寫一致性算法性能優(yōu)化方案。如Li等[47]提出了NOPaxos(Network Ordered Paxos),使用網(wǎng)絡層廣播協(xié)議來減少讀寫一致性算法執(zhí)行過程的數(shù)據(jù)傳輸開銷。Mahmoud等[48]提出了Replicated Commit來提升跨數(shù)據(jù)中心通信性能。Nawab等[49]推導出了跨數(shù)據(jù)中心數(shù)據(jù)提交過程消耗時間下限。Guo等[50]設計了面向SQL語義的讀寫一致性方案來提升并行化事務處理性能。類似工作還有Dynamo[31]、Cassandra[37]、MegaStore[51]、Spanner[52]、FSS (File Storage Service)[53]、Volley[54]、Harp[55]、Mencius[56]、etcd[57]和MDCC(Multi-Data Center Consistency)[58]等。雖然能保證讀寫數(shù)據(jù)的一致性，基于副本的讀寫一致性算法在執(zhí)行過程中需要傳輸大量的用戶數(shù)據(jù)，會帶來較大的數(shù)據(jù)傳輸開銷。為了保障數(shù)據(jù)讀寫操作的執(zhí)行效率，糾刪碼作為一種能減少傳輸開銷的機制被用于減少讀寫過程中的傳輸開銷。

4.3 基于糾刪碼的讀寫一致性算法性能優(yōu)化

糾刪碼作為一種常見的數(shù)據(jù)可靠性保障機制被廣泛部署到了分布式存儲系統(tǒng)中來保存用戶數(shù)據(jù)。如Reed等[59]提出了RS(Reed-Solomon)編碼來保證數(shù)據(jù)可靠性。Dimakis等[60]提出了再生碼來減少數(shù)據(jù)修復操作的網(wǎng)絡傳輸開銷。Shum等[61]提出了合作再生編碼來減少多節(jié)點失效時數(shù)據(jù)修復操作的網(wǎng)絡傳輸開銷。Huang等[62]提出了LRC (Local Reconstruction Codes)來減少單存儲節(jié)點數(shù)據(jù)失效情況下數(shù)據(jù)修復操作的網(wǎng)絡開銷。Shen等[63]使用網(wǎng)絡編碼來加速云際存儲系統(tǒng)數(shù)據(jù)寫入操作的性能。類似的工作還有Core[64]、CaCo(Cauchy Coding)[65]、PUSH[66]、AONT-RS(All-Or-Nothing Transform with Reed-Solomon coding)[67]、CAONT-RS(Convergent AONT-RS)[68]、CDStore[69]、UniDrive[70]和RDOR(Row-Diagonal Optimal Recovery)[71]等。

為了保證數(shù)據(jù)讀寫操作的執(zhí)行效率，研究人員提出了基于糾刪碼的讀寫一致性算法來減少數(shù)據(jù)讀寫過程中傳輸?shù)臄?shù)據(jù)量。如Mu等[72]提出了RS-Paxos算法，引入了糾刪碼機制來減少Paxos算法執(zhí)行過程中數(shù)據(jù)傳輸量。Wang等[73]提出了CRaft算法來將Raft算法部署到糾刪碼存儲系統(tǒng)中。由于基于選舉的讀寫一致性算法需要通過主節(jié)點讀寫數(shù)據(jù)，會降低網(wǎng)絡傳輸性能，Uluyol等[7]提出了Pando方案來高效部署Paxos算法，優(yōu)化糾刪碼存儲系統(tǒng)跨數(shù)據(jù)中心的數(shù)據(jù)讀寫時延，且已被應用到了聯(lián)邦學習[74]等場景中。通過傳輸編碼后的用戶數(shù)據(jù)，基于糾刪碼的讀寫一致性算法能夠有效減少執(zhí)行數(shù)據(jù)讀寫操作過程中網(wǎng)絡帶寬資源的消耗量。然而，糾刪碼也帶來了數(shù)據(jù)修復操作帶寬消耗量大和數(shù)據(jù)讀寫操作消耗時間長等一系列問題[75]。

為了保證數(shù)據(jù)可靠性，提升用戶讀寫數(shù)據(jù)的效率，研究人員提出了多種性能優(yōu)化方案提升在各個應用場景中糾刪碼存儲系統(tǒng)執(zhí)行數(shù)據(jù)修復操作和數(shù)據(jù)讀寫操作的性能。Chen等[76]提出了Giza來保證跨數(shù)據(jù)中心的糾刪碼對象存儲系統(tǒng)的數(shù)據(jù)讀寫一致性。Chen等[77]提出了副本和糾刪碼混合存儲方案來提升內(nèi)存對象存儲系統(tǒng)的數(shù)據(jù)讀寫操作性能。Sathiamoorthy等[75]將再生碼部署到HDFS存儲系統(tǒng)中,以減少數(shù)據(jù)修復操作的網(wǎng)絡傳輸開銷。Shen等[78]提出了跨機架的路由方案來加速多個存儲節(jié)點的數(shù)據(jù)寫入過程。Shi等[79]設計了UMR-EC(Unified and Multi-Rail Erasure Coding)編碼架構優(yōu)化數(shù)據(jù)讀寫操作的執(zhí)行過程。Renesse等[80]綜述了Paxos算法相關讀寫一致性算法。

4.4 讀寫一致性算法性能比較

為了滿足應用場景的存儲需求，開發(fā)人員需要了解讀寫一致性算法的系統(tǒng)開銷和相應的實現(xiàn)機制。本節(jié)將分析各種讀寫一致性算法的存儲空間和容錯性能。本節(jié)將容錯節(jié)點數(shù)量定義為在執(zhí)行數(shù)據(jù)讀寫操作過程中容忍失效節(jié)點的數(shù)量，該參數(shù)越大說明讀寫一致性算法可以在越多節(jié)點失效的情況下執(zhí)行讀寫操作。

表2比較了主要讀寫一致性算法的存儲開銷、容錯節(jié)點數(shù)量及其實現(xiàn)機制。表2中，存儲開銷代表存儲數(shù)據(jù)所消耗磁盤空間大小，n為存儲節(jié)點的數(shù)量，r為設定讀取節(jié)點的數(shù)量，k為數(shù)據(jù)節(jié)點的數(shù)量。假設用戶將數(shù)據(jù)量為M字節(jié)的文件保存到n個存儲節(jié)點中。分布式存儲系統(tǒng)能夠使用副本和糾刪碼機制通過以下步驟完成數(shù)據(jù)讀寫操作：

在副本存儲情況下，每一個節(jié)點的數(shù)據(jù)量為M字節(jié)。由于存在n個節(jié)點，分布式存儲系統(tǒng)共存儲了n*M字節(jié)數(shù)據(jù)。由于所有節(jié)點都保存和傳輸重復數(shù)據(jù)，副本機制通常會消耗大量存儲空間和網(wǎng)絡帶寬，影響數(shù)據(jù)讀寫操作的性能。在糾刪碼存儲情況下，用戶端設備將文件分成k個數(shù)據(jù)分片，將數(shù)據(jù)分片編碼生成m個校驗分片，并存儲到n=k+m個存儲節(jié)點中。其中，每一個存儲節(jié)點將保存M/k字節(jié)數(shù)據(jù)，所以n個存儲節(jié)點共保存(n*M)/k字節(jié)數(shù)據(jù)。

Table 2 Comparison of performance of different consensus algorithms

由于糾刪碼機制將數(shù)據(jù)編碼保存到多個存儲節(jié)點，相較于副本機制，分布存儲系統(tǒng)能夠在消耗更小的存儲空間的前提下保存相同的數(shù)據(jù)內(nèi)容。然而，基于糾刪碼的讀寫一致性算法需要更多在線節(jié)點和更大計算開銷才能正確地完成數(shù)據(jù)讀寫操作，降低了存儲數(shù)據(jù)的可用性。

5 應用場景對讀寫性能的影響

本節(jié)將比較2種應用場景(即單數(shù)據(jù)中心分布式存儲系統(tǒng)和跨數(shù)據(jù)中心云際存儲系統(tǒng))中影響讀寫一致性算法性能的因素。

5.1 讀寫一致性算法的應用場景

開發(fā)人員需要充分了解各種算法的性能，才能選擇適合當前存儲應用場景的讀寫一致性算法。具體來說，讀寫一致性算法部署在以下2種分布式存儲應用場景：

(1)單數(shù)據(jù)中心分布式存儲系統(tǒng)：在寫入數(shù)據(jù)量較大的情況下，前端服務器數(shù)據(jù)寫入和數(shù)據(jù)同步過程消耗的時間占數(shù)據(jù)寫入時間的很大一部分[8]。為了保證讀寫數(shù)據(jù)的性能，開發(fā)人員需要優(yōu)化讀寫操作執(zhí)行流程，以減少數(shù)據(jù)讀寫過程中的網(wǎng)絡通信開銷。

(2)跨數(shù)據(jù)中心云際存儲系統(tǒng)：為了避免單數(shù)據(jù)中心可能出現(xiàn)的數(shù)據(jù)泄露和丟失等問題，跨數(shù)據(jù)中心云際存儲系統(tǒng)將數(shù)據(jù)存儲在多個數(shù)據(jù)中心。由于數(shù)據(jù)被存儲在不同地理位置的云存儲節(jié)點，需要充分考慮各個云存儲節(jié)點之間的傳輸時延。

5.2 單數(shù)據(jù)中心分布式存儲系統(tǒng)

由于單數(shù)據(jù)中心需要運行多種業(yè)務，存儲節(jié)點之間的可用帶寬通常非常有限。圖9展示了包括1個用戶和4個存儲節(jié)點的分布式存儲系統(tǒng)的數(shù)據(jù)寫入操作的執(zhí)行過程：

在圖9a中，不同的存儲節(jié)點之間帶寬具有較大的差異性，需要充分利用用戶端設備和存儲節(jié)點之間的帶寬資源。

圖9b展示了傳統(tǒng)數(shù)據(jù)寫入方案的路由。由于用戶端設備直接將數(shù)據(jù)寫入到存儲節(jié)點，寫入過程通常會受到瓶頸鏈路帶寬的限制。

在圖9c中，通過合理設計數(shù)據(jù)傳輸路由，分布式存儲系統(tǒng)可以有效避開網(wǎng)絡拓撲的瓶頸鏈路，保證數(shù)據(jù)寫入操作的性能。

5.3 跨數(shù)據(jù)中心云際存儲系統(tǒng)

為了保證在跨數(shù)據(jù)中心場景中數(shù)據(jù)讀寫操作的性能，部署讀寫一致性算法時，存儲系統(tǒng)設計人員需要注意以下要點：

(1)為了保證用戶訪問的性能，前端服務器應當盡量靠近存儲節(jié)點，減少網(wǎng)絡傳輸時延。

(2)任意2個前端服務器至少需要訪問1個公共的存儲節(jié)點來保證數(shù)據(jù)一致性。

圖10展示了跨數(shù)據(jù)中心數(shù)據(jù)讀寫過程。

Figure 9 Example of the route strategies for the write operations in distributed storage systems

Figure 10 I/O process of the consensus algorithms between multiple data centers

在實際的云際存儲系統(tǒng)中，前端服務器訪問保存在不同存儲節(jié)點的數(shù)據(jù)的傳輸時延往往存在著較大差異性，因此，前端服務器需要選擇訪問傳輸時延較小的存儲節(jié)點，以保證對用戶數(shù)據(jù)訪問操作的服務質(zhì)量。

6 讀寫一致性算法部署建議和展望

本節(jié)將總結(jié)部署讀寫一致性算法需注意的要點以及學術研究和工業(yè)領域亟需解決的問題。

6.1讀寫一致性算法部署建議

在實際的生產(chǎn)系統(tǒng)中，開發(fā)人員在部署讀寫一致性算法時應當注意以下方面：

(1)根據(jù)應用場景中數(shù)據(jù)寫入請求數(shù)據(jù)量大小的差異，開發(fā)人員需要分析讀寫一致性算法中各個階段在數(shù)據(jù)讀寫操作中的時間占比。為了保證數(shù)據(jù)讀寫操作的執(zhí)行效率，分布式存儲系統(tǒng)需要根據(jù)數(shù)據(jù)讀寫操作的特征部署合適的讀寫一致性策略和性能優(yōu)化方案。

(2)根據(jù)分布式存儲系統(tǒng)的數(shù)據(jù)存儲機制，開發(fā)人員需要選擇合適的讀寫一致性算法來滿足存儲應用的性能需求。由于副本和糾刪碼存儲機制有較大的差異，分布式存儲系統(tǒng)需要部署對應的讀寫一致性算法來適應各種存儲機制下數(shù)據(jù)讀寫操作的性能。

(3)根據(jù)應用網(wǎng)絡環(huán)境的特性，包括傳輸時延和網(wǎng)絡帶寬，開發(fā)人員需要優(yōu)化讀寫一致性算法的通信機制來減小數(shù)據(jù)傳輸帶來的開銷。針對不同的存儲應用場景，分布式存儲系統(tǒng)需要引入相應的傳輸策略來減小讀寫一致性算法數(shù)據(jù)讀寫操作的傳輸開銷。

6.2 讀寫一致性算法研究工作展望

雖然當前讀寫一致性算法能保證數(shù)據(jù)讀寫操作的性能，但是當前讀寫一致性算法依然存在諸多問題，如網(wǎng)絡適應能力弱和難以適應不同大小的數(shù)據(jù)讀寫請求。為了滿足用戶讀寫性能需求，需要部署以下優(yōu)化方案：

(1)高自適應存儲機制：隨著承載服務類型的增加，業(yè)務系統(tǒng)通常提供多種不同的在線服務。由于單獨使用副本機制和糾刪碼機制適合的應用場景有限，分布式存儲系統(tǒng)需部署多種存儲機制融合的讀寫一致性算法，動態(tài)調(diào)整其存儲機制，以適應日益復雜的應用場景。

(2)動態(tài)調(diào)整網(wǎng)絡路由策略：由于存儲節(jié)點之間的網(wǎng)絡通常存在較大異構性，讀寫一致性算法需要根據(jù)分布式存儲系統(tǒng)的網(wǎng)絡狀態(tài)調(diào)整存儲節(jié)點之間的網(wǎng)絡路由策略，以保證分布式存儲系統(tǒng)數(shù)據(jù)讀寫操作的性能。

(3)構建智能讀寫一致性算法：在執(zhí)行當前讀寫一致性算法過程中，存儲節(jié)點通常使用固定通信協(xié)議來保證讀寫操作的正確性，難以滿足服務質(zhì)量需求。通過引入人工智能方案分析過往的用戶行為和存儲集群狀態(tài)，智能讀寫一致性算法能夠有效提升數(shù)據(jù)讀寫操作的性能。

6.3 工業(yè)界讀寫一致性算法性能優(yōu)化展望

雖然當前工業(yè)界已廣泛部署了讀寫一致性組件庫(如ZooKeeper[23])來保證分布式存儲系統(tǒng)執(zhí)行數(shù)據(jù)讀寫操作的正確性，但是這些組件庫存在應用場景單一和讀寫開銷較大等問題，依然有以下值得進一步開展研究的方向：

(1)測試讀寫一致性算法性能： 雖然研究人員已開展了大量的讀寫一致性算法性能優(yōu)化工作，但現(xiàn)有研究中依然缺少對讀寫一致性算法的性能定量測試比較工作。根據(jù)讀寫一致性算法的實現(xiàn)機制，亟需構建大量定量系統(tǒng)性實驗來充分測量讀寫一致性算法的性能，便于開發(fā)人員選擇適合存儲應用場景的讀寫一致性算法。

(2)構建副本和編碼混合讀寫一致性機制：由于不同存儲機制適用的應用場景具有較大的差異，現(xiàn)有適用單一存儲機制的讀寫一致性算法難以滿足多種用戶的數(shù)據(jù)讀寫需求，設計副本和編碼混合的讀寫一致性算法將會有效擴大讀寫一致性算法的適用范圍。

(3)引入新硬件設備減少讀寫開銷：隨著新的時鐘硬件(如銫原子鐘[81])在數(shù)據(jù)中心的應用，存儲節(jié)點可精確地獲取當前時間，更容易實現(xiàn)時鐘同步操作。如何構建適應新存儲硬件設備的讀寫一致性方案也將成為提升讀寫操作性能的重要研究方向。

7 結(jié)束語

本文綜述了分布式存儲系統(tǒng)中的讀寫一致性算法的實現(xiàn)機制，并分析了這些算法適宜的應用場景，從而為開發(fā)人員部署讀寫一致性算法提供了相應的理論依據(jù)。在總結(jié)讀寫一致性算法挑戰(zhàn)性的基礎上，還總結(jié)了讀寫一致性算法主要的實現(xiàn)方案，綜述了相關的性能優(yōu)化工作。在此基礎上，本文分析了單數(shù)據(jù)中心分布式存儲系統(tǒng)和多數(shù)據(jù)中心云際存儲系統(tǒng)2種應用場景中各種參數(shù)對讀寫一致性算法數(shù)據(jù)寫入操作性能的影響，并給出了在這些應用場景中部署讀寫一致性算法需注意的要點，展望了未來可能的性能優(yōu)化方案。