云文件系统中纠删码技术的研究与实现

云文件系统凭借高性能、高扩展、高可用、易管理等特点,成为云存储和大数据的基础和核心。云文件系统一般采用完全副本技术来提升容错能力,提高数据资源的使用效率和系统性能。但完全副本的存储开销随着副本数目的增加呈线性增长,存储副本时造成额外的写带宽和数据管理开销。纠删码在没有增加过量的存储空间的基础上,通过合理的冗余编码来保证数据的高可靠性和可用性。研究了纠删码技术在云文件系统中的应用,从纠删码类型、编码对象、编码时机、数据更改、数据访问方式和数据访问性能等六个方面,对云文件系统中纠删码的设计进行了探究,以增强云文件系统的存储模型。在此基础上,设计并实现了纠删码原型系统,并通过实验证明了纠删码能有效地保障云文件系统的数据可用性,并且节省存储空间。     

基于多级网络编码的多副本云数据存储

云数据存储的快速发展对数据的可用性提出了较高要求.目前,主要采用纠删码计算数据编码块进行分布式冗余数据存储来保证数据的可用性.虽然这种数据编码技术保证了存储数据的安全性并减少了额外的存储空间,但在损坏数据恢复时会产生较大的计算和通信开销.提出一种基于多级网络编码的多副本生成和损坏数据恢复算法.算法基于多级网络编码对纠删码的编码矩阵进行改进形成多级编码矩阵,利用其级联性生成多级编码(hierarchical coding,HC码)来构成多副本数据,使得各副本之间存在编码关系.在损坏数据恢复时,利用数据所有者提供的数据编码信息和云存储中保存的数据块直接计算进行恢复,从而避免从云存储中远程下载数据.理论分析和实验表明,所提算法在相同的存储空间下显著减少了损坏数据恢复时的通信开销并提高了数据的可用性.     

基于数据挖掘的存储数据纠删码容错方法仿真

在存储数据的纠删码容错中,针对传统存储数据纠删码容错方法容错速度较低的问题,提出一种基于数据挖掘的存储数据纠删码容错方法。采用数据挖掘方法对存储数据纠删码进行重构,计算存储数据纠删码的丢失片段;利用CHR算法对存储数据纠删码进行异构修复,通过建立存储数据纠删码容错模型实现存储数据的纠删码容错。为了验证存储数据纠删码容错方法的有效性,将存储数据纠删码容错方法与传统存储数据纠删码容错方法进行对比,实验结果得出:上述方法与基于流水线的存储数据纠删码容错方法、基于RapidRaid码的存储数据纠删码容错方法、基于非规则LDPC码的存储数据纠删码容错方法的容错速度分别为:286Mbps/s、262Mbps/s、243Mbps/s、232Mbps/s,比较可知,所提方法的容错速度最快,证明了上述方法的优越性。     

一种云存储系统数据持久存储机制

针对云存储中的可靠性产生的担忧,提出一种云存储系统完善的数据存储保障机制,以保证系统的高可靠性和数据的高可用性。在处理与数据持久存储的相关的数据分片、数据分发、完整性检查以及冗余数据的维护中,引入基于纠删码的数据冗余机制,与传统的复制冗余方案相比,能够在获得相同的数据可用性时降低存储空间和网络带宽的开销多达50%以上。采用基于缓冲区的分段读入编码对纠删码算法进行优化后,提高了对文件分片与合并的平均编码速率。     

分布式存储方案的设计与研究

针对基于纠删码的分布式存储方法中信息分割算法IDA在运算中涉及构造拆分矩阵,计算开销大,且单纯基于纠删码的方案无法确保所存储数据的完整性、机密性等特性,只能够容忍系统中存在的良性故障,无法容忍入侵者的恶意入侵。提出了分布式系统中一种基于Tornado码的浏览器-服务器工作模式的数据存储方案。在数据写入过程中通过构造编码后数据分块的Hash值级联（即数字指纹）,并与每个数据分块一起分布在存储服务器集中的不同服务器中,当需要读出时对分块及数据指纹进行验证,然后利用Tornado译码方法恢复原始文件,即可实现Byzantine环境数据的完整性保护,并提高了系统的容错能力。     

分布式存储方案的设计与研究

针对基于纠删码的分布式存储方法中信息分割算法IDA在运算中涉及构造拆分矩阵,计算开销大,且单纯基于纠删码的方案无法确保所存储数据的完整性、机密性等特性,只能够容忍系统中存在的良性故障,无法容忍入侵者的恶意入侵.提出了分布式系统中一种基于Tomado码的浏览器-服务器工作模式的数据存储方案.在数据写入过程中通过构造编码后数据分块的Hash值级联(即数字指纹),并与每个数据分块一起分布在存储服务器集中的不同服务器中,当需要读出时对分块及数据指纹进行验证,然后利用Tomado译码方法恢复原始文件,即可实现Byzantine环境数据的完整性保护,并提高了系统的容错能力.     

异构环境下纠删码的数据修复方法综述*

在大规模云存储系统中,由于磁盘或网络故障造成的存储节点失效事件频发,系统需要数据冗余技术以保证数据的可靠性和可用性。纠删码,相对于副本方式而言,能大大提高存储空间的利用率,但纠删码在冗余数据修复方面的代价较副本方式高很多。目前针对纠删码的冗余数据修复研究大都无差别对待每个存储节点,然而实际分布式存储系统中,节点通常存在带宽资源、计算资源、存储容量资源等方面的差异性,这些资源的异构性对冗余数据修复性能影响很大。本文指出影响修复性能的关键因素,选取带宽开销、磁盘访问开销、修复时间、参与修复的节点数量和修复代价作为修复性能的评价标准;分析了现有研究方法如何降低这五种开销,重点讨论了这些方法的优缺点;阐述当前异构分布式存储系统中纠删码修复技术的研究现状;最后指出纠删码数据修复技术中尚未解决的一些难题和未来纠删码修复技术可能的发展方向。     

分布式系统中纠删码容错机制的研究与实现

为降低分布式系统中容错机制的存储开销,在分布式文件系统中使用纠删码容错机制。本文总结纠删码容错机制实现的几个理论基础,并分析其系统可靠性,在阐明实现该机制的具体步骤后对几个关键算法模块进行了说明,最后对该机制在分布式系统环境下进行实验。实验结果表明,该机制能够有效地恢复受损数据。在合理的缓存块大小和文件分块数策略下,该机制的编、译码率能够较好地匹配局域网中的网络传输速率,且能够节省存储空间。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法,与多副本技术相比,能够以较低的存储开销提供较高的数据可靠性;然而,纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题,提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集,然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码,以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量,从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时,依然保留着较高的容错能力,且为满足分布式存储系统的不同需求,可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示,与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比,RGRC只需要增加少量的存储开销,就能降低单节点修复14%~61%的修复成本,同时减少14%~58%的修复时间。     

分布式存储系统中的低修复成本纠删码

纠删码技术是分布式存储系统中典型的数据容错方法，与多副本技术相比，能够以较低的存储开销提供较高的数据可靠性；然而，纠删码修复成本过高的特点限制了其应用。针对现有纠删码修复成本高、编码复杂和灵活性差的问题，提出一种编码简单的低修复成本的纠删码——旋转分组修复码（RGRC）。RGRC首先将多个条带组合成条带集，然后利用条带之间的关联关系对条带集内的数据块进行分层旋转编码，以此得到相应的冗余块。RGRC大幅度地减少了单节点修复过程中所需要读取和传输的数据量，从而能节省大量的网络带宽资源。同时RGRC在解决单节点修复成本高的问题时，依然保留着较高的容错能力，且为满足分布式存储系统的不同需求，可以灵活地权衡系统的存储开销和修复成本。在分布式存储系统中进行的对比实验分析结果展示，与其他常用的RS（Reed-Solomon）码、LRC（Locally Repairable Codes）、basic-Pyramid、DLRC（Dynamic Local Reconstruction Codes）、pLRC（proactive Locally Repairable Codes）、GRC（Group Repairable Codes）、UFP-LRC（Unequal Failure Protection based Local Reconstruction Codes）相比，RGRC只需要增加少量的存储开销，就能降低单节点修复14%~61%的修复成本，同时减少14%~58%的修复时间。     

Hierarchical codes: A flexible trade-off for erasure codes in peer-to-peer storage systems

Redundancy is the basic technique to provide reliability in storage systems consisting of multiple components. A redundancy scheme defines how the redundant data are produced and maintained. The simplest redundancy scheme is replication, which however suffers from storage inefficiency. Another approach is erasure coding, which provides the same level of reliability as replication using a significantly smaller amount of storage. When redundant data are lost, they need to be replaced. While replacing replicated data consists in a simple copy, it becomes a complex operation with erasure codes: new data are produced performing a coding over some other available data. The amount of data to be read and coded is d times larger than the amount of data produced, where d, called repair degree, is larger than 1 and depends on the structure of the code. This implies that coding has a larger computational and I/O cost, which, for distributed storage systems, translates into increased network traffic. Participants of Peer-to-Peer systems often have ample storage and CPU power, but their network bandwidth may be limited. For these reasons existing coding techniques are not suitable for P2P storage. This work explores the design space between replication and the existing erasure codes. We propose and evaluate a new class of erasure codes, called Hierarchical Codes, which allows to reduce the network traffic due to maintenance without losing the benefits given by traditional erasure codes.     

A Distributed Fault-Tolerant Design for Multiple-Server VOD Systems

Fault tolerance is an important design criterion for reliable and robust video-on-demand systems. Conventional fault-tolerant designs use either a primary backup or an active replication method to provide system fault tolerance. However, these approaches suffer from low utilization of the backup or replication system. In this paper we propose two playback-recovery schemes for distributed video-on-demand systems called the forward playback-recovery scheme and the backward playback-recovery scheme. Unlike conventional fault-tolerant designs, our schemes use existing playback resources to recover faulty playbacks without allocating new resources, significantly reducing recovery overhead. To use the schemes effectively, we developed a distributed algorithm for determining the order and gap information between the playbacks on the distributed video-on-demand servers so that overhead for recovering from a server failure can be minimized. This algorithm achieves N – 1 fault-tolerant resiliency for N-server video-on-demand systems. In addition, three server-recovery policies are also presented to guide surviving servers in applying the proper scheme to recover faulty playbacks, thus reducing overall recovery costs. Simulation results show that the proposed recovery schemes are effective and useful in designing fault-tolerant multiple-server video-on-demand systems.     

A dual-direction technique for fast file downloads with dynamic load balancing in the Cloud

File downloads make up a large percentage of the Internet traffic to satisfy various clients using distributed environments for their Cloud, Grid and Internet applications. In particular, the Cloud has become a popular data storage provider and users (individuals and corporates) are relying heavily on it to keep their data. Furthermore, most cloud data servers replicate their data storage infrastructures and servers at various sites to meet the overall high demands of their clients and increase availability. However, most of them do not use that replication to enhance the download performance per client. To make use of this redundancy and to enhance the download speed, we introduce a fast and efficient concurrent technique for downloading large files from replicated Cloud data servers and traditional FTP servers as well. The technique, DDFTP utilizes the availability of replicated files on distributed servers to enhance file download times through concurrent downloads of file blocks from opposite directions in the files. DDFTP does not require coordination between the servers and relies on the in-order and reliability features of TCP to provide fast file downloads. In addition, DDFTP offers efficient load balancing among multiple heterogeneous data servers with minimal overhead. As a result, we can maximize network utilization while maintaining efficient load balancing on dynamic environments where resources, current loads and operational properties vary dynamically. We implemented and evaluated DDFTP and experimentally demonstrated considerable performance gains for file downloads compared to other concurrent/parallel file/data download models.     

结合社区发现和局部恢复码的区块链扩容研究

区块链全节点需要存储完整的账本,不能满足数据快速增长的需求,其存储扩容成为当前研究热点之一。现有最优研究成果虽然结合分片和RS(Reed-Solomon)纠删码技术,降低了存储开销,实现了数据可恢复,但存在网络开销较高和跨节点数据请求效率较低的问题。因此,提出了一种基于社区发现和局部恢复码（local reconstruction codes,LRC）的区块链存储扩容方案,一定程度上解决了这些问题。改进现有基于传导性的社区发现方法,在此基础上提出了一种区块链节点分组方法,使平均连接速度更快的节点分为一组,有效地缩短了跨节点请求区块的响应时间;采用了更优的LRC码来替代RS纠删码,利用更少的原始数据实现单点故障数据恢复,降低了网络开销。大量实验结果表明提出的存储方案在保持目前最优方案的数据恢复能力和存储开销的基础上,能有效减少网络开销和跨节点请求区块的时间。     

网格环境下基于编码机制的数据复制研究

本文提出了基于编码机制的网格数据复制思想,通过对副本数据进行线性分组编码,并将其分散保存到网格存储节点,可形成具有纠删能力的编码子副本组.针对目前热点研究的线性分组编码,探讨基于Cauchy Reed-Solo-mon Code、Tornado Code和Random Linear Code的编码数据复制方案,通过建模手段讨论三者的副本数据访问性能和副本数据可靠性,并与传统的完整数据复制和分块数据复制进行时比分析,证明所提出的编码数据复制有着较优的综合性能.具体实验数据进一步说明,编码副本的编码开销占整个数据复制开销的较小比例,表明编码数据复制是具有可行性的技术方案.     

减少重建数据量的冗余编码技术研究

为防止硬件故障或机器宕机导致的数据丢失,冗余编码技术被广泛应用于分布式存储系统中来保证数据的可靠性。然而,传统的冗余编码技术,如里德-所罗门码,存在着重建数据量大的问题。副本技术在重建丢失数据时只需要读取和传输丢失的数据,而冗余编码需要读取和传输更大的数据量,从而消耗更多的磁盘I/O带宽和网络带宽。因此,基于冗余编码的分布式存储系统在重建数据时将消耗更长的时间,从而将整个系统长时间暴露在一种降级的模式下,进而增加了发生永久性数据丢失的风险。为解决这个问题,减少重建数据量的冗余编码技术不断被提出,然而只有这些冗余编码与传统的里德-所罗门码的比较,缺少它们在存储系统的综合比较。系统地从减少重建数据量等几个重要方面研究了这些减少重建数据量的冗余编码技术,从而为实际系统中采用合适的编码提供重要参考和依据。