我应该如何使用Guava的Hashing#consistentHash？

Question

我正在研究在我正在编写的一些java代码中使用一致的哈希算法.番石榴哈希库有一个consistentHash(HashCode, int)方法,但文档相当缺乏.我最初的希望是,我可以使用consistentHash()简单的会话亲和性来有效地在一组后端服务器上分配负载.

有没有人有一个如何使用这种方法的现实世界的例子？特别是我关心的是管理从目标范围中移除铲斗.

例如:

@Test
public void testConsistentHash() {
    List<String> servers = Lists.newArrayList("server1", "server2", "server3", "server4", "server5");

    int bucket = Hashing.consistentHash(Hashing.md5().hashString("someId"), servers.size());
    System.out.println("First time routed to: " + servers.get(bucket));

    // one of the back end servers is removed from the (middle of the) pool
    servers.remove(1);

    bucket = Hashing.consistentHash(Hashing.md5().hashString("blah"), servers.size());
    System.out.println("Second time routed to: " + servers.get(bucket));
}

导致输出:

First time routed to: server4
Second time routed to: server5

我想要的是在清除列表中较早的服务器之后将该标识符("someId")映射到同一服务器.所以在上面的示例中,删除后我想我想要桶0映射到"server1",桶1映射到"server3",桶2映射到"server4",桶3映射到"server5".

我是否应该维护一个单独的(比列表更复杂)数据结构来管理存储桶删除和添加？我想我可能已经设想了一个更复杂的Hashing API,可以在为我添加和删除特定存储桶后管理重新映射.

注意:我知道示例代码使用的是小输入和存储桶集.我尝试了100个桶中的1000个输入,结果是一样的.当我更改buckets为99并且存储桶99分布在剩余的99个存储桶中时,映射到存储桶0-98的输入保持不变.

Answer 1

恐怕没有任何数据结构可以在当前的consistentHash. 由于该方法仅接受列表大小，因此只能支持从末尾添加和删除。目前，最好的解决方案可能包括替换

servers.remove(n)

经过

server.set(n, servers.get(servers.size() - 1);
servers.remove(servers.size() - 1);

通过这种方式，您可以交换发生故障的服务器和最后一个服务器。这看起来很糟糕，因为它使得两个交换服务器的分配错误。这个问题的严重程度只是其中一个问题失败的一半。但这是有道理的，因为在删除最后一个列表元素之后，一切都很好，除了对故障服务器和之前最后一个服务器的分配之外。

因此，需要更改的作业数量是两倍。不是最佳的，但希望可用？