Loading...
User submits long URL, gets short URL
heavy-read, optimized for fast reads, strong availability over consistency with eventual consistency
100 M+ daily active users, generates around 1B redirects (reads) per day and about 10M new short URLs (writes) per day. 100:1 read-to-write ratio.
Total storage over time (7 bytes) + long URL (200 bytes) + metadata = 500 bytes. At 10M/day x 500B = 5GB/day -> 1.8 TB/year
3.6 TB in years
1.8/year * 5years = 9 TB in 5 years
Request: POST /v1/url {longUrl} -> Response: shortCode (201)
Request: GET /v1/urls {shortCode} -> Response: 301 redirect
Client Request -> API Gateway -> GET Request -> Cache (Redis) for reads, on misses it goes to DB to fetch longUrl.
Client Request -> API Gateway -> POST Request -> Cache (Redis) see if it already exists, return in cache or on miss return DB fetched longURL. For new URL: Client Request -> API Gateway -> POST Request -> Cache (Redis) misses because it's new -> writes to DB, and updates Redis with new cached entry.
For Redis we'll add an expiresAt field to retire entries after specified time.
For shortCode generation, we'll use a counter ID with base 62 encodings, this is to avoid alternate approach of random string hashes based on long URL as they are more collision prone.
Storage Layer: We'll go with NoSQL cassandra DB that will mainly consist of key/value store, short code is key, value is long URL. Redis will contain it but with an additional column expiresAt (a timestamp) to remove entries in the cache as they become cold, no reads for a shortCode over a specified time. Everytime read is used from cache or db fetch timestamp gets updated.
Since this will be heavy-read and only storing a few columns.
NoSQL Cassandra Database will be used with Redis in front of it.
Cache (Redis) on misses we query or write to (based on request) to database.
Cassandra DB: urlShortener {shortCode, longUrl}
Redis: urlShortener {shortCode, longUrl, expiresAt}
For ID Generation, I decided to go with a counter ID with Base 62 encoding versus a string hash of the long URL which is prone to collisions if hash algorithm is not strong enough. With the amount of URLs expected, counter is more safe. The only concern with a counter is handling multiple regions or nations, the solution there is to prefix it with country/region ID. The prefix will be shuffled with bits using random salt before Base 62 encoding.
For caching, Redis retires cold links after specified time, on cache miss it performs a DB fetch. For links that are down or no longer viable we'd prune from DB based on a timestamp and on new requests for the shortCode.
For Partitioning/Sharding, hash the short code so every redirect routes to exactly one shard, no scatter queries. Also, we'll use consistent hashing to minimize reshuffling when adding shards.
For viral link, we'll add read replicas per shard when volume of requests peaks.
For 4, rate limiting would be important, especially when hitting Redis based on IP and Region. Also, we can use a token bucket to smooth bursts with 429 Retry-After headers so clients know when to retry.