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

Design a distributed unique id generator

Comments

System Design

Design a url shortner

More from this blog

8 Simple reminders

Design a url shortner

No regrets

luck surface area

References

Command Palette

Comments

System Design

Design a url shortner

More from this blog

References