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

源码地址：
本文对链接中源码进行剖析。

先来看看对元素的定义：

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来算哈希值实现。