Pastry: Scalable Decentralized Object Location and Routing for Large Scale Peer to Peer Systems (2001)
November 7, 2023Pastry is a decentralized peer-to-peer object location and routing system based on nodes connected via the Internet. When each node in the Pastry network receives a message and a numeric key, it routes them to the node with a nodeId that is numerically close to the key. If a node is not the final destination of a message, it forwards the message to another node with a nodeId that is numerically closer to the key than the nodeId of the present node. The nodeId ranges from 0 to \(2^{128}-1\).
Each Pastry node maintains a routing table, a neighborhood set and a leaf set. A node’s routing table, \(R\), is a table with \lceil\log_{2^b}N \rceil\) rows and \(2^{b}-1\) columns, where \(N\) is the number of Pastry nodes in the network. \(b\) is a configuration parameter, and the typical value is 4. The \(2^b-1\) th entry at row \(n\) of the routing table contains the IP address of a node whose nodeId shares the present node’s nodeId in the first \(n\) digits, but whose \(n+1\) digit has one of the \(2^b-1\) possible values other than the \(n+1\) th digit in the present node’s id. The neighborhood set \(M\) contains the nodeIds and IP addresses of the \(|M|\) nodes that are closest to the local node according to scalar proximity metric like the number of IP routing hops. The leaf set \(L\) is the set of nodes with the \(|L|/2\) numerically closest larger nodeIds, and the \(|L|/2\) nodes with numerically closest smaller nodeIds, relative to the present node’s nodeId.
When a message with key \(D\) arrives at a node with nodeId \(A\), the node forwards the message and \(D\) to another node. If \(D\) falls within the range of nodeIds covered by leaf set, the message is forwarded directly to the destination node whose nodeId is closest to the key. The destination is in the leaf set. If the key is not covered by the leaf set, the present node forwards the message to a node that shares a common prefix with the key by at least one more digit. If the entry is empty or the associated node is not reachable, the message is forwarded to a node that shares a prefix with the key at least as long as the present node, and is numerically closer to the key than the present nodeId.
Pastry can handle the arrival and departure of nodes. Pastry assumes a new node knows initially about a nearby Pastry node \(A\), according to the proximity metric, that is already part of the system. When a new node with nodeId \(X\) arrives at a network, it asks \(A\) to route a special message with they equal to \(X\). Pastry routes the message to the existing node \(Z\) whose nodeId is numerically closest to \(X\). In response to the message, the nodes encountered on the path from \(A\) to \(Z\) send their state tables to \(X\), and \(X\) constructs its own state. Finally, \(X\) transmits a copy of its state to all the nodes in its neighborhood set, leaf set, and routing table.
A node is considered failed when its immediate neighbors in the nodeId space can no longer communicate with the node. To replace a failed node in the leaf set, its neighbor contacts the live node with the largest index on the side of the failed node, and asks that node for its leaf set. To update the entry in a routing table entry \((l, d)\), a node contacts the node referred to by another entry at \((l, i) (i\neq d)\), and asks for the node’s entry for \((l, d)\).