Design a URL shortener: start with one server and let the numbers grow it

Designing a URL shortener typically begins with a grand vision of load balancers, cache clusters, Kafka, and multiple servers. However, interviewers often appreciate a more straightforward approach that starts small and evolves based on the data requirements.

To begin, consider the scale of the project. Suppose individuals generate 100 million links monthly, with each link receiving approximately 100 clicks. This results in about 40 new links per second. When a link goes viral, click rates can surge tenfold. Consequently, the database must handle the load, while the need for a cache increases due to the high number of reads.

With these figures in mind, let's plan the design. Step one involves creating a simple server with a single table that maps short codes to their corresponding long URLs. Additionally, there should be one endpoint for creating links and another for redirecting users. Initially, it's acceptable to acknowledge that this initial design may not be sustainable in the long run.

Moving on to step two, we need to generate unique codes efficiently. If each new link request waits for the database to provide the next number, it would lead to server delays. Instead, each server should take a block of 10,000 numbers at once and allocate them from memory. To avoid clashes, two servers should never be assigned the same block. Furthermore, the numbers can be shuffled using a secret key to prevent patterns that could be exploited to access all links sequentially.

In step three, a cache for tracking clicks is introduced. Once a link's target remains constant, it's unnecessary to constantly query the database. Instead, a cached copy of the target can reside in the server's memory, complementing Redis if required. This cached copy can be temporarily out of sync without causing errors, as each click verifies the information in memory first, then Redis, and finally, the database if needed.

Step four addresses the timing of click counting. Redirect responses shouldn't wait for analytics to be processed. Instead, a small event indicating a click can be placed into a queue, and the redirect can respond immediately. Subsequently, a separate job can tally the clicks in the background, ensuring minimal impact on the user experience.

An important question arises when discussing the design: should the redirect response be a 301 or a 302? A 301 indicates to browsers that the link should be remembered permanently, resulting in reduced traffic but also preventing the ability to track and modify links post-deletion. Conversely, a 302 remains flexible, ensuring that every click is directed back to the system. The choice of response code depends on the interviewer's focus on analytics early in the discussion, as it dictates the desired behavior.

When a link becomes highly popular, such as going viral, the challenge arises from cache misses. Thousands of requests hitting the database simultaneously could cause significant performance issues. The solution involves keeping hot links in each server's memory for a brief period, allowing only one request to reload the link while the others wait.

For a comprehensive guide to designing a URL shortener, refer to the full version available on the author's website. It includes a visual diagram that can be incrementally expanded, a calculator to estimate the required resources based on your numbers, scenarios illustrating potential pitfalls, and code implementations in five different programming languages. The resource is freely accessible without any sign-up requirements.