search

bmuller / kademlia

A DHT in Python using asyncio
http://kademlia.readthedocs.org
MIT License
830 stars 210 forks source link

KBucket.replacement_nodes is never pruned #79

Closed JohnDoee closed 4 years ago

JohnDoee commented 4 years ago

The list of replacement nodes is never pruned so it will grow to contain all nodes ever seen.

Should it be capped to some size?

bmuller commented 4 years ago

Nodes are only added to the replacement list if the bucket is full (see here), and they are moved out of the replacement list into the bucket as other nodes are being removed (see here). Additionally, nodes are pruned from the replacement list if they drop out of the network (see here).

JohnDoee commented 4 years ago

remove_node is called by remove_contact, remove_contact is called when there is no response from a node.

I can't see when a replacement node would be called unless it is no longer a replacement node.

bmuller commented 4 years ago

That's right, replacement nodes aren't used until they're moved out of the replacement list into the bucket. Section 4.1 of the Kademlia paper has more info on the replacement list and its purpose.

JohnDoee commented 4 years ago

It calls for a cache of replacement nodes but currently this is keeping a complete list of nodes.

I'm using this for bittorrent DHT and the result is I have over 10k replacement nodes for some buckets.

bmuller commented 4 years ago

@JohnDoee sorry, think I'm missing something here. These things should be true (and if either isn't, then there's a bug):

  1. the replacement list can only have nodes if the bucket is full
  2. the replacement list should never contain any nodes that are in the bucket

If these two things are true, then the replacement list cannot have "a complete list of nodes," since there are nodes in the bucket that are not the replacement list. If that's not the case and there's a bug, let me know how I can replicate the issue.

JohnDoee commented 4 years ago

The actual issue I have is that replacement_nodes is unbounded, i.e. it will contain an excessive amount of nodes. This leads to wasted memory.

The intended purpose of the replacement cache is to have a new node ready when a node currently in the bucket is deemed unresponsive.

The expectation of the replacement cache is

Since the paper does not specify a number for the cache size I can only assume it's left to the implementer to set a size.

Since this library does not limit anything that means there can be 10.000+ nodes in the replacement cache and the oldest one can be several months old. These things do not fit into a "replacement cache" to me.

Whenever you agree or not is your choice as it is an implementation choice. I capped it to ksize * 2 but saw others cap it at ksize.

bmuller commented 4 years ago

Got it, and good catch! I agree that it would be good to limit the replacement node list, especially if you're seeing nodes that are months old. Memory usage for these node is low though - what do you think of just capping it at the most recent ksize * 5?

Happy to accept a PR if you've got a fix already!