Stream ordering of buckets.streamClosestPeers(targetId) does not follow the xor ordering (Spec Mismatch)

[SangameswaranRS]

Description

Stream ordering of buckets.streamClosestPeers(targetId) does not follow the xor ordering (Spec Mismatch)

Acceptance Criteria

• Stream ordering should exactly adhere to xor distance

Steps to Reproduce (Bug)

1. Call buckets.streamClosestPeers(targetId), after that sort the stream and compare it to your previous stream - Notice the discrepancy

Implementation notes

Vocab:

• Move left - Move from a distance d to d-1.
• Move right - Move from a distance d to d+1

Currently, we start off at the target xor distance, and then simultaneous move left and right and add them to our iterator. But that is wrong. We should Prioritize left buckets, then move right, if we don't get enough peers. Moving left guarantees that atleast cpl bits match

go-libp2p-kbucket follows the exact rationale described above. (Except for them left is right (logDistance vs common prefix length))
geth does and n^2 traversal - gets all the peers from all buckets and sorts them.

Preferred implementation:
if we worry about optimization: Node table is a centrally used data structure, so we have to design it as efficient as possible. We can add an additional parameter n, and stream and add to buckets in the above mentioned order. We stop scanning for extra buckets hasMoreBucketsToScan when we have grabbed and put more than n to a tree set ordered by xor distance comparator

if we don't worry about optimization: Stream all peers and add a .sorted() at the end of the stream. we may use a simple hashset instead of a treeset since we are already sorting at the end.

But as it is going to be 16*256, I'm not exactly sure on how approach 1 would help us. (Again since most of the calls would fall on Bucket 256 anyway)

[ajsutton]

The optimised version of this makes sense to me except that we then can't stream the results effectively. There may be use cases where we do know the number of results required, but for Teku we need to find some number of nodes meeting a specific criteria which may require scanning more nodes. That would then essentially devolve to the unoptimised case where we have to get every node to ensure we actually get enough once filtered.

It would be doable though if we passed in a Predicate to allow filtering the nodes (potentially out of order).

[SangameswaranRS]

Yes, Totally agree with you @ajsutton Actually I faced the same myself.

It totally makes sense as we need some ACTIVE k peers, we won't be knowing how much we should traverse in order to get k

Also, its a great insight to pass a Predicate, so that we'd know if we have streamed enough from the buckets.

Also I faced a weird case when streaming buckets the way I posited. For small values of N its working fine, (Tested over many iterations), but for larger values of N there is sometimes a node which is closer in bucket b+1 than b. (Since they share exactly cpl prefix bits), but there are some, cases like CPL bits....mismatch..mismatch vs CPL bits .... mismatch ..match , leading the xor distance to be smaller than bucket b+1.

Yeah, anyway we need to sort, the go-libp2p-kbucket guys also sort at the end to handle cases like this. So I think It makes sense only if we limit our traversing when we have enough peers.