p2p: Batch send NOTFOUND messages

sipa commented at 10:28 pm on November 10, 2022: member

Message types INV, GETDATA, and NOTFOUND are similar in that they all have a payload consisting of a vector of CInv data structure. But while sent INV and GETDATA messages are constructed by aggregating them, and then sending them out in batch during SendMessages, NOTFOUND is sent immediately.

This means that separate GETDATAs (which do seem sent by some network clients) always result in separate NOTFOUNDs, a potential waste of outbound bandwidth. Improve upon this by introducing Peer state m_notfounds_to_send, aggregating them there during GETDATA processing, and sending the result out when it either overflows or during SendMessages.

Batch send NOTFOUND messages ad393c2d13

sipa force-pushed on Nov 11, 2022

in src/net_processing.cpp:5840 in ad393c2d13

5837+
5838+        // Message: notfound
5839+        if (!peer->m_notfounds_to_send.empty()) {
5840+            m_connman.PushMessage(pto, msgMaker.Make(NetMsgType::NOTFOUND, peer->m_notfounds_to_send));
5841+            peer->m_notfounds_to_send.clear();
5842+        }

maflcko commented at 10:01 am on November 11, 2022:

Can you explain why it is safe to change the order of responses? From a first impression, I think it is possible that a peer sends us a getdata [1], then a ping, then they would receive the pong first, and then the notfound, no? Previously they should be in order.

If this is safe to change, it might be good to explain. Also, then it would be better to move this out of the cs_main scope here, because the lock is not needed.

If it is not safe to change, I guess you can just move the send to the process function?

[1] This should happen intermittently whenever there is fPauseSend backpressure, or you can force it deterministically by sending an unknown getdata type.

ajtowns commented at 7:43 am on November 16, 2022:

We already have out of order notfounds: if you request getdata [a,b,c] and b is known but a and c aren’t; we’ll send back tx b; notfound [a,c]. Having a pong interspersed as well doesn’t seem like it makes a big difference?

amitiuttarwar commented at 5:20 am on November 17, 2022:

agree that this code can be moved out of cs_main
I spent some time, and can’t think of any specific circumstances that would cause this change in ordering to be problematic in normal node operations (which is not to say its necessarily fine)
however, one question that came to mind is if this could negatively impact timing in the tests because of the expectations from the sync_with_ping function. however, with AJ’s patch, any test covering NOTFOUND behavior would require some time delay. so this shouldn’t be an issue.

maflcko renamed this:
~~Batch send NOTFOUND messages~~
p2p: Batch send NOTFOUND messages
on Nov 11, 2022

DrahtBot added the label P2P on Nov 11, 2022

DrahtBot commented at 11:59 pm on November 11, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Reviews

See the guideline for information on the review process.

Type	Reviewers
Concept ACK	vasild, amitiuttarwar

If your review is incorrectly listed, please react with 👎 to this comment and the bot will ignore it on the next update.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#26140 (refactor: Move CNodeState members guarded by g_msgproc_mutex to Peer by dergoegge)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

vasild commented at 8:49 am on November 14, 2022: contributor

Concept ACK

ajtowns commented at 7:46 am on November 16, 2022: contributor

Because ProcessMessages() only deals with one message per invocation (perhaps along with part of a previous message that wasn’t fully dealt with) and we always call SendMessages() after ProcessMessages(), I don’t think this work as-is. However artificially delaying the sending of notfound messages does allow combining; here’s a patch that does that as well as a hacked up demo: https://github.com/ajtowns/bitcoin/commit/48dcba08ae725c9ef8d67325469bb30976196acb

amitiuttarwar commented at 5:28 am on November 17, 2022: contributor

concept ACK. however, agree that the current patch doesn’t always achieve the intended batching across separate GETDATAs. adding the timer from AJ’s patch makes sense to me & increases message batching.

I also like the test from that branch. It currently just prints output & doesn’t assert anything. This was sufficient to help me work through the behavior in the different use cases, but ofc can’t be merged in that state. I started working on cleaning it up & codifying the assertions, and will share tomorrow.

amitiuttarwar commented at 5:14 am on November 18, 2022: contributor

I updated the tests in this branch. an overview of the commits:

ad393c2d130b593b671b66e6a84c244664c3fd4c with the SendMessages functionality pulled out of cs_main
a completely unnecessary tidy to merge the max size constant for addr / getdata / notfound
the timer from @ajtowns’ patch (aka net_processing changes only)
the batching tests, adding assertions & removing the print statements

some notes on the last commit:

cherry-picking that commit (and discarding the net_processing change from it) will fail on master & ad393c2d130b593b671b66e6a84c244664c3fd4c. but should pass on my branch.
AJ introduced a batching timer of 300ms, but I was getting flakiness in my tests, so I increased it to 1s. while that consistently passes on my machine, I don’t know how to guarantee it wouldn’t introduce flakiness in CI without having a sleep statement for each check from the test.

sipa commented at 9:18 pm on November 21, 2022: member

Let me give a bit of background on where this PR comes from.

I’ve been running some of my nodes with a patch to gather statistics on how frequently multiple messages are sent out simultaneously by the network thread (this is in the context of BIP324, where we’re investigating whether it makes sense to support having multiple application-level messages in one transport-level packet). When I looked at these numbers a few weeks ago, I noticed that there were a small number of peers which surprisingly high “message batching” (much more than other peers), and noticed that these same peers also had remarkably high frequency of NOTFOUNDs being sent.

This made me wonder - without further evidence - whether perhaps these peers were broken in some way that caused many NOTFOUNDs to be sent out by us which could really be batched together. If that were the case, it’d mean maybe my gathered statistics were unfairly biased by this easily correctable misbehavior, so I wrote a small patch to add to the nodes gathering statistics. As I then had this patch, it made sense to also PR it, as it wouldn’t hurt.

That said, I haven’t seen changes in the statistics since deploying with the patch, but that’s easily explainable by the fact that a SendMessages always follows a ProcessMessages. I’ve now included @ajtowns’ patch which adds a further delay to NOTFOUNDs and am re-running statistics with that.

To comment on some of the review comments: it’s a good question on whether the behavior change is acceptable and/or desirable. Historically, I’d say yes, because NOTFOUND was specifically introduced with the purpose of avoiding the need to constantly send PING after a GETDATA transaction to figure out whether it was missing or not, plus of course the fact that it’s already sent out of order w.r.t. TX messages in the GETDATA. I’m very open to discussing other issues that could arise of course.

I’ll address further comments on the code when I get more numbers (probably next week somewhere, hopefully that gives a representative picture).

jnewbery commented at 9:32 pm on November 24, 2022: contributor

I noticed that there were a small number of peers which surprisingly high “message batching” (much more than other peers), and noticed that these same peers also had remarkably high frequency of NOTFOUNDs being sent.

Were you able to identify/characterize those nodes in any way? The behaviour you describe seems unusual. In normal operation, most getdata requests will be for transactions that we’ve announced to the peer, and the responses will be individual tx messages - one for each transaction. It’s pretty rare to hit a notfound condition for a tx that we’ve announced (it’d need to have been removed from our mempool and aged out of our mapRelay cache). It therefore seems likely that those peers are requesting lots of transactions that we haven’t announced to them. Is it possible that those are spy/scanning peers? Should we therefore be trying to limit/disconnect those peers, rather than making requests from them more bandwidth efficient?

I do think that a similar change to this PR may be an improvement in the case where a single getdata with a large amount of inventory results in us sending multiple notfound messages. That isn’t a serious attack (after all, a peer could always just request the same tx multiple times if they wanted to waste bandwidth), but it does seem potentially slightly better if a single getdata can only ever result in a single notfound.

Message types INV, GETDATA, and NOTFOUND are similar in that they all have a payload consisting of a vector of CInv data structure. But while sent INV and GETDATA messages are constructed by aggregating them, and then sending them out in batch during SendMessages, NOTFOUND is sent immediately.

There’s a difference here: inv and getdata messages are initial messages in a dialog. The sender is free to batch or delay those messages however they want since the receiver isn’t waiting for them. notfound is an in-dialog response to a previous message so delaying/batching may be unexpected behaviour for the peer. I’m not aware of anywhere else that we batch responses to multiple inbound messages.

We already have out of order notfounds: if you request getdata [a,b,c] and b is known but a and c aren’t; we’ll send back tx b; notfound [a,c]. Having a pong interspersed as well doesn’t seem like it makes a big difference?

Those are different things. Our p2p implementation always treats inbound messages in serial and responds to them in order. Inventory within a single getdata message is not treated as serial, and hasn’t been ever since notfound was introduced in #2192. Lots of our tests use sync_with_ping to synchronise p2p exchange with the node (which isn’t in itself a good reason not to change this, but is a good indication of how deeply that assumption is baked in).

If this is safe to change, it might be good to explain.

I agree with this. I think changing such a long-standing assumption in our p2p implementation would require better motivation/explanation.

ajtowns commented at 11:20 pm on November 24, 2022: contributor

where we’re investigating whether it makes sense to support having multiple application-level messages in one transport-level packet).

Rather than delaying sending the notfounds by some arbitrary interval, it might make sense to have ProcessMessages keep invoking ProcessMessage until either some real work is done (looking up a block, running ATMP, etc), or there are no messages in the queue, and only then be followed by a single run of SendMessages. So if the message queue contains getdata tx; getdata tx; getdata block; getdata tx that’s treated exactly the same as getdata tx tx block tx.

sipa commented at 2:24 pm on February 27, 2023: member

I have no further interest in pursuing this, going to close it and mark as up for grabs.

sipa added the label Up for grabs on Feb 27, 2023

sipa closed this on Feb 27, 2023

bitcoin locked this on Feb 27, 2024

p2p: Batch send NOTFOUND messages #26486

Reviews

Conflicts