Building a Consistent Hashing Ring Part1-Part2(构建一个一致性哈希环 Part1-Part2)
本篇是Building a Consistent Hashing Ring的翻译，原文一步步描述了一个一致性哈希环的构建过程，对于OpenStack Swift存储，对应的Ring文件，其实就是一个一致性哈希环。
这篇文章讲述了OpenStack Swift Ring文件的构建原理。目前翻译了第一部分和第二部分，包含了最原始的算法，并最终引入虚拟节点，减少扩容时的数据移动
Part 1
“一致性哈希”是用于描述使用散列算法分布数据以确定其位置的过程的术语。只需要知道数据id的哈系值，就可以确切地确定数据应该在哪里。哈希与位置的映射关系通常被称为“环”。
也许最简单的哈希只是id的模数。例如，如果所有数据的id都是数字，希望分散数据到两台机器上，可以将所有id为奇数的数据放在一台机器上，id为偶数的数据放在另一台。假设奇数id和偶数id的数据数量大致平衡，并且每个数据的大小也大致平衡，那么数据在两台计算机之间也是大致平衡的。
由于数据通常具有文本名称而不是数字，例如文件或URL的路径，因此实际使用中会先通过散列算法将名称转换成一个数字。例如，使用MD5，名称“mom.png”的散列是’4559a12e3e8da7c2186250c2f292e3af’，’dad.png’的散列是’096edcc4107e9e18d6a03a43b3853bea’。然后，使用模数，我们可以将“mom.jpg”放在奇数机器上，把“dad.png”放在偶数机器上。使用像MD5这样的哈希算法的另一个好处就是生成的哈希值是可以保证均匀分布的，这意味着任意名称最终将均匀分布，不用担心数据id分布的均匀性。
例子：
from hashlib import md5
from struct import unpack_from
# 100个节点，10000000个文件
NODE_COUNT = 100
DATA_ID_COUNT = 10000000
node_counts = [0] * NODE_COUNT
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
# 根据数据id计算md5，并将md5的前4个字节作为一个int
hsh = unpack_from('>I', md5(data_id).digest())[0]
# 取模，计算node_id
node_id = hsh % NODE_COUNT
# 统计节点的数据个数
node_counts[node_id] += 1
# 每个节点数据个数的期望值
desired_count = DATA_ID_COUNT / NODE_COUNT
print '%d: Desired data ids per node' % desired_count
# 数据最多的节点的数据个数
max_count = max(node_counts)
over = 100.0 * (max_count - desired_count) / desired_count
print '%d: Most data ids on one node, %.02f%% over' % (max_count, over)
# 数据最少的节点的数据个数
min_count = min(node_counts)
under = 100.0 * (desired_count - min_count) / desired_count
print '%d: Least data ids on one node, %.02f%% under' % (min_count, under)执行结果：
100000: Desired data ids per node
100695: Most data ids on one node, 0.69% over
99073: Least data ids on one node, 0.93% under结果很不错，对于单个节点，分配的数据差距小于1%。
Part 2
在本系列的第1部分中，我们使用哈希的模数来定位数据进行了简单地测试。可以看到数据分布地很好，但这只是故事的一部分。分布式系统不仅需要分配负载，而且随着数据量的增长，它们也经常需要扩容。
所以让我们想象一下，我们使用我们以前的算法来运行一个100节点的系统，但是它的资源逐渐被耗尽，所以我们要添加另一个节点。当我们将第101个节点添加到我们的系统中时，会注意到许多id将映射到与之前不同的节点。我们将不得不在我们的系统上清理一大堆数据，以便将其全部重新安置到位。
我们在一个最小规模的系统中举个简单的例子：开始只有2个节点，节点0存储偶数id的数据，节点1存储奇数id的数据。因此，数据id为100的将映射到节点0，数据id为101的将映射到节点1，数据id为102的将映射到节点0，依次类推，很简单的，node = id ％ 2。现在我们添加第三个节点（节点2）以获得更多的空间，所以我们想要node = id ％ 3。所以现在数据id为100的将映射到节点1，数据id为101的将映射到节点2，数据id为102的将映射到节点0。所以我们必须移动3个数据中的其中2个，使他们都存在正确的位置。
举个更大规模的例子：
from hashlib import md5
from struct import unpack_from
NODE_COUNT = 100
NEW_NODE_COUNT = 101
DATA_ID_COUNT = 10000000
# 用于统计移动的数据个数
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
node_id = hsh % NODE_COUNT
new_node_id = hsh % NEW_NODE_COUNT
# 很显然，当新旧节点id不同时，需要移动该数据
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)执行结果：
9900989 ids moved, 99.01%结果很严峻，为了提升1%的容量，我们需要移动差不多99%的数据！因此，必须使用一个新的算法，来避免这种情况。
所以在这里我们需要引入“环”的概念，我们可以将一定哈希值范围的数据直接分配给每个节点，然后通过一定的算法减少这些范围的变化。
还是看一个小规模例子，数据id从0到999，两个节点，将0到499的数据分配给节点0，500到999的数据分配给节点1，当新加了节点2时，节点2的数据各有一半来自于节点0和1，这样最小化需要移动的数据量。
大规模的例子：
from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
NODE_COUNT = 100
NEW_NODE_COUNT = 101
DATA_ID_COUNT = 10000000
# 原来每个节点的哈希值区间
node_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_starts.append(DATA_ID_COUNT /
NEW_NODE_COUNT * new_node_id)
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
# 获取原来的节点id
node_id = bisect_left(node_range_starts,
hsh % DATA_ID_COUNT) % NODE_COUNT
# 获取新的节点id
new_node_id = bisect_left(new_node_range_starts,
hsh % DATA_ID_COUNT) % NEW_NODE_COUNT
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)执行结果：
4901707 ids moved, 49.02%结果好了不少，但是在总容量增加1%的情况下，移动50%的数据仍然不容乐观。如果我们仔细研究一下发生了什么，就会明白其实这就是“手风琴效应”，当我们将节点0的范围缩小一点，以赋予新节点，但是将所有其他节点的范围也跟着移位了相同的量。
为了最小化对节点分配范围的更改，可以给节点分配几个较小的区间而不是单个很大的区间。 这可以通过为每个节点创建“虚拟节点”来实现。 所以100个节点可能有1000个虚拟节点。 来看看是如何实现的：
from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
NODE_COUNT = 100
DATA_ID_COUNT = 10000000
VNODE_COUNT = 1000
vnode_range_starts = []
vnode2node = []
# 初始化两个表，vnode_range_starts是每个vnode对应的哈希区间，
# vnode2node是每个vnode实际对应的node_id，
# 这里vnode和node之间对应关系是取vnode_id % NODE_COUNT
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(vnode2node)
new_node_id = NODE_COUNT
NEW_NODE_COUNT = NODE_COUNT + 1
# 计算需要修改指向的vnode数量
vnodes_to_reassign = VNODE_COUNT / NEW_NODE_COUNT
while 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_vnode2node[vnode_id] = new_node_id
vnodes_to_reassign -= 1
break
if vnodes_to_reassign <= 0:
break
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
vnode_id = bisect_left(vnode_range_starts,
hsh % DATA_ID_COUNT) % VNODE_COUNT
node_id = vnode2node[vnode_id]
new_node_id = new_vnode2node[vnode_id]
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)执行结果:
90423 ids moved, 0.90%这就对了，在添加1%容量的情况下，只需要移动0.9%的数据。上面的代码，看起来vnode_range_starts有点多余了，因为在整个生命周期中只被计算了一次，而且从来没变过，所以可以优化一下：
from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
NODE_COUNT = 100
DATA_ID_COUNT = 10000000
VNODE_COUNT = 1000
vnode2node = []
for vnode_id in xrange(VNODE_COUNT):
vnode2node.append(vnode_id % NODE_COUNT)
new_vnode2node = list(vnode2node)
new_node_id = NODE_COUNT
vnodes_to_reassign = VNODE_COUNT / (NODE_COUNT + 1)
while vnodes_to_reassign > 0:
for node_to_take_from in xrange(NODE_COUNT):
for vnode_id, node_id in enumerate(vnode2node):
if node_id == node_to_take_from:
vnode2node[vnode_id] = new_node_id
vnodes_to_reassign -= 1
break
if vnodes_to_reassign <= 0:
break
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
data_id = str(data_id)
hsh = unpack_from('>I', md5(str(data_id)).digest())[0]
vnode_id = hsh % VNODE_COUNT
node_id = vnode2node[vnode_id]
new_node_id = new_vnode2node[vnode_id]
if node_id != new_node_id:
moved_ids += 1
percent_moved = 100.0 * moved_ids / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_ids, percent_moved)结果：
89841 ids moved, 0.90%很好，在下面的系列中，会继续说明算法的局限性，并相应的进行优化。