一貫したハッシュ( Rubyの実装)

問題
あなたが複数のサーバーで実行しているWebアプリケーションを持っていると仮定しましょう.クエリを高速化するために、アプリケーションによって頻繁にアクセスされるデータを格納するためにキャッシュを追加します.情報のデータベースを呼び出す前に、まずキャッシュに存在するかどうかを確認します.あなたがより多くのユーザーを得るように、1つのキャッシュインスタンスは重要なパフォーマンスブーストを提供するにはあまりに小さいです.この場合、より多くの情報をキャッシュするために、キャッシュインスタンスをサーバーに追加します.
しかし、今では、キーを含んでいるかどうかをすべてのキャッシュインスタンスをチェックする必要があります.キャッシュのインスタンスが事前にキーを持っていることを知っていれば簡単です.

ハッシュ
ハッシュを使用して、キーを保存するキャッシュインスタンスを確認できます.計算するhash(key) % N どこhash いくつかのハッシュ関数とN はキャッシュインスタンスの数です.この関数はN それぞれの数値がキャッシュインスタンスを指している場合.したがって、キャッシュインスタンスにキーをマップできます.キーがキャッシュに存在するかどうかを確認するには、キャッシュインスタンスを取得するキーをハッシュし、そのインスタンスがキーを持っているかどうかをチェックします.この戦略は、効率的にルックアップを維持しながら、複数のキャッシュインスタンスを持つことができます.
しかし、キャッシュインスタンスがクラッシュした場合、どうなりますか?キャッシュインスタンスが利用できなくなり、キャッシュされたデータが失われます.将来のクエリでは、別のキャッシュインスタンスでデータをrecacheする必要があります.ただ一つの問題は、(hash(key) % N) 変更.すべてのキーが新しいキャッシュインスタンスにマップされます.マップするキーserver:A サーバへのマップ:サーバ: Cのみが利用できません.つのキャッシュインスタンスが利用できなくても、これはすべてのキャッシュインスタンスのキャッシュミスを増加させます.理想的には、利用できないサーバのキーを再マップしたいだけです.

一貫したハッシュ
一貫したハッシュはキャッシュインスタンスにキーをマップする戦略ですが、キャッシュインスタンスを利用可能なインスタンスのリストから追加または削除することができます.
一貫したハッシュは、円を想像することによって働きます.各キーとキャッシュインスタンスは、この円の対応するポイントを割り当てられます.キーを追加するにはどのキャッシュインスタンスを決定するには、我々は、時計回りの方向に行くサークル上の最も近いキャッシュにキーをマップします.

プログラム的に、一貫したハッシュは実装するのが簡単です.ハッシュ関数を使用して、キャッシュサーバのそれぞれをいくつかの整数にマップします.ここで、ハッシュはキャッシュのための円の点を表します.

  def add_node(node)
    hash = hash_value(node)
    hash_to_node[hash] = node

    puts "Nodes map to #{@hash_to_node}"
  end

 def hash_value(node)
    Digest::SHA256.digest(node).sum % 360
 end

上のコードでは、Hashのマッピングをhash_to_node .
キーを追加するには、どのキャッシュインスタンスを決定するには、我々は、キーのハッシュは、サークル上の対応点を見つける.それからハッシュのハッシュより大きい数にキャッシュを見つけます.これは効果的にキーのハッシュに最も近いキャッシュです.

  def find_cache(key)
    hash = hash_value(key)
    puts "#{key} hashes to #{hash}"

    node_hash = closest_node_hash(hash)
    node = hash_to_node[node_hash]

    puts "#{key} maps to  #{node}"
  end

 def closest_node_hash(key)
   @hash_to_node.keys.sort.bsearch { |server| server >= key } || @hash_to_node.keys.sort.first
 end

インclosest_node_hash(key) , キャッシュインスタンスハッシュをソートします.次に、バイナリ検索を行います.bsearch ) ハッシュキーより大きい値を持つ整数を見つけるには.
値が見つからない場合は、リスト内の最初のキャッシュを返します.リストの先頭に「ラップ」するので、これは円をエミュレートします.
キーより大きいハッシュがあれば、対応するキャッシュインスタンスを取得します.これはキーを追加する必要があるキャッシュです.
キャッシュインスタンスにキーをマップするには一貫した方法があります.

ノードの追加と削除
では、キャッシュインスタンスを追加または削除するときに何が起こるかをテストしましょう.このコードを一組のキーで実行し、マッピングがどのように見えるかを確認します.

Nodes map to {213=>"server:A", 154=>"server:B", 331=>"server:C"}

a hashes to 319
a maps to  server:C

b hashes to 65
b maps to  server:B

z hashes to 284
z maps to  server:C

hello hashes to 165
hello maps to  server:A

ご覧のように、キーは3つのキャッシュインスタンスの間で配布されます.
さあ、リストにノードを追加して、もう一度実行しましょう.

Nodes map to {213=>"server:A", 154=>"server:B", 331=>"server:C", 301=>"server:B1"}

a hashes to 319
a maps to  server:C

b hashes to 65
b maps to  server:B

z hashes to 284
z maps to  server:B1

hello hashes to 165
hello maps to  server:A

サーバを追加すると、キーの小さなサブセットだけが新しいインスタンスに再マップされます.このように、彼らが新しいキャッシュに動かされるので、キーの小さい部分集合だけはキャッシュ・ミスを経験します.これは、マッピングがどのノードがキーに「最も近い」かに依存するためです.新しいサーバーを追加すると、最も近いサーバはほとんどのキーで変更されません.したがって、ほとんどのキーのマッピングは一貫したままです.
さて、削除しましょうserver:B リストから、何が起こるかを見てください.

Nodes map to {213=>"server:A", 331=>"server:C", 301=>"server:B1"}

a hashes to 319
a maps to  server:C

b hashes to 65
b maps to  server:A

z hashes to 284
z maps to  server:B1

hello hashes to 165
hello maps to  server:A

にマップされたキーのみserver:B 再マップする必要があります.他のすべてのキーは、彼らの「最も近い」サーバが変わらないのと同じままです.
ご覧のように、一貫したハッシュ化によって、キャッシュインスタンスを簡単にスケーリングできます.キャッシュインスタンスを追加し、すべてのキーを再マップすることなく削除することができます.

As nodes are added and removed, the distribution of the keys can be uneven between the servers. In this case, we can add "fake" nodes which map to an existing server. For example, we can add another node for server A in the list. This will cause some keys to get remapped to server A and even out the distribution of keys.

結論
私はこのハッシュの戦略の実用的なアプリケーションのためのこのブログのポストにキャッシュを使用しました.ただし、複数のノード間でキーのセットを分割したい場合は、一貫したハッシュを適用できます.例えば、ピアツーピアネットワークまたはロードバランサ.一貫したハッシュについて学ぶ私の好きな部分はハッシュテーブルがどのようにより分散された方法で働くように変更されることができるかを見ていました.

コード
の完全な実装を見つけることができますconsistent hashing code on Github .

資源

Hashing in distributed systems

A Guide to Consistent Hashing

Wikipedia: Distributed Hash Table

Hash algorithm in distributed system