Repository navigation
Supporting the "refresh" operation for NodeGraph buckets #345
Description
Activity
With the new index sublevel, we can iterate over a key stream on the index, with the
ltset to anything less than the current time minus 24 hours, or whatever the "TTL" is here, and then we can then ping these nodes and remove them if they are not live.Note that the
NodeConnectionManagerhas a TTL for eachNodeConnection, this refresh policy would not be like this, because doing so would cause alot of network activity. So instead triggering the refresh operation might be based on a single TTL across the entire node when it is inactive. It depends on the spec. Will assign this to @tegefaulkes to find out.useful reference
Old spec for reference
Specification
The Kademlia paper and Wikipedia page mention a notion of bucket "refreshing":
Refreshing means picking a random ID in the bucket’s range and performing a node search for that ID.
In both the paper and the Wikipedia spec, this is performed in 2 different places:
- Bootstrapping: after initially querying the seed node for the
kclosest nodes to itself, the joining node refreshes all k-buckets further away than the k-bucket the bootstrap (seed) node falls in (alternatively, the paper simply suggests to refresh all k-buckets further away from the closest node you currently have - i.e. find non-empty bucket with smallest index)- this is quite a straightforward place. We'd simply find our closest node (or use our bootstrap node), and iterate over every bucket, calling
getClosestGlobalNodeson your random node ID in the bucket's range
- this is quite a straightforward place. We'd simply find our closest node (or use our bootstrap node), and iterate over every bucket, calling
- Inactivity: if no node lookups have been performed in any given bucket's range for
tRefresh(an hour in basic Kademlia) from http://xlattice.sourceforge.net/components/protocol/kademlia/specs.html#refresh.- this is a little trickier. We'd need a means of continuously evaluating the "liveliness" of a bucket
- we already have a TTL for
NodeConnections that we could use. Additionally, we also have alastUpdatedfield in every node's entry in theNodeGraph. Both of these could be utilised for this purpose
It allows the
NodeGraphto be in a relatively "fresh" state, and would also slightly mitigate the impact of Kademlia poisoning (i.e. by removing "inactive"/invalid nodes from our ownNodeGraph, and replacing them with new nodes).Recall that we have 256 buckets on each node (because we have a 256 bit node ID). It seems like this might be quite a resource heavy process if we perform 256 refreshes, but this will need to be investigated.
Also note that we already have a
refreshBucketsoperation, but this is completely unrelated to this procedure. This is for when our node ID changes (on key renewal, etc) and we need to re-place the nodes in their correct bucket according to our new node ID. A better name for this function might bereoganiseBuckets.Additional context
- originally discussed when talking about adding a node to another node's
NodeGraphin Seed node not adding details of connecting node to itsNodeGraph#344 (comment)
Tasks
- Further investigate the benefits of the refresh operation
- Add
getClosestGlobalNodescalls to the bootstrapping process for a new node - Add means of evaluating the liveness of a bucket
- Use the liveness of a bucket to routinely make calls to
getClosestGlobalNodeson "stale" buckets
- Bootstrapping: after initially querying the seed node for the
- added 2 commits that reference this issue
on Apr 8, 2022 I'm implementing something like a queue for refreshing buckets. Refreshing a bucket can be pretty expensive and can potentially take a while but this all depends on the
findNodeimplementation. We may need to revisit howfindNodeis implemented and check that it's working efficiently. So the queue makes sure that we are only doing onerefreshBucketat a time sequentially.For tidiness we need to wait for the current
refreshBucketoperation to resolve before we can finish stopping theNodeGraphotherwise we have the potential for a dangling promise. But sincerefreshBucketcan possibly take quite a while to finish we may need a way to cancel a currently running one.Shouldn't refresh bucket be done in the background? As in part of our queuing system too?
With #297 we can do a proper cancellation.
That's the Idea i'm going for. I think at this rate we may just need to make a generic async queue class. I feel like we might need it again later.
There's some ideas in #329 which would involving using the DB which can provide a generic queue.
- added a commit that references this issue
on Apr 11, 2022 28 remaining items
- added 4 commits that reference this issue
on Jun 10, 2022 - added 4 commits that reference this issue
on Jun 14, 2022 - added 4 commits that reference this issue
on Jun 14, 2022 - added a parent issue
on Oct 23, 2025
Specification
Kademlia has this to say about refreshing buckets;
"Buckets will generally be kept constantly fresh, due to the traffic of requests travelling through nodes. To avoid pathological cases when no traffic exists, each node refreshes a bucket in whose range it has not performed a node lookup within an hour. Refreshing means picking a random ID in the bucket’s range and performing a node search for that ID. To join the network, a node u must have a contact to an already participating node w. u inserts w into the appropriate k-bucket. u then performs a node lookup for its own node ID. Finally, u refreshes all k-buckets further away than its closest neighbour. During the refreshes, u both populates its own k-buckets and inserts itself into other nodes’ k-buckets as necessary." kademlia spec
Given this we need to implement the following
NodeId.refreshBucketis pretty simple. It generates a randomNodeIdwithin the targeted bucket and preforms anodeFindoperation for that nodeId. We generate the desired 'distance' by generating 32 random bytes and then zeroing the bits above the target bucket bit and forcing 1 for the target bucket bit. The randomNodeIdis made by XOR-ing the distance with the baseNodeId.The activity timers for buckets were implemented the following way. We maintain a map of
bucketIndex -> deadlineto track when each bucket needs to be refreshed. We then maintain a single timer that triggers when the closest deadline has passed. When the timer is triggered we add any bucket that has passed it's deadline to the queue and reset the timer to the next closest deadline. When resetting timers for buckets that have been access we just update the map entry for that timer. if the updated bucket is the closest deadline then we update the timer again. When a bucket is is the queue, it's deadline is disabled by setting it to0and is not considered when updating the timer or adding to queue.The
refreshBucketqueue is implemented using a set of unique bucket indexes so a bucket can only be in the queue once. The queue is asynchronously digested doing a singlerefreshBucketat a time. When arefreshBucketoperation is completed for a bucket it's deadline is reinstated. if a bucket is updated while in the queue then it's deadline is reinstated and removed from the queue.Entering the network has been updated.
NodeConnectionManager.syncNodeGraphhas been updated such that when it completes the initial sync it will add any buckets above the closest node's bucket to therefreshBucketqueue.Additional context
NodeGraphin Seed node not adding details of connecting node to itsNodeGraph#344 (comment)Tasks
refreshBucketas per the above spec.