信息存储系统教育部重点实验室

硕士生余祺、王霖论文被会议IPDPS 2023录用


近日,实验室硕士生余祺、王霖论文《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)。

注:本文为原创,如转载请注明出处。

分享文章

Share