System requirements

Functional:

• User submit URL --> shorten link created
• Shorten link entered --> Redirected to user submitted URL

Non-Functional:

• Performance:
  • Low p99 latency to be redirected
  • Low p99 latency to create shortened link
• Availability:
  • Service available to create

Capacity estimation

• API Hits per second to
  • Create URL
  • Retrieve maybe 10 * the creation
• DB total storage over time
  • e.g. if 100000 per day * 4kb * 465 = 146000000 bytes per year

API design

• API to create shortened link from URL
  • check if shortened for URL exist, if exist return existing
  • hash function to generate shortened URLs
  • ensure shortened URL unique in database
  • save to database
  • returned shortened link
• API to retrieve URL from shortened link
  • Can have LRU cache for frequently visited shortened URLs
  • If not in cache, retrieve from database
  • retrieve original URL
  • perform redirect

Database design

• DB need to enforce:
  • Strong consistency uniqueness on shortened URL
• DB can be eventually consistence for
  • e.g. after shortened URL first created --> retrieving shortened URL can be eventually consistent
• Data model:
  • shortenedURL string (Unique)
  • originalURL string
• Index on shortenedURL + originalURL so it can have fast look up

High-level design

client --> CDN (with DDOS protection and WAF) --> load balancers --> API server

API Server to create shortened URL --> cache --> database

API server to retieve shortened URL --> cache --> database

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

• API server can scale horizontally based on CPU and memory usage / worker availability, fronted by load balancer with round robin load balancing
• Frequently accessed data in memory cache
• Database can have read replicas for retrieving only

Trade offs/Tech choices

• Choice of hashing algorithm for length of URL
  • shorter URL = more limited total number of unique URL
• Separate service for creating and retrieving URL
  • Con: More overhead (compute, deployment)
  • Pro: Creating URL may be more compute intensive (e.g. due to hashing function), can scale this layer independently
  • Pro: Creating URL service can connect to writer DB, and retrieving can connect to read replicas only

Failure scenarios/bottlenecks

• Potential for abuse
  • User may submit many URLs to be shortened
  • User may submit nonsense URLs that are not working to be shortened
  • This will consume unecessary space in database
• As more URL submitted database size increases
  • May have to continue vertical scaling, or eventually horizontally scaling
  • Database size increase may also contribute to query time increase
    • ensure indexes set up for the queries we are using
  • We may have to consider expiring old URLs that are not used
• Database unavailable
• API server unavailable

Future improvements

• Rate limiting in the client for create URL
• Rate limiting by IP in server for create URL
• Expiring URLs
• Metrics for how frequently a URL is visted