System requirements

Functional:

• create a short url from a large url
• a request to the short url should redirect the user to the proper large url
• a request to update a short url's long url property

Non-Functional:

• service must be designed for high availability
• service must be designed to support high throughput for read request.
• latency must be low when accessing the short url and redirect to the original one
• the system must be eventually consistent, meaning that once the short url is created, all request to the short url should redirect to the same long url

Capacity estimation

Let suppose a 5:1 read-write ration, which means that the system should tolerate 5 times more reads than writes.

lets suppose we have 10000 DAU:

• url creation request: 10000 / 24 hours * 3600 seconds = 0.116 request/second
• url reading request = 5 * 0.116 request/second = 0.579

Storage:

The short url record will have the following fields:

• shorUrlId: 8 bytes
• longUrl: 100 bytes
• userId: 20 bytes
• creationDate:14bytes
• expirationDate: 14 bytes

Total Record storage: 256 bytes (aprox)

Storage capacity

• 10000 request per day * 256bytes = 2.56 mb per day
• 5 year storage = 2.56 mb * 365 * 5 = 5tb (aprox)

API design

• create(longUrl, userId) -> shortUrl, expiration_date
• get(shortKey) -> longUrl to redirect

Database design

In this case i will choose a NoSQL database as it will support high write throughput, easily scales horizontally and eventual consistency is required. I'll go with DynamoDB as the records will be accessed by the PK shortUrl and complex queries are not needed

• url_table:
  • shortKey
  • longUrl
  • userId
  • creation_date
  • expiration_date (set to 2 years after creation by default)
• user_table
  • userId
  • name

High-level design

• Api GW
• CDN
• Load balancers
• Cache (redis)
• DynamoDB Database

Request flows

• create(longUrl, userId): The client make a request providing the longUrl, the ShortUrl service generates a random key and creates a document with the random key, the long url and the userId.
• getUrl(shortKey): The client provides the short key in the request. The shortUrl service look for the key in Redis. If the record is found, the client is redirected to the longUrl. If not the service look for the record in DynamoDB using by the key which is records PK. Then adds the record to Redis for future invocations. Finally the client is redirected

Detailed component design

• the system will have an api-gateway between client and app servers for handling authentication and authorization and rate limiting
• A load balancer will be added between client and api gateway and between api gateway and servers to avoid bottlenecks and distribute the load between more than one instance
• A redis database will be used for caching results and improve reading queries. I'll use the expiration_date field for removing unused

Trade offs/Tech choices

• Short Url code: As its random generated, collisions could happen. The system should support retries with new generated codes

Failure scenarios/bottlenecks

Future improvements

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