F-CAD：一種基于CAD的快速持久化協(xié)議

劉靖宇，李浩鵬，牛秋霞，武優(yōu)西

(河北工業(yè)大學(xué) 人工智能與數(shù)據(jù)科學(xué)學(xué)院 天津 300401)

0 引言

在大型分布式系統(tǒng)中，通常使用復(fù)制的方式來提高容錯，然而，在并發(fā)操作的情況下，跨不同集群或遙遠(yuǎn)地理位置的數(shù)據(jù)中心維護(hù)一致的副本是一項(xiàng)復(fù)雜的任務(wù)。因此提出一致性協(xié)議來保證各個節(jié)點(diǎn)數(shù)據(jù)的一致性，例如Paxos[1]、Raft[2]等。

近年來，一致性協(xié)議取得了大量研究成果，如線性一致性[3]、最終一致性、因果一致性[4]、存在一致性[5]、可擴(kuò)展的因果一致性[6]等，但現(xiàn)有協(xié)議在應(yīng)對跨客戶端單調(diào)讀問題時，均難以給出一個高效的解決方案[7]，在跨客戶端讀取數(shù)據(jù)時容易暴露陳舊的數(shù)據(jù)和讀取。

研究發(fā)現(xiàn)實(shí)現(xiàn)跨客戶端單調(diào)讀的一個主要前提條件是數(shù)據(jù)持久化：同步持久化[8]和異步持久化[9]。同步持久化的額外限制雖然可以滿足跨客戶端單調(diào)讀，但速度很慢，而異步持久化雖然具備高性能，但無法滿足嚴(yán)格的單調(diào)性。

Ganesan等[10]基于異步持久化提出的一致性感知持久性(consistency aware durability,CAD)協(xié)議在讀時強(qiáng)制數(shù)據(jù)持久化。但由于CAD需要超過半數(shù)節(jié)點(diǎn)，持久化寫入全量數(shù)據(jù)才能讀取新寫入的數(shù)據(jù)，并且只能從已經(jīng)持久化的節(jié)點(diǎn)讀取數(shù)據(jù)，導(dǎo)致對于迫切想要讀取最新寫入的數(shù)據(jù)時，每次均需要一個持久化等待時間，并且可讀節(jié)點(diǎn)相對較少。

針對以上問題，本文提出了F-CAD(fast CAD)，一種可以快速持久化的一致性協(xié)議。F-CAD將糾刪碼和CAD結(jié)合，使得集群中F+k個節(jié)點(diǎn)僅需持久化寫入全量數(shù)據(jù)的1/k個片段即可實(shí)現(xiàn)跨客端單調(diào)讀，并保證和CAD相同的Liveness。此時節(jié)點(diǎn)存儲唯一數(shù)據(jù)，如果用戶當(dāng)前僅希望讀取某一數(shù)據(jù)片段，便會頻繁訪問對應(yīng)數(shù)據(jù)節(jié)點(diǎn)，從而導(dǎo)致單節(jié)點(diǎn)負(fù)載過高。后續(xù)會通過增設(shè)一張索引表來解決數(shù)據(jù)節(jié)點(diǎn)負(fù)載過高的問題。

F-CAD的工作主要總結(jié)為三點(diǎn)：1) 高效結(jié)合糾刪碼快速持久化；2) 增設(shè)索引表針對數(shù)據(jù)節(jié)點(diǎn)做負(fù)載均衡；3) 保證索引表中數(shù)據(jù)的實(shí)時性。

1 相關(guān)工作

一致性協(xié)議可以提供高度可靠和可用的分布式服務(wù)，其中的持久化模型是確保用戶單調(diào)讀的關(guān)鍵因素。雖然少有專門針對持久化模型的研究，但它是一致性協(xié)議研究的重要部分，在已經(jīng)提出的很多協(xié)議中均包含對持久化問題的研究。

實(shí)現(xiàn)強(qiáng)一致性需要同步持久化，例如文獻(xiàn)[1]提出的線性一致性是分布式系統(tǒng)可以提供的最強(qiáng)保證。這種很強(qiáng)的一致性在實(shí)際生產(chǎn)中有著諸多應(yīng)用，如LogCabin系統(tǒng)會引導(dǎo)程序同步復(fù)制到多數(shù)節(jié)點(diǎn)，并且將對應(yīng)節(jié)點(diǎn)數(shù)據(jù)落盤。不過其缺點(diǎn)也很明顯，研究表明在大型分布式系統(tǒng)中，完全異步配置要比同步多數(shù)復(fù)制和持久化的Redis快10倍[10]。

同步持久化對于實(shí)現(xiàn)單調(diào)讀是必要的，不過單純的同步持久化并不足以實(shí)現(xiàn)嚴(yán)格的單調(diào)性，還需要額外的機(jī)制。如文獻(xiàn)[2]為了實(shí)現(xiàn)單調(diào)性，將讀取限制到Leader節(jié)點(diǎn)，但是這樣的限制嚴(yán)重影響了讀吞吐量，并且它還阻止客戶端從最近的副本讀取數(shù)據(jù)，增加了讀取延遲。

通常系統(tǒng)無法忍受同步持久化的低性能，特別是在實(shí)際生產(chǎn)中，因而很多人選擇了異步持久化[11]。而一些較弱的一致性協(xié)議雖然具備高性能但無法做到嚴(yán)格的單調(diào)性，特別是在故障發(fā)生的時候[12]。Zab協(xié)議是一個工業(yè)級的實(shí)現(xiàn)，通過異步的方式進(jìn)行復(fù)制和持久化實(shí)現(xiàn)了高性能，但復(fù)制過程中可能會丟失數(shù)據(jù)，導(dǎo)致較差的一致性[13]。

CAD一致性協(xié)議是由Ganesan等提出同時兼顧高性能和單調(diào)性的解決方案。CAD選擇用異步寫的高性能，在讀時強(qiáng)制數(shù)據(jù)持久化，寫時按Raft異步思想寫入，讀時會判斷該寫請求要訪問的數(shù)據(jù)是否可以被用戶讀取，也就是該寫入是否至少被F+1[13]個節(jié)點(diǎn)持久化寫入，并且通過租約機(jī)制[14]創(chuàng)造一個有效集來對讀請求做限制，持久化寫入該數(shù)據(jù)的節(jié)點(diǎn)才能加入有效集，用戶僅能對有效集中的節(jié)點(diǎn)進(jìn)行讀操作。

CAD協(xié)議中數(shù)據(jù)可讀的前提條件是該數(shù)據(jù)是否已經(jīng)被持久化寫入至少F+1個節(jié)點(diǎn)。如果用戶恰好要讀取新寫入的數(shù)據(jù)，此時系統(tǒng)需要頻繁等待大多數(shù)節(jié)點(diǎn)全量數(shù)據(jù)持久化寫入。特別是近年來，Raft和Paxos被應(yīng)用于etcd、TiKV和FSS等真正的大型系統(tǒng)中，已用于復(fù)制TB級的用戶數(shù)據(jù)，數(shù)據(jù)量的龐大使得用戶等待時間顯著增加[15]。在較壞的情況下，如果用戶恰好頻繁讀取新寫入的數(shù)據(jù)，此時CAD應(yīng)對熱讀時性能和同步持久化類似，容易導(dǎo)致系統(tǒng)阻塞，甚至癱瘓。

2 F-CAD快速實(shí)現(xiàn)持久化

CAD一致性協(xié)議每次寫入均需要等待持久化完成，從而導(dǎo)致CAD應(yīng)對熱讀時性能較差，根本原因在于：1) 節(jié)點(diǎn)性能不統(tǒng)一，物理跨度較大，網(wǎng)絡(luò)延遲等因素；2) 單節(jié)點(diǎn)單次必須持久化寫入全量數(shù)據(jù)，并且需要保證持久化寫入到至少F+1個節(jié)點(diǎn)，當(dāng)單次寫入的數(shù)據(jù)量較大時，性能缺陷愈加明顯。本文針對第二點(diǎn)進(jìn)行改進(jìn)，通過減少單次寫入的數(shù)據(jù)量進(jìn)行優(yōu)化。

2.1 F-CAD 結(jié)合糾刪碼

在已知的數(shù)據(jù)冗余方案中糾刪碼可以有效降低存儲和網(wǎng)絡(luò)成本[16]，并保證高可靠性，如Reed-Solomon(RS)碼[17]。RS碼將數(shù)據(jù)切分為大小相等的k個片段，并通過編碼計(jì)算得到m個奇偶校驗(yàn)片段，(k+m)個片段中任意k個都足以恢復(fù)原始數(shù)據(jù)。本文將使用RS碼結(jié)合一致性協(xié)議[18]，其參數(shù)k和m服從k+m=N=2F+1。

一致性協(xié)議通常具備Safety和Liveness兩種特性[19]，Safety表示：在非拜占庭[20]條件下，系統(tǒng)不會返回非正確的結(jié)果。Livenesss表示：只要大多數(shù)服務(wù)器都是活躍的，并且可以相互通信，也可以與客戶端通信，它們就可以正常工作，則稱這組服務(wù)器為健康服務(wù)器。諸如Raft和Paxos的Liveness是F，可以容忍F個節(jié)點(diǎn)的故障，而糾刪碼容忍m個節(jié)點(diǎn)的故障，但是經(jīng)常存在m0，便可以保證F的Liveness，即滿足包含-排斥原則，

|QW∪QR|=|QW|+|QR|-|QW∩QR|。

常見的將糾刪碼結(jié)合一致性協(xié)議的方式是通過增加交集大小，使得|QW∩QR|≥k，這樣寫操作的確認(rèn)寫入需由F+1變?yōu)镕+k，才能保證F+1的Liveness，因?yàn)橹辽傩枰狥+k個節(jié)點(diǎn)確定寫入，即QW=F+k，而QW和QR的交集至少為k，根據(jù)包含-排斥原則得|QW∪QR|=|(F+k)∪QR|≥F+k，所以|QW|+|QR|-|QW∩QR|=F+k+|QR|-k=F+|QR|≥F+k，此時F+|QR|≥F+k，令QW=F+1，則N≥F+k必定成立，所以可以保證F+1的Liveness。

當(dāng)寫請求到達(dá)Leader節(jié)點(diǎn)后，如果當(dāng)前集群中至少有F+k個節(jié)點(diǎn)可以互相通信，Leader收到至少F+k-1個確認(rèn)請求，糾刪碼機(jī)制會先將該日志條目進(jìn)行分片(日志索引不做分片)，分為k個數(shù)據(jù)片段和m個校驗(yàn)片段，且k+m=N，其中每個片段均包含日志索引，然后再將這k+m個片段分別寫入全部節(jié)點(diǎn)。當(dāng)Leader節(jié)點(diǎn)收到至少F+k-1個確認(rèn)寫入且k個數(shù)據(jù)片段已經(jīng)全部持久化寫入，便允許讀取該寫入。如此寫入的數(shù)據(jù)量由原來的F+1減少到(F+k)/k，大大減少了達(dá)到單調(diào)可讀條件的數(shù)據(jù)寫入量。

這里需要注意的一點(diǎn)是，如當(dāng)前集群中互相通信節(jié)點(diǎn)數(shù)大于F，但小于F+k，則為了保證F級別的Liveness，選擇按原CAD協(xié)議復(fù)制寫入，保證了集群的可靠性。

接下來通過一個實(shí)例來說明F-CAD如何通過結(jié)合糾刪碼快速單調(diào)可讀。如圖1所示，圖中是一個7節(jié)點(diǎn)集群，使用(3,4)-RS碼。初始用戶發(fā)出一個寫請求a，如果Leader節(jié)點(diǎn)收到至少F+k-1個確認(rèn)，糾刪碼機(jī)制會將a分為3個數(shù)據(jù)片段和4個校驗(yàn)片段，再分別將這7個片段持久化寫入到對應(yīng)的節(jié)點(diǎn)。Leader節(jié)點(diǎn)會選擇性能較優(yōu)的S1、S2、S3節(jié)點(diǎn)寫入數(shù)據(jù)片段，其余節(jié)點(diǎn)寫入校驗(yàn)片段，等待S1、S2、S3和其余任意三個節(jié)點(diǎn)持久化(顏色加深表示持久化完成)寫入后便可以達(dá)到單調(diào)可讀條件，此時需寫入的數(shù)據(jù)量由原來的4減少為2，減少了50%。

圖1 CAD結(jié)合糾刪碼復(fù)制方案結(jié)構(gòu)圖Figure 1 CAD combined with erasure coding

但此時會暴露一個問題，因?yàn)閿?shù)據(jù)片段唯一地存儲于數(shù)據(jù)節(jié)點(diǎn)，如果此時多個用戶恰好要熱讀的數(shù)據(jù)僅存在于S2節(jié)點(diǎn)，則很容易造成S2節(jié)點(diǎn)負(fù)載過高甚至故障，接下來將就這一問題給出一個解決方案。

2.2 F-CAD負(fù)載均衡方案

通常在分布式系統(tǒng)中解決單節(jié)點(diǎn)負(fù)載過高最有效的方案是負(fù)載均衡。但是傳統(tǒng)的負(fù)載均衡是根據(jù)全局負(fù)載進(jìn)行分流以達(dá)到均衡的效果[21]，而CAD需要針對數(shù)據(jù)節(jié)點(diǎn)而非全部節(jié)點(diǎn)，如此性能才能得到最大提升。

本文方法是通過增設(shè)一個索引表來改變后續(xù)寫入規(guī)則，Leader節(jié)點(diǎn)通過查詢表中字段來判斷具體該如何寫入。索引表通過key-value的方式存儲，其中key具有唯一性，value可為任意類型數(shù)據(jù)結(jié)構(gòu)。表中key為Per字段，表示該節(jié)點(diǎn)性能，對于當(dāng)前主流的分布式存儲，如HDFS、Ceph等負(fù)載均衡時均會基于當(dāng)前各個節(jié)點(diǎn)的CPU、內(nèi)存、網(wǎng)絡(luò)、地理位置等因素得到一個確切的值，這里我們調(diào)用原系統(tǒng)負(fù)載均衡接口得到這個值來作為當(dāng)前節(jié)點(diǎn)的Per字段，并且依據(jù)key值對索引表進(jìn)行排序。Value為其余字段，使用雙向鏈表進(jìn)行存儲，分別為：Node字段，節(jié)點(diǎn)名；Log字段，該日志條目索引；Frag_S字段：片段信息，該片段在全量數(shù)據(jù)中的位置。

如圖2所示，索引表已經(jīng)按Per字段順序排列，Leader節(jié)點(diǎn)可以直接通過指針訪問表中數(shù)據(jù)。圖中S5節(jié)點(diǎn)為性能最優(yōu)節(jié)點(diǎn)，S1次之，……，如果多用戶恰好讀取數(shù)據(jù)片段2，會大大增加S2節(jié)點(diǎn)的故障概率，所以此時性能最優(yōu)節(jié)點(diǎn)S5寫入數(shù)據(jù)片段2，如此用戶便可以通過讀取節(jié)點(diǎn)5也可以讀到數(shù)據(jù)片段2，然后由于S6節(jié)點(diǎn)為次差節(jié)點(diǎn)，但是由于S6節(jié)點(diǎn)是校驗(yàn)片段，所以S1節(jié)點(diǎn)不寫入S6節(jié)點(diǎn)片段，為了防止空操作，S1節(jié)點(diǎn)順序?qū)懭霐?shù)據(jù)片段1。同理S3節(jié)點(diǎn)也不寫入S7節(jié)點(diǎn)片段，而寫入數(shù)據(jù)片段1。后續(xù)會進(jìn)行數(shù)據(jù)補(bǔ)全操作，即S5、S1、S3、S4節(jié)點(diǎn)寫入尚未寫入的其余數(shù)據(jù)片段。

圖2 負(fù)載均衡方案結(jié)構(gòu)圖Figure 2 Load balancing scheme

此時全量數(shù)據(jù)已經(jīng)持久化寫入到至少F+1個節(jié)點(diǎn)，系統(tǒng)可以提交該日志條目繼續(xù)進(jìn)行寫入，用戶也可以通過多個節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的讀取，同時也有效地避免了單節(jié)點(diǎn)負(fù)載過高問題，達(dá)到了均衡效果，不過原來的CAD協(xié)議通過一輪遠(yuǎn)程過程調(diào)用(remote procedure call,RPC)即可實(shí)現(xiàn)持久化，在本一致性中需要多輪，因此在達(dá)到單調(diào)可讀條件后可以選擇一次請求包含多個數(shù)據(jù)塊，如此兩輪RPC便可以完成一次日志條目的復(fù)制。當(dāng)數(shù)據(jù)量較大時，相較于數(shù)據(jù)寫入量的減少，兩輪RPC的耗費(fèi)是可以容忍的。

F-CAD負(fù)載均衡的核心是實(shí)時維護(hù)分流索引表。當(dāng)節(jié)點(diǎn)數(shù)目較少時，可以通過一些簡單的數(shù)據(jù)結(jié)構(gòu)和排序算法來實(shí)現(xiàn)基于Per字段的實(shí)時排序，但是在真實(shí)的分布式系統(tǒng)中節(jié)點(diǎn)數(shù)目往往超過了上萬個，很難做到實(shí)時性，接下來就該問題給出一個高效的解決方案。

2.3 實(shí)時維護(hù)分流索引表

當(dāng)節(jié)點(diǎn)數(shù)據(jù)較大時，需要實(shí)現(xiàn)對key、value存儲的同時還要對key值排序。我們選擇紅黑樹作為底層數(shù)據(jù)結(jié)構(gòu)，因?yàn)闊o論是查找、插入還是排序，紅黑樹都有著很高的性能表現(xiàn)。我們使用CPP STL標(biāo)準(zhǔn)庫中的map容器來實(shí)現(xiàn)，map底層是一棵紅黑樹，每一個唯一的key值對應(yīng)一個value值，正好對應(yīng)索引表的key-value結(jié)構(gòu)。并且每次插入均會按自定義進(jìn)行排序。

基于map的特性，將Per字段作為key值存儲，但由于key唯一的特性，會出現(xiàn)key重復(fù)時value被覆蓋的情況，如果為新節(jié)點(diǎn)，對應(yīng)節(jié)點(diǎn)將無法加入索引表。因此如果重復(fù)則先判斷Node字段是否一致，如果不一致則說明為新節(jié)點(diǎn)，新key默認(rèn)最小單位自增，然后加入索引表中。value存儲未交付日志條目信息(已經(jīng)提交的日志條目直接按CAD寫入規(guī)則進(jìn)行存儲、查詢)，由于需要頻繁地插入和刪除操作，這里選擇使用插入和刪除性能較高的雙向鏈表list。List中第一個結(jié)點(diǎn)為Node字段，后續(xù)每組數(shù)據(jù)包含Log字段和Frag_S信息，為了方便區(qū)分，需要將Log字段做特殊標(biāo)記。之所以會出現(xiàn)多組數(shù)據(jù)，是由于在達(dá)到持久化條件后便可以執(zhí)行下輪復(fù)制。

因?yàn)镻er字段需要實(shí)時更新，如果每輪RPC Leader節(jié)點(diǎn)依次去檢測其余節(jié)點(diǎn)的Per字段是否改變，明顯開銷過大。因此，在本文協(xié)議中，F(xiàn)ollower節(jié)點(diǎn)會定時主動判斷自身Per字段是否發(fā)生變化，如果改變，會返回給Leader節(jié)點(diǎn)一個舊的Per值、一個新的Per值和對應(yīng)的Node節(jié)點(diǎn)，根據(jù)舊的Per值，可以很快確定其在map中的位置，并找到value值，更新map。

如算法1所示，Leader節(jié)點(diǎn)通過定義一個二維數(shù)組Per_alter，存儲Follower節(jié)點(diǎn)發(fā)來的舊Per值、新Per值和Node字段，map為索引表。Per_alter非空時需要先用一個臨時數(shù)組Per_tmp存儲Per_alter，然后置空Per_alter，如此便可以快速加入工作線程Project_runing中接收Follower節(jié)點(diǎn)發(fā)來的更新，操作Per_alter數(shù)組時需要對線程Project_runing加鎖，防止拷貝給臨時數(shù)組到置空的過程中有新的Follower節(jié)點(diǎn)發(fā)來信息導(dǎo)致丟失信息。接下來就是循環(huán)判斷，新節(jié)點(diǎn)加入索引表，舊節(jié)點(diǎn)更新索引表中字段。

2.4 F-CAD節(jié)流方案

當(dāng)達(dá)到圖2所示的復(fù)制效果后，會繼續(xù)對尚未寫入全量數(shù)據(jù)的節(jié)點(diǎn)繼續(xù)進(jìn)行數(shù)據(jù)補(bǔ)全并且刪除校驗(yàn)片段，但是如此先前寫入的校驗(yàn)片段便是多余的寫入，并且由于全量數(shù)據(jù)寫入到F+1個節(jié)點(diǎn)，已經(jīng)很大程度上實(shí)現(xiàn)了均衡和高性能，因此系統(tǒng)推薦用戶用部分節(jié)點(diǎn)全量復(fù)制的方式以節(jié)省開支。通過定義一個整數(shù)參數(shù)x(0≤x≤F)，以供用戶在節(jié)能和高性能之間進(jìn)行選擇，用戶可以選擇F+x+1個節(jié)點(diǎn)全量復(fù)制，較小的x代表較小的寫入資源和存儲資源，但是也意味著較少的節(jié)點(diǎn)供用戶可讀，反之較大的x則代表用戶在讀取數(shù)據(jù)時表現(xiàn)出更高的性能。

算法1實(shí)時維護(hù)分流日志表

輸入：Per_alter,map

#define min_double 0.01;

if(Per_alter.size() == 0)

break;

else{

∥工作線程加鎖

Project_runing.mutex.lock();

vectorPer_tmp = Per_alter;

∥置空Per_alter

vector().swap(Per_alter);

if(Per_alter.size() == 0)

∥Per_alter置空后調(diào)用回調(diào)釋放鎖，開始檢測Per字段的改變

基層醫(yī)療機(jī)構(gòu)因發(fā)展空間、薪酬待遇、地理環(huán)境等特點(diǎn)難以吸引醫(yī)學(xué)畢業(yè)生從事基層醫(yī)療工作，相關(guān)研究表明，只有五分之一的醫(yī)學(xué)生愿意從事基層醫(yī)療[22]。關(guān)于免費(fèi)醫(yī)學(xué)生職業(yè)發(fā)展、專業(yè)認(rèn)同影響因素也逐漸被研究者重視。有研究表明，生命意義感對免費(fèi)醫(yī)學(xué)生專業(yè)承諾存在影響[23]，也有觀點(diǎn)認(rèn)為“從事基層醫(yī)療工作者工資高”、“不履約者記錄誠信檔案”對免費(fèi)醫(yī)學(xué)生留任基層醫(yī)療工作存在影響[24]，也有教育者通過開設(shè)職業(yè)生涯規(guī)劃課程，幫助免費(fèi)醫(yī)學(xué)生設(shè)計(jì)適宜的職業(yè)發(fā)展目標(biāo)，對提升免費(fèi)醫(yī)學(xué)生專業(yè)認(rèn)同取得較好的干預(yù)效果[25]。但目前這方面的研究還較為匱乏，未來還需進(jìn)一步加強(qiáng)。

Project_runing.mutex.unlock();

for(int i = 0;i

{∥通過迭代器尋找key對應(yīng)的下標(biāo)

auto it = map.find(Per_tmp[i]);

∥沒有找到對應(yīng)的key

if(it == map.end()){∥開辟臨時空間li暫存map索引表value值

listli;

li.push_back(Per_tmp[i][2]);

continue;

}

∥找到了對應(yīng)的key

while(map.find(Per_tmp[i][0])!=map.end())

{∥防止重復(fù)的key

Per_tmp[i][0] += min_double;

}

map[Per_tmp[i][0]] = it.second;

}

}

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

3.1 實(shí)驗(yàn)平臺

實(shí)驗(yàn)基于ebay的NuRaft一致性協(xié)議進(jìn)行改進(jìn)，本實(shí)驗(yàn)通過一臺物理主機(jī)搭建了多個虛擬平臺，物理主機(jī)的CPU為12核，內(nèi)存為16 GB，硬盤為1 TB SSD。虛擬平臺采用Ubuntu 14.04.6系統(tǒng)，CPU為2核、1GB內(nèi)存，糾刪碼庫為Jerasure 2.0。

3.2 實(shí)驗(yàn)結(jié)果

為了體現(xiàn)加入糾刪碼之后的優(yōu)缺點(diǎn)，分別在N=5、N=7的配置下進(jìn)行了實(shí)驗(yàn)，當(dāng)N=5時，使用(2,3)-RS碼；當(dāng)N=7時，使用(3,4)-RS碼。

通過實(shí)驗(yàn)分別對比在不同節(jié)點(diǎn)個數(shù)下，同步持久化(sync)、CAD、F-CAD協(xié)議在達(dá)到單調(diào)可讀條件時的寫入延遲，由于異步持久化(async)無法滿足嚴(yán)格的單調(diào)性，所以本實(shí)驗(yàn)無需對異步持久化進(jìn)行對比。

圖3和圖4分別顯示了N=5、N=7下不同寫入負(fù)載大小對應(yīng)的寫入延遲。可以看到當(dāng)單次寫入負(fù)載小于2 kB時，3種協(xié)議延遲類似，此時延遲主要由磁盤I/O控制，由于寫入的數(shù)據(jù)量太小，即使F-CAD可以節(jié)省刷新到磁盤的數(shù)據(jù)量，但由于F-CAD會增加I/O操作，所以三個協(xié)議在延遲上沒有太大的區(qū)別。當(dāng)單次寫入負(fù)載變大時，可以看到F-CAD有明顯的優(yōu)勢。此時網(wǎng)絡(luò)流量和磁盤I/O都會影響延遲，由于F-CAD可以極大地節(jié)省網(wǎng)絡(luò)成本和磁盤I/O，當(dāng)N=5時，隨著寫入負(fù)載的增大，減少寫入延遲增大，當(dāng)負(fù)載為8 kB時有明顯的區(qū)別，64 kB時與sync相比可減少47%的寫入延遲，與CAD相比可減少33%的寫入延遲，平均減少約35%的寫入延遲。當(dāng)N=7時，負(fù)載為64 kB時與sync相比可減少54%的寫入延遲，與CAD相比可減少45%的寫入延遲，平均可以減少約40%的寫入延遲。

圖3 5節(jié)點(diǎn)下不同一致性協(xié)議的寫入延遲對比Figure 3 Five nodes write delay comparison

圖4 7節(jié)點(diǎn)下不同一致性協(xié)議的寫入延遲對比Figure 4 Seven nodes write delay comparison

通過寫入延遲的對比可以看到，在5節(jié)點(diǎn)和7節(jié)點(diǎn)下延遲相差并不大，并且7節(jié)點(diǎn)時性能更優(yōu)。因此圖5僅對比7節(jié)點(diǎn)下3種協(xié)議的吞吐量。隨著讀寫負(fù)載的增大，吞吐量先增加，達(dá)到峰值，然后下降，之所以會下降是達(dá)到閾值時由于網(wǎng)絡(luò)擁塞造成的，屬于不可避免的情況。可以看到當(dāng)讀寫負(fù)載小于4 kB時，三種協(xié)議基本一致，此時系統(tǒng)寫入的數(shù)據(jù)量太小，性能上無明顯區(qū)別。當(dāng)讀寫負(fù)載為64 kB時，sync和CAD率先達(dá)到峰值，而F-CAD還在繼續(xù)上升，在512 kB時達(dá)到峰值，這是由于F-CAD方案單個節(jié)點(diǎn)所需寫入的數(shù)據(jù)量相較于CAD和sync減少了近60%?？傮w而言，F(xiàn)-CAD較CAD和sync吞吐量提升了近120%。

圖5 7節(jié)點(diǎn)下不同一致性協(xié)議吞吐量對比Figure 5 Throughput comparison of seven nodes

F-CAD之所以能夠快速持久化，最根本的原因是F-CAD與CAD相比，所達(dá)到持久化條件需要寫入的數(shù)據(jù)量大大減少，接下來就達(dá)到持久化條件時不同節(jié)點(diǎn)數(shù)所需寫入的數(shù)據(jù)量進(jìn)行對比，此處設(shè)置N的值分別為5、7、9、…、21，其中：N=5時使用(2,3)-RS code；N=7使用(3,4)-RS code；…；N=21時糾刪碼為(10,11)-RS code。

單個節(jié)點(diǎn)達(dá)到持久化需要寫入的數(shù)據(jù)量對比如圖6所示，CAD和sync所需寫入的數(shù)據(jù)量相同，由于CAD并未對單個節(jié)點(diǎn)做寫入限制，僅在讀取時進(jìn)行限制以達(dá)到單調(diào)讀的效果。從圖中可以看到F-CAD單個節(jié)點(diǎn)所需寫入的數(shù)據(jù)量明顯要少于sync和CAD，并且隨著節(jié)點(diǎn)數(shù)的增加，這一優(yōu)點(diǎn)愈加明顯，對于單個節(jié)點(diǎn)而言，所需寫入的數(shù)據(jù)量變?yōu)樵瓉淼?/k，隨著N的增大，糾刪碼預(yù)設(shè)的k值也需增大，所以所需寫入的數(shù)據(jù)量逐漸減少。最后趨于穩(wěn)定，減少90%，由于F+k確認(rèn)節(jié)點(diǎn)的前置條件使得k不宜過大，因此會趨于穩(wěn)定。

圖6 單個節(jié)點(diǎn)所需寫入的數(shù)據(jù)量對比Figure 6 The amount of data to be written to a single node

全部節(jié)點(diǎn)所需寫入數(shù)據(jù)量對比如圖7所示(預(yù)設(shè)x=0)，以sync為基準(zhǔn)進(jìn)行對比。從圖中可以看到CAD和F-CAD所需寫入的數(shù)據(jù)量比sync有明顯減少。隨著節(jié)點(diǎn)個數(shù)的增加，CAD所需寫入的數(shù)據(jù)量略有減少，而F-CAD所需的數(shù)據(jù)量有明顯的減少，最后趨于穩(wěn)定，約減少80%。因?yàn)镃AD寫入所需的數(shù)據(jù)量為F+1，而F-CAD所需寫入的數(shù)據(jù)量為(F+k)/k，當(dāng)k=F，F(xiàn)+1/((F+k)/k)=(F+1)/2，可以看到隨著F的增大，F(xiàn)-CAD相較于CAD可以很大程度上減少總體數(shù)據(jù)寫入量。

圖7 總體寫入數(shù)據(jù)量對比Figure 7 The total amount of data written

4 結(jié)論

F-CAD是針對CAD熱讀缺陷的改進(jìn)，通過結(jié)合糾刪碼的方式減少熱讀所需的數(shù)據(jù)量，總體數(shù)據(jù)寫入量減少為N/k，單個節(jié)點(diǎn)的數(shù)據(jù)寫入量減少為1/k，從而達(dá)到快速持久化的效果。由于加入糾刪碼會增加單節(jié)點(diǎn)故障的概率，針對這一問題，提出一個高效的負(fù)載均衡方案。同時通過用戶預(yù)設(shè)的x值減少了數(shù)據(jù)的總體寫入量，可以減少(F+1+x+(F-x)N/k)/N的數(shù)據(jù)寫入量，大量節(jié)省了網(wǎng)絡(luò)和存儲資源，并且隨著節(jié)點(diǎn)個數(shù)的增加優(yōu)勢會愈加明顯。

F-CAD雖然有效解決了CAD熱讀缺陷的問題。但是，由于結(jié)合糾刪碼，Leader節(jié)點(diǎn)寫入所需確認(rèn)節(jié)點(diǎn)數(shù)由F變?yōu)镕+k，使得當(dāng)前需要互相通信的節(jié)點(diǎn)數(shù)目增加，并且加入糾刪碼也會使得整體寫入流程變得相對煩瑣，未來將在這兩方面進(jìn)行改進(jìn)。