Deep Engineering

MEASUREMENT

bench/hashring/practice.py

The script that produced the numbers in the article, and the record of the run. The file is read from the repository at build time — this is the code that was run, not a copy of it.

Cited in
/en/interview/sre/consistent-hashing
How to run it
python3 bench/hashring/ring.py     > bench/hashring/runs/ring.txt
python3 bench/hashring/practice.py > bench/hashring/runs/practice.txt

The run below is recorded in Russian. It is a lab record, kept in the language it was written in; the numbers, the tables and the code read the same either way.

Record of the run

Замеры для урока «Консистентное хеширование»

Файл Что делает
ring.py пять вычислений: сколько ключей меняет узел при добавлении одного узла к делению по модулю; то же самое на кольце; перекос кольца без виртуальных узлов; чем за виртуальные узлы платят; и чьи ключи переезжают при удалении узла
practice.py ответы к задачам урока: доля переехавших ключей при делении по модулю и на кольце, доля затронутых чужих ключей и перекос кольца без виртуальных узлов

Запуск из корня репозитория:

python3 bench/hashring/ring.py     > bench/hashring/runs/ring.txt
python3 bench/hashring/practice.py > bench/hashring/runs/practice.txt

Это вычисление, а не модель

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

Хеш взят как первые восемь байт SHA-1, а не встроенный hash(): у строк тот рандомизируется при каждом запуске, и прогон не воспроизводился бы.

Что воспроизводимо

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

Перекос зависит от того, какие именно точки легли на кольцо, то есть от имён узлов. С другими именами кратность будет другой — воспроизводится не число 90,5, а то, что при одной точке на узел перекос измеряется десятками раз, а при сотне точек — единицами.

Требования к среде

Только CPython, ничего внешнего. Прогон занимает около минуты.

Числа сняты на CPython 3.11.15, 100 000 ключей, 8 узлов.

Script

66 lines
"""Практика к уроку про консистентное хеширование: три ответа и один перекос.

ЗАЧЕМ ОТДЕЛЬНЫЙ ФАЙЛ. Задачи урока проверяются сборкой
(scripts/validate-practice.mjs): показанный читателю код обязан построчно быть
в скрипте, верный вариант — дословно встречаться в записи прогона, а
заявленное число — печататься самой программой.

ЧТО ЗДЕСЬ ПРОВЕРЯЕТСЯ. Два места, где интуиция ошибается. Первое: насколько
именно хуже деление по модулю и переезжают ли при удалении узла чужие ключи.
Второе: во сколько раз самый нагруженный узел кольца тяжелее самого лёгкого,
если виртуальных узлов нет.

Кольцо и хеш берутся из `ring.py`, чтобы задача и разбор урока стояли на одном
и том же коде.

ЗАПУСК: python3 bench/hashring/practice.py
Вывод: runs/practice.txt
"""

import os
import sys

sys.path.insert(0, os.path.dirname(os.path.abspath(__file__)))

from ring import KEYS, NODES, Ring, digest, keys  # noqa: E402


def main() -> None:
    print(f"Python {sys.version.split()[0]} · Linux {os.uname().release}")
    print("exact computation, not a simulation: only the keys are random")
    print()

    hashes = [digest(k) for k in keys()]
    names = [f"node-{i}" for i in range(NODES)]

    # --- Часть 1: три ответа о поведении --------------------------------
    modulo = sum(1 for h in hashes if h % NODES != h % (NODES + 1)) / KEYS
    full, less = Ring(names, 128), Ring(names[:-1], 128)
    before = [full.owner_of_hash(h) for h in hashes]
    after = [less.owner_of_hash(h) for h in hashes]
    ring_moved = sum(1 for a, b in zip(before, after) if a != b) / KEYS
    others = sum(1 for a, b in zip(before, after) if a != names[-1] and a != b) / KEYS
    print(f"{modulo:.1%}")
    print(f"{ring_moved:.1%}")
    print(f"{others:.1%}")

    # --- Часть 2: перекос кольца без виртуальных узлов --------------------
    #
    # ПОЧЕМУ КРАТНОСТЬ ПЕЧАТАЕТ ПРОГРАММА. Деление в уме на стороне редакции —
    # ровно тот шаг, где вкрадывается ошибка, которую потом нечем поймать.
    plain = Ring(names, 1)
    counts = {name: 0 for name in names}
    for h in hashes:
        counts[plain.owner_of_hash(h)] += 1
    shares = sorted(c / KEYS for c in counts.values())
    print()
    print(f"nodes on the ring                    {NODES}")
    print(f"points per node                      1")
    print(f"smallest share of keys               {shares[0]:.1%}")
    print(f"largest share of keys                {shares[-1]:.1%}")
    print(f"largest over smallest                {shares[-1] / shares[0]:.1f}")


if __name__ == "__main__":
    main()