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!!!
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
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.
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
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.
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!!
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
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.
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! 🙏
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 :)
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.
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?
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.
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.)
Performance gonna take a hit, retrieval and put gonna take log(n) instead of n in traditional hash tables. But it is the best solution for consistent systems
Thank You! Great words and very nice vertical stack explanation! One of the humble and clearest videos so far on CH unlike some of the flamboyant ones on YT! Subscribed! \../
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 ?
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.
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.
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.
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.
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.
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?
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.
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.
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
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...... ???
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.
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?
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?
@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 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 !
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).
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.
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?
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.
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.
@@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.👍
Hi, Sir instead of consistent hashing we also can use range. example range (1, 1000) store in key 1 and (1001, 2000) store in key 2 and any disadvantage of consistent hashing?
@@TechDummiesNarendraL when a node is down then down node data distributed to another node which was not down or makes a copy of every node. So when any node down then this can be replaced down node.
One question on Consistent Hash Ring example, what you explained here. Suppose for (key,value) -> (Dog:Max) , the hash function gave 19234 and then at memory address 2022 we saved the following (key,value). Now if I am retrieving data using map.get(Dog), how does it internally finds out the 2022 address, as the hash function will again return 19234? Where is the mapping of 19234 and 2022 is done internally ?
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).
Nice explanation. I have a doubt on consistent hash ring. In order to find the key in the Hash table it sounds like we have to do the liner search starting from the start of the hash, compare it to decide on the location to insert the key-value pair. Is it making better in terms of search time if we chose to have the array solution here?
He didn't mention it explicitly but as you can see the random numbers are in ascending order. So, even if they are random, they are sorted. You can use this sorted nature to find a key efficiently using binary-like search (if you are a C++ programmer, std::lower_bound() does the same)
"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?
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.
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?
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
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 ?
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?
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?
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.”
How do we perform the correct bucket search in CH? I can think of some variation of binary search, but isn't it slower than direct lookup in a simple hashtable (O(logn) vs O(n))?
@@TechDummiesNarendraL what is hash range? Say I have 5 backets in a map, key value space of 5000 and 50 keys ranging from 0-100, 101-200 etc. On get I got key that hashes to 356 - how am I supposed to find that it's a 4th backet? Mark every possible value from range to that one backet, leading to a separate hashmap for keys of size 5000?
Overall, I really like your videos and explanations. However, I felt this particular video is lacking in some important details. 1. You suggest that the randomized keys be stored in a hash-table - however, obviously hash-tables don't provide very good range search capabilities, so searching through a hash-table to find the key that is greater than the hashed-key is not efficient. There are better ways to go about this. Conceptually, though, it did provide a decent abstraction to be able to explain the concepts, but I think that it is rather misleading. 2. I felt like you glossed over *why* consistent hashing is important & the situations in which you would want to use this methodology 3. The video doesn't touch at all on the important topic of having to rehash a bucket, and why / when you would need to do that, and how consistent hashing is beneficial in that case Thanks, though, for creating great content to break down large concepts.
To your 1st point, I think you are right, hash tables do not make sense here, though i am not fully sure but i believe BST would be the ideal data structure to store this type of data.
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?
Consistent Hashing begins at 12:35
Thanks!
big thanks! saved my 12 mins _/\_
Thanks!
Worth watching the whole video to fully understand why you need consistent hashing in the first place.
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!!!
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
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.
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
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.
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!!
Out of all other resources out there, your explanation on consistent hashing is the most concise. Thank you !!
Best explanation of consistent hashing I've seen. Thank you!
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
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.
I found the table to be a nice, concrete way to explain how this would work in practice.
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! 🙏
Nicely explained. Honeatly I saw many videos but none of them come even closer to this one. Thanks a lot
You have explained in a very clear and easy way without using so many typical words.
@Narendra You are the best. I see many videos on consistent hashing but the way you explained is superb
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 :)
I have seen many videos on consistent hashing but this is the best s far! Running trough an examples help retain concepts so well!!!
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.
Excellent stuff! Coincidentally, the dog started barking exactly when called for it at 15:31 😂
clear and concise explanation on hashing and consistent hashing,kudos.
Dude, I really enjoy listening to you. Excellent teaching skills.
best explanation on TH-cam, thanks man!
+1 on that!
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?
Very good explanation👍👍
12:28 : Consistent Hash
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.
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.)
very very good explanation, thanks narendra
Performance gonna take a hit, retrieval and put gonna take log(n) instead of n in traditional hash tables. But it is the best solution for consistent systems
Thank You! Great words and very nice vertical stack explanation!
One of the humble and clearest videos so far on CH unlike some of the flamboyant ones on YT!
Subscribed! \../
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 ?
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.
Great introduction presentation on consistent hashing.
how dose the rehasing happen when a new location added in the ring ?
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.
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.
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.
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.
you make things so easier to understand! thanks a lot !
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?
Good question
Very clear and solid explanation! Thanks a ton!
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.
Very good explanation. Nicely done. Thanks man!
Thanks for taking time to create this
Great explanation. Thank you.
Doesn't 1011 location will be overwhelmed with values when a key does not fit in 9900 bucket?
i too was thinking about it. did you find an answer?
Here you can find answer using virtual server th-cam.com/video/zaRkONvyGr8/w-d-xo.html
Clearest video on this topic that I've found. Thanks!
Is there a load balancer out there which uses this? I cannot see any of them using it. They use only round robin etc.
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.
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
Excellent, Easy to understand explanation.
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...... ???
What's the purpose of wearing a cap? Is this helps to explain hashing?
Really great explanation, as usual. Thanks
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.
Clear explanation.
Thanks Man!
Thank you for the explanation.
explained better than my college professor
good explanation!! Thank you
legendary content! thank you sir!
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?
thankyou soo much for this wonderful presentation
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?
what is we want to retrieve the value from the unavailable node? how consistent hashing solves that issue?
@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.
If data loss is accepted, why not in traditional hashing store the number with which you hash the data?
@@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 !
very good explanation!! thank you
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?
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).
Its O(n/k)...k being linked list size
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.
It is so natural to hear dog bark when your key is "dog" in hashtable :D
which rat makes Grr sound :)
It's so clear! Thanks for the efforts
good example, thank you
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?
Great tutorial
Clever! Thanks!
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.
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.
@@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.👍
Hi, Sir instead of consistent hashing we also can use range. example range (1, 1000) store in key 1 and (1001, 2000) store in key 2 and any disadvantage of consistent hashing?
under the hood that's what happens, but how do you handle when a node is down? you have to reallocate the range.
@@TechDummiesNarendraL when a node is down then down node data distributed to another node which was not down or makes a copy of every node. So when any node down then this can be replaced down node.
One question on Consistent Hash Ring example, what you explained here. Suppose for (key,value) -> (Dog:Max) , the hash function gave 19234 and then at memory address 2022 we saved the following (key,value). Now if I am retrieving data using map.get(Dog), how does it internally finds out the 2022 address, as the hash function will again return 19234? Where is the mapping of 19234 and 2022 is done internally ?
Yes the hash function will again return 19234 and the mapping is saved in hashtable
In consistent hashing, you are only saving values not keys. Then how would we know what value corresponds to what key?
Execellent explanation! Thank you for the links too.
Thanks for the video. Is there any way you could use a better mic?
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).
To find a bucket in Consistent Hashing, linear search is needed. Is it O(1)?
I finally now understand it.
Good Work. Thanks for sharing your knowledge. Keep it up. (Y)
Great Explanation
Its still not clear whats happens when a node which owns certain rows of the tables goes down and comes back up ?
Nice explanation. I have a doubt on consistent hash ring. In order to find the key in the Hash table it sounds like we have to do the liner search starting from the start of the hash, compare it to decide on the location to insert the key-value pair.
Is it making better in terms of search time if we chose to have the array solution here?
He didn't mention it explicitly but as you can see the random numbers are in ascending order. So, even if they are random, they are sorted. You can use this sorted nature to find a key efficiently using binary-like search (if you are a C++ programmer, std::lower_bound() does the same)
Well Explained. Thanks.
Much better & clear, Thank you :)
"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?
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.
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?
Hi, I also got confused in this part. Do you have an idea on this now
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
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 ?
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?
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?
Could you please do video about bank design
Dont you think in this case if last 2 goes down, all load will be on 1st 2 nodes.
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
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.”
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.
Excellent, thank you.
How do we perform the correct bucket search in CH? I can think of some variation of binary search, but isn't it slower than direct lookup in a simple hashtable (O(logn) vs O(n))?
May be you can have a hashtable with hashrange and server mapping? (update this with hearbeat to all active servers?)
@@TechDummiesNarendraL what is hash range? Say I have 5 backets in a map, key value space of 5000 and 50 keys ranging from 0-100, 101-200 etc. On get I got key that hashes to 356 - how am I supposed to find that it's a 4th backet? Mark every possible value from range to that one backet, leading to a separate hashmap for keys of size 5000?
@@thorthegreat10 @martin Correct bucket/slot will be found by performing a binary search on the array of bucket numbers {0, 100, 200, ..., 5000}
Overall, I really like your videos and explanations. However, I felt this particular video is lacking in some important details.
1. You suggest that the randomized keys be stored in a hash-table - however, obviously hash-tables don't provide very good range search capabilities, so searching through a hash-table to find the key that is greater than the hashed-key is not efficient. There are better ways to go about this. Conceptually, though, it did provide a decent abstraction to be able to explain the concepts, but I think that it is rather misleading.
2. I felt like you glossed over *why* consistent hashing is important & the situations in which you would want to use this methodology
3. The video doesn't touch at all on the important topic of having to rehash a bucket, and why / when you would need to do that, and how consistent hashing is beneficial in that case
Thanks, though, for creating great content to break down large concepts.
To your 1st point, I think you are right, hash tables do not make sense here, though i am not fully sure but i believe BST would be the ideal data structure to store this type of data.
Meats starts at 14:00
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?
Do you always need to search? No. why can't you have a mapper hash map?
Great job.