search

libp2p / go-libp2p-kad-dht

A Kademlia DHT implementation on go-libp2p
https://github.com/libp2p/specs/tree/master/kad-dht
MIT License
521 stars 223 forks source link

Add explore state machine to expand population of routing table #934

Closed iand closed 1 year ago

dennis-tra commented 1 year ago

Two general comments:

iand commented 1 year ago

Two general comments:

  • we can only have one explore query at a time, right?

Yes, by design. Do you think that is an issue?

  • the v1 logic actually explores from lowest CPL (bucket 0) to highest CPL (bucket 15). The description of the NewDynamicExploreSchedule and the code suggest that the logic in here does it the other way around. I think it's more reasonable to do it the way v1 does it because virtually half of the queries to the routing table will hit bucket 0 (assuming uniform keys we want to query) so it's important to have that bucket filled early.

We had some discussion on this in the design issue and @guillaumemichel seemed to be of the opinion that exploring closer buckets more frequently was useful (one comment here).

My reasoning is that since every peer discovered is a candidate for inclusion in the routing table, querying for nearby peers will almost certainly discover peers that populate further buckets first. Bucket 0 is likely to fill up with every explore we do.

Given the ExploreSchedule interface, it would just be a matter of adding a new implementation so we could also add it in a separate PR.

Yes, this would be quite simple to add.

dennis-tra commented 1 year ago

Cool, thanks for the clarification! Makes sense 👍

Yes, by design. Do you think that is an issue?

Nope, all good! Just wanted to verify my understanding of what's going on.