一致性哈希
4.80/5 (29投票s)
一致性哈希的介绍和 C 语言库的源代码。
什么是 libconhash
libconhash 是一个一致性哈希库，可以在 Windows 和 Linux 平台上编译，具有以下特点：
- 高性能且易于使用，libconhash 使用红黑树来管理所有节点以实现高性能。
- 默认情况下，它使用 MD5 算法，但也支持用户自定义哈希函数。
- 易于根据节点的处理能力进行扩展。
一致性哈希
为什么你需要一致性哈希
现在我们来考虑一种常见的负载均衡方法。 选择缓存对象 o 的机器编号将是
hash(o) mod n
这里，n 是缓存机器的总数。 虽然这种方法效果很好，直到你添加或删除缓存机器
- 当你添加一台缓存机器时，对象 o 将被缓存在机器上
- 当你删除一台缓存机器时，对象 o 将被缓存在机器上
hash(o) mod (n-1)
hash(o) mod (n+1)
所以你可以看到几乎所有对象都将被哈希到一个新的位置。 这将是一场灾难，因为原始内容服务器被来自缓存机器的请求淹没。 这就是你为什么需要一致性哈希的原因。
一致性哈希可以保证，当缓存机器被删除时，只有缓存在其中的对象才会被重新哈希；当添加新的缓存机器时，只有少数对象会被重新哈希。
现在我们将逐步深入探讨一致性哈希。
哈希空间
通常，哈希函数会将一个 value 映射到一个 32 位 key，0~2^32-1。 现在想象将这个范围映射到一个圆圈，那么 key 将被包裹，并且 0 将跟随 2^32-1，如图 1 所示。
将对象映射到哈希空间
现在考虑四个对象：object1~object4。 我们使用一个哈希函数来获取它们的值并将它们映射到圆圈中，如图 2 所示。
hash(object1) = key1;
.....
hash(object4) = key4;
将缓存映射到哈希空间
一致性哈希的基本思想是使用相同的哈希函数将缓存和对象映射到相同的哈希空间。
现在考虑我们有三个缓存 A、B 和 C，然后映射结果将如图 3 所示。
hash(cache A) = key A;
....
hash(cache C) = key C;
将对象映射到缓存
现在所有的缓存和对象都哈希到同一个空间，因此我们可以确定如何将对象映射到缓存。 以对象 obj 为例，只需从 obj 所在的位置开始，沿着环顺时针方向前进，直到找到服务器。 如果该服务器宕机，则转到下一个服务器，依此类推。 参见上面的图 3。
根据该方法，object1 将被缓存在缓存 A 中； object2 和 object3 将被缓存在缓存 C 中，object4 将被缓存在缓存 B 中。
添加或删除缓存
现在考虑两种情况，一个缓存宕机并被删除； 并且添加了一个新的缓存。
如果缓存 B 被删除，则只有缓存在 B 中的对象才会被重新哈希并移动到 C； 在示例中，请参阅图 4 中 object4 的说明。
如果添加了新的缓存 D，并且 D 在环中 object2 和 object3 之间进行了哈希，则只有介于 D 和 B 之间的对象才会被重新哈希； 在示例中，请参阅图 5 中 object2 的说明。
虚拟节点
如果你没有部署足够的缓存，则有可能在缓存之间出现非常不均匀的对象分布。 解决方案是引入“虚拟节点”的概念。
虚拟节点是圆圈中缓存点的副本，每个真实的缓存对应于圆圈中的几个虚拟节点； 每当我们添加一个缓存时，实际上，我们在圆圈中为其创建了多个虚拟节点； 并且当一个缓存被删除时，我们从圆圈中删除其所有虚拟节点。
考虑上面的例子。 系统中有两个缓存 A 和 C，现在我们引入虚拟节点，副本为 2，那么将有 4 个虚拟节点。 缓存 A1 和缓存 A2 代表缓存 A； 缓存 C1 和缓存 C2 代表缓存 C，如图 6 所示。
然后，从对象到虚拟节点的映射将是
objec1->cache A2; objec2->cache A1; objec3->cache C1; objec4->cache C2
当你获得虚拟节点时，你会获得缓存，如上图所示。
因此，object1 和 object2 被缓存在缓存 A 中，而 object3 和 object4 被缓存在缓存中。 结果现在更加平衡。
所以现在你知道什么是一致性哈希了。
使用代码
libconhash 的接口
/* initialize conhash library
* @pfhash : hash function, NULL to use default MD5 method
* return a conhash_s instance
*/
CONHASH_API struct conhash_s* conhash_init(conhash_cb_hashfunc pfhash);
/* finalize lib */
CONHASH_API void conhash_fini(struct conhash_s *conhash);
/* set node */
CONHASH_API void conhash_set_node(struct node_s *node,
const char *iden, u_int replica);
/*
* add a new node
* @node: the node to add
*/
CONHASH_API int conhash_add_node(struct conhash_s *conhash,
struct node_s *node);
/* remove a node */
CONHASH_API int conhash_del_node(struct conhash_s *conhash,
struct node_s *node);
...
/*
* lookup a server which object belongs to
* @object: the input string which indicates an object
* return the server_s structure, do not modify the value,
* or it will cause a disaster
*/
CONHASH_API const struct node_s*
conhash_lookup(const struct conhash_s *conhash,
const char *object);
Libconhash 很容易使用。 项目中有一个示例，演示了如何使用该库。
首先，创建一个 conhash 实例。 然后，你可以添加或删除该实例的节点，并查找对象。
更新节点的副本功能尚未实现。
/* init conhash instance */
struct conhash_s *conhash = conhash_init(NULL);
if(conhash)
{
/* set nodes */
conhash_set_node(&g_nodes[0], "titanic", 32);
/* ... */
/* add nodes */
conhash_add_node(conhash, &g_nodes[0]);
/* ... */
printf("virtual nodes number %d\n", conhash_get_vnodes_num(conhash));
printf("the hashing results--------------------------------------:\n");
/* lookup object */
node = conhash_lookup(conhash, "James.km");
if(node) printf("[%16s] is in node: [%16s]\n", str, node->iden);
}