Chunk distribution within sections

Features
43

Here are my final thoughts about implementation of best fit algorithm:

  1. a naive implementation based on xor distance would be terrible

  2. current implementation based on linear distance is a good compromise because it is simple and the result is relatively efficient

  3. 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:

N1 = 0x0040_0000
N2 = 0x03B0_0000
N3 = 0x0500_0000
N4 = 0x07FF_0000
N5 = 0x0800_0000
N6 = 0x0B40_0000
N7 = 0x0E40_0000

If another node (N8) is relocated into the section, then the results of the 3 algorithms are the following:

  1. 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.

  2. 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.

  3. 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.

4 Likes