CSE 124 Lecture Notes - Lecture 24: Linked List
31 May 2018
School
Department
Course
Professor
Chord: Successor Pointers
- each node has a pointer to its successor
- each node may ALSO have a pointer to its “predecessor”
-Problem: O(N) lookup time! HORRIBLE
-We want logarithmic insert/delete/etc.
Chord Intuition
- Skip lists
- add log(N) rows
- get “as close as possible” on the TOP row, then traversing down all the way to the
bottom
- Key space: log(# of circles around the ring)
NodeState
Node * succ;
Map<hash, byte[]> data;
[ _,_,_,_,_ ] finger table (5 bits to represent 32 circles)
FT
| 20 | 1 |
| 21 | 2 |
| 22 | 3 |
| 23 | 4 |
| 24 | 5 |
2n ← represents how many jumps away from its current node
20 = 1 →
21 = 2 → →
22 = 4 → → → →
23 = 8 → → → → → → → →
24 = 16 → → → → → → → → → → → → → → → →
How to we build these tables?
Node 1: 1 + 2n
1
1 + 20 = 2
4 ← node that
holds 1 + 2n
2
3
4
3
5
9
4
9
9
5
17
18
Document Summary
Each node may also have a pointer to its predecessor . Each node has a pointer to its successor. Get as close as possible on the top row, then traversing down all the way to the bottom. Key space : log(# of circles around the ring) [ _,_,_,_,_ ] finger table (5 bits to represent 32 circles) 2 n represents how many jumps away from its current node. 2 4 = 16 . 4 node that holds 1 + 2 n. For a million nodes, it"s 20 hops. If each hopt takes 50 ms, lookups take 1 second. In practice, log(n) is better than o(n), but not great. Joining: linked list insert: copy keys 2636 from n40 to n36, notify messages maintain predecessors . Periodically look up nodes, and find which node contains the key that we want. If we find the node that we want, then we update in the ft with the new node that was added .
