一种近似最优的分布式存储系统磁盘修复算法  

An approximately optimal disk repair algorithm for distributed storage systems

作　　者：孙婧 梁松涛 路新江 Jing SUN;Songtao LIANG;Xinjiang LU(Internet Plus Lau Big Data Platform,East China University of Political Science and Lau,Shanghai 201620,China;Rich Media Dept.,Qiniu Information Technology Co.,Ltd,Shanghai 200433,China;The Business Intelligence Lab,Baidu Research Center,Beijing 100085,China)

机构地区：[1]华东政法大学互联网+法律大数据平台,上海201620 [2]七牛信息技术有限公司富媒体部,上海200433 [3]百度研究院商业智能实验室,北京100085

出　　处：《中国科学：信息科学》2020年第12期1834-1849,共16页Scientia Sinica(Informationis)

基　　金：国家重点研发项目(批准号:2018YFC0830900,2018YFC0830903)资助。

摘　　要：如何提升分布式存储系统中磁盘修复的速度,一直是磁盘修复问题中的难点.优化的途径有两种:一种是通过对解码算法的优化,减少修盘数据的传输量.另外一种方法是通过对修盘过程中数据流的调度,最大化地利用节点的计算能力、传输能力,进而加速修盘进程.本文从数据流的调度出发,根据数据流图和拓扑结构,计算出了节点的近似最优的修盘数据比例,并依照此比例,设计了分布式存储系统下的近似最优修盘调度算法(NOPT).对于主流的两种Reed-Solomon(RS)编码方式,本文做了等价性证明,并给出了编码转换矩阵.通过大量实验仿真可以看出,在预知系统拓扑的前提下,可以显著地减少通过交换机的流量,进而缩短修盘的时间.Effectively reducing disk repair time for distributed storage systems is an open problem.Generally,there are two directions,i.e.,constructing better erasure codes to reduce disk repair throughput,and dispatchingrepair tasks to reduce the data flow in switches.In this paper,by analyzing the repair data flow,we provide anapproximately optimal disk repair time.We also prove the best ratio of storage nodes for repairing and present theNOPT repair algorithm.We also prove the equivalence of the two decoding algorithms.The results of simulationexperiments demonstrate that the repair time is improved significantly and repair traffic is reduced notably.

关 键 词：REED-SOLOMON码 磁盘修复技术 分布式存储系统 

分 类 号：TP333[自动化与计算机技术—计算机系统结构]