Amazon Interview question: Learn hashing and consistent hash ring

[@cruxrebels]

Consistent Hashing begins at 12:35

[@dantedt3931]

Thanks!

[@govindraokulkarni]

big thanks! saved my 12 mins _/\_

[@JinayShah]

Thanks!

[@kmdr]

Worth watching the whole video to fully understand why you need consistent hashing in the first place.

[@ShuKlaDeepti]

Thanks much. All tutorials just draw the ring and explain this concept that is hard to understand. First time I understood what consistent hashing is after watching this video!!!

[@WaseemM2]

One correction or clarification. The hash for two keys might not be the same for two different keys but the modulo value can be same, which is where bucket collisions occur. Though there are hash collisions they are extremely rare due to possible large values available but the mod of hash will find many collision and that's where the linked list in a bucket helps. Good video.

[@sureshchandjain2504]

Nice catch !! that's what I was thinking too, whenever we talk about hashing we always keep a consideration that anyway hash function will return unique values for unique inputs. How hash function achieves that's a unique research topic in itself

[@carlaludgate6597]

Best explanation of consistent hashing I've seen. Thank you!

[@aniliitb10]

This doesn't give the complete picture (why/when). To get the complete picture, take a look at: www.toptal.com/big-data/consistent-hashing

[@alexpadilla5741]

Awesome video but it left unclear how it would remap data when a server gets added or removed. It still remaps, but not all data. And that’s the benefit. From above article: “So, how can this problem be solved? We need a distribution scheme that does not depend directly on the number of servers, so that, when adding or removing servers, the number of keys that need to be relocated is minimized.”

[@YashSharma0605]

Nicely explained. I had seen the circular implementation of Hash Ring and was wondering how will it be implemented in the system. In theory we can have a ring but while implementing it we'll have the table like structure which confused me. This explanation was a great help to me. Thanks!!

[@ersinerdem7285]

Is there a load balancer out there which uses this? I cannot see any of them using it. They use only round robin etc.

[@abhishek08aug]

I have a doubt on the failover part where you mentioned that if the last node is unavailable key-value will go get saved in the first node by following the cyclic order. If this is how it actually works, what happens when the last node comes back up and we make a query for the same key. Will there not be a situation that the system is trying to find this key in the last node but the key is actually saved in the first node?

[@manikandansaravanan5248]

how dose the rehasing happen when a new location added in the ring ?

[@vishalchougule3123]

In the given example, say a location is added that accepts values upto 11k, then the values in the range of say 10K-11K put in first location using ring ,will have to remapped to this location.

[@mananshah3471]

Excellent stuff! Coincidentally, the dog started barking exactly when called for it at 15:31 😂

[@leo71648]

Didn't understand the last part for 10115 no, greater key is not present and we go back and we put on first key but the rule was to find key which is greater than current hash key we got...... ???

[@kchaitanya39]

Doesn't 1011 location will be overwhelmed with values when a key does not fit in 9900 bucket?

[@ironhide9955]

i too was thinking about it. did you find an answer?

[@mramit1924]

Here you can find answer using virtual server kzbin.info/www/bejne/sJK1nIKEq956qJo

[@aleshep]

What's the purpose of wearing a cap? Is this helps to explain hashing?

[@reyou7]

best explanation on KZbin, thanks man!

[@TigraStyle]

+1 on that!

[@DK-ox7ze]

What happens when you add another computer to the hash set? In your last example, if you add a computer with memory address 13000, it will be greater than 9000, so data will be stored there. So the data which was earlier going to the first node/computer, will now go to the last one. This will cause inconsistencies in retrieval, because data which was earlier stored in first computer will now be searched in the last one, causing old data to be never retrieved.

[@ashishgandhi1686]

But that’s it. It’s just this one range, corresponding to the failed server node, that needed to be re-assigned, while the rest of the hashring and request-node assignments still remain unaffected. Contrast this with the classic hashing technique in which a change in size of the hash table effectively disturbs ALL of the mappings. Thanks to consistent hashing, only a portion (relative to the ring distribution factor) of the requests will be affected by a given ring change. (A ring change occurs due to an addition or removal of a node causing some of the request-node mappings to change.)

[@preety202]

Buy a mic please

[@_ipublic]

9:40 Use hash to store key-values pairs, what if for N inputs we get same hashKey and appending N values by nodes. White retrieval time complexity would become linear O(N). How do we get values in constant time though? Any suggestion on that would be highly appreciated.

[@shubhammehta319]

Nice Explanation, Thank you. I have one Question, What if one more server needs to be added in the hashtable. How we will assign the # function numbers. Like if we go for number 11k for e.g. we know that values for that could have been stored in the first row earlier. it Would make inconsistent as in getting that value will look for the 11k key but it was in the first raw not the last. please Explain that.

[@anxiousengineer]

An obvious approach could be to transfer values from first row to the last row that satisfy this criteria. Consistent hashing isn't perfect I guess, you still have some processing to do if you add a row, but it's much less than with regular hashing.

[@kisikatube]

In this case, you would move keys from 1011 to 11K location, any keys that are more than 9900. Note that in actual you would need to store the keys as well in order to relocate when a new server added. The advantage of consistent hashing is only one neighbor node need to looked at for relocating keys rather than whole data.

[@ShubhamGupta-mx2hn]

Little lenghty video , even i opened it after watching 4-5 video but yes we needed the starting part to understand the consistent hasing , if u are a new person.

[@PrateekMehtaABDFAN]

Thank you sir , huge fan of your videos . Superb content . Quick question:Complexity will be increased now with consistent hashing rt ? Earlier it was O(1) now it will be logn . Correct me sir If I am wrong ?

[@thealgomasters]

I couldn't understand how consistent hashing is helping in here, as if we trying fetching the values for dog and cat, we will be looking to same bucket (3030).

[@sharejero1121]

Went through many vedios to understand this. But your explaination is very good and in laymen terms so any new person like me can also understand correctly. Thanks for posting this.

[@davidespinosa1910]

Consistent Hashing is a made-up story told by Akamai to get a patent. The ring that everyone draws is really an ordered map, invented around 1960.

[@241praveen]

what will happen if the location is getting added back in hashtable once the node are up again in distributed env? e.g 10115 got stored in 1011 as there was no location more than it available in hashtable. but suppose 10300 got added in hashtable then what will happen? will it remap all key values?

[@sanjuexplore]

"Random numbers" for consistent hashing? How do we arrive at these random numbers? And What if the server at the end is available but not the one in middle. I found this illustration incomplete. Could we get an amended one pls?

[@gauravkathuria1920]

Hey , What if while inserting a key, some locations were not available and due to hash ring it goes to next location (circular way) . What will happen when those locations comes back and i am looking for the key I inserted ( When those locations were down ).Will not it give me the wrong answer ?

[@sergeykichuk2586]

Actually is bad explanation in first standard implementation 2 different hashes can give you same bucket! And don’t understand the advantage of consistent hashing when you will try to retrieve data from the bucket that is gone

[@prashanthtalla]

In case of consistent # ring, when a node is not available, how is the data retrieved? Also, when data is inserted, it will go to the next node. And when the non available node becomes available, how does the system knows where to find the data when queried? Wouldn't it look for the data in the now available node?

[@saaqibz]

Your explanation is very clear and nice. Thank you! One point is I think I like the explanation of consistent hashing using a circle diagram better, but this is very useful too esp when you're thinking about implementing it.

[@nreed7718]

I found the table to be a nice, concrete way to explain how this would work in practice.

[@himanshupanwar8408]

Sir you should improve audio quality

[@TechDummiesNarendraL]

Taken care in recent videos

[@akhilsharma1778]

In consistent hashing, you are only saving values not keys. Then how would we know what value corresponds to what key?

[@rahulsaxena2273]

At 12:01 when he is saying that we get wrong value. How we get wrong value because with equals key will not match so still it will return null. This same problem will occur in consistent hashing as well.

[@travelbuddy4000]

Hi, What happens when the node comes back on, how does the data stored on that node behave? Also, when the node comes back up, is that node added with the same random number, if it is a different random number how do we make sure the data is still consistent that was stored prior to node creation?

[@tango400016]

Please strip out music. Becomes difficult to listen to especially if you are playing the video at a higher speed

[@RitwikDas8690]

Just talk normally, your attempt at this weird accent is ruining your presentation

[@vedant9173]

Brilliant explanation! So what happens if the node that was down comes back up? Will we have to remap the key that was moved to the first node? Or does it mean we would have to search all the nodes for a key?

[@guidogranobles]

Good question

[@ashwathhegde8050]

i stopped watching right after 3 seconds because of the horrible echo

[@frankhart2018]

Love your videos, but what's with the fake accent?

[@RitwikDas8690]

Really bad presentation... Lots of mistakes too.

[@AmolGautam]

explained better than my college professor

[@fact-wala]

good explanation!! Thank you

[@kristhiantiu4317]

very very good explanation, thanks narendra

[@atulnath1474]

So great video, would like to add one thing here: We have two challenges which we try to solve with consistent hashing: 1. Minimize data movement/rehashing when we add/remove servers. 2. Evenly distribute data across servers. Your video talks about the first problem and how to fix it. For the second one, we can use the concept of Virtual Servers, which allows each server to occupy multiple portions distributed throughout your hash ring. This helps with skewed data; for example, if you add a server in between 2 existing servers, then the load on other servers is technically more than this new server, and the server after this. Basically, data isn't evenly distributed amongst servers, hence skewed. Having the same server hashed in different locations over the hash ring helps solve this problem as well

[@neelabhsingh1986]

Hi Narendra, I have some confusion at 18:15, suppose Pair (Rat, Grt) whose hash# 9015 is mapped at bucket #9900. However, due to issue bucket, #9900 is down, If we do mapping again Pair (Rat, Grt), it will give the same hash# 9015, because bucket #9900 is down, it will be mapped to bucket #1011, which is the first bucket. So my question is what happens if bucket #9900 is online, now if we try to get Pair (Rat, Grt) whose hash# 9015 will try to locate on Bucket #9900, and finds that not available so return null, however, this Pair (Rat, Grt) is available on bucket #1011. So how this consistent mapping is helping on this. Waiting for your reply. Thank for your nice tutorial. Regards Neelabh Singh

[@jaatharsh]

as mentioned when a Node goes does what happens to the data stored in it? & if during that node downtime data(ex-ABC) intended to be saved on the particular node(Ex-NodeX) is instead stored to the next Node(NodeA) in clock-wise direction what happens when another node takes dead node place? Now when ABC is searched it will check in NodeX but data for it was saved in NodeA.

[@gauravanand6937]

what is we want to retrieve the value from the unavailable node? how consistent hashing solves that issue?

[@TechDummiesNarendraL]

@gaurav for example consistent hashing is used in Cassandra/load balancer/caching(CDN) like system. Where data is expected to be lost because of hardware failure. Hence you have to have data replicated in case of databases. But in case of caching, LB or CDN you don't need to as data will be populated back from the source.

[@at_tap]

If data loss is accepted, why not in traditional hashing store the number with which you hash the data?

[@kgurumurthybhat]

@@at_tap With Regular hashing, you are affecting all memory location due to one server failure, whereas with Consistent hash only those reside in that servers are affected !

[@devashish887]

Thanks, man, Nicely explained. I got one question though If a system goes down or removed new value coming will be stored in the next range or cycle back to the first range, But what about if it comes back online which was failed or we want to reduce the load of first server(range) suppose lot of load coming to it. now the search will go to the new range, while the data was stored in a different range. how adding of new range works.

[@RaviNarayanaGayam]

Why %8 when 2 buckets are not available, why not %10 for consistent retrieval just like ring . I don’t understand the point of ring if it’s only about keeping hash table consistent when buckets are not available

[@nreed7718]

Great explanation. Thank you.

[@HakuSama1024]

Thanks for the video. Is there any way you could use a better mic?

[@bibekkakati]

When Computer 2 goes down, and at that time if an entry is made (say above 9,500 key) that will get stored in the starting key. But what after Computer 2 becme available later on?

[@adamhughes9938]

What happens when that location that failed comes back but some keys were written to the alternative locations. When lookups are performed, wouldn't they go back to the original location where they should have been? Does some reconciliation process occur when brining the failed locations back?

[@ricardohincapie1537]

Clever! Thanks!

[@kajalkukreja694]

Very good explanation👍👍

[@mukut5ul]

If hash number greater than last then all numbers will be stored in first location, first location linked list will grow...instead of doing all these why not use round robin and equally distribute to available slots and one more one to many mapping index to hash number just for retrieval.

[@azadalishah2966]

😩When u do such important and beautiful topic, environment should b silent but ur music is destroying that & losing concentration of viewers

[@hank91918]

legendary content! thank you sir!

[@Aliaksei_bus]

good example, thank you

[@TheRahul0110]

What is your name? My mom thinks you are from JANAM dance group...

[@sonkarshailendra]

Excellent. I was just thinking, how the value will be retrieved which is stored earlier (in 1011) for keys greater than 9900, when one new location will be added, let's say 10010 or 11000.

[@akshayagrawal2222]

@Narendra You are the best. I see many videos on consistent hashing but the way you explained is superb

[@chewoona7423]

To find a bucket in Consistent Hashing, linear search is needed. Is it O(1)?

[@navpreetkaur4902]

thanks so much, not sure if I can really thank enough with the kind of knowledge I am gaining from all your videos, please keep up a good work like this.

[@anshigupta8101]

why don't you post more videos?

[@satanickid1]

I was wondering how consistent hashing resolves hot partition problem ...

[@talesara74]

Nicely explained. Honeatly I saw many videos but none of them come even closer to this one. Thanks a lot

[@prafulsinghvit]

Woaah... This is awesome. First few minutes I was wondering why are we learning hashmap here..and then all of a sudden everything made sense...boom..!! ❤️ Super explanation. Thanks! 🙏

[@huseyinbarin1653]

Dude, I really enjoy listening to you. Excellent teaching skills.

[@dheten4462]

Remapping of already existing mapped data when some servers go down in really a tedius task.

[@ryan-bo2xi]

Every video in youtube has this one comment "this is the best video " ... now i have to watch every video O(N) . I hate this !

[@shivaprasad.v.g7526]

Its still not clear whats happens when a node which owns certain rows of the tables goes down and comes back up ?

[@大盗江南]

We love u we love u we love u!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

[@navderm]

12:28 : Consistent Hash

[@vipinkoul9129]

How to connect you on linkedIn?

[@prasanthmallepeddi5464]

clear and concise explanation on hashing and consistent hashing,kudos.

[@mudassarh4268]

your explanation is the easiest to understand. I really have huge respect for you and given a chance would definitely return the favor in whatever I can. Stay blessed and keep being awesome

[@shreyasrajanna7361]

Meats starts at 14:00

[@RahulPrajapati-jb3yh]

Thanks man for good explanation, I understood if one of the location mede unavailable, rehashing is easy i.e. move data of this location to next location(Drawback is next location will have double load now) and no need to rehash whole table but how does the rehashing happen when a new location added in the ring?

[@ritingoel9102]

great explanation :) and also the thing is the person who does know how Hashing works how the hash map works also able to understand because you covered from A to Z. Thanks for the Video :)

[@AndhraKitchenFoods]

Great introduction presentation on consistent hashing.

[@nguyenminh1402]

I like this guy lol.

[@amritraj6775]

How it is O(1). we have to search in keys to find a fit that's O(n)

[@linacao2137]

Thanks for explaining the concept but would it change the time of find from O(1) to O(log n)? Or you have build a second map between key and index?

[@tomtran6936]

I have the same question. Why do you think it is O(log n)? My thought, the fact that key index values are picked randomly and we need to loop through the keys (generally all) to compare and find the one that is larger than hashed value makes inserting or looking time become O(n).

[@cccc2740]

Its O(n/k)...k being linked list size

[@gagangupta1255]

Great tutorial

[@ishwaryachandramouleeswara229]

Very clear and solid explanation! Thanks a ton!

[@bahruzaghalarov3363]

It is so natural to hear dog bark when your key is "dog" in hashtable :D

[@anutripathi0304]

which rat makes Grr sound :)

[@AShahabov]

Bad sound :(

[@madhurgwa]

So, the scenario is, if we try to save any object with hash greater than 9900, say '9950' when 9900 is down then it (9950) will be saved at 1011 and whenever we try to fetch the object it will be available. But, if the location 9900 comes up and then we are trying to find the 9950 our logic will hit 9900 and return with nothing, so how this will be handled.

[@TechDummiesNarendraL]

Consistent hashing is mostly used in Caching or Load balancing or NOSQL. Is case of Caching yes, It will get nothing, and duplicate cache happens(since its cache its fine) In case of load balancers you never save anything. In case of NOSQL, using gossip messages all nodes will get to know the 9900 node came back and they sync back the data from 1011 node.

[@madhurgwa]

@@TechDummiesNarendraL thanks for the reply Narendra. I was mainly thinking about if we implement something similar for any database then we need to take care of sync and all like Cassandra or any other nosql db does. Btw It was very simple and clear explanation of consistent hashing.👍

[@santosh0516]

Very good explanation. Nicely done. Thanks man!

[@amitpadgaonkar8830]

Good explanation. Without BG Music would have been nicer.

[@asdfffadff]

very good explanation!! thank you

[@sivaprasad7278]

Because if I withdraw money from atm but still reflects to core banking db,internet bank db,atm db,mobile banking db,imps/neft/rtgs db/upi db/mobile banking db etc...,how this will happen in. Back ground if I do transaction in one db through one of payment method as described earlier

[@raj_kundalia]

Thank you for the explanation.

[@tomtran6936]

Hi, with Consistent hash ring, the fact that we need to loop through the key to find the one that is larger than hash value, makes this is not looking up with O(1) anymore but instead O(n), right?

[@TechDummiesNarendraL]

Do you always need to search? No. why can't you have a mapper hash map?

[@hitesharora751]

Good Work. Thanks for sharing your knowledge. Keep it up. (Y)

[@rajivjha123]

can you or somebody explain the black box here which is hash function ? How is the number generated or regenerated are same ?

[@TechDummiesNarendraL]

Pls refer dzone.com/articles/decoded-examples-of-how-hashing-algorithms-work

[@paulbagioli1885]

Excellent, thank you.

[@FirefoxGuy18]

Thanks for taking time to create this

[@muven2776]

What about the keys present in the 9900 ? when that location is down. are these keys distributed amoung available location ?

[@CHIRANJIBNANDY1]

I finally now understand it.