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:

POST /api/v1/data/shorten payload: { url: string }
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

Design a url shortner

Comments (1)

System Design

DDD: Summary

More from this blog

Database Isolation levels

8 Simple reminders

No regrets

Design a distributed unique id generator

Back of the envelope calculations

Requests

Storage

Redirects

Encoding mechanism

References

Command Palette

Comments (1)

System Design

DDD: Summary

More from this blog

Back of the envelope calculations

Requests

Storage

Redirects

Encoding mechanism

References