Search code examples
network-programmingp2pdistributed-system

Why in chord p2p system, the finger table don't store all the information about the other nodes?

I am learning chord system. But I have a question about its querying algorithm. Why the finger table in chord only store the information of successor(n+2^{i-1}) but not all the other nodes in the ring? Like in this picture,enter image description here

If I want to search key 7 at node 1. If node 1 stores all the address of nodes on the ring, since we obviously know the successor of 7 is 0, we can go directly to 0. Why should I go to node 6 first and use node 6 to route to 0. I am a little confused.

Solution

  • For scalability. Imagine that there are 10,000,000 nodes in the ring. It becomes very difficult to keep track of all of them (due to memory constraints and the communication effort required for signaling and handling node joins/leaves).

    Instead you could take advantage of the fact that node IDs are sorted in the ring. Then you could use them to avoid having to do a linear search over the entire ring. For example: In node 0 you only store info about 9 nodes (assuming IDs are from 0 to 10,000,000): 1,000,000, 2,000,000, 3,000,000, ... and 9,000,000. Then if you want to reach a random node, say 1,337,000 you have to search only in the segment 1,000,000 to 2,000,000. So by storing info about 9 nodes you reduced the amount of work by a factor of 10.

    But you can do even better than that. It's still a lot of work (337,000 steps) to get from 1,000,000 to 1,337,000 if nodes 1,000,000, 1,000,001, etc use shortcuts just like node 0, at intervals of 1,000,000 from each other. Wouldn't it be great if you had 9 shortcuts spaced at intervals of 1M from node 0, but then also 9 shorcuts spaced at intervals of 100k from node 1M to 2M? Then you would have to do the lookup in the segment 1,300,000 to 1,400,000.

    You can take this further by having each node maintain 9 shortcuts for nodes after it at intervals of 10k, and another 9 at intervals of 1k etc.

    So, in summary, the lookup would work like this:

    • We ask node 0 for info from node 1,337,000.
    • Node 0 does not know how to reach node 1,337,000 directly, but it knows how to reach 1,000,000 and 2,000,000. 1,000,000 is the closest one so it sends the query there.
    • Node 1,000,000 does not know how to reach node 1,337,000 directly, but it knows how to reach 1,100,000, 1,200,000, 1,300,000 etc. Node 1,300,000 is the closest one so it sends the query there.
    • Node 1,300,000 does not know how to reach node 1,337,000 directly, but it knows how to reach 1,310,000, 1,320,000, 1,330,000 etc. So it sends the query to 1,330,000.
    • Node 1,330,000 knows how to reach 1,337,000 because it is in its finger table (it knows how to reach 1,331,000, 1,332,000, 1,333,000 etc.)

    So you got the response in only 4 steps. Let's see how much storage you need in the finger tables.

    Any node with id n needs to store info about:

    • 9 nodes spaced apart by intervals of 1M, starting from n;
    • 9 nodes spaced apart by intervals of 100k, starting from n;
    • 9 nodes spaced apart by intervals of 10k, starting from n;
    • 9 nodes spaced apart by intervals of 1k, starting from n;
    • 9 nodes spaced apart by intervals of 100, starting from n;
    • 9 nodes spaced apart by intervals of 10, starting from n and we can stop here.

    So each node only needs to store info about 54 other nodes. In the worst case, you will need 6 + 9 = 15 lookups to reach a node. This is much better than the 10M-1 lookups you need without finger tables.

    Chord uses base 2 instead of base 10 for dividing the ring. Therefore the powers of 2 instead of 10 you see in the paper.

    I don't remember if this is exactly the way Chord works; but it's the same idea. A distributed binary search.