黎 聰，唐 聃

（1.成都信息工程大學 軟件工程學院；2.四川省信息化應用支撐軟件工程技術研究中心，四川 成都 610225）

0 引言

隨著人工智能、物聯(lián)網、云計算等計算機技術的逐漸成熟，數據量級呈爆炸式膨脹［1］。分布式存儲系統(tǒng)因其底層硬件結構和文件系統(tǒng)可以靈活擴展而被人們青睞，常用于解決大數據難題。然而，更多的存儲設備為系統(tǒng)帶來了更大的數據丟失風險。為保證數據的可靠性與可用性，分布式存儲系統(tǒng)需要構建相應的容錯策略［2-3］。普通集群使用多副本技術構建容錯策略，其實現過程簡單，但集群空間消耗大［4-5］。而糾刪碼技術通過特定算法計算冗余塊進行容錯，雖然編譯碼計算復雜度較高，但其存儲利用率和靈活性高，被越來越多的分布式系統(tǒng)使用［6］。例如，分布式文件系統(tǒng)Ceph 就引入了Jerasure 庫、ISA-L 庫（Intelligent Storage Acceleration Library）等糾刪碼編碼和解碼庫［7］。但一些經典糾刪碼，如RS 碼（Reed-Solomon Codes），在數據修復過程中譯碼所需數據量往往是丟失量的數倍，會占用大量網絡傳輸帶寬和磁盤I/O（Input/Output）資源，造成集群資源的浪費［8］。E-MBR 碼（Exact Minimum Bandwidth Regeneration Codes）在一定程度上解決了該問題，其通過引入網絡編碼的概念，在節(jié)點修復時選取較多節(jié)點參與修復過程，且參與修復的節(jié)點首先對本節(jié)點內的數據進行線性組合后再上傳，極大減少了修復失效節(jié)點的帶寬消耗［9］。

由于電子商務、Web 服務和金融等行業(yè)的特殊性，需要對數據進行實時訪問，使得數據中心必須為用戶提供7×24h 的高質量響應服務，然而數據遷移量和擴容時間等因素均會影響擴容效率，造成響應延時［10］。因此，如何使用更短的時間、更少的傳輸數據量完成擴容成為難點所在，也受到了越來越多科研人員的關注。目前，許多研究在特定的RAID-6（Redundant Arrays of Independent Disks）編碼上實現了擴容［11-15］。例如，文獻［11］對數據遷移和奇偶校驗數據更新過程進行了優(yōu)化，減少了擴容時間，但只適用于離線場景且平均響應時間未減少；文獻［12］通過將舊硬盤中的部分數據塊遷移到新硬盤中實現了最小成本的數據遷移，但未說明響應時間變化和適用場景；文獻［13］改變了數據遷移方式，使得數據塊只在同一行奇偶鏈中移動，從而達到了數據遷移最小值，但其同樣未說明響應時間變化，且只適用于離線場景。文獻［16-19］在再生碼［9，20］的基礎上實現了擴容，其中文獻［16-18］均證明了最小擴容帶寬，但文獻［16］只有在功能性修復的情況下可以達到，文獻［17］需要擴容前后重構節(jié)點數相等（k=k'）時才能達到，而文獻［18］的方法復雜度較高，實現困難；文獻［19］提出兩種擴容方法，但其實現方法存在特殊性，未能達到最小擴容帶寬下限。此外，文獻［21］提出的Round-Robin（RR）擴容方法是公認數據布局最優(yōu)的方法，該方法適用范圍廣，但其擴容時幾乎需要遷移所有數據塊，因此數據遷移量和擴容開銷最大，擴容時間較長；文獻［22］基于RS 碼提出轉置數據布局，實現了Scale-RS 擴容方法，該方法達到了數據遷移量的下限，從讀取并行性和寫入吞吐量方面提高了存儲集群的I/O 性能，但未能達到校驗更新的開銷下限。

目前國內外擴容方法分數據遷移與校驗更新兩步完成，大多數不適用或未說明是否適用于在線場景，且部分擴容方法未能達到最優(yōu)下限，或只有在特殊參數條件下才能達到，限制了擴容方法在在線場景中的應用。隨著再生碼在分布式場景中的廣泛使用，以及在線場景存在的必要性不斷增加，不可避免地需要使用在線擴容方法緩解存儲和計算壓力，提高分布式存儲系統(tǒng)性能。為此，本文提出一種基于E-MBR 碼的擴容方法S-E-MBR，可滿足在線擴容場景需求，解決了使用E-MBR 碼作為容錯策略的分布式存儲系統(tǒng)的存儲瓶頸問題。

1 S-E-MBR擴容方法

S-E-MBR 方法結合了E-MBR 碼的構造特點與在線更新時數據從外部輸入的特點，使用增量更新［23］和RS 碼生成矩陣動態(tài)擴張［24］的思想，省去了數據遷移過程，從而能最大程度地減少擴容時的開銷。

1.1 E-MBR碼構造

記E-MBR 碼的總節(jié)點數、重構節(jié)點數、單節(jié)點修復所需節(jié)點數和擴容節(jié)點數分別為n、k、d和s，底層RS 碼總編碼塊和原始數據塊分別為θ和B。圖1（彩圖掃OSID 碼可見，下同）為E-MBR 碼(n=4，k=2，d=3)的構造示意圖，代表總節(jié)點數使用基于范德蒙矩陣的RS 碼(θ=d(d+1)/2=6，B=kd-k(k-1)/2=5) 對原有原始數據塊vi(1 ≤i≤5)進行編碼，得到編碼塊vi(1 ≤i≤6)。其中，vi(1 ≤i≤5)為數據塊，v6為校驗塊或冗余塊。將編碼塊與圖1 中的θ=6 條邊一一對應，對于每個存儲節(jié)點，只存儲與其相連的d=3條邊所對應的編碼塊，則編碼完成。

Fig.1 Schematic diagram of E-MBR codes（n=4，k=3，d=2）encoding process圖1 E-MBR碼(n=4，k=2，d=3)構造示意圖

1.2 增量更新

在E-MBR 碼中，底層使用基于范德蒙矩陣的RS 碼對原始數據塊進行編碼，其生成矩陣的動態(tài)擴展機制能夠快速實現校驗更新。記q為(n，k)RS 碼擴容的節(jié)點數，當其擴容時，容錯數r=n-k不發(fā)生變化，其生成矩陣變化表示為：

在RS 碼擴容時，生成矩陣由k×k階單位矩陣Ik與r×k階的范德蒙矩陣Vr，k擴容為(k+s) × (k+s)單位矩陣Ik+s與r× (k+q)范德蒙矩陣Vr，k+q。采用pi(1 ≤i≤r)表示原始校驗塊，di(1 ≤i≤k) 表示原始數據塊，(k+1 ≤i≤k+q)表示新增數據塊，則擴容后的新校驗塊(1 ≤i≤r)可由式（2）得到，校驗更新完成。

1.3 S-E-MBR擴容方法詳細設計

S-E-MBR 擴容方法分為數據填充與校驗更新兩步完成。填充數據來源于外部輸入。由于S-E-MBR 擴容時不需要將條帶分組，只需以(n，k，d，s)一個條帶擴容過程為例進行說明，其余條帶操作均相同。

1.3.1 數據填充

記M為n×θ的矩陣，代表全連通無向圖的關聯(lián)矩陣，其中(i，j)=1 表 示Vj需 要放置在nodei。關聯(lián)矩陣M的構造方式為遞增式擴張，即每次擴容1 個節(jié)點，經過s次擴容即可得到最終需要的(n+s，k+s，d+s)E-MBR 碼的關聯(lián)矩陣M'。根據M'進行數據填充，對于同一節(jié)點的數據可以使用聚合式發(fā)送，能夠最大程度地減少其I/O 次數。

定理1：擴容前M每行有且僅有d個1存在，擴容s個節(jié)點后M'每行有且僅有d+s個1存在。

證明：記θ'為擴容后對應的參數，擴容前后容錯數r=d-k=d'-k'不發(fā)生改變，因此擴容后θ'=d'(d'+1)/2。首先可以得到擴容前M每行有且僅有d個1 存在。若s=1，可以得到M'需要新增的部分為(n+1) × (θ'-θ)，記為Q。由于Q由n× (θ'-θ)的單位矩陣與1 × (θ'-θ)的1矩陣構成，其每行有且僅有1 個1，每次擴容1個節(jié)點時，其每行也只增加1 個1。當s＞1 時，只需重復上述過程s次，增加s個1，因此M'每行有且僅有d+s個1存在，證畢。

定理2：擴容前后M'每列有且僅有2個1存在。

證明：擴容前M每列有且僅有2 個1 存在，若s=1，新增部分Q由n× (θ'-θ)的單位矩陣與1 × (θ'-θ)的1 矩陣構成，每列有且僅有2 個1，不影響擴容前的M。因此，當重復上述過程，經過s次擴容后，M'依然每行有且僅有2個1存在，證畢。

以上定理的證明表明擴容前后E-MBR 碼本身的構造特點未發(fā)生改變，即擴容方法并不會對編碼過程產生影響，這是擴容方法應遵循的標準。

下面以S-E-MBR 擴容方法一次性擴容2 個節(jié)點為例進行說明。圖2 為(n=5，k=3，d=4)時的關聯(lián)矩陣示意圖，方框分別表示從(n=3，k=1，d=2)開始，每增加一個節(jié)點，M的增加部分Q。虛線部分表示每次進行聚合發(fā)送的部分，首先將得到的新增數據分為新增數據塊vi(4 ≤i≤10)；然后將{v4，v7}、{v5，v8}、{v6，v9}分別聚合發(fā)送到原始節(jié) 點nodei(1 ≤i≤3) 中；最后將{v4，v5，v6，v10} 與{v7，v8，v9，v10}分別聚合發(fā)送至新增節(jié)點nodei(4 ≤i≤5)中即可完成數據填充。

Fig.2 Schematic diagram of correlation matrix when n=5，k=3，d=4圖2 參數為n=5，k=3，d=4時的關聯(lián)矩陣示意圖

1.3.2 校驗更新

校驗更新階段同樣采用“1.2”小節(jié)直接增量更新的方法，首先直接計算出更新所需增量塊，然后將其發(fā)送至校驗塊進行更新即可。同樣以(n=3，k=1，d=2，s=2)為例，擴容前E-MBR 碼使用(n=3，k=2)RS 作為底層編碼方法，因此{v1，v2}為數據塊，v3為校驗塊。擴容后E-MBR需要使用(n=10，k=9)RS 碼作為編碼方法，因此q=7，校驗塊由式（3）得到。只需要將增量Δv3分別發(fā)送至校驗塊v3即可完成更新。至此，一個條帶的擴容過程完成。

1.4 S-E-MBR擴容方法示例

由于“1.3”小節(jié)已經對擴容2 個節(jié)點的情況進行了說明，為證明S-E-MBR 擴容方法的普適性，以下對擴容1 個節(jié)點的詳細過程進行舉例說明。為便于描述，記四元組(n，k，d，s)表示E-MBR 碼從參數(n，k，d)擴容到參數(n+s，k+s，d+s)。圖3為使用S-E-MBR 方法從參數(n=4，k=2，d=3)擴容到(n=5，k=3，d=4)時的示意圖。

Fig.3 Schematic diagram of expanding one node using S-E-MBR method圖3 S-E-MBR方法擴容1個節(jié)點示意圖

使用S-E-MBR 方法擴容1 個節(jié)點分數據填充與校驗更新兩步完成，過程如下：

（1）數據填充。填充過程可以分為原始節(jié)點填充與新增節(jié)點填充兩種。在原始節(jié)點nodei(1 ≤i≤4)中，只需要將新增數據塊vi(7 ≤i≤10)分別發(fā)送到對應節(jié)點即可；在新增節(jié)點node5中，則需要先將新增數據塊vi(7 ≤i≤10)打包，然后再放入到新增節(jié)點node5中。

（2）校驗更新。當E-MBR 碼從(n=4，k=2，d=3)擴容到(n=5，k=3，d=4)時，RS 碼需要從(n=6，k=5)擴展到(n=10，k=9)，此時q=4，根據RS 碼增量更新過程，校驗塊v'6可由式（4）計算得到，然后只需將增量塊△v6發(fā)送到校驗塊中即可完成更新。

2 指標分析

從數據遷移量、I/O 開銷兩個影響擴容方法性能的關鍵指標方面對S-E-MBR、RR 與Scale-RS 3 種擴容方法進行比較，分析S-E-MBR 擴容方法的優(yōu)缺點。比較時均假設在同一條帶中進行。

2.1 數據遷移量分析

數據遷移量指完成一次擴容需要跨節(jié)點遷移的數據塊數量。S-E-MBR、RR、Scale-RS 和Optimal 的數據遷移量如表1 所示，表中n'=n+s，d'=d+s，B'=k'd'-k'(k'-1)/2，分別表示擴容后的相應參數。

Table 1 The number of data blocks migrated by S-E-MBR，RR，Scale-RS，and Optimal in a same stripe表1 S-E-MBR、RR、Scale-RS和Optimal完成一次擴容遷移的數據塊數量

在線擴容場景下，數據填充的最優(yōu)情況為直接將得到的數據拆分為Vi(nd＜i＜=n'd')，然后將其填充至節(jié)點nodei(1 ≤i≤n') 對應位置，此時消耗的傳輸量為n'd'-nd。校驗更新的最優(yōu)情況為直接對2(θ-B)個校驗塊進行更新，此時消耗的傳輸量為2(θ-B)?？梢娫诰€擴容場景下，S-E-MBR 的數據遷移量與Optimal 一致，達到了理論最優(yōu)傳輸量，這也是設計本文方法的目的。然而，RR 與Scale-RS 擴容方法未考慮在線場景與E-MBR 碼的特點，遷移量較大，且RR 與Scale-RS 校驗更新時只能采用重新編碼得到冗余塊后再進行更新，因此校驗更新階段的數據遷移量也較大。圖4 為［n=4，k=2，d=3］、［n=5，k=2，d=4］、［n=5，k=3，d=4］參數下S-E-MBR、RR 和Scale-RS 方法分別擴容s=1 與s=2 個節(jié)點的數據遷移量示意圖。當s=1 時，S-E-MBR 方法與RR、Scale-RS 相比遷移數據塊數量減少了57%～74%；當s=2 時，S-E-MBR 方法與RR、Scale-RS 相比，遷移數據塊數量減少了42%～50%?？梢奡-E-MBR 在數據塊遷移量方面有明顯優(yōu)勢。

Fig.4 The number of data blocks that need to be migrated to expand the capacity of 1 and 2 nodes of S-E-MBR，RR，and Scale-RS scaling methods圖4 S-E-MBR、RR和Scale-RS方法分別擴容1個和2個節(jié)點需要遷移的數據塊數量

2.2 I/O開銷分析

I/O 開銷指完成一次擴容所有存儲節(jié)點執(zhí)行數據輸入和輸出的次數。S-E-MBR、RR、Scale-RS 的I/O 開銷如表2所示。

Table 2 Input and output times of S-E-MBR，RR，and Scale-RS表2 S-E-MBR、RR和Scale-RS I/O 開銷

I/O 開銷與數據遷移息息相關，RR、Sclae-RS 方法的數據遷移次數較多，導致存儲節(jié)點需要頻繁讀取，因而 I/O 次數較多。而S-E-MBR 方法利用聚合發(fā)送的方式，同一節(jié)點中只需要發(fā)送1 次數據，最大程度地減少了I/O 開銷。圖5 為S-E-MBR、RR 和Scale-RS 方法在參數為［n=4，k=2，d=3］、［n=5，k=2，d=4］、［n=5，k=3，d=4］時分別擴容s=1 與s=2 個節(jié)點的I/O 開 銷。當s=1 時，S-E-MBR 方法與RR、Scale-RS 相比，I/O 次數減少了79%～89%；當s=2 時，S-E-MBR 方法與RR、Scale-RS 相比，遷移數據塊數量減少了60%～79%?？梢奡-E-MBR 在I/O 開銷上也有明顯優(yōu)勢。

Fig.5 I/O overhead of S-E-MBR，RR and Scale-RS methods when scaling 1 and 2 nodes respectively圖5 S-E-MBR、RR和Scale-RS方法分別擴容1個和2個節(jié)點時的I/O開銷

3 實驗評估

3.1 實驗環(huán)境

在真實的分布式場景下測試S-E-MBR、RR、Scale-RS方法各方面的性能表現。實驗平臺基于Ceph 分布式存儲系統(tǒng)搭建，主要分為客戶端、Ceph Monitor、OSD（Object Storage Daemon）等?？蛻舳酥饕糜谔峁┯脩舨僮骷旱钠脚_；Ceph Monitor 負責監(jiān)控整個集群的健康狀況、維護集群map 等；OSD 為對象存儲設備，是存儲用戶數據并響應客戶端操作請求的唯一組件。

實驗測試平臺包含23 個節(jié)點，分別為1 個客戶端、2 個Ceph Monitor 節(jié)點和20 個OSD 存儲節(jié)點。所有節(jié)點硬件配置相同，均為CPU 酷睿i5-5200U、8 GB 內存、128 GB 硬盤、1GBps 以太網卡，且均裝載操作系統(tǒng)CentOS8、運行環(huán)境Python3.6、分布式存儲系統(tǒng)Ceph15。

圖6 為實驗平臺結構示意圖。Ceph 中客戶端可通過聯(lián)系Monitor 獲取集群map，并通過Ceph CRUSH 確定數據存儲的OSD 位置，通過直接聯(lián)系該OSD 來存取數據。所有實驗操作均通過客戶端調用擴容算法實現，并采用Ceph直接對OSD 中的數據進行讀寫操作。

Fig.6 Schematic diagram of the experimental platform structure圖6 實驗平臺結構示意圖

3.2 實驗設計與評價指標

為保證公平性，在每次實驗開始前清除節(jié)點中的所有數據，然后以(n=10，k=8，d=9)E-MBR 碼作為基礎編碼，以2M 的分塊大小對50 G 數據進行編碼，作為集群初始存儲數據量。

選擇數據傳輸量、擴容時間和客戶端響應時間3 個指標對各方法性能進行評價與比較。在本文實驗中，數據傳輸量被定義為整個擴容過程中涉及節(jié)點間傳輸的數據量之和，其直接反映了擴容過程中網絡傳輸帶寬的占用情況，也一定程度上反映了各個磁盤I/O 資源的占用情況，是評價擴容方法的重要指標；擴容時間被定義為從發(fā)出擴容指令開始到擴容結束所花費的總時間，其在一定程度上反映了算法實現的復雜度，也是衡量擴容方法效率的重要指標；客戶端響應時間被定義為從客戶端發(fā)出指令到服務器作出反饋的響應時間，其是擴容時用戶最直觀的感受。

3.3 數據傳輸量

圖7 為在線輸入數據為50 G 時，S-E-MBR、RR、Scale-RS 方法分別擴容2、4、6、8 個節(jié)點時的傳輸數據量比較結果，反映了擴容節(jié)點數s對擴容方法性能的影響大小?？梢钥闯觯跀U容節(jié)點數相同時，S-E-MBR 方法的數據傳輸量 比RR 和Scale-RS 方法分別減少52.7%～77.9% 和41.3%～50.4%。隨著擴容節(jié)點數的增多，S-E-MBR 方法的數據傳輸量減少程度呈現下降趨勢，說明該方法在小規(guī)模擴容時更具優(yōu)勢。

Fig.7 Data transmission volume comparison of S-E-MBR，RR and Scale-RS methods under different expansion nodes圖7 不同擴容節(jié)點下S-E-MBR、RR和Scale-RS方法數據傳輸量比較

圖8 為在線輸入數據量分別為6 G、12 G、24 G、48 G，擴容1 個節(jié)點時S-E-MBR、RR、Scale-RS 方法的數據傳輸量比較?？梢钥闯?，在不同在線輸入數據量下，S-E-MBR方法的數據傳輸量比RR 和Scale-RS 方法減少86.3%～86.8%，說明在線輸入數據量大小對S-E-MBR 方法的數據傳輸量產生的影響較小，該方法穩(wěn)定性較好。

Fig.8 Data transmission volume comparison of S-E-MBR，RR，and Scale-RS methods under different online input data volumes圖8 不同在線輸入數據量下S-E-MBR、RR和Scale-RS方法數據傳輸量比較

3.4 擴容時間

圖9 為在線輸入數據量分別為6 G、12 G、24 G、48 G，擴容節(jié)點數為1 時，S-E-MBR、RR、Scale-RS 方法的擴容時間比較?？梢钥闯?，在不同在線輸入數據量下，S-EMBR 方法的擴容時間相較RR 和Scale-RS 方法分別減少72.3%～75.4%和50.6%～53.5%，說明該方法在擴容時間方面有較小起伏。圖10 為各方法擴容時間的平均值，可以看出S-E-MBR 方法的平均擴容時間相較RR 和Scale-RS方法分別減少了74.0%與58.2%，該方法在擴容時間方面具有明顯優(yōu)勢。

Fig.9 Expansion time comparison of S-E-MBR，RR，and Scale-RS methods under different online input data volumes圖9 不同在線輸入數據量下S-E-MBR、RR和Scale-RS方法擴容時間比較

Fig.10 Comparison of average scaling time between S-E-MBR，RR，and Scale-RS methods圖10 S-E-MBR、RR和Scale-RS方法平均擴容時間比較

3.5 客戶端響應時間

圖11 為S-E-MBR、RR、Scale-RS 方法以及無擴容操作的客戶端平均響應時間比較，可以看出3 種擴容方法均在一定程度上降低了集群的響應速度，但執(zhí)行S-E-MBR方法時集群的響應速度更快，與RR、Scale-RS 相比，其響應速度分別提升了39.2%和17.1%，說明S-E-MBR 方法更適合不宕機的在線擴容場景。

Fig.11 Comparison of client response time for S-E-MBR，RR，and Scale-RS methods圖11 S-E-MBR、RR和Scale-RS方法客戶端響應時間比較

4 結語

可以靈活擴充存儲容量是分布式存儲系統(tǒng)解決大數據難題的優(yōu)勢。在以E-MBR 碼為基礎構建安全策略的分布式存儲中，擴容不僅是存儲容量的增加，還意味著數據的重新分配與校驗數據的更新。

本文充分利用E-MBR 底層RS 碼的更新優(yōu)勢與在線擴容場景的特點，提出一種適用于E-MBR 碼的分布式存儲集群擴容方法S-E-MBR，其實現過程相較離線擴容更簡單高效，在數據遷移與校驗更新時均能達到最優(yōu)情況，有效減少了需要消耗的網絡帶寬以及磁盤I/O 資源占用，縮短了擴容時間。在以Ceph 為基礎搭建的分布式測試集群中進行比較實驗，結果表明S-E-MBR 方法相較RR 與Scale-RS 方法擴容時的數據傳輸量減少了52.7%～77.9%和41.3%～50.4%，擴容總時間減少了72.3%～75.4% 和50.6%～53.5%。雖然S-E-MBR 擴容時會在一定程度上降低系統(tǒng)響應速度，但與RR 與Scale-RS 擴容方法相比，其響應速度分別提升了39.2%和17.1%，適合于需要在線擴容的場景。目前，S-E-MBR 方法僅適用于E-MBR 碼需要增加節(jié)點的情況，節(jié)點數減少的情況將作為未來研究方向，以期提出更為通用、高效的在線擴容方法。