some ideas on kadelima kbucket size

[drHuangMHT]

The distance between local key and a remote key is determined by the difference in leading zeros of the XOR result. That means, for buckets that hold records farther and farther from local, their sizes need to get bigger and bigger, because for example a distance of 5 means a space for 2^4 different possible peers(records) and a distance of 50 means 2^49 different possible peers. And given that the records are stored in a vector instead of a tree, it will take longer for a more distant bucket to visit all records(to find a specific record). Simply increasing the bucket size won't solve the problem once and for all, as the network can get bigger and bigger to easily fill up the most distant bucket(imbalance between buckets).

[guillaumemichel]

It seems that you are describing a peerstore rather than a DHT routing table.

The promise of a DHT such as Kademlia is that each node keeps a state (routing table) of size O(log(n)) and the maximal route length to any peer in the network is O(log(n)), with n being the network size. It is the reason why DHTs scale so well.

Maintaining a larger state is expensive in terms of connections, because a node must periodically make sure that the peers in its buckets are responsive. So we don't want to increase the bucket size of farther buckets.

From a routing perspective, all buckets must have the same size, which is a system wide parameter (e.g 16 for discv5, 20 for the Amino DHT, etc.). Adapting the bucket size is important for networks that have different needs that the Amino DHT (current default size for rust-libp2p), not to make client side optimizations.

Ideally, a peerstore would complement the DHT routing table to store information about peers we were recently connected to. Peers in the peerstore require lower maintenance, and can be used easily by applications. The DHT routing table can never replace a peerstore in holding the discovered peers, once a bucket is full, it will discard any newly discovered peers matching this bucket.

[drHuangMHT]

It seems that you are describing a peerstore rather than a DHT routing table.

Yes. I'm specifically talking about the bucket size, which to me is a parameter of a peerstore.

So we don't want to increase the bucket size of farther buckets.

What I mean is that increasing bucket size in current implementation is not a permanent or even a temporary solution. 40 peers can easily fill up the farthest bucket(size 20) causing insertion to fail 50% of the time. To solve this we need a way to balance those buckets.

[guillaumemichel]

The bucket concept belongs to Kademlia's routing table, it is unrelated with the concept of peerstore.

In other libp2p implementations, the peerstore is a standalone component, fully independent from Kademlia (see go-libp2p).

What I mean is that increasing bucket size in current implementation is not a permanent or even a temporary solution.

I am not sure what problem you are referring to?

But I agree that the routing table (buckets) shouldn't act as a peerstore. IMO rust-libp2p needs a dedicated peerstore, or at least a mechanism that allows Kademlia to pass discovered peers to the applications and lets them manage peer storage.

[drHuangMHT]

The bucket concept belongs to Kademlia's routing table, it is unrelated with the concept of peerstore.

Ah yes. add_address puts the record explicitly inside kbuckets, which to my understanding was the same thing we do when we discover new peers, but now it seems not. I've read the spec and it says only peers in server mode should be put into buckets, which made me wonder how can we reach peers in client mode without them being in the buckets. Now everything makes sense.

I am not sure what problem you are referring to?

Simply increasing the size of buckets is not the solution to insertion failure. But if 50% failure rate at 40 peers is acceptable for routable servers, we shouldn't increase the bucket size at all, we can simply ignore them because the marginal benefit is very small, and we still can accept closer peers.

[drHuangMHT]

heck where did I get the impression of insertion failure being the main driver behind configurable bucket size? it seems wrong.