Distributed ID Generator · Analysis

01 · Frame the problem

Understand the central challenge

Design a service issuing sortable 64-bit IDs across several workers. Network partitions and worker restarts must not silently reuse identities. State exactly what chronological ordering can and cannot mean.

Uniqueness depends on worker ownership and restart/clock behavior as much as the bit layout. Establish the issuance envelope before choosing timestamp, worker and sequence field sizes.

02 · Find the design pressure

Start simple, then identify the gap

Begin with one serialized generator and a specified encoding. Adding workers without exclusive identities permits collisions; wrapping a sequence or rolling time backward reuses tuples. Define conservative stop/wait behavior instead of sacrificing uniqueness for availability.

Use explicit timestamp/worker/sequence fields with serialized per-worker generation and conservative issuance bounds. Uniqueness depends on exclusive worker identity ownership and safe persisted restart state. Choose an epoch and millisecond ticks. A 41/10/12 layout offers 1024 worker slots and 4096 IDs per worker per tick within the timestamp lifetime. Return IDs as decimal strings to clients that cannot represent 64-bit integers exactly. Provision worker IDs exclusively through a registry. This design does not automatically reassign an uncertain worker slot: drain or otherwise prevent the old issuer from running before reuse. Registry leases alone are insufficient to fence returned IDs. Persist a reserved timestamp high-water bound before issuing inside that window. After restart, refuse issuance until actual safe time is beyond the previous reserved window; reserve another window durably. A registry/store failure blocks new reservation, not permission to reuse old IDs. Under a per-worker lock, clamp no timestamp backward: wait with a deadline or fail on regression. Reset sequence only on a new tick; on exhaustion wait for a safe tick. Reject timestamps outside the bit lifetime.

03 · Define success

Requirements to preserve

Define timestamp, worker and sequence bit allocation.
Prevent concurrent or restarted workers from reusing a worker identity unsafely.
Handle regressing clocks and exhausted per-tick sequences.
Avoid claiming global strict ordering across unsynchronized workers.

Workload: 1,000 reads/s, 50,000 writes/s, 100 B records, 100 ms read p99 target. These are exercise assumptions; the Solution includes capacity formulas.

04 · Identify the correctness boundary

Consistency, ownership and failure boundaries

Specify bit widths and overflow behavior before implementing shifts. A worker identity must remain exclusive across partitions and restarts; a lease name alone is insufficient if an old process can keep issuing IDs. Persist conservative issuance bounds and stop when clock or ownership assumptions cannot be established.

05 · Make it concrete

Reason through a worked example

A worker exhausts its per-millisecond sequence while the clock has not advanced. It waits or returns bounded backpressure instead of wrapping. After a restart, it respects its persisted issuance boundary. A clock rollback cannot cause reuse of the same timestamp, worker and sequence tuple.