Consistent Hashing & Partitioning

# 1. Keys remapped: K/(N+K) = 5/(10+5) = 33%
# About 33% of keys will map to new nodes (cache miss)

# 2. Warm-up strategy:
def warm_up_new_nodes(old_ring, new_ring, keys_sample):
    for key in keys_sample:
        old_node = old_ring.get_node(key)
        new_node = new_ring.get_node(key)
        if old_node != new_node:
            # Copy data from old node to new node
            value = old_node.get(key)
            if value:
                new_node.set(key, value)

# 3. Virtual nodes: 100-200 per physical node
# With 150 vnodes and 15 physical nodes = 2250 points on ring
# Standard deviation of load: ~5% (good enough)

def get_replica_nodes(ring, key, num_replicas=3):
    """Get N distinct physical nodes for replication."""
    hash_val = ring._hash(key)
    idx = bisect_right(ring.sorted_keys, hash_val)
    replicas = []
    seen_physical = set()

    for _ in range(len(ring.sorted_keys)):
        pos = idx % len(ring.sorted_keys)
        node = ring.ring[ring.sorted_keys[pos]]
        if node not in seen_physical:
            replicas.append(node)
            seen_physical.add(node)
        if len(replicas) == num_replicas:
            break
        idx += 1

    return replicas

# Read repair: compare versions from replicas
def read_with_repair(key, replicas):
    responses = [node.get(key) for node in replicas]
    latest = max(responses, key=lambda r: r.version)
    for node, resp in zip(replicas, responses):
        if resp.version < latest.version:
            node.put(key, latest)  # Repair stale replica
    return latest.value

import random

NUM_READ_SHARDS = 10

def write_hot_key(ring, key, value):
    """Write to primary + fan out to read shards."""
    primary = ring.get_node(key)
    primary.put(key, value)
    # Async fan-out to read shards
    for i in range(NUM_READ_SHARDS):
        shard_key = f"{key}:shard_{i}"
        node = ring.get_node(shard_key)
        node.put(shard_key, value)

def read_hot_key(ring, key):
    """Read from a random shard to distribute load."""
    shard = random.randint(0, NUM_READ_SHARDS - 1)
    shard_key = f"{key}:shard_{shard}"
    node = ring.get_node(shard_key)
    return node.get(shard_key)