一致哈希算法C语言实现（过程剖析）。

源码地址：http://www.codeproject.com/Articles/56138/Consistent-hashing
本文对链接中源码进行剖析。

先来看看对元素的定义：

struct node_s/* 定义实体结点*/
{
char iden[64]; /* 每个缓存结点的名字或者信息 */
u_int replicas; /*实体结点的虚拟结点数量*/
u_int flag;/* 结点标识*/
};

/* 定义虚拟结点 */
struct virtual_node_s
{
long hash;/* 哈希值 */
struct node_s *node; /* 指向实体结点的指针 */
};
/* 一致性哈西 */
struct conhash_s
{
util_rbtree_t vnode_tree; /* 这里是利用红黑树来存储数据的 */
u_int ivnodes; /* 虚拟结点的数量 */
long (*cb_hashfunc)(const char *);
};

函数的声明：

/* 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);//删除实体结点
/*
* update a node's virtual nodes
* @replica: new replica of server
* return 0 success, -1 failed
*/
CONHASH_API int conhash_update_node(struct conhash_s *conhash, struct node_s *node, u_int replica);//更新缓存结点
/*
* 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);//寻找目标对应的实体结点
/* some utility functions export*/
CONHASH_API void conhash_md5_digest(const u_char *instr, u_char digest[16]);//一些使用功能的接口
/* get virtual node number in the hash */
CONHASH_API u_int conhash_get_vnodes_num(const struct conhash_s *conhash);//计算每个缓存结点的哈希值
/*
* get virtual nodes in ascending oder
* @values, pointer to an array, stores all the nodes's hash value
* @size, how many nodes to get, can't be less than the array size
*/
CONHASH_API void conhash_get_vnodes(const struct conhash_s *conhash, long *values, int size);//获得缓存结点的上升值

下面来看看函数的实现：

struct conhash_s* conhash_init(conhash_cb_hashfunc pfhash)
{
/* 定义一个缓存机器并初始化为0 */
struct conhash_s *conhash = (struct conhash_s*)calloc(1, sizeof(struct conhash_s));
if(conhash == NULL)//没calloc出来直接返回
{
return NULL;
}
do
{
/* 设置回调函数 */
if(pfhash != NULL)
{
conhash->cb_hashfunc = pfhash;//传入的数据保存下来
}
else
{
conhash->cb_hashfunc = __conhash_hash_def;
}
util_rbtree_init(&conhash->vnode_tree);//初始化用来存储数据的红黑树
return conhash;
}while(0);
free(conhash);
return NULL;
}
void conhash_fini(struct conhash_s *conhash)
{
if(conhash != NULL)
{
/* 释放红黑树 */
while(!util_rbtree_isempty(&(conhash->vnode_tree)))
{
util_rbtree_node_t *rbnode = conhash->vnode_tree.root;
util_rbtree_delete(&(conhash->vnode_tree), rbnode);
__conhash_del_rbnode(rbnode);
}
free(conhash);
}
}
void conhash_set_node(struct node_s *node, const char *iden, u_int replica)
{
strncpy(node->iden, iden, sizeof(node->iden)-1);
node->replicas = replica;
node->flag = NODE_FLAG_INIT;//把标注转换成已被初始化
}
int conhash_add_node(struct conhash_s *conhash, struct node_s *node)
{
if((conhash==NULL) || (node==NULL))
{
return -1;
}
/* 首先检查结点 */
if(!(node->flag&NODE_FLAG_INIT) || (node->flag&NODE_FLAG_IN))
{
return -1;
}
node->flag |= NODE_FLAG_IN;
/* 再做添加的后续工作 */
__conhash_add_replicas(conhash, node);
return 0;
}
int conhash_del_node(struct conhash_s *conhash, struct node_s *node)
{
if((conhash==NULL) || (node==NULL))
{
return -1;
}
/* 先检查一下node是否存在 */
if(!(node->flag&NODE_FLAG_INIT) || !(node->flag&NODE_FLAG_IN))
{
return -1;
}
node->flag &= (~NODE_FLAG_IN);
/* 调整至删除后对应的状态 */
__conhash_del_replicas(conhash, node);
return 0;
}
const struct node_s* conhash_lookup(const struct conhash_s *conhash, const char *object)
{
long hash;
const util_rbtree_node_t *rbnode;
if((conhash==NULL) || (conhash->ivnodes==0) || (object==NULL))
{
return NULL;
}
/* 计算哈希值 */
hash = conhash->cb_hashfunc(object);
rbnode = util_rbtree_lookup(&(conhash->vnode_tree), hash)
/* 找到了就返回值，找不到就返回NULL */
if(rbnode != NULL)
{
struct virtual_node_s *vnode = rbnode->data;
return vnode->node;
}
return NULL;
}

最后来看上面接口中的小功能实现：

/*
* 利用MD5作为默认的哈希==加密
* instr即为input string
*/
long __conhash_hash_def(const char *instr)
{
int i;
long hash = 0;
unsigned char digest[16];
conhash_md5_digest((const u_char*)instr, digest);
/*利用连续的4个比特位来计算哈希*/
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;
}
void __conhash_add_replicas(struct conhash_s *conhash, struct node_s *node)//加入一个设备需要的代价
{
u_int i, len;
long hash;
char buff[128];
util_rbtree_node_t *rbnode;
for(i = 0; i < node->replicas; i++)
{
/* 计算每个虚拟结点的哈希值 */
__conhash_node2string(node, i, buff, &len);
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++;
}
}
}
}
void __conhash_del_replicas(struct conhash_s *conhash, struct node_s *node)//删除一个设备需要做的工作
{
u_int i, len;
long hash;
char buff[128];
struct virtual_node_s *vnode;
util_rbtree_node_t *rbnode;
for(i = 0; i < node->replicas; i++)
{
/* 计算每个虚拟结点的哈希值*/
__conhash_node2string(node, i, buff, &len);
hash = conhash->cb_hashfunc(buff);
rbnode = util_rbtree_search(&(conhash->vnode_tree), hash);
if(rbnode != NULL)//删掉数据
{
vnode = rbnode->data;
if((vnode->hash == hash) && (vnode->node == node))
{
conhash->ivnodes--;
util_rbtree_delete(&(conhash->vnode_tree), rbnode);
__conhash_del_rbnode(rbnode);
}
}
}
}
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)//如果不为NULL有存入的必要再存
{
struct virtual_node_s *vnode = rbnode->data;
vnode->hash = hash;
vnode->node = node;
}
else//要不然就释放了
{
free(rbnode);
rbnode = NULL;
}
}
return rbnode;
}
void __conhash_del_rbnode(util_rbtree_node_t *rbnode)//释放红黑树结点
{
struct virtual_node_s *node;
node = rbnode->data;
free(node);
free(rbnode);
}

总结：此项目利用红黑树做每个高速缓存机器的底层框架，利用MD5来算哈希值实现。

enenshiwo

一致哈希算法C语言实现（过程剖析）。