The first data had surprised me a little as I didn’t expect such a difference between Vaults especially analyzing the community network data. (my two vault, with 167 and 143MB are, more or less, similar in size to the rest of Vaults).
Jean-Philippe’s clarifications resolve the doubts a little. In addition, there are two factors that, I believe, add more randomness to the network reducing the difference in size between Vaults. One is that the size of each XorData is different and not fixed as in the simulations. The other is that the growth of a real network, with section divisions and continuous relocations, create a much more dynamic network reducing the difference in size between Vaults.
I still think that, in a real network, the size of the Vaults of a section will be quite similar. My biggest fear is that a bad programmer’s design could create some very large data in the same Xor position, using versioned Mutable data, that could generate problems in certain Vaults.
Yes, using 1/3 in a binary world seems a strange decision.
The most important thing may be that the distance metric in this highly mulch-dimensional space is non-Euclidean. I am trying to form a better visual and intuitive image of this myself too, but this a first attempt to gain a better understanding. It’s from my wiki about the SAFE Network:
The concept of mathematical distance is used to recursively home-in on a destination address from the perspective of the originating node, closer and closer. Nodes in a neighborhood know best about nodes in it’s neighborhood.
Distance metrics must satisfy the conditions of a) zero distance between two nodes must mean the nodes are one and the same, b) distances between two nodes are the same no matter from which you start measuring (distance is same and always positive too), and c) the triangle distance inequality applies to any three nodes, which means that there always is a distance between one pair of these nodes that is equal or shorter than the sum of the distances between the remaining two node pairs.
Kademlia proposes the XOR distance metric as a “novel” metric that is very beneficial for a number of reasons. It meets the requirements above. However, it is non-Euclidean (not a straight bird’s flight kind of distance); Euclid’s 5th “parallel” postulate does not hold.
Interesting properties include the fact that other nodes as seen from a node all have unique distances. This results in the “homing-in” from any originating node to converge to a common path as the destination is approached.
The route is not a physical route, but only a journey, visiting and querying nodes each having only partial knowledge of other nodes in the overlay, in order to find the IP and port number of the destination node.
Here are my final thoughts about implementation of best fit algorithm:
a naive implementation based on xor distance would be terrible
current implementation based on linear distance is a good compromise because it is simple and the result is relatively efficient
a better implementation could be based on decomposition of sections in sub-sections, sub-sub-sections … in the xor space to balance them iteratively
I am not good at explaining things with words, so I will give a numerical example to contrast these 3 methods.
Suppose a section with prefix 0b0000. The range of valid addresses for the section is from 0 to 0x0FFF_FFFF…. Suppose the section has the following nodes:
If another node (N8) is relocated into the section, then the results of the 3 algorithms are the following:
Maximum xor distance is between N4 and N5 because this is the only transition with a change in the 5th bit, so the algorithm would return range [0x07FF_5555…, 0x07FF_AAAA…] which is very bad because it is too close to N4. Worse, if another node is added later it will be relocated between N8 and N5 again which means there will be an accumulation of nodes near this location.
Maximum linear distance is between N1 and N2 and the algorithm returns range [0x0165_5555…, 0x028A_AA…] (current algorithm in routing crate). This is acceptable but not the better location.
A better algorithm would return range [0x0C00_0000…, 0x0DFF_FFFF…] because it is the only 8th of section without node. The algorithm would do something like: divide the section in two and select the half with less nodes, then divide this half in 2 and select the quarter with less nodes… Repeat the process until we get a fraction without nodes and return the range corresponding to this fraction.
It doesn’t exist in routing crate. It is ironic that xor operator hasn’t been implemented for XorName in XOR space (precisely: implementation of std::ops::BitXor trait for XorName type)
I have been certainly unclear because this is exactly what I meant.
I’ve got a relocations parameter in the simulation that should allow us to measure this effect.
Thanks for your really clear explanation of this idea, I’ve implemented a quietesthalf strategy that goes only one bit deep, but will make an iterative version of it called emptysector. This sounds like a good strategy. Will be interesting to compare the number of key generations required as well to see how much more/less difficult each strategy is for the vault.
I thought of it as a binary vector, in a space of e.g. 256 dimensions, in each dimension having only two possible values, 0 or 1.
One dimension does not seem reasonable because I cannot imagine a 1D space that is non-Euclidean, and the Kademlia paper clearly says that XOR space is not.
(I am talking about the Kademlia XOR space. The Maidsafe implementation could be different - I have not looked at the code yet.)
The variation in megabytes stored per vault is slightly worse than the variation in chunks stored. This is roughly in line with intuition from ‘compounding’ randomness by adding random chunk size on top of (somewhat) random vault naming and random chunk names.
As previously established, variation in chunks stored is about 2x difference between the vault with most vs least chunks, and about 1.5x difference between the third quartile and first quartile.
Variation in megabytes is about 4x difference between the vault with most vs least MB, but still about 1.5x difference between the third quartile and first quartile.
It’s really good to see that most vaults will still be within 1.5x of each other both for chunks and megabytes stored.
I find it very difficult to pick much difference from looking at the charts, but the stats do indicate MB stored is more variable than chunks stored.
Slight tangent: based on the distribution of chunk sizes, 1M chunks with 8 copies ended up being about 2050 TB total stored by the section.
Note these two charts are from different seeds so the exact shapes are unrelated. It’s more the broad shape / jaggedness that’s of interest.
The degree of variation in all measures (name spacing both xordistance and linear, chunks per vault, megabytes per vault) are all significantly improved compared to other vault naming strategies.
In the table below, smaller numbers means less variation
This is shown graphically in the chart below, which clearly shows the difference in storage for emptysubsection has by far the least variation (smallest box and shortest whiskers).
The technique for relocating a vault into an empty subsection is described very well by @tfa above but I’m going to reword the algorithm here in case it helps for better understanding it.
start with two subsections (where P is the section prefix)
names P0000… to P0111…
names P1000… to P1111…
if either subsection has no vaults in it, relocate into that subsection.
if both subsections are occupied, check four subsections
names P0000… to P0011…
names P0100… to P0111…
names P1000… to P1011…
names P1100… to P1111…
if any of these subsections has no vaults in it, relocate there.
if all are occupied, check eight subsections.
continue increasing the number of subsections until we find one or more empty subsections.
if there are multiple empty subsections, generate random names until the name fits into any empty subsection.
How does the box-and-whisker chart look? Thanks for your feedback on this since creating a consistent and meaningful visual language is something I’d really like to achieve. I’m especially wanting to try and focus on dimensionless measures wherever possible, eg relative storage rather than absolute, so that it’s as easy as possible to compare between scenarios. Haha although my box and whisker chart could have been using relative numbers but still has the absolute mb stored… oh well !
Thanks for having implemented this test. When I have time I should improve my own tests in the other forum with this algorithm.
My idea is slightly different though. At each step the selected half is the least populated one. So the final fraction might not be the deepest most shallow one (with the longest shorter prefix).
I don’t think the result would be different in your simulation. But it could be different if you take into account nodes randomly leaving the section.
Looks nice, though a density map over the number of chunks stored (trivial in R) would be even better. Or maybe just sorting the bar chart by number of chunks instead of the vault id, which would be the simplest. Just a personal opinion though.
Nodes are punished when they do that so I don’t think it’s as big of a problem. At least, older and bigger vaults would not do it that often.
While a formal mathematical perspective may involve a 256-dim vector space with a specialized linear algebra to represent the exclusive-or as addition in modulo 2, you must then mix in the further algebraic shenanigans to create a 256x256 metric tensor that actually can arrive at a single scalar value for the xor-distance via dot product. Not trivial IMO, maybe not possible, and rather complicated for no good reason since the XOR operator itself provides a scalar distance measure in 1D. From a pure mathematical perspective this may lead to a rather elegant formalism, but it doesn’t lend itself well to intuition or visualization, and isn’t necessary for coding actual solutions.
To have a simple and intuitive understanding of xor-space, all you need to do is think of a dense binary tree, or quad-tree. MaidSafe has done a really nice job introducing the subject here.
The reason why your (@tfa’s?) method works so well is because it is essentially the optimal way to populate a sparse binary tree. This is the same thing that is done in multi-resolution schemes for CFD and FEA or other spatial partitioning algorithms when you want to refine tree-based mesh. You traverse the tree from a nearest common ancestor (aka section prefix) to the leaf node and then refine/bisect it if higher spatial resolution is required. In this scenario nodes are typically added 2, 4, or 8 at a time depending on if you are dealing with a binary-tree, quad-tree or oct-tree. Analogously, you add vaults to the xor-address space to increase the spatial resolution of the network itself. However, you’ve only been adding one at a time. For those looking for a visualization, the following provides a nice analogy to how network resolution increases as sections continuously split. For visualization purposes, the network address space can be seen as a single 256 bit binary tree, or by de-interlacing the bits into two 128 bit spaces, you can think of it as a quad-tree, shown below.
Earlier I was conflating xor-distance with depth to nearest common ancestor out of habitual thinking with regard to octree/quadtree meshes. IMO, depth to NCA is much more useful and intuitive than xor “subtraction” and also offers a unique scalar measure for “distance”.
Numerical example to illustrate this principle: suppose a section with prefix P and 7 nodes spread like the following in the section:
Prefix
Node count
P0000
1
P0001
1
P0010
1
P0011
1
P01
0
P100
1
P101
1
P110
1
P111
0
In this situation the second half (defined by P1) is less populated than the first one (P0) so it is better to select the range corresponding to P111 rather than P01 even though its prefix is longer.
Steps of the algorithm:
P0 has 4 nodes and P1 has 3 nodes, so P1 is selected
P10 has 2 nodes and P11 has 1 node, so P11 is selected
P110 has 1 node and P111 is empty, so P111 is selected and is the final range returned by the algorithm.
Yes, that is my understanding. Others may have a more correct view. When the section is split the chunk will go where the first N digits of its address matches the section prefix. N is the length of the section prefix.
Each data and each vault has an address within the XOR space. And it’s the proximity of these two addresses that mainly decides which vaults will store which data.
As in the split the XOR space is divided just in half, this data-vault proximity will still be preserved so we can expect that the need to move data will be limited.
As said by @digipl, only few chunks will be moved.
The split is triggered by a new vault joining a section. A chunk will be moved only if the new vault is nearer to the chunk than the one that was previously in the 8th position in the order of proximity to the chunk.
This is true every time a node is added to a section and not specifically when the new node triggers a split. The moves aren’t related to the split and the moved chunks would have been the same if the section hadn’t split.
When a section is about to split, each section half has more than 8 nodes, which means that the moves are limited to the section half containing the new node. If the new node triggers a section split then this section half becomes a new section and so the moves remain inside this new section.
!