Detailed Component Design

Distributed Db:
1. Before save in Db we hash the short code using a hash to distribute the creation equalitative in the shards, this to avoid hot spots
2. Horizontal Scaling
3. Partitioning
4. Queires just by hashed indexes (shortcodes)
5. Eventual concistency
6. The DB is no sql for get better scalability and avois sinchronization between nodes, just assing like id the generated short code, this allows the db get better scalability
Rate Limiter:
1. Protects the system blocking ips or web browser fingerprints that can potencialy abuse of the system
2. Also by default going to add a CDN/Edge for speed and more security using services like Cloudflare
3. The Rate limiter for creation of urls will use token bucket algoritm to support burst traffic in the systems, using 200 tokens and a bucket with support just for 200, this for allow sudden high traffic from an user and limiting them to prevent abuse
4. The rate limiter for redirection service will be more permisive, with a bucket with 1000 tokens and token generator of 500 tokens
5. The rate limiter will request with a 429 status code to the client if the limite was exceeded, also use te header Retry-after with an exponential time with randomness using jitter to prevent synchronized retry storms
Generation Service:
1. This service is a cluster for fall tolerance
2. Each node have a range if integer numbers that it can reach and the value of the next step to get a new range embebeded in a json fije
3. Basically each node iterate through the given range and response with the number encoded in base 62 and calculate next number or step, this avoid cordination problemes between nodes\
4. Each node doesnt depends on other to manage itself because each one has the needed information to calculate its own numbers
5. if a node fails still will be alive anothers
6. Use etcd to manage the nodes of short code generation service and, cordinate the assignment of new nodes when need to scaling, etcd will be the manager just to assing big range of numbers to nodes, and the nodes internally will manage themselves
7. The services will be single thread to avoid complexity of multithreading and have excellent performance
We add more charge in the short url creation for better security and ensure that the urls dont be potencially malicious
Always validate the validness of an url and avoid SSRF attacks
For annonymous users we use the ip and browser fingerprint to know who or where was created the url
The services will be autoscallable to manage traffic havy changes
CacheDb:
1. CacheDb temporarily saves the hot URLs to provide fast redirection and avoid checking the main database on every request.
2. The eviction policy used for the URL cache is LFU (Least Frequently Used). This is a good fit because some URLs can become viral, while many others stay cold. LFU helps keep frequently accessed URLs in memory and removes less frequently used URLs first when memory is limited.Short Code
3. The cache uses a TTL of 3600 seconds (1 hour). This is because short-code-to-URL mappings usually do not change often, so the TTL can be medium/long. This helps keep hot URLs in memory for enough time to improve redirection speed, reduce database reads, and avoid re-caching the same URLs too often. At the same time, less used URLs will naturally expire, which helps control memory usage.
4. If a URL is blocked, deleted, or expired, it should not be served from cache anymore, so its cache entry should be removed or invalidated.
5. If no manual invalidation happens, the cached URLs are automatically removed when the TTL expires.
6. The distributed cache (for example, Redis Cluster) uses hashing to distribute keys between shards more evenly. The application can use the short code directly as the cache key, and the cache system is responsible for hashing and placing the key in the correct shard.
High Availability:
1. The nodes are stateless and setted up with autoscaling to manage increaseing traffic, if a node failes then the systems will set up another to manage the take its place
Redirection Service:
1. This service first will look up inside the cache db for respond fast, if the url doesnt exist into the cache db then the redirection service create a deterministic hash of the short code of the url and query the main db to get the url by id (the id is the short code hashed), when get the short code the service will validate if the url is available for redirectioning (Exists and is not blocked), if it is then the service will set it into cache db and returned to redirect client to the real direction, if the url is not available then the system just answer 403 Forbiden.

Trade offs:

The first request to redirect to an url always going to be a little more slow if not cached, due to more operations like get the url for main db, validate data of url and re cache the url
The creation of short urls is more expensive in time to ensure security
If the External system for url malware check is fallen the service going to deny creation till the service is available again, this for maintain security, The service can access to differents services of malware check and get better fault tolerance
The url shortene service will call 3 times to the External system for url malware check, and if no response deny the creation, The service can access to differents services of malware check and get better fault tolerance
The eventual concistency in main db can affect the user for a short period of time, this because when the user create the short url it wont be available during around <= 200 miliseconds, this is practicaly nothing

Submissions

Displaying Solutions with Scores Ranging from 1 to 10