Guava 中的一致性哈希

最近发现在Guava中有一个Hashing类简单实现了一个一致性哈希的算法。

它使用起来非常简单,里面有一个consistentHash()的静态方法：

// bucket 的范围在 0 ~ buckets 之间
int bucket = Hashing.consistentHash(id, buckets) 

传入数据主键id(分片片键)和集群中机器数量buckets，返回一个固定的数字，表示数据应当落在第几个机器上。

而这个方法内部实现也非常简单:

public static int consistentHash(long input, int buckets) {
    // 检查
    checkArgument(buckets > 0, "buckets must be positive: %s", buckets);
    // 利用内部的LCG算法实现，产生伪随机数
    LinearCongruentialGenerator generator = new LinearCongruentialGenerator(input);
    int candidate = 0;
    int next;

    // Jump from bucket to bucket until we go out of range
    while (true) {
        // generator.nextDouble() 产生伪随机数
        // 每次hash的循环中每一个的next的值总是会固定 :
        // 比如:
        //      hash 1 round 1 -> 9  hash 2 round 1 -> 9
        //      hash 1 round 2 -> 7  hash 2 round 2 -> 7
        //      hash 1 round 3 -> 2  hash 2 round 3 -> 2
        next = (int) ((candidate + 1) / generator.nextDouble());

        if (next >= 0 && next < buckets) {
            //  如果在 0 到 bucket 范围之外, 将这个next值赋值给candidate,重新计算
            candidate = next;
        } else {
            //  如果在 0 到 bucket 范围之内, 就返回这个 candidate 值,作为 input数据存储的槽
            return candidate;
        }
    }
}

// LCG伪随机数的算法实现，关于LCG的解释可以参考 http://en.wikipedia.org/wiki/Linear_congruential_generator
private static final class LinearCongruentialGenerator {
    private long state;

    public LinearCongruentialGenerator(long seed) {
        this.state = seed;
    }

    public double nextDouble() {
        state = 2862933555777941757L * state + 1;
        return ((double) ((int) (state >>> 33) + 1)) / (0x1.0p31);
    }
}

通过 Guava 的这个方法，我们就可以轻松地在项目中使用一致性哈希了。