Loading...
Let's start with some capacity estimation:
A single long URL might be 100 bytes
A short URL might be 20 bytes.
There will be some extra metadata to store along with this like hitcount(8 bytes), user (20 bytes) who created the URL, Expiry date (8 bytes)
That make around 150-160 bytes. Let us assume worst case of 256 bytes of data per mapping.
Assuming there are 10,000 DAU and about 1000 of them add a URL everyday. 1000*256 bytes is 256kb. Over a year this would be around 93 MB. This is small enough to fit on a single postgresql database without any other additional features.
For starters: I would simply need a server and a database. The server maps the received URL to a short url and returns the short URL, and saves it to the database.
For reads: i hit the read server, which just queries the database and returns the response. The client can handle calling the analytics service for now we will improve upon that.
Okay to go futher i have added multiple servers so that they are available. Load balancer to forward requests to these servers. Database now has read replicas for faster reads. A cache layer has been attached to the server so that cached requests are handled by the load balancer itself without hitting the server.
Analytics will also be forwarded through the load balancer.
Caching layer would work like this: if load balancer is able to find a request in the cache it would return the key value from the cache otherwise it would go to the servers in a round robin fashion to let it fetch the corresponding long url from the database and then we would evict some old key based on some eviction policy such as LRU or LFU and insert this new key.
Write service would access only the leader. Read servers can access any of the read replicas and leader. We will be using strong consistency to ensure the URLs are available and up to date.
For deleting URL's we can use a tombstone to indicate that this url does not exist anymore.
For identifier generation I can use some kind of hashing algorithm. Base62 is good enough for it. It would help compress the URLs enough to shorten it and there wouldn't be any collisions as its not a hash based process and unique for each string.
Another issue is we want some kind of randomization between the URLs otherwise people would just be able to go around to other URLs. We can use a hash function over our generated identifier to give out a usable random key. Another issue is if two people use the same long URL it would give out the same short URL, for that we need to add some kind of randomization as well after the hash function to avoid hash collision as well as protect privacy of users.
Another issue is we want some kind of randomization between the URLs otherwise people would just be able to go around to other URLs. We can use a hash function over our generated identifier to give out a usable random key. Another issue is if two people use the same long URL it would give out the same short URL, for that we need to add some kind of randomization as well after the hash function to avoid hash collision as well as protect privacy of users.