1"""Chapter 31 (case study: URL shortener) deep-dive code.
21. ID ranges: app servers lease blocks of IDs from a ticket server, so codes are unique without coordination per request.
32. Scrambling: a bijection that makes sequential IDs look random but stays collision-free.
43. Hash-based codes with collision retry.
5Run: python3 ch31_url_shortener.py"""
6import hashlib
7import math
8import string
9
10ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase # 62 characters
11
12
13def to_base62(n, width=0):
14 out = []
15 while n > 0:
16 n, r = divmod(n, 62)
17 out.append(ALPHABET[r])
18 s = "".join(reversed(out)) or ALPHABET[0]
19 return s.rjust(width, ALPHABET[0])
20
21
22# ---- 1. ID ranges -------------------------------------------------------------
23
24class TicketServer:
25 """Hands out blocks of IDs. In production this is one row in a database,
26 updated with an atomic 'next_start = next_start + size' (Chapter 10)."""
27
28 def __init__(self, start=1):
29 self.next_start = start
30
31 def lease(self, size):
32 start = self.next_start
33 self.next_start += size
34 return start, start + size # [start, end)
35
36
37class AppServer:
38 def __init__(self, ticket_server, block_size=1000):
39 self.tickets = ticket_server
40 self.block_size = block_size
41 self.next_id, self.end = self.tickets.lease(block_size)
42 self.leases = 1
43
44 def new_id(self):
45 if self.next_id >= self.end: # block used up: lease another
46 self.next_id, self.end = self.tickets.lease(self.block_size)
47 self.leases += 1
48 i = self.next_id
49 self.next_id += 1
50 return i
51
52
53# ---- 2. Scrambling sequential IDs ----------------------------------------------
54
55M = 62 ** 7 # every 7-character code
56A = 2_654_435_761 # odd and not a multiple of 31, so gcd(A, M) == 1 -> a bijection
57B = 1_234_567_891
58
59
60def scramble(i, m=M, a=A, b=B):
61 """Maps 0..m-1 onto 0..m-1 one-to-one. Hides the order; it is NOT encryption."""
62 return (a * i + b) % m
63
64
65# ---- 3. Hash-based codes ----------------------------------------------------------
66
67def hash_code(long_url, taken, length=7):
68 """Take the first characters of a SHA-256 hash in base62. On a clash with a
69 different URL, add a salt and try again."""
70 salt = 0
71 while True:
72 digest = hashlib.sha256(f"{long_url}#{salt}".encode()).digest()
73 code = to_base62(int.from_bytes(digest, "big"))[:length]
74 if code not in taken or taken[code] == long_url:
75 taken[code] = long_url
76 return code
77 salt += 1
78
79
80def run_checks():
81 # 1. Three servers interleaving requests never produce the same ID.
82 ts = TicketServer()
83 servers = [AppServer(ts, block_size=1000) for _ in range(3)]
84 ids = [servers[k % 3].new_id() for k in range(10_000)]
85 assert len(ids) == len(set(ids)), "duplicate IDs"
86 assert sum(s.leases for s in servers) == ts.next_start // 1000 # one ticket-server call per 1,000 IDs
87
88 # A crashed server just leaves a gap: unused IDs are skipped, never reused.
89 crashed = AppServer(ts, block_size=1000)
90 crashed.new_id()
91 after = AppServer(ts, block_size=1000).new_id()
92 assert after > crashed.end - 1
93
94 # 2. Scrambling is one-to-one (check exhaustively on a small space with the same rule).
95 m_small = 62 ** 3
96 assert math.gcd(A, M) == 1 and math.gcd(A, m_small) == 1
97 seen = {scramble(i, m=m_small) for i in range(m_small)}
98 assert len(seen) == m_small
99 # ...and neighbouring IDs give unrelated-looking codes.
100 c1, c2 = to_base62(scramble(1000), 7), to_base62(scramble(1001), 7)
101 assert c1 != c2 and len(c1) == len(c2) == 7
102
103 # 3. Hash codes: same URL -> same code; forced clashes are resolved.
104 taken = {}
105 a1 = hash_code("https://example.com/a", taken)
106 assert hash_code("https://example.com/a", taken) == a1
107 small = {}
108 codes = [hash_code(f"https://example.com/{i}", small, length=2) for i in range(1000)]
109 assert len(set(codes)) == 1000, "every URL must end up with its own code"
110
111 # Capacity of code lengths.
112 assert 62 ** 6 == 56_800_235_584 and 62 ** 7 == 3_521_614_606_208
113
114 print("All checks pass.", f"Sample scrambled codes: {c1}, {c2}")
115
116
117if __name__ == "__main__":
118 run_checks()