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.
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