System requirements

Functional:

We need to return short url of length 6 for a given long url, the short url should only contain English letters and digits.

Non-Functional:

The system should be highly available and respond with low latency.

They system should be reliable that can store the short url for years.

Capacity estimation

Assume we have 1M new short urls generated everyday, which is 1M/86400 = 11/second

For each request, we have to include the metadata and short, long url, average length of long url is 100 characteres, and 6 characters, and metadata 10KB, so the average storage for each request is (10K + 100 * 2 + 6 * 2) =10KB

Assume we need to store the short url for 5 years, then total storage we need is : 10KB * 1M * 365*5= 18TB

API design

We should have the API to generate the short url

• generate(longUrl, user_id, creation_time)

We should be able to visit the original website for a given shortUrl

• visit(shortUrl)

Database design

Table1: newly generate shortUrl - (id, shortUrl)

Table2: used shortUrl - (id, shortUrl)

Table3: longToShortUrl - (id, shortUrl, longUrl)

High-level design

Request flows

• Client sent request to the system for generating a shortUrl
• The request will come to load balancer first, then distribute it to applicatioin servers
• The application servers get a valid short url from the cache in memory
• store the shortUrl together with the longUrl to the database
• Next time client sent request to visit original website using this shortUrl
• It will check the cache to see this mapping (shortUrl -> longUrl) is available, then just return the longUrl and direct client to original website
• If it's not in the cache, then just check with databse to get the longUrl

Detailed component design

-KGS - key generation service

we can run a offline KGS. It keeps running to generate a random url say with 6 chars, the url has to be unique, and it should have a key store to store newly generated url.

We obtain a group of newly generated urls, and store them into a caching in memory. Everytime there is a request to generate shortUrl for a long Url, just pick one shortUrl in the cache and assign it to the longUrl, and store the mapping to the database.

-Caching

We can store the most frequently accessed shortUrl in a key-value store in memory. Key is the short url and value is the longUrl.

-Sharding

We can partition the database based on the hash of the shortUrl. Then decide which partition to store the data based on the hash. With this approach we can distribute all the data evenly on the database partitions. If certain partition is over loaded, we can consider adding more database servers using consistent hashing.

Trade offs/Tech choices

-Availability vs Consistency

When a write request (generate new URl) sent to the server, it generate new shortUrl and store to database, then it has synchronize this update to other database replicas for reading. In this case we may have to sacrifice consistence for availability. Eventually we will see the updated data.

Failure scenarios/bottlenecks

-Caching failure

If the caching fails, then all the read requset has to hit the database, which will cause high latency to the system.

Future improvements

Consider do the sharding on the caching to avoid single point of failure and lower the read latency. But partitioning on the caching means more cost on the infrastrure and more complexity to the system, so we have to do tradeoffs.