肖逸飛，周世杰

(電子科技大學信息與軟件工程學院 成都 611731)

糾刪碼(erasure codes)[1-2]是云存儲中一種較為先進的數(shù)據(jù)容錯技術(shù)，相較于傳統(tǒng)的多副本技術(shù)，采用糾刪碼提供數(shù)據(jù)冗余存儲，會極大地降低系統(tǒng)的存儲開銷。如QFS 文件系統(tǒng)(qunantcast file system)和MapReduce 框架的數(shù)據(jù)存儲后臺采用糾刪碼進行冗余存儲，比原來的HDFS 采用多副本技術(shù)節(jié)省了50%的存儲空間[3]。然而，糾刪碼也引發(fā)了2 個新問題：數(shù)據(jù)修復(fù)[4]和數(shù)據(jù)更新[5]。在數(shù)據(jù)更新中，由于糾刪碼提供的冗余校驗數(shù)據(jù)是多個原始數(shù)據(jù)的線性變換組合，因此，當原始數(shù)據(jù)更新時，為了保證數(shù)據(jù)一致性，其校驗數(shù)據(jù)也需要進行更新(稱為校驗更新)。根據(jù)文獻[6-7]提供的數(shù)據(jù)訪問記錄，可以得出以下兩個結(jié)論。

1) 更新非常普遍，在大約1.73 億次的寫請求中，超過91%的請求是更新數(shù)據(jù)；

2) 更新的數(shù)據(jù)量小，在所有的更新請求中，超過60%的更新小于4 KB。

數(shù)據(jù)中心由成千上萬個節(jié)點組成，其網(wǎng)絡(luò)拓撲結(jié)構(gòu)非常復(fù)雜，數(shù)據(jù)中心的數(shù)據(jù)更新性能往往受到網(wǎng)絡(luò)的限制[8]，如何降低校驗更新的網(wǎng)絡(luò)開銷是糾刪碼中亟待解決的問題。為了優(yōu)化網(wǎng)絡(luò)開銷，國內(nèi)外學者提出了很多數(shù)據(jù)更新方法。如PUM-P 算法是利用更新管理器(update manager)計算數(shù)據(jù)變化(delta 值)，并傳輸delta 值給相關(guān)的校驗節(jié)點進行更新[9]；PDN-P 算法摒棄更新管理器，直接通過數(shù)據(jù)節(jié)點計算并傳輸delta 值到相關(guān)的校驗節(jié)點[9]；TUpdate 算法發(fā)現(xiàn)傳統(tǒng)的數(shù)據(jù)傳輸模型是星型結(jié)構(gòu)，不利于充分利用網(wǎng)絡(luò)帶寬，同時容易造成單點瓶頸，因此，將傳輸模型改為樹型結(jié)構(gòu)，增加網(wǎng)絡(luò)并行度[10]。文獻[8]提出CAU(cross-rack-aware updates)算法，將數(shù)據(jù)中心的各個存儲節(jié)點按照機架(rack)分組，為了減少機架之間的網(wǎng)絡(luò)開銷，提出了2 種可選的更新方式：

1)校驗增量更新(parity-delta update)，當數(shù)據(jù)機架(專用于存放數(shù)據(jù)節(jié)點)的更新量大于校驗機架(專用于存放校驗節(jié)點)的更新量時，選擇將同一機架中的所有delta 值都匯聚到一個數(shù)據(jù)節(jié)點(數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點)，再由數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點計算并轉(zhuǎn)發(fā)校驗更新給各個相關(guān)的校驗節(jié)點；

2)數(shù)據(jù)增量更新(data-delta update)，當數(shù)據(jù)機架的更新量小于校驗機架時，分別將各個數(shù)據(jù)節(jié)點的delta 值發(fā)送給同一個校驗節(jié)點(校驗轉(zhuǎn)發(fā)節(jié)點)，再由校驗轉(zhuǎn)發(fā)節(jié)點計算校驗更新并轉(zhuǎn)發(fā)給其他校驗節(jié)點[8]。

本文的主要目標是對數(shù)據(jù)更新的網(wǎng)絡(luò)傳輸進行優(yōu)化，基于CAU 算法的思想，提出了改進算法—TAR-CAU，該算法針對更新數(shù)據(jù)量普遍較小的現(xiàn)象，借鑒tar 打包原理，提出將同一個節(jié)點中的多個更新數(shù)據(jù)打包成一個塊，再利用CAU 算法更新，從而減少網(wǎng)絡(luò)往返時間，降低發(fā)送端與接收端的更新處理頻率，提高數(shù)據(jù)更新的效率。

本文的主要研究工作有以下3 點。

1) 基于CAU 算法，提出了TAR-CAU 算法。該算法基于XOR 進行數(shù)據(jù)更新，同時，利用更新數(shù)據(jù)量小的特點，將多個更新打包傳輸，從而減少網(wǎng)絡(luò)往返次數(shù)，提高數(shù)據(jù)更新效率。

2) 實現(xiàn)原型系統(tǒng)。本文基于Go 語言在Ubuntu 18.04 平臺實現(xiàn)了TAR-CAU 原型系統(tǒng)，該系統(tǒng)包含中央控制器、算法調(diào)度器和節(jié)點代理的統(tǒng)一調(diào)度框架，不僅可以穩(wěn)定運行TAR-CAU 算法，同時，可以方便擴展并運行其他數(shù)據(jù)更新算法。

3) 驗證算法的有效性。本文基于仿真實驗和本地集群實驗，利用微軟劍橋研究院和哈佛NSR 提供的真實數(shù)據(jù)集進行實驗，與CAU 算法進行了對比，從實驗的結(jié)果來看，本文提出的算法能夠有效提高數(shù)據(jù)更新吞吐量。

1 相關(guān)工作

1.1 糾刪碼概述

糾刪碼也稱為糾錯碼，它將原始數(shù)據(jù)編碼為數(shù)據(jù)量更大的編碼數(shù)據(jù)，并能利用編碼后的部分數(shù)據(jù)恢復(fù)出原始數(shù)據(jù)。糾刪碼一般需要指定n和k兩個參數(shù)，用k份數(shù)據(jù)進行編碼，產(chǎn)生n份數(shù)據(jù)。RS 編碼是最經(jīng)典的一種糾刪碼[1]，圖1 為一個典型的RS(5, 3)的云存儲系統(tǒng)(n=5,k=3)，其中有3 個數(shù)據(jù)節(jié)點和2 個校驗節(jié)點，每個節(jié)點中的數(shù)據(jù)都按照大小固定的塊存儲(塊大小一般為1～64 MB)，編碼后的數(shù)據(jù)塊與校驗塊組成一個條帶(stripe)，大多數(shù)數(shù)據(jù)更新算法都是按照條帶順序一條一條進行更新。圖1 展示了一個條帶信息，其中，di,j表示數(shù)據(jù)塊，pi,j表示校驗塊，同一條帶中屬于同一節(jié)點的數(shù)據(jù)塊或校驗塊稱為條塊(strip)[11]。

圖1 RS(5, 3)云存儲系統(tǒng)

1.2 數(shù)據(jù)更新

糾刪碼的數(shù)據(jù)更新主要有基于RS 的更新和基于XOR 的更新。

1)基于RS 的更新?；赗S 的更新主要利用范德蒙德矩陣或柯基矩陣生成校驗數(shù)據(jù)[3]，圖2 為圖1 的編碼過程，其中，

圖2 RS (5, 3)編碼過程

編碼時，利用生成矩陣(generator matrix)左乘各個數(shù)據(jù)節(jié)點的數(shù)據(jù)向量 (d0,d1,d0)，生成碼字(d0,d1,d0,p0,p1)， 其中，p0和p1為校驗塊，表示為：

當數(shù)據(jù)i更新時，用替換di， 或在數(shù)據(jù)節(jié)點i中計算delta 值(⊕di)，然后將delta 值傳輸給pi所在的校驗節(jié)點，最后計算出最新的校驗數(shù)據(jù)。本文參考的CAU 算法就是基于RS 的數(shù)據(jù)更新。

2)基于XOR 的更新。從式(1)可以看出，基于RS 的更新會產(chǎn)生大量的乘法運算(αj,idi)，消耗CPU 資源。因此，可以利用有限域(galois field)將所有的乘法和加法運算轉(zhuǎn)化為XOR 運算[12-13]。

如圖3 所示，利用 G F(23)的矩陣表示法可以將柯基矩陣轉(zhuǎn)換為位矩陣(binary distribution matrix,BDM)， GF(23)表示所有數(shù)據(jù)均用3 位2 進制數(shù)表示，數(shù)據(jù)范圍為0～7。

圖3 基于XOR 的編碼

圖中，深色表示1，白色表示0，這樣，所有的校驗數(shù)據(jù)都可僅用XOR 公式表示：

基于XOR 的數(shù)據(jù)更新方法僅依賴簡單的XOR 運算，CPU 可以直接執(zhí)行XOR 操作，相比于乘法運算，XOR 運算效率更高，因此，數(shù)據(jù)更新效率也更高。同時，根據(jù)文獻[3]研究表明，基于異或的編碼方式更適合采用現(xiàn)代CPU 的SIMD技術(shù)執(zhí)行并行加速計算。如采用AVX2 指令，可同時進行256 位異或運算。本文在一臺配有4 核2.2 GHz Intel CPU、16 GB DDR3 內(nèi) 存、1 TB SSD 存儲的Mac 操作系統(tǒng)環(huán)境中進行測試，發(fā)現(xiàn)采用AVX2 指令、基于XOR 進行數(shù)據(jù)更新，更新1 MB 的數(shù)據(jù)僅需20 ms，而采用基于RS 的數(shù)據(jù)更新，需要300 ms。因此，與CAU 不同，本文選擇基于XOR 進行數(shù)據(jù)更新。

2 基于XOR 的TAR-CAU 算法

CAU 算法的核心思想可以用圖4 表示，如前所述，CAU 按照節(jié)點所在的機架進行分組，其中，Ri和Rj分別表示數(shù)據(jù)節(jié)點機架和校驗節(jié)點機架，CAU 并不是實時處理每一個更新請求，而是設(shè)置了一個批處理閾值(如100)，當請求數(shù)量超過該閾值時，分條帶批量處理更新請求。當同一條帶中，Ri的數(shù)據(jù)更新量小于Rj的校驗數(shù)據(jù)更新量時，采用data update 方法，即分別將數(shù)據(jù)節(jié)點的delta值發(fā)送給某一校驗轉(zhuǎn)發(fā)節(jié)點，再由校驗轉(zhuǎn)發(fā)節(jié)點通過式(1)計算校驗更新并傳輸給相關(guān)的校驗節(jié)點，如圖4a 所示；相反，當Ri的數(shù)據(jù)更新量大于Rj的校驗數(shù)據(jù)更新量時，采用parity update 方法，即匯總所有的delta 值到數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點，再由數(shù)據(jù)轉(zhuǎn)發(fā)節(jié)點利用式(1)計算校驗更新并傳輸給相關(guān)的校驗節(jié)點，如圖4b 所示。

圖4 CAU 的2 種更新方法

相比于傳統(tǒng)的星型數(shù)據(jù)更新方式(各個數(shù)據(jù)節(jié)點各自將數(shù)據(jù)傳輸給相關(guān)的校驗節(jié)點)，CAU 利用匯聚節(jié)點的轉(zhuǎn)發(fā)，確實可以減少網(wǎng)絡(luò)開銷，尤其是跨機架的網(wǎng)絡(luò)開銷。然而，數(shù)據(jù)更新性能可以進一步優(yōu)化。

1) 采用打包更新。因為大部分的數(shù)據(jù)更新量小(不超過4 KB)，而一般設(shè)置的塊大小為1～64 MB。因此，在同一個機架中，如果同一節(jié)點有多個數(shù)據(jù)塊進行了更新，可以采用tar 打包模型進行校驗數(shù)據(jù)更新。

2) 基于XOR 進行更新。如前文所述，基于RS 計算更新會產(chǎn)生大量的乘法運算，對于CPU 資源開銷較大，鑒于此，本文采用基于XOR 的更新方法，在計算校驗更新時，采用式(2)～式(7)，將有限域乘法與加法運算都轉(zhuǎn)化為XOR 運算。

如圖5 所示，在同一數(shù)據(jù)節(jié)點中，可能有多個數(shù)據(jù)塊被修改(比如 Node 0的0 號、6 號數(shù)據(jù)塊)，考慮到修改的數(shù)據(jù)量較小，本文采用tar 打包的方式，如圖6 所示，將同一個節(jié)點的數(shù)據(jù)進行打包，增加一個頭數(shù)據(jù)(用H 表示)，頭數(shù)據(jù)中記錄該塊所在的條帶編號、塊內(nèi)起始位置、修改數(shù)據(jù)大小等信息。

圖5 數(shù)據(jù)更新示例(CAU 模型)

圖6 TAR-CAU 模型

如此，同一個塊的大小可以容納至少200 個小更新(假設(shè)塊大小為1 MB)，從而可在處理一個條帶時，同時處理多個更新數(shù)據(jù)，然后按照CAU的傳輸模型進行數(shù)據(jù)更新。

同時本文發(fā)現(xiàn)在進行批處理更新時，同一個數(shù)據(jù)塊(如 Node 0的0 號數(shù)據(jù)塊)可能會被多次修改，但是每一次修改的位置和大小不一定相同。這就需要在進行tar 壓縮時，對同一個數(shù)據(jù)塊的多次訪問進行記錄和合并。如圖7 所示，假設(shè)數(shù)據(jù)塊大小為1 MB，在進行批處理更新時，發(fā)現(xiàn)0 號塊有多次修改記錄，于是，本文將多次修改的數(shù)據(jù)進行合并(XOR)，同時找出其中的最小和最大范圍(rangeL 和rangeR)，并將這2 個值轉(zhuǎn)化為塊內(nèi)起始位置和修改數(shù)據(jù)大小，記錄到H。

圖7 TAR-CAU 對同一塊多次訪問的合并處理

從圖7 可以看出，TAR-CAU 算法的優(yōu)化空間是blockSize-(rangeR-rangeL)，優(yōu)化代價是進行了打包與解包處理，增加了CPU 開銷。因此，TARCAU 算法性能對于數(shù)據(jù)訪問有一定的依賴性，優(yōu)化效果與具體的數(shù)據(jù)訪問記錄有關(guān)。

3 實驗

3.1 仿真實驗

本文通過微軟劍橋研究院提供的真實數(shù)據(jù)集進行仿真實驗，數(shù)據(jù)集記錄了來自微軟13 個服務(wù)器，179 塊磁盤中36 個分區(qū)一周內(nèi)的訪問日志，每條記錄包含訪問時間、請求地址、訪問數(shù)據(jù)大小等信息，本文隨機選擇了3 個數(shù)據(jù)集進行仿真測試，仿真實驗平臺采用Go 語言環(huán)境搭建，通過改變塊大小、節(jié)點數(shù)量等參數(shù)，以平均更新時間、吞吐量為指標點，與CAU 算法、基本更新算法(簡稱Base)進行了比較。仿真環(huán)境如表1 所示。

表1 仿真環(huán)境

1) 平均更新時間

如圖8 所示，本文比較了3 個數(shù)據(jù)集的平均單塊更新時間，發(fā)現(xiàn)TAR-CAU 算法更新效率最高，平均更新時間為0.009 4 s，時間效率比BASE 提高54%，比CAU 提高30%。

圖8 平均更新時間(不同數(shù)據(jù)集)

2) 吞吐量

如圖9a 中，盡管本文提出的算法TAR-CAU需要在進行網(wǎng)絡(luò)傳輸之前進行打包處理，增加了CPU 開銷，但是由于降低了網(wǎng)絡(luò)傳輸?shù)念l率，因此，更新效率大大提高，在3 種數(shù)據(jù)集中表現(xiàn)最佳，吞吐量比BASE 提高了119%，比CAU 提高了43%。

圖9 吞吐量

如圖9b 中，本文比較了常見的RS(n,k)配置：RS(4, 2)、RS(9, 6)、RS(16, 12)，機 架 容 量(rack size)分別設(shè)置為2、3、4。仿真結(jié)果表明，TAR-CAU 的吞吐量比CAU 提高了44%。

如圖9c 中，通過改變塊大小(block size)的實驗對比發(fā)現(xiàn)，TAR-CAU 的吞吐量提高了60%。

3.2 本地集群實驗

本文采用Go 語言在Ubuntu 18.04 平臺實現(xiàn)了基于TAR-CAU 算法的原型系統(tǒng)，并在本地局域網(wǎng)搭建集群進行測試，以了解在較為真實的環(huán)境中TAR-CAU 算法的性能。局域網(wǎng)內(nèi)部署了3 臺服務(wù)器(2 臺華為H12M-03，1 臺華為H22M-03)，利用pve 虛擬管理平臺[14]搭建了虛擬機集群環(huán)境，共有13 臺虛擬機，網(wǎng)絡(luò)拓撲結(jié)構(gòu)如圖10 所示，主要由3 個部分組成：中央控制器(central controller)、算法調(diào)度器(scheduler)以及節(jié)點代理(agent)。其中，中央控制器位于元數(shù)據(jù)服務(wù)器(metadata server,ms)中，負責整個流程控制，包括發(fā)送命令給節(jié)點代理、收集代理返回的響應(yīng)ACK、統(tǒng)計時間和跨域流量等；而算法調(diào)度器是整個系統(tǒng)的大腦，負責根據(jù)指定的算法指揮中央控制器進行調(diào)度，算法調(diào)度器也位于元數(shù)據(jù)服務(wù)器中；節(jié)點代理負責接受中央控制器的命令，執(zhí)行相關(guān)任務(wù)，并返回給上級ACK。

每臺虛擬機的配置如表2 所示。

為了模擬真實的網(wǎng)絡(luò)環(huán)境，本文采用Linux tc工具[15]進行網(wǎng)絡(luò)帶寬限制，設(shè)置機架內(nèi)部帶寬1 Gbps，機架外部200 Mbps，該設(shè)置可以根據(jù)具體的應(yīng)用場景自行配置。與仿真實驗一致，本文采用hm_0、hm_1、rsrch_1 這3 個數(shù)據(jù)集進行測試。

1) 平均更新時間

如圖11 所示，設(shè)置塊大小為4 MB，實驗結(jié)果與仿真結(jié)果大體相同，TAR-CAU 算法表現(xiàn)最佳，平均單塊更新時間為0.454 4 s，相比Base 節(jié)省約78%的時間開銷，相比CAU 節(jié)省近70%的時間開銷。

2)吞吐量

如圖12a 所示，設(shè)置塊大小為4 MB，通過3 種數(shù)據(jù)集對比，在吞吐量方面，本文提出的TAR-CAU 算法大大優(yōu)于Base 和CAU，平均吞吐量比Base 高出9 倍，比CAU 也高出206%，這樣的表現(xiàn)也是出乎意料。當然，值得注意的是，如前所述，TAR-CAU 的算法性能依賴于用戶訪問數(shù)據(jù)的位置，如果rangeL 和rangeR 過于靠近邊界(0 和blockSize)，TAR-CAU 的算法表現(xiàn)甚至會略弱于CAU。

圖12b 展示了不同塊大小對各個算法的影響，當塊大小較小時(如1 M)，CAU 算法略優(yōu)于TARCAU，原因可能是rangeL 和rangeR 過于靠近邊界，導(dǎo)致打包產(chǎn)生的收益不如打包帶來的額外開銷。而隨著塊大小的逐漸增大，TAR-CAU 算法的優(yōu)勢愈發(fā)明顯，尤其是在塊大小達到16 M 以上時，頻繁IO 的開銷逐漸成為了性能的主導(dǎo)因素，所以，僅傳輸delta 值的TAR-CAU 算法表現(xiàn)更佳。

由于引入了打包和解包過程，因此，TARCAU 算法相比于CAU 算法會產(chǎn)生額外的CPU 開銷，如圖13 所示，設(shè)置數(shù)據(jù)塊大小分別為1、4、16、64 MB，同時隨機產(chǎn)生100 個數(shù)據(jù)塊更新，每個數(shù)據(jù)更新的大小都不超過數(shù)據(jù)塊大小的1 /100，本文在一臺虛擬機中測試打包與解包性能發(fā)現(xiàn)，打包與解包時間均不超過300 ms。因此，對于整體的數(shù)據(jù)更新性能影響可以忽略不計。

4 結(jié) 束 語

為解決云存儲中數(shù)據(jù)更新的網(wǎng)絡(luò)瓶頸，本文針對數(shù)據(jù)更新的網(wǎng)絡(luò)傳輸進行了優(yōu)化，基于CAU 算法，提出了TAR-CAU，并針對數(shù)據(jù)更新量普遍較小的現(xiàn)象進行優(yōu)化，將同一節(jié)點的多條帶更新數(shù)據(jù)打包到同一條帶進行處理。仿真實驗和本地集群實驗均表明，相比于CAU 算法，當數(shù)據(jù)更新量較小時，本文的TAR-CAU 算法能夠至少提高44%的數(shù)據(jù)更新吞吐量。