10

コンシステントハッシュがどのように機能するかを理解しようとしています。これは私がフォローしようとしているがフォローできない記事です。私の質問から始めましょう。

  1. サーバーはハッシュコードの範囲にマッピングされ、データの分散がより固定され、見た目が簡単になることを理解しています。しかし、これは新しいノードがクラスターに追加される問題にどのように対処しますか？

  2. サンプルのJavaコードは機能していません。単純なJavaベースのコンシステントハッシュの提案です。

アップデート

  1. コンシステントハッシュに代わるものはありますか？
4

4 に答える 4

5

Pythonの実装については、私のgithubリポジトリを参照してください

最も簡単な説明通常のハッシュとは何ですか？

次のキーと値のペアをredisのような分散メモリストアに格納する必要があるとします。

ここに画像の説明を入力してください

上記のIDを取得し、そこからハッシュを作成するハッシュ関数f（id）があるとします。3台のサーバーがあると仮定します-（s1、s2、s3）

サーバーの数、つまり3でハッシュのモジュロを実行して、各キーをサーバーにマップすることができます。

ここに画像の説明を入力してください

f（）を使用した単純なルックアップによって、キーの値を取得できます。キージャクソンについて言う、f（ "ジャクソン"）％（サーバーの数）=> 1211 * 3 = 2（ノード2）。

これは完璧に見えます、そうです、葉巻ではありません！

しかし、サーバーがノード1がダウンしたと言ったらどうなるでしょうか。同じ式、つまりユーザーJacksonにf（id）％（サーバーの数）を適用すると、1211％2 = 1になります。つまり、実際のキーが上記の表からノード2にハッシュされたときにノード1が取得されます。

ここで再マッピングを行うことができます。10億個のキーがある場合はどうなりますか。その場合、面倒なキーを大量に再マッピングする必要があります:(

これは、従来のハッシュ手法の主要なフローです。

コンシステントハッシュとは何ですか？

コンシステントハッシュ法では、円形リング内のすべてのノードのリストを視覚化します。（基本的には並べ替えられた配列）

ConsistantHashingRing

start func
For each node:
 Find f(node) where f is the hash function
 Append each f(node) to a sorted array
For any key
  Compute the hash f(key)
  Find the first f(node)>f(key)
  map it
end func

たとえば、キースミスをハッシュする必要がある場合は、ハッシュ値1123を計算し、ハッシュ値> 1123の直接ノード、つまりハッシュ値1500のノード3を見つけます。

さて、サーバーを失うとどうなりますか、たとえばノード2を失うと、すべてのキーを次のサーバーノード3にマップできます:)はい、ノード2のキーを再マップするだけで済みます

ここに画像の説明を入力してください

于 2019-10-23T04:30:29.543 に答える
4

私はあなたの質問の最初の部分に答えます。まず第一に、そのコードにはいくつかのエラーがあるので、より良い例を探します。

ここでの例としてキャッシュサーバーを使用します。

コンシステントハッシュについて考えるときは、リンク先の記事と同様に、それを円形のリングと考える必要があります。新しいサーバーが追加されると、最初からサーバーにデータがありません。クライアントがそのサーバー上にあるはずのデータをフェッチし、それが見つからない場合、キャッシュミスが発生します。次に、プログラムは新しいノードのデータを入力する必要があるため、今後のリクエストはキャッシュヒットになります。キャッシングの観点からは、これで終わりです。

于 2010-09-29T03:01:39.120 に答える
1

概要

コンシステントハッシュがどのように機能するかについてブログを書きました。ここでは、これらの元の質問に答えるために、以下に簡単な要約を示します。

コンシステントハッシュは、データ分割の目的でより一般的に使用され、通常、次のようなコンポーネントで見られます。

  • ロードバランサー
  • APIゲートウェイ
  • ..。

質問に答えるために、以下はカバーします

  1. 使い方
  2. サーバーノードを追加/検索/削除する方法
  3. それを実装する方法
  4. コンシステントハッシュに代わるものはありますか？

ここで簡単な例を使用してみましょう。ロードバランサーは、2つのオリジンノード（ロードバランサーの背後にあるサーバー）と同じハッシュリングサークル内の着信リクエストをマップします（ハッシュリングの範囲が[0,255]であるとします）。

初期状態

サーバーノードには、次のテーブルがあります。

ここに画像の説明を入力してください

ノードの検索

着信リクエストに対して、同じハッシュ関数を適用し、ハッシュコード= 120のリクエストのハッシュコードを取得すると仮定します。テーブルから、時計回りに次に近いノードが見つかるため、ノード2はこの場合のターゲットノード。

同様に、ハッシュコード=220のリクエストを受け取った場合はどうなりますか？ハッシュリングの範囲は円であるため、最初のノードを返します。

ノードの追加

次に、クラスターにもう1つのノードノード3（ハッシュコード150）を追加すると、テーブルが次のように更新されます。

ここに画像の説明を入力してください

次に、[ノードの検索]セクションで同じアルゴリズムを使用して、次に近いノードを検索します。たとえば、ハッシュコード= 120のリクエストは、ノード3にルーティングされます。

ノードを削除

削除も簡単です。テーブルからエントリ<node、hashcode>を削除するだけです。たとえば、node-1を削除すると、テーブルは次のように更新されます。

ここに画像の説明を入力してください

次に、すべてのリクエストは次のようになります。

  • [201、255]および[0、150]のハッシュコードはノード3にルーティングされます
  • [151、200]のハッシュコードはノード2にルーティングされます

実装

以下は、Javaに非常によく似た単純なc ++バージョン（仮想ノードが有効になっている）です。

#define HASH_RING_SZ 256

struct Node {
  int id_;
  int repl_;
  int hashCode_;
  Node(int id, int replica) : id_(id), repl_(replica) {
    hashCode_ =
      hash<string>{} (to_string(id_) + "_" + to_string(repl_)) % HASH_RING_SZ;
  }
};

class ConsistentHashing {
private:
  unordered_map<int/*nodeId*/, vector<Node*>> id2node;
  map<int/*hash code*/, Node*> ring;

public:
  ConsistentHashing() {}

  // Allow dynamically assign the node replicas
  // O(Rlog(RN)) time
  void addNode(int id, int replica) {
    for (int i = 0; i < replica; i++) {
      Node* repl = new Node(id, replica);

      id2node[id].push_back(repl);
      ring.insert({node->hashCode_, repl});
    }
  }

  // O(Rlog(RN)) time
  void removeNode(int id) {
    auto repls = id2node[id];
    if (repls.empty()) return;

    for (auto* repl : repls) {
      ring.erase(repl->hashCode_);
    }

    id2node.erase(id);
  }

  // Return the nodeId
  // O(log(RN)) time
  int findNode(const string& key) {
    int h = hash<string>{}(key) % HASH_RING_SZ;

    auto it = ring.lower_bound(h);
    if (it == ring.end()) it == ring.begin();

    return it->second->id;
  }
};

代替案

私が質問を正しく理解している場合、質問は、データ分割の目的でコンシステントハッシュの代替案を尋ねることです。実際にはたくさんありますが、実際のユースケースに応じて、次のようなさまざまなアプローチを選択できます。

  • ランダム
  • ラウンドロビン
  • 加重ラウンドロビン
  • Modハッシュ
  • コンシステントハッシュ
  • 加重（動的）コンシステントハッシュ
  • 範囲ベース
  • リストベース
  • 辞書ベース
  • ..。

特に負荷分散ドメインでは、次のようなアプローチもあります。

  • 最小の接続
  • 最小応答時間
  • 最小帯域幅
  • ..。

上記のすべてのアプローチには独自の長所と短所があり、最善の解決策はありません。それに応じてトレードオフを行う必要があります。

最後

上記のように、元の質問の簡単な要約をさらに読むために：

  • コンシステントハッシュアンバランスの問題
  • 雪のクラッシュの問題
  • 仮想ノードの概念
  • レプリカ番号を微調整する方法

私はすでにブログでそれらをカバーしました、以下はショートカットです：

楽しむ ：）

于 2020-07-20T22:13:55.640 に答える
1

私はあなたの質問の最初の部分に答えます。発生する問題は、コンシステントハッシュが実際にどのように機能するかということです。クライアント/サーバーモデルでは、サーバーへのネットワークリクエストのトラフィックに応じて、リクエストをさまざまなサーバーにルーティングするロードバランサーが存在することがわかっています。

したがって、ハッシュの目的は、要求しているすべてのクライアントに数字を割り当て、多数のサーバーによってそれをモード化（数学）することです。モード後に取得する残りの部分は、その特定のサーバーにリクエストを割り当てます。

コンシステントハッシュ戦略では、ハッシュ関数を使用してクライアントとサーバーを循環パス上に配置します。クライアントが時計回りの方向にある場合、リクエストをルーティングします。クライアントのリクエストは、パスの最初に来るサーバーによって受け入れられます。

1台のサーバーが停止した場合はどうなりますか？

以前、単純なハッシュ戦略では、計算をやり直して、取得する残りの部分に従ってリクエストをルーティングする必要があり、キャッシュヒットの問題に直面します。

このコンシステントハッシュ戦略では、いずれかのサーバーが停止した場合、クライアントの要求は同じ時計回りの方向のパスで次のサーバーに移動します。つまり、他のサーバーやキャッシュヒットに影響を与えることはなく、一貫性が維持されます。

于 2021-12-08T06:38:06.363 に答える