#!/usr/bin/env python3
"""DDIA Ch. 7 (Sharding) -- why Cassandra uses 16 vnodes/node and ScyllaDB 256.

Consistent hashing with a SINGLE random range boundary per node (the original
scheme) leaves the load lumpy: with 10 nodes each owning one random slice of the
hash ring, the busiest node can own far more than its 1/10 fair share. Give each
node V small random ranges instead ("virtual nodes") and the lumps average out.

This measures the load imbalance -- max_node_load / mean_node_load -- and the
coefficient of variation (std/mean of node loads) as V grows: 1, 2, 4, 16, 64,
256. Keys are assumed uniform over the hash space, so a node's LOAD is just the
total WIDTH of the hash ranges it owns.

The prediction the reader gets wrong: "random boundaries -> roughly even load."
At V=1 it is badly uneven. The CV shrinks like 1/sqrt(V) -- that is the whole
result, the law of large numbers averaging V independent range-widths per node.

Deterministic: fixed seed list, averaged over trials, so numbers reproduce
byte-for-byte every run. Python 3 stdlib only.
"""

import random

NODES = 10
HASH_SPACE = 2 ** 32
V_VALUES = [1, 2, 4, 16, 64, 256]
SEEDS = list(range(20))  # 20 fixed trials, averaged to tame single-sample noise


def ring_ranges(v, seed):
    """Place NODES*v random boundaries on the ring [0, HASH_SPACE); return the
    NODES*v contiguous range widths, sorted around the ring (last wraps to first)."""
    rng = random.Random(seed)
    n_points = NODES * v
    points = sorted(rng.randrange(HASH_SPACE) for _ in range(n_points))
    widths = []
    for i in range(n_points):
        lo = points[i]
        hi = points[(i + 1) % n_points]
        widths.append((hi - lo) % HASH_SPACE)
    return widths


def node_loads(v, seed):
    """Assign the NODES*v sorted ranges round-robin to NODES nodes; return each
    node's load (sum of its v range widths)."""
    widths = ring_ranges(v, seed)
    loads = [0] * NODES
    for i, w in enumerate(widths):
        loads[i % NODES] += w
    return loads


def stats(loads):
    n = len(loads)
    mean = sum(loads) / n
    variance = sum((x - mean) ** 2 for x in loads) / n
    std = variance ** 0.5
    imbalance = max(loads) / mean
    cv = std / mean
    return imbalance, cv


def main():
    print(f"{NODES} nodes on a 2**32 hash ring; keys uniform, so load = width owned.")
    print(f"Each node owns V random ranges (V=1 is the original single-boundary scheme).")
    print(f"Averaged over {len(SEEDS)} fixed seeds. Fair share per node = "
          f"{100 / NODES:.0f}% of the ring.")
    print()
    print(f"  {'V':>4} | {'imbalance max/mean':>18} | {'CV (std/mean)':>13} | {'1/sqrt(V)':>9}")
    print(f"  {'-'*4}-+-{'-'*18}-+-{'-'*13}-+-{'-'*9}")
    for v in V_VALUES:
        imb_sum = 0.0
        cv_sum = 0.0
        for seed in SEEDS:
            imb, cv = stats(node_loads(v, seed))
            imb_sum += imb
            cv_sum += cv
        imb_avg = imb_sum / len(SEEDS)
        cv_avg = cv_sum / len(SEEDS)
        inv_sqrt = 1.0 / (v ** 0.5)
        print(f"  {v:>4} | {imb_avg:>18.3f} | {cv_avg:>13.3f} | {inv_sqrt:>9.3f}")
    print()
    print("Read it down the last two columns: CV tracks 1/sqrt(V) closely.")
    print("V=1 busiest node ~ its imbalance above the fair share; V=16 (Cassandra)")
    print("CV ~ 25%; V=256 (ScyllaDB) CV ~ 6%. More, smaller ranges -> flatter load.")


if __name__ == "__main__":
    main()