/ocaml-pastry

Pastry implementation in Ocaml

Primary LanguageOCamlBSD 3-Clause "New" or "Revised" LicenseBSD-3-Clause

About

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

Features

Key representation

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

Node

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

Routing table

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:

NodeIdPos0123
1002212102(1)2230120331203203
01(0)113012331223020313021022
221003120310132102(2)10323302
33102002301021130210222302(3)
34102303221023100010232121(3)
1510233001(1)10233232
06(0)10233120
27(2)

Operations:

  • Add a (nodeid, key)
  • Delete by key
  • Query a list of hosts given a key
  • Get a list of all the nodes

Neighborhood set

Unclear if this is needed, looks like later versions of pastry remove this

Leaf set

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

SmallerSmallerLargerLarger
10233033102330211023312010233122
10233001102330001023323010233232

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.

Router

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.

Adding a Node

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.

Removing a Node

A node is removed simply by finding it in the Router and deleting its entry.