System requirements

Functional:

Get a shortened URL for your bigger URL, that when followed, redirects you.

Non-Functional:

Very fast reads

• We will cache, a lot, and work hard to get mostly cache hits.

Relaxed write speeds, strong consistency

Capacity estimation

100mil urls a month ~ 3.5mil urls a day ~ 40 an hour

Data growth

hash length: 12bytes

url length (est): 100 bytes

with meta call it 250 bytes

100 mil * 250 bytes:

~ 25 GB of data a month

API design

Write service -> client (user) gives it a URL, it returns a shortened version on success. Internally retries on collision.

Database design

hash_url table

string hash Primary Key

int userID FK -> user table PK

string originalURL

user table

userID int PK

{other metadata}

High-level design

Relational database and read replicas store all permanent state

Two services,

1. Portal, that does the admin for the user/URLs
2. Redirect, the read heavy

Request flows

Write service uses a serialisable transaction to write the hash + URL to the database and only responds succesfully to the client if the transaction commits.

Redirection service uses the hash to select which sharded cache node to visit, which will either return the raw URL from memory, or go read from one of the read replicas of the database, then return the raw URL.

Detailed component design

Cache layer shards by a consistent range hash (where it doesnt need to hash since the url hash is already a hash). If there is no database entry at a given hash, it also stores that information.

Postgres writes use serializable to enforce strict consistency of hash -> urls and protect users. In case of hash collision, increment by 1 (and so on).

The load balancers will do WAF-like-things to prevent DDOS etc.

Trade offs/Tech choices

We need strong transaction isolation. We are a very read heavy service, our writes are practically trivial in number.

Relational databases have slow write throughput in part due to their strong isolation and consistency guarantees.

Using a hashrange caching layer increases complexity but increases our chances of cache hits, the alternative is something like a multi master redis with CRDTs, but new URLs might take a while to replicate to all of the cache nodes and we might end up with less coverage of hashes since we would have all the data on all nodes rather than a subset of data of some subsets of nodes.

Failure scenarios/bottlenecks

The single write leader relational database setup is inherently low write throughput, if we became fantastically more popular, we would need to vertically scale the leader in the short term.

In case of leader failure, the redirect service would still work 100% even if there was a cache miss, but the writes would be unavailable until the standby took over.

Future improvements

we could use the hash to shard some postgres clusters, so only a subset of writes was going to each leader. hash writes are disjoint by nature.