![](https://i.imgur.com/ucdnYJA.png)
- Consistent Hashing
- ring space of \(0\) to \( 2^m - 1 \)
![](https://i.imgur.com/Dsr0ol4.png)
- 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
![](https://i.imgur.com/TQrk6Ur.png)
- correctness
- because it is a ring!
- always a node that hold they keys
- performance
![](https://i.imgur.com/SupTs0B.png)
- routing
- start at any node which will contain where the next node is
- worst case is \(O(n)\) - not great
![](https://i.imgur.com/mKJQ0qr.png)
![](https://i.imgur.com/pVoWNf8.png)
- correctness with stabilization algorithm
- updates predecestor and successor
![](https://i.imgur.com/OxuNoVT.png)
- 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
![](https://i.imgur.com/XVJdUhH.png)
- 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}\)
![](https://i.imgur.com/ViiUAeW.png)
- fault tolerance if the node fails, successor and precessor has a copy!
![](https://i.imgur.com/TYEYbP1.png)
- Dynamo used Chord's Consistent Hashing but using a SLA agreement