李 乾 胡玉鵬 葉振宇 肖 葉 秦 拯

(湖南大學信息科學與工程學院 長沙 410082)(qianli160@hnu.edu.cn)

由于糾刪碼具備高可用性和高存儲空間有效性的特點，采用糾刪碼為分布式存儲系統(tǒng)以及數(shù)據(jù)中心[1-4]提供數(shù)據(jù)持久性已成為約定俗成的標準.糾刪碼把大數(shù)據(jù)對象劃分成多個小的數(shù)據(jù)塊，然后將這些小的數(shù)據(jù)塊通過編碼生成多個校驗塊，最后將這些數(shù)據(jù)塊和校驗塊部署在不同存儲群集的存儲節(jié)點上.

數(shù)據(jù)更新在分布式存儲系統(tǒng)中很常見[5-8].在許多企業(yè)的服務器和網(wǎng)絡文件系統(tǒng)中，更新請求常常主導了寫入工作負載(通常超過90%)[9-10].在典型的最大距離可分(maximum distance separable, MDS)MDS(n,k)糾刪碼存儲系統(tǒng)中，1個數(shù)據(jù)塊的更新請求涉及到n-k個校驗塊的更新.根據(jù)糾刪碼更新過程中是否有傳輸整個數(shù)據(jù)塊，可以將更新分為2類：基于raid的更新和基于增量的更新.其中，基于raid的更新方案需要在數(shù)據(jù)節(jié)點和校驗節(jié)點之間傳輸整個數(shù)據(jù)塊，為了完成對數(shù)據(jù)節(jié)點的更新，數(shù)據(jù)節(jié)點首先需要收集所有新的數(shù)據(jù)塊，然后重新計算更新后的校驗塊，并將其傳到相應的校驗節(jié)點.基于增量的更新方案只需要將數(shù)據(jù)節(jié)點上數(shù)據(jù)增量(數(shù)據(jù)塊修改的部分)通過廣播的方式傳輸?shù)矫恳粋€校驗節(jié)點，相比之下，基于增量的更新可以節(jié)省更多的IO操作和網(wǎng)絡帶寬.然而，頻繁的數(shù)據(jù)更新也會導致巨大的IO操作和帶寬開銷.尤其在使用糾刪碼的鍵值存儲系統(tǒng)中，對鍵值數(shù)據(jù)進行密集的小型更新會導致巨大的IO操作和昂貴的網(wǎng)絡流量[7,11-15].

提高糾刪碼的更新效率具有十分重要的意義[16].最近一些研究工作者投入了大量精力來優(yōu)化糾刪碼更新性能，以減少IO操作和降低網(wǎng)絡時延[6,17-19].在現(xiàn)有的更新方案中，如CodFS[17]和Azure[20]，采用追加式更新方式，或采用替換式更新和追加式更新的混合方式.一些研究者試圖通過優(yōu)化更新順序和更新過程來減少網(wǎng)絡傳輸開銷[6,18-19].

從網(wǎng)絡性能角度來看，數(shù)據(jù)增量最好是能夠沿著數(shù)據(jù)節(jié)點與校驗節(jié)點之間的最佳網(wǎng)絡路徑進行傳輸.雖然當前的路由算法能夠可靠地處理分布式存儲系統(tǒng)的大量網(wǎng)絡流量[21-22]，但是數(shù)據(jù)更新路由技術缺乏對異構(gòu)存儲系統(tǒng)(異構(gòu)是指系統(tǒng)中的存儲節(jié)點的吞吐量、IO速率不同，以及各段網(wǎng)絡鏈路的有效帶寬均不同)的深入研究，從而導致網(wǎng)絡資源利用率不高.因此，優(yōu)化大規(guī)模分布式存儲系統(tǒng)路由極為重要，需要深入研究糾刪碼存儲系統(tǒng)中數(shù)據(jù)更新路由.為了設計多目標路由優(yōu)化更新算法，包括內(nèi)存IO速率和其他服務質(zhì)量(quality of service, QoS)指標，如時延和帶寬，本文提出一種基于蟻群優(yōu)化算法的多數(shù)據(jù)節(jié)點更新方案(ant colony optimization algorithm based multiple data nodes update scheme, ACOUS)，ACOUS采用2階段的數(shù)據(jù)更新過程來優(yōu)化多數(shù)據(jù)節(jié)點的更新路由，并且使用基于多目標蟻群優(yōu)化更新路由算法(multi-objective ant colony optimization update routing algorithm, MACOU)建立的更新樹進行數(shù)據(jù)增量的收集和校驗增量的分發(fā).

具體而言，所提出的ACOUS方案采用集合式數(shù)據(jù)更新模式，主要包含2個階段：在第1階段，數(shù)據(jù)更新由數(shù)據(jù)節(jié)點觸發(fā).可以有多個數(shù)據(jù)節(jié)點(最多k個)進行更新，而其中的1個節(jié)點將被選為集合節(jié)點，其他所有數(shù)據(jù)節(jié)點計算數(shù)據(jù)增量并根據(jù)MACOU算法將數(shù)據(jù)增量發(fā)送到集合節(jié)點.在第2階段，集合節(jié)點根據(jù)MACOU算法建立的多目標更新樹，將較驗增量依次分發(fā)到相應的校驗節(jié)點.

本文的主要貢獻有3個方面：

1) 針對大規(guī)模異構(gòu)糾刪碼存儲系統(tǒng)的內(nèi)存吞吐量和跨節(jié)點鏈路帶寬不相等的問題，本文提出的ACOUS是第一個深入研究異構(gòu)糾刪碼存儲系統(tǒng)中多數(shù)據(jù)節(jié)點更新過程和更新路由的工作.由于蟻群算法在解決QoS路由問題上的廣泛應用[23]，因此本文使用多目標蟻群優(yōu)化算法來提高糾刪碼更新效率.

2) 分別定量分析了集合式更新和分布式更新方式下的數(shù)據(jù)更新IO操作數(shù)量和數(shù)據(jù)傳輸開銷，分析了多個數(shù)據(jù)節(jié)點的更新路由問題.

3) 開發(fā)了一個原型系統(tǒng)，進行了大量實驗以評估在典型數(shù)據(jù)中心網(wǎng)絡拓撲下ACOUS的性能.實驗結(jié)果表明，本文提出的MACOU更新算法優(yōu)于TA-Update[5]，在保證收斂性的前提下顯著提高了更新效率.

1 背景及相關工作

本節(jié)先介紹糾刪碼以及蟻群優(yōu)化路由算法的原理，然后介紹目前常用的糾刪碼的更新方法.

1.1 糾刪碼和蟻群優(yōu)化路由算法

由于分布式存儲系統(tǒng)有持久性和存儲效率的需求，糾刪碼在大規(guī)模存儲系統(tǒng)的應用成為研究焦點.眾所周知，里德-所羅門碼RS(n,k)[24](reed solomon codes, RS)糾刪碼首先將一個大小為D字節(jié)的文件分為k個大小相等的數(shù)據(jù)塊di(1≤i≤k)，每個數(shù)據(jù)塊大小為Dk字節(jié).然后，這些等大的數(shù)據(jù)塊通過編碼生成k個數(shù)據(jù)塊和n-k個校驗塊，這些數(shù)據(jù)塊和校驗塊組成一組(稱為條帶Stripe)，分布在n個不同的存儲節(jié)點(D1…Dk;P1…Pn-k)中，這n個節(jié)點屬于不同的群集，以此來最大限度地提高系統(tǒng)的可靠性.每個校驗塊pj(1≤j≤n-k)根據(jù)式(1)進行計算，其中表示di到pj的系數(shù).基于這種線性編碼，n個塊中任何不多于k個塊出現(xiàn)故障就可以重建整個原始文件.

(1)

(2)

蟻群算法是一種啟發(fā)式智能優(yōu)化算法，可以用來在圖中尋找最優(yōu)路徑，該算法起源于在環(huán)境變化后，螞蟻通過感知其他螞蟻留下的信息素這種相互合作方式快速找到到達食物源的最短路徑.蟻群算法已經(jīng)被用來解決一系列組合優(yōu)化問題，如最短路徑問題、最優(yōu)任務分配問題、QoS路由問題等[23].其原理是每只螞蟻在爬行的過程中都會留下信息素，每條路徑上的信息素隨著時間的推移不斷增加或減少，所有的螞蟻在爬行時更傾向于選擇信息素更多的路徑.定義時刻t+1節(jié)點i到節(jié)點j的路徑上的信息素的數(shù)量為

τij(t+1)=(1-ρ)τij(t)+Δτij(t),

(3)

(4)

每只螞蟻在爬行的過程中，當下一時刻有多條路徑可以選擇時，螞蟻選擇某條路徑的概率又會受到可選路徑上信息素的量和全局啟發(fā)式因子的影響，式(5)說明了螞蟻從節(jié)點i移動到節(jié)點j的公式，這個公式也稱為狀態(tài)轉(zhuǎn)移公式.

(5)

其中，φk(i)表示節(jié)點i的下一跳候選集，ηij是螞蟻從節(jié)點i移動到節(jié)點j的全局啟發(fā)式因子，α和β分別表示信息素和全局啟發(fā)式因子的權(quán)重.通過這種方式，每條路徑上的信息素的數(shù)量不斷地增加或者減少.最終所有的螞蟻都會沿著最短的那條路徑爬行，這也稱為蟻群算法的收斂性和正反饋機制.

1.2 相關工作

目前存在2種刪除糾刪碼的更新方案，分別是基于raid的更新和基于delta的更新.基于raid的更新方案需要在數(shù)據(jù)節(jié)點和校驗節(jié)點之間傳輸整個數(shù)據(jù)塊.基于delta的更新只需要在數(shù)據(jù)節(jié)點和校驗節(jié)點之間傳輸原數(shù)據(jù)塊和新數(shù)據(jù)塊之間不同的部分.與基于raid的更新方案相比，基于delta的更新方案數(shù)據(jù)傳輸量更小，后者數(shù)據(jù)更新效率更高.因此，本文采用基于delta的更新方案.在基于delta的更新方案中，又存在3種更新方式，分別為覆蓋式更新、追加式更新和混合式更新.

覆蓋式更新方式通過利用新數(shù)據(jù)直接覆蓋原始數(shù)據(jù)塊和校驗塊，實現(xiàn)了數(shù)據(jù)的實時更新.因為覆蓋式更新能夠確保數(shù)據(jù)的一致性和恢復效率，所以它被廣泛地應用于糾刪碼的更新.但是為了完成檢驗塊的更新，覆蓋式更新方式又引入了大量的IO操作和網(wǎng)絡開銷[5].

混合式更新方式是在允許數(shù)據(jù)塊和校驗塊異步更新的前提下，數(shù)據(jù)塊采用覆蓋式更新，校驗塊采用追加式更新.這種更新方式可以確保數(shù)據(jù)塊的訪問效率以及校驗塊的更新效率.比如PL[26]，PLR[17]采用覆蓋式更新方式，直接用新的數(shù)據(jù)覆蓋原始數(shù)據(jù)塊，然后將校驗增量追加在校驗塊之后.

總而言之，以上3種更新方式中，數(shù)據(jù)節(jié)點必須向校驗節(jié)點發(fā)送數(shù)據(jù)增量，以保證數(shù)據(jù)一致性.而ACOUS與現(xiàn)有的方法不同，不是關注單個節(jié)點的數(shù)據(jù)更新操作，而是優(yōu)化整個更新過程中的IO開銷，并且致力于提高數(shù)據(jù)傳輸效率，針對多個QoS指標提高糾刪碼更新效率.

多約束QoS路由問題是一個典型NP-C問題[23].由于蟻群算法具備魯棒性和收斂性，已成功地應用于求解許多離散優(yōu)化問題.蟻群優(yōu)化技術在解決QoS路由問題中得到廣泛的應用.文獻[27]采用基于蟻群優(yōu)化的路由技術，將節(jié)點的實時位置和負載2個參數(shù)作為路由指標，以提高網(wǎng)絡的QoS性能.文獻[28]提出了一種改進的基于蟻群算法的動態(tài)源路由方案，該方案可以在較低的時延、較低的路由開銷以及較低的能耗的情況下產(chǎn)生高數(shù)據(jù)包投遞率.文獻[29]利用蟻群算法提高以信息為中心的網(wǎng)絡性能.

2 挑 戰(zhàn)

通常情況，在大規(guī)模分布式存儲系統(tǒng)中執(zhí)行碎片化的、小數(shù)據(jù)塊的糾刪碼更新操作可能導致性能顯著下降.這是因為數(shù)據(jù)更新涉及到多個校驗節(jié)點的更新，這不可避免地會導致相當大的IO和帶寬開銷.尤其是對于分布式存儲系統(tǒng)的更新操作，例如，云存儲系統(tǒng)、分布式內(nèi)存鍵值存儲系統(tǒng)和塊存儲系統(tǒng)，大多數(shù)都是寫請求，這將導致較大的時延.云存儲系統(tǒng)Azure[20]采用了基于日志的更新方案來分攤更新開銷.分布式鍵值存儲系統(tǒng)中的更新操作可能會導致一些小的更新，這將引入巨大的編碼操作和網(wǎng)絡流量.例如，在基于Memcached的Cocytus[11]中，對于密集的小規(guī)模更新操作，即set操作，需要頻繁地修改分布在多個校驗節(jié)點上的數(shù)據(jù).對于糾刪碼的磁盤陣列或塊存儲系統(tǒng)文件，如結(jié)構(gòu)化數(shù)據(jù)庫文件和虛擬機文件系統(tǒng)，對一個文件的更新可能導致多個節(jié)點在不同的集群中同時需要進行更新操作[8].糾刪碼更新主要面臨如下挑戰(zhàn)：

1) 當有多個數(shù)據(jù)節(jié)點需要更新時，這些節(jié)點之間的協(xié)作會導致大量的有限域運算和網(wǎng)絡流量.根據(jù)式(2)，雖然增量和編碼計算可以并行地在所有數(shù)據(jù)節(jié)點上高效執(zhí)行以完成更新，但如何協(xié)調(diào)更新的數(shù)據(jù)節(jié)點，以最小的網(wǎng)絡流量將增量發(fā)送到相應的節(jié)點仍是一個難題.

3 多個節(jié)點更新的路由問題分析

3.1 糾刪碼存儲系統(tǒng)多數(shù)據(jù)更新的2種模式

當有多個數(shù)據(jù)節(jié)點需要更新時，有2種更新模式：分布式和集合式.圖1(a)顯示了分布式更新模式的更新過程，其中用于更新的每個數(shù)據(jù)節(jié)點分別向每個校驗節(jié)點發(fā)送Δdi.圖1(b)顯示了集合式更新模式的更新過程，所有更新的數(shù)據(jù)節(jié)點Di在完成更新之后計算Δdi，并將其發(fā)送到集合節(jié)點(rende-zvous node, RN)，由集合節(jié)點計算Δpj，然后將Δpj發(fā)送到相應的校驗節(jié)點Pj.

Fig. 1 Two update patterns for multiple data nodes圖1 多數(shù)據(jù)節(jié)點更新的2種模式

表1顯示如果u(1≤u≤k)個數(shù)據(jù)塊需要更新，2種更新模式產(chǎn)生的數(shù)據(jù)傳輸開銷和數(shù)據(jù)讀寫開銷.從表1可以看出，2種模式在并行計算下的IO開銷幾乎相同.分布式更新模式下的數(shù)據(jù)傳輸開銷隨著u的增加迅速超過了集合模式中的數(shù)據(jù)傳輸開銷，因此本文采用集合式更新模式來完成多節(jié)點更新問題.

Table 1 The Overhead of Two Update Patterns When u Data Nodes for Update

3.2 路由的QoS度量

本文的目標是圍繞3個典型的QoS指標進行研究，以提高大規(guī)模異構(gòu)糾刪碼存儲系統(tǒng)中多個數(shù)據(jù)節(jié)點的更新效率.

1) 距離.節(jié)點s到節(jié)點d之間的距離D(s,d)是根據(jù)2個節(jié)點之間的跳數(shù)計算，距離通常被用來構(gòu)建數(shù)據(jù)傳輸?shù)淖钚∩蓸?，由于網(wǎng)絡的物理拓撲結(jié)構(gòu)在一段的時間內(nèi)保持穩(wěn)定，TA-Update[5]基于Prim算法以網(wǎng)絡距離作為度量來構(gòu)造更新樹，通過更新樹可以反映節(jié)點之間的路徑長度，同時更新樹的構(gòu)造是以數(shù)據(jù)節(jié)點為根節(jié)點，采取自上而下的數(shù)據(jù)傳輸方式，最終的目的是使得整個更新過程數(shù)據(jù)傳輸距離最小.網(wǎng)絡距離越小表示數(shù)據(jù)傳輸?shù)奶鴶?shù)較少，意味著數(shù)據(jù)傳輸時延較小.

2) 帶寬.帶寬是衡量網(wǎng)絡中鏈路容量的指標.數(shù)據(jù)傳輸?shù)钠款i由傳輸路徑上的最小帶寬確定[30]，由于存儲節(jié)點之間鏈路上帶寬是異構(gòu)的，樹狀的拓撲結(jié)構(gòu)由此形成，文獻[30]利用帶寬來構(gòu)造再生樹，并將再生樹的構(gòu)建和再生碼進行結(jié)合，從而有效利用存儲節(jié)點之間每條鏈路上的可用帶寬，降低網(wǎng)絡流量，提高再生碼的恢復效率.但實時可用帶寬難以獲得，因此，本文利用平均帶寬B(e)作為鏈路e的帶寬，B(s,d)表示路徑p(s,d)上的最小平均帶寬.

B(s,d)=min{B(e),e∈path(s,d)}.

(6)

3) 時延.本文采用時延作為衡量更新效率的關鍵指標.時延越小代表數(shù)據(jù)傳輸效率越高.路徑path(s,d)上的總時延delay(s,d)是處理時延dproc、傳輸時延dtrans和傳播時延dprop之和.式(7)表示總時延的計算方式，本文沒有考慮計算排隊時延，因為排隊時延超出了本文的討論范圍.

(7)

距離、帶寬、時延這3個因素是影響糾刪碼更新的主要網(wǎng)絡因素[5]，但是TA-Update僅以距離為度量并基于Prim算法來構(gòu)造更新樹，存在局限性.本文利用多目標蟻群優(yōu)化算法可以綜合考慮這3個因素，實現(xiàn)多目標優(yōu)化，以此提高糾刪碼的更新效率.

4 基于蟻群優(yōu)化的多數(shù)據(jù)節(jié)點更新方案

本節(jié)將針對3.2節(jié)列出的3個QoS指標詳細說明ACOUS更新方案.首先介紹2階段集合式更新模式的過程，然后介紹多目標蟻群優(yōu)化更新路由算法.

4.1 集合式更新的2個階段

Fig. 2 The two-stage rendezvous update scheme圖2 集合式更新的2個階段

ACOUS的主要思想是采用2階段集合式更新方案，多目標更新樹實現(xiàn)對RS(k+r,k)編碼高效的數(shù)據(jù)增量收集和校驗增量分發(fā).

4.2 多目標蟻群優(yōu)化更新路由算法

表2解釋了算法中涉及的符號.式(8)描述了節(jié)點s和節(jié)點d之間的最佳更新路徑的問題.其中節(jié)點的權(quán)重代表節(jié)點的處理時延以及傳輸時延的大小，邊的權(quán)重代表傳播時延的大小.

arg min{delay(s,d)}, s.t.B(e)≥Breq,
e∈path(s,d).

(8)

Table 2 Ant Colony Algorithm Parammeters表2 蟻群算法參數(shù)

算法1詳細描述了MACOU算法，其目的是在帶寬約束下搜索從節(jié)點s到節(jié)點d的最小時延的路徑.

算法1.多目標蟻群優(yōu)化更新路由算法MACOU.

輸入：網(wǎng)絡拓撲圖G(V,E)、每個節(jié)點的權(quán)重Wi(i∈V)和每個邊的權(quán)重We(e∈E)、每條邊的帶寬B(i,j)和最小帶寬Breq約束、源節(jié)點s和目標節(jié)點d；

輸出：滿足最小帶寬約束下時延最小的路徑p(s,d).

① 初始化α,β,λ,k,m,i=s,converge=false;

② 初始化每條路徑上的信息素τ;

③ 計算每個節(jié)點i到目的節(jié)點d的距離D(i,d),i∈V;

④ for (m=0,m

⑤ for (k=0,k

⑥ whilei≠d或φ(i)≠? do

⑦ for eachj,j∈φ(i) do

⑧ 計算概率Pij;

⑨ end for

⑩ 從Pij中選擇最大的Piv,v∈φ(i);

MACOU算法首先根據(jù)輸入初始化行①②中每個參數(shù)的值，行③計算每個節(jié)點到目標節(jié)點的距離.

η(i,j)=(1(D(j,d))β×(1(Wi+We))λ,
j∈φ(i).

(9)

例1.圖3說明了MACOU算法的過程.圖3(a)是多目標更新樹，其中V1是集合節(jié)點，其他所有節(jié)點為校驗節(jié)點.在圖3(a)中節(jié)點權(quán)重代表時延的總和，邊的權(quán)重代表帶寬的大小.在實際的分布式存儲系統(tǒng)中，所有節(jié)點都通過樹狀拓撲結(jié)構(gòu)連接，其中一些節(jié)點連接底層交換機，然后底層交換機連接上層交換機.節(jié)點之間的所有路徑都通過交換機中繼.每條邊的權(quán)值表示其可用平均帶寬(單位是Mbps).每條邊的權(quán)值表示其可用平均帶寬.假設最小帶寬要求是Breq=50 Mbps，本文需要找到一個具有最小時延的更新樹，其每條邊e應滿足B(e)≥50 Mbps.本文提出的更新路由算法MACOU可以在網(wǎng)絡初始化過程中進行部署，因此，每個數(shù)據(jù)節(jié)點能夠在一段時間內(nèi)保持到每個校驗節(jié)點的最優(yōu)路由，直到下一次網(wǎng)絡重新配置.圖3(a)中的黑色粗線箭頭和所有節(jié)點的邊構(gòu)造了以V1為根節(jié)點的多目標更新樹.

圖3(b)描繪了路徑p(V1,V7)的搜索步驟.螞蟻從V1開始，在初始信息素相同的情況下，由于B(V1,V2) <50 Mbps，因此下一跳是V3.類似地，螞蟻從V3出發(fā)，距離D(V2,V7)=2，距離D(V4,V7)=D(V5,V7)=1.但是，V5的時延大于V4.所以，螞蟻選擇V4作為下一跳.最后，V4可以直接到達V7.由于MACOU的正反饋機制，選擇路徑：V1→V3→V4→V7的螞蟻數(shù)量越多，該路徑上的信息素就越多.因此，經(jīng)過多次迭代后，從V1到V7的路徑最終收斂于V1→V3→V4→V7，且這條路徑滿足最小更新時延和帶寬約束.

Fig. 3 A case study of multi-objective update tree construct with MACOU圖3 基于MACOU算法的多目標更新樹

類似地，本文可以找到V1到其他校驗節(jié)點最佳更新路徑，并由此構(gòu)造出類似圖3(a)中的更新樹.值得注意的是，第1階段的數(shù)據(jù)增量收集也可以利用MACOU算法和校驗增量分發(fā)的方式構(gòu)建.MACOU與圖3(a)中基于Prim算法的TA-Update方案形成的虛線箭頭組成的更新樹相比，前者具備更小的更新時延.例如，需要搜索從V1到V2的路徑，由于帶寬約束，通過MACOU算法搜索出的路徑是V1→V3→V2，比TA-Update搜索的路徑V1→V2效率更高.2條路徑之間的總時延隨傳輸數(shù)據(jù)包大小的增大而增大，例如，傳輸大小為1～9 MB的數(shù)據(jù)包，路徑V1→V3→V2和路徑V1→V2的時延分別是0.03～0.27 ms和0.033～0.3 ms.

5 集合節(jié)點的選擇

(10)

算法2.ORN選擇過程.

輸入：網(wǎng)絡拓撲G(V,E)、每個節(jié)點的權(quán)重Wi(i∈V)和每條邊的權(quán)重We(e∈E)、每條邊上的帶寬B(i,j)、需要更新的數(shù)據(jù)節(jié)點的集合D和校驗節(jié)點的集合P；

輸出:DORN.

① 初始化sumdelay[i]=0;

② for eachDiinD′ do

③ for eachDk(Dk≠Di) inD′ do

④ 使用算法1計算時延delay(Di,Dk);

⑤sumdelay[i]=sumdelay[i]+

delay(Di,Dk);

⑥ end for

⑦ for eachPjinPdo

⑧ 使用算法1計算時延delay(Di,Pj);

⑨sumdelay[i]=sumdelay[i]+

delay(Di,Pj);

⑩ end for

本文通過在原型系統(tǒng)上進行實驗，以驗證ORN和RRN的更新效率.如圖4所示，隨著更新節(jié)點數(shù)量的增加，在忽略集合節(jié)點選擇計算的情況下，ORN的時延比RRN的時延更低.在存在30多個節(jié)點原型存儲系統(tǒng)中，基于MACOU算法獲得的路由信息，算法2的選擇過程不超過0.01 s.值得注意的是，在網(wǎng)絡重新配置之前，MACOU算法為每個數(shù)據(jù)節(jié)點獲取的路由信息在一段時間內(nèi)不會頻繁更新.因此，考慮到計算資源的普遍可用性，大規(guī)模存儲系統(tǒng)最好選擇ORN.由于計算成本可以忽略，本文在第6節(jié)中對2個不同的集合節(jié)點的更新時延進行了更多的評估，由于節(jié)點的更新序列是隨機的，ORN基本均勻分布在不同的節(jié)點上，可以實現(xiàn)負載均衡，因此ORN節(jié)點的性能不會成為糾刪碼更新效率的瓶頸.

Fig. 4 Comparisons of update delay under different RNs圖4 不同RN下的時延

6 實驗評估

本文在基于存儲集群的騰訊云虛擬機上實現(xiàn)了ACOUS更新方案，并研發(fā)了一個原型系統(tǒng)(1)https://github.com/599020328/acous來評估本文提出的方案.同時本文在更大的網(wǎng)絡拓撲(大于200個節(jié)點)上進行仿真，以進一步評估本文的更新方案.屬于同一條帶的數(shù)據(jù)節(jié)點和校驗節(jié)點通常被隨機部署在不同的集群中.由于ORN中集合節(jié)點選擇操作的時延通常是以微秒為單位，與數(shù)據(jù)更新時延相比可以忽略，因此本文在下面的評估中忽略了計算時間.

6.1 原型系統(tǒng)評估

本文的原型存儲集群由多達35臺騰訊云虛擬機(Ubuntu服務器14.04.1 LTS,4 GB RAM和雙核Intel Xeon Cascade Lake (2.5 GHz))組成，它們通過帶寬為1.5 Gbps的網(wǎng)絡連接在同1個子網(wǎng)中.本文利用騰訊云的性能監(jiān)測工具來估計平均帶寬.

在圖5中，我們提供了不同方案下更新時延的廣泛比較.如圖5(a)所示，當r=3時更新時延隨更新數(shù)據(jù)節(jié)點數(shù)量k增加的情況.如圖5(b)所示，當k=5時，更新時延隨校驗節(jié)點數(shù)量r增加的情況.隨著數(shù)據(jù)節(jié)點或校驗節(jié)點數(shù)量的增加，將會有更多的數(shù)據(jù)增量和校驗增量沿著本文方案中最優(yōu)更新樹有效地傳遞.因此，當k或r增加時，本文的方案能夠減少更多的更新時延.與TA-Update相比，MACOU方案降低了30%～32%的更新時延.

如圖5(c)所示，本文的原型系統(tǒng)在有5個數(shù)據(jù)節(jié)點和5個校驗節(jié)點需要更新的情況下，系統(tǒng)中不同節(jié)點數(shù)量下的更新時延，這些節(jié)點隨機部署在不同的存儲集群中.

隨著節(jié)點數(shù)量的增加，本文將它們安排到更多的存儲集群中以實現(xiàn)負載平衡，從而產(chǎn)生了更多的傳遞躍點和數(shù)據(jù)包中繼.因此，隨著存儲系統(tǒng)的擴展，本文的方案與ORN和MACOU結(jié)合后降低的時延從28%迅速增加到37%左右.如圖5(d)所示，隨著數(shù)據(jù)增量增加，本文的方案可以減少的時延幾乎線性增加的.

Fig. 5 Experiment in prototype system圖5 原型系統(tǒng)中的實驗

6.2 大規(guī)模網(wǎng)絡仿真

本文在基于組件的模擬器OPNET[31]上進行了大量的實驗，以評估本文在大規(guī)模異構(gòu)分布式存儲網(wǎng)絡系統(tǒng)中更新方案的性能，并且該系統(tǒng)定期執(zhí)行更新.除了構(gòu)建IO和帶寬的隨機拓撲結(jié)構(gòu)外，本文還評估了其他2種典型數(shù)據(jù)中心網(wǎng)絡拓撲的更新方案，如圖6所示，即Fat tree和DCell，這2種網(wǎng)絡拓撲結(jié)構(gòu)都有很高的網(wǎng)絡容量和健壯的連通性.在相同的條件下，本文還在相同的條件下與TA-Update方案進行對比.表3列舉了仿真系統(tǒng)的一些關鍵參數(shù).

6.2.1 不同大小數(shù)據(jù)傳輸量的系統(tǒng)更新時延

本節(jié)比較了不同數(shù)據(jù)傳輸量下更新時延的仿真結(jié)果.首先比較了在傳輸不同數(shù)據(jù)增量時，ORN和MACOU、RRN和MACOU與TA-Update方案更新效率的不同，如圖7所示，更新時延隨著傳輸數(shù)據(jù)增量的增大而增大.可以看到，與TA-Update方案相比，采用RRN和MACOU的方案可以節(jié)省大約26%的更新時延，采用ORN和MACOU方案的時延降低了18%左右.

Fig. 6 Two typical data center network topologies圖6 2種典型的數(shù)據(jù)中心網(wǎng)絡拓撲

Table 3 Experiment Parameters表3 實驗參數(shù)

Fig. 7 Delay under data delta圖7 數(shù)據(jù)增量下的時延

圖8顯示了當k=9時，更新時延隨r增加的情況.圖9顯示了當r=5時更新時延隨k增加的情況. 與圖5中原型系統(tǒng)的評估結(jié)果一致，隨著數(shù)據(jù)節(jié)點或校驗節(jié)點數(shù)量的增加，本文方案的優(yōu)勢變得更加明顯.可以看到，本文采用ORN和MACOU的方案與TA-Update相比，時延降低了30%.

Fig. 8 Delay under varying r when k=9圖8 更新時延隨r的變化

Fig. 9 Delay under varying k when r=5圖9 更新時延隨k的變化

6.2.2 不同規(guī)模的系統(tǒng)更新時延

圖10描述了當更新的數(shù)據(jù)節(jié)點和校驗節(jié)點的數(shù)量分別占總節(jié)點數(shù)量的5%時，不同大小規(guī)模下的更新時延情況.這些用于更新的節(jié)點隨機部署在定期啟動更新過程的存儲系統(tǒng)中.隨著系統(tǒng)規(guī)模的增大，TA-Update更新方案與本文采用ORN和MACOU的方案相比，TA-Update更新的時延增加得更快.圖11顯示了系統(tǒng)中只有5個數(shù)據(jù)節(jié)點和5個校驗節(jié)點進行更新時，系統(tǒng)中總節(jié)點數(shù)在不同情況下的時延.根據(jù)圖5(c)原型系統(tǒng)的評價結(jié)果，并從圖10和圖11可以看出，由于本文采用了ORN和MACOU結(jié)合的方案，隨著系統(tǒng)的擴展，糾刪碼的更新效率明顯優(yōu)于TA-Update算法.因此，當節(jié)點數(shù)超過250時，本文的方案可以將更新時延降低28%～30%.

Fig. 10 Update delay under the varying system scale圖10 不同網(wǎng)絡規(guī)模下的時延(r,k占總節(jié)點5%)

Fig. 11 Update delay under the varying system scale圖11 不同網(wǎng)絡規(guī)模下的時延(r=5,k=5)

6.2.3 不同網(wǎng)絡拓撲的更新時延

為了進一步研究本文提出的方案的適應性，如圖6所示，本文在2個典型的數(shù)據(jù)中心網(wǎng)絡拓撲結(jié)構(gòu)(即胖樹和DCell)下進行了大量的實驗.Fat tree拓撲網(wǎng)絡分為3個層次：自上而下分別邊緣層、匯聚層和核心層，其中匯聚層交換機與邊緣層交換機構(gòu)成一個pod.在圖12和圖13中給出了在不同數(shù)據(jù)中心拓撲結(jié)構(gòu)下更新時延的實驗結(jié)果.與之前的實驗結(jié)果類似，本文的方案也能夠節(jié)省幾乎相同的時延，這表明本文提出的方案具有良好的適應性.

Fig. 12 Update delay under varying scale of Fat tree圖12 不同規(guī)模的胖樹結(jié)構(gòu)下的時延

Fig. 13 Update delay under varying scale of DCell圖13 不同規(guī)模的DCell結(jié)構(gòu)下的時延

6.3 收斂性分析

如圖13所示，當本文設置MACOU算法的相關參數(shù)α=1，β=1，λ=1.6，ρ=0.4時，更新時延隨著螞蟻數(shù)量的增加而迅速減少，然后達到最佳螞蟻數(shù)量的下限，最后實現(xiàn)搜索路徑的收斂.信息素的定期更新使蟻群算法能夠快速收斂,圖14評估了本文的方案的收斂性.當圖14(a)中的總節(jié)點個數(shù)為300時，在釋放的螞蟻數(shù)約為500個時實現(xiàn)了路徑的收斂.如圖14(a)～(c)所示，在較大的網(wǎng)絡規(guī)模中通常會導致較慢的收斂.例如，圖14(b)中當pod的數(shù)量Npod分別為6和8時，最佳螞蟻數(shù)量接近250和500，而當pod數(shù)量Npod=10時，需要大約1 000個螞蟻才能完成更新路徑搜索.在圖14(d)中比較了由200個節(jié)點組成的3種網(wǎng)絡拓撲下的更新方案的收斂速度.可以看到，在DCell拓撲結(jié)構(gòu)中，由于其高效的全局連接性，本文的方案在螞蟻數(shù)量達到230左右時實現(xiàn)了最快的收斂速度.相反，由于隨機網(wǎng)絡的復雜性和冗余性，隨機網(wǎng)絡拓撲收斂速度最慢.

Fig. 14 Update delay with increasing number of ants 圖14 隨著螞蟻數(shù)量增加的更新時延

7 結(jié) 論

針對分布式糾刪碼存儲系統(tǒng)中的頻繁數(shù)據(jù)更新問題，本文嘗試考慮多個QoS度量下的多數(shù)據(jù)節(jié)點的數(shù)據(jù)更新優(yōu)化問題.本文提出的ACOUS更新方案是基于MACOU算法，采用2個階段來優(yōu)化多個數(shù)據(jù)節(jié)點更新.具體來講，在數(shù)據(jù)更新過程中，使用基于蟻群優(yōu)化路由算法構(gòu)建的多目標更新樹來實現(xiàn)數(shù)據(jù)增量的收集和校驗增量的分發(fā).在典型的數(shù)據(jù)中心網(wǎng)絡拓撲下，與TA-Update更新方案相比，大量實驗結(jié)果表明，本文的ACOUS更新方案以忽略不計的計算開銷為代價實現(xiàn)了MACOU算法收斂，從而將糾刪碼的更新時延降低26%～30%.

貢獻聲明：李乾負責論文的所有實驗和論文撰寫，胡玉鵬對論文研究方案做全面指點和論文修改，葉振宇參與論文實驗模擬驗證，肖葉參與論文后期修改，秦拯參與論文后期修改.