URL shortener

01 · CONTEXT AND REQUIREMENTS

What a URL shortener needs to do

A URL shortener receives a long address and returns a short code. When someone opens the short link, the system looks up the original address and redirects. It is simple to explain, which makes it a good first exercise in requirements gathering.

The functional requirements are just two: create the short link and redirect from it. An optional third is letting the user choose their own alias. Among the non-functional requirements, three drive the design: each code points to a single long URL, redirects are fast, and the service is up almost all the time, favoring availability over consistency.

02 · SCALE ESTIMATION

Back-of-the-envelope math

The ByteByteGo book starts from one hundred million URLs created per day, which works out to about eleven hundred writes per second. With a ratio of ten reads for every write, that is over eleven thousand reads per second. Over ten years it would be 365 billion records and, with URLs of about one hundred bytes, around 36.5 TB.

Hello Interview uses other assumptions: a billion URLs and a hundred million daily active users, with a ratio of a thousand clicks per link created. The two sources disagree on the read-to-write ratio, and that is expected: an estimate is a hypothesis, not a fact. What matters is the shared conclusion that reads far outnumber writes.

03 · API AND DATA MODEL

Two endpoints and a table

A API has one route to create, for example a POST on /urls, and another to redirect, a GET that takes the short code and responds with an HTTP redirect to the long URL.

O data model is a table that links the code to the long URL. In the simplest version of the book it has three columns: id, short code, and long URL. The lookup key is the short code, because it is what arrives with every click.

1. The browser sends the long URL to the shortener API.

2. The API picks a short code and writes the code and long URL pair to the database.

3. Then, whoever opens the short link makes a GET with the code; the API queries the database and returns the redirect.

This first version works, but it leaves the central question of the case open: how does the API pick the short code?

04 · GENERATING THE SHORT KEY

Hash or counter, and the role of base62

There are two families of solutions. The first applies a hash function, such as CRC32, MD5, or SHA-1, to the long URL and uses only the first characters of the result. A hash output looks random, and that result is usually encoded in base62.

Base62 uses lowercase letters, uppercase letters, and digits. With seven characters there are about 3.5 trillion combinations, more than the 365 billion URLs in the estimate. With eight characters there are about 218 trillion.

The problem with hashing is collision: two different URLs can generate the same code, and the more URLs are stored, the higher the chance of a duplicate. Resolving it by querying the database on every request is expensive. Two defenses are a UNIQUE constraint on the code column and a Bloom filter, which answers quickly and uses little memory whether a code already exists.

The second family uses a counter. Each URL gets the next number, converted to base62. Since every number is unique, there are no collisions. The cost is depending on a unique ID generator, and sequential codes are predictable, which allows links to be enumerated.

For this junior-level version, the counter is the simplest choice to explain and avoids collision handling. In this design, the write service asks the counter, for example a Redis, for a unique number and converts it to base62. Since Redis is single-threaded and has atomic operations, it works as a counter; to avoid asking for a number on every write, each instance can reserve a batch of values.

1. The browser sends the long URL; the load balancer forwards it to an instance of the write service.

2. The write service asks the counter for a number. Each returned value is unique, so there are no collisions.

3. The service converts the number to base62 and writes the pair of code and long URL to the database.

4. To avoid hitting the counter on every write, the instance can reserve a batch of values and consume them locally.

05 · CACHE AND REDIRECTS

Fast reads: cache and the 301 or 302 status

Since reads dominate, it pays to put an in-memory cache, such as Redis or Memcached, in front of the database. Best practice: the cache time to live (TTL) should be equal to or shorter than the URL's expiration, so the cache never serves an expired link. Separating the read service from the write service lets you scale each side independently.

1. The browser opens the short link; the load balancer sends the click to a read instance.

2. The read service queries the cache. If the code is there, it responds immediately without touching the database.

3. If the code is not in the cache, the service fetches it from the database, stores the result in the cache, and responds.

We still need to choose the HTTP status code for the redirect. 301 says the URL moved permanently: the browser caches the response and later clicks never reach the shortener. 302 says the move is temporary: every click goes through the service again.

If the goal is to reduce load, 301 makes sense; if click analytics and the ability to update or expire links matter, 302 is the better choice. Hello Interview uses 302 in its design.

06 · EVOLUTION AND LIMITS

What changes as the system grows

With more traffic, the cache and the database need to handle more reads. With six characters the space runs out at about 56 billion URLs, and then it is necessary to move to seven. Across multiple regions, each one can receive separate ranges of the counter, so numbers are not repeated.