Skip to content

Latest commit

 

History

History
144 lines (104 loc) · 6.59 KB

5_design_consistent_hashing.md

File metadata and controls

144 lines (104 loc) · 6.59 KB
Raw

Consistent Hashing

  • 水平スケーリングの際に検討が必要な、分散リクエストに対応するためのシステム.
  • Wikipedia
ハッシュテーブルのサイズが変更された時、Kをキーの数、nをスロット数とすると、平均K/n個のキーのマッピングの変更のみでハッシュテーブルの機能を提供することのできる特殊なハッシュ法である。
それに対して、その他の多くのハッシュ法では、キーとスロット間のマッピングがモジュラ演算によって定義されているため、ハッシュテーブルのスロット数が変化するとほぼすべてのキーが再マッピングされてしまう。
分散システムの一形態である分散キャッシュなどで利用されている。

The Rehashing problem

N個のキャッシュサーバを持っていた時にロードバランスするための一般的な方法

serverIndex=hash(key)%N
  • 例えば，8Key・4サーバの場合は下図

image

図示すると以下

image

サーバが増減したときにいくつか問題が発生する. mod4⇒mod3に変化する image

image

Keyの配置が変わるので，fetch時に異常になる．再配置を試みると，ほぼ全て再配置される．

Consistent hashing

  • Wikipedia：冒頭参照

Hash space and Hash ring

  • Consistent hashingの動作を観察する．f:=SHA-1とする． X0=0,...Xn=2^160-1とする． image

これを円環にする.

image

Hash servers

  • 先ほどと同様のHash関数fを考える．
  • Hash ring上に4台のサーバを配置すると以下になる：

image

Hash keys

  • 上記のHash関数はMOD操作がないので，冒頭のRehashing problemとは異なる．
    • 4つのキャッシュkeysを円環上にマッピングすると下図：

image

Server lookup

  • Keyに対して時計回りにサーバ探索を行う．
    • Key0はServer0に蓄積される．
    • Key1はServer1に蓄積される．
    • ete

image

Add a server

  • 新しいサーバが配置されたときの挙動は？
  • 例
    • サーバ4が追加されたとき，Key0のみが再配置される．
    • Key1,2,3は同じサーバに居続ける
    • 時計回りに見て最近接なサーバはどれか？

image

Remove a server

  • サーバ除去時の挙動は？
  • サーバ1が除去されたとき，Key1は時計回りにおける次の位置「サーバ2」に配置される
    • 残りのKeyはそのまま

image

Two issues in the basic approach

  • ここまでのまとめ
    • MITにより開発された
    • 基本的なステップ
      • 円環上にあるMAPサーバ・Keyは決められたHash関数を使用する
      • 各Keyがどのサーバに配置されているか？は以下の手順で見つけられる
        • Keyを始点に時計回りに探索し，最初に見つかったサーバ
  • 2つの問題がある
    • 円環上のサーバが増減することを考えると，すべての区間を等距離にすることは不可能
      • 区間＝Hash space
      • 区間をとても小さいorとても大きい　は可能

image

  • 配置したKeyが偏る可能性がある
    • Server2には多くのKeyがあるが，他サーバにはKeyがない

image

Virtual nodes または replica という技術で解決する.

Virtual nodes

  • サーバを分割し，そこに仮想ノードを整備する．
  • 3つに分割した例

image

Key0は時計回りに探索したとき，s1_1に衝突する．これはサーバ1なので，Key0はサーバ1に格納される．

image

  • Virtual nodesを設定することで，Keyの分散具合が均等になる．
  • トレードオフが存在する
    • Virtual nodeを増やすほうが標準偏差が小さくなり，安定
    • Virtual nodeを増やすにつれSpaceが必要になり，コスト増

Find affected keys

  • サーバ増減によって行われるキーの再配置はどこまで影響するか？
  • サーバ4を円環上に追加した例
    • Server4から円環を反時計回り方向に見ると，Server3が最初に見つかる．この区間[S3, S4]が影響範囲である．

image

  • サーバ1を除去した例
    • 同様に考えると，影響区間は[S0, S1]である．

image

Step4:まとめ

Consistent Hashingの利点

  • サーバ増減に伴うKeyの再配置を最小限にする
  • データの再配置が効率的なので，水平スケーリングに適している
  • Mitigate hotspot key problem．特定のサーバへの過度なアクセスはサーバのオーバーロードを引き起こす．
    • 例：歌手Mapping，同一ノードにKaty PerryやLady Gagaがいる　など
    • Consistent Hashingによりこれらに耐えられる

使用されているサービス

  • Amazon Dynamo DB
  • Apache Cassandra
  • Discord chat APP
  • Akamai CDN
  • Maglev network load balancer

Extra