System requirements

Functional:

• Generate short URL for new URL
• Redirect from shortened URLs to original URLs
• Store short URL to long URL mapping

Non-Functional:

• High availability
• Low latency
• URLs should be short enough for the service to be of value
• URLs need to not collide
• URLs should be persisted for a decent period (multiple years)
• Generated shortened URLs shouldn't be modifiable

Capacity estimation

Estimate the scale of the system you are going to design...

More read than write traffic: shortened URL gets generated once, but used many times

Say we make short URLs with 6 characters

There are 128 ascii characters-- round to 100

100^6 is 1,000,000,000,000 = 1 Trillion possibilities

URLs are up to 1,024 bytes -- 1KB

So we need to store about a petabyte of data

Short URL is www.sitename.com/<6 chars> -> about 20 characters

20 characters -> 20 B per URL -> 20 Terabytes

Dominated by the petabyte factor above

Honestly not sure what assumptions to make about usage

Info provided by coach: 10,000-20,000 redirect requests for each shortened URL

BUT traffic is not uniform-- likely will have some very hot URLs and many that are accessed infrequently if at all

API design

shortenURL(URL) -> URL: generate shortened URL given regular URL

redirectURL(URL) -> URL: provide original URL given shortened URL

Database design

Key value store makes sense for this use case

We don't care about search/range queries, so we can use hashing to generate shortened URLs

• this will distribute URLs across range of possible shortened URLs
• Can then partition by URL range with something like consistent hashing to support scaling

Since we want high availability, we want replicas for fault tolerance

More read than write traffic, so single leader replication makes sense

How should the system handle a request for a URL it's already shortened? -> generate new short URL, to reduce the impact of hot keys

Access patterns suggest a cache would make sense -- generated URLs probably go stale and are rarely used after a while (say a couple months, generously)

High-level design

See diagram

Request flows

Read request:

Client -> Load balancing / reverse proxy -> Server -> Cache -> Database

Write request

Client -> Load balancing -> Webpage server -> database

Detailed component design

Load balance using geohashing for low latency to cluster of servers

Then load balance within the cluster by range of the short URL hash to send request to server

Server checks its cache, and if that fails (cache miss), checks the database

• we may want multiple caches since database check is more expensive
• Should each server have its own cache, or should they share?
  • Own cache is simpler
  • Shared cache can scale independent of servers
  • But then we need load balancing for the cache too

When cache is full, evict least recently used (LRU)

Trade offs/Tech choices

For low latency, we should distribute clusters of servers globally -> geohashing for load distribution

Will need periodic sync between clusters to propagate newly written short URLs

Eventual consistency for this is probably OK

Could use change data capture to keep database replicas across geographically distributed clusters in sync

Since URLs will go stale, we want to cache commonly used short URLs. (Tradeoff: duplicating data)

Failure scenarios/bottlenecks

Failure scenarios:

Trying to access a short URL that doesn't exist

• checking for this could be expensive, since we need to go past the cache (possibly multiple caches)
• use something like a bloom filter to check for nonmembership

Trying to access a short URL that exists but hasn't been replicated/propagated

Hot keys prevent nice distribution across servers

Future improvements

Hot keys: handle separately?