System requirements

Functional:

• User should be able to generate a short URL by adding long one.
• User should be able to list and delete old URLs
• User should be redirected to the long URL by clicking on the short one

Non-Functional:

• Availability: system should be available 24/7 to serve redirections on all links
• Consistency: whoever clicks on a short link should be successfully redirected to the long one (Strong consistency)
  • The system is read-heavy, so we can tolerate delay in write for strongly consistent redirection process
• Scalability: the system should be scalable to serve the increasing number of requests
• Performance: the system is expected to redirect me in less than 100 ms while it could take around 500 ms to create the url

Capacity estimation

Let's say we're going to serve 50 millions redirection requests and 1 million shortening requests per day.

API design

• Post: tinier.com/createShortUrl
  • Input: longUrl
  • Header: Bearer Token
  • Output: tiner.com/uniqueSequenceId
• Get: tinier.com/{uniqueSequenceId}
  • Output: savedLongURL
• Get: tinier.com/listUrls
  • Header: Bearer Token
  • Output: [{uniqueSequenceId, longURL, creationDate}]
• Delete: tiner.com/deleteUrl?{id}
  • Header: Bearer Token
  • Output: {deletedId}

Database design

• User database will contain the user's data and login credintials in on collection of documents
• The URLService will contain the shortURL, longURL and creationDate.

High-level design

• API Gateway that performs load balancing.
• Replicas from the URLShorter service
• Replicas for User Service
• Distirbuted caching to store frequently access urls
• NoSQL database Database for user service
• NoSQL db for URLShortner service
• Sequencer to generate unique ids for short URLs

1. The Gateway will decide which service to forward the request based on the url (if it contains /user will redirect the user service)
2. The Gateway will also balance the load over the service replicas.
3. The user service will be responsible for signup, signin and authorizing the user by handing an access token
4. URL service is resoponsible for adding, deleting and listing short urls, and caching the frequently access URLs using cache aside pattern.
5. The sequencer will generate a unique strings for the short urls, making sure that each dirtibuted replica has its own unique range of IDs to prevent duplication and avoid race conditions
6. The urls database will use the userId as the sharding key

Request flows

Create new short URL

1. Client will send a post request for creation
2. The gateway to redirect to one of shortner serice replicas based on round robin algorithm
3. The service will call the sequencer to generate the unique string
4. The service will save the unique Id paired with the longURL, userId and creation date
5. The database will decide which shard to save in based on the userId

Read a short URL

1. Client will try to access a short url
2. The gateway will recieve the request and redirect it to one of the available url service replicas
3. The service will search in the cache and return the result if existing
4. If not, will read from the db and return the result, then save it into the cache asyncrounously while defining a 1 day TTL.
5. If not existing, redirect to error page

Delete url:

1. Client will try to delete a short url
2. The gateway will recieve the request and redirect it to one of the available url service replicas
3. The service directly send a delete request to the db.
4. If existing, the service will return success, then remove the same Id from the cache if existing

Detailed component design

Check the class diagrama

Trade offs/Tech choices

• The sequencer call and db sharding might affect the write performance, but it scales better and guarantees more availability
• Caching on the read instead of the write to not cache useless URLs

Failure scenarios/bottlenecks

• The sequencer might be a bottleneck, so it also has to scale with leader follower algorithms
• Distributed cache might be overloaded, so it also has to scale and we might need explicit invalidation to the LFU urls after specifc threshold

Future improvements

• Clear the LFU urls from the cache even before the TTL with specific threashold reached
• We might use a queuing system to offload the creation requests rather than overscaling the URL service to handle more creation requests