Design a url shortner

A URL shortener is a proxy service that provides a mapping between the short and full representation of a URL. The short URL has the advantage of being small. The service can also provide useful analytics.

The API provides two endpoints:

1. POST /api/v1/data/shorten payload: { url: string }
2. GET /api/v1/{shortUrl}

Back of the envelope calculations

Requests

Assume

100M writes / day

With ~100K seconds a day

= ~1K writes / second

Assuming a typical 10:1 read:write ratio

= ~10K reads / second

We'd need to cache.

Storage

Having

100M records / day

at 100 bytes per record is

~= 1 GB / day ~= 400 GB / year

Redirects

• 301 — permanent, where the browser caches subsequent requests and reduces load.
• 302 — temporary, where the browser's requests always query the service first, which is useful for analytics.

Encoding mechanism

• Hashes are too long, and prefixes could result in collisions that need to be handled.
• Using a unique integer that is base62 encoded avoids collisions at the expense of enumeration attacks.

Why base62? With 62 characters [a-zA-Z0-9], a 7-character short code covers 62^7 ~= 3.5T URLs — plenty of headroom for the storage estimate above.

Happy Hackin'!

References

• base62 encoded

---

This article is part of the system design series where I am summarizing chapters from The System Design Interview: Volume 1 / Volume 2 amongst other related content