#!/usr/bin/env python3 """Uniqueness needs a total order; async multi-leader grants the same username twice, DDIA 2e Ch. 13. Two users concurrently claim the username 'alice'. A UNIQUE(username) constraint says exactly ONE of them may own it. The surprise is where the constraint holds. Model the store as asynchronous multi-leader replication -- two independent leaders L1 and L2, each with its own local `taken` set, no shared state until a later async merge. Both claims arrive at the same instant, one per leader. Each leader checks its LOCAL table, finds 'alice' free, and grants. BOTH succeed. The constraint is violated the moment two leaders decided independently; the conflict is only discovered at merge time -- too late, two users were already told they own 'alice'. Even a compare-and-set inside each leader does not help: the leaders don't share the register it would test. Now route every claim for a username through ONE totally-ordered log partition (partition by hash of username), consumed single-threaded. The consumer sees a DEFINITE first writer: it grants the first appended claim and rejects every later one. Exactly one owner. That single ordered log IS the consensus uniqueness needs. Pure standard library, concurrency modeled explicitly -> deterministic, reproducible. """ import hashlib USERNAME = "alice" # Two users race for the same name. (request_id, user_label) -- distinct people. CLAIMS = [("req-1", "user-1"), ("req-2", "user-2")] # --- Model 1: asynchronous multi-leader replication ------------------------- # # Two leaders, each authoritative for writes it receives, each with a LOCAL # copy of the uniqueness index. There is no shared order: a write accepted at # L1 is not visible at L2 until an asynchronous replication/merge step later. class Leader: """One multi-leader replica: a local uniqueness index and local grants.""" def __init__(self, name): self.name = name self.taken = {} # username -> owning request_id (local view) def claim(self, request_id, user, username): # Check-then-set against the LOCAL table only. This is exactly what a # per-node UNIQUE constraint does; it cannot see the other leader. if username in self.taken: return ("REJECTED", self.taken[username]) self.taken[username] = request_id return ("GRANTED", request_id) def run_multi_leader(): print("MODEL 1 -- asynchronous multi-leader replication") print(" two independent leaders, each enforces UNIQUE(username) on its LOCAL table") print(f" two users concurrently claim '{USERNAME}', one request routed to each leader:\n") l1, l2 = Leader("L1"), Leader("L2") routing = [(l1, CLAIMS[0]), (l2, CLAIMS[1])] # The two claims are concurrent: each leader decides BEFORE either has # replicated to the other, so both see 'alice' as free. grants = [] for leader, (request_id, user) in routing: status, owner = leader.claim(request_id, user, USERNAME) print(f" {leader.name} receives {request_id} ({user}): checks local table," f" '{USERNAME}' is free -> {status}") if status == "GRANTED": grants.append((leader.name, request_id, user)) print("\n ... asynchronous replication merges the two leaders ...") # Merge the two local indexes. Both already committed a grant for 'alice'. conflict = l1.taken.get(USERNAME) != l2.taken.get(USERNAME) print(f" L1.taken['{USERNAME}'] = {l1.taken[USERNAME]} " f"L2.taken['{USERNAME}'] = {l2.taken[USERNAME]}") print(f" CONFLICT at merge: two owners for '{USERNAME}' " f"-- {'detected, but both users were already told they won' if conflict else 'none'}") print(f"\n RESULT: {len(grants)} grants for '{USERNAME}' -- " f"UNIQUE constraint VIOLATED (two owners)") for name, request_id, user in grants: print(f" owner: {user} via {request_id} (granted by {name})") print() return grants # --- Model 2: one totally-ordered log partition, single-threaded consumer ---- # # Every claim for a username is appended to ONE log partition (chosen by hash of # the username) and a single consumer processes the partition in log order. The # log imposes a total order on all contenders for that key, so there is a # well-defined FIRST writer. def partition_for(username, num_partitions=8): h = int(hashlib.sha256(username.encode()).hexdigest(), 16) return h % num_partitions def run_total_order_log(): print("MODEL 2 -- one totally-ordered log partition, single-threaded consumer") part = partition_for(USERNAME) print(f" all claims for '{USERNAME}' route to log partition #{part} (hash of username)") print(" the log fixes ONE order; a single consumer grants the first, rejects the rest:\n") # Append both concurrent claims to the one partition. The log serialises # them into a definite order (here: arrival order req-1, then req-2). log = list(CLAIMS) # [(req-1, user-1), (req-2, user-2)] print(f" log partition #{part} order: " + " , ".join(f"{rid}({u})" for rid, u in log) + "\n") taken = {} # username -> owning request_id (the single consumer's state) grants = [] for offset, (request_id, user) in enumerate(log): if USERNAME in taken: print(f" offset {offset}: consume {request_id} ({user}): " f"'{USERNAME}' already owned by {taken[USERNAME]} -> REJECTED") else: taken[USERNAME] = request_id grants.append((request_id, user)) print(f" offset {offset}: consume {request_id} ({user}): " f"'{USERNAME}' is free -> GRANTED") print(f"\n RESULT: {len(grants)} grant for '{USERNAME}' -- " f"UNIQUE constraint HELD (exactly one owner)") for request_id, user in grants: print(f" owner: {user} via {request_id}") print() return grants def main(): print(f"Two users race to claim the username '{USERNAME}'. " f"UNIQUE(username) permits exactly one owner.\n") ml = run_multi_leader() to = run_total_order_log() print("=" * 68) print(f" async multi-leader : {len(ml)} owners -> constraint violated") print(f" totally-ordered log: {len(to)} owner -> constraint held") print(" uniqueness needs all contenders to agree who was FIRST;") print(" independent leaders have no shared order, so both think they won;") print(" one ordered partition gives every contender the same first writer.") if __name__ == "__main__": main()