Consistent Hashing一致性哈希库libconhash的使用与实现

发表于 更新于
闲着没事看了看一致性哈希，找了个开源库libconhash看看如何实现。整过过程非常清晰，代码也非常易懂，注释也非常全，带sample，简直就是开源库的典范！！

闲着没事看了看一致性哈希，找了个开源库libconhash看看如何实现。
整过过程非常清晰，代码也非常易懂，注释也非常全，带sample，简直就是开源库的典范！！
libconhash的sourceforge下载地址

From wikipedia

一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对K/n 个关键字重新映射，其中 K是关键字的数量，n是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。
需求:在使用n台缓存服务器时，一种常用的负载均衡方式是，对资源o的请求使用hash(o) = o mod n来映射到某一台缓存服务器。当增加或减少一台缓存服务器时这种方式可能会改变所有资源对应的hash值，也就是所有的缓存都失效了，这会使得缓存服务器大量集中地向原始内容服务器更新缓存。因些需要一致哈希算法来避免这样的问题。 一致哈希尽可能使同一个资源映射到同一台缓存服务器。这种方式要求增加一台缓存服务器时，新的服务器尽量分担存储其他所有服务器的缓存资源。减少一台缓存服务器时，其他所有服务器也可以尽量分担存储它的缓存资源。 一致哈希算法的主要思想是将每个缓存服务器与一个或多个哈希值域区间关联起来，其中区间边界通过计算缓存服务器对应的哈希值来决定。（定义区间的哈希函数不一定和计算缓存服务器哈希值的函数相同，但是两个函数的返回值的范围需要匹配。）如果一个缓存服务器被移除，则它会从对应的区间会被并入到邻近的区间，其他的缓存服务器不需要任何改变。
实现:一致哈希将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。 当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。 更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

#使用方式
首先进行初始化

1
struct conhash_s *conhash = conhash_init(NULL);

其中参数是个函数指针，指定将字符串转成long int的hash函数。默认hash函数的实现是:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
long __conhash_hash_def(const char *instr)
{
    int i;
    long hash = 0;
    unsigned char digest[16];
    conhash_md5_digest((const u_char*)instr, digest);

    /* use successive 4-bytes from hash as numbers */
    for(i = 0; i < 4; i++)
    {
        hash += ((long)(digest[i*4 + 3]&0xFF) << 24)
            | ((long)(digest[i*4 + 2]&0xFF) << 16)
            | ((long)(digest[i*4 + 1]&0xFF) <<  8)
            | ((long)(digest[i*4 + 0]&0xFF));
    }
	return hash;
}
1
struct node_s g_nodes[64];

node_s是标识节点的结构体，定义如下：

1
2
3
4
5
6
struct node_s
{
    char iden[64]; /* node name or some thing identifies the node */
    u_int replicas; /* number of replica virtual nodes */
    u_int flag;
};

接下来是设置节点以及将添加节点：

1
2
3
4
/* set nodes */
conhash_set_node(&g_nodes[0], "titanic", 32);
/* add nodes */
conhash_add_node(conhash, &g_nodes[0]);

其中titanic是这个节点的唯一标识符也就是node_s中的iden，一般可以用机器名或IP地址。而后面的32则代表这个节点对应的虚拟节点的数量replicas，一般来说一个节点的虚拟节点数占总的虚拟节点数的比重越大，那么分配到这个节点的条目也就越多。
flag是标识节点状态的，有

1
2
#define NODE_FLAG_INIT  0x01 /* node is initialized */
#define NODE_FLAG_IN    0x02 /* node is added in the server */

两种状态

删除节点与查询：

1
2
conhash_del_node(conhash, &g_nodes[0]);
struct node_s node = conhash_lookup(conhash, str);

释放资源：

1
conhash_fini(conhash);

#内部实现原理

libconhash使用红黑树来保存虚拟节点。当一个节点插入后，生成所有的虚拟节点标识符字符串，并进行hash运算转成long之后插入到红黑树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//replicas是节点的虚拟节点数量
for(i = 0; i < node->replicas; i++)
{
    //生成虚拟几点的标识符
    __conhash_node2string(node, i, buff, &len);
    //计算标识符的hash，cb_hashfunc是初始化时制定的hash函数指针
    hash = conhash->cb_hashfunc(buff);
    //如果红黑树种没有存在的话就插入其中。
    if(util_rbtree_search(&(conhash->vnode_tree), hash) == NULL)
    {
        //生成红黑树节点
        rbnode = __conhash_get_rbnode(node, hash);
        if(rbnode != NULL)
        {
            //生成成功就插入到红黑树中
            util_rbtree_insert(&(conhash->vnode_tree), rbnode);
            conhash->ivnodes++;
        }
    }
}

其中生成红黑树节点的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
util_rbtree_node_t *__conhash_get_rbnode(struct node_s *node, long hash)
{
    util_rbtree_node_t *rbnode;
    rbnode = (util_rbtree_node_t *)malloc(sizeof(util_rbtree_node_t));
    if(rbnode != NULL)
    {
        rbnode->key = hash;
        rbnode->data = malloc(sizeof(struct virtual_node_s));
        if(rbnode->data != NULL)
        {
            struct virtual_node_s *vnode = rbnode->data;
            vnode->hash = hash;
            vnode->node = node;
        }
        else
        {
            free(rbnode);
            rbnode = NULL;
        }
    }
    return rbnode;
}

virtual_node_s保存了hash值和实际节点的指针：

1
2
3
4
5
struct virtual_node_s
{
	long hash;
	struct node_s *node; /* pointer to node */
};

而删除节点就是将红黑树中的它的所有虚拟节点删除
其中虚拟节点标识符的生成规则是：

1
_snprintf_s(buf, 127, _TRUNCATE, "%s-%03d", node->iden, replica_idx);

而查找的流程就是计算查找对象的hash然后查找红黑树中比他大的最小节点如果没有比他大的就选择最小的节点。

1
2
3
4
5
6
7
hash = conhash->cb_hashfunc(object);
rbnode = util_rbtree_lookup(&(conhash->vnode_tree), hash);
if(rbnode != NULL)
{
	struct virtual_node_s *vnode = rbnode->data;
	return vnode->node;
}

红黑树的查找代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if((rbtree != NULL) && !util_rbtree_isempty(rbtree))
{
	util_rbtree_node_t *node = NULL;
	util_rbtree_node_t *temp = rbtree->root;
	util_rbtree_node_t *null = _NULL(rbtree);
	while(temp != null)
	{
		if(key <= temp->key)
		{
			node = temp; /* update node */
			temp = temp->left;
		}
		else if(key > temp->key)
		{
			temp = temp->right;
		}
	}
	/* if node==NULL return the minimum node */
	return ((node != NULL) ? node : util_rbtree_min(rbtree));
}