Loading...
1) User should be able to generate short url - fixed in character limits based on the provided url.
2) Short url should have the expiry time with default TTL. User can provide expiry time as well. Once expired the short url wont be available for an year as an grace period.
3) Admin should be able to see analytics of the system.
4) Once the user hits the short url, it should be redirected to the original url within single digit ms at p99.
1) System should be reliable i.e. once the short url is generated and persisted, it should not be modified.
2) System should be able to handle concurrent requests.
3) Short url must be unique and should not lead to multiple addresses.
4) System should be scalable to handle peak load.
5) System should be highly available.
6) Each redirect should be recorded for auditing purpose.
It's a ready heavy system.
1) User Base -
Total users - 100 M
Daily Active Users - 10 M
Considering 80:20 ratio for read:write -
Daily read requests - 8M
Daily write requests - 2M
2) Network Bandwidth -
Daily read requests - 8M
Request per seconds - 80
Single request size - token(1KB) + short url(20 bytes) = ~1KB
Redirect size - Long URL - ~ 500 bytes
Total bandwidth used per request = 1.5 KB
Read bandwidth size per second= 80*1.5KB = 120KB
Daily write requests - 2M
Request per seconds - 20
Single request size - token(1KB) + long url(500 bytes) = ~1.5 KB
Response size - short URL - ~ 20 bytes
Total bandwidth used per write request = 1.5 KB
Write bandwidth size per second= 20*1.5KB = 30KB
Storage -
Single request would contain = user details(~1KB) + Short URL(~20 bytes) + Long URL(~500bytes) + Expiry time(~20 bytes) = ~2KB
If default expiry period is 5 years then =
in 5 years - 100M * 5 = 500M request -> if 10% traffic increase per year then = 100+110+121+132+146 = 600M requests in 5 years
600M * 2 KB = 1200M KB = 1200 * 1000000 = 1.2TB Space required for storage
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
Request to redirect to long url
GET api/v1/{unique code}
Auth - No auth
Response - 307 response code to maintain audit and to prevent browser changing method and then redirect to long url
Request to create short url
POST api/v1/url
Auth - JWT token
Request param - Long url, expiry date(optional)'
Response - 201 response code with short url. If duplicate request then 409 conflict with message that resource already exist along with short url.
Request to get status of short url expiry date
GET api/v1/{unique code}/Validity
Auth - JWT token
Response - 200 with JSON
{
user : {user name},
short url : {unique code}
long url : {actual url}
created date : {date}
Expiry date : {date}
}
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
The core concepts of a scalable system are -
1) Decouple First by lowering the subsequent dependencies
2) Protect the Database by having cache
3) Design for failure such as circuit breaker
4) Queue the system for async tasks
5) Observer everything
Write Path -
1) User will make a request which will go via Load Balancer.
2) LB will choose underlying instance of request handler by traffic/bandwidth/round robin algorithms.
3) The respective request handler will call the redis and get the unique code generated by URL unique code generator service.
4) Unique code generator service need fix on the size of code. Now it has 0-9 and a-z, A-Z = 62 characters to make use of it.
If we fix 5 characters then this service can generate 62^5 = 916 million unique code which would be suffice for 600M unique code as per the estimation plus the 1 year grace period.
Since we are expecting 20 requests per second, we can keep ~30 unique code already generated and give it back to request handler.
Concurrency issue - What if 2 requests are getting the same code from URL unique code generator service?
Solution - Redis sets can be used for the atomic operations. The unique code generator service feed redis with >1000 unique codes. It keeps a check of current available quota at Redis to manage load in advance. The generator service uses INCR on a redis counter and base62 encodes the results. With that, short codes are always unique.
5) Once request handler has the unique code. It writes to DB about the user details, long url and short url. DB is durable system of record.
6) Request handler also pushes the message to Kafka queue which then send to Analytics system for audit and analytics purpose.
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
Read Path -
1) User hits the short url.
2) It comes to load balancer.
3) LB sends request to handler and handler gets the long url from Redis and redirect the original request to long url by sending the 307 response code. Internally it decodes the short code, get
For the hot requests, Redis keeps it in the cache based on LRU algorithm.
Since it is in ready heavy system, multiple instances of Load balancers and request handler would be running to manage load.
Redis would be running on cluster to manage traffic. The cluster would be sharded by hash(short_code). In case of failure of few nodes, shard rebalancing would happen to honor requests. However in case of Redis failure of almost all nodes, a circuit breaker would open and only 25% of the request would be moving to DB.
A heartbeat script would be running at infra level to keep checking all component and send alert to Support for any failure.
The unique code generator generates codes based on Redis INCR and then passed to feistel cipher function to scramble to another unique integer before finally getting base62 encode it which is hard to guess. Redis works as single thread application and all the concurrent requests would be queued. With that each unique code would be served to each unique request.
Cache - miss scenario - Read the data from DB, enter it into cache with TTL.
Rate limiting is applicable at ip level.
In case of updates or disable of short url, the request also invalidate the respective cache.