Art of Codeartofcode
Lesson 12 of 16

10. Unique ID Generation

1
The picture to keep in your head
2
10.1 What makes a good ID?
3
10.2 What's wrong with auto-increment?
4
10.3 Why does auto-increment break across many servers?
5
10.4 What are UUIDs, and which version should you use?
6
10.5 How do Snowflake IDs work?
7
10.6 What are ticket servers and ID ranges?
8
10.7 Why does clock skew matter for time-based IDs?
9
10.8 How do you make short IDs with base62?
10
10.9 Should IDs be guessable or unguessable?
11
Memory card and where the analogy breaks
12
Practice: five levels
13
Interview questions
14
Solutions
15
Sources
16
Code lab
10. Unique ID Generation

Practice: five levels

3 min read+10 XP

Assignments

Five levels. Do them in order. Answers are in "Solutions" at the end, so try first.

Level 1: Think (no code)

A. Which ID scheme fits? One line each.

  1. A small app with one PostgreSQL database.
  2. A chat app writing 200,000 messages a second across many servers, shown newest first.
  3. Password-reset links sent by email.
  4. Short links for a URL shortener.
  5. Order IDs across 8 database shards, stored in a BIGINT column.

B. True or false? Explain.

  1. "Our order IDs are UUID v4, so we don't need to check that the order belongs to the user."
  2. "Snowflake IDs from two different machines are exactly in the order the events happened."
  3. "Auto-increment IDs are always continuous, so the highest ID equals the number of orders."

Level 2: Calculate

  1. A Snowflake-style layout gives 41 bits of milliseconds. How many years does it last from its epoch? If you only used 39 bits?
  2. With 12 sequence bits, how many IDs can one machine make per millisecond? Per second? With 1,024 machines, per second in total?
  3. How many base62 characters do you need for every possible 64-bit value? For 6 billion short links?
  4. Roughly what's the chance of any collision among one trillion UUID v4s? (Use n² ÷ (2 × 2¹²²).)

Level 3: Build

In Python, write:

  1. A Snowflake generator with 41 time bits (from your own epoch), 10 machine bits and 12 sequence bits. It must: produce unique, increasing IDs; wait for the next millisecond when 4,096 IDs are used up; and refuse if the clock moves backwards.
  2. A decode(id) that returns the time, machine and sequence.
  3. A uuid7(ms) that builds a valid version-7 UUID from a timestamp.

Check that: 10,000 IDs from one generator are unique and sorted; the 4,097th ID in one millisecond lands in the next millisecond; two machines produce different IDs in the same millisecond; a backwards clock raises an error; UUID v7s made at increasing times sort in order and report version 7.

Level 4: Debug

The orders table suddenly reports a duplicate primary key error a few times a week, always on the same server, always around the time its clock is corrected by NTP.

python
  1. Find the bug. Walk through how a duplicate is created.
  2. Fix it.

Level 5: Design

The bookstore is moving to 8 order shards and adding a public "share your wishlist" feature. Design its IDs:

  1. Order IDs: the scheme, the bit layout or format, and why.
  2. How machine or shard IDs are assigned and kept unique.
  3. What happens when a clock jumps backwards.
  4. Wishlist share links: the format and why.
  5. How existing auto-increment order IDs (up to about 40 million) keep working.