近日，实验室硕士生余祺、王霖论文《Boosting Multi-Block Repair in Cloud Storage Systems with Wide-Stripe Erasure Coding》被International Parallel & Distributed Processing Symposium（IPDPS 2023）

概括：纠删码（Erasure Code）作为一种数据可靠性保障技术，被广泛应用在低成本、低冗余云存储架构中（例如，Azure Storage，Facebook F4，Microsoft Pelican）。近来，工业界推出了大比例纠删码的概念（例如，VAST）。所谓大比例纠删码，指的是纠删码的编码参数k很大，从而可以大幅减少冗余（(k+m)/k），进一步降低存储成本。然而，大比例纠删码会带来较为严重的修复放大问题，因为任意一个失效块都必须由k个幸存块重建。此外，较大的k会导致多块失效出现频率明显增加，而现有的多块修复方案都有不足之处：1）集中式修复策略（CR），会导致某个节点下载链路数量远多于其他节点；2）独立式修复策略（IR），一方面会受限于流水线中最慢的节点，另一方面会增大带宽消耗。因此，有必要针对多块修复提出一个可行且高效的方案。

图1 现有方案（CR和IR）示例

信息存储及应用实验室硕士余祺、王霖在冯丹教授、胡燏翀教授的指导下，分析了RS码的三大特性：1）MDS性质，（k，m）RS码中任意k个块都可以解码出任意一个块；2）线性特性，单块修复满足交换律和分配律；3）细粒度修复特性，由于每个块的最小编码单位是w位字，因此一个条带中，处于不同块的相同偏移的数据可以被一起编解码。基于以上三个特性，文章提出了一种混合式的多块修复方案HMBR。HMBR利用一个比例p0（可视为一个自适应变量），将一个条带的块分割成上子块和下子块，并指示上、下子块并行修复，其中上子块采用CR策略，下子块采用IR策略。文章从理论上证明了可以由各个节点可用带宽生成p0，且当分割比例为p0时理论多块修复时间最优。此外，文章针对可能出现的场景提出了两种拓展策略：1）异构网络，HMBR在此场景下以少量额外带宽为代价，大量减少跨机架传输链路，减少多块修复时间；2）多节点修复，HMBR基于LFS和LRS调度策略，平衡节点传输流量。实验结果显示HMBR在多个场景下均优于传统CR、IR方案：1）多块修复最多减少64.8%的修复时间；2）异构网络优化版本最多减少55.3%修复时间；3）多节点修复优化版本最多减少15.9%修复时间。

图2 实验结果

该研究于2022年12月被37th IEEE International Parallel & Distributed Processing Symposium（IPDPS 2023）录用，题为“Boosting Multi-Block Repair in Cloud Storage Systems with Wide-Stripe Erasure Coding”。IPDPS是并行和分布式计算方向计算机系统领域的旗舰会议。该工作得到了的支持。该工作得到了国家自然科学基金No. 62272185，No. 61821003）以及国家重点研发计划青年科学家项目的支持（2021YFB0301400）。