我应该如何使用番石榴的哈希#consistentHash？

java guava consistent-hashing

2022-09-01 21:23:11

我正在研究在我正在编写的一些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”。

我是否应该维护一个单独的（比列表更复杂）的数据结构来管理存储桶的删除和添加？我想我设想了一个更复杂的哈希API，它将在为我添加和删除特定存储桶后管理重新映射。

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

答案 1

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

servers.remove(n)

由

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

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

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

答案 2

我认为目前没有一个好方法可以做到这一点。在当前形式下，只有在简单的情况下才有用 - 基本上，在你有一个旋钮来增加或减少服务器数量的情况下......但总是通过添加和删除在最后。consistentHash

正在进行一些工作来添加如下类：

public final class WeightedConsistentHash<B, I> {
  /** Initially, all buckets have weight zero. */
  public static <B, I> WeightedConsistentHash<B, I> create(
      Funnel<B> bucketFunnel, Funnel<I> inputFunnel);

  /**
   * Sets the weight of bucket "bucketId" to "weight".
   * Requires "weight" >= 0.0.
   */
  public void setBucketWeight(B bucketId, double weight);

  /**
   * Returns the bucket id that "input" maps to.
   * Requires that at least one bucket has a non-zero weight.
   */
  public B hash(I input);
}

然后你会写：

WeightedConsistentHash<String, String> serverChooser =
    WeightedConsistentHash.create(stringFunnel(), stringFunnel());
serverChooser.setBucketWeight("server1", 1);
serverChooser.setBucketWeight("server2", 1);
// etc.

System.out.println("First time routed to: " + serverChooser.hash("someId"));

// one of the back end servers is removed from the (middle of the) pool
serverChooser.setBucketWeight("server2", 0);

System.out.println("Second time routed to: " + serverChooser.hash("someId"));

而且每次都应该获得相同的服务器。该 API 看起来合适吗？