基于纠删码的云存储数据扩展的理论与技术研究

Erasure coding has been adopted by many cloud storage systems due to its flexible fault tolerance and space efficiency, and data scaling is often triggered in cloud storage systems due to storage capacity increasing or dynamic application demands. However, it still lacks efficient schemes to reduce the storage resource (bandwidth, IO, etc.) consuming incurred by data scaling for erasure-coded cloud storage. Motivated by this, we start our studies based on cloud storage, use the information flow graph as the main modeling methodologies, adopt network coding as the main technique, work on private cloud data centers and public cloud key value stores, and study how to do the data scaling in erasure-coded cloud storage from theory to techniques, including: (1) we analyze the lower bound of erasure-coded data scaling bandwidth and design corresponding optimal scaling schemes; (2) we design adaptive erasure-coded data scaling mechanisms on demand and resource balancing algorithms according to erasure codes’ features; (3) we design and implement optimal scaling methods for regenerating codes and locally repairable codes with network coding; (4) we design and implement techniques using lazy parity-updating and multiple-hash-ring-based coding for optimizing erasure-coded data scaling. Our goal is to reduce the bandwidth and IO cost consumed by erasure-coded data scaling so as to lower running costs of cloud storage, and promote the application and diffusion of erasure-coded cloud storage.

纠删码由于其容错灵活、空间利用率高等特性而被云存储广泛采用，同时云存储常会因设备扩容或需求变化而触发数据扩展，然而针对基于纠删码的云存储系统，目前仍然缺乏有效机制去降低数据扩展时所造成的大量存储资源消耗(包括带宽、IO等)。本项目拟以云存储为出发点，以信息流图为建模分析方法，以网络编码为设计手段，以私有云数据中心和公有云键值存储为主要系统平台，从理论到技术对基于纠删码的云存储数据扩展进行研究，内容包括：(1)分析纠删码扩展的带宽下界，并在设计满足下界的最优扩展算法；(2)设计按需适配的纠删码扩展机制和针对纠删码特性的资源均衡扩展算法；(3)设计并实现基于网络编码的再生码和局部修复码的优化扩展方案；(4)设计并实现校验块延迟更新的扩展优化技术和多环编码的扩展优化技术。该研究主要目标是降低纠删码在数据扩展所产生的带宽和IO开销以降低云存储运营成本，从而促进纠删码在云存储应用和普及。

本项目基本按照申请的研究计划顺利进行，围绕着项目主要目标——面向云存储系统的纠删码“高效扩展”展开研究，并拓展到“高效修复”；同时在云存储系统在数据中心和键值存储的不同场景所面临的挑战研究了一系列基于网络编码和纠删码的数据扩展、修复技术，降低了云存储系统的网络开销和存储开销，以及编码计算开销。.项目围绕研究目标，从基于纠删码的云存储系统的高效扩展技术、高效修复技术、数据中心、键值系统四个方面展开研究：.（1）面向云存储系统，开展扩展带宽优化研究，建立基于信息流图的纠删码扩展和修复问题模型，分析一般扩展情况下扩展带宽下界，并且构建满足带宽下界的最优扩展算法，与最先进的技术相比，扩展时间可降低多达50％，大条带扩展时间最多可减少87.8%，相关结果发表在ACM/IEEE TON，ICDCS'21等CCF A类和B类会议期刊上；.（2）面向云存储系统，开展大比例纠删码下修复带宽优化研究，首次提出了极致成本的纠删码模型和修复算法，与基于局部性的最先进技术相比，复合局部性可将单块修复时间减少多达90.5%，冗余度仅为1.063x，为纠删码在低成本云存储系统部署提供了良好的技术支撑，相关结果发表在FAST'21，ICPP'21，计研发等CCF A类和B类会议（中文）期刊上；.（3）面向云存储数据中心，开展修复带宽优化研究，建立面向机架和异构网络的高效并行修复机制和流水线修复算法，与最先进的修复方案相比，单块修复和全节点修复的修复时间可以分别减少多达 71.27%和16.50%，为纠删码在数据中心的复杂拓扑下的高效修复提供了技术保障，相关结果发表在ICDCS'22，ICPP'21，SRDS'19等CCF B类会议上；.（4）面向云存储键值服务，开展扩展操作优化研究，针对一致性哈希架构下的纠删码扩展所带来的校验块更新的问题，实现一致性哈希架构下的存储扩展方案，本地集群和云端实验均表明本方案可以在节点扩展过程中大大提高数据吞吐量(最高8.3x)同时减少了降级读性能损耗(最高89.0%)，相关结果发表在SC'21，SoCC'19等CCF A类和B类会议上。.在项目资助的四年时间里，项目研究团队发表高水平论文共14篇，包括CCF A/B类期刊/会议论文共13篇，CCF A类中文论文1篇，申请国家发明专利10项（授权8项），并且培养硕博研究生14名。