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

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

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

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

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

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

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

本文的主要貢獻(xiàn)有3個方面：

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

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

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

1 背景及相關(guān)工作

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

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

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

(1)

(2)

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

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

(3)

(4)

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

(5)

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

1.2 相關(guān)工作

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

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

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

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

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

2 挑 戰(zhàn)

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

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

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

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

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

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

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

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

3.2 路由的QoS度量

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

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

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

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

(6)

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

(7)

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

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

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

4.1 集合式更新的2個階段

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

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

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

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

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

(8)

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

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

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

輸入：網(wǎng)絡(luò)拓?fù)鋱DG(V,E)、每個節(jié)點(diǎn)的權(quán)重Wi(i∈V)和每個邊的權(quán)重We(e∈E)、每條邊的帶寬B(i,j)和最小帶寬Breq約束、源節(jié)點(diǎn)s和目標(biāo)節(jié)點(diǎn)d；

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

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

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

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

④ for (m=0,m

⑤ for (k=0,k

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

⑦ for eachj,j∈φ(i) do

⑧ 計(jì)算概率Pij;

⑨ end for

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

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

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

(9)

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

圖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的時(shí)延大于V4.所以，螞蟻選擇V4作為下一跳.最后，V4可以直接到達(dá)V7.由于MACOU的正反饋機(jī)制，選擇路徑：V1→V3→V4→V7的螞蟻數(shù)量越多，該路徑上的信息素就越多.因此，經(jīng)過多次迭代后，從V1到V7的路徑最終收斂于V1→V3→V4→V7，且這條路徑滿足最小更新時(shí)延和帶寬約束.

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

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

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

(10)

算法2.ORN選擇過程.

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

輸出:DORN.

① 初始化sumdelay[i]=0;

② for eachDiinD′ do

③ for eachDk(Dk≠Di) inD′ do

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

⑤sumdelay[i]=sumdelay[i]+

delay(Di,Dk);

⑥ end for

⑦ for eachPjinPdo

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

⑨sumdelay[i]=sumdelay[i]+

delay(Di,Pj);

⑩ end for

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

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

6 實(shí)驗(yàn)評估

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

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

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

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

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

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

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

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

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

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

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

Fig. 6 Two typical data center network topologies圖6 2種典型的數(shù)據(jù)中心網(wǎng)絡(luò)拓?fù)?/p>

Table 3 Experiment Parameters表3 實(shí)驗(yàn)參數(shù)

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

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

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

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

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

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

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

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

6.2.3 不同網(wǎng)絡(luò)拓?fù)涞母聲r(shí)延

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

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

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

6.3 收斂性分析

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

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

7 結(jié) 論

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

貢獻(xiàn)聲明：李乾負(fù)責(zé)論文的所有實(shí)驗(yàn)和論文撰寫，胡玉鵬對論文研究方案做全面指點(diǎn)和論文修改，葉振宇參與論文實(shí)驗(yàn)?zāi)M驗(yàn)證，肖葉參與論文后期修改，秦拯參與論文后期修改.