糾刪碼存儲系統數據更新方法研究綜述

張 耀 儲佳佳 翁楚良

(華東師范大學數據科學與工程學院 上海 200062)(zhangyao@stu.ecnu.edu.cn)

在分布式存儲系統中，節點故障已成為常態，根據文獻[1]，Facebook數據倉庫每天平均有50個節點不可用.通常分布式存儲系統會采用數據冗余的方式來保證系統的可用性，以免機器宕機、網絡分區等故障帶來的數據丟失、請求不能正常響應情況的發生.目前數據冗余的方式主要有2種：一種是多副本，另一種是糾刪碼.隨著大數據時代的到來，每天都會產生大量的數據，這給存儲系統帶來了更大容量的需求，隨之產生的成本開銷也越來越大.根據Facebook統計數據顯示[2]，數據中心中每PB的數據每個月所產生的經濟開銷大約是200萬美元.多副本機制的使用無疑使這種情況更加惡化.隨著CPU、網絡設備等新硬件技術的快速發展，人們逐漸把目光從多副本方式轉向糾刪碼.相比于多副本方式，糾刪碼能夠在保證相同甚至更高的系統可用性的同時，將存儲開銷降低為原來的50%，甚至更低，這節省的經濟開銷無疑是巨大的.目前越來越多的分布式存儲系統開始支持糾刪碼方式的存儲，像HDFS[3],Windows Azure[4],Ceph[5],f4[6]等.

但是糾刪碼本身也存在缺點.和多副本直接將原始數據完整拷貝多份作為冗余信息不同，糾刪碼之所以能夠將存儲開銷降低，是因為其利用特定的編碼規則對原始數據進行特定的結合,計算后生成少量的冗余信息，冗余信息和編碼規則結合能夠恢復出出錯的數據.當原始數據中的一些數據被更新時，對應的冗余信息也同樣需要更新來保證數據與冗余信息之間的一致性.可以看出，編碼、解碼、更新過程都需要計算消耗CPU資源.而且，解碼和更新操作都需要讀取相應的數據和冗余信息，這會消耗更多的網絡帶寬和硬盤IO.和多副本機制相比，糾刪碼的寫、更新、恢復數據過程更加復雜，導致糾刪碼的性能相對較差.為了兼顧系統性能和存儲效率，目前糾刪碼方式多是用于冷數據或者溫數據的存儲.像熱數據這種需要頻繁讀、寫、更新，并且對性能要求很高的場景還是用多副本方式存儲.很多研究工作致力于改善糾刪碼的性能，這些工作大多只是專注于其中一個方面.但是對于熱數據存儲來說，讀、寫、更新3種操作對性能的要求都很高，只有當糾刪碼在這3個方面的性能達到和多副本同樣性能甚至更好時，才能真正替換掉多副本機制，獲得更高的存儲效率.近年來不斷發展的非易失性內存(non-volatile memory, NVM)技術能夠極大地改善計算機的計算能力和存儲性能，消除了硬盤IO開銷，使得糾刪碼用于熱數據存儲成為可能.

目前國內外存在少量的糾刪碼技術的研究綜述.文獻[7]從糾刪碼的編碼、解碼、更新3個方面對現有的研究工作做了概括性的總結分析，文獻[8]僅關注了再生碼和本地修復碼2種編碼的技術進展，文獻[9]主要介紹編碼方面的相關工作，文獻[10]專注于數據恢復方面的工作，還沒有專門一篇介紹糾刪碼更新這一重要工作領域的綜述.文獻[7]也僅僅是從更新規則角度介紹了糾刪碼幾種基本的更新方法，并沒有全面分析和糾刪碼更新有關的工作.所以本文將專注于糾刪碼存儲系統中的數據更新操作，從硬盤IO、網絡傳輸、系統優化3個方面對現有的糾刪碼更新的相關工作做了深入分析，并對目前具有代表性的編碼方案的更新性能做了對比分析，最后指出糾刪碼未來的研究方向.

1 糾刪碼基本原理和背景知識

本節主要介紹了糾刪碼的編碼、解碼、更新的基本原理，分析了和多副本機制相比，糾刪碼更新的額外開銷.

1.1 基本原理

在分布式存儲系統中，數據通常以固定大小的塊的形式存儲起來，存儲數據的塊被稱為數據塊(data block)，存儲冗余信息的塊被稱為冗余塊，在糾刪碼中也被稱為校驗塊(parity block).存放數據塊的節點和存放校驗塊的節點被分別稱為數據節點和校驗節點.糾刪碼存儲系統中數據塊和校驗塊被統稱為編碼塊.存儲開銷和容錯能力是分布式存儲系統中非常重要的2個指標，本文對存儲開銷和容錯能力的定義為：

1) 存儲開銷.指冗余塊和數據塊大小之和與數據塊大小的比值，以3副本為例，其存儲開銷是3.

2) 容錯能力.指存儲系統在能夠正常提供服務的前提下允許發生故障的機器的最大數目，還是以3副本為例，其容錯能力為2.

糾刪碼作為數據存儲中除了多副本之外的另一種保護數據可用性的方法，在提供相同容錯能力的同時，能夠極大地降低存儲開銷.因為目前大多數存儲系統使用最廣泛的是線性糾刪碼，所以本文將只關注線性糾刪碼.線性糾刪碼的編碼、解碼重構操作都能通過在有限域內的線性操作來完成.編碼的基本原理是將原始數據以w位為單位在有限域(2w)[11]內線性結合得到對應的校驗信息,w通常為8，也就是1 B[12].通常來說，存儲系統會將被編碼的數據劃分成k個固定大小的數據塊，通過編碼生成m個校驗塊，然后將這k個數據塊和m個校驗塊分別存儲到不同的故障隔離域內.k個數據塊和m個校驗塊組成1個邏輯條帶(stripe),這是維護數據可用性的基本單元，能夠允許1個條帶內同時出現m個編碼塊損壞(容錯能力為m)，這樣一種編碼被稱為(k+m,k)碼.(k+m,k)碼的基本原理的數學形式為

(p0,p1,…,pm-1)T=G×(d0,d1,…,dk-1)T,

(1)

其中，pi為校驗塊(0≤i≤m-1)，dj為數據塊(0≤j≤k-1)，G為生成矩陣.在大多數存儲系統中采用的糾刪碼都有這樣一個特性：條帶內的數據塊以原生的形式存放，這樣使得系統能夠不用執行任何編碼操作直接響應請求.圖1是著名的RS(Reed-Solomon)編碼[13]的編碼過程的圖形化表示.假設第1個和第2個數據塊出現損壞，利用生成矩陣構造出解碼矩陣(去除生成矩陣第1行和第3行后的方陣的逆矩陣)，執行相應的矩陣運算即可恢復出損壞的數據塊.

Fig. 1 A pictorial representation of erasure coding encoding principle

1.2 糾刪碼基本更新方法

從圖1可以看出，校驗塊的生成是每個數據塊對應位置的數據在有限域內的線性結合，當數據塊發生變化時，校驗塊也需要相應地更新，如此才能在后期數據出現損壞或不可訪問時利用相應的解碼規則恢復出正確的數據.

最直接也是最傳統更新校驗塊的方法，就是重新執行一遍編碼.重新編碼是一個非常耗時的過程，這需要將條帶內所有的數據塊讀出，重新計算出校驗塊.以RS(5,3)為例，當更新數據塊d0時，需要消耗5x網絡IO(讀出d1,d2,寫回新編碼塊硬盤讀寫(讀出d1,d2,寫入但是在3副本中只需要3x的網絡IO和硬盤寫.當被更新的數據很小時，這種差距更明顯.這種更新方法適合于條帶內大多數數據都被更新的情況.如果只有1個數據塊，甚至是1個數據塊內的一部分被更新，這種方式的開銷無疑是巨大的.

(2)

根據其推導過程可以看出，系統只需要計算出更新增量來更新校驗塊.圖2展示了增量更新的流程，客戶端將新數據發送到存儲系統，存儲系統需要讀出原始數據塊，計算出增量，并將增量發送到相應的校驗節點.校驗塊節點再讀出原始校驗塊，根據式(2)計算出最新校驗塊并持久化，這時存儲系統才能將更新的數據覆蓋原始數據，響應客戶端.和重新編碼的更新方式相比，這種方式消除了很多不必要的網絡IO、硬盤IO，很適合被更新的數據較小的負載.但是可以看出，更新流程仍然很復雜，和基于多副本的數據更新性能有較大差距.多副本機制的數據更新過程類似于數據寫入過程，只需要將更新數據發送到相應節點寫入即可.而糾刪碼機制的更新過程涉及到數據塊和校驗塊2種數據，會產生額外的網絡IO、硬盤IO和更多計算.所以，針對基于糾刪碼機制的分布式存儲系統，需要設計一個高效的數據更新方法來改善更新效率.

Fig. 2 Incremental update process

2 糾刪碼更新優化的研究進展

糾刪碼本身并不是針對存儲系統設計的容錯技術，最早是用在通信行業解決數據傳輸中的數據損耗問題[14-15]，所以分布式存儲系統中的一些限制因素比如硬盤IO、網絡IO并沒有被考慮進來，導致糾刪碼在用于分布式存儲系統中時不可避免地產生很多冗余開銷.這些開銷主要體現在讀、寫、更新3種操作的性能方面.讀、寫操作主要因為編碼、解碼所產生的開銷，已有相關綜述對這些方面做了詳細的分析總結，在此不再贅述.本節接下來將專注于更新方面的研究工作，根據這些研究工作的優化角度可將其劃分為3類：第1類是針對硬盤IO開銷的優化工作，從圖2可以看出糾刪碼更新流程中都有“讀后寫”操作，這是導致硬盤IO開銷比多副本大的一個主要原因，這類研究工作主要針對這一問題進行優化；第2類是針對網絡傳輸的優化工作，這類工作主要根據糾刪碼數據更新的特點減少網絡中的數據傳輸量，從而改善糾刪碼更新性能；第3類工作是針對自身分布式存儲系統特點利用糾刪碼基本更新方法優化系統更新性能，這部分工作雖然改善了自身存儲系統的更新性能，但是并沒有對糾刪碼本身的更新性能做出改進優化，本文將這類工作稱為系統優化.基于這3個分類標準，表1對糾刪碼更新優化工作中具有代表性的工作進行了分類總結，本節接下來會詳細介紹.

Table 1 Classification Summary of Erasure Coding Update Related Work

2.1 硬盤IO優化

如1.2節所述，糾刪碼主要有重新編碼和增量更新2種方法.重新編碼會消耗大量的網絡帶寬、硬盤IO，不適合于被更新數據長度較小的情況.對MSR Cambridge traces[16]數據集分析可以發現平均每個更新操作涉及的數據長度普遍很小，超過60%的更新操作的數據長度小于4 KB.Harvard NFS traces數據集也具有類似的特征[17].所以目前的研究工作基本上都是基于增量更新做優化，盡可能減少更新過程中網絡IO、硬盤IO的消耗.

增量更新方法一般使用就地更新方式，即新數據塊和校驗塊直接寫入舊塊所在位置[18-19].相比于重新編碼，增量更新方法能夠很大程度上減少更新過程中參與的數據量，并且就地更新方式能夠有效保證條帶內數據的一致性.但是每一次更新操作都需要讀取原始數據塊和校驗塊，計算新校驗塊后方可寫入新數據，這些“讀后寫”操作使得其性能仍然比多副本更新性能差.

為了在更新操作的關鍵路徑上避免冗余的硬盤讀開銷，存儲系統可以利用日志追加形式將新數據和校驗塊更新增量順序寫入到硬盤內來消除更新路徑上原校驗塊的硬盤讀，同時將隨機寫轉換為順序寫，改善更新效率.這種方法被用于很多企業集群的存儲系統內，像GFS[20],Azure.但是這種方式對讀操作不友好，每次讀取數據時都需要查找隨機分布在日志中的所有更新增量得到最新數據，無法順序讀取數據，嚴重影響讀操作的性能[21].此外，當有數據損壞需要執行糾刪碼恢復操作時，需要先合并數據，削弱了糾刪碼的恢復性能[22-24].日志追加的形式導致系統中同時存在著舊數據和新數據，也一定程度上降低了存儲效率.

為了兼顧數據讀操作和更新操作的性能，可以對校驗塊更新采取日志追加形式，數據塊仍然采用就地更新方式.這種方式最先被Stodolsky等人[25]用于解決磁盤冗余陣列中的小寫問題.他們提出PL(parity logging)方法，對校驗塊增量利用日志追加形式寫入到硬盤內，對新數據使用就地更新方式，從而消除硬盤查找新數據和讀取原校驗塊時間.糾刪碼存儲系統也可以應用這種方法，但是這種方法仍然存在著恢復性能差的問題，因為恢復時需要查找并讀取校驗塊增量來得到最新校驗塊信息.為了能進一步改善這個問題，Chan等人[26]提出PLR(parity logging with reserved space)方法.這種機制會在硬盤內緊挨著校驗塊的位置分配一些額外空間來存儲未來的校驗增量，確保每個校驗塊和它的更新增量可以被順序訪問，從而消除硬盤查找開銷,將隨機讀轉化為順序讀，改善恢復性能.這種方式雖然消除了校驗塊的“讀后寫”問題，但是數據塊的“讀后寫”問題仍然存在，成為糾刪碼更新性能的一個瓶頸.

為了解決數據塊的“讀后寫”問題，進一步減少更新過程中的硬盤IO開銷，Li等人[27]提出PARIX方法，是一種預測部分寫模式的方法，將“讀后寫”問題轉變為單純寫操作.假設1個條帶內的某個數據塊dj被更新多次，代表數據塊dj第r次更新，代表對應的校驗塊.通過式(3)：

(3)

上述工作都是致力于改善糾刪碼更新過程中的“讀后寫”問題，可以看出相比于基本的糾刪碼更新方法，這些工作都對糾刪碼更新的硬盤IO開銷做出了一定程度的優化，但是“讀后寫”問題并沒有被徹底解決，和多副本方式的更新性能相比還是有一定差距.如何進一步優化硬盤IO開銷，獲得和多副本相近的更新性能仍需要研究人員繼續探索.

2.2 網絡傳輸優化

2.1節提到的工作都只是專注于條帶內的單個數據塊更新操作的優化.當1個條帶內有多個數據塊被更新或者多個條帶同時被更新時，這些更新可以共享數據傳輸或者數據計算來減少網絡傳輸的數據量，改善更新效率.此外，以上提到的優化工作所涉及的更新模式都采用星型結構來完成更新流程，所有被更新的數據節點連接到校驗節點，數據節點或者校驗節點會成為星型結構的核心，這會成為更新時的計算瓶頸或者網絡瓶頸.Zhang等人[28]從負責計算任務處理的節點位置角度出發，提出PUM-P，PDN-P兩種方式.通過將計算子任務盡可能放在距離數據近的節點上處理，來減少在網絡中需要傳輸的數據量，從而改善更新性能.PUM-P方法將計算任務交給1個中心節點update manager，其負責計算出校驗塊增量，然后將校驗塊增量發送到各個校驗節點上，由校驗節點負責新的校驗塊的計算.這種方式相比于將所有計算任務交給update manager的方式，節省了原始校驗塊的網絡傳輸.PDN-P方式將計算校驗塊增量的任務交給被更新數據塊所在節點，減少原始數據塊和更新后的數據塊的網絡傳輸，進一步減少更新過程中數據的網絡傳輸.

PUM-P和PDN-P更新流程采用的便是典型的星型結構模式，相關研究[29-30]表明即使存在可用帶寬更高的空閑鏈路，星型結構也無法充分利用其來改善數據傳輸效率.Pei等人[31]針對此問題提出一種基于樹形結構的自頂向下的更新模式T-Update，來充分利用節點間的網絡帶寬，改善更新效率.T-Update通過一種機架感知的樹形構建算法RA-TREE構建一棵最優更新樹，其核心思想是盡可能選擇較為臨近的節點作為連接節點，以保證節點之間數據傳輸的高效性.Wang等人[32]在T-Update的基礎上設計了一種更加通用的自適應更新模式，TA-Update，來改善T-Update的通用性.精心構建的樹形結構相比于星型結構能夠充分利用網絡帶寬來改善數據傳輸效率，但是這些工作仍然只是針對單點數據更新場景下的優化，單點問題依然存在.

Pei等人[33]針對多點更新提出一種分組流水線的更新模式Group-U，進一步優化更新效率，減少更新開銷.Group-U將被更新的節點分成若干組，每組選擇1個數據節點負責組織組內從其他數據節點發往校驗節點的數據流，通過這種方式，將數據傳輸和計算限制在每一個分組內，從而改善更新效率.Huang 等人[34]也采用了分組的思想，通過改善多個數據塊更新的并行性來改善分布式內存存儲系統的更新延遲.

Shen等人[35]給出了不一樣的解決糾刪碼多個數據塊更新的思路.在真實的存儲工作負載中，數據之間存在著關聯性，這些關聯的數據在訪問負載中占有很大比例，通常會被一起訪問.如果關聯的數據分散在多個不同的條帶中，那么對這些數據的1次更新操作就需要更新相應條帶中的所有校驗塊.將這些關聯的數據放在同一個條帶內的話，就可以減少需要更新的校驗塊數目，降低網絡帶寬的占用，從而改善更新性能，所以文獻[35]提出了一種基于數據關聯性的條帶組織算法CASO，通過檢測數據塊的被訪問特征確認數據塊的關聯性，然后將數據塊劃分為關聯和不關聯2類.對于關聯的數據塊，CASO構造一個關聯圖來評估它們的相關程度，將條帶組織問題轉化為一個圖分區問題.

在數據中心中，機架與機架之間的通信開銷相比于機架內部的通信開銷較大，通常1個節點的可用跨機架帶寬在最壞情況下是機架內部帶寬的15到120，這會成為限制系統性能的一個瓶頸.在糾刪碼存儲系統中，為了增強容錯能力，1個條帶內的數據塊和校驗塊通常會放置在不同機架內的節點上，這會導致在更新時產生大量的機架間數據傳輸.受限的跨機架網絡帶寬成為影響糾刪碼更新操作性能的一個瓶頸.針對這個問題，Shen等人[36]提出一種跨機架感知的更新機制——CAU，來減少跨機架的數據通信量.由式(2)可以看出，系統可以將條帶內每個被更新的數據塊的數據增量發送到校驗節點更新校驗塊，也可以讓條帶內1個數據節點負責計算出校驗增量，然后發送給校驗節點更新校驗塊.這2種方式在不同的數據分布和更新負載下會有不同的跨機架數據通信量.所以CAU采用選擇性的校驗塊更新方法，基于當前的數據分布和更新模式選擇一個最優方式進行更新.此外，CAU會進行數據重定位，將同一個條帶內更新的數據塊盡可能部署在1個機架內，進一步減少機架間的數據通信.

以上這些研究工作優化了糾刪碼存儲系統更新過程中需要網絡傳輸的數據量，減少了網絡帶寬的開銷，進一步改善了更新性能.如果將分組、跨機架感知、數據關聯等特性融合在一起，相信會有一個更好的性能改進.

2.3 系統優化

還有一些研究工作是從分布式存儲系統的自身特點出發，結合糾刪碼更新特點，優化更新性能.

Esmaili等人[37]在采用CORE編碼[38]的HDFS中實現了增量更新方法，并和重新編碼方法做了對比.CORE是一種將RS碼和奇偶校驗碼簡單耦合的編碼，在數據恢復時優先使用奇偶校驗碼，改善恢復性能.在數據更新時，需要將更新增量發送到所有校驗節點更新校驗塊.實驗結果表明當1個條帶中有小于一半的數據塊被更新時，增量更新性能比重新編碼好，反之比重新編碼差，所以在實現系統更新策略時需要結合當前更新負載特征，靈活選擇合適的更新方法來更新數據.

此外，在HDFS中寫入的文件會被劃分成多個固定大小的塊，這些塊通常很大，比如64 MB或者128 MB.這使得更新操作發生時，需要讀取的數據量很大，極大地增加了網絡IO和硬盤IO開銷.Subedi等人[39]針對此問題提出了一種FINGER(fine grained erasure coding scheme)的想法來改善HDFS-RAID中的寫操作和更新操作的性能.為了在不增加元數據大小的同時改善更新性能，他們在塊內執行糾刪編碼而不是塊與塊之間，減少寫和更新過程參與的數據量.Zhou等人[40]提出的采用數據頁(page)粒度的SEDP模型和Zakerinasab等人[41]提出的基于字節優化的OptDUM都是采用了類似的思想來處理云系統內的頻繁更新，減少更新過程中的計算開銷和網絡IO、硬盤IO開銷，改善更新性能.

Chen等人[42]觀察到分布式內存鍵值存儲系統中大量零散的元數據需要被頻繁更新.如果直接將糾刪碼機制移植到這類系統中，必將帶來零散元數據更新開銷大的問題.所以他們采用了一種混合存儲方式，對元數據采用多副本機制，對數據采用糾刪碼方式，避免了元數據被頻繁更新的開銷，同時獲得更高的存儲效益.但是當數據對象也很小時[43]，混合存儲方式帶來的存儲效率收益就很低了，所以Yiu等人[12]針對由小對象負載主導的分布式內存存儲設計了MemEC，按照固定塊大小的方式來組織對象和元數據，并設計了2階段索引來改善數據訪問性能.Chen等人[44]采用了類似的思想設計了一個分布式文件系統來存儲大量的小文件(比如應用中的大量圖片).

本節介紹的這些研究工作結合了分布式存儲系統的不同特點和糾刪碼更新特點，采用了不同對策來改善系統性能，但是糾刪碼本身的更新問題依然存在.

3 現有編碼方案的更新性能

目前已有的一些研究工作通常是考慮優化糾刪碼的一個方面.但是某些場景下，比如熱數據的存儲，系統對讀、寫、更新3種操作的性能需求都很高.有些工作對糾刪碼數據恢復性能做了優化工作，但是使得更新操作的流程更加復雜.為了能夠在降低熱數據存儲開銷的同時達到和多副本一樣的性能，需要從糾刪碼的編碼、解碼、更新3個方面去考慮優化.本節對目前一些比較有代表性的編碼方案進行了分析，這些編碼方案大多是為了優化數據恢復性能而專門設計的.為了衡量它們的更新性能，本節主要從網絡開銷和硬盤IO開銷2方面與多副本做對比.網絡和硬盤IO開銷具體指的是對條帶內1個數據塊就地更新時所需要傳輸和讀寫的數據量，如表2所示.不失一般性，更新模式采用PUM-P方式，利用1個專門的中心節點update manager來處理更新請求.

Table 2 Comparison of Update Cost of Codes

RS編碼是最流行的一種MDS碼，在很多分布式存儲系統中使用，比如Atlas[45],Colossus[46],f4.在RS(4,2)編碼中，更新條帶內的1個數據塊，通常采用增量更新方式來更新校驗塊.update manager從相應的數據節點讀出原數據塊計算數據增量，將增量發送到2個校驗節點，每個校驗節點分別讀出原校驗塊，計算最新校驗塊后寫到硬盤內，整個過程產生3個編碼塊的硬盤讀和寫以及4個編碼塊的網絡傳輸，比3副本多了3個編碼塊的硬盤讀操作和1個數據塊的網絡傳輸.

由于RS編碼將條帶內k個數據塊進行線性結合生成校驗塊，數據恢復時需要讀取剩余的k個塊才能執行解碼操作.為了減少數據恢復過程中需要的數據量，局部修復碼(local reconstruction codes, LRC)[47]被提出.LRC在RS編碼的基礎上引入局部校驗塊，在恢復數據時優先使用局部校驗塊，從而減少恢復過程需要的數據量.

圖3展示了LRC(6,2,2)編碼，其中k=6代表6個數據塊(d0，d1，d2，d3，d4，d5)，l=2代表2個局部校驗塊(p0，p1)，r=2代表2個全局校驗塊(p2，p3).6個數據塊被分為2組，分別對分組內數據塊線性結合得到局部校驗塊p0(由第1組d0，d1，d2線性結合得到)，p1(由第2組d3，d4，d5這3個數據塊線性結合得到).p2，p3由所有數據塊計算得到.在修復時優先使用局部校驗塊，從而減少數據恢復需要的數據量，改善糾刪碼恢復性能.當某個數據塊被更新時，需要更新對應的局部校驗塊和全局校驗塊，其產生的開銷和RS(6,3)編碼一樣.由于LRC只需要在標準RS編碼的基礎上引入局部校驗塊，實現簡單，所以已被Azure[48]，Facebook[49]使用.需要注意的是，LRC編碼本身不是MDS碼，數據恢復只能訪問固定的節點集合.相比于RS編碼，LRC編碼引入的局部校驗塊雖然可以降低恢復開銷，但是當不同分組內的數據塊被同時更新時，會引入額外的硬盤IO和網絡數據傳輸開銷.

Fig. 3 LRC(6,2,2) code

再生碼(regenerating codes)[50-51]RGC(n,k,x)是另一種減少糾刪碼恢復過程中網絡數據傳輸開銷的編碼,其能夠通過任意k個塊恢復整個條帶的數據，任意x(k≤x≤n-1)個節點能夠恢復單個節點故障.雖然RGC編碼需要更多的節點參與數據恢復，但是總的數據傳輸量更少，從而減少網絡開銷.由于在恢復過程中需要從更多的節點上讀取數據，雖然總的網絡傳輸的數據量減少，但是顯著增加了硬盤IO開銷和計算開銷.RGC編碼主要分為2類：一類是MSR碼，與RS編碼相比有同等存儲開銷，具有更低的網絡開銷；另一類是MBR碼，通過存儲更多冗余數據獲得更低的網絡開銷.由于MBR的存儲利用率較低，所以對其不做考慮.EMSR(4,2,3)碼[52]是一種MSR碼，利用干擾對齊技術同時消去多個不需要的變量，如圖4所示，每個數據塊劃分為2個子塊，每個校驗塊也包含2個校驗子塊.如果數據塊d0損壞，d1，p0，p1三個塊分別將子塊求和合并成單個子塊，然后發送到修復節點，修復節點通過對接收到的3個子塊進行計算得到d0.整個修復過程中，網絡中只需要傳輸3個子塊，若是RS(4,2)編碼，則需要傳輸4個子塊.若d0塊被更新，與其子塊a0，b0相關的所有校驗子塊都需要被更新.雖然EMSR(4,2,3)在更新過程中傳輸和讀寫的數據量和RS(4,2)相同，但是由于在校驗節點上更新校驗子塊的操作更復雜，導致其比RS(4,2)編碼消耗更多計算資源和硬盤IO資源.

Fig. 4 EMSR(4,2,3) code

Hitchhiker-XOR碼[18]是在現有的RS碼基礎上對其改造，將RS編碼中的2個條帶組合成1個更大的條帶.2個子條帶之間通過一些冗余信息產生關聯，從而減少恢復時所需要的數據量.如圖5所示，Hitchhiker-XOR(4,2)碼先對每個子條帶進行RS(4,2)編碼，然后將第2個子條帶內的第2個校驗塊與第1個子條帶內的數據塊進行異或運算.若a0，b0兩個數據塊出現損壞，可以先用b1，f1(b)恢復出b0，然后用b0和b1計算出f2(b)，最后利用f2(b)，a1和f2(b)+a0+a1恢復出a0.整個過程需要4個塊參與，這雖然與RS(4,2)編碼相同，但是這僅限于此實例.當子條帶內塊數量較大時，比如說10個數據塊、4個校驗塊時，恢復a0，b0只需要13個塊，相比于RS(14,10)，數據量減少了35%.由于一個子條帶內的某些數據塊信息會關聯到另一個子條帶內的校驗塊，所以更新開銷會相應增大.比如說更新a0，需要更新f1(a)，f2(a)，f2(b)+a0+a1三個校驗塊，更新b0則只需要更新f1(b)，f2(b)+a0+a1兩個校驗塊.雖然Hitchhiker-XOR碼減少了數據恢復所需要的數據量，降低了網絡傳輸開銷和硬盤IO開銷，但是卻導致了更新性能的削弱.

Fig. 5 Hitchhiker-XOR(4,2) code

因為多副本機制的數據更新過程類似于數據寫入過程，只需要將更新數據發送到相應節點寫入即可.以3副本為例，更新過程只需要3x的網絡傳輸和硬盤寫操作.表2中對比了各編碼方案的更新開銷，可以看出，優化了糾刪碼恢復性能的各類編碼都導致了糾刪碼更新性能的削弱，使得糾刪碼更新性能比多副本機制更差.由于目前糾刪碼的讀、寫、更新3種操作的性能都弱于多副本，使得熱數據存儲這種對性能要求較高的場景無法使用糾刪碼容錯機制，只能使用多副本來保證數據高可用，導致熱數據的存儲開銷很大.

4 未來研究趨勢

從第3節的分析可以看出，目前糾刪碼更新操作的性能仍然無法與多副本機制相媲美，所以糾刪碼大多用于冷數據或者溫數據這種一次寫入后很少被訪問和更新的場景，需要頻繁訪問和更新的熱數據仍然使用多副本機制來存儲.如何應用糾刪碼改善熱數據存儲開銷的同時，滿足系統性能需求是一個值得深入研究的方向.

伴隨著非易失性內存技術的不斷發展，計算機計算能力和存儲性能得到了質的提升.比如新興的電阻式隨機存取存儲器(RRAM)[53-54]不僅可以提供非易失性存儲，還可以提供矩陣向量乘法的內在邏輯.磁疇壁存儲器(domain-wall memory)[55],又被稱為賽道存儲器(racetrack memory)[56]，它在提供非易失性特性的同時，能夠提供和DRAM非常接近的訪問延遲、密度和功耗.筆者現有工作[57-58]利用其構建了內存計算架構極大地改善了系統的吞吐量、延遲和功耗.可以看出NVM的特性能夠很好地消除糾刪碼更新過程中的硬盤IO開銷，降低糾刪碼存儲系統的計算開銷和功耗，使糾刪碼用于熱數據存儲成為可能.但是NVM本身也具有一些缺點，比如在數據一致性方面，當節點因故障重啟后，NVM內部之前的數據還在，這些數據中有可能存在臟數據，這要求使用NVM的系統需要專門的管理機制來管理數據.再加上糾刪碼自身的編碼規則和特點，這勢必會增加系統設計的復雜度.如何結合NVM新硬件和糾刪碼自身特點，構建一個安全、高效的分布式存儲系統是一個值得深入研究的方向.

目前很多分布式存儲系統，尤其是云系統都是采用追加式更新的方式來更新數據.更新數據以新數據的形式寫入，原有數據被標記為無效數據.這樣將隨機寫轉化為順序寫操作，來優化寫的性能.這種日志結構存儲方式避免了糾刪碼更新所帶來的問題，但是引入了一個新的問題，就是無效數據所占用的空間回收問題.為了釋放掉無效數據占用的空間，垃圾回收功能被引入進來.垃圾回收是一個代價比較昂貴的操作，需要消耗大量的計算機資源，所以垃圾回收功能通常在節點空閑時被觸發，避免對系統性能產生影響.但是在熱數據的存儲場景中，更新操作頻繁，如果觸發垃圾回收的周期太長，就會使得大量無效數據聚集，降低存儲效率，頻繁觸發垃圾回收又會影響系統性能.而且，采用糾刪碼機制的日志結構存儲系統中的垃圾回收和傳統的基于多副本機制的日志結構存儲系統的垃圾回收有所不同.為了方便描述，本文將前者稱為ECGC(erasure coding garbage collection)，后者稱為MRGC(multiple replication garbage collection).MRGC和ECGC主要有3點不同：

1) 在MRGC中，垃圾回收的粒度通常以段(segment)或者塊(block)為單位.segment內的有效數據拷貝到新的位置后即可回收舊segment.但是在ECGC中，垃圾回收需要以條帶為粒度.由于1個條帶內數據塊和校驗塊之間存在著關聯性，為了保證條帶內數據的高可用，只有當條帶內所有有效的數據都安全地拷貝到新的位置后才可以回收舊條帶內的數據.

2) 條帶內的數據塊通常位于不同節點，如圖6所示，2個條帶內的數據塊和校驗塊均勻分布在集群內的每個節點上，如果對這2個條帶內的無效數據進行回收，就需要將條帶內的每個有效數據塊從相應節點上讀出，重新編碼持久化到不同節點，然后才可以刪除原來的條帶.這個過程涉及到集群內的每個節點，如果不仔細設計垃圾回收機制，ECGC有可能影響到整個集群處理上層請求的能力.MRGC則不存在這個問題.

Fig. 6 Data stripe distribution in erasure-coded storage systems

3) MRGC中1次回收的有效數據沒有長度限制，但是在ECGC中1次回收的有效數據的長度通常需要k個數據塊的整數倍，因為只有滿足(n,k)編碼的長度要求時才能進行編碼并持久化.這要求ECGC在選擇條帶進行垃圾回收時需要考慮到該特點.

為了不影響系統的延遲和吞吐量，使用糾刪碼機制的日志結構存儲系統需要一個針對糾刪碼優化的高效的垃圾回收機制，但是目前這方面的研究工作非常少.Li等人[59]設計了一個啟發式垃圾回收算法，其基本想法是將無效數據占用比例最大的條帶內的有效數據遷移到無效數據占用比例最小的條帶內，盡可能減少垃圾回收過程中數據塊的移動數量.為了進一步減少數據塊的移動，改善垃圾回收效率，他們利用工作負載中鍵傾斜分布的特點，對客戶端發來的數據按照熱度進行排序，將熱度相近的數據放置在相同的條帶內.因為熱度相同的數據更容易被一起訪問，被更新時無效數據就會更多地聚集在1個條帶內.如圖7所示，條帶1內有2個無效數據塊，條帶2內有1個無效數據塊，將條帶1內剩余的1個有效數據塊遷移到條帶2內，然后即可刪除條帶1.啟發式垃圾回收一定程度上減少了垃圾回收過程中數據的傳輸和讀寫，但是垃圾回收過程中所產生的數據遷移，相當于觸發了更多的數據更新請求，這些請求會和上層應用請求交錯在一起，占用系統網絡帶寬、硬盤IO等資源，使系統吞吐量和延遲產生波動.

Fig. 7 Heuristic garbage collection

以日志結構方式來更新數據消除了糾刪碼更新所導致的性能削弱，但是糾刪碼條帶內部數據一致性的特征導致垃圾回收活動有可能波及到存儲系統內的每個節點，導致系統性能波動，尤其是在熱數據存儲場景下.針對糾刪碼的特點設計一個高效的垃圾回收機制，在不影響系統響應上層請求能力的同時，降低存儲開銷值得深入探討.

5 總 結

隨著數據量的與日俱增，分布式存儲系統的開銷越來越大，多副本容錯機制使得這種情況更加嚴重.伴隨著硬件技術的不斷發展，越來越多的存儲系統將目光從多副本機制轉向糾刪碼，但是糾刪碼本身復雜的規則導致其性能較差.本文專注于糾刪碼存儲系統中的數據更新操作，從硬盤IO、網絡傳輸、系統優化3個方面對相關工作進行了總結分析,并對目前具有代表性的編碼方案的更新性能做了對比分析，最后展望了未來研究趨勢.與多副本機制相比，現有糾刪碼更新方案會產生更多網絡IO、硬盤IO開銷，導致糾刪碼存儲系統的更新操作的性能較差.如何結合新硬件技術特點，從糾刪碼編碼規則本身和系統架構角度對其優化，還存在巨大技術挑戰.目前較優的一種避免糾刪碼更新開銷的方案是采用日志結構追加式更新，但是如何設計一個高效的垃圾回收機制來應對熱數據這種頻繁更新的場景仍需探索.