#!/usr/bin/env python3
"""Quorums: w + r > n guarantees overlap -- and still reads stale, DDIA 2e Ch. 6.

In leaderless (Dynamo-style) replication with n replicas, a write goes to w nodes
and a read queries r nodes. If w + r > n, the write set and the read set are
forced to share at least one node (pigeonhole), so a read is guaranteed to touch a
node carrying the latest write. That is the quorum condition.

The book is careful to call this a GENERAL guarantee ("you can generally expect
every read to return the most recent value"), then lists cases where w + r > n
STILL returns stale data. This script builds a tiny quorum key-value store in pure
Python and walks three steps:

  Step 1  w + r <= n  -- the write set and read set can miss each other (stale).
  Step 2  w + r >  n  -- enumerate EVERY write/read pair; all of them overlap.
  Step 3  a sloppy quorum -- w + r > n by count, yet the sets are disjoint (stale).

No randomness: every set is chosen explicitly, so the output reproduces exactly.
"""
from itertools import combinations


class QuorumStore:
    """n replicas, each holding a single (value, version) for one key.

    Version is a monotonically increasing integer stamped by the writer; a read
    returns the value with the highest version among the nodes it queried. Higher
    version == more recent write.
    """

    def __init__(self, n, initial_value, initial_version=1):
        self.n = n
        # replica id -> (value, version)
        self.replicas = {i: (initial_value, initial_version) for i in range(n)}

    def write(self, node_ids, value, version):
        """Write (value, version) to exactly the given nodes (the w write set)."""
        for i in node_ids:
            self.replicas[i] = (value, version)

    def read(self, node_ids):
        """Query the given nodes (the r read set); return the highest-version value."""
        value, version = max((self.replicas[i] for i in node_ids), key=lambda vv: vv[1])
        return value, version


def step1_undersized_quorum():
    print("=" * 70)
    print("STEP 1  --  w + r <= n is NOT safe (w=1, r=1, n=3)")
    print("=" * 70)
    n, w, r = 3, 1, 1
    store = QuorumStore(n, initial_value="v1", initial_version=1)
    print(f"start: all {n} replicas hold ('v1', version 1)")
    print(f"w + r = {w} + {r} = {w + r}   n = {n}   -> w + r <= n\n")

    write_set = {0}
    store.write(write_set, value="v2", version=2)
    print(f"write ('v2', version 2) to w={w} node:  write set = {sorted(write_set)}")

    read_set = {1}
    value, version = store.read(read_set)
    print(f"read from r={r} node:                   read  set = {sorted(read_set)}")
    print(f"read returned: ('{value}', version {version})\n")

    overlap = write_set & read_set
    print(f"write set {sorted(write_set)} INTERSECT read set {sorted(read_set)} = "
          f"{sorted(overlap) if overlap else '(empty)'}")
    print(f"-> the read never touched the node that got 'v2', so it saw STALE 'v1'.")
    print()


def step2_full_enumeration():
    print("=" * 70)
    print("STEP 2  --  w + r > n GUARANTEES overlap (w=2, r=2, n=3)")
    print("=" * 70)
    n, w, r = 3, 2, 2
    print(f"w + r = {w} + {r} = {w + r}   n = {n}   -> w + r > n\n")
    print("enumerate EVERY way to pick a write set of 2 and a read set of 2:\n")

    nodes = range(n)
    write_sets = list(combinations(nodes, w))
    read_sets = list(combinations(nodes, r))

    total = 0
    all_overlap = True
    fresh_reads = 0
    header = f"{'write set':>12}  {'read set':>10}  {'overlap':>12}  {'read sees'}"
    print(header)
    print("-" * len(header))
    for ws in write_sets:
        # fresh copy: write 'v2' (version 2) to this write set, over a 'v1' base
        store = QuorumStore(n, initial_value="v1", initial_version=1)
        store.write(set(ws), value="v2", version=2)
        for rs in read_sets:
            overlap = set(ws) & set(rs)
            value, version = store.read(set(rs))
            total += 1
            if not overlap:
                all_overlap = False
            if version == 2:
                fresh_reads += 1
            print(f"{str(list(ws)):>12}  {str(list(rs)):>10}  "
                  f"{str(sorted(overlap)):>12}  ('{value}', v{version})")

    print("-" * len(header))
    print(f"{total} combinations: every one overlaps in >= 1 node = {all_overlap}")
    print(f"reads returning the latest ('v2', version 2): {fresh_reads}/{total}")
    print(f"-> with w + r > n, no write set and read set can be disjoint (pigeonhole).")
    print()


def step3_sloppy_quorum():
    print("=" * 70)
    print("STEP 3  --  the limitation: a SLOPPY QUORUM (w=2, r=2) still reads STALE")
    print("=" * 70)
    print("n = 3 HOME replicas for this key: {0, 1, 2}")
    print("w + r = 2 + 2 = 4 > 3 = n   -> the count says 'guaranteed overlap'\n")

    # Home replicas 0,1,2 all start at v1. Two extra nodes 3,4 exist in the
    # cluster but are NOT home replicas for this key.
    replicas = {i: ("v1", 1) for i in range(5)}
    print("a network partition cuts the WRITER off from home nodes 1 and 2;")
    print("only home node 0 is reachable. A sloppy quorum accepts the write anyway,")
    print("storing it on node 0 plus a FALLBACK node (hinted handoff) to reach w=2.\n")

    write_set = {0, 3}            # 0 is home; 3 is a fallback / hinted-handoff node
    for i in write_set:
        replicas[i] = ("v2", 2)
    print(f"write ('v2', version 2):  write set = {sorted(write_set)}   "
          f"(node 3 is a fallback, not a home replica)")

    # The reader is on the other side of the partition: it reaches the home
    # replicas but not the fallback node, and happens to read nodes 1 and 2.
    read_set = {1, 2}            # r=2 home replicas -- neither got the sloppy write
    value, version = max((replicas[i] for i in read_set), key=lambda vv: vv[1])
    print(f"read from r=2 home nodes: read  set = {sorted(read_set)}")
    print(f"read returned: ('{value}', version {version})\n")

    overlap = write_set & read_set
    print(f"write set {sorted(write_set)} INTERSECT read set {sorted(read_set)} = "
          f"{sorted(overlap) if overlap else '(empty)'}")
    print(f"-> w + r = 4 > n = 3, yet the sets are DISJOINT, so the read is STALE 'v1'.")
    print()
    print("why the pigeonhole broke: w + r > n only forces overlap when both sets are")
    print("drawn from the SAME n home nodes. A sloppy quorum lets the w writes land on")
    print("fallback nodes OUTSIDE that home set, so 'w + r > n' is counting nodes from a")
    print("larger pool -- the write and read quorums can miss each other entirely. This")
    print("is exactly the case DDIA flags: 'even with w + r > n, ... there are likely to")
    print("be edge cases in which stale values are returned' -- a sloppy quorum is one.")
    print()


def main():
    step1_undersized_quorum()
    step2_full_enumeration()
    step3_sloppy_quorum()
    print("=" * 70)
    print("takeaway: w + r > n is a GENERAL guarantee, not an absolute one. It holds")
    print("only among a fixed set of n nodes with a clear version ordering; sloppy")
    print("quorums, concurrent writes, and node failures are the edge cases where a")
    print("read can still come back stale.")
    print("=" * 70)


if __name__ == "__main__":
    main()