#!/usr/bin/env python3
"""DDIA Ch. 7 (Sharding) -- consistent hashing vs. hash % N.

Grow a cluster from 10 nodes to 11 and count how many of 200,000 keys have to
move, and -- the real question -- where the movers land.

Rendezvous (highest-random-weight) hashing is one concrete way to get the
"consistent hashing" property the book describes: adding a node moves only the
minimal share of keys, and every moved key goes to the NEW node. Contrast it
with the textbook-naive `hash % N`, which reshuffles almost everything and sends
huge numbers of keys hopping between two OLD nodes that never changed.

Deterministic: node ownership is decided by md5, never Python's per-process
randomized hash(), so the numbers below reproduce byte-for-byte every run.
Stdlib only.
"""

import hashlib

N_KEYS = 200_000
KEYS = [f"key{i}" for i in range(N_KEYS)]


def h(s):
    """Stable, process-independent 128-bit hash of a string as an int."""
    return int(hashlib.md5(s.encode()).hexdigest(), 16)


# --- Rendezvous (highest-random-weight) hashing ------------------------------
# The owner of a key is the node that maximizes md5(f"{key}:{node}").
def rendezvous_owner(key, n_nodes):
    return max(range(n_nodes), key=lambda node: h(f"{key}:{node}"))


# --- Naive modulo hashing ----------------------------------------------------
def mod_owner(key, n_nodes):
    return h(key) % n_nodes


def measure(owner_fn, n_before, n_after, new_node_id):
    """Return (moved, movers_to_old, movers_to_new) growing n_before -> n_after."""
    moved = 0
    movers_to_old = 0
    movers_to_new = 0
    for key in KEYS:
        before = owner_fn(key, n_before)
        after = owner_fn(key, n_after)
        if before != after:
            moved += 1
            if after == new_node_id:
                movers_to_new += 1
            else:
                movers_to_old += 1
    return moved, movers_to_old, movers_to_new


def pct(n):
    return f"{100 * n / N_KEYS:.2f}%"


def main():
    N_BEFORE, N_AFTER = 10, 11
    NEW_NODE = 10  # node ids are 0..9 before; adding node id 10 makes 0..10

    print(f"Grow the cluster from {N_BEFORE} nodes to {N_AFTER}, "
          f"re-placing {N_KEYS:,} keys.")
    print(f"    old nodes = ids 0..{N_BEFORE - 1}    new node = id {NEW_NODE}")
    print()

    r_moved, r_old, r_new = measure(rendezvous_owner, N_BEFORE, N_AFTER, NEW_NODE)
    print("RENDEZVOUS (consistent) hashing -- owner = argmax_node md5(key:node):")
    print(f"    keys moved 10 -> 11 : {r_moved:>7,}  ({pct(r_moved)})")
    print(f"    of those, movers landing on an OLD node (id <= 9) : {r_old:>7,}")
    print(f"    of those, movers landing on the NEW node (id 10)  : {r_new:>7,}")
    print(f"    -> every one of the {r_moved:,} moved keys went to the new node; "
          f"{r_old} hopped between old nodes.")
    print()

    m_moved, m_old, m_new = measure(mod_owner, N_BEFORE, N_AFTER, NEW_NODE)
    print("NAIVE hash % N hashing -- owner = md5(key) % N:")
    print(f"    keys moved 10 -> 11 : {m_moved:>7,}  ({pct(m_moved)})")
    print(f"    of those, movers landing on an OLD node (id <= 9) : {m_old:>7,}")
    print(f"    of those, movers landing on the NEW node (id 10)  : {m_new:>7,}")
    print(f"    -> {m_old:,} moved keys hopped between old nodes that never changed.")
    print()

    print("Same keys, same new node. Rendezvous moved "
          f"{pct(r_moved)} of keys, {r_old} of them uselessly;")
    print(f"hash % N moved {pct(m_moved)}, {m_old:,} of them uselessly.")


if __name__ == "__main__":
    main()