论文部分内容阅读
构建于大量节点之上云存储方便易用、成本低廉且可弹性扩展，被广泛用来保存人们快速产生的海量数据。根据节点分布，云存储可分为单中心云存储、跨中心云存储和P2P云存储三类。前二者通过运营包含大量服务器的一个或多个数据中心来提供服务；P2P云存储则通过大量租用个人闲置的存储空间和网络带宽来提供服务。对于任何一类云存储，采用容错技术以保证数据不因节点失效而丢失都至关重要。基于纠删码的容错技术容错能力更强且存储效率更高，近年来广泛替代了传统基于副本的容错技术。然而，由于基于纠删码的容错技术更为复杂，其在云存储中面临着以下问题：（1）数据编码包括数据分块、数据运算和数据分发等操作，已有的编码方法或者消耗了过多的I/O资源或者具有低下的数据读写速度；（2）数据修复时每修复一个失效块都需要传输多个块并进行复杂的运算，已有的数据修复方法不能有效降低数据传输开销并提高数据修复效率。近年来，跨中心云存储和P2P云存储的兴起使这些问题变得更加突出。本文针对这些技术难题，综合考虑各类云存储的特点，对纠删码容错技术中的数据编码问题和数据修复问题展开深入研究，主要贡献如下：
已有的数据编码方法或因需要进行容错技术转换而产生过多的网络传输和磁盘读写，或因使用离散分块方式而严重降低了数据读写速度，尤其不适用于跨中心云存储。针对此问题，本文面向单中心云存储和跨中心云存储研究提出了一种基于流水线的分布式渐进编码方法PDCE。PDCE采用连续分块，以流水线的方式将新写入的数据传输到多个节点，在数据流过编码节点的同时直接对数据进行渐进式编码并将中间数据缓存在内存中，随着数据的写入逐步地在多个编码节点上分别产生校验块，最终再存储到相应的节点上，既可获得最优的数据写入效率，也无需进行容错技术转换。通过调节编码节点的数量，PDCE可以灵活地权衡编码完成之前的容错能力与编码的网络传输开销。理论分析和单中心以及跨中心环境下的大量实验表明，PDCE能够在网络传输和磁盘读写量与数据读写效率之间取得更好的权衡。具体地，与已有的数据编码方法相比，PDCE在取得接近最优数据读写效率的同时，可将网络传输减少44.5%–48.4%，可将磁盘读写减少45.6%–66.7%。
在已有的数据修复方法中，绝大部分数据传输都要经过网络拓扑中的瓶颈链路，如数据中心内部网络的核心层链路和数据中心之间的链路。这不仅严重限制了总体修复效率，也对系统中正常的数据读写造成了不利影响。针对此问题，本文面向单中心云存储和跨中心云存储研究提出了一种局部性感知的树型修复方法LATR。LATR先根据网络拓扑信息或节点之间延迟确定数据的局部性，然后根据局部性构建一棵以替代节点为根覆盖所有提供节点的最小生成树作为修复树。修复时，数据从修复树的叶节点开始向上传输，在内部节点合并后继续向上传输，依此类推，直至到达根节点完成修复。这使得距离较近的数据就近合并后再传输到较远的地方与其它数据合并，减少了经过上层链路的数据量。此外，LATR采用一种基于局部性的提供节点选择算法，可在有多种选择时迅速挑选出最优的提供节点组合。分析表明，LATR修复时的核心层流量比已有修复方法低20%–61%。大量实验表明，LATR可将主动修复吞吐率提高至少23%，可将降级读取速度提升高达68%。
P2P云存储中节点的上传带宽常常远低于其下载带宽，使数据上传成为严重的性能瓶颈。已有数据修复方法均未考虑到这一特点，导致它们在P2P云存储中的数据修复效率较低。针对此问题，本文面向P2P云存储研究提出了一种基于分片的分布式星型修复方法FDSR。FDSR采用一种“分散-聚合”的双层修复框架，先将编码块分成多个大小相同的编码片，然后使用多个修复节点以星型修复方法并行地修复失效编码片，对于不同的失效编码片选用不同的提供节点组合，最后再将修复出的编码片聚合至替代节点完成修复。通过使尽可能多的可用节点作为提供节点，FDSR减少了单个提供节点需要上传的数据。采用星型方法作为底层修复方法使FDSR可以同时适用于单点失效和多点失效的修复，而多个修复节点分散修复的方式则避免了传统星型修复方法负载不均衡的问题。理论分析表明，FDSR中提供节点的上传数据量明显低于现有方法，并且FDSR的整体负载更加均衡。大量实验表明，与已有数据修复方法相比，FDSR可将单点失效时的数据修复速度提高33.2%–87.8%，将多点失效时的数据修复速度提高78.4%–110.0%。
已有的数据编码方法或因需要进行容错技术转换而产生过多的网络传输和磁盘读写，或因使用离散分块方式而严重降低了数据读写速度，尤其不适用于跨中心云存储。针对此问题，本文面向单中心云存储和跨中心云存储研究提出了一种基于流水线的分布式渐进编码方法PDCE。PDCE采用连续分块，以流水线的方式将新写入的数据传输到多个节点，在数据流过编码节点的同时直接对数据进行渐进式编码并将中间数据缓存在内存中，随着数据的写入逐步地在多个编码节点上分别产生校验块，最终再存储到相应的节点上，既可获得最优的数据写入效率，也无需进行容错技术转换。通过调节编码节点的数量，PDCE可以灵活地权衡编码完成之前的容错能力与编码的网络传输开销。理论分析和单中心以及跨中心环境下的大量实验表明，PDCE能够在网络传输和磁盘读写量与数据读写效率之间取得更好的权衡。具体地，与已有的数据编码方法相比，PDCE在取得接近最优数据读写效率的同时，可将网络传输减少44.5%–48.4%，可将磁盘读写减少45.6%–66.7%。
在已有的数据修复方法中，绝大部分数据传输都要经过网络拓扑中的瓶颈链路，如数据中心内部网络的核心层链路和数据中心之间的链路。这不仅严重限制了总体修复效率，也对系统中正常的数据读写造成了不利影响。针对此问题，本文面向单中心云存储和跨中心云存储研究提出了一种局部性感知的树型修复方法LATR。LATR先根据网络拓扑信息或节点之间延迟确定数据的局部性，然后根据局部性构建一棵以替代节点为根覆盖所有提供节点的最小生成树作为修复树。修复时，数据从修复树的叶节点开始向上传输，在内部节点合并后继续向上传输，依此类推，直至到达根节点完成修复。这使得距离较近的数据就近合并后再传输到较远的地方与其它数据合并，减少了经过上层链路的数据量。此外，LATR采用一种基于局部性的提供节点选择算法，可在有多种选择时迅速挑选出最优的提供节点组合。分析表明，LATR修复时的核心层流量比已有修复方法低20%–61%。大量实验表明，LATR可将主动修复吞吐率提高至少23%，可将降级读取速度提升高达68%。
P2P云存储中节点的上传带宽常常远低于其下载带宽，使数据上传成为严重的性能瓶颈。已有数据修复方法均未考虑到这一特点，导致它们在P2P云存储中的数据修复效率较低。针对此问题，本文面向P2P云存储研究提出了一种基于分片的分布式星型修复方法FDSR。FDSR采用一种“分散-聚合”的双层修复框架，先将编码块分成多个大小相同的编码片，然后使用多个修复节点以星型修复方法并行地修复失效编码片，对于不同的失效编码片选用不同的提供节点组合，最后再将修复出的编码片聚合至替代节点完成修复。通过使尽可能多的可用节点作为提供节点，FDSR减少了单个提供节点需要上传的数据。采用星型方法作为底层修复方法使FDSR可以同时适用于单点失效和多点失效的修复，而多个修复节点分散修复的方式则避免了传统星型修复方法负载不均衡的问题。理论分析表明，FDSR中提供节点的上传数据量明显低于现有方法，并且FDSR的整体负载更加均衡。大量实验表明，与已有数据修复方法相比，FDSR可将单点失效时的数据修复速度提高33.2%–87.8%，将多点失效时的数据修复速度提高78.4%–110.0%。