A lookup protocol: How to locate the node that stores a data item in a dynamic P2P system with frequent node arrivals and departures? In other words, given a key, it maps the key onto a node.
IPaddress Lookup(key) service, no data storage.
Distributed Hash Table (DHT)
Consistent Hashing: Key ID and Node ID are in the same ID space with SHA-1. A key is stored at is successor (node with next higher ID). For each node ...
Each node picks a random ID in a circular numeric space, and supervises a region of ID space immediately following its ID. The data shall be stored in its successor.
Lookup(my-id, key-id) n = my sucessor if my-id < n < key-id call Lookup(id) on node n // next hop else return my successor // done
Finger i points to successor of n+2^i.
Lookup(my-id, key) look in local finger table for highest node m s.t. my-id < n < key-id if n exists call Lookup(id) on node n // next hop else return my successor // done
How to join a new node? For example, join N36 (Node 36) between N25 and N40.
How to deal with failure (a node doesn't know correct successor)?
Lookup(my-id, key-id) look in local finger table and sucessor-list for highest node n s.t. my-id < n < key-id if n exists call Lookup(id) on node n // next hop if call failed remove n from finger table return Lookup(my-id, key-id) else return my sucessor // done
Chord uses consistent hashing, distributed hash tables, and novel finger tables to provide lookup services for P2P systems. Each node maintains only O(logN) other nodes. The arrivals and departures acquire only O(log^2 N) messages. The successor list can deal with failure effectively. Chord is simple, scalable, and efficient.