一致性hash算法，1997年麻省理工学院提出的一种分布式hash（DHT）实现算法，设计目标是为了解决因特网中热点（Hot spot）问题。hash算法的判断从四个方面来判断：平衡性、单调性、分散性、负载。
普通的hash（硬hash）采用简单的取模方式，进行散列。一致性hash算法实现的基本原理是将节点和key值都按照一样hash算法映射到0-2^32的环上。到有一个缓存的请求到来时，计算key值k对应的hash(K)，如果该值正好对应之前某个机器节点的hash值，则直接写入该机器节点，如果没有对应的节点，顺时针查到到下一个节点，进行写入。如果超过2^32还没有对应节点，则从0开始查找。
一致性算法Consistent-hashing：URL：
http://www.codeproject.com/Articles/56138/Consistent-hashing
Consistent-hashing 一致性hash算法
libconshash 源码使用了红黑树来存放虚拟节点信息。
1 首先对node的标志(“%s-%03d”, node->iden, 节点名 replica_idx，节点索引number)进行md5计算，然后对整数进行4字节的整数hash算法( MurmurHash, 一种非加密型哈希函数， 由Austin Appleby在2008年发明，并且有多个变种 特点：对于规律性较强的key，MurmurHash的随机分布特性表现更良好），得到了一个长整数
for(i = 0 ;i<4;i++){Md5是一个16字节长度的数组，将16字节的数组每四个字节一组，分别对应一个虚拟结点.
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));
}
。
2 然后根据__conhash_add_replicas 生成n->replicas数量的虚节点插入红黑树 。__conhash_get_rbnode(node, hash); 分配一个虚拟节点，然后插入红黑树中。util_rbtree_insert
3 __conhash_del_replicas 将虚节点从红黑树中删除
每次操作都是对每个虚拟节点vnode单独调用malloc和free。利用红黑树添加删除的时间负载度为O(logW).数组的实现因为每次都要重新初始化HASH环，因此时间复杂度为O(WNlog(WN))(N为节点数)。缺点为相对于数组实现来说，每个虚拟节点要浪费至少两个指针（红黑树节点的左右字数指针，以及一个颜色标记）的空间。
HAproxy的一致性hash算法
以cache为例，实现思想：
1. 根据server（cache）某个参数计算出的key，将server映射到2^31-1的环形空间中；object对象根据自身的key存储到相近的cache server中；当cache A server down之后，只会影响环中其key附近的object；
2. 由于cache server无法均匀的映射到环形空间中（不均衡问题），所以引入虚拟节点的概念，每台cache server分配X个虚拟节点映射到环中。
HAProxy 利用EBtree来管理node，而不是rbtree。优点是：是删除操作的复杂度是O(1)
chash_init_server_tree 虚拟节点的分配函数。
虚拟节点的个数为
srv->lb_nodes_tot = srv->uweight * BE_WEIGHT_SCALE;（uweight unsigned,32;BE_WEIGHT_SCALE,16) //512
即1台server会有512个虚拟节点；
hash key的计算
每个虚拟节点的hash key按如下公式计算：
for (node = 0; node < srv->lb_nodes_tot; node++) {
srv->lb_nodes[node].node.key=chash_hash(srv->puid*SRV_EWGHT_RANGE + node);
}
其中，puid为server配置的id号，SRV_EWGHT_RANGE=4K;
chash_hash()是一个32位的Thomas Wang的HASH算法（homas Wang在Jenkins的基础上，针对固定整数输入做了相应的Hash算法）
static inline unsigned int chash_hash(unsigned int a)
{
a = (a+0x7ed55d16) + (a<<12);
a = (a^0xc761c23c) ^ (a>>19);
a = (a+0x165667b1) + (a<<5);
a = (a+0xd3a2646c) ^ (a<<9);
a = (a+0xfd7046c5) + (a<<3);
a = (a^0xb55a4f09) ^ (a>>16);
/* ensure values are better spread all around the tree by multiplying
* by a large prime close to 3/4 of the tree.
*/
return a * 3221225473U;
}
添加/删除节点。
采用EBtree管理节点，添加删除节点在chash_queue_dequeue_srv()中实现；
chash_queue_dequeue_srv()相应操作函数为：
eb32_delete(&s->lb_nodes[s->lb_nodes_now].node); eb32_insert(s->lb_tree, &s->lb_nodes[s->lb_nodes_now].node);
对应的文件为Eb32tree.c文件的函数
static forceinline struct eb32_node * __eb32_insert(struct eb_root *root, struct eb32_node *new)。
旧版本HAProxy曾经使用过红黑树，用于任务调度、负载均衡等方面。但是Willy Tarreau认为，在事件响应非常频繁的情况下，任务插入、删除的频率非常高，这时候使用红黑树存在性能瓶颈，尤其不能接受红黑树删除节点的时间复杂度为O(log n)。因此，他发明了一种新的数据结构，叫做弹性二叉树（elastic binary tree），简称ebtree。
ebtree是不平衡的二叉搜索树（BST），而红黑树、AVL树等都是平衡的BST。传统的BST最怕的就是退化成线性搜索，因此，红黑树等BST插入、删除时都需要对树进行平衡化，而平衡化是一个从叶子节点开始，向根节点方向递归向上的过程，时间复杂度是O(log n)。
有鉴于此，ebtree为了实现删除节点时O(1)的时间复杂度，必然放弃保持树的平衡，为了拒绝由此而来的副作用——退化成线性搜索（或者更准确地说，退化成不受限制的线性搜索），不可避免地引入了一些新的成员和新的思路。
