Предисловие: будучи большим поклонником каламбуров разработчиков и «Властелина колец», я просто не мог удержаться от того, чтобы придать этой статье тон. Если вы чувствуете, что вам нужна нормальная, не веселая, человеческая версия. Дайте мне знать.

В сфере распределенных систем существует волшебная концепция, известная как согласованное хэширование. Точно так же, как Единое кольцо в саге «Властелин колец» может управлять всеми другими кольцами, согласованное хэширование позволяет сбалансировать нагрузку и свести к минимуму повторное хеширование при изменении размера хэш-таблицы. Эта захватывающая история, полная интриг и чудес, отправит вас в путешествие по глубинам этой концепции и приведет вас к величайшему сокровищу: реализации кода Python.

Сказка начинается: что такое хеширование?

В мире информатики существует мощное заклинание под названием «хеширование». Целью этого заклинания является преобразование любого фрагмента данных в уникальное значение фиксированного размера. Это уникальное значение называется «хэш-код». Это преобразование выполняется мистической сущностью, известной как «хэш-функция».

Поворотный момент: проблема с традиционным хешированием

Однако, как и в любой хорошей сказке, здесь есть поворот. В царстве распределенных систем традиционное хеширование представляет собой проблему. Когда добавляется новый узел (необходимо добавить больше серверов для распределения нагрузки) или существующий узел удаляется из системы (осколок или сервер выходит из строя или дает сбой), необходимо переназначить значительное количество ключей, что приводит к тому, что известный как «перефразирование». Это чрезвычайно дорогая операция, отнимающая время и ресурсы и вызывающая нестабильность системы.

Появление героя: согласованное хеширование

Когда кажется, что всякая надежда потеряна, из тени появляется герой: последовательное хэширование. В отличие от традиционного хеширования, согласованное хеширование только переназначает ключи, которые сопоставляются с добавленными или удаленными узлами, тем самым значительно снижая стоимость изменений узла.

Согласованное хеширование работает в волшебном мире, известном как «кольцо». Каждый узел и ключ в системе хэшируются в позицию на этом кольце. Когда в системе необходимо найти ключ, кольцо перемещается по часовой стрелке до тех пор, пока не встретится первый узел, и именно там хранится ключ.

Когда узел добавляется, он помещается в кольцо, и необходимо переназначить только ключи между ним и его предшествующим узлом. Точно так же при удалении узла необходимо переназначить только его ключи на следующий узел в кольце.

Обнаруженное сокровище: реализация кода Python

Теперь, когда история рассказана, давайте перейдем к сути вопроса: реализации последовательного хэширования в коде Python. Наш квест проведет нас через создание двух классов: Node и ConsistentHashRing.

import hashlib
import bisect

class Node:
    def __init__(self, id, ip):
        self.id = hashlib.sha1(ip.encode('utf-8')).hexdigest()
        self.ip = ip

class ConsistentHashRing:
    def __init__(self):
        self.nodes = dict()
        self.keys = []

    def add_node(self, node):
        self.nodes[node.id] = node
        self.keys.append(node.id)
        self.keys.sort()

    def remove_node(self, node):
        del self.nodes[node.id]
        self.keys.remove(node.id)

    def get_node(self, key):
        if not self.nodes:
            return None

        key = hashlib.sha1(key.encode('utf-8')).hexdigest()
        node_id = self.keys[bisect.bisect(self.keys, key) % len(self.keys)]
        return self.nodes[node_id]

if __name__ == "__main__":
    ring = ConsistentHashRing()

    # Adding nodes to the ring
    for i in range(1, 6):
        node = Node(i, f'192.168.0.{i}')
        ring.add_node(node)
        print(f'Added node with IP: {node.ip} and ID: {node.id}')

    # Getting the node for a specific key
    key = 'my_precious_key'
    node = ring.get_node(key)
    print(f'\nThe key "{key}" is mapped to the node with IP: {node.ip} and ID: {node.id}')

    # Removing a node from the ring
    node_to_remove = Node(3, '192.168.0.3')
    ring.remove_node(node_to_remove)
    print(f'\nRemoved node with IP: {node_to_remove.ip} and ID: {node_to_remove.id}')

    # Getting the node for the same key after node removal
    node = ring.get_node(key)
    print(f'\nThe key "{key}" is now mapped to the node with IP: {node.ip} and ID: {node.id}')

Небольшое уточнение приведенного выше фрагмента.
В этом коде каждый Node инициализируется IP-адресом, который хэшируется для создания уникального идентификатора. ConsistentHashRing поддерживает словарь узлов и отсортированный список идентификаторов узлов. Когда узел добавляется или удаляется, словарь узлов и список идентификаторов обновляются. Метод get_node хэширует ключ и использует его для поиска подходящего узла для хранения или извлечения значения ключа. Функция bisect используется для поиска правильного узла, обеспечивая эффективность операции поиска с использованием двоичного поиска.

Каждый узел (осколок или что-то другое) представлен как экземпляр класса Node, а хэш-кольцо представлен как экземпляр класса ConsistentHashRing.

Заключение: сказка заканчивается, но путешествие продолжается

Итак, дорогой читатель, наша повесть подошла к концу. Подобно Братству во «Властелине колец», мы изучили концепцию последовательного хэширования и обнаружили его способность решать проблему повторного хэширования в распределенных системах. Мы также видели, как эта концепция может быть реализована в коде Python с использованием принципов объектно-ориентированного программирования. Но помните, что и в Средиземье, и в области компьютерных наук путешествие никогда не заканчивается. Всегда есть новые концепции для изучения, новые проблемы для решения и новый код для написания. Пусть ваше путешествие продолжит быть путешествием открытий и роста.

Один хэш, чтобы править ими всеми, один хэш, чтобы найти их, Один хеш, чтобы привести их всех и в сети связать их