Loading...
Requirements
Estimated Url created per day:1millions url
Url per Hours:~42000
Url per Seconds:700
Assuming read write ratio of 100:1 we will hv nearly 70000 red requests per seconds means we will might need to think about caching.
Storage Size:We will store id,longurl,shorturl,created_at and some metadata associated with so each row assuming takes 500 bytes
Storage Per day:500Mb
Storage Per Month:15GB
Storage Per Year:180GB
Storage Requirements for 10 years:1.8Tb
So majorly at first we will hv two url one is read url and another is write url.The write url just takes the long url and sends a post request to the server.the server saves it in db and sends a response with short url in response,the read url just sees which long url has been asked and returns the short url.
The api will be /create-short-url and /get-url.
The user inputs a url to be created and the server responds with a 7 letter short url.And for the read requests we have a redis caching layer between server and db .Each key in redis will store minimal info for max storage of keys such as the long-url and corresponding short url along with some info like ip address for analytics .Also redis max memory config i will set to least recently used(lru).
Now to scale it further all fo the designs we chose are single instances hence single point of failure .To resolve this we can hv multiple instances of each layer so that none of them becomes the bottlenecks.
I would start with relational db postgres sql since its offer simplicity and great consistency.The schema would be itself very simple it would hv a single table at the start with an uiud,long-url,short-url and some metadata like created at .This ensures our schema remains very simple and extremely scalable.Later when amount of data becomes too big to manage we can shard it by id.Basically we can use a hash function to shard them across different partitions.This distributes load on db uniformly but it also makes range queries difficult.We will also have a bloom filter for each shard which means each shard maintains its own filter.We can add indexes to speed up read queries on db.
Now comes the analytics portions -so each url we would hv ip address and counter on redis to maintain a count so that we can analyse it later.We can add promesthus and grafana to set up monitoring for our applications.
If at any point in future the workloads becomes high we will use a replicatoins+sharding strategy.I would create multiple read replicas with eventual consistency .This spreads loads among those replicas and i would use quorom writes.Where no of read replicas woudl be 2 and no fo write replicas also 2 and total no fo replicas 3.this ensures in case the primary write replicas go down we would have atleast one replicas which would be consistent.I would also add a zookeeper where all the servers and the replicas are subscribed to for changes.So if one server or one node goes down the zookeeper can remove that replica for actives and we can observer the reasonw hy it went down.And the applications still remains highly available .I would also design the applications to be partition available else low latency this ensures in case of network paritions node continue serving read requests.
I will make each short url as 7 letter length and they would follow the base62 encoding scheme (0-9,a-z,A-Z).This alligns well with our capacity eg for 10years as per capacity we would need for 10years around 3.6 billions url and this 7 letter lenght will give us huge numbers around somethings in 3 trillions.So even after 10years we wont be still hitting close to the capacity.Afte r10year we would hv used around 3.6 billiosn url which is still less than 0.1 of total capacity.
We can use other approaches like hashing the request counter and converting to base 62.But this approach is deterministic and anyone can be able to predict what hashing would be produced.We can avoid this by appending random url characters to the end .But this would also need distributed counter management.
Alternatively we can hash the long url into sha based hash and take the first 7 characters however this approach can also lead to duplicates because truncating it to first seven characters can cause same short url hashes to be produced.
The most simple solution for this will be to just pick random characters from base62 alphabets and then just check if the key exists in db.And if it exists we can just create other random key and do the same check.Since we hv huge address space around 3.5 trillion probability of generating same keys is very less.And to optimise the checks further i would also use bloom filters .The insert would first query the bloom filter and only proceed if it returns no.If it says yes we might need to do some extra lookup but thats veryvery rare. And here in this case we will also need to tune the size of bit arrays and the no of hash functions and the no of items we are gonna store in the array.
I would also add a load balancer in front of our servers with round robin configurations .this ensures all of our servers will hv a equal amounts of balance .Also a cdn to cache our static frontend assets and some of the most used keys to further reduce loads on our servers and redis.The redis keys would hv max ttl of around 1 day +some random timestamp so that all of our keys dont expire at once and flood the database with very high reads.
I would also incorporatte a rate limiter which stop millions of requests coming from the same ip or malicious request or ddos attacks.I would use a token bucket rate limiter as its extremely simple and storage efficient and it also supports burst requests.All of these things will be supported by metrics using promethus and grafafna for monitoring.
Apart from this for ensuring very high availability we can have cache the most used urls in the user browser and also in cdn layer.So this prevents huge amount of requests from overwhelming our servers and also ensures high availablity.Our api woud also return a 302 response whihc means a temporary redirects instead of returning a 301 response which is permanent redirect .