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

发布时间：2021-08-21 12:31

　　我们正处于一个大数据的时代.如今一个分布式存储系统需要存放PB数量级数据的情况越来越常见.这些系统一般由普通商用组件构成,其出错率相对较高.由此,分布式存储系统需要保证数据的可靠性和可用性.多副本和纠删码是现在最为常用的技术.相比多副本技术,采用纠删码能在同等容错能力下大幅降低存储开销.然而,在进行数据恢复时,使用传统的纠删码（如Reed-Solomon码）会导致系统中产生大量的网络带宽消耗及磁盘读写操作,进而导致退化读延迟过高.注意到在系统中数据的访问频率呈Zipf分布,大多数数据访问只涉及到少量数据,而绝大多数数据的被访频率很低.根据这种数据访问的偏斜性,本文提出如下存储策略以解决采用纠删码的系统退化读延迟过高的问题:对被访频率高的热数据采用低恢复延迟的纠删码（如局部恢复码Local Reconstruction Code,LRC）进行编码,而对被访频率低的冷数据采用保证最小存储开销的纠删码（如Hitchhiker码）进行编码.由于热数据占据了绝大多数的数据访问,因此绝大多数的退化读也将应用在这些热数据上,这样这一策略就能在整个系统的角度获取低恢复开销的优势.同时,冷数据占据了系统... 

【文章来源】：计算机学报. 2020,43(04)北大核心EICSCD

【文章页数】：13 页

【部分图文】：

5个HDFS集群的数据访问频率分布图[15],CC{1,2,3,4}表示4个不同的Cloudera上的集群，FB表示Facebook的一个实际集群

(6,2,2)LRC（例）[11]

图3展示了一个（10,4)RS码应用于Piggybacki‐ng框架的例子，图4给出了图3对应的HH码.在图4中，如果要恢复第一个数据块，即a1和b1，可以先利用b2、b3、…、b10和f1(b）恢复b1，进而求得f2(b）.在读取a2、a3以及子条带b中的第12个子块f2(b）⊕a1⊕a2⊕a3后，进行异或运算即可恢复得到a1.图4(10,4)Hitchhiker码（例）[12]


本文编号：3355607