System Design Basics 1. Globally Unique ID Generator

Globally unique IDs are ubiquitous in distributed systems. Companies use globally unique IDs to distinguish a lot of things, visitors, orders, transactions, and tweets, just to name a few. In a distributed system, we need a Globally Unique ID Generator that’s highly performant, highly available, fault-tolerant, and can generate thousands or even millions of IDs per second. It’s unlikely you will be asked to design a Globally Unique ID Generator in a real interview, but you might need one as an auxiliary system to generate IDs for the main system you are asked to design. In this article, we will go through four solutions for generating globally unique IDs.

Relational Database

Relational Databases such as MySQL come with the AUTO_INCREMENT feature that can generate unique IDs for new rows. This uniqueness is only guaranteed within the same database. In a distributed system, you would need to have multiple databases to prevent a single point of failure. To generate unique IDs among databases. You can set auto_increment_offset differently for each database and set auto_increment_increment to be the number of databases, as shown below. Once the databases are set up correctly, you can put them behind a load balancer so requests can be distributed evenly among the databases. If one database goes down, it won’t affect the others. Once it’s fixed, we can put it back into the pool and it can resume from the last ID generated.

-- For Server 1, this will generate ids 1, 6, 11, ...
SET GLOBAL auto_increment_offset=1;
SET GLOBAL auto_increment_increment=5;
-- For Server 2, this will generate ids 2, 7, 12, ...
SET GLOBAL auto_increment_offset=2;
SET GLOBAL auto_increment_increment=5;
-- For Server 3, this will generate ids 3, 8, 13, ...
SET GLOBAL auto_increment_offset=3;
SET GLOBAL auto_increment_increment=5;
-- For Server 4, this will generate ids 4, 9, 14, ...
SET GLOBAL auto_increment_offset=4;
SET GLOBAL auto_increment_increment=5;
-- For Server 5, this will generate ids 5, 10, 15, ...
SET GLOBAL auto_increment_offset=5;
SET GLOBAL auto_increment_increment=5;

Redis

Another way to generate unique IDs is to use Redis. You can use the INCR command to get a unique number and the atomic nature of the command guarantees that each connection will get a unique number. To get a globally unique number, you can use the same technique as mentioned in the MySQL solution. For example, if you have 5 Redis instances, you can set the starting number as 1, 2, 3, 4, and 5 for each instance respectively, and use INCRBY key 5 on each instance.

Generate IDs without using databases or caches

You also can create globally unique IDs without using any of the databases or caches as mentioned above. For example, languages like Java already have atomic classes such as AtomicInteger. We can use methods like incrementAndGet to safely get a unique number. To get a globally unique ID, we just need to concatenate the server ID with the number. This is also how globally unique ID generator such as Twitter’s Snowflake system is based upon.

UUID

The last approach to generate globally unique IDs is to use UUID. UUIDs are 128-bit numbers and represented as 32 base-16 characters, for example, 6dc6a798-e855–4528–8a59–463883a024a1. One of the benefits of UUIDs is that they don’t need to be issued by a central authority and can be generated independently. To use it, you just need to import the library and call the method to generate the IDs. The chances of collision are practically none. This means any of our web servers can generate UUIDs and uniqueness is guaranteed among them. Theoretically, UUIDs can have collisions, but that’s only possible if you are generating a billion per second, for many many years. UUID is good for non-critical use cases when collision doesn’t cause major issues for the system.