lab11 — consistent hashing и bloom filter¶

Две структуры, которые редко проходят в академическом DSA, но без которых не понять, как устроены распределённые системы: consistent hashing (хеш-кольцо) и bloom filter (вероятностная проверка принадлежности). Обе строятся вокруг хеш-функции из lab05, но решают «системные», а не «словарные» задачи: куда положить ключ, когда серверов много, и как не ходить на диск за тем, чего там точно нет.

Хеш-функция реализована вручную прямо в lab11.py (полиномиальный хеш с солью), длина списков считается собственной array_length из common.

Хеш-функция с солью¶

Полиномиальный хеш строки (база 31, схема Горнера), но с двумя отличиями от lab05: результат держим в 64-битном кольце (& _MASK64), а в затравку подмешиваем соль (salt).

_MASK64 = (1 << 64) - 1

def hash_str(key: str, salt: int = 0) -> int:
    h = (salt * 0x9E3779B1 + 1) & _MASK64   # затравка зависит от соли
    for ch in key:
        h = (h * 31 + ord(ch)) & _MASK64    # держим хеш в [0, 2^64)
    return h

Зачем 64-битное кольцо: нам нужно конечное пространство хешей фиксированного размера, по которому раскладываются и ноды, и ключи. Зачем соль: из одной функции получаем семейство независимых хешей. Это нужно дважды — для k хеш-функций bloom-фильтра и для разнесения виртуальных нод по кольцу.

Почему `hash % N` ломается при добавлении ноды¶

Самый частый способ «размазать» ключи по N серверам — node = hash(key) % N. Просто и быстро. Проблема вылезает, когда N меняется.

def naive_node(key, num_nodes: int) -> int:
    return hash_key(key) % num_nodes        # шард = остаток по числу нод

Остаток зависит от делителя. Поменяли число нод 4 -> 5 — поменялся делитель — поменялся остаток почти у всех ключей. Конкретно: при росте N -> N+1 ключ остаётся на месте, только если hash % N == hash % (N+1), а это редкость. В демо на 10000 ключах при 4 -> 5 переезжает порядка 80% ключей.

Что значит «переезжает ключ» в проде: данные надо физически перенести на другой сервер, а до переноса кэш холодный и запросы идут не туда. Добавление одной ноды вызывает ребаланс почти всего кластера — это и есть «шардирование ломается при добавлении ноды».

Consistent hashing: хеш-кольцо¶

Идея: отобразить и ноды, и ключи в одно пространство хешей [0, 2^64), свёрнутое в кольцо (после максимума идёт минимум). Ключ обслуживает первая нода по часовой стрелке от позиции ключа.

def get_node(self, key):
    h = hash_key(key)
    # бинарный поиск первой точки с position >= h
    lo, hi = 0, array_length(self._ring)
    while lo < hi:
        mid = (lo + hi) // 2
        if self._ring[mid][0] < h:
            lo = mid + 1
        else:
            hi = mid
    if lo == array_length(self._ring):
        lo = 0                              # ключ «правее» всех -> замыкаем кольцо
    return self._ring[lo][1]

_ring держим отсортированным по позиции списком пар [position, node], поэтому get_node — это бинарный поиск, O(log V), где V — число точек на кольце.

Почему переезжает мало. Когда добавляем ноду, она встаёт в одну точку кольца и «отрезает» себе только тот сегмент, что лежит между ней и предыдущей точкой против часовой стрелки. Ключи этого сегмента переезжают на новую ноду, все остальные остаются на месте. Доля переехавших ≈ 1/(N+1) вместо ≈ 1 у hash % N.

def ring_rebalanced_fraction(keys, nodes, new_node, replicas=100):
    before = ConsistentHashRing(replicas); [before.add_node(n) for n in nodes]
    after  = ConsistentHashRing(replicas); [after.add_node(n) for n in nodes]
    after.add_node(new_node)
    moved = sum(1 for k in keys if before.get_node(k) != after.get_node(k))
    return moved / array_length(keys)

На 10000 ключах: hash % N ≈ 80%, кольцо ≈ 20% (1/5). Тот же эффект при удалении ноды: переезжают только её ключи на соседа.

Виртуальные ноды (replicas)¶

У «голого» кольца проблема: с малым числом точек ноды садятся на кольцо неравномерно, и одной достаётся вдвое больше ключей, чем другой. Решение — виртуальные ноды: каждую физическую ноду кладём на кольцо replicas раз, подмешивая в имя номер реплики.

def _vnode_position(self, node, replica):
    return hash_key(f"{node}#{replica}", salt=replica)   # replicas точек на ноду

Чем больше виртуальных нод, тем кучнее точки покрывают кольцо и тем ровнее ключи делятся между физическими нодами. В демо перекос (max-min) падает с десятков процентов при replicas=1 до единиц процентов при replicas=100. Бонус: при добавлении ноды её доля «отъедается» понемногу у всех соседей, а не сваливается на одного.

Параметр	Малый replicas	Большой replicas
Равномерность раскладки	плохая (перекос)	хорошая
Размер `_ring` (память)	мал	велик (N·replicas)
Стоимость `add/remove_node`	мала	выше (replicas вставок)

Bloom filter: вероятностная принадлежность¶

Задача: быстро отвечать «есть ли элемент в множестве», когда само множество слишком большое, чтобы держать его целиком (в памяти/быстро). Bloom filter отвечает вероятностно и занимает константную память.

Гарантии асимметричны и в этом вся соль:

False — элемента точно нет (ложноотрицательных НЕ бывает);
True — элемент возможно есть (бывают ложноположительные).

Устройство: битовый массив на size бит и k хеш-функций. Биты пакуем руками в список целых по 64 бита (без bytearray/set). k хеш-функций получаем из одной — с разными солями.

def add(self, item):
    for pos in self._positions(item):       # k позиций = hash(item, salt=0..k-1) % size
        self._set_bit(pos)                  # ставим все k бит

def contains(self, item):
    for pos in self._positions(item):
        if not self._get_bit(pos):
            return False                    # хоть один бит не стоит -> точно НЕ добавляли
    return True                             # все k бит стоят -> ВОЗМОЖНО есть

Почему нет ложноотрицательных. add выставляет биты и никогда их не гасит. Если элемент добавляли, все его k бит стоят навсегда — contains вернёт True.

Откуда ложноположительные. Биты разных элементов перекрываются. Может случиться, что все k бит чужого элемента уже выставлены другими — тогда contains соврёт True. Вероятность растёт с заполнением: FPR ≈ (1 - e^(-k·n/m))^k, где m = size, n — число добавленных, k — число хешей. Чем больше элементов на тот же массив — тем выше доля ложных срабатываний (в демо это видно по росту estimated_false_positive_rate).

Сложность — итог¶

Операция	Структура	Сложность	Память
`get_node`	хеш-кольцо	O(log V), V = N·replicas	O(N·replicas)
`add_node` / `remove_node`	хеш-кольцо	O(V) (вставка/фильтрация точек)	—
`add` / `contains`	bloom filter	O(k)	O(m) бит, не зависит от n

У bloom-фильтра ключевое — память O(m) и не зависит от числа элементов n: добавив миллион элементов, мы не выросли в размере, только подняли FPR. Это и есть его суперсила перед set/хеш-таблицей, где память растёт с n.

Где это в проде¶

Шардирование БД и балансировка. Consistent hashing — как раскладывают ключи Cassandra, DynamoDB, Riak, как шардит данные client-side Redis Cluster и как распределяют запросы балансировщики (Envoy/Nginx consistent_hash, memcached-клиенты типа ketama). Главная причина — ровно та, что в демо: при наивном hash % N добавление/падение одной ноды ребалансит почти весь кластер (холодные кэши, лавина переносов), а кольцо двигает только ≈ 1/(N+1) ключей. Виртуальные ноды (vnodes в Cassandra) выравнивают нагрузку и сглаживают переезд при изменении состава кластера.
Bloom filter — фильтр «точно нет» перед дорогим обращением. Ставится перед диском/сетью, чтобы не платить за заведомо пустой запрос. Cassandra и HBase держат bloom-фильтр на каждый SSTable/HFile: прежде чем читать файл с диска ради ключа, спрашивают фильтр — False значит ключа в этом файле точно нет, чтение пропускается (огромная экономия I/O при чтении отсутствующих ключей). CDN и кэши используют bloom, чтобы не ходить на origin за объектом, которого нет. По той же логике работают «one-hit-wonder» фильтры (не класть в кэш то, что запросили впервые) и проверки «видели ли мы уже этот элемент» в потоковой обработке.