基于XOR 的TAR-CAU 數據更新方法

肖逸飛，周世杰

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

1.1 糾刪碼概述

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

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

1.2 數據更新

糾刪碼的數據更新主要有基于RS 的更新和基于XOR 的更新。

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

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

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

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

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

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

圖3 基于XOR 的編碼

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

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

2 基于XOR 的TAR-CAU 算法

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

圖4 CAU 的2 種更新方法

相比于傳統的星型數據更新方式(各個數據節點各自將數據傳輸給相關的校驗節點)，CAU 利用匯聚節點的轉發，確實可以減少網絡開銷，尤其是跨機架的網絡開銷。然而，數據更新性能可以進一步優化。

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

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

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

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

圖6 TAR-CAU 模型

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

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

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

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

3 實驗

3.1 仿真實驗

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

表1 仿真環境

1) 平均更新時間

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

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

2) 吞吐量

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

圖9 吞吐量

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

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

3.2 本地集群實驗

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

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

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

1) 平均更新時間

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

2)吞吐量

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

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

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

4 結 束 語

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