System requirements

Functional:

• Ability to map a long url to a short url, accurately, by taking into account potential collision
• Ability to retrieve stored mapping and redirect the user to the original long url, as quickly as possible
• (Optional but suitable) Ability to specify an expiration time. Which would also help keeping the volume of data as low as possible
• Ability to specify the short url

Non-Functional:

• Availability & Scalability: System should be able to gracefully handle load, as well as peaks of traffic
• Performance: Latency is critical for the redirection part, although lower expectation for the shortening service is probably acceptable
• Consistency: System must be consistent, avoiding duplicated mappings for instance as well as redirecting to the right long URL. That being said, eventual consistency for the redirection part would be acceptable (and would lean toward high availabilty rather than high consistency)

Capacity estimation

• Shortening Service: 200 RPS could peak at 400 or 600 RPS.
• Redirection Service: 20,000 RPS could peak at 40,000 or 60,000 RPS.

API design

• shortenUrl()
  • Inputs: User ID, long URL, short URL (optional), expiration (optional)
  • Output: short URL and if not used as identifier, an identifier. Or an error in case of failure
• redirect()
  • Inputs: short URL
  • Outputs: Long URL or an error in case of failure (like non-existent expired mapping)

Database design

• URL mapping:
  • Short URL, identifier if possible (else an additional ID may be required)
  • Long URL, string. A maximum length is suitable, like 100 or 256 chars
  • User ID
  • expiration date (optional)

High-level design

See diagram.

API gateway will be responsible for requests routing, will off-load authentication mechanism from underlying service as well as managing rate limiting to protect servers. Logging and metrics emission are also its responsibilties.

Load balancers are not mentioned but are implied by autoscaling and will sit in front of instances pools (API gateway as well as services)

Request flows

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

Trade offs/Tech choices

Failure scenarios/bottlenecks

Database infinite growth: Implement cleaning mechanism removing expired mapping from databases and caches. And advertise a retention policy to the user (like mapping not used for X months will be removed)

High load/Abuse/DDOS: Implement rate limiting on API gateway to protect servers as well as autoscaling to answer the load. Additional strategy like shuffle sharding may be used to further protect again chain reactions. As well as retry strategy and circuit breaker. Thanks to micro-services architecture, shortening service and redirection service are isolated (bulkhead) which would allow one to continue to work if the other is down or degraded (even though it may imply discrepancies in redirection, data will eventually be consistent when system get back on track)

Future improvements

Functional:

• Custom short URLs: ability to specify short URL. Implies higher complexity especially when checking for duplicate while relying on a simple/fast algorithm with low colission would be simple. May imply to introduce more effective way of checking for duplicates like a map or even better or bloom filter
• URL expiration notification: If expiration is highly used, user may indeed be happy to be notified before url expired. Imply a kind of user authentication in order to be able to reach the user (even if a simple "notification email" would suffice at the beginning)

Non functional:

• Bloom filters: in order to increase duplicate lookup efficiency, especially if custom short url is implemented.
• Monitoring: Carefully monitor database metrics and rebalance shards if needed. Monitor cache miss as well as latency difference between a request relying on the cache versus one relying on the database and fine-tune the cache configuration accordingly.
• Redundancy/Disaster recovery: Carefully monitor systems usage and fine-tune configurations to better meet usages