24

我正在研究在我正在编写的一些 java 代码中使用一致的哈希算法。guava Hashing 库有一个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));
}

导致输出：

第一次路由到：server4
第二次路由到：server5

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

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

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

4

4 回答 4

4

我认为目前没有什么好的方法可以做到这一点。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 看起来合适吗？

于 2012-09-07T14:34:01.073 回答
4

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

servers.remove(n)

经过

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

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

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

于 2012-09-07T15:11:48.610 回答
2

guava API 不知道您的服务器列表。它只能保证：

int bucket1 = Hashing.consistentHash(Hashing.md5().hashString("server1"),N);    
int bucket2 = Hashing.consistentHash(Hashing.md5().hashString("server1"),N-1);

assertThat(bucket1,is(equalTo(bucket2))); iff bucket1==bucket2!=N-1

您需要自己管理存储桶到您的服务器列表

于 2012-09-09T03:29:26.100 回答
1

问题中提出的答案是正确的：

我是否应该维护一个单独的（比列表更复杂的）数据结构来管理存储桶的删除和添加？

番石榴正在散列成一个带有序数的环。从这些序数到服务器 ID 的映射必须在外部维护：

  • 最初给定 N 个服务器 - 可以为每个序数 0..N-1 选择一些任意映射到服务器 ID A..K ( 0 -> A , 1 -> B , .., N-1 -> K ) . 还需要从服务器 ID 到其序号的反向映射（A -> 0，B -> 1，..）。

  • 在删除服务器时 - 序数空间缩小一。所有以已删除服务器的序号开头的序数都需要重新映射到下一个服务器（移位一个）。

    例如，在初始映射之后，假设服务器 C（对应于序号 2）被删除。现在新的映射变为： ( 0 -> A , 1 -> B , 2->D , 3 -> E , .., N-2 -> K )

  • 在添加服务器 L 时（比如从 N 到 N+1 个服务器） - 可以从 N->L 添加一个新映射。

我们在这里所做的是模仿节点在添加和删除时如何在环中移动。虽然节点的顺序保持不变 - 它们的序号（Guava 在其上运行）可以随着节点的到来和离开而改变。

于 2018-08-20T06:05:00.403 回答