System requirements

Functional:

• Given a long full url, it returns a short url. Let's say a short url with length of 7
• Given the short url, it can redirct to its corresponding address in full url

Non-Functional:

• Reliability: the syste should be reliable for users to get/add urls
• Performance over consistency
• Scalability: it should be scalable with the increasing business need
• Cost: it should be cheap if possible
• The short url should expires after 10years

Capacity estimation

Assume we have

• 100M DAU, 1B peak users
• create short url 1/day and get short url 10/day
  • write 100M QPD and read 1B QPD
  • 1k write QPS, 10k read QPS

API design

CreateTinyUrl:

• req:
  • full_url, string
• response:
  • short_url

GetFullUrl:

• req:
  • short_url, string
• full_url

Database design

url table

• url
• short_url
• long_url
• create_time
• expire_time

High-level design

• The load balancer provides the functionality of load balancer and protect malicious attackling
• API Gateway can support authentication, authorization(not discussed in this design), API level rate limiting
• API server is the backend processing the logic of creating short url and resolve the short url to its long url
• We uses in-memory key value pair to store the hot url
• All the data are stored in a NoSQL DB

Request flows

CreateTinyUrl

• client calls API server to creata a short url by providing long url
• The API server generate a uuid tiny url and check if it exists in the database.
  • if yes, regenerate and repeat this step
  • if no, write this tiny url into the database
• Return the short url to the client

GetFullUrl

• client calls API server to get the full url by providing the short url
• The API servers check if the short url is in the cache
  • if yes, return this full url to the client
  • if not, try to fetch that from the database
    • if not found in db, returns a 401 Bad Request
    • otherwise write that into the inmem kv cache and return the long url to the client

Detailed component design

• uuid generation: we generate the short url by relying on doing md5 on the full address and uses its first 7chars as the uuid. We need to double check if it has collection with the existing short url in the db
• we uses the key value in-memory cache for reading cache as read qps is much higher than writing qps and we uses nosql db.

Trade offs/Tech choices

• Hash function vs Global UUID generation: the another way is to maintain a global increasing uuid in the API server. Suppose you are using base64-7-letter and you can uses epochTime-instanceId-threadId-localCounter.
  • pros: no extra db read for cache collision checking
  • cons: extra logic to maintain
• NoSQL vs SQL
  • write qps is only 1k qps so 1 master instance is sufficient to handle all the write quries and in the meanwhile we can have several read replica to specifically serve read quries
  • nosql is relatively more performant and cheaper than relational db.

Failure scenarios/bottlenecks

• API server and db can fail potentially and they should be covered by redundant backup instance
• the API server can be bottlenecks with high qps and we could scale the number of instance
• as for db, we can have read replica

Future improvements

• we can add API rate limiting
• Add API metrics and API analytics