Big respect for your knowledge and how you unselfishly share this. There is no one on RU-vid that does this in such details. Keep doing what you are doing man.
For anyone wondering, apparently a "lakh" or "lac" as he was saying at 29:57 "is a unit in the Indian numbering system equal to one hundred thousand" - Wikipedia
Yeah, indian numbering doesnt go up in terms of 3 digits like (thousand, million, billion, etc..) It goes up in 3, 2, 2, ... eg . 1,000 -> Thousand 1,00,000 -> Lakh 1,00,00,000 -> crore ...
An additional strategy: have one or more background worker processes generating the base 62 random strings, checking they don't collide and adding them to a stack, creating a buffer of safe random values the app servers can just pop and use. Fantastic video, thank you.
Great video, maybe you can start with the API calls, Functional and Non Functional req to make it clear where are you going which will help you define your writes and reads and you could split the app servers to optimize your design. Also, I would like to know more about your approach on the reassigning or cleaning of ranges as those could go fast if you have such a limited number of characters for the short URL and reusability would be a factor as your number will be used completely within the first two years according to the analysis you had.
THE BEST SYSTEM DESIGN VIDEO SERIES. I've seen other channels, I must say they are nowhere in the competition, because all they do is talk, and but You are doing fantastic work - You have your own study, references, alternative solutions to every system design problem and the way you deliver is fabulous. Simply loving this series. Thank you for everything - Keep up the best work !
Very well explained with all pros and cons way of implementations and finally landed with a robust and scalable solution. URL shortener looks simple but very hard and I rarely found anyone else reaches close to your solution and way of explanation. just advice will be better if you explained with UML and ER diagram representations as well.
Excellent... from then i opened account 12 years ago.. i had not commented this world.. hats off bro to the capacity of sharing knowledge... only a few are there.. you are one among
Great video! Some helpful feedback so that viewers also know this. Your base62 function has a typo. Instead of doing the regular division of deci and 62 ( deci /= 62 ), it needs to be an integer division so that you are not infinitely dividing because you will continue to output a value as you approach zero. The function will not exit until you are so close to zero that python will basically consider it zero and exit the while loop. So it should read deci //= 62 instead. Thanks again, cheers.
Thanks for your work! One thing I noticed is that if you use the counter method, it may generate multiple new 7-character strings for the same long URL. A malicious client may keep sending requests for the same long URL and the system may run out of keys.
Software Engineer in Google, I barely write any comments, but you really did good job by making those impressive videos. Really appreciate your work, inspired me a lot and I learned tons of knowledge from those.
Thanks for the excellent video. learned a lot. A follow up question : if we set expiration date for short URL, how can we collect or recycle the numbers used for those expired short URLs? Thanks.
So there are a couple of approaches as explained in Grokking the System Design interview and I am quoting them here : "If we chose to actively search for expired links to remove them, it would put a lot of pressure on our database. Instead, we can slowly remove expired links and do a lazy cleanup. Our service will make sure that only expired links will be deleted, although some expired links can live longer but will never be returned to users. Whenever a user tries to access an expired link, we can delete the link and return an error to the user. A separate Cleanup service can run periodically to remove expired links from our storage and cache. This service should be very lightweight and can be scheduled to run only when the user traffic is expected to be low. We can have a default expiration time for each link (e.g., two years). After removing an expired link, we can put the key back in the key-DB to be reused. Should we remove links that haven’t been visited in some length of time, say six months? This could be tricky. Since storage is getting cheap, we can decide to keep links forever."
Hi, If I reuse one of the expired link again then is it possible that a customer tries to access a very old URL and gets redirected to a wrong URL ( recently used post clean up) . This might cause an issue if , a system needs to provide short URLs and keep the mapping for 10 years . Any solution for this?
@@sombudhya That is genuinley good question and to be honest I think you may be right... according to this design I cant see imagine thaa a mapping will guarantee no repetiion of url "keys". But if you look at it pragmatically, to run out of 62^7 addresses your service needs to have to go through 3.5 TRILLION Writes which is alot 😂 but.... a busy service *could* use that up very quick..... a simple solution to that problem could be to transition to 8 character spaces on top of precious 7 character, that is over 22 TRILLION URLS! and Im pretty sure for any system to loop back from that counter, so much time would have passed that the distributor of old links would have realised themselves....
@Tech Dummies How will it insure that tiny url length is 7 char? Since we are pasing an integer and what if we passed big integer and that return more than 7 char from base62 method.
One quick question. I did write the implementation of base62 encoder and converted a simple text to Base62. The number of characters in the output is proportional to the length of the input. As the input increases, the encoded string length increases. In that case, how can u control the code to generate only 7 or 8 characters? taking the first 7 chars might not be a good idea. What is the solution?
Thanks for this video. I really liked how in-depth you went in this one. I know it’s been a while since you created this video, but I would like to ask couple of questions: 1) We could just use the counter as the unique id for the short URL. This has the drawback of not generating enough combinations as each character only supports 9 combinations. 2) To solve the above problem, we are using Base62 encoding on the counter, which will always be unique because the counter will be unique. The question is how do you limit the encoded string to only 7-characters when the counter reaches a certain limit such that the encoding produces more than 7 characters.
Like you said we will use base 62 on the counter. Because we're using base62 we will actually have 62 different combinations for each character. Because counting in base 62 would include all these characters [0-9 A-Z a-z]. instead of just [0-9] 2) If you go to the highest number in base 62 which would look like: zzzzzzz this will equal a little over 3.5 trillion. Which is an extremely high number of unique IDs and that would take a significant amount of time to reach. But, after reaching that number then I assume they would probably clear out old data that aren't being used anymore and restart the counter... but if for whatever reason they could not keep up then I think, and I could be wrong, the solution would be to increase from 7 character limit to an 8. Which would make the number of ID's insanely high, over 200 trillion.
@@metaversity3586 I think Sarafs 2nd question was more in line with how do we use the base 62 encoding to generate a 7 (or a different specific number) char encoding? Do we simply take the first 7 chars of the encoding we get by converting the long URL to base 62 using the auto incremented id? Wouldn't this result in the same potentially non-unique issue as the MD5 encoding approach? This is something I am confused about as well.
3:00 - isn't it enough to keep 7 characters for each shortened url? The base of the url is going to be the same for all shortened so at this scale it would be quite significant waste of space to repeat the same thinh so many times if I'm correct.
Thanks for sharing such wonderful knowledge. I have a doubt here - Why cant we use timestamp number with prefix of server id and pass it to Base62 function to generate the short URL
When you perform Base62 on the Timestamp and prefix of server ID, the resulting string will contain more than 7 characters. Since the tinyURL cannot have more than 7 , you will forced to choose only first 7 or last 7 (as per your choice). This will create collisions.
Nicely covered in a simple, lucid manner. Easy to understand. Thanks for the same. Just one thing. How will the last solution handle the repeated shortening of URLs? Meaning, if the same URL is given twice for shortening, although counter will generate a new short URL, guess the system won't check in DB if the shortened URL exists or not for the same long URL. This can lead to lot of duplication, I suppose.
From what I understand of URL shorteners, what you described is actually a desired feature, especially in order to provide accurate metrics for the user (eg. if two users shorten the same long URL and want to know which shortened URL had the most visits, each shortened URL must be unique, not the long URL).
This is nice informative video. I had implemented Scheduler Server in past where zookeeper was in BETA on AWS cloudformation. Which worked pretty much but it is nice to use available services since it is such a pain to maintain separate code base.
Great video, thanks for the explanation. One question though. How do we make sure the short URL is always 7 chars long regardless the counter number (1 - 3.5 trillion)?
For the counter approach at 18:48 you said that counter will give unique B62 value and we don't need to check in DB. I agree that counter will give unique B62 value, however we are only picking first 7 characters from encoded string, which might still result in collision. Is that right?
I was also wandering the same thing until I look again at the code and played with and I got the answer. Notice that the base62 code that he showed is oblivious to the origin url, it is only output the counter in base 62. In this approach we ignore the original url while generating the key and only map counter in base62 as key to the original url
@@user-jp5ck4xw2t Does that mean our Counter would need to start at a number high enough to generate 7 characters on its own since 1 for example = n which would not work in this case. Also what if the 7 digit prefix of 2 numbers is the same would this cause a collision?
Good solution! I just want to add that if the application server goes down, the URL that was getting processed will be lost. To save us from that, we have to implement a temporary storage(with checkpointing) for a single app server or a distributed message queue for multiple app servers.
Thanks a lot for this! A few interesting questions: 1. How are the counters/addresses recovered after a 5 year cycle or when all of the 3.5 Trillion hashes are exhausted? 2. Does the zookeeper come with redundancy assurances? Or is it a bottleneck for the entire service?
The explanation is awesome. However, I have a query: if "A" generates "XX" as hash value (common first 7 chars) and "B" generates "XX" as hash value(common first 7 chars) then why can't counter value C1 -> generate "YY" (common first 7 chars) and C2 -> generate "YY" (common first 7 chars)? If yes, then there can't be a "No collision guarantee" + here insertion is done without checking presence in DB.
It's been 3 years and no reply... The counter solution does not use a hash. It's just a number represented in base 62 so there won't be a collision if the same counter values are not used
Hey I really like your content, loads of respect for you. I'd like to add to this that you can very easily use a combination of unique values and dropDups at schema level in mongoDB (NoSQL) to tackle the duplicate issue like this: new Schema({ shortID : { type : String , unique : true, required : true, dropDups: true } }); Unique alone is very powerful but in very rare cases it might not work if index is not refreshed, for those situation dropDups comes to the rescue. dropDups means that MongoDB will "drop" any queries which try to create a record with a schema value that already exists in the database. For ex: if you already have a record with name : bob and you try to insert another record with name : bob then this insertion will fail due to dropDups.
Your way of explanation is simply great. Since we are using counter to generate the hash key. For same long URL requests, you will store different hash keys which will unnecessary increase DB size.
Zookeepr is deployed as a cluster - typically you would have 3, 5, 7 or more zookeeper nodes managing many instances of an app (say 20-200 instances). Zookeeper knows how to synchronize itself so if app instance 5 went down, all zookeeper nodes will eventually (and rather quickly) know about it.
@@TechDummiesNarendraL Thank you for the videos! Amazing job! One question - if we need to restart all Zookeeper nodes in the cluster, how Zookeeper would know the actual count of the counter ranges when it goes up? Do we need to store it somewhere?
Awesome video! Something that is still unclear that every 'Build TinyURL' video/article doesn't explain is an example of actually generating the url. So we agree that we use the distributed counter and then base62 encode it. However when you encode a somewhat large number (much less than 3.5 trillion), you get a string that is longer than 7 characters! Ex. 1234567 ==[Base62]=> MTIzNDU2Nw That number is not even 1.5 million and we're way over the 7 character limit. If we truncate that and only take the first 7 characters, then we have the exact same problem as truncating the MD5 hash: collisions! Any help would be appreciated thanks!
Great analysis of the system design of a URL Shortener, we hit several of the caveats here especially when building the defender application, however; our job is far from done.
It seems to me that you didn't solve anything by adding the Zookeeper... Then the Zookeeper becomes the single point of failure, right? I.e. what if the Zookeeper is down? Also, the counter will give a bit strange short URLs, in particular they will be successive. Which could perhaps even be a security issue in some circumstances (it will be possible to guess valid short URLs).
We can consider ZK as a single service, but it is not a single server. It will remain available as long as majority of the under the hood machines stay alive. I'm pretty agree with you about "non randomness" of the resulting urls is a problem. Because your service is pretty DDoS-friendly :). But you can made this approach better almost for free. Say, you were given the range [2^16, 2^24]. You can generate some random number M from [2^16, 2^24]. And let your counter currently having value C. Then you can use (C xor M) instead of just C. This makes your urls not so much consecutive (you should not forget about the case when C equal to M :) ) Obviously, you can use more sophisticated hash functions as long as they are injective.
Hey Hi, Thank you for sharing your knowledge. Just one question, what if I use the same url to shorten it twice..it will generate 2 short urls..is that breaking a test case..or fine. I think we may need to keep a track of all the long urls also in a set so as to return same shorten url.
Same URl wont be converted to Short URL again. It returns the existing one from DB. If the URL doesn't exists in DB, Then it generates a new SHORT url.
@@saikishorer But what if two user try to shoten the same url at the same time , then in that case there will be two entry of the same URL , how can we avoid that.
Thanks for the URL shortener system design Tutorial. As you mentioned to avoid collision we can concatenate the counter value range [1 - the size of data type] if we consider counter as Integer then it will be 4 bytes, So it will increase the key size which is currently 7 characters long. Suppose if we append an increasing counter to each input URL. I think still it does not work because we are taking only 7 characters after converting from base64 or MD5. I didn't understand your point. Could you explain more it. Thanks
*Did he ask to concatenate? I think you can just store mapping of input long url to counter value in your DB that should be good enough and will guarantee zero collisions.*
@@studiousguy8138 but how will you map the hash in the URL with the counter. When the user uses the short URL, how would map it to the counter in the DB
@@rishabhjain2404 Hi! Rishabh it will not map to counter it will take it from database you can make the unique id as primary index and then while fetching it will be faster. SO when user click the shorten URL it will take the unique id fetch from database via primary index and as long url will be stored with short url you will get it.
@@shreysom2060 I think the question is, multiple integers can be mapped to the same hash using Base62. How to retrieve the long URL now if you only have the hash, as it may be mapped to multiple long URLs?
@@hoyiya i think he mentioned that every shortened url will be unique right,in that case it can act as primary index in rdbms and user can fetch it right? I will watch the video once again though
Thanks for the great tutorial, one qs I am wondering how to ensure we always generate 7 base62 characters with random integer/long as input. I tried with the lib I have, the number of characters is not quaranteed.
how about taking it as a digit system with 62 characters, that meas we have abc....xyzABC...XYZ012...789 corresponding to 0...61, so an input 0 will have output aaaaaaa, and input 1 will be aaaaaab, so aaaaaba will be 62. For numbers from 0 ~ 62^7-1, we can have exactly 7 characters.
It is OK to have the scenario you described. You could have two different shortURL point to the same longURL, but not the other way around. In the example he provided, two different longURL (said longURLA and longURLB) resulted in the same shortURL (us.com/GA29x51). As a result, when shortURL (us.com/GA29x51) was referred and translated back to its corresponding longURL, redirection could go either longURLA or longURLB, which is not deterministic.
There is one thing that bothers me is we solve problems by adding new technology (ZooKeeper in this example) and saying that it's highly available and never thinking about the case where the ZooKeeper fails :/
Great video! Really informative. Thanks a lot. I think there is still a missing component for invalidating the short url post expiration which was discussed during the core structure, but need to be discussed.
thank you - that was a great explanation! Imho, the only thing missing, worth mentioning is that app should have thundering herd protection - so e.g. if tweet gets viral we should avoid cache misses
It is very intutive and facinating to learn how these systems works behind the scene, i am watching this series as i if i am watching discovery channel.Thanks for sharing
This was a really good video. I read the solution in a different resource but it wasn't as clear and concise as this. Thanks for sharing your knowledge.
