随着互联网的不断发展, 数据呈现爆炸式的增长.IDC研究报告指出:到2020年, 全球数据量将达到40ZB^[1].对象存储系统由于具有块存储系统、文件存储系统无可比拟的可扩展性、数据可靠性和可管理性等特性, 已成为当前主流存储架构^{[2, 3]}.在对象存储系统中, 数据以对象的形式存储到对象存储设备(object-based storage device, 简称OSD), 对象是读写的基本单位.国内外大量的公司和科研机构, 如微软、IBM、谷歌、Oracle、清华大学、中国科学院、华中科技大学, 都针对对象存储系统展开了广泛而深入的研究, 并且推出了各具特色的存储系统, 如Oracle的Ceph对象存储系统^[4]、Facbook的Cassandra存储系统^[5]、微软的Azure存储系统^[6]和中国科学院的蓝鲸分布式对象系统^[7].

对象存储系统面临着海量对象的管理问题, 即对象分布算法如何有效地将对象分布到大量的OSD中存储.对象和节点间的映射关系可以抽象为经典装箱问题, 装箱问题存在于云计算的存储资源和计算资源的管理^[8]等方面.与GFS等采用中心化的master节点管理数据存储位置的方式不同, 目前, 研究人员大都采用基于hash的算法分布对象到OSD节点, 保证所有对象映射到存储节点的随机性和存储系统的可扩放性.Karger等人在1997年提出的一致性hash算法最初用来解决分布式Web服务的缓存问题, 随后应用到存储系统中.该算法将所有对象和节点映射到0~(2³²)-1空间, 对象存储在其顺时针方向最近的节点上, 可以使对象大致均匀分布, 计算复杂度为O(logn)^[9].但是节点失效后, 仅将对象迁移到相邻节点, 增加相邻节点负载, 且只适用于同构存储系统.其变种算法根据每个节点的权值设置其虚拟节点个数, 支持异构系统, 但是空间复杂度较高.Sage等人基于RUSH算法提出了CRUSH算法, 该算法已应用于Ceph分布式存储系统, 用户能够自定义不同的数据放置规则满足数据可靠性、性能的要求^[10].但是该算法节点变化后最多迁移理论值的h倍使对象再平衡, 其计算时间复杂度是CRUSH Map每一层时间复杂度之和.Lamping等人从降低对象分布的时间复杂度考虑, 提出了跳跃hash算法^[11].该算法可以从理论证明对象均匀分布, 时间复杂度为O(logn), 但是只支持同构系统, 不具有多副本策略.谢伟等人针对异构存储系统提出了双模对象分布算法^[12].此算法可以使存储系统表现出性能型和容量型模式, 最大计算时间为一致性hash算法的两倍.Miranda等人提出了基于动态区间的对象分布算法.该算法将对象映射到(0, 1) 区间, 并将区间划分为多个子区间, 每个节点拥有和其权值成正比的多个子区间, 以此为依据进行数据映射, 但是真实的存储系统节点频繁失效, 将会使区间维护变得非常复杂^[13].Alon等人提出了适用于社交网络的social hash算法, 通用性较差^[14].陈涛等人提出了EFAH hashing算法^[15], 可以在集群间和集群内分布对象, 但是需要维护区间分配表, 应用于真实的存储系统难度较大.

目前, 存储系统仍然需要多方面优化, 如降低节点间网络开销^[16]等, 其中, 对象分布算法可以在以下两个方面进行改进.

(1) 天气预测、地震预测、电子商务等大数据应用要求存储系统具有高吞吐、低延迟等特性.对象分布算法很大程度影响了存储系统的聚合带宽和处理时间, 因此, 较快的对象分布算法能够提高存储系统性能.当前的对象分布算法主要着重于对象均匀分布、自定义放置策略等方面.面对大数据应用对存储系统的低延迟、高吞吐的需求, 如何降低对象分布算法的计算时间, 已成为对象存储系统需要解决的问题.

(2) 对象存储系统中, 所有OSD节点都会运行包含对象分布算法的程序, 因此, 简单而高效的对象分布算法能够占用较低内存, 降低程序出现bug的概率.而当前的对象分布算法有些需要维护表信息, 有些处理逻辑复杂, 并不适用于真实的存储系统.

本文针对上述问题做了如下工作.

(1) 基于跳跃hash算法的思想, 提出了一种表示对象副本和节点映射关系的函数, 并证明对象映射到每个节点的概率理论上相同.基于此函数思想和动态子数组提出了跳跃查找算法.该算法根据节点的权值计算每个节点的虚拟节点数目, 对所有节点的虚拟节点依次分配序号组成数组; 同时, 每个节点也具有由其虚拟节点组成的子数组, 对象的定位、查找过程只需计算对象映射的虚拟节点序号, 然后查找此虚拟节点所对应的节点即可.

(2) 将情形(1) 中提到的跳跃查找算法和二维矩阵结合, 提出了MJHAR(matrix-based jump hash algorithm for replication data)对象分布算法.该算法初始时将所有节点映射到二维矩阵内.对象的定位查找过程主要分为两步:首先, 对象利用跳跃查找算法映射到矩阵的某一行内; 其次, 在目标行内使用跳跃查找算法映射到矩阵的某一节点.通过理论分析证明:MJHAR算法是简洁而高效的, 对象是均匀分布的, 节点变化后对象迁移量是较少的.实验结果表明, MJHAR算法的计算时间比一致性hash算法快40%, 比跳跃hash算法快23%.

本文第1节给出描述存储系统和算法相关的概念、术语.第2节介绍MJHAR算法, 并描述理论基础、对象映射过程、二维矩阵构造过程和节点变化后再平衡过程.第3节通过理论分析证明MJHAR算法具有均匀分布、迁移量较少等特点, 并对算法复杂度进行分析.第4节给出实验仿真结果和分析.第5节给出本文的结论.

1 问题定义

假定对象数目为n(n≥1), 依次编号为0, 1, 2, …, n-1.每个对象拥有唯一的识别符, 用X_i表示第i个对象的标识符.存储节点数目为m(m≥1), 依次编号为0, 1, 2, …, m-1, 并组成数组, 其中第s个存储节点的权值用w_s表示.对象数目理论上无限, 且对象数量远远大于节点数量, 也就是n≥m.对象存储系统的对象分布问题可以抽象为数学问题:构造函数G(X_i, R, m)=s, 函数G表示将对象X_i的第R个副本映射到第s个节点.

对象分布算法的优劣可以用以下4个指标来评价^[17].

● 公平性:每个节点存储的对象数目和其自身的能力(存储容量、性能和节点带宽等)成正比, 即若第s个节点存储数据对象数目为$n \times {w_s}/\sum\nolimits_{j = 0}^{m - 1} {{w_j}}, $则该算法是公平的.

● 高效性:若对于任意对象, 都可以快速计算得到其存放节点, 则该算法是高效的.

● 简洁性:若算法只需要少量信息计算存放对象的节点, 且代码实现逻辑简单, 则该算法是简洁的.

● 自适应性:存储系统为了满足容量、性能需求会加入新的存储设备, 也会替换、删除损坏的设备.此类情况都可以认为是节点的权值发生变化.节点的权值变化后, 应进行数据迁移来保证数据的可用性和节点的负载均衡.若迁移后仍是均匀分布的, 且迁移过程中尽可能地迁移较少的对象, 即对象迁移仅仅发生在权值不变的节点和权值变化的节点之间, 权值不变的节点之间不发生对象迁移, 则该算法是自适应的.

2 MJHAR算法

MJHAR算法的主要思想是:将节点映射到二维矩阵内, 从矩阵的行间和行内分别采用跳跃查找算法计算目标节点的行号和列号, 行号和列号组合就是目标节点序号.针对对象查找和对象迁移问题, MJHAR算法与其他算法不同的是, 它并不需要复杂的放置规则或者维护、更新表信息等, 其逻辑处理极其简单、高效.下面的内容分3个部分:理论基础、对象查找过程、构造二维矩阵和对象迁移过程.

2.1 理论基础

跳跃hash算法中将节点排序依次编号0, 1, 2, …, m-1, 并将所有对象哈希映射到(0, 1) 区间, 在一维数组内计算对象映射的节点序号^[10].本文借鉴跳跃hash的思想, 提出了表示对象副本与目标节点关系的数列p:{a_m}, {a_m}= a₀, a₁, a₂, …, a_m和其递推公式$H:{a_{i + 1}} = \left\lfloor {\frac{{{a_i} + 1}}{{{r_i}}}} \right\rfloor .$其中,

(1) 数列P的项表示对象X_i的第R个副本映射的节点.数列P内的相邻两项中前一项是后一项的上一跳节点, 后一项是前一项的下一跳节点.如数列P:0, 2, 5, ……, 对象X_i的第R个副本可以映射到0号、2号、5号节点.0号节点是对象X_i的第R个副本的初始存放的节点.2号节点是0号节点的下一跳节点, 并且是5号节点的上一跳节点.

(2) 递推公式H表示数列P的项, 即存储对象X_i的第R个副本的上一跳节点和下一跳节点之间满足的关系, 初始时a₀=0.

(3) 递推公式H中, r_i表示以对象X_i的第R个副本为种子产生(0, 1) 区间的随机数序列, 且产生的随机数在(0, 1) 区间内均匀分布.

如表 1所示, 举例说明存储对象X₁, X₂, X₃的副本与节点关系的数列.

因为存储系统中节点数目是有限的, 数列P引入限制条件, 即对象X_i的第R个副本的数列P最后一项a_i作为其最终存储的节点, 且满足a_i < m≤a_i+1.若m=10, 则表 1中存储对象X₁第1个副本的节点、对象X₂第3个副本和对象X₃的第2个副本的节点分别为第9号节点、第8号节点和第7号节点.以上内容可得对象X_i第R个副本与映射节点关系的跳跃查找函数G(X_i, R, m)=a_i(a_i∈P, a_i < m≤a_i+1, r_i∈hash(X_i, R)).该函数的证明过程见第3.1节.

2.2 数据定位过程

MJHAR算法支持权值和数据冗余机制.计算对象X_i的第R个副本的存储节点的伪码如图 1所示, 主要分为2步:(1) 假设矩阵M的行是具有较大权值的虚拟节点, 且本行所有节点之和$\sum\nolimits_{j = 0}^k {{M_{ij}}} $为矩阵M第i行的权值RW_i, 采用跳跃查找算法在矩阵M中计算对象X_i第R个副本映射的目标行; (2) 目标行内采用跳跃查找算法计算映射的节点.

MJHAR算法的目标行和行内目标节点的计算都采用跳跃查找算法, 跳跃查找算法将函数G的思想和动态子数组相结合, 首先根据节点的权值为每个节点分配相应数目的虚拟节点, 若节点的权值为5, 则该节点具有5个虚拟节点.将所有节点的虚拟节点排序分配序号并组成数组$L = 0, 1, 2, ..., \sum\nolimits_{i = 0}^{m - 1} {{w_i}}, $在数组L内, 第i个节点的虚拟节点组成的子数组${L_i} = \left[{\sum\nolimits_{j = 0}^i {{w_j}, \sum\nolimits_{j = 0}^{i + 1} {{w_j}} } } \right].$首先计算对象的副本映射的虚拟节点序号; 然后, 通过查表法确定虚拟节点所对应的节点, 其具体实现算法如图 2所示.

存储系统为了提高性能、降低程序出现bug概率, 其每一模块理论设计应该精简高效, 代码逻辑简单明了. MJHAR算法相对于其他对象分布算法具有两个方面的优势.

● 对象采用概率理论映射到节点, 此过程仅涉及计算操作和少量查表操作; 而动态区间映射算法需要不断维护每个节点拥有的区间段, 存储系统的扩容、删除节点等操作会造成节点拥有的区间段碎片化, 其维护将会变得复杂.

● 本算法可以在百行代码内实现, 逻辑清晰; 而Crush算法等需要数千行代码实现.

因此可见, MJHAR算法满足高效性和简洁性, 可以有效避免Bug的出现, 提高程序运行的可靠性.

2.3 构造二维矩阵及对象迁移过程

MJHAR算法将所有节点映射到二维矩阵M内, 采用跳跃查找算法分别计算对象的目标节点在二维矩阵的行号和列号.为了使行、列查找更加公平, 根据节点个数m构造二维加权矩阵M[h][k], 其中, $\sqrt m \le h, k \le \sqrt m + 1$.存储节点和二维加权矩阵M的映射关系为:第s个节点对应二维加权矩阵的第s/k行、第s%k列, 并且M[s/k][s%k]的值是第s个节点的权值w_s.节点数m不一定等于二维加权矩阵M的行列之积, 因此, 二维矩阵M从M[(m-1)/k][(m-1)%k+1]到M[h-1][k-1]的值设为0.以上为二维加权矩阵M[h][k]的构造过程.

存储设备的增加、删除和更换都会造成节点的权值发生变化.本算法针对此种情况简单易行.若是加入节点, 按照行遍历矩阵M, 若查找到元素值为0, 即为空余位置, 则新加入的存储节点放入空余位置.如果矩阵M已满, 则需要扩容矩阵M:为了保证矩阵M的行列满足关系$\sqrt m \le h, k \le \sqrt m + 1$, 首先判断矩阵的行、列关系, 若矩阵M行大于列, 则矩阵M新增一列; 若矩阵M列大于行, 则矩阵M新增一行.若是删除节点, 则该节点在矩阵M中相应元素的值为0.若是替换节点, 则矩阵M中相应元素的值为替换后的权值.节点的权值变化后对所有对象重新计算其目标节点, 若对象的存放节点发生变化, 则迁移其至新目标节点.

3 算法分析 3.1 公平性证明

第2.1节中描述了表示对象副本和节点映射关系的函数G, 本节证明对象X_i的第R个副本映射到节点0, 1, 2, …, m-1的概率相等.首先推导数列P的通项公式.递推公式$H:{a_{i + 1}} = \left\lfloor {\frac{{{a_i} + 1}}{{{r_i}}}} \right\rfloor $中包含向下取整运算, 且0 < r_i < 1.根据节点数目m, 可以将r_i所在的(0, 1) 区间划分为m-a_i份, 即$\left( {0, \frac{{{a_i} + 1}}{m}} \right), \left( {\frac{{{a_i} + 1}}{m}, \frac{{{a_i} + 1}}{{m - 1}}} \right), ..., \left( {\frac{{{a_i} + 1}}{{{a_i} + 2}}, \frac{{{a_i} + 1}}{{{a_i} + 1}}} \right)$, 则递推公式共有m-a_i种可能性.第j个区间对应的递推公式:

$\begin{array}{c} H:{a_{i + 1}} = m - j + 1, 2 \le j \le m - {a_i}, \\ H:{a_{i + 1}} \ge m, j = 1. \end{array}$

若对象X_i的第R个副本的数列P的最后一项是a_i=k(k < m), 则对象X_i的第R个副本最终映射到节点k的概率p(a_i=k)等于a_i-1 < k, 即上一跳节点分别是0, 1, 2, ……, k-1时, 其下一跳节点是k的概率之和与节点k下一跳节点序号大于m, 即a_i+1 > m的概率之积; 且a_i-1∈{0, 1, 2, …, k-1}时, a_i等于k的概率是p(a_i=k|a_i-1=j)·p(a_i-1=j), 0≤j≤k-1.因此, 只需递归计算a_i-1∈{0, 1, 2, …, k-1}的概率p(a_i-1).此处省略递归计算过程, 最终计算得到a_i-1∈{0, 1, 2, …, k-1}时, 下一跳节点是a_i=k的概率之和是1/(k+1).a_i+1 > m的概率等于p(a_i+1=l|a_i=k)·p(a_i=k)=a_i+1/m=(k+1)/m, l > m.可得对象X_i的第R个副本存放到节点k的概率p(a_i=k)=1/m.因此, 函数G中对象的副本映射到每个节点的概率相等.

由上文可得:跳跃查找算法中, 数组L内, 每个虚拟节点存储任意对象副本的概率是$1/\sum\nolimits_{s = 0}^{m - 1} {{w_s}} .$因此, 每个虚拟节点存储对象数目的期望值为$n \times 1/\sum\nolimits_{s = 0}^{m - 1} {{w_s}} .$因第s个节点的虚拟节点组成的子数组${L_s} = \left[{\sum\nolimits_{j = 0}^s {{w_j}, \sum\nolimits_{j = 0}^{s + 1} {{w_j}} } } \right], $所以第s个节点存放的对象数目理论值是$n \times {w_s}/\sum\nolimits_{s = 0}^{m-1} {{w_s}}, $与其权值成正比.因此, 跳跃查找算法是均匀分布的.

MJHAR算法分别从行内和行间调用跳跃查找算法.第1次以行为单位计算目标行过程中, 第i行被选中的概率是$\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} /\sum\nolimits_{i = 0}^{h - 1} {\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} } ;$第2次在目标行计算目标节点过程中, 若第i行为目标行, 矩阵M的第i行、第j列节点被选中的概率是${M_{ij}}/\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} .$由此可得, 矩阵M中, 第i行、第j列的节点被选中的概率是

$\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} /\sum\nolimits_{i = 0}^{h - 1} {\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} } \times {M_{ij}}/\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} = {M_{ij}}/\sum\nolimits_{i = 0}^{h - 1} {\sum\nolimits_{j = 0}^{k - 1} {{M_{ij}}} } .$

节点存储的对象数目与其权值成正比, 因此证明MJHAR算法是公平的.

3.2 迁移量分析

由第3.1节的证明可知:无论跳跃查找算法中节点的权值是否变化, 任意对象的副本映射到每个虚拟节点概率相等.因此, 权值变化只会影响每个节点存储对象数目的变化.而节点存储对象数目与其权值成正比的关系不会受到影响, 因此跳跃查找算法和MJHAR算法可以保证节点变化后对象仍然均匀分布.

● 节点加入、权值增加的情况

权值w_m的节点加入存储系统, 可以认为分w_m次加入权值为1的存储节点, 因此, 首先分析加入权值为1的节点数据量迁移量.第3.1节的证明中, 节点数目增加, 区间数从m-a_i个增加到m+1-a_i个, 则每个区间的范围都将减少.可以计算出:节点加入后, 当前所有节点会迁移其自身$1/\left( {\sum\nolimits_{s = 0}^{m - 1} {{w_s}} + 1} \right)$的数据对象到新节点, 则前m个节点迁移数据量之和是$n \times \sum\nolimits_{s = 0}^{m - 1} {\left( {{w_s}/\sum\nolimits_{i = 0}^{m - 1} {{w_i}} \times 1/\left( {\sum\nolimits_{i = 0}^{m - 1} {{w_i} + 1} } \right)} \right)} = n \times 1/\left( {\sum\nolimits_{s = 0}^{m - 1} {{w_s}} + 1} \right).$跳跃查找算法再平衡后, 新节点拥有对象数目为$n \times 1/\left( {\sum\nolimits_{s = 0}^{m - 1} {{w_s}} + 1} \right).$同理可证:权值为w_m的节点加入存储系统后将分配$n \times {w_m}/\sum\nolimits_{s = 0}^m {{w_s}} $个对象, 且前m个节点的数据迁移量之和是$n \times {w_m}/\sum\nolimits_{s = 0}^m {{w_s}}, $因此可以得出, 新节点分配的对象数目和其他节点迁移量之和相等.即前m个节点之间并未发生数据迁移.因此, 跳跃查找算法是数据迁移量最优的.MJHAR算法由于调用两次跳跃查找算法, 会有两次对象迁移.在第1次数据迁移中数据迁移最优, 但是第2次数据迁移会导致行内节点发生不必要的对象迁移.因此, 节点的权值增加或加入新节点, MJHAR算法对象迁移量是较优的.

● 节点删除、权值减少的情况

因为跳跃查找算法中对象X_i存放的节点和节点在数组L的位置有关, 所以存储系统的节点失效后, 对象会依次迁移到后续节点.即第s个节点失效后, 第s个节点的所有对象迁移到第s+1个节点, 第s+1个节点的所有对象依次迁移到第s+2节点, 第m-2个节点的所有对象迁移到第m-1个节点.第s个节点的权值变化后, 最大对象迁移量为$\sum\nolimits_{k = s + 1}^{m-1} {\left( {n \times {w_k}/\sum\nolimits_{i = 0}^{m-1} {{w_i}} } \right)} + n \times {\rm{\Delta }}w/\sum\nolimits_{i = 0}^{m-1} {{w_i}}, $Δw是第i个节点的权值变化前后之差.此公式表明了对象迁移量和失效节点在数组L位置的关系.失效节点越处于存储节点数组L后端, 对象迁移量越少.当失效节点是第m-1个节点时, 对象迁移量最优; 当失效节点是第1个节点时, 会造成所有对象重新分布.MJHAR算法从两个方面避免了跳跃查找算法节点失效后, 对象大量重分布的问题:首先, 第1次以行为单位的计算过程中, 因为很少或者不会出现某一行节点集体失效的情况, 所以行间不会产生对象大规模迁移; 其次, 对于矩阵M行内某一节点的失效的情况, 即使是行内首节点失效, 对象大规模迁移也仅仅会发生行内的节点, 不会导致除本行之外的节点对象发生大规模迁移.因此, 对于任意节点的权值变化, MJHAR算法能够保证较少的对象迁移量.

综上所述, 可以得出MJHAR算法是自适应的这一结论.

3.3 性能分析

第3.1节中提到:当a_i-1=0, 1, 2, …, k-1时, a_i=k的概率之和是1/(k+1), 因此对象副本的映射节点序号的期望值是1/2+1/3+…+1/m≈lnm, 跳跃查找算法中, 数组L的长度等于所有节点的子数组长度之和, 节点子数组长度为常数, 因此, 其计算复杂度为O(logm).跳跃查找算法仅仅需要存储每个节点的信息(ip地址和权值等), 其空间复杂度为O(m).

MJHAR算法的计算时间包括矩阵M的构造时间和对象的计算时间.由于矩阵M的构造过程只需1次, 随着对象定位的次数增加, 其构造时间可以被无限次的对象计算过程分摊, 因此构造时间可以忽略.主要考虑对象计算过程花费的时间.MJHAR算法调用两次跳跃查找算法.矩阵M的行、列长度为$\sqrt m $或$\sqrt m + 1$, 因此, MJHAR算法的时间复杂度为$2 \times O\left( {\log \sqrt m } \right) = O(\log m).$MJHAR算法仅仅存储节点的信息(ip地址和权值等), 其空间复杂度为O(m).这里, 虽然MJHAR算法的时间复杂度为O(logm), 但是其计算时间lnm和logm相差常量log₂e.

4 实验仿真

本文在模拟环境下比较MJHAR算法、一致性hash算法和跳跃hash算法的计算时间、对象分布均匀性和对象迁移量这3个方面.首先介绍模拟实验的环境:本实验操作系统为ubuntu 14.04 LTS系统, 采用python语言实现MJHAR分布算法.一致性hash算法和跳跃hash算法源码从python官方仓库^[18]下载所得.仿真程序首先随机生成32位字符串表示对象的标识符, 随后分别调用3种对象分布算法计算存储对象的OSD节点编号.最后统计每个OSD节点的对象数目.通过比较某个OSD节点的权值改变前后, 每个节点拥有的对象变化量来模拟节点的增加和失效后对象迁移量.以下图表数据来自于对不同节点数目组成的存储系统模拟读写30万个对象的实验结果.节点数目以30个节点为步长, 从50个节点到620个节点递增.因为跳跃hash算法不支持权值, 当前所有节点的权值设为1.

如图 3所示为MJHAR算法、跳跃hash算法和一致性hash算法的计算时间.从图中可以看出, MJHAR算法是最快的, 跳跃hash算法次之, 一致性hash算法的计算时间最长.虽然跳跃hash算法、MJHAR算法和一致性hash算法时间复杂度都为O(logn), 但是MJHAR算法和跳跃hash算法其迭代次数期望值为lnn, 其计算时间和一致性hash算法有常数log₂e的差别, 因此, MJHAR算法和跳跃hash算法快于一致性hash算法.MJHAR算法调用两次跳跃查找算法, 且每一次的迭代次数期望值都小于$\ln \sqrt n $, 则两次之和更小于lnn, 所以MJHAR算法比跳跃hash算法计算得更快.

图 4是3种算法的均匀性比较.横坐标表示节点数目, 纵坐标表示存储系统中节点存储对象数目的标准方差.从图中可以看到, MJHAR算法和跳跃hash算法的方差比一致性hash算法的方差小.即这两种算法对象分布得更加均匀, 有效地保证了存储节点的负载均衡.因为MJHAR算法和跳跃hash算法中每个节点分配的对象数目与其权值成正比, 而一致性hash算法只是将节点、对象随机分布到0~(2³²)-1空间, 对象存储到顺时针最近的节点, 当节点和对象较多时, 可以保证数据对象大致均匀分布, 因此, MJHAR算法和跳跃hash算法的对象分布更加均匀.

本文模拟比较了3种算法节点的权值变化后的对象迁移量.第3.2节提及MJHAR算法对象迁移量与节点位置有关.为了不失一般性, 本文模拟比较了中间节点变化后, 3种算法的对象迁移量.图 5~图 8展示了50个节点、320个节点组成的存储系统中节点增加、删除后的对象迁移量.图 5、图 6是模拟50个和320个节点组成的存储系统, 其第25号、第160号节点失效后每个节点的对象迁移量.从图中可以看出, 一致性hash算法对象迁移量较少, 跳跃hash算法和MJHAR算法的前一半节点对象迁移量也较少, 但是后一半节点对象迁移量较大.且跳跃hash算法后一半节点的对象迁移量是MJHAR算法的4倍左右.

如图 7、图 8所示是模拟50个和320个节点组成的存储系统, 第25号、第160号位置增加节点后每个节点的对象迁移量.从图中同样可以看出, 一致性hash算法对象迁移量较少, 跳跃hash算法和MJHAR算法的前一半节点对象迁移量也较少, 但是后一半节点对象迁移量较大.且跳跃hash算法的后一半节点对象迁移量是MJHAR算法的对象迁移量5倍左右.

从图 5~图 8中可以看出, 在节点增加、删除的情况下, 一致性hash算法对象迁移量最少, 但是每个节点的对象迁移量是非均匀的.跳跃hash算法和MJHAR算法对象迁移量较大, 节点对象迁移量是相对均匀的, 并且MJHAR算法对象迁移量比跳跃hash算法数据迁移量更少.

但值得注意的是, 一致性hash算法是在节点删除后将其拥有的对象迁移到相邻节点或节点增加后从相邻节点迁移对象到新加入节点, 因此节点的变化仅仅影响到相邻节点, 也就是加大了或者减轻了相邻节点的负载; 而MJHAR算法和跳跃hash算法是将删除节点的对象迁移到所有剩余节点或者从所有节点迁移对象到新加入节点, 保证再平衡后对象均匀分布, 因此系统不会出现负载不均的现象.

MJHAR算法一方面相对于跳跃hash算法, 其对象迁移量降低了数倍; 另一方面, 相对于一致性hash算法的对象迁移量还是较大.这是因为MJHAR算法行间对象迁移量较小, 但是权值变化的节点, 其所在行内的对象迁移量还是较大.我们将在后续研究中降低行内对象迁移量.

5 结论

大数据时代下, 对象分布算法对对象存储系统的性能影响更加显著.目前, 大部分对象分布算法计算时间较长, 实现逻辑复杂, 很难适用于存储系统.

本文提出了一种高效而简洁的对象分布算法MJHAR.与其他对象分布算法将节点映射在一维数组的方式不同, 该算法创造性地将节点映射到二维矩阵内, 对象的分布、定位只需从矩阵的行内、行间计算目标节点的行号和列号即可, 降低了对象分布时间.该算法支持权值和数据冗余策略, 同时具有公平性、简洁性、自适应性的特点.

实验结果表明:

● MJHAR算法在实际计算时间上, 相对于跳跃hash算法和一致性hash算法分别下降了23%和40%.

● MJHAR算法相对于一致性hash算法分布更加均匀, 更加接近理论最优值.

● 相对于跳跃hash算法, 节点变化后, MJHAR算法对象迁移量较少.

因此, MJHAR算法更加适用于异构对象存储系统.