System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

1. Given a long url produce short url
   1. User can optionally provide an alias for the url
2. Short URL is readable and short - 6 chars, a-z, 0-9 excluding i, I ,L, l, o, O, 1 characters.
   1. 26 lowercase chars - 3 chars = 23 chars
   2. 26 uppercase chars - 3 chars = 23 chars
   3. 0 - 9 : 10 digits - 2 digits = 8 digits
   4. 2 symbols - $, @,+, !
   5. 58 usable chars - can make 58^6 combinations of hash - 38B hashes using base58 encoding

Out Of Scope:

1. User Authentication & Account Management
2. Tracking click per short URL, geolocation
3. Expiring URL
4. Security, monitoring & filtering malicious requests

Non-Functional:

List non-functional requirements for the system...

1. System ensures no duplication of short url
2. Redirection occurs less < 100ms
3. System is reliable and available 99.99% of time
4. System should support 10B URLs

Capacity estimation

Estimate the scale of the system you are going to design...

1. URL Generated
   1. 100K URLs per day i.e 1 URL/sec
   2. Month - 3M URLs per month
   3. Yearly - 36M URL per year
   4. 5 yrs - 180M URLs in 5 yrs
2. Storage Size - each short url is of 6 chars,
3. Redirection
   1. RPS - 1K redirections/sec
   2. With a spike of 70% rounded to 2K redirections/sec
4. Storage Size
   1. 3MB per URL record - 3MB x 180M = rounded to 550GB

API design

Define what APIs are expected from the system...

Generate URL

Redirection Request

This is a third-party site requesting us to get the long url for a short url, for instance if some user clicks on a link "www.mytinyurl.ly/ABC123" where the host "mytinyurl.ly" is me and then I have to respond with a 301/302 HTTP response code with long url

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

1. URL Record in database - Over all max 3MB per record

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

1. API - Generate short URL, get long url using a short url
2. Service layer
   1. URL Generator Service - Generates a short url code for a given long url
   2. Redirection Service - Given a short url, the redirection service lookup in cache with key shortUrl, if found the long url is returned to API gateway else the service looks up in database and pull the shortUrl record, add to cache, returns the long URL which API gateway wraps into response header with HTTP 302
   3. Service layer deployed in Kubernetes or containerized environment lets API gateway pass the request to Kubernetes controller and let Kubernetes load balance the request to an instance of a microservice

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

1. API Gateway - User submits a long url (post login) via UI > API. The api gateway routes the request to an instance of a microservice. At the same time api gateway logs metrics on who, when and what is looked up or generating a url
2. The API forwards request to a service that generates a short url and returns with HTTP 201 response code indicating url is generated and persisted in the database.
3. Third-party sites or application presents a shorturl with a domain https://tinyurl.ly/{short-url} which the API gateway redirects to a redirection service that looks up in the cache, on cache miss, the services looks up in database, add to cache and return the long url

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

1. Short URL Generator - One or more nodes that generates a hash for the given long url.
2. Cache Service - a redis cache service that uses LRU eviction strategy to cache the shortUlr-to-longurl key/values for fast lookup using short url

Hash Generation Steps

Each short url generator has a logic to generate a hash without collisions and without the need for distributed counter or hash generator. Each node takes a 36 bit id, which contains (bits from right to left)

1. 0 - 21 bits - 22 bit time stamp from latest epoch for instance from 18-May-2025
2. 22 to 27 - 6 bit node id that is generating the code, each node has a unique id assigned at the start
3. 28 to 36 - a 8 bit sequence number starting at 0 and monotonically increases, this is persisted onto disk/database for recover from service crash
4. Once a 32 bit ID is generated, the id is base62 encoded to generate a hash. This hash is used as the short url code

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

1. Avoids distributed hash generator - this introduces maintenance cost of running a zookeeper or multiple nodes etc
2. Postgres database - since we are dealing with a well structured data of a long url to short. url and its expiration/created date, a regular RDBMS is good enough. A RDBMS binary search on indexes will be suitable
3. Load Balancer - NGINX or ALB to route the request to a API Gateway for either generating short url or redirection requests
4. API Gateway - A gateway service like Kong api gateway or AWS api gateway that routes requests, log requests, has additional functions to rate limit or deny requests is suitable
5. Short URL generator/Redirector service - a nodejs or even a java/go/rust service deployed in kubernetes is suitable to scale. the kubernetes has its own orchestration, load balancing and controller components to route requests to a service running in the pod.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

1. Expiring a URL - this requires synchronizing database with redis cache
2. Hash Collision - Can have a Bloom filter to quickly check whether a hash is already seen earlier to avoid collisions, this bloom filter is deployed in each of the url generator node.
3. database. - The single instance of postgres going down is a major bottleneck for redirection and url generator. This needs to have a synchronous replica to a standby node that will ensure failover and disaster recovery
4. Placing the cache service right below API gateway or loadbalancer before redirection microservice helps in looking up fast, however we cannot track metrics of how many lookups are done and bill the user. Though this is not an immediate requirement, but in the future we might introduce these functionalities

Future improvements

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

1. Hash Collision - avoid collision on user provided alias without looking up in database. Something like using a Hyperloglog cache
2. Billing and Payment - handle billing user based on the redirections - say 0.001 USD for a redirection
3. Implement telemetry - track who clicked, from where and target for redirection requests. Helps the user in devising specific marketing strategy for a region
4. Monitoring - implement observability and monitoring