PASTRY is a DHT.
PASTRY is described here http://research.microsoft.com/en-us/um/people/antr/PAST/pastry.pdf
The main implementation can also be found here http://www.freepastry.org/
A Go implementation can be found https://github.com/secondbit/wendy
Keys are 128 bit numeric value.
Operations:
- Relational comparison
- Common prefix digits given a particular base (1 <= b <= 8 for now)
- Find the closest between two nodes
A node represents an abstract location.
A node is created and manipulated by the IO layer.
Nodes have a strict ordering between them.
Operations:
- distance - Give the distance to the node
- key - Key representation of the node
Represents a table of nodes that the algorithm can route traffic to. Each entry in the table corresponds to a number of nodes.
The routing table two dimensional where the columns are the numeration of the digits in the base the node id is represented in and the rows are the digits of the node id.
Given a base = 4 node id of 10233102, a hypothetical routing table would be:
| NodeId | Pos | 0 | 1 | 2 | 3 |
|---|---|---|---|---|---|
| 1 | 0 | 02212102 | (1) | 22301203 | 31203203 |
| 0 | 1 | (0) | 11301233 | 12230203 | 13021022 |
| 2 | 2 | 10031203 | 10132102 | (2) | 10323302 |
| 3 | 3 | 10200230 | 10211302 | 10222302 | (3) |
| 3 | 4 | 10230322 | 10231000 | 10232121 | (3) |
| 1 | 5 | 10233001 | (1) | 10233232 | |
| 0 | 6 | (0) | 10233120 | ||
| 2 | 7 | (2) |
Operations:
- Add a (nodeid, key)
- Delete by key
- Query a list of hosts given a key
- Get a list of all the nodes
Unclear if this is needed, looks like later versions of pastry remove this
The leaf set is an even number with value L. Half the leaf set is devoted to nodes whose value is smaller than the current nodeid and half devoted to larger.
Common values or 2^b or 2 x 2^b
NodeId 10233102
| Smaller | Smaller | Larger | Larger |
|---|---|---|---|
| 10233033 | 10233021 | 10233120 | 10233122 |
| 10233001 | 10233000 | 10233230 | 10233232 |
The table is just for visualizing it and the actual rows do not matter, just that half of it is composed of nodes smaller and half of nodes larger.
The Router contains a leaf set and a routing table. The Router only changes when a node is added or removed.
A Router starts out with no entries in it. Nodes are added to it and popular the leaf set first and spill over to the routing table.
When a node is added, it is first added to the leaf set. The node is either inserted just fine, or it cannot be added because the leaf set is full and the new node is not any closer to the current node, or it evicts a node in there.
In the case of not fitting in the leaf set or evicting a node, the node is possibly added to the routing table. The node is successfully added to the routing table if the node in its position is empty or if present node is closer than the existing node.
A node is removed simply by finding it in the Router and deleting its entry.