一致性哈希（Consistent Hashing）算法的C++实现

野性酷女 2021-12-10 21:21 268阅读 0赞

一致性哈希算法在缓存系统中得到广泛应用，主要解决了下面两个问题：

1、增加或移除缓存服务器时，尽量少的key-value映射失效；

2、哈希后的结果尽可能平衡的分布到各个缓存服务器。

解决这两个问题的思路：

1、不简单的采用取模运算，而是把服务对象和缓存服务器均映射到环形哈希空间，在这个环形空间中，沿顺时针方向从对象的哈希值出发，直到遇见一个cache，那么就将该对象存储在这个cache上，这样增加或减少缓存服务器时只有少部分k-v映射失效；

2、一个缓存服务器对应哈希环上的多个虚拟节点，具体数目根据其处理能力决定。

Code-Project上这个项目（[http://www.codeproject.com/Articles/56138/Consistent-hashing][http_www.codeproject.com_Articles_56138_Consistent-hashing]）是一致性哈希的开源实现，对其做了简单测试。

有10000个用户访问某网站，网站利用4台缓存服务器，其中两台服务器的处理能力是另两台的2倍。

随机生成IP地址:

1 void getIP(char * IP)
     2 {
     3     int a=0, b=0 , c=0 , d=0;
     4     a = rand()%256;
     5     b = rand()%256;
     6     c = rand()%256;
     7     d = rand()%256;
     8     char aa[4],bb[4],cc[4],dd[4];
     9     sprintf(aa, "%d", a);
    10     sprintf(bb, "%d", b);
    11     sprintf(cc, "%d", c);
    12     sprintf(dd, "%d", d);
    13     strcpy(IP,aa);
    14     strcat(IP,".");
    15     strcat(IP,bb);
    16     strcat(IP,".");
    17     strcat(IP,cc);
    18     strcat(IP,".");
    19     strcat(IP,dd);
    20 }

为2台处理能力强的服务器生成100个虚拟节点，另两台50个：

1 struct node_s g_nodes[4];
     2 
     3 int main()
     4 {
     5     int i;
     6     const struct node_s *node;
     7     char ip[128];
     8 
     9     /* init conhash instance */
    10     struct conhash_s *conhash = conhash_init(NULL);
    11     if(conhash)
    12     {
    13         /* set nodes */
    14         conhash_set_node(&g_nodes[0], "202.104.236.0", 50);
    15         conhash_set_node(&g_nodes[1], "202.104.236.1", 50);
    16         conhash_set_node(&g_nodes[2], "202.104.236.2", 100);
    17         conhash_set_node(&g_nodes[3], "202.104.236.3", 100);
    18 
    19         /* add nodes */
    20         conhash_add_node(conhash, &g_nodes[0]);
    21         conhash_add_node(conhash, &g_nodes[1]);
    22         conhash_add_node(conhash, &g_nodes[2]);
    23         conhash_add_node(conhash, &g_nodes[3]);
    24 
    25         printf("virtual nodes number %d\n", conhash_get_vnodes_num(conhash));
    26         printf("the hashing results--------------------------------------:\n");
    27 
    28         /* try object */
    29         srand(time(NULL));
    30         for(i = 0; i < 10000; i++)
    31         {
    32             getIP(ip);
    33             node = conhash_lookup(conhash, ip);
    34             //if(node) printf("[%16s] is in server: [%16s]\n", str, node->iden);
    35         }
    36 
    37         for(i = 0; i < 4; i++)
    38             printf("%3d clients in server %s\n", g_nodes[i].items, g_nodes[i].iden);
    39     }
    40     conhash_fini(conhash);
    41     return 0;
    42 }

IP地址在4台服务器上分布比较合理：

![2012110515500783.png][]

转载于:https://www.cnblogs.com/crazychris/archive/2012/11/05/2755269.html

[http_www.codeproject.com_Articles_56138_Consistent-hashing]: http://www.codeproject.com/Articles/56138/Consistent-hashing
[2012110515500783.png]: /images/20211210/55132201fa8a409c97d276b472036ec6.png