consistent_hashing_cpp

复习算法的过程中看到了对一致性哈希的讲解，发现GitHub上很多代码实现的功能都不全（比如新增节点、删除节点时没考虑数据的迁移），于是自己代码实现了一下，总体思路参考左程云的书。使用了虚拟节点，并且在新增实际节点或者删除实际节点时，会对数据进行迁移。整个思路理解起来其实不难，但在自己实现的时候发现要考虑的细节还挺多的，很多是之前看书时没有想过的。

一致性哈希原理

映射空间可抽象为一个环，长度为2^32，范围为[0, 2^32-1]，每个服务器节点根据自己的哈希值被映射到这个环上；
判断一条数据属于哪个服务器节点的方法：根据数据的哈希值，去哈希环找到第一个大于等于数据哈希值的机器（可以理解为离它最近）。如果数据的哈希值大于当前最大的机器哈希值，那么就把这个数据放在位置最靠前（哈希值最小）的机器上，因为是一个环；
为了解决实际机器过少导致的数据倾斜问题（例如目前一共3个机器，机器A、B的哈希值分别为1和2，而另一个机器C的哈希值为 2^32-1，那么大部分的数据都会被分给机器C），引入了虚拟节点概念，虚拟节点相当于真实节点的分身，一个真实节点可以有很多个虚拟节点，当数据被分配给这些虚拟节点时，本质上是分给这个真实节点的。由于数量变多了，数据分布的均衡性会有所提高；
新增节点时：例如原本的节点哈希值列表为[1,100,500,1000]，新增节点800后，在501~799范围内的数据原本是分给哈希值为1000的节点的，现在要把这部分数据迁移到节点800；
删除节点：例如原本的节点哈希值列表为[1,100,500,800，1000]，删除节点500后，原本范围是101~500的数据要迁移到节点800.

代码实现过程的一些思考

理解原理其实不难，但实现的时候需要考虑的东西就有很多了，比如要怎么处理虚拟节点和实际节点的对应关系、新增或者删除节点后的数据要怎么处理。

下面直接说数据存放在某个虚拟节点，其实是存在这个虚拟节点对应的实际节点上的，为了描述方便才这样说的。虚拟节点本身其实并不是实际存在的，只是为了让数据分布的更加均匀而设置的。

哈希值怎么得到

使用了 Murmurhash算法，它是一种非加密型哈希函数，适用于一般的哈希检索操作。高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年Appleby被Google雇佣，随后Google推出其变种的CityHash算法。代码里直接复用了MurmurHash2的实现。

unsigned int my_getMurMurHash(const void *key, int len)

如何找到第一个大于等于当前数据哈希值的节点

在哈希类中存储一个有序的虚拟节点哈希值列表this->sorted_node_hash_list，在这个列表中使用二分查找，返回值为节点在列表中的位置，从而方便在添加、删除节点时，复用这个函数然后找到当前位置后面的节点。

unsigned int consistent_hash::find_nearest_node(unsigned int hash_value)

新增一个实际节点

看了Github上一些别人实现的一致性哈希，大多都没考虑新增节点时数据的迁移问题。在新增一个实际节点后，会为它生成一些虚拟节点，每个虚拟节点有一个自己的哈希值，会对应到哈希环中的一个位置，插入新虚拟节点后可能会需要从后面位置的虚拟节点上“抢”一些数据。抢夺的数据可能与当前的虚拟节点是属于同一个实际节点的，例如：原本的虚拟节点列表为[1,100,500，1500]，在新增实际节点A时，先生成了一个虚拟节点1000，那么它会从1500节点上“抢”走范围在501 ~ 1000的数据；然后节点A又生成了一个哈希值为800的虚拟节点，那么就会从节点1000上“抢”走范围在501 ~ 800的数据。

void consistent_hash::add_real_node(string ip, unsigned int virtual_node_num)

删除一个实际节点

删除一个实际节点时，属于它的虚拟节点也要删除。如果在删除过程中，某个虚拟节点有存放数据，那么就要从当前虚拟节点的位置向后遍历，找到第一个不属于要被删除实际节点的虚拟节点。例如目前哈希值为1000、属于A实际节点的虚拟节点要被删掉了，1500节点也属于A，不能把数据迁移到这里；2000节点属于B，因此选择把1000节点上的数据迁移到2000节点。

void consistent_hash::drop_real_node(string ip)

代码运行结果

重点测试了新增节点、删除节点后数据的迁移。完整代码见https://github.com/metang326/consistent_hashing_cpp

测试步骤：

创建实际节点192.168.2.136，拥有300个虚拟节点；
插入6条数据；
打印哈希表状况，目前6条数据放置的虚拟节点都属于实际节点192.168.2.136；
新增两个实际节点，192.168.2.137和192.168.2.138，各有300个虚拟节点。在插入过程中，有部分数据会迁移到新增的虚拟节点上；
打印哈希表状况，目前6条数据放置的虚拟节点和第一次打印时有所变化；
删除实际节点192.168.2.136，属于它的数据节点如果存放了数据，则要迁移到离它最近的、后面的一个属于别的实际节点的虚拟节点；
打印哈希表状况，目前6条数据放置的虚拟节点只属于192.168.2.137或者192.168.2.138。

    consistent_hash hash = consistent_hash();
    hash.add_real_node("192.168.2.136", 300);

    hash.put("metang1996");
    hash.put("buaa");
    hash.put("hello world");
    hash.put("test add data");
    hash.put("python");
    hash.put("c++");

    cout << endl << "---------------------------------step 1---------------------------------" << endl;
    hash.print();

    cout << endl << "---------------------------------step 2---------------------------------" << endl;
    hash.add_real_node("192.168.2.137", 300);
    hash.add_real_node("192.168.2.138", 300);
    hash.print();

    cout << endl << "---------------------------------step 3---------------------------------" << endl;
    hash.drop_real_node("192.168.2.136");
    hash.print();

运行结果：

[add_real_node] 192.168.2.136
[add_real_node finished]        192.168.2.136

data:   metang1996(4222505775)  was put on virtual node:192.168.2.136:263(4235609549)
data:   buaa(3454011751)        was put on virtual node:192.168.2.136:267(3456706561)
data:   hello world(1164859173) was put on virtual node:192.168.2.136:164(1166539894)
data:   test add data(4091638786)       was put on virtual node:192.168.2.136:174(4105552776)
data:   python(2193893537)      was put on virtual node:192.168.2.136:258(2228356111)
data:   c++(3909345298) was put on virtual node:192.168.2.136:29(3930339622)

---------------------------------step 1---------------------------------

------------consistent_hash.print()------------
real_node_sum:  1       virtual_node_sum:       300

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.136      virtual_node_num=300
virtual node:   192.168.2.136:29(3930339622)    has data:(c++,3909345298)
virtual node:   192.168.2.136:164(1166539894)   has data:(hello world,1164859173)
virtual node:   192.168.2.136:174(4105552776)   has data:(test add data,4091638786)
virtual node:   192.168.2.136:258(2228356111)   has data:(python,2193893537)
virtual node:   192.168.2.136:263(4235609549)   has data:(metang1996,4222505775)
virtual node:   192.168.2.136:267(3456706561)   has data:(buaa,3454011751)


---------------------------------step 2---------------------------------
[add_real_node] 192.168.2.137
[move data]     2193893537      from node:      192.168.2.136:258(2228356111)   to      192.168.2.137:1(2212322557)
[move data]     3909345298      from node:      192.168.2.136:29(3930339622)    to      192.168.2.137:13(3929102228)
[move data]     2193893537      from node:      192.168.2.137:1(2212322557)     to      192.168.2.137:55(2202566453)
[move data]     3909345298      from node:      192.168.2.137:13(3929102228)    to      192.168.2.137:127(3918333119)
[move data]     3454011751      from node:      192.168.2.136:267(3456706561)   to      192.168.2.137:172(3455963154)
[add_real_node finished]        192.168.2.137

[add_real_node] 192.168.2.138
[move data]     2193893537      from node:      192.168.2.137:55(2202566453)    to      192.168.2.138:2(2195513987)
[move data]     1164859173      from node:      192.168.2.136:164(1166539894)   to      192.168.2.138:25(1166108575)
[move data]     4222505775      from node:      192.168.2.136:263(4235609549)   to      192.168.2.138:166(4227248974)
[add_real_node finished]        192.168.2.138


------------consistent_hash.print()------------
real_node_sum:  3       virtual_node_sum:       900

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.136      virtual_node_num=300
virtual node:   192.168.2.136:174(4105552776)   has data:(test add data,4091638786)

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.137      virtual_node_num=300
virtual node:   192.168.2.137:127(3918333119)   has data:(c++,3909345298)
virtual node:   192.168.2.137:172(3455963154)   has data:(buaa,3454011751)

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.138      virtual_node_num=300
virtual node:   192.168.2.138:2(2195513987)     has data:(python,2193893537)
virtual node:   192.168.2.138:25(1166108575)    has data:(hello world,1164859173)
virtual node:   192.168.2.138:166(4227248974)   has data:(metang1996,4222505775)


---------------------------------step 3---------------------------------
[drop_real_node]        192.168.2.136
[move data]     test add data   from node:      192.168.2.136:174(4105552776)   to      192.168.2.138:181(4105865009)
[drop_real_node finished]       192.168.2.136


------------consistent_hash.print()------------
real_node_sum:  2       virtual_node_sum:       600

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.137      virtual_node_num=300
virtual node:   192.168.2.137:127(3918333119)   has data:(c++,3909345298)
virtual node:   192.168.2.137:172(3455963154)   has data:(buaa,3454011751)

------------consistent_hash.print_real_node------------
real_node ip:192.168.2.138      virtual_node_num=300
virtual node:   192.168.2.138:2(2195513987)     has data:(python,2193893537)
virtual node:   192.168.2.138:25(1166108575)    has data:(hello world,1164859173)
virtual node:   192.168.2.138:166(4227248974)   has data:(metang1996,4222505775)
virtual node:   192.168.2.138:181(4105865009)   has data:(test add data,4091638786)

runtest007 / consistent_hashing_cpp Goto Github PK