feat: periodically fill the routing table with KADIds #215
Conversation
achingbrain
changed the title
In order to make queries in fewer hops it's useful to fill the routing table with imaginary peers that have IDs that are uniformly distributed over the sha2-256 value space. This means we've always got a peer ID on hand that's kind of xor-close to anything we might be looking up. We can then issue period DHT queries for any actual existant peers that are close to our imaginary peers to ensure we've got a good range of peers we know about, so making queries requires fewer hops to locate ones that are xor-close to the data we are interested in.
achingbrain
force-pushed
the
feat/ensure-routing-tables-have-contacts
branch
from
52056ff to
b5335ba
Compare
|
Waiting for latest libp2p release. |
BigLep
added
status/ready
|
@achingbrain : we removed "status/blocked" given llibp2p release has happened. |
|
@achingbrain (q from triage) we assume this is mostly done, and you want to rebase this? |
|
2021-06-14 note: this will get picked up by @achingbrain after Multiformats work. |
lidel
added
status/blocked
achingbrain
removed
the
status/blocked
|
|
||
| // Start random walk, it will not run if it's disabled | ||
| this.randomWalk.start() | ||
| return Promise.all([ |
There was a problem hiding this comment.
Can you please add a breaking change message to the commit so that we do not forget it on merge?
| @@ -54,6 +54,7 @@ | |||
| "heap": "~0.2.6", | |||
| "interface-datastore": "^5.1.1", | |||
| "it-first": "^1.0.4", | |||
| "it-length": "^1.0.3", | |||
| "it-length-prefixed": "^5.0.2", | |||
| "it-pipe": "^1.1.0", | |||
| "k-bucket": "^5.1.0", | |||
There was a problem hiding this comment.
we want to get rid of xor-distance below, right? 🎉
| // @ts-ignore | ||
| const KBuck = require('k-bucket') | ||
| const { xor: uint8ArrayXor } = require('uint8arrays/xor') | ||
| const GENERATED_PREFIXES = require('./generated-prefix-list.json') |
There was a problem hiding this comment.
we should have a browser empty list? I know we do not recommend using the DHT in the browser, but there are users who run it. It also will be part of the bundle, if we not have a browser alternative
There was a problem hiding this comment.
If they use it in the browser and we've removed random walk, it probably shouldn't be an empty list otherwise peer discovery will not work properly, or at least will be very slow.
We could always have a 'light' version that's like, 1/4 of the values or something?
There was a problem hiding this comment.
yeah, good point. Ok, I think we can start with a 1/4 of the list for now. These are the kind of things I wish JS testground had shipped.
We will likely need to revisit, but we will need to revisit all browser story either way. So, yes, let's do 1/4 for now.
| @@ -0,0 +1,85 @@ | |||
| package main | |||
There was a problem hiding this comment.
I wonder if we really want this in the tests, or a top level folder
There was a problem hiding this comment.
I think it's useful to show we're working with the same data
This reverts commit 10f0cc8.
In order to make queries in fewer hops it's useful to fill the routing table with imaginary peers that have IDs that are uniformly distributed over the sha2-256 value space. This means we've always got a peer ID on hand that's kind of xor-close to anything we might be looking up. We can then issue period DHT queries for any actual existant peers that are close to our imaginary peers to ensure we've got a good range of peers we know about, so making queries requires fewer hops to locate ones that are xor-close to the data we are interested in. BREAKING CHANGE: .start() is now async and random walk has been removed
In order to make queries in fewer hops it's useful to fill the routing
table with imaginary peers that have IDs that are uniformly distributed
over the sha2-256 value space. This means we've always got a peer
ID on hand that's kind of xor-close to anything we might be looking up.
We can then issue period DHT queries for any actual existant peers that
are close to our imaginary peers to ensure we've got a good range of
peers we know about, so making queries requires fewer hops to locate
ones that are xor-close to the data we are interested in.
Related to #183
BREAKING CHANGE:
.start()is now async and random walk has been removed