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

Question

我正在考虑使用 consistent hash我正在编写的一些java代码中的算法。 guava Hashing 库有一个 consistentHash(HashCode, int) 方法，但是 the documentation比较缺乏。我最初的希望是我可以使用 consistentHash() 来实现简单的 session 亲和性，从而在一组后端服务器之间有效地分配负载。

有人有如何使用此方法的真实示例吗？特别是我关心管理从目标范围中移除存储桶。

例如:

@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: server4Second time routed to: server5

我想要的是在删除列表中较早的服务器后将该标识符(“someId”)映射到同一服务器。所以在上面的示例中，删除后我想我希望存储桶 0 映射到“server1”，存储桶 1 映射到“server3”，存储桶 2 映射到“server4”，存储桶 3 映射到“server5”。

我是否应该维护一个单独的(比列表更复杂的)数据结构来管理存储桶的删除和添加？我想我可能已经设想了一个更复杂的哈希 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);

这样你就可以交换失败的服务器和最后一个服务器。这看起来很糟糕，因为它使对两个交换服务器的分配错误。这个问题只是其中一个失败的一半。但这是有道理的，因为在以下删除最后一个列表元素之后，一切都很好，除了分配给失败的服务器和之前的最后一个服务器。

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