mufassall

Cheat sheet · Data & storage

Unique IDs

12 min · Intermediate · mufassall.dtwin.uz/en/l/unique-ids/

← Open the lesson

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
Final scene
20%32%20%31%

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_2

Mermaid: 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, waiting

D2

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_2

PlantUML: 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
@enduml

PlantUML: 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
@enduml

Recap

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

MetricStartEnd
Insert p954 ms6 ms
Duplicate ids0/day0/day
Index page splits2/s3/s

Steps

  1. Case One database, one counter

    Every new order gets its id from the database: a sequence that only goes up.

  2. Problem Two shards, two counters, same numbers

    Orders are split by user across two databases.

  3. 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.

  4. Fix Let the service make the id: random UUID

    The API now creates the id itself before the insert: a UUIDv4, 122 random bits.

  5. Problem Random keys tear the index apart

    The primary key index is a B-tree kept in key order.

  6. Fix UUIDv7: time first, randomness after

    UUIDv7 keeps the same 128-bit format, but its first 48 bits are the current time in milliseconds.

  7. Case Smaller still: time + machine + sequence in 64 bits

    A second API server joins.

  8. Problem The clock moves back and an id repeats

    The time server tells API #2 that its clock is 40 ms ahead.

  9. Fix Never go below the last timestamp

    The generator remembers the time of its last id.

  10. 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.