educative.io

Why in the example of consistency hashing, when adding node N5, the nodes N3 AND N4 don't get affected?

Courses
,
#1

Why in the example of consistency hashing, when adding node N5, the nodes N3 AND N4 don’t get affected?

My understanding after reading on Internet is, if we have the following nodes, and each node hold a range let’s say
Node A: [0-249]
Node B: [250-499]
Node C: [500-749]
Node D: [750-999]

and we add a new node, let’s say Node E and it has to go next to Node B (as a result of the hashing), the new range of the existing nodes after E will be like

Node A: [0-249]
Node B: [250-499]
Node E: [500-624]  <- New Node
Node C: [625-874]  <- Adjusted range due to Node E
Node D: [875-999]  <- Adjusted range due to Node E

Is my understanding correct? If so why in the example given here Ensure Scalability and Replication - Grokking Modern System Design Interview for Engineers & Managers for consistency Hashing, it is not mentioned in this way?

Also why in the example in that link, it is mentioned "N3 shares the keys from N2 to N5 with N5
". What N2 node has to do here???

#2

Hi @Rodrigo_Sandoval !!
In the context of consistent hashing, your understanding of how the ranges are adjusted when adding a new node is partially correct, but there are some important details to consider. Let’s address your questions and clarify the concepts:

  1. Adjusting Ranges When Adding a New Node:

    • When a new node (Node E) is added between existing nodes (Node B and Node C), the ranges of the existing nodes need to be adjusted to accommodate the new node.
    • In your example, the new range for Node E is [500-624], which is correct.
    • However, the adjusted ranges for Node C and Node D would be:
      • Node C: [625-874 - (range of Node E)]
      • Node D: [875-999 - (range of Node E)]
    • The adjusted ranges depend on the size of the range occupied by Node E and how it affects the neighboring nodes’ ranges.

  2. Consistent Hashing example is given in lesson:

  • In that example, the explanation does not explicitly mention the adjustment of ranges when adding Node 5 (N5).
  • However, in consistent hashing, when a new node is added, the existing nodes do get affected, and their ranges may need to be adjusted.
  • It’s important to note that consistent hashing is a distributed hashing technique that aims to minimize the reassignment of keys when adding or removing nodes.
  • In the example , it states that “N3 shares the keys from N2 to N5 with N5.” This statement implies that N3, as the node preceding N5, might have to redistribute some of its keys to N5 to maintain load balancing.
  • The example does not explicitly mention the adjustments made to the ranges of N3 and N4, but it is assumed that such adjustments are necessary for consistent hashing to distribute the load effectively.

Overall, when adding a new node in consistent hashing, the ranges of existing nodes may need to be adjusted to ensure that the keys are evenly distributed among the nodes and to maintain load balancing. The specifics of the range adjustments depend on the hashing algorithm and the implementation of consistent hashing used.
I hope it helps. Happy Learning :blush:

2 Likes
#3

Hi Javeria! Thanks for your excellent clarification.

Yes! my understanding was certainly wrong, and I ended up understanding the partial re-arrangement of the keys. What finally helped me to understand was start thinking in adding and removing a node. When adding a new node, keys that were handled by the next node to the one being added will be now shared with the new node, so the one that comes next will handled a new range of keys. And when removing the same node that had been added, if nothing has changed (meaning no other node has been added on the meantime), those keys that this node (the new node we had added before) will be back to the next one to it.

I used this explanation, which a read, and then came back re-read to educative.io to fully understand the process: https://www.acodersjourney.com/system-design-interview-consistent-hashing/

Thanks again!

1 Like