Improve node search over k-buckets (getClosestLocalNode)

[joshuakarp]

Specification

To optimise reading out the closes nodes to a target node we need to apply some improvements.

The getClosestNode function needs to take a nodeId and limit as parameters. The nodeId is the node we're calculating the distance relative to. The limit is how many nodes we wish to return. The limit defaults to the nodeBucketLimit as per the Kademlia spec.

We need to avoid reading out all of the buckets and iterating over empty buckets. This can be achieved by using a readStream over the nodeGraphBucketsDb level. This level contains sub levels for each bucket. Each sub level contains the nodeId:nodeInfo key:value pairs. Using the nodeGraphBucketsDb level we can iterate over each stored node in bucket order all at once. Note when setting the gt or lt on the stream we need to start from the desired bucket. In this case the starting point is the bucket 'above' the desired starting bucket. the key we want to start from takes the form of a Buffer with <prefix><higherBucketId><prefix>. Iterating less than this gives us the target bucket plus all lower buckets. Above this is all of the higher buckets.

When we run out of lower buckets we need to iterate over the higher buckets from where we started. If we run into limit while iterating over the nodes we need to get the whole of the last bucket we read. since nodes are out of order within a bucket we need whole buckets to ensure we obtain the closest nodes.

The resulting list is sorted by distance using nodesUtils.bucketSortByDistance and the list is truncated down to the provided limit.

As implemented

We iterate over the nodes directly across the buckets. the nodes are read out in the following order.

1. all nodes within the target bucket N
2. nodes in order of bucket 0 to bucket N-1
3. nodes in order of bucket N+1 to 255.

When we reach our specified limit we read the whole of the last bucket we've read and add that to the list. we then sort all of the nodes and truncate the list back down to the limit and return that.

Additional context

• discussion thread https://gitlab.com/MatrixAI/Engineering/Polykey/js-polykey/-/merge_requests/195#note_612883452 (text above copied from a previous comment of mine)
• Improve node search over k-buckets (getClosestLocalNode) #212 (comment)

Tasks

• 1. Update getClosestNodes implementation to use a readStream to iterate over each node sequentially across all of the buckets.
• 2. if we run out of 'closer' buckets we iterate over the higher buckets.
• 3. buckets are not ordered via distance, so if we read any node from a bucket into the list we need to get the whole bucket.
• 4. the returned list needs to be sorted by distance and truncated down to the limit.

[CMCDragonkai]

With the NodeGraph using sublevels to represent buckets, you can now use createReadStream to stream to the "left" from the designated bucket and NodeId to be looked up. You just need to use reverse: true and lt with a synthesised seek key based on the bucket key and NodeId. See nodes/utils for the utilities to create that seek key. Use limit: k to limit the number of nodes to find.

If you cannot fill out the k buffer, then just start streaming to the right.

Then you can return it.

[CMCDragonkai]

Reposting from #326 (comment)

I've done some further prototyping on the NodeIds that are in each bucket. And this has an important impact on how we do the getClosestNodes function, and any visualisation of the NodeGraph.

The first thing to realise is that NodeId is just a sequence of bytes, they can be 1 byte or 32 bytes or whatever. They are set to 32 bytes, but it's easier to explain everything by thinking of them with only 1 byte.

And because they are just a sequence of bytes, there is a numeric equivalence of NodeId. 0 - 255 can be represented as 1 byte, and 0 - 65535 can be represented with 2 bytes.

The Buffer.compare function compares pair-wise bytes using the numeric representation. So [255, 0] is less than [255, 1].

Buffer.compare(Buffer.from([255, 0]), Buffer.from([255, 1])) === -1

Note that this means our NodeId are in big-endian format.

The buckets sublevel stores keys in lexicographic order, this means we are in ascending order of bucket indexes by default, and then in each bucket, the node IDs are also in lexicographic order. This is achieved by lexi.pack of the bucket index, and storing raw NodeId buffers as the final keys.

I believe lexicographic order of the raw NodeId buffers are the same as the numeric order of the bigints that the NodeIds would represent (remember that 32 bytes can represent a VERY large number, so that's why we use bigint).

A 1-byte NodeId like 00000001 would be just 1 in numeric order and would look like [1]. I have to check though, by adding an additional test to js-db that proves that lexicographic order of binary keys is the same order as produced by Buffer.compare which just compares the numeric values in each byte.

Supposing lexicographic order of NodeId is equal to numeric order of NodeId, the next question is whether this order can be used to produce NodeIds that are ordered by Kadmelia XOR distance. So I tried it out because it looked like it did in the wiki image:

However upon testing with more node IDs, this did not end up being the case.

The end result is that for any given NodeId, the closest NodeId is a directly adjacent NodeId with an XOR distance of 1, this corresponds to a bit-wise output of XOR of just 1, whether that is 001 or 000000...00001.

    101
xor 100
    001

This can be applied to any NodeId using XOR, because the inverse of XOR is XOR.

So:

5^1 == 4
76^1 == 77

Afterwards, all other NodeId are grouped into buckets on either side of the numeric line.

Then each bucket has NodeId, and the numeric/lexicographic order is not the same as if it were sorted by distance.

Here's an example to prove this:

    // Create 100 NodeIds
    // They all have a size of 1 byte
    // Numerically they represent 0 - 99
    const nodeIds: Array<NodeId> = Array.from(
      {length: 100},
      (_, i) => IdInternal.create<NodeId>(utils.bigInt2Bytes(BigInt(i), 1))
    );

    const results: Array<any> = [];

    for (let i = 0; i < nodeIds.length; i++) {
      let bucketIndex;
      let distance;
      try {
        // 77 is the chosen NodeId
        bucketIndex = nodesUtils.bucketIndex(nodeIds[77], nodeIds[i]);
        distance = nodesUtils.nodeDistance(nodeIds[77], nodeIds[i]);
      } catch (e) {
        // Ignore the chosen NodeId
      }
      results.push(
        [
          i,
          nodeIds[i],
          bucketIndex,
          distance
        ]
      );
    }

    console.log(results);

The output is:

    [
      [ 0, IdInternal(1) [Uint8Array] [ 0 ], 6, 77n ],
      [ 1, IdInternal(1) [Uint8Array] [ 1 ], 6, 76n ],
      [ 2, IdInternal(1) [Uint8Array] [ 2 ], 6, 79n ],
      [ 3, IdInternal(1) [Uint8Array] [ 3 ], 6, 78n ],
      [ 4, IdInternal(1) [Uint8Array] [ 4 ], 6, 73n ],
      [ 5, IdInternal(1) [Uint8Array] [ 5 ], 6, 72n ],
      [ 6, IdInternal(1) [Uint8Array] [ 6 ], 6, 75n ],
      [ 7, IdInternal(1) [Uint8Array] [ 7 ], 6, 74n ],
      [ 8, IdInternal(1) [Uint8Array] [ 8 ], 6, 69n ],
      [ 9, IdInternal(1) [Uint8Array] [ 9 ], 6, 68n ],
      [ 10, IdInternal(1) [Uint8Array] [ 10 ], 6, 71n ],
      [ 11, IdInternal(1) [Uint8Array] [ 11 ], 6, 70n ],
      [ 12, IdInternal(1) [Uint8Array] [ 12 ], 6, 65n ],
      [ 13, IdInternal(1) [Uint8Array] [ 13 ], 6, 64n ],
      [ 14, IdInternal(1) [Uint8Array] [ 14 ], 6, 67n ],
      [ 15, IdInternal(1) [Uint8Array] [ 15 ], 6, 66n ],
      [ 16, IdInternal(1) [Uint8Array] [ 16 ], 6, 93n ],
      [ 17, IdInternal(1) [Uint8Array] [ 17 ], 6, 92n ],
      [ 18, IdInternal(1) [Uint8Array] [ 18 ], 6, 95n ],
      [ 19, IdInternal(1) [Uint8Array] [ 19 ], 6, 94n ],
      [ 20, IdInternal(1) [Uint8Array] [ 20 ], 6, 89n ],
      [ 21, IdInternal(1) [Uint8Array] [ 21 ], 6, 88n ],
      [ 22, IdInternal(1) [Uint8Array] [ 22 ], 6, 91n ],
      [ 23, IdInternal(1) [Uint8Array] [ 23 ], 6, 90n ],
      [ 24, IdInternal(1) [Uint8Array] [ 24 ], 6, 85n ],
      [ 25, IdInternal(1) [Uint8Array] [ 25 ], 6, 84n ],
      [ 26, IdInternal(1) [Uint8Array] [ 26 ], 6, 87n ],
      [ 27, IdInternal(1) [Uint8Array] [ 27 ], 6, 86n ],
      [ 28, IdInternal(1) [Uint8Array] [ 28 ], 6, 81n ],
      [ 29, IdInternal(1) [Uint8Array] [ 29 ], 6, 80n ],
      [ 30, IdInternal(1) [Uint8Array] [ 30 ], 6, 83n ],
      [ 31, IdInternal(1) [Uint8Array] [ 31 ], 6, 82n ],
      [ 32, IdInternal(1) [Uint8Array] [ 32 ], 6, 109n ],
      [ 33, IdInternal(1) [Uint8Array] [ 33 ], 6, 108n ],
      [ 34, IdInternal(1) [Uint8Array] [ 34 ], 6, 111n ],
      [ 35, IdInternal(1) [Uint8Array] [ 35 ], 6, 110n ],
      [ 36, IdInternal(1) [Uint8Array] [ 36 ], 6, 105n ],
      [ 37, IdInternal(1) [Uint8Array] [ 37 ], 6, 104n ],
      [ 38, IdInternal(1) [Uint8Array] [ 38 ], 6, 107n ],
      [ 39, IdInternal(1) [Uint8Array] [ 39 ], 6, 106n ],
      [ 40, IdInternal(1) [Uint8Array] [ 40 ], 6, 101n ],
      [ 41, IdInternal(1) [Uint8Array] [ 41 ], 6, 100n ],
      [ 42, IdInternal(1) [Uint8Array] [ 42 ], 6, 103n ],
      [ 43, IdInternal(1) [Uint8Array] [ 43 ], 6, 102n ],
      [ 44, IdInternal(1) [Uint8Array] [ 44 ], 6, 97n ],
      [ 45, IdInternal(1) [Uint8Array] [ 45 ], 6, 96n ],
      [ 46, IdInternal(1) [Uint8Array] [ 46 ], 6, 99n ],
      [ 47, IdInternal(1) [Uint8Array] [ 47 ], 6, 98n ],
      [ 48, IdInternal(1) [Uint8Array] [ 48 ], 6, 125n ],
      [ 49, IdInternal(1) [Uint8Array] [ 49 ], 6, 124n ],
      [ 50, IdInternal(1) [Uint8Array] [ 50 ], 6, 127n ],
      [ 51, IdInternal(1) [Uint8Array] [ 51 ], 6, 126n ],
      [ 52, IdInternal(1) [Uint8Array] [ 52 ], 6, 121n ],
      [ 53, IdInternal(1) [Uint8Array] [ 53 ], 6, 120n ],
      [ 54, IdInternal(1) [Uint8Array] [ 54 ], 6, 123n ],
      [ 55, IdInternal(1) [Uint8Array] [ 55 ], 6, 122n ],
      [ 56, IdInternal(1) [Uint8Array] [ 56 ], 6, 117n ],
      [ 57, IdInternal(1) [Uint8Array] [ 57 ], 6, 116n ],
      [ 58, IdInternal(1) [Uint8Array] [ 58 ], 6, 119n ],
      [ 59, IdInternal(1) [Uint8Array] [ 59 ], 6, 118n ],
      [ 60, IdInternal(1) [Uint8Array] [ 60 ], 6, 113n ],
      [ 61, IdInternal(1) [Uint8Array] [ 61 ], 6, 112n ],
      [ 62, IdInternal(1) [Uint8Array] [ 62 ], 6, 115n ],
      [ 63, IdInternal(1) [Uint8Array] [ 63 ], 6, 114n ],
      [ 64, IdInternal(1) [Uint8Array] [ 64 ], 3, 13n ],
      [ 65, IdInternal(1) [Uint8Array] [ 65 ], 3, 12n ],
      [ 66, IdInternal(1) [Uint8Array] [ 66 ], 3, 15n ],
      [ 67, IdInternal(1) [Uint8Array] [ 67 ], 3, 14n ],
      [ 68, IdInternal(1) [Uint8Array] [ 68 ], 3, 9n ],
      [ 69, IdInternal(1) [Uint8Array] [ 69 ], 3, 8n ],
      [ 70, IdInternal(1) [Uint8Array] [ 70 ], 3, 11n ],
      [ 71, IdInternal(1) [Uint8Array] [ 71 ], 3, 10n ],
      [ 72, IdInternal(1) [Uint8Array] [ 72 ], 2, 5n ],
      [ 73, IdInternal(1) [Uint8Array] [ 73 ], 2, 4n ],
      [ 74, IdInternal(1) [Uint8Array] [ 74 ], 2, 7n ],
      [ 75, IdInternal(1) [Uint8Array] [ 75 ], 2, 6n ],
      [ 76, IdInternal(1) [Uint8Array] [ 76 ], 0, 1n ],
      [ 77, IdInternal(1) [Uint8Array] [ 77 ], undefined, undefined ],
      [ 78, IdInternal(1) [Uint8Array] [ 78 ], 1, 3n ],
      [ 79, IdInternal(1) [Uint8Array] [ 79 ], 1, 2n ],
      [ 80, IdInternal(1) [Uint8Array] [ 80 ], 4, 29n ],
      [ 81, IdInternal(1) [Uint8Array] [ 81 ], 4, 28n ],
      [ 82, IdInternal(1) [Uint8Array] [ 82 ], 4, 31n ],
      [ 83, IdInternal(1) [Uint8Array] [ 83 ], 4, 30n ],
      [ 84, IdInternal(1) [Uint8Array] [ 84 ], 4, 25n ],
      [ 85, IdInternal(1) [Uint8Array] [ 85 ], 4, 24n ],
      [ 86, IdInternal(1) [Uint8Array] [ 86 ], 4, 27n ],
      [ 87, IdInternal(1) [Uint8Array] [ 87 ], 4, 26n ],
      [ 88, IdInternal(1) [Uint8Array] [ 88 ], 4, 21n ],
      [ 89, IdInternal(1) [Uint8Array] [ 89 ], 4, 20n ],
      [ 90, IdInternal(1) [Uint8Array] [ 90 ], 4, 23n ],
      [ 91, IdInternal(1) [Uint8Array] [ 91 ], 4, 22n ],
      [ 92, IdInternal(1) [Uint8Array] [ 92 ], 4, 17n ],
      [ 93, IdInternal(1) [Uint8Array] [ 93 ], 4, 16n ],
      [ 94, IdInternal(1) [Uint8Array] [ 94 ], 4, 19n ],
      [ 95, IdInternal(1) [Uint8Array] [ 95 ], 4, 18n ],
      [ 96, IdInternal(1) [Uint8Array] [ 96 ], 5, 45n ],
      [ 97, IdInternal(1) [Uint8Array] [ 97 ], 5, 44n ],
      [ 98, IdInternal(1) [Uint8Array] [ 98 ], 5, 47n ],
      [ 99, IdInternal(1) [Uint8Array] [ 99 ], 5, 46n ]
    ]

As you can see, bucket 2 & 3 are left-of NodeId 77, while bucket 4 & 5 is right-of NodeId 77 and finally bucket 6 is on the far-left.

Additionally, the numeric/lexicographic order for each NodeId does not match an ordered distance.

However it is true that all possible NodeIds in particular bucket would be contiguous numerically.

This means when getting the closest node IDs, we still need to sort each bucket's item by the distance function. This is bounded by the bucket size since buckets are limited to 20 nodes by default.

I'm writing 2 methods that do similar things:

• getBuckets - this streams out buckets in order of bucket index and then by lastUpdated
• getNodes - this streams out nodes in order of bucket index

I originally thought that I could have getNodes return in order of distance. But the DB would only provide me either order by lastUpdated similar to getBuckets, or lexicographic ordering of NodeId, which you can see isn't particularly useful.

The 2 sort-orders within buckets that are useful are ultimately:

1. In order of distance
2. In order of lastUpdated

So this means I'll need to bring back the sortByDistance utility and potentially make it available to the getBuckets and getNodes methods.

@tegefaulkes - you'll need to beware of this to solve this issue.

[CMCDragonkai]

Insertion sort would be nice to use here, but I fear it won't be efficient because arrays will end up being resized. So once you map all the values to distance, you then just sort them all.

[CMCDragonkai]

This test was added, so it proves that lexicographic order is equal to Buffer.compare order as well as numeric order of big-endian buffer bytes. MatrixAI/js-db@7f7d75e

[tegefaulkes]

A NodeId's distance is fully reversible calculation given we know the node it's relative to. This means if we wanted distance ordering we can use the distance as the key in the db instead of the NodeId. That's just something to consider.

[CMCDragonkai]

A NodeId's distance is fully reversible calculation given we know the node it's relative to. This means if we wanted distance ordering we can use the distance as the key in the db instead of the NodeId. That's just something to consider.

We cannot do that as I explained in #158. The distances are different because sometimes we want to know the closest nodes to a node that isn't the own node. So there's no way to just index by 1 distance metric.

You have to use the way I'm doing it in getBuckets to create a new method called getClosestNodes.

[CMCDragonkai]

I suggest a signature like:

getClosestNodes(nodeId: NodeId, limit: number): Array<[NodeId, NodeData]>

This is similar to getNodes except that that because it is a limit, it can be a finite return type compared to the async genreator.

[CMCDragonkai]

Use this comment: #158 (comment)

[CMCDragonkai]

With nodesUtils.bucketSortByDistance.