深入云存储系统Swift核心组件Ring实现原理剖析Word格式.docx

1、1. 普通Hash算法与场景分析先来看一个简单的例子假设我们手里有N台存储服务器（以下简称node），打算用于图片文件存储，为了使服务器的负载均衡，需要把对象均匀地映射到每台服务器上，通常会使用哈希算法来实现，计算步骤如下：1.计算object的hash值Key2.计算Key mod N值 有N个存储节点，将Key模N得到的余数就是该Key对应的值需要存放的节点。比如，N是2，那么值为0、1、2、3、4的Key需要分别存放在0、1、0、1和0号节点上。如果哈希算法是均匀的，数据就会被平均分配到两个节点中。如果每个数据的访问量比较平均，负载也会被平均分配到两个节点上。但是，当数据量和访问量进一步

2、增加，两个节点无法满足需求的时候，需要增加一个节点来服务客户端的请求。这时，N变成了3，映射关系变成了Key mod （N+1），因此，上述哈希值为2、3、4的数据需要重新分配（2-server 2，3 - server 0，4 - server 1）。如果数据量很大的话，那么数据量的迁移工作将会非常大。当N已经很大，从N加入一个节点变成N+1个节点的过程，会导致整个哈希环的重新分配，这个过程几乎是无法容忍的，几乎全部的数据都要重新移动一遍。 我们举例说明，假设有100个node的集群，将107项数据使用md5 hash算法分配到每个node中，Python代码如下：from hashlib

3、import md5from struct import unpack_fromNODE_COUNT = 100DATA_ID_COUNT = 10000000node_counts = 0 * NODE_COUNTfor data_id in xrange（DATA_ID_COUNT）: data_id = str（data_id） # This just pulls part of the hash out as an integer hsh = unpack_from（I, md5（data_id）.digest（）0 node_id = hsh % NODE_COUNT node_co

4、untsnode_id += 1desired_count = DATA_ID_COUNT / NODE_COUNTprint%d: Desired data ids per node % desired_countmax_count = max（node_counts）over = 100.0 * （max_count - desired_count） / desired_count Most data ids on one node, %.02f% over % （max_count, over）min_count = min（node_counts）under = 100.0 * （de

5、sired_count - min_count） / desired_count Least data ids on one node, %.02f% under （min_count, under）100000: Desired data ids per node100695: Most data ids on one node, 0.69% over99073: Least data ids on one node, 0.93% under分布结果如下所示：名称数据项数量百分比值数据项均值1000000%最多数据项节点100695+0.69%最少数据项节点99073-0.93% 从数据分布

6、上来看拥有最多/最少数据项的节点没有超出平均值的1%。现在假设增加一个节点提供负载能力，不过得重新分配数据项到新的节点上，代码如下：from struct import unpack_from NEW_NODE_COUNT = 101moved_ids = 0, md5（str（data_id）.digest（）0 new_node_id = hsh % NEW_NODE_COUNT if node_id != new_node_id: moved_ids += 1percent_moved = 100.0 * moved_ids / DATA_ID_COUNT%d ids moved, %.

7、02f% % （moved_ids, percent_moved）9900989 ids moved, 99.01%通过计算我们发现，为了提高集群1%的存储能力，我们需要移动9900989个数据项，也就是99.01%的数据项！显然，这种算法严重地影响了系统的性能和可扩展性。增加1%的存储能力=移动99%的数据？ 这种亏本生意显然做不得，那么怎么办呢？一致性哈希算法就是为了解决这个问题而来。2. 一致性哈希算法一致性哈希算法是由D. Darger、E. Lehman和T. Leighton等人于1997年在论文Consistent Hashing and Random Trees:Distrib

8、uted Caching Protocols for Relieving Hot Spots On the World Wide Web首次提出，目的主要是为了解决分布式网络中的热点问题。在其论文中，提出了一致性哈希算法并给出了衡量一个哈希算法的4个指标：平衡性（Balance）平衡性是指Hash的结果能够尽可能分布均匀，充分利用所有缓存空间。单调性（Monotonicity）单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到新的缓冲中去，而不会被映射到旧的缓冲集合中的其他缓冲区。分散性（Spread）分散性定义

9、了分布式环境中，不同终端通过Hash过程将内容映射至缓存上时，因可见缓存不同，Hash结果不一致，相同的内容被映射至不同的缓冲区。负载（Load）负载是对分散性要求的另一个纬度。既然不同的终端可以将相同的内容映射到不同的缓冲区中，那么对于一个特定的缓冲区而言，也可能被不同的用户映射为不同的内容。Swift使用该算法的主要目的是在改变集群的node数量时（增加/删除服务器），能够尽可能少地改变已存在key和node的映射关系，以满足单调性。一致性哈希一般两种思路：1.迁移为主要特点（swift初期采用）2.引入虚结点，减少移动为特点（swift现采用）具体步骤如下： 1. 首先求出每个节点（机器

10、名或者是IP地址）的哈希值，并将其分配到一个圆环区间上（这里取0-232）。 2. 求出需要存储对象的哈希值，也将其分配到这个圆环上。 3. 从对象映射到的位置开始顺时针查找，将对象保存到找到的第一个节点上。 其中这个从哈希到位置映射的圆环，我们就可以理解为何使用术语“Ring”来表示了。哈希环空间上的分布如图1所示：图1 哈希环空间假设在这个环形哈希空间中，Cache5被映射在Cache3和Cache4之间，那么受影响的将仅是沿Cache5逆时针遍历直到下一个Cache（Cache3）之间的对象（它们本来映射到Cache4上）。图2 一致性哈希算法的数据移动 现在，使用该算法在集群中增加一个

11、node，同时要保证每个节点的数据项数量均衡，代码如下所示，其中node_range_starts表示每个node的数据项的开始位置。from bisect import bisect_leftnode_range_starts = for node_id in xrange（NODE_COUNT）: node_range_starts.append（DATA_ID_COUNT / NODE_COUNT * node_id）new_node_range_starts = for new_node_id in xrange（NEW_NODE_COUNT）: new_node_range_star

12、ts.append（DATA_ID_COUNT / NEW_NODE_COUNT * new_node_id） node_id = bisect_left（node_range_starts, hsh % DATA_ID_COUNT） % NODE_COUNT new_node_id = bisect_left（new_node_range_starts, hsh % DATA_ID_COUNT） % NEW_NODE_COUNT4901707 ids moved, 49.02%结果虽然比之前好了些，但是提高1%的性能与移动50%的数据仍不理想。增加1%能力=移动50%数据？引入虚拟节点（Pa

13、rtition）考虑到哈希算法并不是保证绝对的平衡，尤其node较少的话，对象并不能被均匀的映射到 node上。为了解决这种情况，一致性哈希引入了“虚拟节点”的概念：“虚拟节点”是实际节点在环形空间的复制品，一个实际节点对应了若干个“虚拟节点”，“虚拟节点”在哈希空间中以哈希值排列。图3 虚拟节点 引入了“虚拟节点”后，映射关系就从【object-node】转换成了【object-virtual node- node】。查询object所在node的映射关系如下图所示。图4 对象、虚结点、节点间的映射关系 对100个node细分为1000个vnode，使用vnode_range_starts来

14、指定vnode的开始范围，vnode2node表示vnode到node的指派，然后增加一个node，完成vnode的重新分配，并计算所移动的数据项：VNODE_COUNT = 1000vnode_range_starts = vnode2node = for vnode_id in xrange（VNODE_COUNT）: vnode_range_starts.append（DATA_ID_COUNT / VNODE_COUNT * vnode_id） vnode2node.append（vnode_id % NODE_COUNT）new_vnode2node = list（vnode2nod

15、e）new_node_id = NODE_COUNTNEW_NODE_COUNT = NODE_COUNT + 1vnodes_to_reassign = VNODE_COUNT / NEW_NODE_COUNTwhile vnodes_to_reassign 0: for node_to_take_from in xrange（NODE_COUNT）: for vnode_id, node_id in enumerate（new_vnode2node）: if node_id = node_to_take_from: new_vnode2nodevnode_id = new_node_id

16、vnodes_to_reassign -= 1 if vnodes_to_reassign for vnode_id, node_id in enumerate（vnode2node）: vnode2nodevnode_id = new_node_id vnodes_to_assign -= 1 if vnodes_to_assign moved_id = 0 vnode_id = hsh % VNODE_COUNT#（1） moved_id += 1percent_moved = 100.0 * moved_id / DATA_ID_COUNT % （moved_id, percent_mo

17、ved）%d seconds pass . % （time（） - begin）预设合理的虚结点数 现在已构建好了一致性哈希ring的原型。但是存在一个问题，以上例子中，1000个虚结点对应着100个结点，结点变动时，虚结点就需要重新分配到结点。当100个结点扩展到1001个结点时，此时至少有一个结点分配不到虚结点，那么就需要再增加虚结点数，而虚结点是与数据项对应的哈希关系，如果改变了虚节点数，那么就需要重新分配所有的数据项，这将导致移动大量的数据。 所以在设置虚结点数的时候，需要对系统预期的规模做充分考虑，假如集群的规模不会超过6000个结点，那么可以将虚结点数设置为结点数的100倍。这样，

18、变动任意一个结点的负载仅影响1%的数据项。此时有6十万个vnode数，使用2bytes来存储结点数（065535）。基本的内存占用是6*106*2bytes=12Mb，对于服务器来说完全可以承受。 在此，引入了2个概念： 在swift中，为了区分vnode和node，将vnode称为partition。位操作代替取模操作 此外，在计算机中使用位操作来确定partition的位置比取模更快。所以，在此引入了partition power的概念。 继续改进ring的代码，设有65536个node（216），有128（27）倍个partition数（223）。由于MD5码是32位的，使用PARTITION_SHIFT（等于32- PARTITION_POWER）将数据项的MD5哈希值映射到partition的223的空间中。from array import arrayPARTITION_POWER = 23PARTITION_SHIFT = 32 - PARTITION_POWERNODE_COUNT = 65536DATA_ID_COUNT = 100000000part2node = array（H）for part in xrange（2 * PARTITION_POWER）: part2node.append（part % NODE_COUNT）for