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
2 回目のルーティング先: server5

私が望むのは、リストの前のサーバーを削除した後、その識別子 (「someId」) を同じサーバーにマップすることです。上記のサンプルでは、​​削除後、バケット 0 を「server1」に、バケット 1 を「server3」に、バケット 2 を「server4」に、バケット 3 を「server5」にマッピングしたいと思います。

バケットの削除と追加を管理するために、別の (リストよりも複雑な) データ構造を維持する必要がありますか? おそらく、特定のバケットを追加および削除した後の再マッピングを管理する、より複雑なハッシュ API を想定していたと思います。

注:サンプル コードが小さな入力とバケット セットを使用していることはわかっています。100 個のバケットにわたる数千の入力でこれを試しましたが、結果は同じです。バケット 0 ～ 98にマップされる入力は、 を 99 に変更しても同じままで、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

残念ながら、現在の .xml では本当に正しく処理できるデータ構造はありませんconsistentHash。このメソッドはリスト サイズのみを受け入れるため、末尾からの追加と削除しかサポートできません。現在、最良の解決策はおそらく交換で構成されています

servers.remove(n)

に

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

このようにして、失敗したサーバーと最後のサーバーを交換します。これは、スワップされた 2 つのサーバーへの割り当てが間違っているため、見栄えがよくありません。この問題は、そのうちの 1 つが失敗した場合の半分にすぎません。ただし、最後のリスト要素を次のように削除した後は、失敗したサーバーへの割り当てと以前の最後のサーバーへの割り当てを除いて、すべて問題ないため、これは理にかなっています。

したがって、必要に応じて 2 倍の割り当てが変更されます。最適ではありませんが、うまくいけば使用できますか?

于 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 に答える