一种混合局部恢复码及Hitchhiker码的存储策略

作者：王梓仲; 王海霞; 邵艾然; 汪东升^*

来源：计算机学报, 2020, 43(04): 618-630.

• 纠删码
• 退化读
• 编码切换
• 容错
• 存储

我们正处于一个大数据的时代.如今一个分布式存储系统需要存放PB数量级数据的情况越来越常见.这些系统一般由普通商用组件构成,其出错率相对较高.由此,分布式存储系统需要保证数据的可靠性和可用性.多副本和纠删码是现在最为常用的技术.相比多副本技术,采用纠删码能在同等容错能力下大幅降低存储开销.然而,在进行数据恢复时,使用传统的纠删码(如Reed-Solomon码)会导致系统中产生大量的网络带宽消耗及磁盘读写操作,进而导致退化读延迟过高.注意到在系统中数据的访问频率呈Zipf分布,大多数数据访问只涉及到少量数据,而绝大多数数据的被访频率很低.根据这种数据访问的偏斜性,本文提出如下存储策略以解决采用纠删码的系统退化读延迟过高的问题:对被访频率高的热数据采用低恢复延迟的纠删码(如局部恢复码Local Reconstruction Code,LRC)进行编码,而对被访频率低的冷数据采用保证最小存储开销的纠删码(如Hitchhiker码)进行编码.由于热数据占据了绝大多数的数据访问,因此绝大多数的退化读也将应用在这些热数据上,这样这一策略就能在整个系统的角度获取低恢复开销的优势.同时,冷数据占据了系统绝大多数的数据量,且冷数据由保证最小存储开销的编码进行存储,因此这一策略的存储开销会很低.然而,对于混合存储策略而言,热数据可能会变冷,而冷数据也可能会变热,因此它需要配置一种编码切换过程.一个不恰当的编码切换过程会引起巨大的数据传输量,这是难以让人接受的.为了避免这一缺陷,本文提出了一种LRC和Hitchhiker码之间的高效切换算法.这一算法可以避免上述策略在部署时因冷热数据的转换出现系统瓶颈.在精心选取了两种编码并提出它们之间的高效切换算法后,本文提出的混合存储策略避免了现阶段其余混合存储策略的主要缺点.通过实验验证,此存储策略相较传统的ReedSolomon码在退化读延迟方面降低了55. 8%.在编码切换方面,切换延迟能分别降低为重新编码算法用时的13. 4%及33. 1%,且当数据从LRC切换为Hitchhiker码时(更为频繁出现的情况)的数据传输量能降至10%.

• 单位
  清华大学