System design practice: distributed ID generation

Hiring for Tech
March 23, 2020

Tilt shift lens photo of stainless steel chain

The URL shortener problem is all about links. Photo by JJ Ying on Unsplash

It can be hard to get experience designing complex systems if you don’t previously have that experience. For that reason, I recently started a series on my personal blog on scalability concepts. Today, let’s explore distributed ID generation in the context of a very common systems design question: building a URL shortener.

The problem statement

Build a service where users can input URLs, and the service will return a short URL. Later, that short URL should redirect to the original URL. Common examples of this type of service are and TinyURL.

At its core, a URL shortener is a mapping from an arbitrary long URL to a short ID you store in your service. Given a short ID, you need to look up the long URL for redirection. (As part of the “requirements gathering state”, you might decide you want the reverse mapping too, in order to avoid generating two IDs for the same long URL.)

Once the mapping exists, doing the redirection is straightforward, so we’ll look at the ID generation.

Generating a short ID

The important part of the short ID generation is the short ID must be unique. If you give the service a long URL, whatever ID is generated must not be in use for another long URL. For a single-threaded, single server application, the requirement is easily met: generate a random short ID, check if it already exists in the database, then write to the database only if the ID didn’t exist.

The situation becomes more complicated as you handle more traffic. Let’s evaluate the different solutions in the blog post:

The URL shortener problem is a classic, partially because it’s easy to explain, but brings about some interesting scaling challenges if you take it to its limit. A lot of developers will never encounter these challenges, which is why I don’t think this problem allows for adequate evaluation of all candidates. But if you’re looking to bootstrap your scaling knowledge, you’ll be better prepared for big company interviews.