TrafficServer一致性Hash的实现分析

时间：2010-11-01 来源：wahu0315210

    ts(TrafficServer)在iocore下面的cluster中的ClusterHash.cc下利用一种非常巧妙的方式实现了一致性hash算法，用于将需要缓存的对象object均匀地分配到Cluster集群中的各个节点中去。
    ts在具体实现时规定：
    (1)一个Cluster集群最大只能由256个机器组成。
    (2)hash数值空间的大小为小于2^15的最大素数32707，在一致性hash下，这个hash数值空间的大小代表的就是虚拟节点的数目。
    以下给出ts在具体实现时的代码，这里，我将多余的代码都删除了。

//hash数值空间

#define CLUSTER_HASH_TABLE_SIZE 32707
//组成一个Cluster的最大机器数

#define CLUSTER_MAX_MACHINES 256

struct ClusterMachine
{
    unsigned int ip;
};
struct ClusterConfiguration
{
    ClusterMachine *machines[CLUSTER_MAX_MACHINES];
    int n_machines;
    unsigned char hash_table[CLUSTER_HASH_SIZE];
};

inline unsigned short
next_rnd15(unsigned int *p)
{
    unsigned int seed = *p;
    seed = 1103515145 * seed + 12345;
    seed = seed & 0x7FFF;
    *p = seed;
    return seed;
}

void
build_hash_table_machine(ClusterConfiguration *c)
{
    int left = CLUSTER_HASH_TABLE_SIZE;
    int m = 0;
    int i = 0;
    unsigned int rnd[CLUSTER_MAX_MACHINES];
    unsigned int mach[CLUSTER_MAX_MACHINES];
    int total = CLUSTER_HASH_TABLE_SIZE;

    for (i = 0; i < c->n_machines; i++) {
        int mine = total / (c->n_machines - i);
        mach[i] = mine;
        total -= mine;
    }

    for(m = 0; m < c->n_machines; m++)
    {
        rnd[m] = (((c->machines[m]->ip >> 15) & 0x7FFF) ^ (c->machines[m]->ip & 0x7FFF))
            ^ (c->machines[m]->ip >> 30);
    }

    for (i = 0; i < CLUSTER_HASH_TABLE_SIZE; i++)
      c->hash_table[i] = 255;

    m = 0;
    while (left) {
        do {
            i = next_rand(&rnd[m]) % CLUSTER_HASH_TABLE_SIZE;
        } while (c->hash_table[i] != 255);
        mach[m]--;
        c->hash_table[i] = m;
        left--;
        m = (m + 1) % c->n_machines;
    }
}

    我们可以通过以下两点来理解ts的一致性hash的实现：hash算法的平衡性和单调性。
    (1)对于一个环形的hash空间，ts将每一位都映射到Cluster集群中的某个节点机器上去。这样，Cluster中的每一个节点就对应hash空间中的多个虚拟节点。为了保证hash算法的平衡性，这里需要保证映射到Cluster中的每一个节点的虚拟节点数目大致相同。ts通过以下代码保证这一点：

for (i = 0; i < c->n_machines; i++) {
    int mine = total / (c->n_machines - i);
    mach[i] = mine;
    total -= mine;
}

    这段代码可以通过这样一个例子来理解：现在一共有N个苹果，n个小孩来分，N不能整除n，请问怎么分既快又公平？比较好的解决方法是：首先按照N能够整除 n的假设，将苹果平均分给这n个小孩。这样，第一个小孩就得到N/n个苹果，然后在剩余的苹果和小孩中按照上面的假设递归分下去。最后每个小孩得到的苹果数目就比较平均，而且时间复杂度为O(n)。
    (2)为了保证hash算法的单调性，ts需要保证增加节点或删除节点时，剩余的大多数节点能够映射到与原来相同的hash空间上去。ts通过以下代码来保证这一点：

while (left) {
        do {
            i = next_rand(&rnd[m]) % CLUSTER_HASH_TABLE_SIZE;
        } while (c->hash_table[i] != 255);
        mach[m]--;
        c->hash_table[i] = m;
        left--;
        m = (m + 1) % c->n_machines;
    }

    这段代码可以保证：1)由于每个节点对应的hash空间中的虚拟节点都是通过对节点的ip地址取随机数然后向hash空间的大小取模，这样删除或增加节点时，剩余节点获取虚拟节点的公式不受影响，所以可以保证hash算法的单调性。2)由于每次是循环顺序遍历Cluster中的每个节点得到该节点对应的虚拟节点，这样可以保证每个节点对应的hash空间中的虚拟节点分布比较均匀。
    这段代码中让我有点迷惑的是next_rand函数，它实现了一个随机数算法，ts代码中注释是这样解释的："Not very random, but it generates all the numbers within 1 period which is all we need."。有时间需要做个实验查看一下这个随机数产生的结果是怎样的，也期待大牛给予解释。
    后续我会给出该算法的实验性能数据，以供参考。
    以下给出一些一致性Hash的参考资料：
http://en.wikipedia.org/wiki/Consistent_hash
http://blog.csdn.net/sparkliang/archive/2010/02/02/5279393.aspx