Markdown Editor

Distributed Unique ID Generator System Design Template

UUIDv4 and v7 per RFC 9562, Snowflake 41/10/12 layout, clock skew and backwards clocks, leased worker IDs, index locality, 53-bit JS limit, ticket servers

System DesignFullRFC 9562 (May 2024)designuniquegeneratormath

How to use: Use it when choosing an ID format for sharded databases or APIs, or practising the ID generator interview. Fill the peak rate and the number of generating processes first, because worker bits run out before sequence bits. The main pitfall is sending 64-bit IDs as JSON numbers, which JavaScript clients silently round above 2^53.

Preview

System Design: [Unique ID generator name]

Reference design for a distributed unique ID generator: when to use UUID version 4 or version 7 (RFC 9562, May 2024), how a Snowflake-style 64-bit layout works, how to survive clock skew and clocks that move backwards, how to assign worker IDs safely, what sortability buys for database indexes, why JavaScript clients need IDs as strings above 2532^{53}, and when a database ticket server is still the simplest answer. It follows the structure of the System Design Document template, adds a 45-minute interview path, access-pattern and failure-mode tables, and is pre-filled with a worked design to adapt. Replace every [bracketed] value and every row marked Example; values marked Example are assumptions, not benchmarks.

Document control

FieldValue
Document ID[SDD-UID-001]
System / feature[Distributed ID generation]
Version[0.1]
Status[Draft / In review / Approved / Implemented / Superseded]
Owner[@owner]
Author(s)[@author]
Reviewers[@reviewer-1], [@reviewer-2]
Last updatedYYYY-MM-DD
Classification[Internal]
ID formats in use[UUIDv7 / Snowflake-style 64-bit / ticket server]
Custom epoch[YYYY-MM-DDTHH:MM:SSZ]
Related[Database schema standards], [API style guide], [ADR: ID format]

Approvals

RoleNameDecisionDate
Tech lead[@name][Approved / Changes requested]YYYY-MM-DD
Staff / principal engineer[@name][Decision]YYYY-MM-DD
Database owner[@name][Decision]YYYY-MM-DD
API and client leads[@name][Decision]YYYY-MM-DD
SRE / operations[@name][Decision]YYYY-MM-DD

Revision history

VersionDateAuthorChange summary
0.1YYYY-MM-DD[@name]First draft for design review
0.2YYYY-MM-DD[@name]Example: Switched worker IDs from static config to leases
0.3YYYY-MM-DD[@name]Example: IDs serialised as strings in all JSON APIs
1.0YYYY-MM-DD[@name]Example: Approved

Contents

1. Overview

1.1 Problem statement

[Example: Each service uses its own database auto-increment column. After splitting the orders database into 16 shards, two shards issued the same order number, and merging data for analytics needs a shard prefix everywhere. Some teams switched to random UUIDs, which made insert-heavy tables slower and IDs no longer sort by creation time.]

1.2 Proposed solution

[Example: Two approved ID formats. Internal high-volume tables use a 64-bit Snowflake-style ID: 41 bits of milliseconds since a custom epoch, 10 bits of worker ID and 12 bits of sequence, generated in-process by a library. Worker IDs are leased from a coordination store and renewed every 10 s, so no two live processes share one. Records that are created on devices or shared across organisations use UUIDv7. All JSON APIs send 64-bit IDs as strings. A database ticket server remains for the few tables that need dense, gap-tolerant counters.]

1.3 Decisions requested from reviewers

IDQuestionRecommended optionSection
Q-01Example: Default format for new tables?Snowflake-style 64-bit for high-volume internal tables; UUIDv7 elsewhere7.1
Q-02Example: How are worker IDs assigned?Leases in the coordination store with fencing on expiry7.4
Q-03Example: What happens when the clock goes backwards?Wait up to 5 ms, then refuse and alert7.3
Q-04Example: Number or string in JSON?String7.6
[Q-nn][Question][Option][Section]

1.4 45-minute interview path

Use this order when the document serves an interview or a short review.

MinutesCoverOutput on the whiteboard
0 to 5Scope: unique, 64-bit or 128-bit, sortable by time, rate; below-the-line itemsFour properties
5 to 10Estimates: IDs per second, generating processes, lifetime of the layoutBit budget with a consequence for each field
10 to 15Options: auto-increment, ticket server, UUIDv4, UUIDv7, SnowflakeComparison table
15 to 25High-level design: in-process library, lease store, decode toolOne diagram
25 to 40One deep dive: clock skew and backwards clocks (default), or worker ID assignmentOptions, choice, reason
40 to 45Failures, the 53-bit client limit, 10x changeFailure rows

The interviewer usually wants to see the bit layout with its arithmetic and a clear answer to "what if the clock goes back". Draw the 64 bits early.

2. Requirements

2.1 Core functional requirements

IDRequirementPriority
FR-01Example: IDs are unique across all services, regions and timeMust
FR-02Example: IDs fit in a signed 64-bit integer for high-volume tablesMust
FR-03Example: IDs sort roughly by creation time (within a few milliseconds across machines)Must
FR-04Example: Generation works without a network call on the hot pathMust
FR-05Example: The creation time can be decoded from an ID for debuggingShould
FR-06Example: Records created offline on devices get IDs without a serverShould (UUIDv7)
[FR-nn][Requirement][Must / Should / Could]

2.2 Non-functional requirements

IDQualityTargetMeasured as
NFR-01ThroughputExample: 1 million IDs/s globally at peak; 50 000/s per processLoad test
NFR-02LatencyExample: under 1 microsecond per ID in-process at p99Benchmark
NFR-03AvailabilityExample: Generation continues for 10 minutes if the lease store is downChaos test
NFR-04UniquenessExample: Zero duplicates, checked by unique constraints and a sampling jobDuplicate detector
NFR-05Layout lifetimeExample: At least 50 years from the custom epochArithmetic in 3.3
[NFR-nn][Quality][Target][Measurement]

2.3 Below the line (out of scope)

  • [Example: short human-readable codes such as booking references (see URL Shortener System Design, system-design/design-url-shortener, for encoding)]
  • [Example: gap-free invoice numbers required by tax law (a per-series counter in the ledger database)]
  • [Example: hiding creation time or volume from customers (would need encrypted or random IDs)]
  • [Example: strict global ordering of events (needs a sequencer or consensus, not an ID scheme)]
  • [Item deferred, with the release that will take it]

3. Capacity estimation

3.1 Assumptions

InputSymbolValueSource
Peak IDs per second, all servicesGGExample: 1 millionWrite traffic forecast
Processes that generate IDsppExample: 1 500Deployment inventory
Peak IDs per second in the busiest processggExample: 50 000Profiling
Rows with an ID after 5 yearsNNExample: 10 billionData growth plan
Copies of each ID in indexes and foreign keysjjExample: 3Schema review

3.2 Sequence bits

With 12 sequence bits a worker issues 212=4 0962^{12} = 4\,096 IDs per millisecond, which is about 4.1 million per second per worker:

g1000=50 0001000=50 IDs per ms in the busiest process≪4 096\frac{g}{1000} = \frac{50\,000}{1000} = 50 \ \text{IDs per ms in the busiest process} \ll 4\,096

Consequence: the sequence field is far from the limit; we keep 12 bits and spend nothing on more.

3.3 Time bits and layout lifetime

241 ms=2 199 023 255 552 ms≈69.7 years2^{41} \ \text{ms} = 2\,199\,023\,255\,552 \ \text{ms} \approx 69.7 \ \text{years}

Consequence: 41 bits of milliseconds meet NFR-05 only if the epoch is recent, so we set a custom epoch at the launch date instead of 1970, which would already have used nearly 57 years.

3.4 Worker bits

10 worker bits give 210=1 0242^{10} = 1\,024 worker IDs, but p=1 500p = 1\,500 processes.

Consequence: we cannot give every process a permanent worker ID. Either IDs are leased only while a process runs and only to processes that generate IDs (7.4), or the layout changes (for example 12 worker bits and 10 sequence bits). We choose leases and audit that live generators stay below Example 800.

3.5 Storage cost of 64-bit versus 128-bit

Δ=N×j×8 B=1010×3×8 B=240 GB\Delta = N \times j \times 8 \ \text{B} = 10^{10} \times 3 \times 8 \ \text{B} = 240 \ \text{GB}

Consequence: 128-bit IDs would add about 240 GB of index and key storage (before replication) on the high-volume tables, plus larger indexes in memory. 64-bit stays the default for those tables; UUIDv7 is fine elsewhere.

3.6 Summary

QuantityEstimateDesign consequence
Per-worker rate50 per ms vs 4 096 per ms limit12 sequence bits are plenty
Layout lifetime~69.7 years from epochCustom epoch at launch
Worker IDs1 500 processes vs 1 024 IDsLeased worker IDs, generators only
Width240 GB saved at 10 billion rows64-bit for high-volume tables
JSON safetyIDs exceed 2532^{53} after about 25 days from epoch (7.6)IDs as strings in JSON

4. API design

4.1 Interfaces

InterfaceOperationPurpose
Librarynext_id() -> int64Generate one Snowflake-style ID in-process
Librarynext_uuid7() -> UUIDGenerate a UUIDv7
Librarydecode(id) -> {timestamp, worker, sequence}Debugging and support
ID service (for languages without the library)POST /v1/ids?count=100Batch of IDs over the network
Lease storeacquire, renew, release on a worker IDWorker ID assignment

4.2 Request and response examples

A batch request to the ID service, and a decode result:

POST /v1/ids?count=3 HTTP/1.1
{"ids": ["173946227268390913", "173946227268390914", "173946227268390915"], "format": "snowflake64", "epoch": "[YYYY-MM-DDTHH:MM:SSZ]"}
{"id": "173946227268390913", "timestamp_ms_since_epoch": 41472012345, "worker_id": 417, "sequence": 1}

The decoded example is about 480 days after the epoch, worker 417, sequence 1; recompute it with your own epoch. The IDs are strings so JavaScript clients do not round them (7.6).

4.3 Errors

CaseStatusBody type
Clock moved backwards beyond tolerance503 with Retry-Afterproblems/clock-regression
No worker lease held503problems/no-worker-id
Count above maximum batch400problems/batch-too-large

5. Data model

5.1 Snowflake-style 64-bit layout

BitsWidthFieldNotes
631SignAlways 0, so the value stays positive in signed 64-bit types
62 to 2241Milliseconds since custom epochAbout 69.7 years
21 to 1210Worker ID1 024 values, leased (7.4)
11 to 012Sequence4 096 IDs per millisecond per worker
id=(t−tepoch)×222+worker×212+seq\text{id} = (t - t_{epoch}) \times 2^{22} + \text{worker} \times 2^{12} + \text{seq}

5.2 UUID version 7 layout (RFC 9562)

FieldWidthContent
unix_ts_ms48Milliseconds since the Unix epoch, big-endian
ver4Version 7
rand_a12Random bits, or a sub-millisecond fraction or counter for monotonic ordering
var2Variant bits
rand_b62Random bits, or a counter continued from rand_a

UUIDv4 by contrast holds 122 random bits and no time, so it never sorts by creation.

5.3 Lease records

Leases live in the coordination store; ticket sequences live on the ticket servers. Neither is on the hot path of next_id().

5.4 Access patterns

QueryKey or index that serves itPartition key and rationale
Acquire a free worker IDScan for expires_at in the past, compare-and-setSingle small keyspace in the coordination store; 1 024 rows need no partitioning
Renew my leaseworker_id with my fencing_tokenSame keyspace; conditional write fails if someone else took it
Resume safely after restartlast_issued_ms for the workerStored with the lease so a new holder starts after the old holder's last time
Insert a row with a new IDPrimary key B-tree on the IDTime-ordered IDs append near the right edge of the index
Find recent rowsRange on the ID (time prefix)No separate created_at index needed for coarse time ranges
Next ticket numberTICKET_SEQUENCE.nameOne row per sequence on the ticket server

6. High-level design

ComponentResponsibilityScales by
ID libraryCompose IDs, guard the clock, hold the leaseWith each process
Coordination storeWorker leases with expiry and fencingSmall; three-node consensus cluster
ID serviceBatches for languages without the libraryStateless instances, each with its own lease
Ticket server pairDense counters with odd and even offsetsTwo database instances
Duplicate detectorSample new keys, alert on any duplicateBatch job

7. Detailed design

7.1 Deep dive: choosing an ID scheme

SchemeSizeSortable by timeCoordinationMain weakness
Database auto-increment64Yes, per databaseThe databaseSingle writer; collides across shards
Ticket server (auto-increment on dedicated hosts)64RoughlyA network call per ID or batchExtra dependency on the write path
UUIDv4128NoNoneRandom inserts spread across the whole index
UUIDv7128Yes, by millisecondNoneTwice the width of 64-bit
Snowflake-style64Yes, by millisecondWorker ID assignmentDepends on clocks and unique worker IDs

Choice: Snowflake-style for high-volume internal tables, UUIDv7 for records created on devices, exported, or merged across systems, ticket server only for existing dense counters. Reason: Snowflake fits 64 bits and sorts by time without a call on the hot path; UUIDv7 needs no worker assignment at all, which matters where we do not control the generator.

7.2 Deep dive: composing an ID

The library keeps last_ms and seq per worker under a lock or an atomic compare-and-set. Starting the sequence at a random small value each millisecond, instead of 0, spreads low bits for systems that shard by id mod n.

7.3 Deep dive: clock skew and clocks moving backwards

Clocks on different machines disagree by milliseconds, and a clock can step backwards when NTP corrects it or a virtual machine migrates. Disagreement between machines only blurs ordering; a backwards step on one machine can produce a duplicate if the same worker reuses old timestamps.

OptionBehaviourRisk
IgnoreKeep generating with the earlier timeDuplicates when the sequence repeats
WaitSleep until the clock passes last_msStalls for the size of the step
RefuseReturn an error until the clock catches upWrite errors during the step
Logical clockKeep using last_ms and advance it artificiallyTime in the ID drifts from real time

Choice: wait if the step is at most Example 5 ms; refuse and alert if larger. Configure NTP to slew (adjust gradually) rather than step, and persist last_issued_ms with the lease so a restarted process with a slow clock does not reuse time. Reason: small steps are common and waiting is invisible to users; large steps signal a broken host, which should stop generating rather than risk duplicates.

Ordering across machines is only as good as clock agreement. IDs are "roughly sorted": if two IDs are created within the skew window on different machines, their order may not match real time. Do not use ID order to decide which of two concurrent writes happened first.

7.4 Deep dive: worker ID assignment

OptionHowRisk
Static config per hostOperator assigns numbersCopy-paste duplicates, does not fit autoscaling
Derived from IP or host nameHash to 10 bitsCollisions are likely with hundreds of hosts
Lease from a coordination storeCompare-and-set a free worker ID with expiry and fencing tokenStore outage blocks new processes
Central ID service onlyFew service instances hold IDsNetwork call on the hot path

Choice: leases. A process acquires a worker ID with an expiry of Example 15 minutes and renews every 10 s. If renewal fails, it keeps generating until 30 s before expiry, then stops, so a lease store outage leaves about 14 minutes of generation and meets NFR-03 (10 minutes). The cost is that a worker ID held by a crashed process stays unusable for up to 15 minutes; clean shutdowns release it at once, and the pool keeps live generators below Example 800 of 1 024 for this reason. A new holder of the same worker ID starts only after the previous lease expired and only at a time later than the stored last_issued_ms. Reason: it fits autoscaling and makes duplicate worker IDs impossible as long as clocks advance, which 7.3 already guards.

7.5 Sortability and database indexes

Time-ordered IDs insert near the end of a B-tree primary key, so recent pages stay in memory and page splits stay rare. Random UUIDv4 keys land anywhere in the index, touching cold pages and fragmenting it, which slows insert-heavy tables. Time-ordered keys do create a hot spot on the last page in some distributed databases that range-partition by key; in those, hash-partition the table or put a shard prefix in front of the key.

7.6 The 53-bit JavaScript limit

JavaScript numbers are double-precision floats and represent integers exactly only up to 253−12^{53} - 1 (Number.MAX_SAFE_INTEGER). A Snowflake-style ID exceeds that once the time part exceeds 2312^{31} ms, because 231×222=2532^{31} \times 2^{22} = 2^{53}; 2312^{31} ms is about 24.9 days after the epoch. After that, JSON.parse silently rounds IDs and two different IDs can compare equal.

  • Send 64-bit IDs as JSON strings in every API, and keep them strings in client code.
  • If a numeric field must stay for compatibility, add a string field next to it and document that clients must use the string.
  • In JavaScript code that must do arithmetic on IDs, use BigInt.

7.7 Ticket servers

A ticket server is a database whose only job is to hand out numbers from an auto-increment column. Two servers with the same increment of 2 and offsets 1 and 2 give odd and even numbers, so either can serve if the other fails. Clients may fetch blocks of numbers to cut calls. It is simple and produces compact numbers, but IDs are only roughly ordered between the two servers, and every block fetch is a network call. Keep it for existing counters.

7.8 How real systems do it

How real systems do it (paraphrased, not copied). Twitter announced Snowflake in 2010 when moving storage away from a database that could issue sequential IDs. The archived project README describes the layout used in 5.1: a millisecond timestamp from a custom epoch, a machine number configured per host, and a per-machine sequence, with NTP recommended in a mode that never steps the clock backwards and a generator that refuses to issue IDs until time passes the last one it used. Flickr's 2010 post on ticket servers describes the odd and even database pair in 7.7. Instagram's 2011 post on sharding and IDs describes generating time-ordered 64-bit IDs inside each logical database shard, combining time, shard number and a sequence. Read the originals in 12.3; this box keeps only the general idea.

8. Scalability and performance

ConcernApproachLimit before redesign
Per-process rateIn-process generation with an atomic4 096 per ms per worker; add a second worker ID per process beyond that
Global rateNo shared state on the hot pathNone from the generator; worker IDs are the limit
Worker IDsLeases for generating processes only1 024 live generators
Lease storeSmall, renewals every 10 sExample: 1 024 renewals per 10 s, trivial load
ID serviceBatches of up to 1 000Network latency per batch

9. Reliability, security and operations

9.1 Failure modes

ComponentFailureDetectionBlast radiusMitigationRTO
Host clockSteps backwardsLibrary metric clock_regression_msOne processWait up to 5 ms; refuse beyond; slew-only NTPExample: seconds
Host clockRuns far ahead, then correctedTime vs. lease store timeIDs from that host sort in the futureCompare with store time at acquire; refuse if skew above 1 sExample: minutes
Coordination storeUnavailableRenewal errorsNew processes cannot start generatingExisting leases keep working until expiry; restore quorumExample: 10 min
Worker leasesExhausted (1 024 in use)Free lease countNew processes cannot generateAlert at 80%; release on shutdown; reduce generator countExample: 30 min
ConfigurationWrong epoch deployedDecode check in CI and canaryDuplicate or out-of-order IDsEpoch is a compiled constant with a testExample: rollback
Ticket serverOne of the pair downHealth checkHalf the counter capacityClients use the other serverExample: immediate
[Component][Failure][Signal][Scope][Mitigation][Time]

9.2 Security and privacy

ConcernControl
IDs reveal creation timeAccept for internal IDs; do not use time-ordered IDs where creation time is sensitive
Sequential numbers reveal volume (orders per day)Do not expose ticket-server numbers publicly; use Snowflake or UUIDv7 in URLs
IDs guessed to access other recordsAuthorisation on every read; an ID is never a secret or a capability
UUIDv4 or v7 with weak randomnessUse the platform's cryptographically secure generator
[Concern][Control]

9.3 Observability

SignalMetricAlert threshold
Clock regressionCount and size per hostAny above 5 ms
Sequence overflow waitsWaits per minuteSustained above 0 in one process
Lease healthFree worker IDs, renewal failuresFree below 20%; any failed renewal streak
DuplicatesUnique-constraint violations on ID keysAny

10. Trade-offs and alternatives

DecisionOptionsChosenWhyWhat we give up
Default formatAuto-increment; ticket server; UUIDv4; UUIDv7; SnowflakeSnowflake for high-volume, UUIDv7 elsewhere64-bit and sortable, or zero coordinationTwo formats to support
Worker IDsStatic; derived; leased; central serviceLeasedAutoscaling safeDepends on a coordination store
Backwards clockIgnore; wait; refuse; logical clockWait then refuseNo duplicatesRare write errors
Wire formatNumber; stringStringSafe in JavaScriptClients must not do arithmetic on IDs
Bit split41/10/12; custom41/10/12Known, lifetime fits1 024 worker limit
What changes at 10x / 0.1x10x processes: worker bits run out first, so move to 12 worker bits or route generation through an ID service. 0.1x: UUIDv7 everywhere and no lease storeReview with each platform changeProcess count, not ID rate, drives the design[Note]
[Decision][Options][Chosen][Why][Cost]

11. Delivery plan and risks

11.1 Milestones

MilestoneScopeExit criterionTarget date
M1Library with leases, clock guard, decode toolProperty tests and chaos test with clock steps passYYYY-MM-DD
M2New tables use the library; APIs send stringsContract tests in all clientsYYYY-MM-DD
M3ID service for other languagesBatch p99 under 5 msYYYY-MM-DD
M4Duplicate detector and dashboardsZero duplicates over 30 daysYYYY-MM-DD

11.2 Rollout and rollback

[Example: Existing tables keep their IDs; only new tables and new rows in migrated tables use the new format, chosen so new IDs are larger than all existing ones. Rollback stops the library from being used for new tables; IDs already issued remain valid forever.]

11.3 Risks

IDRiskLikelihoodImpactMitigationOwner
R-01Example: A client parses IDs as numbers and corrupts themMediumHighStrings only, contract tests, lint rule[@name]
R-02Example: Worker IDs exhausted after autoscaling growthMediumMediumAlerts at 80%, layout change plan ready[@name]
R-03Example: NTP misconfigured to step clocksLowHighHost baseline check, clock guard in the library[@name]
[R-nn][Risk][L / M / H][L / M / H][Mitigation][@name]

12. Appendices

12.1 Open questions

IDQuestionOwnerDue
OQ-01Example: Should the worker field split into region and worker bits?[@name]YYYY-MM-DD
OQ-02Example: Which UUIDv7 monotonic method does our library implement?[@name]YYYY-MM-DD
[OQ-nn][Question][@name]YYYY-MM-DD

12.2 Glossary

TermMeaning
Custom epochThe moment from which ID timestamps count, chosen near launch
Worker IDNumber that makes concurrent generators produce disjoint IDs
LeaseTime-limited exclusive right to a worker ID
Fencing tokenIncreasing number that lets the store reject an older holder
Roughly sorted (k-sorted)Sorted by time except within the clock skew window
Ticket serverDatabase host that only issues auto-increment numbers

12.3 References

ReferenceUse
RFC 9562, "Universally Unique IDentifiers (UUIDs)", IETF, May 2024 (obsoletes RFC 4122)5.2 UUIDv4 and UUIDv7 layouts
Twitter engineering blog, "Announcing Snowflake", June 2010, and the archived twitter-archive/snowflake README on GitHub5.1, 7.3, 7.8
Flickr engineering blog, "Ticket Servers: Distributed Unique Primary Keys on the Cheap", 8 February 20107.7, 7.8
Instagram engineering blog, "Sharding & IDs at Instagram", 20117.8
MDN Web Docs, Number.MAX_SAFE_INTEGER, and ECMA-2627.6
Xu, System Design Interview: An Insider's Guide (volume 1, 2020), chapter "Design a Unique ID Generator in Distributed Systems"Inspiration only; no text or figures reused
URL Shortener System Design (system-design/design-url-shortener)Short codes from IDs
Distributed Key-Value Store System Design (system-design/design-distributed-kv-store)Partitioning by key
Back-of-Envelope Estimation and Capacity Model (system-design/back-of-envelope-estimation)Method for section 3

Standard and licence note

Based on RFC 9562 for UUID formats and on common industry practice for Snowflake-style identifiers, using the public sources cited in 12.3. The book and engineering write-ups listed there are inspiration only; no text, diagrams or numbers were copied, and all figures here are illustrative examples. Check the current RFC errata and your language's UUID library before relying on a specific version or monotonic method. Original text written for this collection. Template licence: MIT.

Related templates