Loading...
-> For each input url generate a unique X characters long tiny url ( x = 7 )
-> No 2 input url should have same output tiny url as it would result in data corruption
-> Use a hashing algorithm like base64 to get the unique tiny url since with 7 characters we can generate a very large amount of tiny urls
-> Hashing algo requires a number as input , we can take either generate a random number pass it to the hash algorithm and generate the output tiny url , or we could use a counter which increments after each request , pass this counter value to the hash generator and get the output. Both of the above work with a single server and database check ( check in database whetether the generated hash exists or not, if it exists generate a new random number and get the new hash )before inserting an entry into the database.
-> There has to be a delete/cleanup mechanism to clean/delete urls older than some time interval . Lets assume to be 1 year
-> System should be highly available . For this we can have multiple instances of our main server and a load balancer to handle and distribute user requests.
-> System should be highly scalable. Since our database operations would be high read and write we would need to scale the database too, for this we would prefer a noSql database which helps in easy horizontal scaling, in case of sql database we would need to implement sharing and corresponding handling algo for making efficient queries . Also, we would have multiple instances of our main server which would help in scalability as it would help offload task on a single instance of main server.
-> System should be fatst. This could be done by implementing a cache between main server and database to fetch the short url. Also, indexing the correct columns in the database would help with fast querying of the results.
-> 10% of monthly activity on twitter
-> equal to 30 M monthly activity on our system
-> Data to be stored -> incoming url ( let’s assume = 1000 characters = 1000 Bytes ), generated_url ( 7 characters = 7 bytes ) , created_at ( a timestamp of about 8 caharacters )
-> This would mean we would require around 60 gb of data per month , or around 700 gb per year. This is a very huge data so we would need proper indexing based on our queries to the database
/createShortUrl
-> path = /createShortUrl
-> method = POST
-> Body = “original url “
-> output -> provide user with the short url
Since we need not require ACID properties here and also we would deal with huge read and write we would like to use a NoSql database, however even sql database would work efficiently.
We can use a mongo db (noSql ) db , with below schema
-> original_url : string
-> short_url: string
-> created_at: timestamp
-> We can utilize mongoldb ttl feature to set the auto deletion of older records ( to meet requirements of deleting records older than a year )
-> We would also use a cache layer after our Main servers and before database , so that the data is first written in cache and then in database, this would help with the eventual consistency of our database since records would be fetched from cache before being fetched from read replica and this would give some time for the read replica to come in sync with the master ( write replica )
Below are the high level components in the design
-> Client : The user which makes request
-> Load Balancer: , handle authentication, To distribute request between multiple main servers
-> Main server: Servers to handle and process a single request , there are multiple instances to handle for scalability and availability
-> Zookeeper: Zookeeper is a managing system which manages the counter values for each Main Server. It contains multiple ranges of number as slots. Whenever a main server is created or has its range expired it asks zookeeper for a new range, the zookeeper looks for available ranges in its system and assigned a valid unused range to the server instance . The server instance can now use number one by one from the range as a value of counter specific to the instance and generate unique base64 hash and store it in db. Whenever a range get exhausted for an instance it requests zookeeper for a new range, and the zookeeper provides the instance with a new range which is ‘un occupied ‘ and marks the newly allotted range as ‘occupied’ so as it does not give the same range to any other instance of main server.
-> Cache ; There is a cache between the main server and database layer so as to reduce the latency of the system and also give the time for the nosql database to become eventual consistent
The request to create a short url flows from client to load balancer
The load balancer checks for authentication and redirects the request to one of the main server instances using round-robin or least used algo
The main Server on its boot up had requested the zookeeper for a range and on being provided the range of values has it stored in its memory
The main Server selects the counter value from the range and increments the counter, if the counter value gets exhausted it requests the zookeeper for another range, other wise it just increments the counter
The main server uses the counter value to generate the base64 value.
The main server stores this base64 value in cache and then into the db, and returns the base64 value to the client
below is example of a document -> { id : uuid , short_url : ‘sdfghjk’ , long_url: ‘www.example.com/sfsdfsadfsdfsdfds', created_at: ‘2023-08-78 :: 2:34:99}
MAIN SERVER
-> We would use base64 algo to hash the 'counter' which is a number to generate a unique 7 character long short url
-> This counter value would be picked from a range of values , each main server has its own range of counter values assigned to it by zookeper.
There is not single point of failure for our system since we have decided using multiple instances of main server and databases . Also the zookeeper in itself is a distributed system , ie. It is a multimode system so if a single node goes down in zookeeper the other takes up the place and reconfigure themselves.
-> We could implement our own deletion / cleanup process for expired records instead of relying upon db functionality
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?