TrafficServer一致性hash实现

        TrafficServer的一致性hash实现与基于RBTree的一致性hash实现存在着比较大的差异。下面以Cluster模式的一致性哈希实现为例进行说明：

 1 数据结构

在trafficser中实现一致性hash的结构为struct ClusterConfiguration，其定义如下：

struct ClusterConfiguration

{

int n_machines; //cluster包含的机器数目

ClusterMachine *machines[CLUSTER_MAX_MACHINES]; // 机器结构，256

ClusterMachine *machine_hash(unsigned int hash_value) // 计算hash在那台机器

{

return machines[hash_table[hash_value % CLUSTER_HASH_TABLE_SIZE]];

}

unsigned char hash_table[CLUSTER_HASH_TABLE_SIZE]; // hash空间 32707

…...

};

2. hash空间建立过程

假设有三台server，ip地址分别为1.1.1.1，2.2.2.2，3.3.3.3。则通过这三个ip地址能够分别计算出来三个hash值，再在该hash值的基础上加入随机因子计算出来另外的hash值（hash = 1103515145 * hash + 12345），依次递归可以得到三台server的一连串hash值。如下所示：

server：hash1->hash2->hash3.......hash n

hash(n) = 1103515145 * hash(n - 1) + 12345

再利用hash%/ CLUSTER_HASH_TABLE_SIZE分别得到hash table的slot，如果发生冲突则再用本hash链的下一个hash值，直至分配到一个hash table的slot。通过这样的方式依次利用server1、server2、server3 hash链中的hash值交替的填充hash table。

备注：实现文件trafficserver/iocore/cluster/ClusterHash.cc，实现函数为：build_hash_table_machine()

3 机器变动处理

在增加一台server（假设为Server4）时，由于原有server的hash链不会发生改变。因此，通过原有的hash链中hash值得到的slot不会发生变化。只是由于交替插入的时候引入了Server4的hash链，因此重新生成hash table时，server1-server3 hash链中插入hash table的hash值个数变少了。而这些少的slot正好由Server4 hash链中的hash值代替了。从而实现一致性hash。

在删除一台server（Server3）时，由于原有server的hash链不会发生改变。因此，通过原有的hash链中hash值得到的slot不会发生变化。只是由于交替插入的时候由于删除了Server3的hash链，因此重新生成hash table时，server1-server2 hash链中插入hash table的hash值个数变多了。而这些多的slot正好代替Server3 hash链中的hash值。从而实现一致性hash。

4 不足

基于hash链的一致性hash实现在有节点变动的时候需要重建hash table，其时间复杂度为O（hash table size * hash冲突）。而基于RBTree实现的时间复杂度为O（log（hash table size）*虚拟node数）。因此，在一些情况下，时间复杂度会高于RBTree的实现。