System requirements

Functional:

• Shorten urls given a long url
• Redirect to long url given short url

Non-Functional:

• low latency for redirects
• High availability for redirections
• prevent abuse
• scalable

Capacity estimation

• Space
  • Assume [a-zA-Z0-9] - 8 char combination -> 8 bytes
  • Assume long URLs up to 500 bytes
  • Metadata
    • created date - 8 bytes
    • expiry - 8 bytes
    • user_id - 4 bytes

• • Approx 512 bytes per request

• Throughput
  • Assume 100 shortening requests per second
  • Assume 100, 000 reads per second

• Writes
  • 51200 Bps -> 4.1 GB per day
  • Approx 1.5TB per year without cleaning up expired URLs

Database design

Read heavy database and no strong joins required.

Select document DB such as dynamoDB or D1. This allows for ease of scaling.

URLs

{

short: string - primary,

url: string,

created_at: int64,

expires_at: int64,

user_id: int

}

User

{

user_id: int,

...

}

High-level design

• Writes
  • Write back operation to redis first, assuming user wants to use the url immediately.
  • replicate using eventual consistency
    • Inform user global availability will require some time.
• Reads
  • Hit CDN cache first where possible. Reduce traffic coming to server
  • Read from redis if available
  • Read from DB and promote to redis cache as well as to CDN

Request flows

Detailed component design

We might want to encode the short url to contain partitioning logic so that we can distribute read loads using the short url directly without additional hashing. This would improve read throughput.

To handle hotspots - i.e. links with exceptionally heavy traffic. We could do a round-robin distribution to balance loads across read replicas.

Trade offs/Tech choices

• DB eventual consistency vs strong consistency
  • ++
    • user will get faster response and still be able to use the link within his region
  • --
    • global availability will require some wait time.
    • generally acceptable we can inform user about this.
    • user can pre-generate urls in advance for their upcoming events.

• Write back vs write through/write around
  • ++
    • ensures lowest latency for user immediately after creating link
    • redis can persist state in the event of failure
  • --
    • require higher redis memory -> higher cost

Failure scenarios/bottlenecks

• read hotspots
  • If poorly handled, excessively high reads can throttle other users sharing the resource.
  • Can be mitigated by imposing a rate limit on the short by default. High profile clients can pay for dedicated resources if they foresee high usage for an upcoming use case.
• all components should have at least one replication to prevent SPOF.

Future improvements

• custom urls
  • deeper consideration required if we also use shorts as a balance tooling