Unique ID Generator: ID Generation Strategies

• ID Format Example: Using this structure, an example 64-bit ID in binary might look like:

  [timestamp: 41 bits][region+machine: 10 bits][seq: 12 bits]

  For illustration, suppose the 41-bit timestamp (since epoch) is 101010... (some value), region ID = 3 (00011 in 5 bits), machine ID = 5 (00101 in 5 bits), and sequence = 37 (0000 1001 01 in 12 bits). These bits concatenate to form the 64-bit number. In a real example, Snowflake ID 1922298559865028608 (which is a tweet ID) breaks down to timestamp, machine, sequence as documented. Because of this composition, one can extract the time and other info if they know the format, which is why we categorize it as non-opaque. But it serves the ordering and scaling purpose well.

• Machine ID Coordination: We will run a ZooKeeper (or similar) cluster that manages the 10-bit machine IDs. When an ID generator node starts, it will create an ephemeral node in ZooKeeper like /id-generators/<region>/<machine_id>. ZooKeeper can be configured to auto-assign an ID or the node can attempt to create nodes with incremental IDs until it finds a free one. Another approach is to have the node supply its region and ask ZooKeeper for a free machine slot in that region. For example, region 1 nodes can use IDs 0-31. ZooKeeper ensures two live nodes don't get the same ID by keeping track of active ephemeral nodes. If a node goes down, its ZK ephemeral node is removed, freeing up that ID for reuse. We must be careful with reuse: ideally, we don't immediately reuse a machine ID of a node that just went down until we're sure its clock won't cause issues. In practice, since the node is down, it won't generate new IDs, so reuse is safe if the new node's clock is >= the last timestamp of the old node. We might add a small buffer or record of last timestamp to avoid edge cases (more on clock issues below).

  • Failure scenario: If ZooKeeper itself fails, existing ID nodes can continue to generate IDs with their already-assigned IDs (no impact). We just wouldn't be able to start new nodes or reassign IDs until ZK is back. To mitigate that, we run ZK as a 3-node ensemble across different servers (and possibly across regions) so that it's highly available. The ID generator is not very sensitive to short ZK outages, as it rarely changes state after initial assignment.

• Clock Synchronization and Handling Skew: All Snowflake-like systems depend on system clocks moving forward reasonably in sync. We will ensure that all generator nodes run NTP (Network Time Protocol) daemons to keep their clocks accurate to a few milliseconds. Minor clock differences mean one node's IDs might appear slightly out-of-order compared to another's in wall-clock time, but it won't cause duplicates. The real risk is if a clock jumps backward on a node (e.g., an NTP correction or VM pause causes time to go back). Suppose node A's clock goes 100ms backwards - suddenly its timestamp may duplicate a range it had already used. To prevent collisions:

  • Each node's algorithm will track the last timestamp used. If the current system time is less than the last timestamp, the generator will pause until the clock catches up beyond the last timestamp. For small skews, this is quick. For larger jumps, this essentially means the service on that node is stalled for that duration (worst case, an operator alert might be needed if the machine's clock is really off). This pause prevents it from generating IDs that could duplicate previously generated ones.
  • In practice, significant backward jumps are rare if NTP is configured with small adjustments. If a large jump does occur (say someone manually changed the clock), the safe approach might be to restart the service with a new machine ID (treat that node as a new instance) so it doesn't overlap its past timeline.
  • We could also record the last timestamp to stable storage on shutdown and refuse to start if time is behind that, but given we prefer stateless, a simpler runtime check is sufficient.
  • Clock moving forward too fast (jumping ahead) is less dangerous for uniqueness (it'll just produce very large timestamp values, which are still unique). But it could create a gap in the time ordering compared to other nodes. We don't specifically prevent that, but NTP usually smooths adjustments to avoid big leaps. If a node's clock jumped far into the future and generated IDs, then reverts, subsequent IDs from that node will have lower timestamps than it previously produced - which could break the sorting property slightly (those future IDs would appear as outliers). However, they'd still be unique. This situation is unlikely, but in extreme cases, manual intervention (like configuring NTP to step slowly or restarting the service after a big time correction) can manage it.

• Concurrency and Throughput on a Node: The generation algorithm on a single node can be made very fast. It essentially does: read clock (time in ms), if same as last time -> increment sequence; if new time -> reset sequence=0. Then compose bits into ID. This can be done in a few CPU instructions. We will implement this carefully to handle concurrent calls on a multi-threaded server:

  • Use a lock or atomic compare-and-swap on the timestamp and sequence values. Since this is very low-level, the overhead is minimal. Alternatively, some implementations use a single thread or coroutine to generate IDs sequentially to avoid locking and just feed an internal queue - but given the simplicity, even a locked section that does a couple of comparisons and increments can handle millions of ops/sec in modern CPUs. Our target ~100k/sec per node is easily handled with a lock (that's only 100k lock operations per second, trivial for a CPU).
  • If throughput per node needs to be higher, we could partition sequence ranges among threads (e.g., thread 1 uses sequence 0 to 2047 and thread 2 uses 2048 to 4095 within the same millisecond). But this adds complexity and likely isn't needed unless a single machine must push the absolute limits. With multiple nodes available, we prefer to scale out rather than overly optimize one node's multi-threading beyond necessity.
  • The node will likely run as a stateless service (maybe an HTTP server or RPC server). Each incoming request triggers the ID generation routine. This routine should be extremely fast (microseconds), so the majority of request latency will be network overhead. We can thus handle many requests per second per thread. If needed, the service can pipeline or batch internally, but likely one ID per request is fine given the throughput.

• Integration with the API: The generator node will format the 64-bit ID into the response. Often, systems return Snowflake IDs as decimal strings (Twitter, for example, exposes tweet IDs as large decimal numbers). We can do the same, or return as JSON number. Clients (especially in languages that can handle 64-bit ints) can treat it as an integer. Some databases might store it as a BIGINT. We must ensure that any client in JavaScript (which loses precision beyond 53-bit for numbers) gets it as a string to avoid precision issues. That's more of an API detail, but worth noting for implementation.

6.3 Opaque ID (UUID) Generation Design

For the opaque IDs, our design is simpler:

• We will use a 128-bit UUID version 4 style generation. This essentially means: generate 16 random bytes using a CSPRNG (cryptographically secure pseudo-random number generator). Ensure the proper bits for UUID version and variant are set (UUID v4 requires certain bits to indicate it's random). This yields an identifier such as f47ac10b-58cc-4372-a567-0e02b2c3d479 (the canonical 8-4-4-4-12 hex digit format with hyphens). We can also choose to output it as a 32-character hex string without hyphens, depending on preference. The exact format doesn't affect uniqueness.
• Uniqueness and Collision: The chance of two 128-bit random values colliding is so incredibly low that we consider it impossible for practical purposes. As a cited estimate, generating 1 billion random UUIDs per second for 100 years gives a ~50% chance of one collision. Our system generating maybe 10^10 per day is nowhere near that scale. Thus, we don't need any coordination or checking for duplicates. We trust the large address space. (We will use a good source of randomness; most languages provide secure RNG suitable for UUIDs, or even library functions to directly get a UUID.)
• Performance: Generating a random 128-bit number is very fast. The bottleneck might be converting it to string or formatting with hyphens, but that's also trivial at our scale. Modern CPUs can generate millions of random numbers per second. Even with locking around a RNG, it's not a problem to do 100k/sec. If needed, we can use thread-local RNG instances to avoid contention. The latency added per request is negligible (cryptographically secure RNG might be slightly slower than a normal RNG, but still microsecond-level per generation).
• Statelessness: Each call is independent. We don't have to remember anything between calls. That means any node can handle an opaque-ID request at any time. We don't even need the coordination service for this mode except to ensure the same nodes aren't also accidentally generating the same random (which is statistically implausible anyway). There is no sequence or time to manage.
• Security & Opaqueness: The generated ID is effectively meaningless to an outsider. It does not reveal the time or the origin. This is ideal for cases where IDs might be visible in URLs or through APIs and we don't want users to infer how many items exist or when something was created. (For example, if user IDs were sequential, a malicious actor could scrape and guess valid IDs; using opaque random IDs mitigates that, at the cost of not being able to sort by creation without an external timestamp field).
• API Integration: The service will return the opaque ID likely as a string in UUID format. For example: {"id": "de305d54-75b4-431b-adb2-eb6b9e546014"}. Clients will treat it as an opaque token. If they need to store creation time, they must store that separately because the ID itself doesn't convey it. In some cases, we might decide to use UUIDv7 (which is time-based) or ULID for opaque IDs if we wanted slight ordering, but that would leak time, making it not truly opaque. So we stick to purely random for the opaque variant. (We can document to clients that if they require ordering, they should use the time-sortable IDs; if they require non-guessable IDs, use opaque).

6.4 Data Storage and State Management

Our chosen design deliberately minimizes persistent storage:

• No ID database: We are not storing each generated ID in any database or log (beyond transient logs perhaps for debugging). This means the system doesn't build up a storage burden proportional to IDs generated. We avoid the complexity of a distributed DB or cache to store IDs. The uniqueness is guaranteed by design rather than by checking against stored records. This is crucial for scalability (imagine trying to insert 100k keys/sec into a DB - not feasible without huge infrastructure). Instead, uniqueness is pre-guaranteed by the algorithm (via time + machine + sequence uniqueness, or via randomness space).
• Coordinator storage: The only storage of note is in the coordinator (ZooKeeper/etcd). ZooKeeper will store small znodes for each active worker (e.g., a few bytes each with maybe the worker's address or ID). This is on the order of at most a thousand entries, which is tiny. ZK keeps this in memory and its own transaction log on disk (which is minimal here). The coordinator state is important to preserve (so that if everything restarts, we don't double-assign IDs). But since it's only a few entries, even a backup or reload is trivial. In worst case, if coordinator data is lost and all nodes restart, we could temporarily risk duplicate assignments - to prevent that, we'd either have a convention (like each node configured with an ID manually in that scenario) or require coordinator recovery. Generally, we will treat coordinator data with care (e.g., run it with persistence on disk, even though we use ephemeral nodes, we might also maintain a mapping record).
• Monitoring and Logging: We will have logs for operations and possibly an audit trail for issued IDs (at least for a short window) in memory to detect any anomaly (like duplicate detection). But logging every single ID to disk is not practical. Instead, we might log counts per second or significant events (like if the sequence had to roll over or if a clock went backward event happened). These logs help in debugging but are not part of the functional data path.
• Data for ID Validation: If needed, our service could offer a method to parse/validate IDs (e.g., given a purported ID, confirm if it's a valid format and maybe decode timestamp). This doesn't require stored data - it's purely algorithmic (e.g., check length or bit patterns). For Snowflake IDs, one can decode the timestamp by shifting right 22 bits (in our 64-bit scheme) and adding the epoch, etc. That could be a utility API but not a major component.

6.5 Failure Recovery Details

• Generator Node Failure: If an ID generator instance crashes or is removed, any IDs it already issued remain valid (they're just numbers, already used by clients). The coordinator will detect the session loss (e.g., ZooKeeper notices the ephemeral znode gone) and free up that machine ID. Our system can automatically spin up a new generator instance (if using an orchestrator like Kubernetes or auto-scaling group) to replace it. The new instance will register and likely get the same machine ID if it's the next available in that region. If it does get the same ID, we rely on the clock handling to avoid duplicate IDs. (We assume the new instance's clock is current; if by chance the old instance had a slightly ahead clock, the worst case is the new one might produce IDs slightly lower than the old's last ones, but since the old one is offline, duplicates still won't occur - those lower IDs were never generated before). To be extra safe, we could configure that a restarting node uses a different machine ID than a recently failed one, but that may reduce our ID space if not managed. Given synchronized clocks, this isn't a major concern.

• Datacenter Outage: If an entire region's datacenter goes down, those nodes stop generating. Clients can be configured to failover - e.g., the load balancer could route requests to a secondary region. Since region is encoded in IDs, an ID from a different region will still be unique. There's no dependency between regions, so other regions continue normally. When the down region comes back, its nodes might start again (with time caught up) and generate IDs with their region bits, which will be higher than anything they generated before the outage (because the timestamp will be later). We should ensure the epoch and time bits make sense - if a region is down for a long time, it just wasn't producing IDs, which is fine. There's no "hole" problem globally, since IDs don't need to be contiguous - uniqueness is enough.

• ZooKeeper Failure: As mentioned, if the coordinator cluster (ZK) fails completely, no new nodes can join and if it's down for long, an existing node losing session might be unable to re-establish (which in worst case could cause it to stop if it was programmed to require an active ZK session; we could design the generator to continue with its last known ID if ZK is down, to be more robust, as long as it doesn't detect a conflict). We mitigate this by having a reliable ZK setup. Also, because ZK only manages node IDs and not each request, even a slow ZK doesn't affect generation throughput. The system is mostly decoupled from ZK at runtime (especially if all nodes are already assigned). We might implement a cache such that if ZK is temporarily unreachable, a node just continues using its assigned ID until it can reconnect (this avoids it shutting down unnecessarily). Once ZK recovers, it can reconcile any changes. This is an engineering detail but ensures high availability.

• Duplicate ID Safeguards: Although our logic guarantees uniqueness in theory, we can add runtime checks in debug mode - e.g., each node could keep a sliding window of recent IDs it generated (or just the last generated ID) to assert that new IDs are always larger (for time-sortable) or not equal to the last (for random). This is mainly to catch any bug. In production at scale, storing even a million recent IDs per node is too much overhead, but storing the last one or last timestamp is fine. We rely on the mathematical guarantees for the rest.

• Scaling Beyond 1024 Nodes: If we ever needed more generator nodes concurrently (say the service became so popular we needed more than 1024 instances to handle load, or more than 32 regions, etc.), we have a few options:

  • Increase the machine ID bits (at expense of reducing timestamp bits, shortening the time range). For example, 12 bits for machine and 10 for sequence (instead of 10/12) would allow 4096 nodes but only 1024 IDs/ms per node. If we had so many nodes, likely per-node throughput isn't a problem, so that trade-off could work.
  • Or deploy a second independent Snowflake service with a different epoch or different ID namespace (like prefix the IDs differently). But that complicates clients having to coordinate which service to call.
  • Given each node can handle millions per second, needing >1024 concurrently active nodes is unlikely unless each is limited by other factors (like network or CPU). In practice, we likely won't hit this limit. 1024 nodes, each producing millions of IDs per second, is vastly above our target of 100k/sec.

In conclusion, our detailed design chooses the Snowflake algorithm to fulfill the time-sortable, high-throughput ID needs, and a UUID-like random approach for opaque IDs. This covers both functional requirements. By carefully managing the bit schema, machine ID assignment, and clock behavior, we ensure global uniqueness and reliability. The design is proven in production (Twitter's Snowflake and its derivatives), which shows it works at scale. Meanwhile, using UUIDs for opaque IDs uses a well-understood standard for uniqueness.