Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• Redirect latency: <= 5ms
• create latency: <= 200ms
• Rate limiter per ip and browers fingerprint
• External apis for consult malware urls
• Short url code for petabytes of data
• Non collitions in urls short codes
• Stateless nodes for scalability using horizontal scaling
• Cache for fast responses
• High availability using multiple nodes for services and distributed databases

API Design

POST short/ {url: http://longurlexample.com}

GET /{uniqueshortcode}

High Level Design

1. Components
   1. ApiGateway/Edge Layer: Responsible for receiving client requests, routing them to the correct service, load-balancing traffic across service instances, and applying rate limiting to prevent abuse. It serves as the public entry point of the system, and all client connections use HTTPS/TLS for secure communication.
   2. Rate Limiter: The rate limiter service will add a system for block potencial abuse, with ddos attacks
   3. Url Shortener Service: Responsible of short urls into short urls using the path: short/ before the short code for the url, next the servcie will hash the shortcode and save it in db for better distribution in the distributed db and avoid hotspots
   4. ShortCode Generator Servie: This service is basically a cluster of servers, each one with a range of data and the step for get the next range, this makes the system more independent, without strong synchronization between nodes and mantain the generation of ids short, independient from database and fault tolerant, each short code will be encoded into base 62
   5. Url Reputation service: This system is used by the Url Shortener Service to valdate if a url is malicious before create it, this consult another services to validate if an url is potentialy malicious
   6. Redirection Service: Responsible of redirect requests to using a short url to the original direction, using the CacheDb for fast redirectioning, in case that is not into the CacheDb the service will consult the main db using the a hash of the short code
   7. Distributed Main Db: A dabatase responsible of save the real url directions associated to the short code created for it, this is a no Sql database with eventual concistency for speed and store petabytes fo data.
      1. The Main Source of truth
      2. Recive writes of url creation and queries for get urls from storage
      3. Fallback access when cache miss an url
      4. No sql because it is better for horizontal scaling, the system doesnt need complex relationships, queries by id are so fast, and the system is read heavy
   8. Cache: An In Memory db used for fast access to urls most used insetead of check the main db in each request
      1. Temporaly saves hot urls for fast redirectioning
      2. Partitioning to manage more volume of data and better performance not searching into all the data
      3. Replication for fault tolerance
      4. Is the first database to look up
      5. Is used by redirection service
      6. Uses a medium size TTL to dont re cache data a lot, and because the urls mostly dont change
2. Unique short codes
   1. The short codes will be, incremental integers based on a range in each node, the nodes going to encode the number into base 62, each number going to be unique, each node have a range of numbers to use, when the range ends calculates the next step based on information embebeded into each node, this help us to dont have to cordinate the nodes between them, the nodes save information localy into a small json for fault tolerance and dont repeat number used before, a base 62 of an unique number is also unique

Detailed Component Design

1. 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
2. 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
3. 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
4. We add more charge in the short url creation for better security and ensure that the urls dont be potencially malicious
5. Always validate the validness of an url and avoid SSRF attacks
6. For annonymous users we use the ip and browser fingerprint to know who or where was created the url
7. The services will be autoscallable to manage traffic havy changes
8. 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.
9. 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
10. 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:

1. 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
2. The creation of short urls is more expensive in time to ensure security
3. 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
4. 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
5. 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