System requirements

Functional:

• create short URLs from long URLs
• redirect short URLs to long URLs
• basic analytics (tracking click counts)

Out of scope

• custom short URLs
• time to live for short URLs

Short URL generation process

• Long URL -> Hash (i.e. MD5) = long int -> base62 encoding

Non-Functional:

• scalable
• fault-tolerance
• performance
• availability

Capacity estimation

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

short url character limit:

• use a-zA-Z0-9, 62 chars
• use base62 encoding

short URL creation

• 100 reqs/sec (write)
  • Can go w/ SQL DB since writes < 10k/sec

short URL redirection requests

• 10k reqs per sec (read/write)
  • Read from SQL DB

storage

• 100M short URLs
• 100 bytes/short URL and long URL pair. So need 10^2*10^6*10^2 = 10^10 bytes or 10*10^9 = 10 GB storage

support 62^n chars. n=7 means 3.5T possible hashes. n = 5 means 916 million possible hashes. go with length 5.

API design

Define what APIs are expected from the system...

HTTP 2

• POST /api/create/v1/
  • pass in the long URL as a parameter
  • return a short URL
• https://shorturl.com/<shortURL>
  • redirect 3xx to longURL

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

DB Schema (SQL)

• short URL (pk)
• long URL (secondary index)
• creation date/time

Primary - Secondary replication

• fault-tolerance
• performance - distribute reads

Analytics

• on short URL redirect, update separate analytics table
  • short URL (primary key)
  • count
    • need to make use of database primitive to automatically increment count
  • last accessed

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

Short URL creation

• client sends request to short URL service
• short URL service generates short URL and checks if it exists in DB Cache/DB
• If it exists (i.e. collision) add 1 to the generated md5sum and regenerate base62 again and repeat above
• once DB Write is successful, return short URL to use

Short URL redirection

• client sends short URL to short URL service
• short URL service checks the DB to see if it exists
• if it does, return a HTTP 3xx to the client w/ the long URL address
  • also update the analytics table
• else return HTTP 4xx error to the client indicating invalid user request

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...

See Diagram

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

scalability & fault-tolerance

have a in-memory cache in front of the short URL DB to serve both workflows

• useful for frequently accessed requests
• start with redis
• key = short URL, value = long URL

employ primary-secondary replica for the DBs for performance and fault tolerance

• writes goto primary
• reads from secondary

short URL service is stateless = horizontal scaling and fault-tolerance

Load balancer can goto any of the short URL service instances, say via round robin for simplicity

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

DB - SQL vs NoSQL

• went w/ SQL since writes are 100/sec (< 10k/sec threshold limit of SQL)
• don't need partitioning for now since we only need 10GB storage for all URLs

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Failure scenarios have backup:

short URL service = stateless, horizontally scalable (= backups)

short URL DB Cache = configure for replication

short URL DB = replicated

Analytics DB = replicated

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?

• Add monitoring and alerting for performance and failure
• Discuss security (tokens) / rate limiting
• Discuss time to live for each short URL