System Design Interview Question: Design URL Shortener

[@vijayansivaraman7923]

@Hayk Simonyan, In my 13 years of experience in .Net as as full stack developer, So far i didn't see any other channel explaining this much crisp and clear with animation images to understand better. Kudos to your effort and hardwork. Very much Appreciated. I wish you will get more subscribers and will reach great heights. Can you post videos on Angular, Javascript and .Net 7, EFCore , Azure full tutorials with real time examples ?

[@hayk.simonyan]

@vijayansivaraman7923 It's great to hear that you're interested in these topics! Expect more tutorials like this here. I'm not an expert in .Net, but I'm planning to post about JS + frontend frameworks (Angular, React) and cloud providers (Azure, etc.) on this channel

[@Coding101-nb5ej]

I feel like I should have paid for this level of insights. thank you so much for sharing

[@hayk.simonyan]

Glad to hear that

[@mattf4089]

@@hayk.simonyan Agreed. Thanks for the great content.

[@hayk.simonyan]

@@mattf4089 You're welcome!

[@kzrfaisal]

Wooahh....I have watched so many videos on this topic but always loose it in the middle of the video, but you made me stick to the end, the amount of simplicity you brought in system design explanation is commendable. We really need more of these 🙌. THANKS A LOT.

[@hayk.simonyan]

Great to hear that!! Expect many more

[@RandomGuy34-j1u]

Damn this is some gold content !! Absolutely loved it !!

[@hayk.simonyan]

Thank you!!

[@GermainHirwa]

Let me take this time to thank you for this great video Sir. I have my first ever LinkedIn system design interview for my university internship and I feel a little bit confident after watching your video a couple times. Will watch it like four to five times and will be good for the interview. Thanks again for this lengthy free resource. I appreciate

[@hayk.simonyan]

You're welcome! If you're preparing for system design interview, I suggest you watch the other 3 videos as well from this playlist kzbin.info/aero/PLdNCznBZ77NqqZMrLPRb1RLm7LObOCb21 to be prepared for different scenarios. And wish you good luck in your interviews 💪

[@jorgegallego9672]

Hayk you are my favorite system design channel. Congrats, no other channel taught me as much as you did!

[@hayk.simonyan]

Thanks! Glad you enjoy it!

[@sankalpswami3335]

simply the best!!!!

[@JoseSanchez-vv1zd]

Excellent video. Thank you for creating it!

[@hayk.simonyan]

You're welcome!!

[@janakiramankirthivasan5955]

after watching five different videos , i finally understood the concept from yours . Thank you very much!

[@hayk.simonyan]

You're welcome. Glad it helped!

[@karvinus]

I tell you why your videos are better than others. They are short and to the point. At the same time they are covering everything in depth without feeling being rushed. This helps me understand to pace at which i should deliver mine. mine will be slightly longer because of drawing and asnwering questions.

[@hayk.simonyan]

Thanks! I always aim to condense essential topics into brief videos, cutting out unnecessary details to save your time 👍

[@vinoths7140]

I am grateful for your help in making me understand.

[@hayk.simonyan]

You're welcome! Glad it was helpful.

[@2sourcerer]

10:12 you said the system with Postgres doesn't handle generating 1000 URLs / sec so cache layer is introduced. Yet 10:22 you talked about "popular URL" which implies the URL is meant for a redirection service. So is the caching layer needed for both creation and redirection? I don't understand how the creation could be "locked" with cache?

[@hayk.simonyan]

The caching layer in this system is mainly for accessing the URLs from the NoSQL database, not when generating them via URL shortener. That's because this is a read heavy system, meaning it will get many more reads compared to writes

[@passionforsciencel5180]

Hey, I stumbled upon a more efficient approach for the initial step of our URL shortener project. Instead of the traditional method involving database creation and random ID insertion to ensure unpredictability, I devised a single script. This script generates IDs synchronously without relying on a database. It's incredibly memory-efficient (no heap allocation) and adept at handling high traffic seamlessly. The secret? Just a simple mathematical concept. Intrigued? Let me know if you want to dive in! 😊

[@hayk.simonyan]

hey, yes creating all keys upfront will be inefficient. A better approach is to start with a database auto-incrementing integer as your unique identifier for each shortened URL. Then encode this integer into a short alphanumeric string (using base62 or similar techniques) for a compact and user-friendly representation

[@passionforsciencel5180]

@hayk.simonyan, I have come across a mathematical concept known as the "Modular Inverse" that could revolutionize the approach to URL shortening, eliminating the need for a database entirely: First, select a large prime number, denoted as 'm', ideally the nearest prime number to the anticipated number of links to be generated over the lifetime of the application. Within your application, initialize a counter, 'i', starting from 2 (1 always return 1) and incrementing up to 'm'. For each incoming request, return the modular inverse of 'i' with respect to 'm'. This operation guarantees unpredictability and non-repetitiveness due to the prime nature of 'm'. Increment 'i' by one after each request. Here's an example with 'm' set to 37: i = 2, result = 19 i = 3, result = 25 i = 4, result = 28 i = 5, result = 37 i = 6, result = 31 i = 7, result = 16 i = 8, result = 14 i = 9, result = 33 i = 10, result = 26 i = 11, result = 27 i = 12, result = 34 i = 13, result = 20 i = 14, result = 8 i = 15, result = 5 i = 16, result = 7 i = 17, result = 34 i = 18, result = 35 i = 19, result = 2 i = 20, result = 13 i also searched about the time complexity of Modular_Inverse function and i get O(log(min(i,m))) . So what you think ? Best regards, Bouzid Kobchi

[@hayk.simonyan]

@@passionforsciencel5180 it's a clever approach 👍 For URL shortening systems where the anticipated scale is known, this inverse method might be a great fit. However, for large scale systems where flexibility, unpredictability, and advanced features such as custom short URLs are expected, a traditional database backed method is likely more suitable

[@passionforsciencel5180]

@@hayk.simonyan Anyway, i like to mention it , sometimes mathematicians can replace us 😅 Thanks for your feedback

[@AizazShahid-ck8cn]

Why not use a database with B-trees instead of LSM + SST in Cassandra considering we want to optimise for reads? And if we use that then we can use the same database for storing short URLs as well rather than doing another network call for the short URL from a separate databse

[@hayk.simonyan]

Good question! While B tree databases could optimize reads for this case, the choice of LSM-based systems (like cassandra) often comes from their great scalability and distributed nature. It also excels at handling high write throughput and horizontal scaling and these features are important for handling the massive traffic and global distribution typical of URL shorteners

[@AizazShahid-ck8cn]

@@hayk.simonyan What makes Cassandra better for horizontal scaling compared to something like mysql or postgres? In this scenario, complex multi-shard joins is not really a use case then what makes LSM-based systems scale better?

[@hayk.simonyan]

@@AizazShahid-ck8cn cassandra distributes data evenly and ensures high availability unlike MySQL/postgres, which require complex sharding logic. And in a URL shortener we typically prioritize write performance and scalability over complex multi-shard joins

[@ntnmnk2009]

How do you use the two databases, one SQL and another NoSQL? Like what is each database's purpose?

[@hayk.simonyan]

Sql database keeps track of the available keys, and Nosql is the primary database that stores the shortened URLs and their metadata

[@girjashankar7925]

why do we need url shortening and lengthing techniques?

[@hayk.simonyan]

Example use case is for posting on Twitter (X) which limits your characters and you need to shorten some URLs to fit content. Another example is to also add tracking through this URL.

[@user-gj1ps4kq3e]

Don't we also have to scale Postgres ?

[@hayk.simonyan]

Initially postgres will have less load compared to nosql database because it stores simple structured data, but along with user growth yes, postgres might also need to scale

[@piotrkulinski922]

Low latency as functional?

[@hayk.simonyan]

no, low latency was mentioned in non-functional requirements section

[@LironTal-q4x]

I don't understand, you mentioned that: URL shortener service contains logic for * generating short URLs * Storing URL mappings * Retrieving original URLs for redirection Then why there's no connection between service and DB in the diagram? Why don't we replicate the service itself? How would the service know the short URL doesn't exist already? Thanks

[@hayk.simonyan]

The URL shortener doesn't read directly from the NoSQL database, but the information that is needed from NoSQL can be passed through the web servers to this URL shortener. That's why you don't see a connection in the diagram. Hope this helps!

[@LironTal-q4x]

@@hayk.simonyan Still unclear, and I'm extremely curious :) 1. Storing URL mappings - Meaning it passes the mappings through the web servers and to the database? Same for reading? 2. Why don't we replicate the service itself? 3. How would the service know the short URL doesn't exist already? 4. Is this a design pattern going through the web servers? thanks a lot

[@hayk.simonyan]

​@@LironTal-q4x 1. Yes, in the most basic form of this desig, web server checks the availability of a url from URL shortener & if it's available it stores the mapping in the database (same for retreival) 2. You could replicate the URL shortener if needed, but in this case one service should be enough for storing 3.5T keys 3. If the short URL already exists, our web server will notify the URL shortener and that short URL key will be marked as used (the value will be set to false) 4. Yes, the requests go through web servers

[@LironTal-q4x]

@@hayk.simonyan Ok last question if I may generating short URLs and storing them, I understand it's the shortener service job (because it can access the SQL DB of keys, and tell the web servers what to store in the NoSQL) But I don't understand the redirection part, if I wish to redirect a user through the GET /api/urls/{shortUrlId}, why can't I let the web servers look directly at the No SQL for the tiny url? why do I have to go through the shortener to do redirection? thanks!!!

[@hayk.simonyan]

@@LironTal-q4x you only go through the shortener the first time when you create the shortened URL (to check the availability of the URL) and when a user removes their shortened URL, you mark that URL as unused via shortener service. But the redirection is happening through web servers, not through URL shortener.

[@chessmaster856]

How is az different from AZ in case of url.. also this calculation does not have much values Is your code and database scalable? That's all

[@moonlight-kh6uz]

Even with Canva, it is a time-consuming to create these diagrams, and then add text, narrative. Does it pay off?

[@hayk.simonyan]

You're right, creating these presentations is time-consuming. If you mean in terms of YT monetization, then no, it hardly even covers the Canva pro subscription ))