These are the notes for System Design episode 23. Two ChaiNow servers give the same order number to two different customers, and one order simply disappears. You'll see why one counter per server collides, why splitting servers into odd and even lanes breaks the day you add a server, why random UUIDs never collide but lose the order, then invent the Snowflake ID (time + machine + sequence in 64 bits, announced by Twitter in June 2010), break it with a clock that goes backwards, fix it, and finish with UUIDv7, a sortable UUID. Every demo is plain Python and runs as-is; outputs are real (Python 3.13). Outputs that depend on randomness or on the time of the run (UUIDs, shuffled orders, Snowflake numbers, dates) will be different on your machine.
First, the word everything here is about. An ID (identifier) is a number or name that points to exactly one thing: order 1001, roll number 23, token 42. Its one job is to be unique: no two things may share it. In a database the ID column is usually the primary key, the column the database uses to find a row and refuses to repeat.
The problems
| Problem | What it teaches |
|---|---|
| Two servers, one number | Auto increment, why per-server counters collide, duplicate keys and lost orders |
| Odd and even lanes | Start + step ranges, why they break when you add a server, why one central counter is a bottleneck |
| Random IDs | UUIDs, UUIDv4, collision odds, why random IDs are unordered and hurt a B-tree index |
| Put the time first | The Snowflake ID: 1 + 41 + 10 + 12 bits, epoch, bit shifts, sequence numbers, roughly sorted IDs |
| The clock goes back | Clock drift, NTP, duplicate IDs, the "never go back in time" rule |
| Sortable UUIDs | UUIDv7: 48-bit millisecond time + random bits, RFC 9562, and how to choose |
Problem 1: two servers, one number
At a busy chai stall every customer gets a paper token from one roll: 41, 42, 43. One roll means no number ever repeats. At lunch rush the owner opens a second counter with its own roll, also starting at 41. Now "Token 42, your chai!" makes two people walk up.
A database's auto increment column is that token roll: every new row gets the last number plus one (1001, 1002, 1003...), handed out by the database. In episode 12 we split ChaiNow's orders across servers. Each server now has its own counter:
# Two ChaiNow order servers, each with its own counter
class OrderServer:
def __init__(self, name):
self.name = name
self.next_id = 1001 # like AUTO_INCREMENT
def new_order(self):
order_id = self.next_id
self.next_id += 1
return order_id
mumbai, delhi = OrderServer("mumbai"), OrderServer("delhi")
orders = {} # order id -> customer
for i in range(5000):
orders[mumbai.new_order()] = f"Mumbai customer {i}"
orders[delhi.new_order()] = f"Delhi customer {i}"
print("orders placed: 10000 orders saved:", len(orders))
print("order 1001 is:", orders[1001])
Output:
orders placed: 10000 orders saved: 5000
order 1001 is: Delhi customer 0
ordersis a dictionary keyed by order id, like a table whose primary key is the id. Writing to a key that already exists replaces the old value.- Mumbai hands out 1001, 1002, ... and so does Delhi. Every Delhi order lands on a key Mumbai already used, so half the orders are silently overwritten: 10,000 placed, 5,000 saved.
- Order 1001 now belongs to "Delhi customer 0". The Mumbai customer's order is gone.
Why? Each counter only knows its own count. Neither server knows the other already used 1001. When two different things get the same ID, that's called a collision. In a real database the second insert would fail with a duplicate key error (the primary key refuses repeats), or, without that rule, two customers would share one order. Either way it's broken.
Problem 2: odd and even lanes
Walk down a street: houses on one side get odd numbers (1, 3, 5), the other side even numbers (2, 4, 6). Two sides, never a clash. Same idea for servers: give each one a start and a step (how much to jump each time). Server A starts at 1 and jumps by 2; server B starts at 2 and jumps by 2. Many databases let you set exactly this, a start and a step for auto increment.
class OrderServer:
def __init__(self, start, step):
self.next_id, self.step = start, step
def new_order(self):
order_id = self.next_id
self.next_id += self.step
return order_id
# 2 servers: one hands out odd ids, the other even ids
a, b = OrderServer(1, 2), OrderServer(2, 2)
ids = [s.new_order() for _ in range(5000) for s in (a, b)]
print("2 servers:", len(ids), "ids,", len(set(ids)), "unique")
# Diwali rush: add a 3rd server, everyone switches to step 3
c = OrderServer(3, 3)
a.step = b.step = 3
ids += [s.new_order() for _ in range(5000) for s in (a, b, c)]
print("3 servers:", len(ids), "ids,", len(set(ids)), "unique")
Output:
2 servers: 10000 ids, 10000 unique
3 servers: 25000 ids, 20000 unique
set(ids)keeps only the different values, solen(ids) - len(set(ids))is the number of repeats.- With two servers: 10,000 IDs, all unique. Perfect.
- After adding server C: 25,000 IDs but only 20,000 unique, 5,000 collisions. Server C starts at 3 and walks 3, 6, 9, ... straight over numbers A and B already handed out.
Lanes only work if you plan every server in advance. Adding one means stopping, finding the biggest ID used so far, and restarting every lane above it (Practice 3 does this). That's careful coordination every time you grow.
And a single central counter that every server asks ("give me the next number")? It never collides, but every order now waits on one machine. It becomes a bottleneck (everything queues behind it) and a single point of failure (if it dies, nobody can order, episode 11's lesson again).
Problem 3: random IDs (UUIDs)
Second idea: stop counting. If every server picks a number at random from an enormous range, nobody needs to talk to anybody, like picking a lottery number from trillions: two people picking the same one is almost impossible.
That's a UUID (universally unique identifier): a 128-bit number, usually written as 32 hexadecimal digits in 5 groups, like 232557e3-fe02-42e3-add7-b7beb11cc9a7. (A bit is one binary digit, 0 or 1; 128 bits is a number up to 2^128. Hexadecimal writes numbers with 16 digits, 0-9 and a-f, so each hex digit holds 4 bits.) There are several versions of UUID. The common one, UUIDv4 (version 4), is almost all random. Stripe's API docs suggest "V4 UUIDs, or another random string with enough entropy to avoid collisions" for keys that clients generate themselves (idempotency keys, which you'll meet next episode).
import time, uuid
ids = set()
for _ in range(500_000):
ids.add(uuid.uuid4()) # random: no counter, no talking
print("500,000 UUIDs, duplicates:", 500_000 - len(ids))
orders = []
for n in range(1, 9): # 8 orders, one after another
orders.append((uuid.uuid4(), f"#{n}"))
time.sleep(0.01)
print("sorted by id:", [name for _, name in sorted(orders)])
u = orders[0][0]
print(u, "->", len(str(u)), "characters, version", u.version)
Output (one real run; the UUIDs and the shuffled order change every run):
500,000 UUIDs, duplicates: 0
sorted by id: ['#8', '#2', '#1', '#3', '#6', '#4', '#5', '#7']
232557e3-fe02-42e3-add7-b7beb11cc9a7 -> 36 characters, version 4
- Zero duplicates in half a million, with no server talking to any other. Great.
- But the 8 orders were made one after another, 10 ms apart, and sorting them by id shuffles them. A random ID says nothing about when it was made, so "show the newest orders" can't use the id.
- As text it's 36 characters (32 hex digits + 4 dashes). The
4at the start of the third group is the version.
How unlikely is a collision? (our own arithmetic)
A UUIDv4 has 128 bits, but 4 of them hold the version number and 2 hold the variant (bits that say "this is a standard UUID"). So the random part is 128 - 4 - 2 = 122 bits:
# chance that n random 122-bit ids contain ANY duplicate (approx.)
for n in [500_000, 10**9, 10**12]:
p = n * (n - 1) / 2 / 2**122
print(f"{n:>17,} ids -> about {p:.1e}")
Output:
500,000 ids -> about 2.4e-26
1,000,000,000 ids -> about 9.4e-20
1,000,000,000,000 ids -> about 9.4e-14
n * (n - 1) / 2 is the number of pairs; each pair matches with chance 1 in 2^122. (This "birthday" estimate is good while the result is tiny.) Even a trillion IDs gives a chance of about 0.00000000000009. Safe in practice, as long as the random numbers come from a good random source.
Why "no order" hurts a database
Remember the index from episode 10: a B-tree index, a sorted tree of keys stored in fixed-size blocks called pages, so the database can find a row without reading the whole table. Where does each new ID go?
import bisect, uuid
def landed_at_end(new_ids):
index, at_end = [], 0 # a sorted list, like an index
for x in new_ids:
pos = bisect.bisect(index, x) # where it must go to stay sorted
at_end += pos == len(index)
index.insert(pos, x)
return at_end
n = 10_000
print("counting ids :", landed_at_end(range(n)), "of", n, "at the end")
print("random uuid4s :", landed_at_end(uuid.uuid4() for _ in range(n)),
"of", n, "at the end")
Output (the random count varies by run, usually around 10):
counting ids : 10000 of 10000 at the end
random uuid4s : 10 of 10000 at the end
bisect.bisectfinds the position where a value must go to keep the list sorted.- Counting IDs always go at the end: the database only ever fills the last page.
- Random IDs land anywhere. Each new row has to go into some page in the middle; when that page is full it is split into two half-full pages (a page split). Pages all over the index keep getting touched and split, which means more disk work and a bigger, half-empty index.
Size matters too:
import uuid
u = uuid.uuid4()
print("as text :", len(str(u)), "characters ->", str(u))
print("as bytes:", len(u.bytes), "bytes")
print("snowflake fits in", 64 // 8, "bytes (a 64-bit integer)")
Output (the UUID varies):
as text : 36 characters -> b582c16a-55fd-43e8-81fc-bfb76194f93b
as bytes: 16 bytes
snowflake fits in 8 bytes (a 64-bit integer)
A byte is 8 bits. Stored as text a UUID takes 36 characters; stored as raw bytes, 16. The ID we invent next takes 8.
Problem 4: put the time first (the Snowflake ID)
We want both: no coordination and IDs in time order. The trick: build the ID out of parts, like a date written first on a form.
| Part | Bits | What it does |
|---|---|---|
| Sign bit | 1 | Always 0, so the number stays positive in a signed 64-bit integer |
| Time | 41 | Milliseconds since a chosen starting moment: bigger ID = newer |
| Machine ID | 10 | The server's own number (0 to 1023), given once when it starts: two machines never make the same ID |
| Sequence | 12 | A small counter for IDs made in the same millisecond on the same machine |
1 + 41 + 10 + 12 = 64 bits: a normal long integer (BIGINT in SQL). This is Twitter's Snowflake ID, first announced in June 2010. The time is counted from an epoch, a chosen starting moment. Unix time counts from 1 January 1970; Twitter (now X) counts from its own epoch, 1288834974657 milliseconds after 1970, so that 41 bits last longer.
import time
EPOCH = 1288834974657 # Twitter's epoch, in ms
class Snowflake:
def __init__(self, machine): # 0 to 1023: 10 bits
self.machine, self.last_ms, self.seq = machine, -1, 0
def next_id(self):
ms = int(time.time() * 1000) - EPOCH
if ms == self.last_ms:
self.seq = (self.seq + 1) & 4095 # 12 bits
if self.seq == 0: # 4096 used: wait
while ms <= self.last_ms:
ms = int(time.time() * 1000) - EPOCH
else:
self.seq = 0
self.last_ms = ms
return (ms << 22) | (self.machine << 12) | self.seq
mumbai, delhi = Snowflake(1), Snowflake(2)
m = [mumbai.next_id() for _ in range(100_000)]
d = [delhi.next_id() for _ in range(100_000)]
print("ids:", len(m + d), " unique:", len(set(m + d)))
print("Mumbai's ids in time order:", m == sorted(m))
x = m[-1]
print(x, "= ms", x >> 22, "| machine", x >> 12 & 1023, "| seq", x & 4095)
Output (the last line changes with the time of the run):
ids: 200000 unique: 200000
Mumbai's ids in time order: True
2116268207227539847 = ms 504557658965 | machine 1 | seq 391
How the code works, line by line:
time.time() * 1000is the current Unix time in milliseconds; subtractingEPOCHcounts from Twitter's start instead.- Same millisecond as last time: the sequence number goes up by one.
& 4095keeps only the lowest 12 bits (4095 is twelve 1-bits), so after 4095 it wraps to 0. If it wrapped, all 4,096 numbers for this millisecond are used, so the loop waits for the next millisecond. - New millisecond: the sequence restarts at 0.
- Gluing the parts: a bit shift
<<moves a number's bits to the left, like adding zeros at the end of a decimal number (5 followed by three zeros = 5000).ms << 22makes room for 22 bits (10 machine + 12 sequence) on the right;machine << 12makes room for the 12 sequence bits;|(bitwise OR) combines the parts, since they don't overlap. - Taking it apart:
x >> 22shifts right to get the time back;x >> 12 & 1023gets the 10 machine bits;x & 4095gets the 12 sequence bits.
The result: 200,000 IDs, all unique, each machine's IDs in time order, and every ID knows its own birth time, with no server asking another. Discord uses the same idea (with its own epoch, 1420070400000), and Instagram uses a version with 41 bits of time, a 13-bit shard ID (which database shard the row lives on) instead of a machine number, and a 10-bit sequence.
Snowflake by the numbers (our own arithmetic)
print("sequence, 12 bits:", 2**12, "ids per ms per machine")
print(" per second :", f"{2**12 * 1000:,}")
print("machine, 10 bits :", 2**10, "machines")
years = 2**41 / 1000 / 60 / 60 / 24 / 365.25
print(f"time, 41 bits : {2**41:,} ms = {years:.1f} years")
print("total :", 1 + 41 + 10 + 12, "bits")
print(f"UUIDv4 random bits: 128 - 4 - 2 = {128 - 4 - 2}")
print(f"2**122 = {2**122:,}")
Output:
sequence, 12 bits: 4096 ids per ms per machine
per second : 4,096,000
machine, 10 bits : 1024 machines
time, 41 bits : 2,199,023,255,552 ms = 69.7 years
total : 64 bits
UUIDv4 random bits: 128 - 4 - 2 = 122
2**122 = 5,316,911,983,139,663,491,615,228,241,121,378,304
- 4,096 IDs per millisecond per machine is over 4 million a second from one server.
- 41 bits of milliseconds last about 69.7 years from the epoch. Counting from 1970 they would have run out in 2039 (Practice 5); counting from 2010 they last until 2080.
Decoding a Snowflake ID into a date
Add the epoch back and you get a normal Unix time:
from datetime import datetime, timezone
EPOCH = 1288834974657 # Twitter's epoch, in ms
def decode(snowflake_id):
ms = (snowflake_id >> 22) + EPOCH # back to Unix milliseconds
when = datetime.fromtimestamp(ms / 1000, tz=timezone.utc)
return when, snowflake_id >> 12 & 1023, snowflake_id & 4095
for x in [2116268207227539847, 0, (1 << 63) - 1]:
when, machine, seq = decode(x)
print(f"{x:>19} -> {when:%Y-%m-%d %H:%M:%S.%f} UTC"
f" | machine {machine} | seq {seq}")
Output:
2116268207227539847 -> 2026-10-30 20:37:13.622000 UTC | machine 1 | seq 391
0 -> 2010-11-04 01:42:54.657000 UTC | machine 0 | seq 0
9223372036854775807 -> 2080-07-10 17:30:30.208000 UTC | machine 1023 | seq 4095
- The first ID is the one from the demo run above: made on machine 1, sequence 391, on 30 October 2026.
- ID 0 is the epoch itself: 1288834974657 ms after 1970 is 4 November 2010, 01:42:54.657 UTC.
(1 << 63) - 1is the biggest positive 64-bit number: the last moment the 41 time bits can hold, in July 2080.
Roughly sorted, not perfectly sorted
Within one machine, IDs are strictly in order. Across machines, two IDs from the same millisecond are ordered by machine number, not by the exact moment they were made, and machine clocks are never perfectly equal. So Snowflake IDs are roughly sorted (also called k-sorted: every ID is close to its true place in time order). That's good enough for "newest orders first" and keeps index inserts near the end.
Problem 5: the clock goes back
Snowflake has one weak spot: it trusts the clock. Your wristwatch runs 2 minutes fast, so you set it back. Normal. Server clocks drift too (clock drift: a clock slowly running fast or slow), and a time sync service called NTP (Network Time Protocol) regularly corrects them, sometimes pulling the time backwards. Then the same milliseconds happen twice on the same machine.
A tiny Snowflake maker with a fake clock we control:
def make_id(ms, machine, seq):
return (ms << 22) | (machine << 12) | seq
seen, last_ms, seq = set(), -1, 0
clock = [100, 100, 101, 102, 100, 101] # time sync pulls it back
for ms in clock:
seq = seq + 1 if ms == last_ms else 0
last_ms = ms
new_id = make_id(ms, 1, seq)
print(ms, new_id, "DUPLICATE!" if new_id in seen else "ok")
seen.add(new_id)
Output:
100 419434496 ok
100 419434497 ok
101 423628800 ok
102 427823104 ok
100 419434496 DUPLICATE!
101 423628800 DUPLICATE!
The first four IDs are fine. Then millisecond 100 comes back with sequence 0 and makes exactly the same ID as the very first one. Then 101 again: another duplicate. Same machine, same millisecond, same sequence: same ID.
The fix: never go back in time
Remember the last millisecond used. If the clock reads less than that, don't make an ID: wait until the clock catches up, or refuse with an error. Here is the CLOCK demo with that check (the episode's homework):
def make_id(ms, machine, seq):
return (ms << 22) | (machine << 12) | seq
seen, last_ms, seq = set(), -1, 0
clock = [100, 100, 101, 102, 100, 101, 102, 103]
for ms in clock:
if ms < last_ms: # the clock went back
print(ms, "refused: clock is", last_ms - ms, "ms behind")
continue
seq = seq + 1 if ms == last_ms else 0
last_ms = ms
new_id = make_id(ms, 1, seq)
print(ms, new_id, "DUPLICATE!" if new_id in seen else "ok")
seen.add(new_id)
print("ids made:", len(seen))
Output:
100 419434496 ok
100 419434497 ok
101 423628800 ok
102 427823104 ok
100 refused: clock is 2 ms behind
101 refused: clock is 1 ms behind
102 427823105 ok
103 432017408 ok
ids made: 6
- While the clock is behind, no IDs are made, so no duplicates.
- When the clock reaches 102 again, it equals
last_ms, so the sequence continues (sequence 1) instead of restarting:427823105, one more than the earlier427823104. - A real generator usually waits if the clock is only a few milliseconds behind, and raises an error if it is far behind (the mini project does both).
Problem 6: sortable UUIDs (UUIDv7)
Snowflake needs a machine number for every server, which someone has to hand out and keep unique (two servers accidentally given machine 5 would collide again). Can we skip that? Think of a cheque: the date is written first, then a long number. Sort by the front and you sort by date.
UUIDv7 does exactly that: the first 48 bits are a timestamp, milliseconds since the Unix epoch (1970), and the remaining bits, except the version and variant bits, are random. It's still a normal 128-bit UUID, defined in the standard RFC 9562, so tools that accept UUIDs accept it. (An RFC, "Request for Comments", is a numbered document that defines an internet standard.)
Python 3.13 doesn't have a uuid7() function, so we build one:
import os, time, uuid
def uuid7():
ms = int(time.time() * 1000) # 48-bit time
rand = int.from_bytes(os.urandom(10), "big") # 80 random bits
value = (ms << 80) | rand
value = value & ~(0xF << 76) | (0x7 << 76) # version = 7
value = value & ~(0x3 << 62) | (0x2 << 62) # variant bits
return uuid.UUID(int=value)
orders = []
for n in range(1, 9):
orders.append((uuid7(), f"#{n}"))
time.sleep(0.01)
print("sorted by id:", [name for _, name in sorted(orders)])
u = orders[0][0]
print(u, "-> version", u.version)
print("time inside:", time.strftime("%Y-%m-%d %H:%M:%S",
time.gmtime((u.int >> 80) / 1000)), "UTC")
Output (the UUID and time change with each run; the sorted order is always #1 to #8):
sorted by id: ['#1', '#2', '#3', '#4', '#5', '#6', '#7', '#8']
01a18e87-e78e-737b-bda8-0adabe5876a4 -> version 7
time inside: 2026-10-30 20:37:13 UTC
ms << 80puts the 48-bit time at the top of the 128 bits (48 + 80 = 128);os.urandom(10)gives 10 random bytes = 80 bits for the rest.value & ~(0xF << 76)clears the 4 version bits (0xFis four 1-bits;~flips every bit, so this is a mask with zeros there), then| (0x7 << 76)writes 7 into them. The variant line does the same for 2 bits. That's why the third group starts with7, like737b.- Sorting by id is now #1 to #8, the order they were made, and
u.int >> 80reads the creation time straight out of the ID. - No machine numbers: two servers making a UUIDv7 in the same millisecond still differ in their random bits.
One limit of this simple version: two IDs made in the same millisecond on one server are ordered by their random bits, not by which came first. (Here they are 10 ms apart.)
Which one do you pick?
| Auto increment | Odd/even lanes | UUIDv4 | Snowflake | UUIDv7 | |
|---|---|---|---|---|---|
| Size | 8 bytes | 8 bytes | 16 bytes (36 chars as text) | 8 bytes | 16 bytes |
| Needs coordination? | One database hands them out | Plan every server ahead | No | A unique machine ID per server | No |
| Time-ordered? | Yes | Roughly | No (shuffled) | Roughly (k-sorted) | Yes, to the millisecond |
| Index inserts | At the end | Near the end | Anywhere (page splits) | Near the end | Near the end |
| Trusts the clock? | No | No | No | Yes: must refuse to go back | Yes, for ordering |
| Good for | One database | A fixed number of servers | Random keys, e.g. idempotency keys | Many servers, 64-bit numbers | Many servers, no setup, 128 bits OK |
The whole chain
- One counter per server: 10,000 placed, 5,000 saved (same ids overwrite).
- Odd/even lanes work, until a third server joins: 5,000 collisions.
- Random UUIDv4: 500,000 with zero duplicates, but 36 characters and shuffled order (new rows land all over the index).
- Snowflake: 41-bit time + 10-bit machine + 12-bit sequence, 64 bits, unique and roughly time-ordered.
- The clock goes back: duplicates, so never go back in time (wait or refuse).
- UUIDv7: 48-bit millisecond time first, random after: sortable, no machine numbers.
Common mistakes (and the real outputs)
| Mistake | Code | Output | Fix |
|---|---|---|---|
| A separate counter on every server | next_id += 1 on every server |
orders placed: 10000 orders saved: 5000 |
A machine number in the ID (Snowflake), or UUIDs |
| Adding a lane later | c = OrderServer(3, 3) and a.step = b.step = 3 |
3 servers: 25000 ids, 20000 unique |
Restart all lanes above the biggest used id, or use Snowflake |
| Sorting random UUIDs to find the newest | sorted(orders) with uuid4() ids |
sorted by id: ['#8', '#2', '#1', '#3', ...] |
A time-ordered id (Snowflake, UUIDv7) or a separate created-at column |
| Trusting the clock blindly | ms = clock() with no check |
100 419434496 DUPLICATE! |
if ms < last_ms: wait or refuse |
| Two servers with the same machine ID | Snowflake(1) on both servers |
duplicates whenever they share a millisecond and sequence | Hand out machine IDs from one place, and check them at startup |
| Storing a 64-bit id as a float | int(float(x)) |
same id? False | off by 121 |
Keep it an integer, or send it as a string |
The last mistake, run for real. A float (a 64-bit floating-point number, a "double") holds only about 16 significant digits exactly, and Snowflake IDs have 19. So converting one to a float quietly changes it. Any language or data format that stores all numbers as doubles has this problem; sending big IDs as strings avoids it.
x = 2116268207227539847 # a real Snowflake id
y = int(float(x)) # stored as a float somewhere
print(x)
print(y)
print("same id?", x == y, "| off by", y - x)
print("as a string:", str(x) == "2116268207227539847")
Output:
2116268207227539847
2116268207227539968
same id? False | off by 121
as a string: True
Mini project: ChaiNow's ID service
A Snowflake-style ID maker you could actually run on every order server: it checks its machine number fits 10 bits, waits if the clock is a few milliseconds behind, refuses if it's far behind, waits when 4,096 IDs in one millisecond are used up, and decodes any ID back into a date. The clock is passed in, so we can test it with a fake clock.
# Mini project: ChaiNow's ID service, safe against a clock going back
import time
from datetime import datetime, timezone
EPOCH = 1288834974657 # Twitter's epoch, in ms
class ClockWentBack(Exception):
pass
class IdMaker:
def __init__(self, machine, clock=None, max_wait_ms=5):
if not 0 <= machine <= 1023:
raise ValueError("machine must be 0..1023 (10 bits)")
self.machine, self.last_ms, self.seq = machine, -1, 0
self.clock = clock or (lambda: int(time.time() * 1000))
self.max_wait_ms = max_wait_ms
def now(self):
return self.clock() - EPOCH
def next_id(self):
ms = self.now()
if ms < self.last_ms: # clock went back
behind = self.last_ms - ms
if behind > self.max_wait_ms:
raise ClockWentBack(f"{behind} ms behind")
while ms < self.last_ms: # small: just wait
ms = self.now()
if ms == self.last_ms:
self.seq = (self.seq + 1) & 4095
if self.seq == 0: # 4096 used: wait
while ms <= self.last_ms:
ms = self.now()
else:
self.seq = 0
self.last_ms = ms
return (ms << 22) | (self.machine << 12) | self.seq
def decode(x):
ms = (x >> 22) + EPOCH
t = datetime.fromtimestamp(ms / 1000, tz=timezone.utc)
return f"{t:%Y-%m-%d %H:%M:%S.%f}"[:-3], x >> 12 & 1023, x & 4095
# 1. three servers, real clock
makers = [IdMaker(m) for m in (1, 2, 3)]
ids = [mk.next_id() for _ in range(50_000) for mk in makers]
print("ids:", len(ids), "unique:", len(set(ids)))
print("newest id:", max(ids), "->", decode(max(ids)))
# 2. a fake clock: +0, +3, back to +1 (waits), then back 500 ms
base = int(time.time() * 1000)
ticks = iter([base, base + 3, base + 1, base + 2, base + 3,
base + 4, base - 496])
fake = IdMaker(7, clock=lambda: next(ticks))
start = base - EPOCH
try:
while True:
x = fake.next_id()
print(f"fake clock: ms +{(x >> 22) - start}, seq {x & 4095}")
except ClockWentBack as e:
print("refused:", e)
# 3. a bad machine number
try:
IdMaker(1024)
except ValueError as e:
print("refused:", e)
Output (the first two lines change with the time of the run):
ids: 150000 unique: 150000
newest id: 2116268536463634669 -> ('2026-10-30 20:38:32.118', 3, 237)
fake clock: ms +0, seq 0
fake clock: ms +3, seq 0
fake clock: ms +3, seq 1
fake clock: ms +4, seq 0
refused: 500 ms behind
refused: machine must be 0..1023 (10 bits)
What to notice:
- 150,000 IDs from 3 servers, all unique, and the newest decodes to the time of the run, machine 3.
- The fake clock jumps from +3 back to +1. That's only 2 ms behind, so the maker waits (reading +2, then +3) and continues at +3 with sequence 1: no duplicate.
- Then the clock jumps 500 ms back. Waiting that long would stall every order, so it refuses with
ClockWentBack. A real service would raise an alert and stop handing out IDs until the clock is fixed. - Machine 1024 doesn't fit in 10 bits, so it's rejected at startup instead of silently overlapping machine 0 later.
Extend it: add a UUIDv7 maker next to it and compare sizes; store machine IDs in one shared table so no two servers can start with the same one; make the waiting loop sleep briefly instead of spinning.
Practice
- Homework: in the CLOCK demo, add the check that refuses to go back in time. Do the duplicates disappear?
- Homework: in the SNOWFLAKE demo, decode an ID into a date.
- Fix the LANES demo so that adding a third server causes zero collisions.
- Homework: Instagram uses 41 bits of time, a 13-bit shard ID and a 10-bit sequence. Compare it with Snowflake. Why might you choose that split?
- When do 41 bits of milliseconds run out if you count from 1970? From Twitter's epoch? From Discord's (1420070400000)? How long do UUIDv7's 48 bits last?
- Homework: for ChaiNow's orders, Snowflake or UUIDv7? Argue both sides.
- A Snowflake server gets 10,000 order requests in one millisecond. What happens?
- Why does a random UUIDv4 primary key make inserts slower than a counting key in a B-tree index?
Solutions and hints
1. Add if ms < last_ms: before the sequence line and skip that tick (the full code and output are in "The fix: never go back in time" above). The output ends with 100 refused: clock is 2 ms behind, 101 refused: clock is 1 ms behind and ids made: 6: no DUPLICATE! lines.
2. Shift right by 22 to get the milliseconds, add the epoch back, and turn it into a date (full code in "Decoding a Snowflake ID into a date"). For the ID from the demo run:
2116268207227539847 -> 2026-10-30 20:37:13.622000 UTC | machine 1 | seq 391
3. Before switching to step 3, restart every server above the biggest ID used so far:
class OrderServer:
def __init__(self, start, step):
self.next_id, self.step = start, step
def new_order(self):
order_id = self.next_id
self.next_id += self.step
return order_id
a, b = OrderServer(1, 2), OrderServer(2, 2)
ids = [s.new_order() for _ in range(5000) for s in (a, b)]
# Diwali rush: restart ALL lanes above the biggest id used so far
base = max(ids) # 10000
a = OrderServer(base + 1, 3)
b = OrderServer(base + 2, 3)
c = OrderServer(base + 3, 3)
ids += [s.new_order() for _ in range(5000) for s in (a, b, c)]
print("3 servers:", len(ids), "ids,", len(set(ids)), "unique")
3 servers: 25000 ids, 25000 unique
It works, but only because one program could see every server's state at the same moment. In a real system you'd have to pause all servers, agree on base, and restart them: exactly the coordination we wanted to avoid.
4. Our own arithmetic:
for name, t, m, s in [("Snowflake", 41, 10, 12),
("Instagram", 41, 13, 10)]:
print(f"{name}: {t + m + s} bits used")
print(f" {2**m:,} machines or shards, {2**s:,} ids per ms each")
print(f" {2**m * 2**s:,} ids per ms across all of them")
Snowflake: 63 bits used
1,024 machines or shards, 4,096 ids per ms each
4,194,304 ids per ms across all of them
Instagram: 64 bits used
8,192 machines or shards, 1,024 ids per ms each
8,388,608 ids per ms across all of them
Instagram's split gives 8x more shards but 4x fewer IDs per millisecond on each. That makes sense when you have many shards, each of which makes only a modest number of IDs per millisecond. A bonus of a shard ID: the ID itself tells you which shard the row lives on, so you can find it without a lookup. (Snowflake's 63 + the always-zero sign bit = 64.)
5.
from datetime import datetime, timezone
def when(unix_ms):
t = datetime.fromtimestamp(unix_ms / 1000, tz=timezone.utc)
return f"{t:%Y-%m-%d %H:%M:%S} UTC"
print("Twitter epoch :", when(1288834974657))
print("Discord epoch :", when(1420070400000))
print("Twitter 41 bits run out:", when(1288834974657 + 2**41))
print("Discord 41 bits run out:", when(1420070400000 + 2**41))
print("1970 + 41 bits run out :", when(2**41))
years = 2**48 / 1000 / 86400 / 365.25
print(f"UUIDv7 48 bits last : {years:,.0f} years after 1970")
Twitter epoch : 2010-11-04 01:42:54 UTC
Discord epoch : 2015-01-01 00:00:00 UTC
Twitter 41 bits run out: 2080-07-10 17:30:30 UTC
Discord 41 bits run out: 2084-09-06 15:47:35 UTC
1970 + 41 bits run out : 2039-09-07 15:47:35 UTC
UUIDv7 48 bits last : 8,919 years after 1970
Counting from 1970 would leave only until 2039; a recent custom epoch buys decades. UUIDv7's 48 bits are plenty, even counting from 1970.
6. There's no single right answer. Snowflake: 8 bytes (smaller indexes, fits a BIGINT), roughly time-ordered, readable as a number; but every server needs a unique machine ID, and big IDs must be sent as strings to anything that stores numbers as doubles. UUIDv7: no machine IDs to manage, a standard (RFC 9562) that UUID tools understand, time-ordered; but 16 bytes, and long to read out over the phone ("my order is 01a18e87-..."). Many teams also show customers a short separate order code and keep the long ID internal.
7. The sequence has 12 bits, so only 4,096 IDs fit in one millisecond. The 4,097th request waits for the next millisecond (the while ms <= self.last_ms loop), so the 10,000 requests are spread over 3 milliseconds (4,096 + 4,096 + 1,808). Nothing collides; a few requests wait less than 3 ms. If that's not enough, add more machines.
8. In a B-tree index, keys are kept sorted in pages. Counting keys always go into the last page, which stays in memory. Random keys land on a random page anywhere in the index (see the bisect demo: about 10 of 10,000 at the end), so the database keeps reading different pages and splitting full ones (page splits), leaving many half-empty pages. UUIDv7 and Snowflake fix this by putting the time first.
Quick quiz
# Snowflake: 41 bits time, 10 bits machine,
# 12 bits sequence
# How many IDs can ONE machine make
# in ONE millisecond?
- A. 1,024
- B. 4,096
- C. 41
- D. Unlimited
Answer
B. The sequence has 12 bits: 2^12 = 4,096 IDs per machine per millisecond. 1,024 is the number of machines (10 bits). After 4,096 the generator waits for the next millisecond, so it's not unlimited.
Interview questions
- Design a unique ID generator for a distributed system. (Clarify: must IDs be sortable by time? 64 or 128 bits? How many per second? Then compare a central counter, ranges, UUIDv4, Snowflake and UUIDv7.)
- Why doesn't auto increment work across many database servers? (Each counter only knows its own count, so the same numbers are handed out twice; a central counter avoids it but is a bottleneck and a single point of failure.)
- What's wrong with odd/even (start + step) ranges? (Every server must be planned in advance; adding a server means re-planning and restarting all lanes above the used IDs.)
- What are the pros and cons of UUIDv4 as a primary key? (No coordination, collisions practically impossible with 122 random bits; but 16 bytes, 36 characters as text, unordered, so inserts land all over the B-tree index and cause page splits.)
- Explain the Snowflake ID layout. (1 sign bit always 0, 41 bits of milliseconds since a custom epoch, 10 bits machine ID, 12 bits sequence: 4,096 IDs per ms per machine, about 69.7 years of time.)
- Why use a custom epoch instead of 1970? (41 bits of milliseconds last about 69.7 years; counting from 1970 they'd run out in 2039, from a recent epoch decades later.)
- What happens if the clock moves backwards? How do you handle it? (The same millisecond, machine and sequence can repeat, giving duplicate IDs; remember the last millisecond, wait if slightly behind, refuse and alert if far behind.)
- Are Snowflake IDs strictly sorted? (Per machine, yes; across machines only roughly (k-sorted), because same-millisecond IDs are ordered by machine number and clocks differ slightly.)
- How are machine IDs assigned? (From one place at startup, e.g. a config or a shared table or coordination service, checked so no two live servers share one.)
- What is UUIDv7, and when would you choose it over Snowflake? (A 128-bit RFC 9562 UUID whose first 48 bits are Unix milliseconds and the rest random; choose it when you want time order without managing machine IDs and can afford 16 bytes.)
- Why might you send a 64-bit ID as a string in a JSON API? (Systems that store numbers as 64-bit floats keep only about 16 digits exactly, so a 19-digit ID gets changed.)
Glossary
| Term | Meaning |
|---|---|
| ID (identifier) | A number or name that points to exactly one thing, e.g. order 1001 |
| Unique | No two things share the same value |
| Primary key | The column a database uses to identify each row; it refuses repeats |
| Duplicate key error | What a database raises when you insert a row whose primary key already exists |
| Auto increment | A database column that gives each new row the last number plus one (1001, 1002, ...) |
| Counter | A number that goes up by one each time something is handed out |
| Collision | Two different things getting the same ID |
| Start and step | A counter that begins at a chosen number and jumps by a fixed amount (1, 3, 5 = start 1, step 2) |
| Odd/even lanes (ID ranges) | Giving each server its own non-overlapping set of numbers by start and step |
| Coordination | Servers having to talk to each other (or to one central place) to agree on something |
| Central counter | One server that hands out every ID; never collides, but slow under load and a single point of failure |
| Bottleneck | One part that everything has to wait for, limiting the whole system |
| Single point of failure | One part whose failure stops the whole system (episode 11) |
| Shard | One piece of data split across machines (episode 12) |
| Shard ID | The number of the shard a row lives on; Instagram puts 13 bits of it inside its IDs |
| Bit | One binary digit, 0 or 1 |
| Byte | 8 bits |
| 64-bit integer / long / BIGINT | A whole number stored in 64 bits (8 bytes); the size of a Snowflake ID |
| Sign bit | The top bit of a signed integer; 0 means positive. Snowflake keeps it 0 |
| Hexadecimal (hex) | Writing numbers with 16 digits (0-9, a-f); each hex digit is 4 bits |
| UUID | Universally unique identifier: a 128-bit ID written as 32 hex digits in 5 groups (36 characters) |
| UUIDv4 | The random UUID version: 122 random bits (128 - 4 version bits - 2 variant bits, our arithmetic) |
| UUIDv7 | A UUID whose first 48 bits are Unix milliseconds and the rest random (except version and variant); sortable by time |
| Version bits | 4 bits inside a UUID that say which version it is (4, 7, ...) |
| Variant bits | 2 bits inside a UUID that mark it as a standard (RFC) UUID |
| RFC | "Request for Comments": a numbered document defining an internet standard |
| RFC 9562 | The standard that defines UUIDs, including version 7 |
| Entropy | How unpredictable random data is; more random bits = more entropy |
| Idempotency key | A random key a client sends with a request so a retry isn't done twice (next episode); Stripe suggests V4 UUIDs |
| Birthday estimate | Approximate chance of any duplicate among n random values: about n²/2 divided by the number of possible values |
| Snowflake ID | Twitter's 64-bit ID (announced June 2010): 1 zero bit + 41 bits time + 10 bits machine + 12 bits sequence |
| Epoch | The starting moment time is counted from; Unix uses 1 January 1970, Twitter 1288834974657 ms, Discord 1420070400000 ms |
| Unix time | Time counted in seconds (or milliseconds) since 1 January 1970 UTC |
| Millisecond (ms) | One thousandth of a second |
| UTC | The world's reference time zone, used so IDs don't depend on local time |
| Timestamp | A number recording a moment in time, e.g. milliseconds since the epoch |
| Machine ID | The number (0 to 1023 in Snowflake) given to each server so two servers never make the same ID |
| Sequence number | A small counter for IDs made in the same millisecond on the same machine (12 bits: 0 to 4095) |
Bit shift (<<, >>) |
Moving a number's bits left (making room on the right) or right (dropping bits on the right) |
Bitwise OR (|) |
Combines two numbers bit by bit; used to glue the ID's parts together |
Bitwise AND / mask (&) |
Keeps only chosen bits, e.g. x & 4095 keeps the lowest 12 |
| Roughly sorted / k-sorted | Every ID is close to, but not exactly at, its true place in time order |
| Clock drift | A computer's clock slowly running fast or slow |
| NTP | Network Time Protocol: a service that keeps server clocks correct, sometimes moving them backwards |
| Clock going backwards | The clock reading an earlier time than before, e.g. after an NTP correction |
| Never go back in time | The rule that a generator must not make IDs when the clock reads less than the last millisecond used |
| Index | A sorted structure that lets a database find rows without reading the whole table (episode 10) |
| B-tree index | The usual database index: a balanced tree of sorted keys stored in pages |
| Page | A fixed-size block of an index or table on disk |
| Page split | When a full page must take a new key in the middle, it is split into two half-full pages |
| Float / double | A number stored in 64-bit floating-point form; exact only to about 16 digits |
set |
A Python collection that keeps only unique values; used here to count duplicates |
bisect |
Python's module for finding where a value goes in a sorted list |
Summary
- An ID must be unique. One auto increment counter per server hands out the same numbers twice: 10,000 orders placed, 5,000 saved.
- Odd/even lanes (start + step) work only if every server is planned ahead; adding one caused 5,000 collisions. A central counter is a bottleneck and a single point of failure.
- UUIDv4 needs no coordination and collisions are practically impossible (122 random bits), but it's 16 bytes, 36 characters as text, and unordered, so inserts scatter across the B-tree index.
- Snowflake puts the time first: 1 + 41 bits of milliseconds since a custom epoch + 10-bit machine ID + 12-bit sequence = 64 bits; 4,096 IDs per ms per machine, about 69.7 years, roughly time-sorted.
- Snowflake trusts the clock: if NTP pulls it back, IDs repeat. Remember the last millisecond; wait if slightly behind, refuse if far behind.
- UUIDv7 (RFC 9562): 48-bit Unix milliseconds first, random bits after. Time-sorted, no machine IDs, 128 bits.
- Choosing: one database → auto increment; many servers and 64-bit numbers → Snowflake; many servers, no setup, 128 bits OK → UUIDv7.
Next episode: a payment times out. Do you try again? Try again, and the customer may pay twice: reliability patterns, with retries, idempotency and circuit breakers.
Sources: Wikipedia, "Snowflake ID" (first announced by Twitter in June 2010; 64 bits: highest bit always 0, 41 bits timestamp, 10 bits machine ID, 12 bits per-machine sequence; X epoch 1288834974657; Discord epoch 1420070400000; Instagram 41 bits timestamp, 13 bits shard ID, 10 bits sequence); Fastly docs, uuid.version7 ("The first 48 bits represent a timestamp since the Unix Epoch in milliseconds", remaining bits except version and variant random, RFC 9562); Stripe API docs, Idempotent requests ("V4 UUIDs, or another random string with enough entropy to avoid collisions"). 2^12 = 4,096, 2^41 ms ≈ 69.7 years, 122 random bits, collision odds and the run-out dates are our own arithmetic.