******************转载请注明出处！**********

最后更新：2011年8月22日22:29:01

写在前面。

原打算只从代码角度做些swift ring的分析工作。但无意中看到了gholt的文章，收益良多，便动了翻译的念头。

“翻译向来是一件费力不讨好的事情。”这是郑烨在某本书序言中的如是说。自己曾零散的翻译过一些，深有同感，因此不打算只是原样翻译。

虽然本系列文章源自gholt，但不尽相同。

原文链接：http://tlohg.com/building-a-consistent-hashing-ring-part-1(这只是part 1,其余part请自行查找)

本系列文章的代码下载：http://code.google.com/p/swift-cn-doc/downloads/list

原文结构索引

part1:介绍普通hash的方法，引入“平衡”的度量标准

part2:线性hash存在的问题：增加一个bucket会导致hash结果剧烈变动；分区域以减少变动影响范围；进一步减少变动；去除冗余代码

part3:代码转型到swift中的类ring形式

part4:增加replica和zone的概念，并添加进类ring原型

part5:代码改进成module, 类ring原型增加weight概念

 

本系列文在gholt的基础上加上了自己的理解，以飨读者。

系列文章结构索引

part1:普通hash及其问题，对应原文part1&part2

part2:swift实际中的情况介绍和部分特性的引入，提出问题。相应问题的解决，并附“ring已废弃方案”。对应原文part3&part4。

part3:对应原文part5。引入weight属性，并封装成module。

part4:对swift中的几个文件(ringdata.py;ringbuilder.py的简单分析)

0 准备工作

为了便于之后python代码的说明，这里需要做一些准备工作。

0.1 /和%的关系

一个除法求商(/),一个除法求余(%)，有什么区别？

其实没什么区别。只是映射的关系不一样。如图1.1所示

总结如下：

M%N：把max(M)个区映射到N个区，每个区至少有个元素

M/N：把max(M)个区映射到个区，每个区不会多于N个元素

以上的基本前提是：应保证M个区的样本数量是足够多的。

 

0.2数据分区和hash结果“抖动”的关系

这个小节名称很拗口。但确实找不到相对合适的名字...-_-!

普通hash函数会有剧烈抖动情况。如图1.2所示。

例如：hash函数为：x->x/N，N取2、3，x取值[1,10]

N由2变到3过程中，hash结果80%发生了变化(数字1、3除外)。这种抖动是需要避免的。

 

对数据分区之后，抖动情况依然存在。如图1.3所示。

例如：hash函数为：x->x/N，N取5、6、7，x取值为[1,7][11,17][21,27][31,37]

N由6->7过程中，红色和绿色标识的hash结果是不变的；

N由5->6过程中，蓝色和绿色标识的hash结果是不变的。

数据分区后，情况比图1.2好一些，但仍不理想，最好时有50%的结果发生了变化。

0.3还是一致性哈希

一致性哈希来源于[1]论文，起初是为了解决因特网中的热点(Hot spot)问题，被广泛应用于路由算法中。Dynamo中使用一致性哈希思想对数据进行分区，同时引入虚节点概念，以实现系统的增量扩展[2]。

一致性哈希很多博文都有深刻的介绍。比如[3]、[4]，这里不赘述，只介绍思路。

一致性哈希的两种思路：

1.迁移为主要特点([1]论文中的思路，swift初期采用，后废弃)

2引入虚结点，减少移动为特点(swift现采用)

 

如图2.1，为第1种思路。

每个key都映射到hash区间里某方向(例如顺时针)最近的那个bucket。当有新bucket加入时，key的映射更改到新的bucket。如图3.1中，key2原映射到Bucket C；当Bucket D加入时，key2映射到Bucket D。

 

如图2.2，为第2种思路

每个Bucket对应着若干个虚结点(图中标识的为5个)。key映射的是虚结点。当有新的Bucket加入时，需要从原有的Bucket中把虚结点分给新的Bucket，原有的key映射并不变化。如图2.2中，Bucket D加入时，原来归属于Bucket B的虚结点被分配给Bucket D。无论虚节点是否有key与其映射，改变的都是虚结点的归属，即虚结点和Bucket之间的关系。

这里需要说明的是：图2.2为了简化，在hash环空间上只标注了15个虚结点,考虑到replica，实际上只有5个真正存储用的虚结点(这个数可以定制，这里用5只是为了画图方便，实际情况下，swift中默认会有2^18个虚结点。)。且每个Bucket分到5个(5*3/3)。当Bucket D加入时，虚节点重新分配，每个(现在有4个) Bucket约分到4(5*3/4约为4)个。Bucket D只分到3个虚结点，总数为15个不变。

 

0.4二分查找bisect_left

bisect.bisect_left(list, item[,lo[, hi]])

实际上要求list是有序的，然后在[lo,hi]之间找到item应该在的位置。如果item已经存在于list中，那么插入到原位置的左边。

如果list不是有序的，也能找到位置。当然，找到的位置是没有意义的。

 

python文档中对bisect_left的解释有些让人郁闷。例子刚开始也没看明白。经指点后去找的源代码。这里贴出来，留着以后查看。

Python-2.6.7 Modules\_bisectmodule.c: line109

static Py_ssize_t
internal_bisect_left(PyObject *list, PyObject *item, Py_ssize_t lo, Py_ssize_t hi)
{
    PyObject *litem;
    Py_ssize_t mid, res;

    if (lo < 0) {
        PyErr_SetString(PyExc_ValueError, "lo must be non-negative");
        return -1;
    }
    if (hi == -1) {
        hi = PySequence_Size(list);
        if (hi < 0)
            return -1;
    }
    while (lo < hi) {
        mid = (lo + hi) / 2;
        litem = PySequence_GetItem(list, mid);
        if (litem == NULL)
            return -1;
        res = PyObject_RichCompareBool(litem, item, Py_LT);
        Py_DECREF(litem);
        if (res < 0)
            return -1;
        if (res)
            lo = mid + 1;
        else
            hi = mid;
    }
    return lo;
}

OK，准备工作做完。之后就可以开始ring的演进之旅！

构建一致性哈希ring  Part1

注意：以代码原始博客中的顺序命名。下同。

ring1.py

from hashlib import md5
from struct import unpack_from
from time import time

NODE_COUNT = 100
DATA_ID_COUNT = 10000000

begin = time()
node_counts = [0] * NODE_COUNT
for data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    hsh = unpack_from('>I', md5(data_id).digest())[0]
    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)
print '%d seconds pass...' % (time() - begin)

结果：

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
20 seconds pass...

说明：

ring1.py不用过多解释，把10^7个数hash到100个bucket中。值得注意的是，hash结果比较均匀， bucket在平均值上下1%之间。

ring2_0.py

from hashlib import md5
from struct import unpack_from
from time import time

NODE_COUNT = 100
NEW_NODE_COUNT = 101
DATA_ID_COUNT = 10000000

begin = time()
moved_ids = 0
for data_id in xrange(DATA_ID_COUNT):
    data_id = str(data_id)
    hsh = unpack_from('>I', md5(data_id).digest())[0]
    node_id = hsh % NODE_COUNT
    new_node_id = hsh % 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)
print '%d seconds pass...' % (time() - begin)

结果：

9900989 ids moved, 99.01%
21 seconds pass...

说明：

如0.2小节所述。当增加1一个Bucket时，造成hash结果剧烈抖动(99%的结果和原来不同)。这很不理想。(以下Bucket统称为node)

ring2_1.py

from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
from time import time

NODE_COUNT = 100
NEW_NODE_COUNT = 101
DATA_ID_COUNT = 10000000

begin = time()

node_range_starts = []
for node_id in xrange(DATA_ID_COUNT):#(1)
    node_range_starts.append(DATA_ID_COUNT / NODE_COUNT * node_id)
    
new_node_range_starts = []
for new_node_id in xrange(DATA_ID_COUNT): #(2)
    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]
    node_id = bisect_left(node_range_starts, hsh % DATA_ID_COUNT) % NODE_COUNT #(3)
    new_node_id = bisect_left(new_node_range_starts, hsh % DATA_ID_COUNT) % NEW_NODE_COUNT #(4)
    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)
print '%d seconds pass ... ' % (time() - begin)

结果：

4901817 ids moved, 49.02%
49 seconds pass ...

说明：

#(1)中把[1,100]的node编号扩展到[1,10^7]空间中去。即原空间步长为1，新空间步长为10^5。

#(2)中类似，是把[1,101]的node扩展到[1,10^7]空间。因此步长比#(1)的小了一点。正因为小了这么一点点(将近900)，累加效应后，直接导致后面将近50%的映射发生变化。

#(3)在node_range_starts空间中，找到hsh % DATA_ID_COUNT位置。hsh已经是打散的均匀值，取模是为了让结果均匀落在[1,10^7]空间。bisect_left函数在这里比较重要，当然也非常耗时。bisect_left忽略了具体的hsh % DATA_ID_COUNT的值，只是按照一定规格分拣出落在的node范围。比如落在[1,10^5]内的就算是node0，[10^5，2*10^5]就是node1，类推。因此前面两次hash运算失去了意义(相比改进后的ring2_3.py而言)。

#(4)和#(3)类同，不赘述。只是步长小了900左右。

50%的变化比起ring2_0.py会好一些，但仍然不能接受。

ring2_2.py

from bisect import bisect_left
from hashlib import md5
from struct import unpack_from
from time import time

NODE_COUNT = 100
DATA_ID_COUNT = 10000000
VNODE_COUNT = 1000

begin = time()
vnode_range_starts = []
vnode2node = []
for vnode_id in xrange(VNODE_COUNT):
    vnode_range_starts.append(DATA_ID_COUNT / 
                              VNODE_COUNT * vnode_id)#(1)
    vnode2node.append(vnode_id % NODE_COUNT) #(2)
new_vnode2node = list(vnode2node)
new_node_id = NODE_COUNT
NEW_NODE_COUNT = NODE_COUNT + 1
vnodes_to_reassign = VNODE_COUNT / NEW_NODE_COUNT#(3)
print 'vnodes_to_reassign is %d' % vnodes_to_reassign

while vnodes_to_reassign > 0:  #(3)
    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
                if vnodes_to_reassign <= 0:
                    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#(4)
    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)
print '%d seconds pass ...' % (time() - begin)

结果：

vnodes_to_reassign is 9
90108 ids moved, 0.90%
30 seconds pass ...

说明：

正如ring2_1.py对[1,10^7]空间分为100份。ring2_2.py引入虚结点的概念进一步细分，即分为1000份。如果这里只是类似ring2_1.py，变动区别于1000和1001，那就不用再细表了。然而不仅仅如此。

先说明一个问题。[1,10^7]空间未来会扩充到[1,2^128]（准确的上限不确定，默认是2^114）。1000个虚结点未来会扩充到2^18。这样来看，暂不提效率，依靠变化虚结点数目减少映射变动是非常有限的。

ring2_2.py中解耦了对node的依赖，即不以node数目的变动而影响映射关系。映射关系更依赖于vnode数目，但是vnode相对稳定。vnode会对应到不同的node。（参照0.3小节）

#(1) vnode_range_starts对[1,10^7]空间划分为1000份。

#(2) vnode2node是vnode和node之间的对应关系。注意这个list初始化时比较有规律，之后变更“对应”时会用到。

#(3) vnodes_to_reassign反映node变动。根据node的变动调整vnode和node的对应关系。vnode只变动有限个，这个数目才真正影响到结果中0.90%的映射变动

#(4)注意这里被查询的list为vnode_range_starts。

ring2_3.py

from struct import unpack_from
from hashlib import md5
from time import time

NODE_COUNT = 100
DATA_ID_COUNT = 10000000
VNODE_COUNT = 1000

begin = time()
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_assign = VNODE_COUNT / (NODE_COUNT + 1)
while vnodes_to_assign > 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_assign -= 1
                if vnodes_to_assign <= 0:
                    break
        if vnodes_to_assign <= 0:
            break
moved_id = 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#(1)
    node_id = vnode2node[vnode_id]
    new_node_id = new_vnode2node[vnode_id]
    if node_id != new_node_id:
        moved_id += 1
percent_moved = 100.0 * moved_id / DATA_ID_COUNT
print '%d ids moved, %.02f%%' % (moved_id, percent_moved)
print '%d seconds pass ...' % (time() - begin)

结果：

90369 ids moved, 0.90%
22 seconds pass ...

说明：

因为变为“手动”重分配vnode和node对应关系。因此不再需要像ring1.py#(3)那样使用数学的方法归类。这样节省了很多比较时间(显然二分查找还是很快的)。

#(1)需要注意这里的变动。和前几例比较后会发现会清爽很多。

 

到此，Part1已经构建好了一致性哈希ring的原型。但似乎和swift中的实际代码有些差距。不要着急。之后的Part会不断添加特性。我们会越来越接近真相。

---

[1] D. Darger, E. Lehman, T. Leighton, M.Levine, D. Lewin and R. Panigrahy. Consistent Hashing and RandomTrees:Distributed Caching Protocols for Relieving Hot Spots On the World WideWeb. ACM Symposium on Theory of Computing, 1997. 1997：654-663.

[2] G. Decandia, D. Hastorun, M. Jampani,G. Kakulapati, A. Lakshman, A. Pilchin, S. Sivasubramanian, P. Vosshall and W.Vogels. Dynamo:Amazon's Highly Available Key-Value Store.SOSP'07. 2007:205-220.

[3]http://blog.csdn.net/sparkliang/article/details/5279393  sparkliang的博客，做了深入总结

[4]http://blog.sina.com.cn/s/blog_4e6b346e0100eokj.html  一直对其中“黑帮分地盘”的例子记忆犹新