Design a distributed unique id generator

We need to create a unique ID generator for our high-traffic web application, generating about 10K IDs/second.

The IDs can't simply be monotonically increasing integers, which are good for data access but pose a security concern with enumeration attacks.

For unique integers, we could limit it to a single generator. This is a single point of failure, and producing IDs at a high rate would be hard. Having multiple generators for resilience requires coordination, adding complexity.

Generating UUIDs on the device forgoes the coordination issues, allowing us to scale horizontally. UUIDv4 is the current standard, using 122 bits of entropy to effectively guarantee uniqueness.

However, using these as primary keys for databases negates any data locality optimizations of indexes. Twitter's Snowflake IDs or UUIDv7 reserve the higher order bits for the timestamp and the lower order bits for randomness (or a counter), allowing for sorted IDs and reducing thrashing.

With a reduced level of randomness, one would be worried we could get duplicates. Don't be, it would take centuries.

Happy hackin'!

References

This article is part of the system design series where I am summarizing chapters from The System Design Interview: Volume 1 / Volume 2 amongst other related content