分布式存储系统中数据副本管理机制

分布式存储系统(Distributed Storage Systems)是基于存储服务器集群(Cluster)和分布式文件系统，将网络中大量各种不同类型的存储设备通过应用软件集合起来协同工作，并通过各种相应的应用软件或应用接口，共同为用户提供高可用、高可靠的数据存储和业务访问功能的存储资源系统。为了保证数据安全、可用、可靠、可扩展性和服务的高效、连续性，分布式存储系统需要完善的数据多副本创建、部署、选择、定位和一致性管理机制。随着互联网中的用户对资源的需求量日益增多，如果仅有一份数据，则需要该数据的用户都须到同一个节点上读取它，网络容易出现拥塞，而处理能力有限的节点也会因为访问数量太大而宕机。然而，创建多份数据副本，并将它们合理分布在多个服务器节点上，分担处理访问请求的任务，可以有效降低节点失效率，减少用户响应时间。
 

文中详细分析了目前国内外对分布式存储系统中的副本管理机制研究现状，重点对副本创建、副本定位、副本一致性维护和副本撤销机制进行深入的研究，并从数据可用性、节点负载均衡、数据一致性和带宽消耗等性能指标进行了系统的分析。
 

某一节点上的数据被频繁访问使得该服务器节点负载过重时，或出于提高可靠性的考虑时，可将数据复制一份或多份副本并存储到其它节点上。
 

副本数量对分布式存储系统的可用性的影响很大，创建太少容易产生数据热点问题，延长访问时间，太多则会造成无谓的存储空间浪费。很多存储系统复制的默认数据副本数是3份，即在数据投入使用时复制3份它的副本，之后根据具体情况来创建和撤销副本。

文献根据副本复制的数量可将副本复制方法分为3种：均匀复制，所有数据对象复制相同数量的副本;比例复制，复制数量与被访问频率成正比;方根复制，复制数量与被访问频率的方根成正比。方根复制在平均查询距离和副本利用率方面具有较理想的性能表现。文献经模拟实验得出当副本的生命周期较长和副本密度较高时更能体现方根复制方法的优势。虽然副本复制的数量一般被认为应该正比于原数据大小的平方根，而文献的研究结论表明，副本复制的数量应该反比于原数据大小的平方根。

副本复制策略分为路径复制、源请求复制、邻居节点复制、随机复制和优先级复制五种：

(1)路径复制。发送副本给请求路径上的所有节点。优点是实现原理简单，方便数据的查找;缺点是创建的副本数量供过于求，且增加了副本的一致性维护的开销。

(2)源请求复制。只发送副本给请求节点。LAR(Lightweight Adaptive Replication，轻量级自适应的复制方法)算法是美国马里兰大学研究人员提出的经典源请求复制算法，其主要思想是：当访问请求到达目的节点时，若目标节点未过载，则能读取数据，若目标节点处理能力不够，将创建一份新副本，而且如果请求节点未过载，才把新创建副本发给该请求节点，并告知请求路径上所有节点该请求节点上也有该数据副本。优点是对于目的节点来说，减少了副本的复制数量;缺点是请求路径上有该副本且达到复制阈值的节点都存一份副本到请求节点上，易造成请求节点过载。
 

(3)邻居节点复制。对网络数据都保存访问历史记录，节点将被频繁访问的副本新建一份发送给频繁请求的节点的邻节点，当请求节点再次访问该数据时，可以到其邻居节点直接读取数据了，从而减少了请求的跳数。该方法缺点在于历史记录预测会有一定概率的失误。

(4)随机复制。随机选择一个或多个节点来存放副本，有随机选择的对象是请求路径上的节点和整个网络的节点两种策略，后者主要运用多哈希函数和关联哈希两种方法。多哈希函数的优点是可以动态调整副本的数目;副本被高度分散了，有益于负载均衡;缺点是管理多个哈希函数是个复杂的工作。关联哈希的优点是明显减少了访问时延;缺点是产生较大的副本数量和系统开销。
 

(5)优先级复制。请求发生就向已经有副本的节点发送所需副本，直至饱和，再选择别的节点来存储副本。优点是减少了存放副本的节点数，减低了节点的维护开销;缺点是存放副本的节点易过载，容易出现新一轮的访问热点问题。
 

通过比较这5种副本分布方法，可以发现路径复制和优先级复制方法不够灵活、效率相对较低，其它3种方法可以在大多数分布式网络环境下使用并能解决热点问题。
 

文献提出了一种渐进优化的选举和分区合并算法来存储多个副本，以求得目标区域中的最佳存储节点。方法假设要存储n个副本，先将拓扑结构划分为多个区域，每个区域都有一个服务节点，即该区域内最适合放置副本的节点，然后根据选举法，选举过程中，考虑了客户的分布情况、访问频率、通信时延和节点的处理能力四个因素，每次淘汰一个区域，并有调整剩余区域的环节，经过多次的选举淘汰区域调整，最终将整个网格划分为n个区域，这n个区域的服务节点就是最佳存储节点。

文献提出一种网格环境下的多副本后向预测调度的算法。方法与邻居节点复制策略有些相似，也是根据已收集的历史数据来预测合适的存储节点，不同的是在发生负载失衡情况之前将副本直接存储到选出的节点而不是它们的邻居节点。
 

网络系统的一个重点问题是如何实现负载均衡，通过新副本的添加或撤销能达到这一目的，另外一种常用的方法则是数据迁移。虚拟节点技术的核心思想就是数据迁移。数据虚拟节点是存储数据文件、路由定位的基本单元，一个物理节点可管理多个虚拟节点。若一个物理节点过载，则将其管理的部分虚拟节点转移给其它物理节点管理，数据将随之转移。
 

虚拟节点技术有一对一、一对多和多对多这三种策略。虚拟节点策略的缺点在于实现复杂。由于复制技术本身已包含分布策略，且虚拟节点技术必须是在拥有足够数量的副本才能实现，所以虚拟节点技术更适合于与复制技术结合使用。
 

节点访问数据性能表现的优劣很大程度上受到数据定位策略的影响，即如何快速定位出目标数据所在节点的位置，然后读取数据。

传统的基于覆盖网(Overlay network)的副本定位算法虽然在不同程度上解决了副本定位效率、负载均衡和可扩展性等问题，但目标节点不能很好地满足特定应用的服务质量需求 。文献提出一种多维度服务质量约束的副本定位方法，通过采用分层和对等的混合定位机制，在高效定位的同时，还保证目标节点提供有效的服务质量。方法基于区域内分层、区域间对等的覆盖网拓扑结构，运用了区间路由算法、副本信息发布算法、站内副本算法、区内副本定位算法和区间副本定位算法等五个算法，使大量副本定位在本区域完成，从而有效降低了定位延迟，以满足特定应用的多维度服务质量规约作为副定位标准，有效地保障了目标节点的服务质量。