Loading...
100 million users * 5 urls = 500 million url per day
around 6000 url generated per second
182.5 billion urls generated in a year
2 trillion urls generated in a decade
With 10-100 clicks on short url, could be up to 60k reads per second
Two endpoints
Post endpoint
/url
{
url:
}
Get endpoint
/url/
404 not found if short url not registered
302 redirect to actual url short url maps to
First we have an API gateway, this will handle all incoming requests and any authorization/rate limiting we want to add on later on. This'll be a clients first point of contact into our system
Then we have 2 load balancers, one for Post and round robins requests to the url generation service. Similar for the other one but round robins to url redirection service.
Two services - allows us to handle scaling read/write independently
one to handle generating new urls
one to handle reads on short urls, multiple replicas of this with loa
URL generation
We support alpha numeric values, lower case and upper case, which equates to 62 possible characters per. 8 characters (length of short url) should be enough urls to support the life time of our service.
For URL generation, we can do it either by hashing the long url or by pre-allocating blocks of our short url domain space.
Hashing would be fast, but there's a risk of collisions that we'd need to resolve. Linear probing can be done in this case and we increment the hashed value until there's an available short url. With consistent hashing, if we need to scale up storage, we'd be able to scale up by only repartitioning a portion of the data.
Pre-allocating blocks would be done by having another service responsible for keeping track of the blocks of short urls that have been used (this would need to be stored also). Whenever one of the replicas of the url generating service starts up, it asks for a block from this service. When the block generation service provides a block, it marks it as used forever in storage. The url generating service uses urls from the block until it runs out, when it then asks for another block. This ensures there's no collisions amongst the url generating services when they're running in parallel.
Hashing vs pre-allocating - we'd have additional complexity for the pre-allocating approach with another service and needing to store all blocks of urls that have been used. We can go with the hashing approach to reduce the number of components in our system.
NoSQL data base for storing short url to long url mapping (the data we're handling isn't relational and key value store works well in this case as we're storing mappings of urls). Let's say for now we're using DynamoDB, which provides automatic partitioning via consistent hashing and availability guarantees across regions/availability zones
Consistent hashing uses a logical ring. Shards are placed on the ring using a hash function. Keys are also hashed onto the same ring and assigned to the first shard encountered when moving clockwise.
With shards A, B, and C on the ring, each shard owns the keys between its predecessor and itself. If a new shard D is added between C and A, only the keys in the range (C → D] are reassigned, moving from A to D. All other keys remain on their original shards.
To ensure that we return the same URL for a long URL that's submitted multiple times, storage has both mappings of url
short -> long
long -> short
To support faster reads, add a Redis cache with LRU eviction policy to avoid having to read from storage.
Url Generation flow
client -> gateway -> lb -> url generating service
At url generating service
Start a transaction with the
For URL generation, since there are multiple instances, we need to handle the case if the same long url is submitted to multiple services.
For read performance, we can consider having a LRU cache (Redis) that the url fetch service would check before querying the storage.
Track cache hit/miss and adjust cache size accordingly