一致性哈希算法

如果要将多个数据分散到任意节点上，有一种方法是将数据的ID或哈希值除以保存节点的总数，然后得到保存的节点。然而，这种方法的缺点是如果节点数量发生变化，将导致整个数据的节点移动。
因此，在节点数量增减时，可以使用一种称为一致性哈希的数据布局方法，以确保最低限度的数据移动。
这种方法被用于分布式数据库，如Cassandra和Amazon Dynamo，用于确定数据的存储位置。

大致的方法

请提醒我，如果有任何不足之处。

对于数据和节点的ID，使用同一个可进行大小比较的哈希函数。

将哈希函数应用于密钥（数据的ID）。

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

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

在节点（容器）的一侧也应用相同的哈希函数

# IDが1~5のノードを用意する
node_ids = range(1, 6)

# (ノードIDのハッシュ値 ,ノードID) のリストを用意
def get_hashed_node_list(node_ids):
    """
    :type node_ids: list of int
    :rtype list 
    """
    hashed_node_list = []
    for node_id in node_ids:
        hashed_node_id = hashlib.md5(str(node_id).encode('utf-8')).hexdigest()
        hashed_node_list.append((hashed_node_id, node_id))
    # ハッシュ値でソートしておく
    return sorted(hashed_node_list, key=lambda n: n[0])

hashed_node_list = get_hashed_node_list(node_ids)

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

将节点以环形方式排布

以以下顺序确定分配数据的节点：
1. 与键具有相同哈希值的节点。
2. 在具有大于键的哈希值的节点中，选择哈希值最小的节点。
3. 选择哈希值最小的节点。

def get_node_id(hashed_key, hashed_node_list):
    """
    :type hashed_key: str
    :type hashed_slots: list of (hashed_node_id, node_id)
    :rtype int 
    """
    for hashed_node_id, node_id in hashed_node_list:

        if hashed_key == hashed_node_id:
            # 1. キーと同じハッシュ値のノード
            return node_id

        if hashed_key < hashed_node_id:
            # 2. キーより大きいハッシュ値を持つノードの中で、ハッシュ値が最小のノード
            return node_id

    # 3. どれにもヒットしなければハッシュ値が最小のノード
    return hashed_nodes[0][1]

添加数据

key_list = range(1, 21)
nodes = {i: [] for i in range(1, 6)}

hashed_node_list = get_hashed_node_list(nodes.keys())

for key in key_list:
    hashed_key = hashlib.md5(str(key).encode('utf-8')).hexdigest()
    target_node_id = get_node_id(hashed_key, hashed_node_list)
    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, 20]
5 [5, 8, 10]

如果从这里开始删除5个节点…

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

另外，如果添加节点6…

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

在整体节点数较少的阶段，一个缺点是每个节点之间出现数据偏差的现象。因此，通过在节点间放置虚拟节点的方法来尽可能均匀地分布数据，被广泛采用。

虚拟节点

我会尽快添加。

请看；参见；借鉴；看一下；引用

学习一种称为”一致性哈希”的方法，并尝试实现分布式缓存系统.