Help us understand the problem. What is going on with this article?

コンシステントハッシング

コンシステントハッシング法

複数のデータを任意のノードに分散させる場合、データのIDやそのハッシュ値を保存先ノード総数で割るという方法があるが、この方法はノード数自体の変更があった場合にデータ全体のノード間移動が発生してしまうという欠点がある。
そこでノード数の増減時に、必要最低限のデータの移動で済むようなデータの配置方法の一つとしてコンシステントハッシュ法がある。
CassandraやAmazonDynamoのような分散データベースにおいて、データの保存先の決定に使われている。

ハッシュ関数を適応したノードとデータをリング状に時計回りに配置し、各ノードは自身と同じかそれより手前に配置されたデータを担当する。
下の図でいうとデータd1-d3はノードn3に保存される。
スクリーンショット 2019-07-09 午後6.29.21.png

ざっくりとしたアプローチ

※不足点あればご指摘ください。

データとノードのIDに、大小比較可能な同じハッシュ関数を適応する。

キー(データのID)にハッシュ関数をかける

# 今回はハッシュ関数にmd5を使用
import hashlib

hashed_key = hashlib.md5(str(key)).hexdigest()

ノード(容れ物)側にも同じハッシュ関数をかける

# IDが1~5のノードを用意する
node_dict = {node_id:[] for node_id in range(1, 6)}

# (ノードIDのハッシュ値 ,ノードID) のリストを用意
hashed_nodes = sorted(
    [(hashlib.md5(str(node_id)).hexdigest(), node_id) for node_id in node_dict.keys()]
)

# ノードIDとハッシュ値の対応は以下のようになる
# 1 => c4ca4238a0b923820dcc509a6f75849b
# 2 => c81e728d9d4c2f636f067f89cc14862c
# 3 => eccbc87e4b5ce2fe28308fd9f2a7baf3
# 4 => e4da3b7fbbce2345d7772b0674a318d5
# 5 => e4da3b7fbbce2345d7772b0674a318d5

ノードをリング状に配置する

以下の順番でデータを割り当てるノードを決定する
1. キーと同じハッシュ値のノード
2. キーより大きいハッシュ値を持つノードの中で、ハッシュ値が最小のノード
3. ハッシュ値が最小のノード

def get_node_id(hashed_key, hashed_nodes):
    """
    :type hashed_key: str
    :type hashed_slots: list of (hashed_node_id, node_id)
    :rtype int 
    """
    nodes = [node for node in hashed_nodes if node[0] == hashed_key]
    if nodes:
        return nodes[0][1]

    nodes = [node for node in hashed_nodes if hashed_key < node[0]]
    if nodes:
        return nodes[0][1]

    return hashed_nodes[0][1]

データを追加する

target_node_id = get_node_id(hashed_key, hashed_nodes)
nodes[target_node_id].append(key)

仮にデータのキーが1~20のシーケンシャルなIDとすると、各ノードへの割当ては以下のようになる

>> for k, v in nodes.items():
>>     print '{} {}'.format(k, v)

1 [1, 12, 14]
2 [2, 13, 16]
3 [3]
4 [4, 6, 7, 9, 11, 15, 17, 18, 19]
5 [5, 8, 10]

スクリーンショット 2019-07-20 午後7.40.49.png

ここから5のノードを抜くと...

1 [1, 12, 14]
2 [2, 13, 16]
3 [3, 5, 8, 10]
4 [4, 6, 7, 9, 11, 15, 17, 18, 19]

ノード5のデータ(5, 8, 10)のみが隣のノード3に移動する
スクリーンショット 2019-07-09 午後6.45.47.png

また、ノード6を追加すると...

1 [1, 12, 14]
2 [2, 13, 16]
3 [3]
4 [4, 7, 9, 11, 15, 17, 18, 19]
5 [5, 8, 10]
6 [6]

ノード4のデータ(6)がノード6に移動する。
スクリーンショット 2019-07-09 午後6.53.07.png

欠点として、全体のノード数が少ない段階では各ノードにデータの偏りが発生するという点がある。
そのため、仮想ノードを間に配置することでデータをなるべく均等に配置する方法がセットで使用される。

仮想ノード

そのうち追記します。

参考

Consistent hash
コンシステント・ハッシュ法を学びつつ分散キャッシュを実装してみる

hharu
突然記事を書き換えます
gumi
Python、Erlang、Elixir などちょっと変わった技術でゲームをつくったりする会社。プログラマだけじゃなく、企画、デザイン、イラストなど開発全般揃ってます。
http://gu3.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした