Ensure DHT clients remain discoverable

[jacobheun]

Design notes

• Problem: Servers will prune client connections frequently because they presumably rank low in the connection manager.

  • This: (a) thrashes the routing table, and (b) leads to connection flapping.
  • For solving (a), continue reading below.
  • For solving (b), we can either wait for QUIC/UDP, or implement libp2p connection resumption.

• Solution:

  • With dissociating the routing table from the connection state, clients will no longer remove disconnected servers from their routing table; instead they’ll test connectivity on refresh. This avoids routing table thrashing.
  • Splinter the table refresh routine into two separate routines:
    • Self-walk (calls GetCloserPeers(self), or FindPeer(self) -- which is special-cased anyway).
    • Table refresh.
  • If we are a DHT client: edit: we should do this regardless
    • Perform self-walks every 5 minutes; perform standard table refreshes every 10 minutes.
    • When we receive a local address update from the eventbus, trigger an immediate self-walk + connect, and reset the timer.
      • Specifically, we need to make sure our K closest peers have our latest address. An actual walk may not be necessary, we just need to be connected.
  • Queries must no longer terminate upon a hit, they continue until the end (as defined by Kademlia) in order to find the latest record (highest seq number). (part of implementing Kademlia correctly)
  • Signed peer routing records are a requirement.

Testing mechanics

1. Two cohorts: DHT clients and DHT servers.
   • DHT clients use the ListenAddrs host constructor option to listen on localhost only, yet they advertise dialable addresses by using a custom AddrFactory.
2. From all nodes, try to find all DHT clients, and record the time and hops it took.
3. Make a subcohort of DHT clients change their addresses (and signal so via Redis), and try to find all DHT clients again, recording whether we saw the new addresses (SUCCESS), or not (FAILURE).

Success Criteria

• DHT clients remain discoverable even when (#dht clients)/(#dht servers) >> connection manager limits.

[aarshkshah1992]

@jacobheun Some questions to improve my understanding of this issue.

Servers will prune client connections frequently because they presumably rank low in the connection manager.

Why do clients rank low in the connection manager ?

With dissociating the routing table from the connection state, clients will no longer remove disconnected servers from their routing table; instead they’ll test connectivity on refresh. This avoids routing table thrashing.

Assuming Connection/RT decoupling gets implemented, even the server will mark the client as "missing" and still keep it in it's RT & therefore test it's connectivity to the client on refresh assuming the client refresh hasn't fired yet ?

After every self-walk, CONNECT to our closest peers to push our latest peer record via IDENTIFY.

How would the peer record be used by the server ? Will the peer record pushed by a client C to server S be used when another peers asks S if it knows about C ?

If yes, why do we need this considering the fact that the client's re-connection to the server on a refresh adds it to the server's list of connected peers & therefore makes it discoverable ?

[aschmahmann]

@aarshkshah1992

Why do clients rank low in the connection manager ?

Because as far as the server nodes are concerned they're leeches and not high priority connections. If the server can keep a connection to another server or to a client it should keep a connection to the server since it's more useful.

Assuming Connection/RT decoupling gets implemented, even the server will mark the client as "missing" and still keep it in it's RT & therefore test it's connectivity to the client on refresh assuming the client refresh hasn't fired yet ?

This is combined with server nodes not adding nodes identified as "dht clients" to their routing tables.

Will the peer record pushed by a client C to server S be used when another peers asks S if it knows about C ?

Yes

If yes, why do we need this considering the fact that the client's re-connection to the server on a refresh adds it to the server's list of connected peers & therefore makes it discoverable ?

You are correct. IDENTIFY is the libp2p protocol that will automatically occur when we have a connection. The words "to push our latest peer record via IDENTIFY" are just explaining the useful result of connecting.

@jacobheun

After every self-walk, CONNECT to our closest peers to push our latest peer record via IDENTIFY.
...
Queries must no longer terminate upon a hit, they continue until the end (as defined by Kademlia) in order to find the latest record (highest seq number). (part of implementing Kademlia correctly)

Given the existence of the second sentence the first is now extraneous, right? As part of our Kademlia search for ourselves we should be connecting to all of our closest peers anyway (to see if they know anyone closer).

[aarshkshah1992]

@aschmahmann

Thanks for the reply.

This is combined with server nodes not adding nodes identified as "dht clients" to their routing tables.

Would you be able to link me to the issue where we've decided against adding clients to routing tables ?

[jacobheun]

Given the existence of the second sentence the first is now extraneous, right? As part of our Kademlia search for ourselves we should be connecting to all of our closest peers anyway (to see if they know anyone closer).

Yes it's extraneous, I've removed it from the description.

[aschmahmann]

@jacobheun is this feature meant to help users with publicly dialable addresses who have decided not to participate in the DHT (e.g. Raspberry Pi behind a router with port forwarding), users without publicly dialable addresses (e.g. standard laptop behind a NAT that may not have MDNS enabled), or both?

[jacobheun]

@jacobheun is this feature meant to help users with publicly dialable addresses who have decided not to participate in the DHT (e.g. Raspberry Pi behind a router with port forwarding), users without publicly dialable addresses (e.g. standard laptop behind a NAT that may not have MDNS enabled), or both?

I believe it should be both. Any DHT client should still be discoverable, otherwise we risk losing that data. If it's impossible for the client to be dialed (no intermediary or relay), it probably should avoid using the DHT as a client and instead use a delegate node.

[aschmahmann]

If it's impossible for the client to be dialed (no intermediary or relay), it probably should avoid using the DHT as a client and instead use a delegate node.

Are you sure? The current proposal of automatically switching from client to server mode based on whether a node is dialable or not doesn't abide by this strategy. Also, it doesn't seem unreasonable to me that a node that is behind a NAT might want to query the DHT (i.e. be a client) even though it's not able to be a server node.

Maybe I'm not sure what you mean by delegate nodes in this context. IIUC delegate nodes in a p2p network are for when resources (e.g. computing, file descriptors, etc.) are low or when certain platforms cannot fully support the protocol (e.g. they only support HTTP, but not arbitrary TCP or QUIC connections), not necessarily when there are connectivity issues.

Any DHT client should still be discoverable, otherwise we risk losing that data

Given the above, is having a publicly undialable node that is no longer discoverable via the DHT a huge loss? They can be discovered locally via MDNS for the nodes that can actually connect to them.

[jacobheun]

Given the above, is having a publicly undialable node that is no longer discoverable via the DHT a huge loss? They can be discovered locally via MDNS for the nodes that can actually connect to them.

This would mean we need to validate the addresses for a peer prior to adding them to the routing table, yes? What do you do when you don't understand an address that is publicly dialable by other nodes? If I can't dial them it doesn't mean nobody else can dial them.

[aschmahmann]

This would mean we need to validate the addresses for a peer prior to adding them to the routing table, yes?

Discoverability of addresses isn't strictly related to routing tables or even being directly connected to the peer. As an example, everyone could put their addresses to /p2p/myAddress and the publicly exposed FindPeer would just do a record query. We could even be a little clever and have a rule where /p2p/QmXYZ gets stored at the peer closest to Hash(QmXYZ) instead of Hash(/p2p/QmXYZ).

Validating that addresses are public should not be necessary (might need to do some thinking here to confirm). We could have three states we're worrying about:

1. Automatic mode switching + publicly dialable (or set to always be on server mode)
2. Client mode set + publicly dialable
3. Not publicly dialable

If we wanted we could enable the first two groups to advertise without allowing the third group to. We may not want to do this approach, but it's feasible.

What do you do when you don't understand an address that is publicly dialable by other nodes? If I can't dial them it doesn't mean nobody else can dial them.

While it's true that just because I can't dial them nobody else can it's also not clear that they should be advertising their address in the DHT if they're not accessible. It also seems reasonable to me to expect this behavior for provider records.

[aarshkshah1992]

@yusefnapora Please can you direct me to a PR where a peer pushes it's signed address on Identify ? Also, when/how are these records consumed by the receiver ?

Queries must no longer terminate upon a hit, they continue until the end (as defined by Kademlia) in order to find the latest record (highest seq number). (part of implementing Kademlia correctly)

@aschmahmann
Will this be done as part of the efficient query PR ? Specifically, will we guarantee that the queries (FindPeer & FindProvider) return the signed peer record with the highest seq number ?

[aschmahmann]

Will this be done as part of the efficient query PR

It seems likely that we'll merge the efficient query PR mostly as is and once the signed peer records PR is merged we'll go back and plug it in.

Specifically, will we guarantee that the queries (FindPeer & FindProvider) return the signed peer record with the highest seq number

@aarshkshah1992 per #784 yes for FindPeer. Unlike FindPeer, FindProvider has the ability to shortcut early since we can decide to return after we've found "enough" providers for some definition of enough (e.g. the code is now set to enough=k), we may want to tweak and/or disable the shortcutting behavior here too (by default) if we're concerned about attacks and/or particularly unfortunate caching. I'll add more about this to this issue linked above.

[aarshkshah1992]

Some design notes/concerns based on offline discussions with @yusefnapora and @aschmahmann:

• Would it fair to say that we are doing this so that DHT clients who are providers of some other service remain discoverable ? i.e. a peer has some dialable address -> it chooses not to be a DHT server for whatever reason(bandwidth, selfishness etc.) -> it still wants to be discovered for some other service it provides. In that case, do we really want to promote this selfish behaviour given that the DHT is a shared service ?
• There is NO hard dependency of this issue on the signed peer records work. What's important is that a client keeps it's K closest peers informed about it's addresses. Pushing signed address records is simply better for integrity purposes and nice to have.
• The FindPeer query will return a signed address record if it has one. However, we have no plans to store/return signed record for FindpProvider because of the excessive space consumption required for putting the signature info in each block. However:
  • What should a peer that responds to a FindPeer query do if it dosen't have a signed address
    record but has an unsigned one because the client hasn't opted in to signed records yet ?
  • Will the receiver of the FindPeer response treat both signed/unsigned records equally i.e. is the signed address record stuff really on a best effort basis ?
• @aschmahmann will merge Query logic closely match Kademlia paper go-libp2p-kad-dht#436 before the Identify signed records work lands. We will have to integrate signed records into DHT after the latter. @jacobheun We should create an issue to track this.

[aarshkshah1992]

Sir @Stebalien

Perform self-walks every 5 minutes; perform standard table refreshes every 10 minutes.

• While I see the wisdom in doing a self walk with a much higher frequency than we do now in context of this issue, why do we ALSO need to do a table refresh every 10 minutes compared to the one hour interval that we have now ?
• Why do DHT servers ALSO need to do self walks with a much higher frequency for this issue ?

When we receive a local address update from the eventbus, trigger an immediate self-walk + connect, and reset the timer.
Specifically, we need to make sure our K closest peers have our latest address. An actual walk may not be necessary, we just need to be connected.

• Identify will push the changed address to all peers we are connected to. So, what we specifically want to ensure as part of this additional mechanism is that the K closest peers ALSO have the latest address. What do we mean by "An actual walk may not be necessary, we just need to be connected" ?

[aschmahmann]

@aarshkshah1992

An actual walk may not be necessary, we just need to be connected

As you mentioned Identify will pushed the changed address to all peers we are connected to. I think the idea is that if we have "high confidence" that we're already connected to our K closest peers then we may not need to do anything at all because Identify will have already pushed the changes.

AFAIU this is a pretty small optimization since if we're already connected to the K closest peers then sending them a FindNode RPC (Kademlia paper terminology, using to disambiguate from the FindPeer API call) should be pretty cheap.

[yusefnapora]

@aarshkshah1992

Will the receiver of the FindPeer response treat both signed/unsigned records equally i.e. is the signed address record stuff really on a best effort basis ?

A while ago, @raulk and I were thinking that the DHT would have a "strict mode" flag which would cause it to ignore unsigned addresses and only accept addrs from signed peer records. "Lenient" peers would prefer peer records, but would also accept unsigned addrs. At the time there were two basic approaches we were thinking about:

1. Use one DHT protocol (one protocol ID), and have peers advertise their support for peer records and whether they're in strict mode as part of their RPC messages. Responders would send unsigned addrs if the requester is in lenient mode or doesn't support peer records at all.
2. Use two DHT protocols with separate IDs. Strict mode peers will only use the protocol that supports signed addrs, while lenient mode peers will support both.

Option 1 saves a multistream-select roundtrip, but it would need branching / special casing within the query logic of the DHT, which is already not the simplest code to follow.

Option 2 could be done a few different ways; we could have one codebase that responds to both protocol IDs and changes behavior depending on which was negotiated, or we could have two completely separate DHT instances, and put a facade in front to unify them into one ContentRouting provider (and PeerRouting, etc).

However, we recently started talking about moving the "strict mode" flag to the peerstore instead of having it be local to the DHT. That would allow the peerstore to accept signed peer records, but also accept unsigned addrs for the same peer afterwards. We haven't implemented that yet, but if we do it will have implications for the DHT, since if the peerstore is in "strict mode", the DHT effectively will be in strict mode also, and we probably want to communicate that to other peers so they know whether to send us unsigned addrs or not.

So, to sort of answer your question, we're going to need some kind of "hybrid" / lenient mode during the transition to exchanging peer records, but we haven't fully worked out how to implement it.

[yusefnapora]

It occurs to me that "strict mode" has a slightly different meaning for the peerstore vs the strict mode we were considering for the DHT.

Strict mode for the peerstore means that we will stop accepting unsigned addrs as long as we have any valid signed addrs for the peer, while lenient mode lets us always accept unsigned addrs.

Strict mode for the DHT means that we only send and accept signed peer records, and never send or accept unsigned addrs.

So the DHT is a bit "stricter" in the sense that a strict peerstore would still accept unsigned addrs up until it received a peer record for the peer, whereas a strict DHT would never accept unsigned addrs, even if we don't already know any addrs for the peer.

[Stebalien]

@aarshkshah1992

Thinking through this a bit, I don't think we need to increase the refresh rate to ensure that DHT clients can be found. I believe we started down that path before we finished thought through dissociating routing tables from connection state. However, I think we need to do it anyways.

Closest peers (self query): not being connected to one's closest nodes is a pretty big issue for network stability. If servers don't know their closest peers, they'll give incorrect information to clients trying to perform queries. Given network churn, I'd rather error on the side of doing this too often. An hour is a long time.

If our peers are acting correctly, they should connect to us when they join. However, something might go wrong and waiting an hour is too long.

Does this make sense? I haven't thought about this enough to be sure.

The rest of the buckets: In general, we want to keep our buckets full. Now that we keep a queue of peers to refill our buckets, this is less of an issue. However, I'm concerned about not being able to recover from a routing table issue for an hour. Example:

1. We have some kind of network blip and lose connectivity.
2. Several connection fail keep-alives (but not all).
3. We run through all the peers in the queues but can't reach anyone).
4. We regain network connectivity.

At this point, we'll have some peers in each bucket so nothing will trigger an instant refresh. However, our routing table will be mostly empty.

Note: Part of the solution here would be to not evict peers from the routing table until we've found a suitable replacement. However, a more frequent refresh rate would also help.

Identify will push the changed address to all peers we are connected to. So, what we specifically want to ensure as part of this additional mechanism is that the K closest peers ALSO have the latest address. What do we mean by "An actual walk may not be necessary, we just need to be connected" ?

Because DHT clients usually won't be connected to their K closest nodes because they're useless to their K closest nodes (so these nodes will disconnect from them). When a DHT client's addresses change, it doesn't really need to do a self-walk. Really, it just needs to get the top K peers from its routing table, calling Connect on all of them just in case.

[Stebalien]

Would it fair to say that we are doing this so that DHT clients who are providers of some other service remain discoverable ? i.e. a peer has some dialable address -> it chooses not to be a DHT server for whatever reason(bandwidth, selfishness etc.) -> it still wants to be discovered for some other service it provides. In that case, do we really want to promote this selfish behaviour given that the DHT is a shared service ?

Yes.

• Nodes behind NATs are often dialable, it's just not efficient/reliable to dial them. For now, we have to dial them through a relay. In the future, we'll be able to upgrade the relayed connection to a direct connection (but that still requires the relay).

• Some nodes (e.g., phones) can't afford to receive a bunch of inbound dials.

• Some nodes are just generally unreliable and frequently go offline. We really don't want to put DHT records to these nodes.

If we force these nodes to actually join the DHT to be findable, they'll end up degrading the performance of the DHT as a whole. That is, we're better off if unreliable and hard-to-dial nodes are selfish.

[aarshkshah1992]

@Stebalien

Thinking through this a bit, I don't think we need to increase the refresh rate to ensure that DHT clients can be found. I believe we started down that path before we finished thought through dissociating routing tables from connection state.

Because clients will anyways proactively connect to "missing" DHT servers in their Routing Table thus making them discoverable. Makes complete sense.

Closest peers (self query): not being connected to one's closest nodes is a pretty big issue for network stability. If servers don't know their closest peers, they'll give incorrect information to clients trying to perform queries. Given network churn, I'd rather error on the side of doing this too often. An hour is a long time.

If our peers are acting correctly, they should connect to us when they join. However, something might go wrong and waiting an hour is too long.

So when a peer joins the network, it connects to "bootstrap peers" -> immediately does a self walk thus discovering the closest peers -> a new closer peer will discover us as part of the same dance -> we keep repeating this dance hourly to account for network churn(a close peer we knew of might have died thus creating the possibility of discovering/adding another close peer/candidate) -> we are concerned the current 1 hour duration is too less compared to the intensity of our churn. Hmm.. we can lower the interval but need to be mindful that it comes with increased bandwidth usage.

At this point, we'll have some peers in each bucket so nothing will trigger an instant refresh. However, our routing table will be mostly empty.

We do have a RT size threshold to to trigger a refresh. Would increasing the threshold be a better solution than kicking off blanket refreshes more frequently ? We could even add a per bucket threshold to help buckets for higher CPLs stay full. Really, it's the buckets with higher Cpls we should be more concerned about as there will be far fewer peers we discover for them in the normal course of work than the ones with lower CPLs.

Because DHT clients usually won't be connected to their K closest nodes because they're useless to their K closest nodes (so these nodes will disconnect from them). When a DHT client's addresses change, it doesn't really need to do a self-walk. Really, it just needs to get the top K peers from its routing table, calling Connect on all of them just in case.

You mean K closest peers from the network and not from the RT, right ?

[Stebalien]

So when a peer joins the network, it connects to "bootstrap peers" -> immediately does a self walk thus discovering the closest peers -> a new closer peer will discover us as part of the same dance -> we keep repeating this dance hourly to account for network churn(a close peer we knew of might have died thus creating the possibility of discovering/adding another close peer/candidate) -> we are concerned the current 1 hour duration is too less compared to the intensity of our churn. Hmm.. we can lower the interval but need to be mindful that it comes with increased bandwidth usage.

The bandwidth usage should be pretty minimal given that we already have connections. We just need to send a message to our closest peers asking if they know of any closer peers. The main issue is that these peers will return signed address records...

Napkin calculation says: strictly less than 1MiB per interval. If we do the refresh once every 10 minutes, that's less than 2KiB/s on average.

Size of a multiaddr: ~8-21 bytes
Size of all the addresses (max): ~200 = 10 x 20
Double it: ~400
Size of the signature plus the key: 512 bytes
Size of each peer in each response: 1KiB
Size of each response (20 peers): 20KiB
Size of all K (20) responses: 400KiB
Total: 1MiB = 2 * 400KiB + fudge

However, we can probably get away with just querying our closest alpha nodes. We don't actually need to query all 20. I wonder if we should just manually do that. If we get closer peers, then we can seed a query with the results from the closest alpha.

Assuming an alpha of 3, that would yield:

Size of a multiaddr: ~8-21 bytes
Size of all the addresses (max): ~200 = 10 x 20
Double it: ~400
Size of the signature plus the key: 512 bytes
Size of each peer in each response: 1KiB
Size of each response (20 peers): 20KiB
Size of all K (3) responses: 60KiB
Total: 150KiB = 2 * 60KiB + fudge

~ 256 bytes/s

Would increasing the threshold be a better solution than kicking off blanket refreshes more frequently ?

Yes. However, we need to avoid repeatedly bootstrapping if we're in a small network.

We could even add a per bucket threshold to help buckets for higher CPLs stay full.

👍

You mean K closest peers from the network and not from the RT, right ?

From the RT. That is, DHT servers will frequently kill connections to clients
because these clients aren't in their routing table. However, these clients need
to ensure that at least a subset of the 20 closest DHT servers know their latest
addresses.

I'm saying that, when we go to do an identify push, we need to re-connect to our 20 closest nodes so they actually get that identify push.