Unique ID Generator

Every large system needs IDs for posts, orders, and messages that are unique across many machines and data centers. The interesting part is producing them at high rates without a central bottleneck, while keeping them compact and roughly sorted by time.

Clarify requirements

Functional

• nextId() returns a unique ID.
• IDs are 64-bit integers (fit in BIGINT, compact in indexes).
• IDs are roughly ordered by creation time (k-sortable), so sorting by ID ≈ sorting by time.
• Optionally, extract the creation timestamp from an ID.

Non-functional

• 1M+ IDs per second across the fleet; generation latency under 1 ms (ideally in-process).
• Highly available: ID generation must never be the reason writes fail.
• Works across multiple data centers.
• No duplicates, ever, including across restarts and clock adjustments.