I think your system design videos are top notch and helped me tremendously. I usually spend my working hours writing code and not worrying about the design videos, but thanks to you I was able to bridge the gap of missing knowledge

We can optimise the generation of the URL part in your service layer by delegating the key generation part to multiple instances of offline services(KeyGenerationService). Each service will generate the keys in the particular range and give the pre-generated tiny urls to servers in need. Servers can also keep some unused url in their local caches to speed up the process more. Their will be some race conditions which could be taken care by designing the service properly to take care of interaction between different threads in the services. All in all, it is a great video, kudos to the efforts you put to come up with such content !!!

@tusharroy2525

7 жыл бұрын

its a good idea of pre-gnerating of tiny url. Thanks for bring this up. Hopefully other viewers will read this.

@rockylovesall

7 жыл бұрын

Awesome approach!, I think race condition we can handle via some synchronization approach.

@yasharshahi

7 жыл бұрын

+Tushar Roy - Coding Made Simple thanks for the great video. you can pin a comment if you want your viewers to see it.

@RussellWu

5 жыл бұрын

The pro of using a range is because of its compact size to be stored and operated on. Pre-generated keys will take up a lot more space and increase a lot more roundtrip time between internal services while calculating a tinyurl from a integer is relatively cheap. So I think it's only worth it if the calculation is expensive, like blockchain addresses.

@renjithr7676

4 жыл бұрын

in this approach you should first check actual url already present, insert only if not.

I appreciate your efforts in making system design tutorial videos. My algorithms for tackling this question: -6 characters long TinyURL: a. Use MD5/SHA256 on Base64 encoding with 6 letters long key (This was mentioned by you also, I uplifted it a bit) b. Use Key Generation Service for 6 digit keys already pre-computed - Key DB of ~500 GB size + Replication of this to avoid Single Point Of Failure + Lock system to avoid concurrency issue + Use Memcache to speed up -> Fetch key from DB and Use HTTP 302 redirect to browser, in case of success else return 404 to the user.

Tushar! I'm so grateful for what you're doing here on KZread! I've literally spent hours watching your videos on dynamic programming this last week to study for an algorithms module of mine. Even almost got a bit of your accent!

i really appreciate how indepth your design analysis was! thank you

Thank you so much for the video, I am really excited and glad to have you back! Keep on killing it!

Great to see design interviews. Welcome back :)

Great articulation & simple enough for non CS folks to understand. Thanks Tushar!

Again, very good content. I really like that you're talking fast and not waste time on things that are easily found on the internet (definitions etc.). Very nice to watch.

Hello, tushar, I would really like to thank you for your videos. recently, I was able to crack an interview by watching your videos. Especially your videos on Dynamic Programming are treat to eyes. Thanks again.

@tusharroy2525

7 жыл бұрын

+Rishabh Daim great. Happy videos helped.

Hi Tushar - Thanks for the awesome video! You asked how other people would design the url service and here’s my 2 cents: I would start the design with a stateless API service and write thru in-memory cache, backed by a relational database. Collisions are detected at the db level (eg. a unique primary key on the shorten url) and corrected by hashing the original url + a prefix. The regional issue you mentioned could potentially be mitigated with a combo of load balancer routing configuration and in-memory cache at each service instance. In the case of GET request burst, it is likely that the instances will have the URL cached. I would imagine this starter design is good for couple thousands URL per sec. An AWS RDS with SSD could handle up to 10K IOPS according to their doc. The in-memory cache size could also be adjusted for read performance. To scale up this design for higher volume, I probably would try the distributed cache with write-behind before considering Zookeeper. In general, I like to stay stateless if possible :) I created a simple tiny url implementation in case anyone is interested. github.com/edithau/simple-tiny-url

@tusharroy2525

7 жыл бұрын

+Edith Au thanks for your insights

Hurray ! The legend is back!! more design questions please. 😍😍

Thank you so much Tushar, your videos are always helpful! We really appreciate your work!!

People (multiple people) spend days/weeks/months designing a scaleable system. Then comes some hot shot interviewer with all the right answers he found earlier from his google search, and then asks you to design a tinyurl system and expects you to spit it out in 24 minutes? Also consider the fact that his company has a product that is being used by only a few users, that a Windows 98 PC could happily support. Interviewers really need to get off their fucking clouds and stop searching for unicorns.

@tusharroy2525

7 жыл бұрын

lol

@ripplecutter233

6 жыл бұрын

Vitamin B goddamn tech interviews. (begrudgingly goes back to studying some obscure algorithm that some brilliant mind took ages to figure out)

@sohineebasak4644

5 жыл бұрын

couldnt agree more

@gopala5334

4 жыл бұрын

lol, exactly said. I was asked to design the same in 30 mins, that too over telephonic discussion. Great video, thanks to Tushar Roy.

@borhadesumit58

4 жыл бұрын

I’ve exactly same view. People/scientists invest days, months or even years to come to solution and some stupid people expect to answer in 30 or 60 mins.

Dear Tushar, it is great to see that you are back in action. Thanks a lot for your efforts. I truly appreciate your hard work. Could you please share your knowledge on design problems. Thanks a lot.

@sagardafle

7 жыл бұрын

Navdeep Dahiya Kya baat hai

@tusharroy2525

7 жыл бұрын

I m trying. Started with tiny url and more to come.

@rohitkumarkhatri2203

7 жыл бұрын

You are awesome..... Plz keep it up with ur design knowledge.....

@UMAKANTJENABCE

7 жыл бұрын

Please continue to do your good work of design problems I am waiting for your next coming videos on this eagerly.

I love your videos, it's so elegant, clean and beautiful

11:17 so let's say you make your GET request on a newly generated md5 tiny url and the first result's long url doesn't match the long url you just entered (i.e. that tiny url already exists). How do you generate a new tiny url such that if the same link is entered again you'll be able to find the same one? Bit shift and repeat?

Brilliant video! Well explained and perfectly paced.

Very nice explanation. Please share more design/ system design topics. Thanks a lot.

@tusharroy2525

7 жыл бұрын

definitely

@deepamohan3157

7 жыл бұрын

when can we see more of them?

Appreciate such videos which give different/alternative ways towards solutions & one must go through various such views before finalizing on the solution. But seriously, only a king of fools can ask such questions & expect a good logical answers in those 10-15 minutes. I myself have got such questions with the expectations to say those fancy words of design patterns & algorithms. Man, such interviewers themselves do google the questions/answers for the interviews & they themselves don’t know to solve the trivial problems in their own projects. Many issues with interviewers’ mentality & processes but for such videos, these really help a person to think differently & find the solutions. Appreciate Tushar for providing such informative videos.

Thank you for this. I have been going through examples and lessons and this made it all click for me.

Hello Tushar, Thank you for the great explanation and making it very simple to understand the problem. Waiting for more designing problems. :)

Amazing !! You are like my guru dude learnt so much from you.

I was so so looking forward to your amazing videos ! keep it coming please .

@tusharroy2525

7 жыл бұрын

I will

Thank you for the video! That's the most organized / structured content (about app layer) I've seen for that problem.

great guy is back! more system design video please.

very enlighted video, thank you. I have a doubt: in Counter (2) All host method, why we need to add a timestamp into the bits, what about hostid(6bits)+random/increment bits(37bits)?

What is the advantage of the 3rd approach versus the 2nd? I fail to imagine a scenario in which it would be better suited than the second one, which I find elegantly simple.

Hi Tushar so good to see you back . Please upload more videos on system design

@tusharroy2525

6 жыл бұрын

+Akshay Suman doing it

WoW You're Back!

@nands4410

6 жыл бұрын

11 months ago

This guy and this video helped a millions.

the best i have seen on this is to pre-generate the short urls and keep them ready. Have relational DB with failover (two or more DB servers) to hand over these keys (relational allows to implement locking). Hash Partition the read shards with consistent hashing. You have the full solution without any single point of failure or hot-spots.

Curious why you choose 43 bits, as you only actually need 42 bits to represent 3.5 trillion (max for 42 bits is 4.398 trillion). Is there a use for the extra bit I'm not seeing?

@rohanabhutkar

5 жыл бұрын

Yes also since we have 7 char tiny url, and each char is 6 bits in base64, 42 bits is enough even if we use base64 encoding (a-z, A-Z, 0-9, _ , . )?

@adityasahai9020

5 жыл бұрын

@@rohanabhutkar he is using base62 because there are 62 unique chars.

@renurani3311

4 жыл бұрын

2*42 = 4398046511104 = 4.3 * 10 * 12 = 4.3 Trillion. So, we only need 42 bits to represent 4.3 trillion numbers But these numbers also include negative numbers and we only need positive numbers (0 - 3.8 Trillion). So we will 43 bits and keep our MSB as 0 to make it a positive number.

@Shogoeu

4 жыл бұрын

@@renurani3311 or we can use unsigned data type and save 1 bit :D

@zhongyuanzhang5611

4 жыл бұрын

@@renurani3311 ddkkokoi Iojkoiw e seeders (know((in(.m Mi

Great video! Very informative and helpful information.

That's was enlightening, Tushar. What do you think about probabilistic data structures to generate the tinyUrl? Like the MD5 hash you mentioned, I think we could use Bloom Filters to tackle the problem too.

@gkcs

6 жыл бұрын

Haha, yes I have become interested in bloom filters recently :)

@ryc8889

6 жыл бұрын

this was actually one of the things i thought of as well. I think a md5 hash might be too slow for an efficient bloom filter depending on the performance requirements but maybe it can be combined with the CDN idea. i was reading about bloom filters on wiki and there was an example about how akamai uses bloom filters in their webservers en.wikipedia.org/wiki/Bloom_filter#Examples

@thakur8711

6 жыл бұрын

Gaurav Sen, thanks for bringing up this point. I agree with you that we can use bloom filter to generate tinyURL. But there is a caveat. As far as I understand, bloom filter can help you to check if the hashOfBigURL(tinyURL) is already existing on the persistence layer or not. It will help us finding the existence of the tinyURL faster instead of going to the disk & finding it there. The remains part is how would you generate the hashOfBigURL(tinyURL) that remains not clear. Tushar have demonstrated those options to generate. Please correct me if there is any invalid statement I made.

@AmreshTripathi

3 жыл бұрын

My my we have a design principle celebrity here

@kavyashree513

2 жыл бұрын

0

Like video a lot, hoping to see more service design videos in the future

Very well explained, Tushar. Liked your presentation and the length of the video.

@Tushar, thanks for the video. 12:15-13:55 is a very convoluted way of conveying that log2(62**7) bits are needed encode 62**7 values. Also, that evaluates to 42 and not 43. An oversight, I presume...

Thanks Tushar your explanation was really simple and it did help me a lot to understand the topic well.

16:36 , can we reduce collisions by considering timestamp along with milliseconds?

@Himanshu-ed3mf

4 жыл бұрын

but that would increase the bits needed for the timestamp. from 32 to 48.

toooo goood. I think even the interviewer will also have to refer this as well. Hope to see more. :)

Legend is back :)

Tushar, I thoroughly enjoy your design analysis. One suggestion though, it would be beneficial for the audience if, in the description, you directly linked any reference to the dependencies - concepts, articles etc (example, Apache Zookeeper) that you talk about in the video. Thanks and keep being awesome.

@tusharroy2525

7 жыл бұрын

+Sudipta Karmakar I will add that

Great AWesome Bro to see you back.

Great Video. Can you talk about the retrieval part? Specially given a long url, see if we already have a url for it and give that back.

In md5 technique what is the action to be taken when we get a redundant 43 bits.?

Thank you for awesome explanation. Please post more videos for design questions.

Could you please tech more system design questions. Your architecture's is really well thought through

Wonderful, Tushar! Lot of details ! So much passion! I'm becoming your fan !!

@tusharroy2525

6 жыл бұрын

+Yamini L thanks

thanks for this, I was asked this in interview

I wish I could like this video twice!

Hey Tushar, thank you very much for sharing your knowledge. I'd like to request a discussion on how media (images & videos) is managed by big companies (youtube, imgur, etc) and how it is organized. Thanks!

@83rossb

6 жыл бұрын

look up content delivery networks (CDNs) and consistent hashing

Thanks for coming back sir

Hi Tushar, Awesome video and thanks for the same. The only minor observation I have is that 3.5 Trillion translates to a 2^42=4,398,046,511, 104 i.e. 4.3 Trillion. So we should be using 42 bits instead of 43 bits from the 128 Bit MD5 Hash ? 43 bits translates to 2^43 = 8,796,093,022,208 i.e. 8.7 Trillion.

@osrax

5 жыл бұрын

this is correct, I observed that as well. log(2) of 62^7 = 42

Perfect explanation. Thank you for your time and efforts. I really appreciate it if you can share your solution for "finding median in very large randomly distributed system?" (load on each system is known but not equal and numbers are not sorted and unique" Thank you again.

For people who are confused why do we need 43 bits: 2**42 = 4398046511104 = 4.3 * 10 ** 12 = 4.3 Trillion. So, we only need 42 bits to represent 4.3 trillion numbers But these numbers also include negative numbers and we only need positive numbers (0 - 3.8 Trillion). So we will 43 bits and keep our MSB as 0 to make it a positive number.

@vipuljain9550

4 жыл бұрын

However, Tushar says that 5 bits can be randomized, rather he should mention it as 4 bits, please correct me if am wrong.

@renurani3311

4 жыл бұрын

@@vipuljain9550 Yes, that should be 4 as he needs first 7 bits to represent number 0 - 63 (MSB is always 0 because number is positive)

@lugesot

4 жыл бұрын

I just want to say, you are so gogerous.

@vishalmahavratayajula9658

4 жыл бұрын

Thank you. This saved my time

@TheProCion

4 жыл бұрын

I don't think that this is correct. Just assume that the number is unsigned integer.

great man a good way to unwrapped complexity.

amazing, i have been watching your videos..

I remember timestamp is 64 bites(8 bytes). "The internal representation of a timestamp is a string of 7 - 13 bytes. Each byte consists of 2 packed decimal digits. The first 4 bytes represent the date, the next 3 bytes the time, and the last 0 - 6 bytes the fractions of a second"

@saam6348

2 жыл бұрын

With year 2038 problem, a 32-bit can represent Unix time. But it will end after the completion of 2,147,483,647 (2^31 - 1) seconds from the beginning (00:00:00 1 January 1970), i.e., on 19 January, 2038 03:14:08 GMT.

@liuhongqian

2 жыл бұрын

@@saam6348 I would be more than 70 years old by then LOL

Would it be feasible for every worker to generate a set of tiny URLs at the time of setup and store them in a resource pool (a queue, maybe)? In this case, if a tiny URL is released, or gets expired, it can be returned to the resource pool and reused. As every worker is generating tiny URLs within predefined limits, there won't be the issue of collision.

@Tushar Roy - Thanks for such helpful videos. Please keep doing more...

Thank you Tushar, vary helpful. Hoping you can post more design question videos. Thanks.

I think it is supposed to be 42 bits not 43. If you think about it, your language has 62 chars and to uniquely identify each char you need 6 bits. because 2^6 is 64. Then you can map 000000 to a, 000001 to b and so on till 9. So in a 7 character string each character will need 6 bits and 7*6 is 42. So you will have to save 42 bits in your DB and when you get it back from your DB, you have to use the same mapper and get back the characters. Hope that clears out the doubt around 42 and 43 bits.

@kingofwebguru

2 жыл бұрын

@Revanth Kumar Thanks for the clarification. I was thinking why it is an odd number (43).

@nrjdalal

8 ай бұрын

I have built one too rdt-li an open source free url shortener with built in analytics, check it out

It was very nice explanation! :) I've listened with pleasure.

@tusharroy2525

7 жыл бұрын

Thanks

Instead of base 62 we can use base 64.Just need to add 2 more characters. Underscore and dash(_-) can be added to 62 characters we have. This makes its easier to convert a MD5 output to a 7 character printable string as you can convert blocks of 6 bits directly to base64 character. Even this KZread link uses underscore to represent url of this video !!!

Tushar. I really missed you. Hope you can shed sometime in your busy schedule and create more videos like this

For the first 43bit MD5 solution, what do you do if you encounter a collision with 2 different long URLs, i.e., there are 2 totally different long URLs that has the same first 43bit MD5 sum.

@pllx2

5 жыл бұрын

Perhaps we could pluck some parts of the counter solution, e.g., take 30 bits of the MD5 + the 16 latter bits of the timestamp (since first 16 are much slower to change) + 7 bits randomly generated or by counter?

The best system design video ever!

@tusharroy2525

6 жыл бұрын

+erol yeniaras thanks

Dear Tushar, great topics and great details. One video on sms and email enrollment design pattern. Design options and best practices.

Welcome back!

Amazing video and explanation.. u got one more subscriber

Would it be correct to pass all randomly generated urls through a bloom filter so we can use the bloom filter to check for existence of the tiny url before using it instead of querying the database? We can say the tiny url is only valid if the bloom filter says the tiny url is not in the database, otherwise generate a new one and put it into the database. The length of tiny url would be increased to improve random hits on an unused tiny url, whereas recovering tiny urls by using expiration time on already generated tiny urls would also help.

Thanks. I so needed this

@tusharroy2525

7 жыл бұрын

+Praveen Chukka welcome

Ommggggg Tushar's first ever design video 😍😍😍

What are the tradeoffs between option 2 (md5) and option 3 (counter) besides that option 2 provides some de-duping?

When MD5 (or whatever has function being used) generates the same first 43 bit for two different URLs, how are we going to generate a new random number to avoid collision? Use a different hash function?

I think you should make more design videos, subscribers are waiting for it

Hope more leetcode problems, OOD problems and more other interview questions!

Awesome, learned some good design approach. Thanks

@tusharroy2525

7 жыл бұрын

+Sajjad Hossain welcome

How high is the load to overload a dedicated process/host which its only responsibility is to increment a single counter once on every request?

Thank you so much for this amazing content!

Counter based approach is not optimal. There are multiples challenges like maintaining the locking in a worker thread. Another thing these days deployment of worker node done multiple times in a day and every time worker will lose the counter and It will have to ask a new range from zookeeper.

I really learnt alot on this system design, good job

Hi, I have a doubt! what if same long-url is asked to be converted to tiny-url? If we use counter/timestamp it's going to create a new one every time and we will have duplicates. For md5 it will create the same hash for same string and hence we can avoid duplicates. So, do you still think zookeeper approach is better? and of course security threat

@dhananjayans

6 жыл бұрын

Hi, did you find a solution for this?

@whyareyounervous

6 жыл бұрын

Duplicates are not a problem, you can always scale the DB. But generally, you should avoid hashing to guarantee uniqueueness, as you are trying to map a bigger value set to a smaller value set so you WILL have collisions.

Hi Tushar that's a detailed and nice video. Thanks so much. Can you please post a video on 1.design of distributed cache of strings to reduce server hits. 2. Design of a memory allocator+garbage collector

When I did this, I took the insert-id from the database call and used the base36 of that id which would work as a hash key and as the id from the database in case the system needed to be be recreated in a new region.

@Tushar I have a question, if multiple worker hosts can access db , then even while executing second technique put if absent () , we can have conflict with any operation from other worker thread coming and executing a request..so is there any constraint that at a time only one instruction can interact with db ? same can happen in 3rd technique..stable prod. system might not deploy the third technique as well

What do you think about a system that is running in the background generating the urls before they get requested, so by the time someone gets a url you already have a huge amount of urls generated already and just link the url with the url.

@tusharroy2525

7 жыл бұрын

what do you save by doing that? generating a url from a number is by no means an expensive operation for today's computers.

@NovaMenteMedia

7 жыл бұрын

I was thinking on the request time of the API :p

@shubhamdave6039

6 жыл бұрын

I agree that generation of url is not expensive but if URLs are randomly pre-generated, we could have more security and possibly 0 collision. By that, I mean generate range based URLs but when assigning it, use random choosing from generated URLs. Just another way of looking at it...may be?

@jalaj1430

6 жыл бұрын

@Alejandro, I think this approach will work pretty well if nicely Implemented and will reduce overall overhead , collisions etc of the system pretty well. This can be a 4th approach and in my opinion better then the other 3 he has mentioned.

@badrequest403

6 жыл бұрын

True, but you have to be extremly careful in terms of security. Once generated and stored you have to make sure no one gets that full dump. This for example doesnt of course apply when you post a tinyUrl on twitter. But its a different story when you just want to shorten the url for your group of friends or family and so not everyone should see or have this URL. So yes the pre generation could work in terms of reduction in the possible collisions but you have to be extremly strict in terms of security. Because running bots against an dumped table is actually quit fast and easily done.

I have a question based on the concept inspired by this video at 7:40, If there is a concurrency race problem for multiple users buying inventory item, we can use serializable/optimistic/pessimistic locking, but what if two users read inventory item as with status unsold and both will call 'update inventory set status = sold and userId = A/B where inventory id = 1(for ex) and status = unsold' and only one will succeed, this way we avoided optimistic locking(rollbacks) although intrinsic write lock on row will be there fo all updates, for other users update will not update anything and they can try other items, What is this approach known as?? why don't we use it more often?

Sir with 42 bits, we can generate a total combinations of 4*10^12 and with seven bits about 3*10^12. So why did we take 43 bits and not 42 bits?

Thanks Tushar, Glad to have you here.

awesome, mate!

How do we handle the case when the base62 encoding of a counter is < 7 characters?

Impressive! It is also super helpful to practice with FAANG engineers at Meetapro through mock interviews

Didn’t get technique 3 .. the put will either fail due to collision or override the old value , am I missing anything?

Instead of covering how we will design starting from what we will ask the interviewer to creating high level design and then scaling that solution and so on and so forth, the presenter is going to detailed into how we will generate the tiny url etc. I would recommend looking at this for a good example of how to design tiny url www.hiredintech.com/classrooms/system-design/lesson/52

@abhikk4064

4 жыл бұрын

thanks

Around 9:14 Tushar describes a solution that first puts (short, long) to the database and then reads to verify nobody wrote after it. Doesn't the put corrupt the previous value that someone else left there (and wanted it as the value in the database)?

@gsb22

3 жыл бұрын

no, it is insert if not present.

To support ranges we created service that just give your process some range (x to x+100000) and increment counter in DB. It is guarantee the everyone is completely unique and that service is not heavily loaded

@tusharroy2525

7 жыл бұрын

+Aleksey Telyshev fair enough. That should work

I am not sure but how if we go with group of two four or eight character calculate its binary and add them as one and derived its decimal and thats your one character for url and same way to decode it( I haven't thought of that as of now) so no need to store in database an all that I.e www.facebook.com calculate binary of f,a,c,e and add them , to say 1001,0101,1000,1110= 1010 than this is the one character for that 4 character as per url gets long increment the group of number. Please correct me if I am wrong.

In regards to the third option for storing the URL - you say that the worker 1. generates a random tiny URL, 2. writes it, and 3. does a read to validate the tiny URL points to the intended long URL. Doesn't #2 override any existing tiny-to-long URL mapping that has the same randomly generated tiny URL? Isn't that a problem?

@the_sweet_heaven

7 жыл бұрын

I also have difficulty in understanding it. Suppose Even if worker creates a random and unique tiny url and put in db say t1--L1. Now when he get t1 won't he always get L1 ? what is that comparison for ?

@the_sweet_heaven

7 жыл бұрын

I guess the put doesn't override the previous value. So if T1--L1 is present then for the next time if the random tiny url gerenated is again T1 then when he put T1--L2 he still has T1--L1 in db and when he get() he get L1 not equal to L2. So he generate some T2--L2.

@vinodbhai3485

7 жыл бұрын

prashant patel but at table level if tiny url is our primary key , it will always same so it can not have duplicate primary key.

@nikhil199029

6 жыл бұрын

and regarding the same, why cant we use a simple mutex while writing to db?

@mrincodi

6 жыл бұрын

Yeah, I think he meant "put if absent".