A url shortener web service must support the following minimal operations:

• Link creation: map a url to the shortened form <hostname>/<slug>
• Link resolution: redirect <hostname>/<slug> to the original url

Assumptions:

• Links are immutable
• Redirect operations will be much more common than requests to shorten urls

How many urls can we represent?

The number of urls in use is naturally much larger than the set we can represent.

A slug with

• character set of length $b$ and
• length $r$

has $b^r$ permutations. So we can form

$$ N = \sum_{r=1}^n b^r = \dfrac{b^{n+1}-b}{b-1} $$

distinct slugs until we reach slugs of length $n+1$.

If we are able to map each of these to a different url, then we can represent $N$ urls.

A base 64 character set of "[A-Z][a-z][0-9]-_" can represent $\frac{64^6-64}{64-1}$ ~ 1 billion urls before reaching slugs of length six.

Architecture

Real systems can support the maximum number of links.

Suppose our url shortener maintains a counter, and a table mapping counter value to url.

Set URL