"""Консистентное хеширование: сколько ключей переезжает при смене состава.

ЗАЧЕМ ЭТОТ ФАЙЛ. «Берём хеш по модулю числа узлов» — решение, которое работает
ровно до первого изменения состава. Насколько плохо оно работает потом, обычно
описывают словами «много ключей переедет». Здесь это считается точно, и число
оказывается хуже, чем подсказывает интуиция.

ЧТО ЗДЕСЬ СЧИТАЕТСЯ. Это не симуляция и не модель: раскладка ключей по узлам —
чистое вычисление, и доля переехавших ключей получается точной. Случайности
здесь нет вовсе, кроме самих ключей, а они фиксированы зерном.

  1. Деление по модулю: сколько ключей меняет узел при добавлении одного.
  2. Кольцо: то же самое при том же изменении состава.
  3. Перекос кольца без виртуальных узлов.
  4. Что с перекосом делают виртуальные узлы и чем за это платят.
  5. Удаление узла: чьи ключи переезжают.

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

import bisect
import hashlib
import os
import random
import statistics
import sys

KEYS = 100_000
SEED = 20260905
NODES = 8


def show(title: str) -> None:
    print()
    print(title)
    print("-" * len(title))


def row(label: str, value: object) -> None:
    print(f"  {label:<46} {value}")


_CACHE: dict[str, int] = {}


def digest(value: str) -> int:
    """Хеш, не зависящий от версии интерпретатора.

    Встроенный hash() у строк рандомизируется при каждом запуске, поэтому
    прогон на нём не воспроизводился бы. Здесь берётся первые восемь байт
    SHA-1 — числа получаются одни и те же на любой машине.
    """
    cached = _CACHE.get(value)
    if cached is None:
        cached = int.from_bytes(hashlib.sha1(value.encode()).digest()[:8], "big")
        _CACHE[value] = cached
    return cached


def keys() -> list[str]:
    rng = random.Random(SEED)
    return [f"key-{rng.getrandbits(64):016x}" for _ in range(KEYS)]


# ------------------------------------------------------------------ модуль
def by_modulo(key: str, nodes: int) -> int:
    return digest(key) % nodes


# ------------------------------------------------------------------ кольцо
class Ring:
    """Кольцо: у каждого узла vnodes точек, ключ идёт к ближайшей по часовой."""

    def __init__(self, nodes: list[str], vnodes: int) -> None:
        self.vnodes = vnodes
        self.points: list[tuple[int, str]] = []
        for node in nodes:
            for i in range(vnodes):
                self.points.append((digest(f"{node}#{i}"), node))
        self.points.sort()
        self.positions = [p for p, _ in self.points]

    def owner_of_hash(self, value: int) -> str:
        index = bisect.bisect(self.positions, value)
        if index == len(self.points):
            index = 0
        return self.points[index][1]

    def owner(self, key: str) -> str:
        index = bisect.bisect(self.positions, digest(key))
        if index == len(self.points):
            index = 0
        return self.points[index][1]


def moved(before: list[str], after: list[str]) -> float:
    """Доля ключей, у которых сменился владелец."""
    changed = sum(1 for a, b in zip(before, after) if a != b)
    return changed / len(before)


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(f"{KEYS} keys, {NODES} nodes, hash is the first 8 bytes of SHA-1")

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

    show("1. MODULO SHARDING: ADDING ONE NODE MOVES ALMOST EVERYTHING")
    print(f"  {'nodes':>12} {'-> nodes':>10} {'keys moved':>13} {'ideal share':>13}")
    ratios = []
    for extra in (1, 2):
        before = [h % NODES for h in hashes]
        after = [h % (NODES + extra) for h in hashes]
        share = sum(1 for a, b in zip(before, after) if a != b) / KEYS
        ideal = extra / (NODES + extra)
        ratios.append(share / ideal)
        print(f"  {NODES:>12} {NODES + extra:>10} {share:>12.1%} {ideal:>12.1%}")
    print()
    row("times more than the minimum, +1 node", f"{ratios[0]:.1f}")
    print()
    print("  Ideal share is what has to move at minimum: the keys the new nodes")
    print("  take over. Modulo moves many times that, because the divisor")
    print("  changes for every key at once - a key's node is not a property of")
    print("  the key, it is a property of the current node count.")

    show("2. A RING MOVES ONLY WHAT IT HAS TO")
    print(f"  {'vnodes per node':>17} {'keys moved, +1 node':>21} {'ideal share':>13}")
    ideal = 1 / (NODES + 1)
    for vnodes in (1, 16, 128):
        ring_before = Ring(names, vnodes)
        ring_after = Ring(names + ["node-8"], vnodes)
        before = [ring_before.owner_of_hash(h) for h in hashes]
        after = [ring_after.owner_of_hash(h) for h in hashes]
        print(f"  {vnodes:>17} {moved(before, after):>20.1%} {ideal:>12.1%}")
    print()
    print("  The same change of membership as in block 1, and the same keys.")
    print("  What changed is only how the owner is chosen - and the traffic of")
    print("  moving data drops from most of the dataset to about a ninth.")

    show("3. WITHOUT VIRTUAL NODES THE RING IS BADLY SKEWED")
    print(f"  {'vnodes per node':>17} {'smallest share':>16} {'largest share':>15} {'max/min':>9}")
    for vnodes in (1, 16, 128, 512):
        ring = Ring(names, vnodes)
        counts: dict[str, int] = {name: 0 for name in names}
        for h in hashes:
            counts[ring.owner_of_hash(h)] += 1
        shares = sorted(c / KEYS for c in counts.values())
        print(
            f"  {vnodes:>17} {shares[0]:>15.1%} {shares[-1]:>14.1%}"
            f" {shares[-1] / shares[0]:>8.1f}x"
        )
    print()
    print("  With one point per node the ring is a random partition of a circle,")
    print("  and random partitions are uneven. Virtual nodes are the fix: many")
    print("  small arcs average out where few large ones cannot.")

    show("4. WHAT VIRTUAL NODES COST")
    print(f"  {'vnodes per node':>17} {'points on the ring':>20} {'max/min':>9}")
    for vnodes in (1, 16, 128, 512):
        ring = Ring(names, vnodes)
        counts = {name: 0 for name in names}
        for h in hashes:
            counts[ring.owner_of_hash(h)] += 1
        shares = sorted(c / KEYS for c in counts.values())
        print(f"  {vnodes:>17} {len(ring.points):>20} {shares[-1] / shares[0]:>8.1f}x")
    print()
    print("  The points are what a lookup searches and what every node must")
    print("  hold. Going from 128 to 512 quadruples the structure to buy the")
    print("  last few percent of evenness - which is the shape of the trade,")
    print("  not a recommendation.")

    show("5. REMOVING A NODE MOVES ITS KEYS AND NOBODY ELSE'S")
    ring_full = Ring(names, 128)
    ring_less = Ring(names[:-1], 128)
    before = [ring_full.owner_of_hash(h) for h in hashes]
    after = [ring_less.owner_of_hash(h) for h in hashes]
    owned_by_gone = sum(1 for owner in before if owner == names[-1]) / KEYS
    others_moved = sum(
        1 for a, b in zip(before, after) if a != names[-1] and a != b
    ) / KEYS
    row("share of keys the removed node owned", f"{owned_by_gone:.1%}")
    row("share of keys that moved in total", f"{moved(before, after):.1%}")
    row("share of OTHER nodes' keys that moved", f"{others_moved:.1%}")
    print()
    print("  Everything the removed node held changed owner, and not a single")
    print("  key of any other node did. That is the property the whole scheme")
    print("  exists for, and it is what modulo sharding does not have.")


if __name__ == "__main__":
    main()