Cheat sheet · Data & storage
Unique IDs
The problem
An orders service gets its ids from a database counter. Then the data is split across two databases, and the counters start handing out the same numbers. How to make ids that are unique everywhere, sort well in an index and survive a clock that jumps back.
What you learn
- Why auto-increment stops being unique once you shard
- Why random UUIDv4 keys hurt a B-tree index, and how UUIDv7 fixes it
- How a 64-bit id is built from time, machine and sequence
- What to do when the clock moves backwards
Diagram as code
The lesson's final design as text: paste it into Jira, GitLab, GitHub, Notion or your docs, where Mermaid renders by itself. There are D2 and PlantUML (Confluence, IntelliJ) versions too.
Mermaid: flowchart
flowchart LR
n_client(["App"])
n_api["Orders API"]
n_db_1[("Shard 1")]
n_db_2[("Shard 2")]
n_api_2["Orders API #35;2"]
n_ntp>"Time server"]
n_client --> n_api
n_api --> n_db_1
n_api --> n_db_2
n_client --> n_api_2
n_api_2 --> n_db_2
n_ntp --> n_api_2Mermaid: request sequence
sequenceDiagram
participant n_api as Orders API
participant n_db_1 as Shard 1
participant n_db_2 as Shard 2
participant n_client as App
participant n_api_2 as Orders API #35;2
participant n_ntp as Time server
Note over n_api,n_db_1: One database, one counter
n_api->>n_db_1: INSERT INTO orders (user_id, total)
n_db_1-->>n_api: id = 48213
Note over n_api,n_db_2: Two shards, two counters, same numbers
n_api->>n_db_2: INSERT INTO orders (user_id, total)
n_db_2-->>n_api: id = 48214
Note over n_api,n_db_2: Patch: odd ids on one shard, even on the other
n_api->>n_db_2: ALTER SEQUENCE orders_id_seq
n_db_2-->>n_api: ALTER SEQUENCE
Note over n_client,n_api: Let the service make the id: random UUID
n_client->>n_api: POST /orders HTTP/1.1
n_api-->>n_client: HTTP/1.1 201 Created
Note over n_api,n_db_1: Random keys tear the index apart
n_api->>n_db_1: SELECT avg_leaf_density, leaf_fragmentation
n_db_1-->>n_api: 61.2 #124; 48.7
Note over n_client,n_api: UUIDv7: time first, randomness after
n_client->>n_api: POST /orders HTTP/1.1
n_api-->>n_client: HTTP/1.1 201 Created
Note over n_api_2,n_db_2: Smaller still: time + machine + sequence in 64 bits
n_api_2->>n_db_2: DEBUG new id 250413553075367937
Note over n_ntp,n_api_2: The clock moves back and an id repeats
n_ntp->>n_api_2: INFO clock step: -40 ms (offset from server 0.040 s)
Note over n_api_2,n_db_2: Never go below the last timestamp
n_api_2->>n_db_2: WARN clock behind last id by 40 ms, waitingD2
direction: right
n_client: "App" {
shape: rectangle
}
n_api: "Orders API" {
shape: rectangle
}
n_db_1: "Shard 1" {
shape: cylinder
}
n_db_2: "Shard 2" {
shape: cylinder
}
n_api_2: "Orders API #2" {
shape: rectangle
}
n_ntp: "Time server" {
shape: cloud
}
n_client -> n_api
n_api -> n_db_1
n_api -> n_db_2
n_client -> n_api_2
n_api_2 -> n_db_2
n_ntp -> n_api_2PlantUML: request sequence
@startuml
participant "Orders API" as n_api
database "Shard 1" as n_db_1
database "Shard 2" as n_db_2
participant "App" as n_client
participant "Orders API #2" as n_api_2
boundary "Time server" as n_ntp
note over n_api, n_db_1 : One database, one counter
n_api -> n_db_1 : INSERT INTO orders (user_id, total)
n_db_1 --> n_api : id = 48213
note over n_api, n_db_2 : Two shards, two counters, same numbers
n_api -> n_db_2 : [duplicate] INSERT INTO orders (user_id, total)
n_db_2 --> n_api : id = 48214
note over n_api, n_db_2 : Patch: odd ids on one shard, even on the other
n_api -> n_db_2 : ALTER SEQUENCE orders_id_seq
n_db_2 --> n_api : ALTER SEQUENCE
note over n_client, n_api : Let the service make the id: random UUID
n_client -> n_api : POST /orders HTTP/1.1
n_api --> n_client : HTTP/1.1 201 Created
note over n_api, n_db_1 : Random keys tear the index apart
n_api -> n_db_1 : SELECT avg_leaf_density, leaf_fragmentation
n_db_1 --> n_api : 61.2 | 48.7
note over n_client, n_api : UUIDv7: time first, randomness after
n_client -> n_api : POST /orders HTTP/1.1
n_api --> n_client : HTTP/1.1 201 Created
note over n_api_2, n_db_2 : Smaller still: time + machine + sequence in 64 bits
n_api_2 -> n_db_2 : DEBUG new id 250413553075367937
note over n_ntp, n_api_2 : The clock moves back and an id repeats
n_ntp -> n_api_2 : INFO clock step: -40 ms (offset from server 0.040 s)
note over n_api_2, n_db_2 : Never go below the last timestamp
n_api_2 -> n_db_2 : WARN clock behind last id by 40 ms, waiting
@endumlPlantUML: components
@startuml
left to right direction
agent "App" as n_client
component "Orders API" as n_api
database "Shard 1" as n_db_1
database "Shard 2" as n_db_2
component "Orders API #2" as n_api_2
cloud "Time server" as n_ntp
n_client --> n_api
n_api --> n_db_1
n_api --> n_db_2
n_client --> n_api_2
n_api_2 --> n_db_2
n_ntp --> n_api_2
@endumlRecap
A database counter is perfect until there is more than one database.
1) Generate ids in the service, not per shard. 2) Prefer time-ordered ids (UUIDv7, ULID, time + machine + sequence) over random ones: the index stays compact. 3) Give every generator a unique machine number. 4) Never issue an id with a timestamp below the last one: wait, or refuse.
Numbers: at the start and at the end
| Metric | Start | End |
|---|---|---|
| Insert p95 | 4 ms | 6 ms |
| Duplicate ids | 0/day | 0/day |
| Index page splits | 2/s | 3/s |
Steps
- Case One database, one counter
Every new order gets its id from the database: a sequence that only goes up.
- Problem Two shards, two counters, same numbers
Orders are split by user across two databases.
- Fix Patch: odd ids on one shard, even on the other
Both counters now step by 2 and start apart: shard 1 gives odd numbers, shard 2 even ones.
- Fix Let the service make the id: random UUID
The API now creates the id itself before the insert: a UUIDv4, 122 random bits.
- Problem Random keys tear the index apart
The primary key index is a B-tree kept in key order.
- Fix UUIDv7: time first, randomness after
UUIDv7 keeps the same 128-bit format, but its first 48 bits are the current time in milliseconds.
- Case Smaller still: time + machine + sequence in 64 bits
A second API server joins.
- Problem The clock moves back and an id repeats
The time server tells API #2 that its clock is 40 ms ahead.
- Fix Never go below the last timestamp
The generator remembers the time of its last id.
- Recap Recap
A database counter is perfect until there is more than one database.
Terms
- UUIDv7
- A 128-bit id whose first 48 bits are the time in milliseconds and the rest is random. New ids land at the end of the index, so it does not tear a B-tree apart like random UUIDv4.
- Snowflake ID (time + machine + sequence)
- A 64-bit id made of milliseconds since a chosen epoch, a machine number and a counter within that millisecond. Each server makes ids alone, and waits or refuses if its clock moves back.