- Consistent Hashing
- ring space of \(0\) to \( 2^m - 1 \)
- take an id like ip, hash it and put it on the ring
- in our key value store, where to store keys?
- node 20 knows key-values for [16, 20] since the previous node is at 15
- correctness
- because it is a ring!
- always a node that hold they keys
- performance
- routing
- start at any node which will contain where the next node is
- worst case is \(O(n)\) - not great
- correctness with stabilization algorithm
- updates predecestor and successor
- a new node gets one node from DNS
- it calls another node, which calls another node, etc.
- the final node connects to the new node and updates its successor as the new node
- finger table
- a table that knows probabilisticly approximately halfway, quarter, eighth, etc.
- now instead of having to hope each node
- you can jump at most half way, then another quarter, etc.
- \(\text{key}+2^i ~ \text{mod} ~ \text{ringsize}\)
- fault tolerance if the node fails, successor and precessor has a copy!
- Dynamo used Chord's Consistent Hashing but using a SLA agreement