What is CONSISTENT HASHING and Where is it used?

Load Balancing is a key concept to system design. One of the popular ways to balance load in a system is to use the concept of consistent hashing. Consistent Hashing allows requests to be mapped into hash buckets while allowing the system to add and remove nodes flexibly so as to maintain a good load factor on each machine.
The standard way to hash objects is to map them to a search space, and then transfer the load to the mapped computer. A system using this policy is likely to suffer when new nodes are added or removed from it.
Consistent Hashing maps servers to the key space and assigns requests(mapped to relevant buckets, called load) to the next clockwise server. Servers can then store relevant request data in them while allowing the system flexibility and scalability.
Some terms you would here in system design interviews are Fault Tolerance, in which case a machine crashes. And Scalability, in which case machines need to be added to process more requests. These two principles are allowed by Consistent Hashing, and hence it is an important building block to a system design architect's toolbox.
Another term used often is request allocation. This means assigning a request to a server. Consistent hashing assigns requests to the servers in a way that the load is balanced are remains close to equal.
Server architecture is a subjective concept, and there are outliers for many cases. Don't think of Consistent Hashing as a silver bullet for fault tolerance and scalability, but a useful concept for request allocation.
Use it to solve software questions in interviews and real life. Best of luck!
Prerequisite: • What is LOAD BALANCING...
Recommended system design video course:
interviewready.io
00:00 Request Hashing
03:00 Request Mapping
06:02 Problems
07:01 Virtual Servers
09:40 Applications
10:18 Thank you!
Along with video lectures, this course has architecture diagrams, capacity planning, API contracts and evaluation tests. It's a complete package.
References:
www.hackerearth.com/practice/...
www.tomkleinpeter.com/2008/03/...
michaelnielsen.org/blog/consis...
• Consistent Hashing - G...
System Design:
highscalability.com/
• What is System Design?
Code:
github.com/coding-parrot/Syst...
#consistent-hashing #system-design #load-balancing

[@pranay020692]

Sitting in the hotel room, watching this 1 hour before my google interview in New York. Thanks Gaurav!

[@gkcs]

All the best!

[@gkcs]

@@pranay020692 wow, tough stuff. How'd you reckon it went?

[@pranay020692]

@@gkcs I believe, It went well. I have watched most of your system design videos, they were quite helpful. I am on the junior side 3 YOE so I think they went easy on me in Sys Design. Also, I was able to complete all coding questions in time. Google is always a long shot though. 🤞🤞

[@karthikmucheli7930]

@@pranay020692 hope you got the job

[@Leptoszom]

You got the job, Bajpai?

[@shreysom2060]

I used to see your "Competitive Programming" videos before getting into a company and now after getting learning things there ,I am watching your "System Design" it feels good to grow with this channel. Thank you so much 😊

[@andreimarculescu911]

the best solution is not to use K hash functions, but to generate K replica ids for each server id. Designing K hash functions while maintaining random uniformity and consistency is hard. Generating K replica ids is easy: xxx gives K replicas xxx + '1', xxx + '2', ..., xxx + 'K'. Then you take these replicas and generate K points on the ring with the same hash function and this is what is actually used in practice. Chord algorithm is just an example of this technique to add K replicas for each server id

[@gkcs]

That makes sense. K numbers assigned to each server would do the job :)

[@pradipacharjee4915]

Hi Andrei, can you just tell me how to choose idle replica count(k) ? for efficiently add or remove servers.

[@dudejaa]

The example that you took mentions xxx+1,+2,+3...+k. Correct me if I am wrong but if you assign k consecutive numbers to the same server the load wouldn't distribute (on adding or removing a server) uniformly. That could be one reason to look for different hash functions ?

[@charchitpatodi8677]

@@dudejaa Just a thought : he probably not means +1, +2... instead if xxx is id, M is ring capacity and k is number of servers then second position (after hash(xxx) )will be hash(xxx) + (M/k) OR hash(xxx+M/k).. And probably third position will be hash(xxx) + 2*(M/k) and so on till multiple of 'k'

[@rishabhmalhotra7058]

@Abhishek Dudeja xxx, xxx+1.. are ids for one server to take a hash on and then reach the respective points on the ring, not the points on the ring itself. And then the hash generated on xxx and on xxx+1.. would be completely different and random, and hence would plot k uniformly random points. @CHARCHIT PATODI I dont think that's the case cause if you think about it , if you add multiple servers each with k different points with that technique -> hash(xxx) + 2*(M/k)..till K, then you're not really randomizing and there would be no difference between adding 1 point or k points per server when it comes to choosing a server for a request. It would be like if you multiplied the ring length into k after choosing one point per server which would not get us what we want.

[@headoverbars8750]

What an outstanding video! No shortage of tutorials on how to code or write algorithms out there buy not enough on Systems design... This is truly outstanding... been writing software 10 years and fringely do I touch these concepts, heck work within them daily yet either forgot or never knew. Thanks so much!!

[@UlfAslak]

Notes to self: * The previous video gives the impression that there is a mapping from ranges of integers to server ids, and that consistent hashing is about to mapping request ids to integers in ranges resulting in more consistent routing of requests to same servers. -> I did realize that this would not work very well over time, as you would end up completely changing the ranges for higher-index servers with the addition of multiple servers. * In this video, requests ids map to an index in a ring with `M` indices. The "trick" then, is the map the server indices to indices in the ring using the same hash function that also hashes request ids. Now, to assign a server to a request, one simply looks clockwise for the nearest server. * To make it less likely that load will be unbalanced due to (what I would call) unlucky hashing, another idea is used: simply have multiple hash functions for the servers, such as to map them to multiple locations in the index ring! (clever). * @Andrei Marculescu points out that better than using multiple hash functions for server ids, it is easier to maintain multiple aliases for each server id ("...xxx gives K replicas xxx + '1', xxx + '2', ..., xxx + 'K'.") and thus map servers to multiple locations in the index ring.

[@Luk3Stein]

Thank you!! I was having so much doubts after watching, reading this made it more clear.

[@codingfork6708]

How can we determine the value of `M`? Is [0, M-1] the range of the output of the hash function?

[@UlfAslak]

@@codingfork6708 Correct. I think there are good heuristics for choosing M (and probably everyone uses the same standard values). Your hash function has to apply modulus M, otherwise you get an index out of range.

[@nxpy6684]

Thank you! This helped me a lot!

[@SP-db6sh]

This channel is like System-Design Wala , far far better than most paid courses, simple explanation

[@timurmukhtarov1319]

This was amazing! Havent seen other videos that talked about provisioning virtual servers/using multiple hash functions! Hooked!

[@jeffruan7701]

Knowledgeable and confident presenter!

[@akshatagrawal3300]

You are simply amazing gaurav, system design concepts couldn't be explained better than this!

[@AbhishekKumar-ub8co]

I loved the way with ease and simplicity you explained the problem using some pictorial diagram. Good work keep it up!!

[@gkcs]

Thank you 😋

[@Justinkol]

Thanks for making these videos! I was always unsure about load balancing, but this helped explain a lot of my unanswered questions :)

[@gkcs]

Glad it helped :)

[@johnleonardo]

your content is insanely good. seriously, the best! you were destined to teach others!

[@jrajesh11]

Simply brilliant and clear explanation . Keep doing such awesome work.

[@azeeztaiwo2802]

best explanation of consistent hashing i have seen so far.

[@user-oy4kf5wr8l]

u r amazing Gaurav! i watched ur video one year ago, i didnt understand then, now i watch again lol ...i understand most of it... thank u !

[@krishnasandeep4779]

Your Videos are very informative. Thanks for making it Gaurav. Your explanation is crisp and Clear

[@jananiravichandran8370]

Thanks for doing this! Your videos have really helped me understand things better =)

[@gkcs]

Thanks Janani!

[@SuiMizu]

You are a really good teacher, Gaurav! Please keep up your good work! :)

[@gkcs]

Thanks!

[@gautamtyagi8846]

many thanks Gaurav for making this concept so clearly explained.

[@raghuvamsi8740]

After this video, I downloaded the entire playlist!! More love More support!! Gratitude _/\_

[@bouzie8000]

That virtual server solution blew my mind I'm so sorry. Geniuses have really paved the way for us in computer science.

[@harshdusane8687]

Awesome explanation. This has truly elevated my understanding of Hashing and Load Balancing in general. Keep up the good work!!!! :)

[@asafmesika]

Brilliant explanation! I read the Wikipedia article on this and Cassandra docs and your video clicked everything together!

[@AbhishekChoudhary-tu7ig]

I am a 3rd sem student and I guess I should not be bothering about these things but your explanations are sooooo gooood that I always wanna watch them :D

[@arnabthakuria2243]

Learned a lot from the actual implementation in the attached git repo . Thanks

[@fiveyearclub6024]

Super helpful, thanks! I never got a CS degree and needed to learn more about sharding.

[@shishirkumar8335]

Great video. One comment is using consistent hashing seems good option for distributed search scenarios (like you pointed for distributed cache, DB search algo) but not for use cases of load balancing where nodes are added to server large numbers of request (like web servers, applications etc). Please comment your view

[@jatinderarora2261]

Thanks Gaurav. Excellent video.

[@rishabhagarwal9871]

A good video. I am really impressed. Thanks a lot.

[@consistentthoughts826]

When you said try to think of solution, first thing come to my mind is "change the hash function" Thank god i'm understanding it well and its first time I am studying

[@nafeezahid214]

Excellent video Master. Thanks a lot.

[@SayHelloMeetPatel]

Very nice explanation. Really liked the video. Thanks. Keep making it. 👍

[@gkcs]

Thank you!

[@gymbeestar]

This video is so helpful! Thanks!

[@VishalYadav-gk1kg]

Very Nice Explanation Sir, Thank you !

[@SOULOFBUU7]

Great explanation clear and concise

[@gkcs]

Thanks!

[@xiuwenzhong7375]

thx a lot, really helpful for people like me has no sense of system design.

[@keshavabhamidipaty3126]

Great video! I was wondering though, with this architecture, do you have to ensure that the hash functions don't ever collide though right? What would happen if an incoming request suddenly mapped to two servers that fell on the same point?

[@gkcs]

It's answered in the other comments 🙂

[@chandrakantasaini6438]

Explain in an easy and nice way.

[@i-tingchen439]

Very clear and helpful! Thank you.

[@gkcs]

Thanks!

[@xbeta84]

This is great stuff!

[@rockrock5838]

Really well explained man....

[@responsive_random]

Clearly explained. Thank you!

[@gkcs]

Thanks!

[@brothers_karamazovs]

Thank you! It was clear to understand.

[@prakharsaxena796]

Amazing videos man!!

[@hellaren]

Thank you! It was extremely helpful

[@mattwilson1845]

Awesome, thanks for making this video, really helped me understand. :D

[@gkcs]

Glad to hear that :D

[@krishnareddy3010]

Wow back to back !!!

[@vaibhav8257]

Thank you for Teaching this in such a nice manner.😊

[@rishabhmalhotra7058]

Awesome stuff man :)

[@satheeshprabhakaran5330]

Read the article about consistent hashing in wikipedia, this video has clearly articulated the core idea. Thank you!

[@OmarNg7X]

Great explanation. Thank you.

[@giobaldu]

Great video! Question: where do the requests sit in practice? Is there a node acting as a scheduler dispatching request by request, or the requests are mapped immediately to a server and kept internally in memory? Or both, so that the requests can be rescheduled if the server goes down? (I suppose this would require the scheduler to periodically ping each server, or set a timeout). What happens if the scheduler goes down? Second question: would it be possible to use work-stealing instead do reduce inbalance? Whenever a server is out of work, it would steal a request from the back of the queue of another random server. Or could this skew too much the execution order of the requests?

[@gkcs]

Thanks! The load balancer is a service which needs to tell the other services where a request is to be routed. It can either be queried per request (which is very expensive), or a snapshot of the current assignments can be cached by all services. If the snapshot changes at the load balancer, it can notify all interested clients. The service is distributed and backed by a 'reliable' database, so a single failure won't take the system down. Second answer: It sounds complicated and I have never seen it implemented on a large scale system.

[@NehaKumari-my7cv]

Hi Gaurav, Thanks for sharing such a nice concept.I have one doubt what happen if one server die suppose s1 for 2 hr and then again come back after that so in this case how request are handled.

[@crabjuice47]

God Bless you Gaurav. Love from Pakistan.

[@osamaa.h.altameemi5592]

fantastic explanation. Thx a ton.

[@rakeshvarma8091]

Gaurav, This video is wonderful Have small doubts Let's assume that request R1 is served by server S1. Now we have added a new server S2. Because of this let's assume the request R1 is now coming to S2. How the above scenario gets handled ? Is it like when a new server S2 is added , we have to move some portion of the data from the existing servers (S1) to the new server S2 based on its position on the ring? If it is the case, how can we do the distribution in real time ?

[@deepakrao1100]

boss code dal na ..!! studying for interviews with your videos, which btw the THE most helpful resource. Thanks for time you put into this !!!

[@Arif.Amirov]

how did your interview go?

[@gkcs]

A little late to arrive 🙈: github.com/coding-parrot/SystemDesignCourse/blob/master/service-orchestrator/src/main/java/algorithms/ConsistentHashing.java

[@manveersingh5822]

This was a pretty good video. Thanks Gaurav g!

[@nankitable]

With multiple hash being applied, can there be case of collisions, i.e. multiple servers ending up on the same bucket? If not , why? If yes, how is it handled?

[@yosihashamen1]

Great explanation!

[@sivas09]

'n' being the number of servers and 'm' being possible hash values, would spacing out the servers at a value of m/n be a working solution? For ex - with m as 256 and n as 4, first server could be at 64, second be at 128, third at 192 and 4 at 256 - along those lines Understood the possibility of skewed allocations and the need for replicating ids tho. Hooked to your amazing content! kudos

[@LeSaboteur3981]

easy and fast explanation👍👏

[@nehamadaan3328]

@Gaurav Sen , Great Video! Thanks a lot ! Question - You mentioned at the end, its used in many many places. Are there places where systems don't use Consistent Hashing at all ? Also, are there systems using some other techniques for consistent hashing? Is this the only approach or one of the approaches to implement consistent hashing?

[@gkcs]

Yes, definitely. Consistent hashing has it's own issues, and is usually only used for servers which need to maintain state (caches). Some databases also use consistent hashing. You can also try to reduce data migration by keeping master slaves for DB servers.

[@harshulbhaliya193]

Loved this video👾

[@Wise___Man]

great explanation, thanks!

[@subhabera5775]

Legendary tutorial, specially I really like where you try to prove your logicswith mathematical equations, same goes for one of the video called "finding loop in a linked list". Thanks Gaurav again :)

[@tanvirt16]

Gaurav, thanks so much for your videos! Very informative and easy so follow despite the complexity of the concepts. Just had a couple questions from this video! #1 So one of the original problems in the regular hashing solution was that when you add a new server, you'd have to destroy much of the local caches of the other servers because they become useless, which makes sense. So in this case, less changes occur, but how would you update the local caches to make sure you don't have to clear out the entire cache? Do you need some form of algorithm to determine what cache items should be evicted? #2 Also, how about the algorithm required to determine what the "closest" server is in the ring which will serve the request? Is there a simple mathematical solution for that, or is it somewhat complex? It does seem that the additional complexity in maintaining a consistent hashing system is worth the advantages, just want to understand a bit about how complex it actually is, or if it's simply just a genius solution to a problem.

[@soumyajitdas4433]

Try looking into Chord Algorithm (en.wikipedia.org/wiki/Chord_(peer-to-peer) for #2 Tl;dr; - every node in the hash ring maintains something called a finger table containing the information around it's predecessor node, successor node and also pointer to nodes (n+2, n+4, n+8 ... n+2^k). This way we can query any node and find the successor node to a particular hash value in O(log n) time.

[@soumyaranjanmohanty7839]

Great explanation Gaurav.

[@AbhishekKumar-ky3uc]

To be honest this video was more clear than the previos one in the playlist (what is load balancing), the pie chart concept in the previous one made me confused but this hopefully made it clear. Nice work!

[@gkcs]

Thanks!

[@eyalpery8470]

I learned a lot, you're awesome

[@RihanPereira]

@Gaurav sen, hashing(applying h2 function) all the servers again, will reshuffle data and request routing of all existing nodes to entirely new nodes.

[@SK-ur3hw]

Great video!! I thought that we can add a load factor or load limit like one server can have x requests. So once the load limit is reached, the incoming requests will point to next clockwise server. That way, no server will have too much load. But of course the virtual servers concept is good. Can you please add the code in the desc? Thanks. :)

[@gkcs]

Sounds interesting. There are variations on consistent hashing which allow this. Code link: github.com/coding-parrot/SystemDesignCourse/blob/master/service-orchestrator/src/main/java/algorithms/ConsistentHashing.java 😁

[@sreeram8942]

@@gkcs As you said in previous video about the User's cache data in a particular server , How does consistent hashing solve that issue ?

[@sasirekhamsvl9504]

Explained very well

[@AngadSingh97]

This was soooo cool!

[@pradyum88]

Would the User caching still exist in consistent hashing? Great videos BTW!

[@ashishmittal7048]

Thanks for the amazing video and describing the ring buffer based design for load balancing. I am wondering how this design will work efficiently when say for an example a subset of users are making too many requests? Because of consistent hashing the requests may land to the same machine , and certain machines might get more work assigned whereas all other machines are starving for the jobs.

[@phaneendran4208]

Hi Gaurav, Great series of videos. Thank you for sharing your experiences. I have one question on consistent hashing.. Which component of the distributed system is responsible for implementing this technique. 1) Is it load-balancer's job because it is a load distribution technique? 2) Or is it application's responsibility.? Curious to hear your thoughts. Cheers!

[@_romeopeter]

I don’t know if you still need answer to this but it’s the Load Balancer’s job because distributes the request and allocate them to the right servers.

[@atharvdineshbadgujar1724]

awesome explanation !!!!

[@smitmandavia5044]

Hi Gaurav, Thanks for the video! How about we divide request into M groups and assign each group to a given server. By say keeping a map? If a server goes down, we can remap its ids to other servers randomly. If new server is added, we can take one group from each server? Is having a mapping somewhere makes requests slow??

[@xawnia]

Thanks a lot Gaurav, this was very clear! I was wondering what would happen if there is a clash between different (or the same) hash functions h(x)=h1(y) which server will the load get assigned to?

[@vikassaran6430]

same question .....do you know the answer

[@debjyotibiswas3793]

You should write a book on system design, this is really great.

[@ashutoshmishra2328]

Hey gaurav, Thanks for this great video. i have one question, can we achieve the same results using a stick-table (which will keep user/IP and server mapping) in loadbalancer with some nondeterministic load balancing algorithm like RoundRobin or Least connection. if not then can you explain why.?

[@gkcs]

The main objective here to reduce the "rebalancing", the total number of cache loads and evictions. This is useful for load balancing on a cache cluster. The RoundRobin or Least connection algorithms are also useful in different scenarios.

[@jeyakumar4728]

Hi Gaurov, Wont removing / adding servers to the cluster affects the hash function modulo(%) Example: initially we have 4 servers hash(req for same id) % 4 -> s2 if we remove 1 server :- Hash(req for same id) % 3 -> s1 in this way, still the server 2 have stale cache data right?

[@JollyBeJolly]

Great teacher

[@ChandramouliMallampalli99]

very clever solution with multiple hashes

[@gkcs]

It's super cool 😋

[@perfectlyfantastic]

8:33 it was told that k value should be log(M),Is it just a suggestion or its the value we should definitely consider

[@roamwithashutosh]

🙂

[@SandeepVerma-yh9ec]

Thanks, Gaurav. Nice work. I have a small doubt. As you told to handle the skewed request by having virtual servers[by having multiple hashing functions for servers], how can we handle the collisions? I mean server S1 and S2 got the same output(say O1) from the hash function. Both will be serving the user request then

[@gkcs]

That's rare. If that doesn't work, we can change one of the hash functions and rebalance 😁

[@omarraghib905]

@@gkcs While hash collision might be rare, but the mod M of hashes may collide more frequently. How do we handle those?

[@zhikaicui3217]

Nice video Gaurav, and I have a quick question. What if there are collisions in the K has functions?

[@gkcs]

It's mentioned in the comments 🙂 The chances of two same values in the hash functions is less than that of an astroid blowing up Earth :)

[@DarshitSuratwala]

Really well explained mate. Had one question, is it the same approach used by AWS , GCP etc cloud providers?

[@gkcs]

Consistent hashing is used by many systems, so a lot of AWS users can ask for routing based on this. I think it's a customer preference.

[@goutkannan]

It is based on the load balancing logic u want to be used. One can always ask for a memcache to front any server setup

[@vishalkalaskar8567]

Hello Gaurav, when you said 'adding virtual servers' did you mean, adding differently generated hashes of the available servers so that their relative positions on hash ring is uniformly distributed giving us the flexibility of less skewed distribution of requests..? if yes, That implies if 1 physical server goes down, isn't it it's multiple hashed positions will also be off the ring giving more skewed results?

[@sauravdas7591]

Yes, it will affect the load, but consider this. If a server has, let's say, 4 points uniformly distributed across the hash ring, so when it crashes it will remove those 4 points, and this being uniformly distributed will increase the load other on other servers by 25%.

[@mallikarjunchalla226]

Using consistent hashing, we can overcome the rehashing problem i.e. rehashing the total number of keys which occurs in distributed hashing technique due to adding/removing servers.

[@ranajitjana4030]

wonderful video

[@nagarishyendarpanguluri6322]

Hi Gaurav, Great work! Quick question, How do we choose the number "m"?

[@srinivasasrikanthpodila4376]

Gaurav, The Addition/Deletion of Servers using the k-hash functions with the fixed ring size is a hard problem to solve to ensure the correctness. It could be simplified with generating the multiple ids of the same server.

[@gkcs]

That's right 👍

[@pavankongara792]

Amazing!

[@angadpathania]

Hey Gaurav... Great video... I'm a non techie and was trying to get familiar with these concepts... Essentially what ur saying is as your requests increase the load balancer should have those many server allocation hash functions so that there is a higher probability of equal distribution of load... Virtual servers here basically mean having those many server hash mapped points on the ring... Am I correct..? :)

[@ankur2443]

Thank you very much for explaining the concepts in such depth. I just have one question, what would happen if two different servers are hashed to same slot?

[@akhilraj9334]

Not an expert , but ideally the hash function you pick should have minimum chance of collision. Another scenario it might collide is when you are adding too many virtual servers into the ring, so should may be have a bigger ring or reduce the number of servers.

[@kollisashank1465]

Hi Gaurav, thanks a lot for creating these videos. It really helps us in understanding somethings which we use day to day. I have question, How do we decide on Search space M? Can we consider it as no of requests per second?

[@gkcs]

Thanks Kolli! The choice of M depends on the implementation, but it is usually a large number to have a better distribution of the hash function. Typically, values like 2^64 are used.

[@sridharbalabhadrapatruni1247]

@Gaurav, What would happen to the caching that we talked about in the initial part of the discussion? I understand caching is not going to happen because the requests are too randomized for caching to occur. Is this algorithm so efficient that even without caching it's more efficient than having an algorithm that relies on caching? Also, as a performance engineer, i dealt with load balancing a few times, but never got to see these kinds of algorithms for load balancing. we have implemented algorithms that distributed load across servers based on several parameters such as - geographic proximity of the request to the server, hardware utilization (Server with least CPU, RAM, utilization gets the request), Least connections(Server serving the least active connections gets the new request), etc. Do you have anything to say about those logics, and whether they are related to the hashing algorithm we have seen...

[@kaustubhparmar4274]

May be late, but I think the caching will happen because the hashes will always return the same output for same input, so if the servers do not change then caching is not affected. But if the number of server changes we need consistent hashing so as to minimise the remapping of the request to the server.