论文部分内容阅读
数据网格作为一种大型分布式系统，具有数据分散存储、数据I/O吞吐量大、节点间拓扑结构易变等特性。而适应数据网格特性的“动态副本分布”能够为地理位置上广泛分布的各类数据网格应用提供一种高可靠性或可用性、低副本存取延迟的数据访问性能。目前的数据网格社区在副本分布问题上的研究主要集中在提高数据可靠性的静态副本分布上，且通常都以副本为只读或牺牲副本一致性为前提，无法应对那些副本访问模式动态变化或有副本一致性要求的数据网格应用。另外，在数据网格中引入了大量动态分布的数据副本，会为另一个决定副本高效存取的副本定位问题带来新的挑战。
针对上述问题，本文对数据网格中具有副本更新代价约束的动态副本分布问题、提供副本高效存取的分布式副本定位及一致性更新等问题进行深入了研究，主要创新成果包括：1.提出基于节点“Heavy-tailed”分布特性的按簇复制策略
目前的分布式系统中的动态副本分布算法往往是单个节点根据自身的副本访问模式进行自主的复制，并不考虑节点所处的位置及相互间副本传输速度，这样可能造成两个距离很近的节点各维护一份相同副本的情况发生，导致不必要的副本创建并由此产生额外的副本分布和维护代价，造成副本分布效率降低的直接后果。
为解决这一问题，我们基于数据网格节点的“Heavy-tailed”分布特性，提出了一种基于簇覆盖的动态副本分布算法“ACB-R”。首先，该算法提出了基于节点“Heavy-tailed”分布特性的簇划分规则，并基于该簇划分规则实现了一个增量的簇维护过程，能够适应变化的节点间拓扑结构，为算法中实现的按簇复制过程提供实时的簇划分服务。其次，该算法提出了一种类“Hot-spot”算法的“按簇复制”策略，以“簇”为单位指导副本的动态分布过程，实现了比“Hot-spot”算法更低的计算复杂度和更高的副本分布效率。由于ACB-R采用了按簇复制技术，在保证副本存取速度损失不大(簇内访问延迟)的前提下，该算法对减少副本数量和降低副本一致更新代价效果显著。
2.提出基于QoS隐式簇覆盖的动态副本分布算法
副本的动态分布是以提高数据网格应用的性能为目标的。一个数据网格应用可能包含多次副本访问请求，每次副本访问请求所需的副本访问服务质量(QoS)是不同的。而目前的一些分布式系统中的动态复制研究没有考虑到上述QoS约束的情形，仍以最大化每次副本访问请求的副本访问速度为目标代价函数指导数据复制及分布，导致系统需要维护的副本数量远远大于考虑QoS约束的复制所需的副本数量，而副本数量增多会导致副本占用空间、副本分布和副本一致性维护代价的增大，造成数据网格尤其是有副本写或更新需求的数据网格的副本分布性能的降低。
为消除无QoS约束进行数据复制产生的上述问题，我们基于副本大小、节点间带宽、节点间路由距离、副本访问QoS需求之间关联关系的研究，提出一种数据网格上的基于QoS隐式簇覆盖的动态副本分布算法“QCMR-DG”。该算法提出一种隐式QoS簇覆盖规则，并用其指导副本在数据网格节点中的动态分布，能够针对不同的网格应用产生的不同副本访问QoS需求，产生适应性的副本分布模式，在有效控制副本数量的同时，为数据网格应用提供满意的副本访问性能。该算法克服了上述无QoS考虑的动态副本分布盲目追求副本访问速度最大化所造成的高复制低性能的弊端，使得副本创建趋于理性化，减少了多余副本的创建，减少了副本分布和维护代价。
3.提出了一种数据网格上的缓冲索引架构“IFOG”，实现了最近副本的快速定位算法和高效的副本一致性更新策略
数据网格中的副本定位需要位置独立的逻辑名字空间。目前一些好的分布式副本定位研究能够在“对数级”消息路由之内根据数据对象的逻辑名(LFN)定位副本的存储位置(PFN)。但这些副本定位技术通常不考虑定位得到的副本实际存储位置，只保证找到的副本在逻辑覆盖上距请求者最近，这样的副本定位可能会将数据访问请求定位到一个实际存储位置较远的副本。
为克服上面出现的问题，我们提出了一种缓冲索引架构“IFOG”，该架构能够做到：既保留位置独立的逻辑名字空间，又能够从多个副本存储位置中迅速定位一个实际存储位置最近的副本。副本定位速度在最好情况下为O(1)，最差情况下是O(log(n))，其中n是网格节点总数。对“缓冲副本”的更新，我们提出一种“随访问”更新算法，实现了缓冲副本的松一致性维护。同时，我们提出一种基于“更新分发树”的即时副本更新算法，利用存储转发技术分布式地遍历被更新数据对象的所有副本节点，在更新缓冲副本的同时更新根副本，提高副本更新在数据网格节点中的传播速度。