Design a Distributed Unique ID Generator (Snowflake)

To design a globally unique, monotonically increasing ID generator, I would adapt the Snowflake algorithm while addressing its specific challenges. First, I'd define the requirements: we need roughly 10 billion IDs daily with sub-millisecond generation latency. The structure would use a 64-bit integer split into four parts: a sign bit (ignored), a 41-bit timestamp in milliseconds since an epoch, a 10-bit machine ID, and a 12-bit sequence number. The timestamp ensures sortability; however, since clocks can drift, I must handle clock skew. If the current time is less than the last recorded time, the system waits or uses the previous timestamp with an incremented sequence. To ensure uniqueness across thousands of nodes, each node requires a unique machine ID, perhaps assigned via a lightweight registry service that supports high availability through sharding. For high availability, the machine ID assignment service should be replicated, and nodes could cache their IDs locally to avoid network calls during peak load. While this sacrifices strict monotonicity slightly during clock adjustments, it maintains global uniqueness and near-linear scalability, which aligns with Google's focus on massive throughput and reliability.