System Design: URL Shortener Like TinyURL

This is the classic first design question. It is small enough to finish, and it touches on IDs, caching and read-heavy traffic.

1. Requirements#

Functional: create a short link from a long URL, redirect to the original, optional custom names and expiry.

Non-functional: very fast redirects, high availability, and codes that are hard to guess.

Out of scope for now: accounts, and detailed analytics.

2. Estimates#

Assume 100 million new links a month, and 10 reads for each write:

links_per_month = 100_000_000
writes = links_per_month / (30 * 86_400)
reads = writes * 10
storage_tb = links_per_month * 12 * 5 * 500 / 1_000_000_000_000

print(f"Writes: {writes:,.0f}/s")
print(f"Reads:  {reads:,.0f}/s (peak perhaps {reads * 3:,.0f}/s)")
print(f"Links in 5 years: {links_per_month * 60:,}")
print(f"Storage at 500 bytes each: {storage_tb:,.1f} TB")

Writes: 39/s
Reads:  386/s (peak perhaps 1,157/s)
Links in 5 years: 6,000,000,000
Storage at 500 bytes each: 3.0 TB

This is read-heavy, but the data is small. Reads are what we must make fast.

3. API#

POST /api/links  { "url": "https://...", "alias": "sale", "expires_at": "..." }
                 --> 201 { "code": "aZ3kP9q", "short_url": "https://sho.rt/aZ3kP9q" }

GET  /{code}     --> 301 or 302, Location: https://...

4. Data model#

links(code PRIMARY KEY, long_url, user_id, created_at, expires_at)

The only query is a lookup by code, with no joins. A relational database with an index works well for a long time. A key-value store such as DynamoDB or Cassandra also fits, and it scales out easily.

5. How long is the code?#

Using a-z, A-Z and 0-9 gives 62 characters, known as base62:

for length in (6, 7, 8):
    print(f"{length} characters: {62 ** length:,} codes")

6 characters: 56,800,235,584 codes
7 characters: 3,521,614,606,208 codes
8 characters: 218,340,105,584,896 codes

Seven characters are plenty for 6 billion links.

6. Generating codes#

With a counter, turn the number into base62:

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode(n):
    if n == 0:
        return ALPHABET[0]
    out = []
    while n:
        n, rem = divmod(n, 62)
        out.append(ALPHABET[rem])
    return "".join(reversed(out))


for n in (1, 61, 62, 125, 3_500_000_000_000):
    print(f"{n:>16,} -> {encode(n)}")

               1 -> 1
              61 -> Z
              62 -> 10
             125 -> 21
3,500,000,000,000 -> ZCpdjxe

To avoid one counter being a bottleneck, each app server takes a block of IDs, say a thousand at a time, from a central service, and it hands them out locally. If a server restarts, it loses some numbers, which does no harm. To make codes hard to guess, you can shuffle the bits of the ID before encoding it.

Random codes rarely collide at first, and the chance grows with the number of links:

space = 62 ** 7
for existing in (1_000_000, 1_000_000_000, 6_000_000_000):
    print(f"{existing:>13,} links: {existing / space:.4%} chance a new code collides")

    1,000,000 links: 0.0000% chance a new code collides
1,000,000,000 links: 0.0284% chance a new code collides
6,000,000,000 links: 0.1704% chance a new code collides

7. High-level design#

                 +--> API servers --> ID blocks
Client --> LB ---+
                 +--> Redirect servers --> Redis cache --> Database
                                                 ^
                                    popular links, about 20% of keys

Create: validate the URL, get an ID, encode it, save it, and return it.

Redirect: check the cache, then the database, and send the redirect. Cache misses fill the cache. Keep the database behind replicas, and shard by code if needed.

A small share of links gets most traffic, so caching a little goes a long way.

8. Which redirect?#

If analytics matter, use 302.

9. Deep dives#

Analytics. Do not write to the database during a redirect. Send click events to a queue, and let workers count them.

Expiry. Check expires_at at read time, and remove old rows with a background job.

Abuse. Rate limit creation, and check URLs against lists of malicious sites.

Custom aliases. Use the same table, and rely on the unique key to reject duplicates.

Multiple regions. Deploy redirect servers and caches near users, with a CDN or edge workers.

Trade-offs to mention#

• A counter is simple but predictable; random needs collision checks.
• 301 cuts load, but loses analytics.
• Relational is simple, and a key-value store scales further.

Key takeaway#

Next: Design a Chat App.