Loading...
User should able to convert long url to a short url
POST /api/v1/generateShortUrl/{longUrl}
User should be able to re-generate long url from short URL
GET /api/v1/gerLongUrl/{shortUrl}
System should be highly available, Fault Tolerant
System should be consistent
System should be able to handle high traffic and should be scalable.
let us assume, long url takes avg. of 2 KB of space.
and we'll make short url of hash length 7 characters (in UNICODE, 1 char take 2 bytes so, 7 chars will take: 7 * 2 = 14 Bytes)
also, we need to evict old entries, say older than 1 month, so we need to store the time stamp.
so, we can assume upper bound of 2.5 KBs of data for each URL.
Lets assume, daily active users are 1 Billion.
out of which, 25% of them create a new short url, rest of them will only convert short to long url.
Daily write requests : 250M
Data for 1 day: 250M * 2.5 KB = 625 GBs of data for 1 day.
1 month : 625 GB * 30 = 1.8TB ~ 2 TBs of data.
based on our assumptions, our system is going to be read heavy.
Define what APIs are expected from the system...
API to convert long url to short url.
POST /api/v1/generateShortUrl/{longUrl}
API to convert short URL to long url. or, when user clicks on this url, we'll redirects him/her to the long url site.
GET /api/v1/gerLongUrl/{shortUrl}
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
Clearly, our design is Key, value store, where use is going to query on short url and we'll return the long url.
So, we'll require highly scalable, available and consistent db.
Since, our data is very much structured, we can also use RDBMS database that will have primary key as shortUrl. But we generally face problem as RDBMS is not horizontally scalable. We can shard this database.
say, every query starting with A - K will go to the node1 K - Z to node2 and so no. And if one node goes down, we can have a replica of the same node like leader/follower architecture.
but, this possess 1 serious concern.. say in future, we wants to scale up and wants to add more database nodes.. in that case, we've to do a lot of re-balancing.
We can overcome by this using consistent hashing.
or, we can also go with cassandra database which is Highly available, partition tolerant and we can tune the consistency to ALL. When a write request is coming on the coordinator node and we will write this request to all the replica node and then we'll return the ack for the write. Here, downside is, our read will become slow but we can achieve strong consistency.
But, we can read from any of the replica and will get the correct value.
Also, cassandra maintains Write ahead log and memtable and retains some data in memory. which will be v. fast than accessing disc. Once, data becomes huge, it will convert data to LSM tree and writes to SSTables. (Sorted String Tables, its some sort of AVL/ RED black trees)
Also, we are writing data / flushing data in batch, so writes are also optimized.
Verdict:
Use cassandra with primary key as shortURL and consistency param = WRITE TO ALL REPLICAS
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Explain any trade offs you have made and why you made certain tech choices...
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?