Time has now come to talk a little more about sharding in Fleming. It’s an interesting topic as it impacts many aspects.
Now the notion of Disjoint Sections is not a new one for Fleming, the original RFC is available at rfcs/0037-disjoint-groups.md at master · maidsafe/rfcs · GitHub and describes the fundamental concept pretty well, even though some parts are slightly out of date. Here we will briefly go over the similarities to Kademlia DHT.
Partition and structure the network
To bring some sort of structure to the nodes connecting to the Network, the name space is partitioned into disjoint sections. By that we mean that each address in the Network belongs to exactly one section where each section is defined by its bit-prefix. An example would be:
S(00), S(01), S(10), S(11)
It is a valid non-overlapping partition of the Network address space where all nodes in a section share the first set of bits.
In each Disjoint Section, nodes use PARSEC to agree on the order of Network events, making them in a sense a fundamental building block and a level of abstraction where you can start to effectively reason on what’s happening in the Network. Furthermore, communication patterns are highly influenced by this structure.
Kademlia
To understand messaging with Disjoint Sections it’s useful to consider some other well-established communication patterns, in particular Kademlia which is commonly used in other peer-to-peer systems.
Nodes that know about other nodes by having them in their routing table are referred to as connected. In a sense Kademlia defines how to connect nodes so that you traverse an XOR space in O(log(n))
steps while needing to maintain only O(log(n))
connections. This means that traversing the entire space takes about as many steps as the tree’s height, which is much less than the total number of nodes. For instance, a Network with millions of nodes can be traversed in well under 30 steps. It can be seen as a compromise between all nodes being connected to all other nodes, and all nodes being connected along a long line. In the first case the routing table scales linearly with network size but any message can traverse the Network in a constant number of steps, while for the line the routing table is constant but messages must visit a linear number of nodes on their way to their destination.
Example: Nodes connected along a line, and each node connected to all others.
Example: Kademlia centred around node 000.
From the perspective of node 000 the network is divided into 3 buckets, i=0,1,2, depending on the length of the common prefix. In each bucket up to k
nodes are kept. In general:
- Each node is connected to at least
k
nodes withi
bits of common prefix. This means the routing table isO(k*log(n))
and knowledge of the network becomes “fuzzier” further away. - To reach a node far away jump to the node closest to the destination. Optionally use a
route
parameter to choose theroute = 0,1,...
closest node. This means it takes O(log(n)) hops to reach the destination.
Precisely which other nodes in a specific bucket a node is connected to is usually determined by past communication history, that is, the most recently encountered nodes are usually kept in the routing table.
To see how messages can be relayed let’s consider a concrete example. If node 000 is connected to 101 in bucket i=0, which in turn has the buckets given below
Figure: The three buckets of node 101.
Further assume that 101 is connected to 110, but not 111, in its bucket i=1. Then a message sent from 000 to 111 would take the path shown below.
Figure: Message relay across the network.
Disjoint Sections as a Kademlia DHT
For Disjoint Sections the structure bears many similarities to plain Kademlia, but adds further structure. As mentioned in the introduction, nodes are all grouped according to their prefix.
We require that for a node with section prefix pfx0
, it is connected to all nodes in all sections pfx
where pfx
differs in at most one bit from pfx0
. This means the Disjoint Sections satisfies the rules of Kademlia but further specifies exactly which nodes in the buckets to stay connected to.
Example: Disjoint Sections
In the example above the nodes in prefix 000 are connected to all nodes in prefixes 001, 010, and 100. These three sections are subsets of i=2,1,0 in the Kademlia example.
This for example affects how we can view message delivery. The arrows in the figure indicate how section 000 would send a message to 111. Using a route parameter we can always pass messages to the k-th closest (to the target) member in the next section and routes will not intersect in the absence of churn.
In Fleming, message delivery is a part that is undergoing heavy development and is likely to be further refined as it needs to be as reliable as possible, especially as sections constantly churn.