基于分布式存储的OHitchhiker码

发布时间：2021-01-12 02:00

　　为推进纠删码在分布式存储系统中的应用,研究提高系统修复效率的算法。Hitchhiker码作为一种最新的具有最优存储空间和较低修复成本的纠删码,已在Hadoop等分布式系统中部署实现。针对目前Hitchhiker码采用均分的数据分配模式,存在网络带宽浪费的问题,提出一种最优分配的Hitchhiker编码（optimal allocation of Hitchhiker,OHitchhiker）。通过在编码的分配环节引入一种动态选择分配算法,使得OHitchhiker码可以针对不同（n,k）值选择具有最小修复代价的编码结构。理论分析以及实验结果验证了OHitchhiker码在保持较低存储空间的同时,进一步降低了下载带宽。 

【文章来源】：计算机工程与设计. 2020,41(07)北大核心

【文章页数】：6 页

【部分图文】：

（n,k)=(13,10)3种纠删码

OHitchhiker码（n=13,k=10）的编码结构

以OHitchhiker码（n=13,k=10）为例，当节点Node8失效时，修复过程如图3所示。从图3中可以发现，当节点Node8失效时，OHitchhiker码首先通过下载{b1，…，b10,f1(b）}/b8，共10个数据，恢复出b8；然后根据DSDA算法生成分块情况S={4,3,3}，发现失效节点Node8中数据a8∈S3；所以先下载Node12中的第一子条带然后再下载Node13中的第二子条带计算得到f2(b）和f3(b），全进行异或操作得到最后通过下载{a9,a10}，异或恢复出a8，此时下载了4个数据。因此，OHitchhiker码（n=13,k=10）的修复过程需要下载图中灰色块部分，共14个数据块，其平均修复带宽βsysOHH=13.7。


本文编号：2971911