容错存储系统的扩容问题研究

Disk failure is a common phenomenon in large storage systems, fault tolerance must be implemented in the current storage systems. On the other hand, the rapid growth of data and the growing demand of users on the system performance lead to necessary scaling to existing storage systems. With this project, we are to design effective scaling algorithms and the corresponding data migration algorithms for storage systems based on different fault-tolerant coding schemes, to optimize the system performance during scaling process, such as load balancing, the amount of data migration, I\O loads, update of parity data, metadata management, data consistency and data storage continuity, etc. Some specific research topics include: (1) The design of efficient scaling algorithms for different codes, such as a variety of RAID codes, erasure codes, regenerating codes; (2) For the above mentioned codes, designing efficient scaling algorithm to increase the fault tolerance capability of the storage systems; (3) For the different storage media storage systems, such as solid-state disk, hard disk, modelling the performance parameters during the scaling process, designing optimized scaling algorithms; (4) For a number of different system access patterns, analyzing the key factors which affect the performance of scaling algorithms, designing optimized online scaling algorithms; (5) Building a practical heterogeneous distributed storage system and implementing a variety of scaling algorithms atop this system to efficiently deploy the scaling algorithms in practice.

磁盘故障是大型存储系统中常见现象，容错已成为当前存储系统必备的基本功能。另一方面，数据量的高速增长以及用户对系统性能不断增长的需求导致存储系统需要扩容。本项目拟研究基于不同容错编码的存储系统的有效扩容算法与相应数据迁移算法，优化系统扩容过程中系统负载均衡、迁移数据量、I\O负载、校验块的更新、元数据的管理、数据一致性以及数据存储连续性等多方面的性能，具体的研究内容包括：（1）针对各种RAID编码、纠删码、再生码，设计系统扩容算法；（2）针对以上各种编码，设计增加容错能力的扩容算法；（3）针对不同存储介质的存储系统，如固态硬盘、传统硬盘，建立扩容过程中性能参数模型，设计优化的扩容算法；（4）针对一些不同的系统访问模式，通过其trace数据分析影响扩容算法性能的关键因素，设计优化的在线扩容算法；（5）建立一个实际的异构分布式存储系统，在此系统上实现各种扩容算法，优化扩容算法在实际系统中的部署。

本项目的实施过程中，共录用与发表论文33篇，其中CCF推荐的A类会议/期刊论文14篇、B类会议/期刊论文8篇，申请专利7项（已经授权2项）。培养毕业博士生4名、硕士生6名。共资助研究参加国际学术会议21人次，在2017年全国高性能计算学术年会上许胤龙教授做“高性能计算中的存储墙”的大会特邀报告；在2015年中国计算机大会上，许胤龙教授与清华大学舒继武教授作为共同主席，组织了“新型存储系统与系统构建”论坛，并做了“基于纠删码的容错存储系统”主题报告。. 本项目资助的主要成果有：.(1) Cauchy Reed-Solomon（CRS）编码是一种非常常用的容错编码。针对基于CRS编码的存储系统，首次提出了扩容前编码矩阵与扩容后编码矩阵同时综合设计的思想，并给出了相应的编码矩阵设计算法和数据迁移算法，能够保证扩容前后的编解码算法非常高效，而且保证扩容后的系统中数据块\校验块分布均衡、扩容过程中迁移数据量最少且校验块更新最少。.(2) 大规模存储系统中，常采用校验散布的纠删码来加速故障数据的恢复。针对基于校验散布纠删码的存储系统，我们首次设计了扩容算法。该算法可以同时兼顾存储容量的扩容与系统可靠性的增加，且能够达到扩容后的系统中数据块与校验块分布均衡、扩容过程中迁移的数据量达到最少且不需要更新校验块。.(3) 针对大规模存储系统，我们首次设计实现了一种分组编码OI-RAID。OI-RAID将所有节点分成一些组，组内节点之间与组间节点之间分别设计了编码算法。这样通过组内编码与组间编码可以达到更高的容错能力，而且可以根据实际需求，设计相应的编码，大大加速故障数据的恢复速度。.(4) 针对基于固态盘的RAID存储系统，设计了一个轻量级的冷热数据识别算法，该算法用很小的代价，能够达到90%以上的冷热数据识别率。进一步将该冷热数据识别算法应用于基于固态盘的阵列系统，在系统中分区域分别放置冷热数据，大大减少了阵列系统垃圾回收的开销和校验块更新导致的额外I/O操作，同时使得平均I/O响应时间减少到80%左右。