-
Notifications
You must be signed in to change notification settings - Fork 37.7k
p2p: update inbound eviction protection for multiple networks, add I2P peers #21261
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
p2p: update inbound eviction protection for multiple networks, add I2P peers #21261
Conversation
3fdb720
to
486b7a3
Compare
The following sections might be updated with supplementary metadata relevant to reviewers and maintainers. ConflictsReviewers, this pull request conflicts with the following ones:
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. |
Concept ACK |
486b7a3
to
c228f1b
Compare
bf882d2
to
831b329
Compare
Concept ACK, will review more closely soon. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Approach ACK 831b329
76850b4
to
f5ba441
Compare
Concept ACK |
ba5e750
to
4890e2f
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Approach ACK 4890e2f
Some squashing is warranted.
Thanks! Indeed. Re-arranging. |
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Approach ACK 831b329
4890e2f
to
dd6f8c4
Compare
to compare and sort peer eviction candidates by the passed-in is_local (localhost status) and network arguments, and by longest uptime.
as we are about the change the behavior sufficiently that when we have multiple disadvantaged networks and a small number of peers under test, the number of protected peers per network can be different.
ce211cd
to
a457f34
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ACK a457f34
I've been running this PR (various versions) on a busy node for the last weeks. Unfortunately this node has a really high In any case |
with a more abstract framework to allow easily extending inbound eviction protection to peers connected through new higher-latency networks that are disadvantaged by our inbound eviction criteria, such as I2P and perhaps other BIP155 networks in the future like CJDNS. This is a change in behavior. The algorithm is a basically a multi-pass knapsack: - Count the number of eviction candidates in each of the disadvantaged privacy networks. - Sort the networks from lower to higher candidate counts, so that a network with fewer candidates will have the first opportunity for any unused slots remaining from the previous iteration. In the case of a tie in candidate counts, priority is given by array member order from first to last, guesstimated to favor more unusual networks. - Iterate through the networks in this order. On each iteration, allocate each network an equal number of protected slots targeting a total number of candidates to protect, provided any slots remain in the knapsack. - Protect the candidates in that network having the longest uptime, if any in that network are present. - Continue iterating as long as we have non-allocated slots remaining and candidates available to protect. Localhost peers are treated as a network like Tor or I2P by aliasing them to an unused Network enumerator: Network::NET_MAX. The goal is to favorise diversity of our inbound connections. Credit to Vasil Dimov for improving the algorithm from single-pass to multi-pass to better allocate unused protection slots. Co-authored-by: Vasil Dimov <vd@FreeBSD.org>
This commit extends our inbound eviction protection to I2P peers to favorise the diversity of peer connections, as peers connected through the I2P network are otherwise disadvantaged by our eviction criteria for their higher latency (higher min ping times) relative to IPv4 and IPv6 peers, as well as relative to Tor onion peers. The `networks` array is order-dependent in the case of a tie in candidate counts between networks (earlier array members receive priority in the case of a tie). Therefore, we place I2P candidates before localhost and onion ones in terms of opportunity to recover unused remaining protected slots from the previous iteration, guesstimating that most nodes allowing both onion and I2P inbounds will have more onion peers, followed by localhost, then I2P, as I2P support is only being added in the upcoming v22.0 release.
a457f34
to
1b1088d
Compare
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
ACK 1b1088d
Last restart was last week, it gets connections quite quickly. Then again it is connected to all possible networks and has had a >99% uptime for a few years. Either that helps or maybe it's just all spy nodes 🙂 |
…iple networks, add I2P peers 1b1088d test: add combined I2P/onion/localhost eviction protection tests (Jon Atack) 7c2284e test: add tests for inbound eviction protection of I2P peers (Jon Atack) ce02dd1 p2p: extend inbound eviction protection by network to I2P peers (Jon Atack) 70bbc62 test: add combined onion/localhost eviction protection coverage (Jon Atack) 045cb40 p2p: remove unused m_is_onion member from NodeEvictionCandidate struct (Jon Atack) 310fab4 p2p: remove unused CompareLocalHostTimeConnected() (Jon Atack) 9e889e8 p2p: remove unused CompareOnionTimeConnected() (Jon Atack) 787d46b p2p: update ProtectEvictionCandidatesByRatio() doxygen docs (Jon Atack) 1e15acf p2p: make ProtectEvictionCandidatesByRatio() fully ratio-based (Jon Atack) 3f8105c test: remove combined onion/localhost eviction protection tests (Jon Atack) 38a81a8 p2p: add CompareNodeNetworkTime() comparator struct (Jon Atack) 4ee7aec p2p: add m_network to NodeEvictionCandidate struct (Jon Atack) 7321e6f p2p, refactor: rename vEvictionCandidates to eviction_candidates (Jon Atack) ec590f1 p2p, refactor: improve constness in ProtectEvictionCandidatesByRatio() (Jon Atack) 4a19f50 test: add ALL_NETWORKS to test utilities (Jon Atack) 519e76b test: speed up and simplify peer_eviction_test (Jon Atack) 1cde800 p2p, refactor: rm redundant erase_size calculation in SelectNodeToEvict() (Jon Atack) Pull request description: Continuing the work in bitcoin#20197 and bitcoin#20685, this pull updates and abstracts our inbound eviction protection to make it fully ratio-based and easily extensible to peers connected via high-latency privacy networks that we newly support, like I2P and perhaps others soon, as these peers are disadvantaged by the latency criteria of our eviction logic. It then adds eviction protection for peers connected over I2P. As described in bitcoin#20685 (comment), we've observed over the past few months that I2P peers have a min ping latency similar to or greater than that of onion peers. The algorithm is a basically a multi-pass knapsack: - Count the number of eviction candidates in each of the disadvantaged privacy networks. - Sort the networks from lower to higher candidate counts, so that a network with fewer candidates will have the first opportunity for any unused slots remaining from the previous iteration. In the case of a tie in candidate counts, priority is given by array member order from first to last, guesstimated to favor more unusual networks. - Iterate through the networks in this order. On each iteration, allocate each network an equal number of protected slots targeting a total number of candidates to protect, provided any slots remain in the knapsack. - Protect the candidates in that network having the longest uptime, if any in that network are present. - Continue iterating as long as we have non-allocated slots remaining and candidates available to protect. The goal of this logic is to favorise the diversity of our peer connections. The individual commit messages describe each change in more detail. Special thank you to Vasil Dimov for the excellent review feedback and the algorithm improvement that made this change much better than it would have been otherwise. Thanks also to Antoine Riard, whose review feedback nudged this change to protect disadvantaged networks having fewer, rather than more, eviction candidates. ACKs for top commit: laanwj: Code review re-ACK 1b1088d vasild: ACK 1b1088d Tree-SHA512: 722f790ff11f2969c79e45a5e0e938d94df78df8687e77002f32e3ef5c72a9ac10ebf8c7a9eb7f71882c97ab0e67b2778191effdb747d9ca54d7c23c2ed19a90
…ionCandidatesByRatio() b1d905c p2p: earlier continuation when no remaining eviction candidates (Vasil Dimov) c9e8d8f p2p: process more candidates per protection iteration (Jon Atack) 02e411e p2p: iterate eviction protection only on networks having candidates (Jon Atack) 5adb064 bench: add peer eviction protection benchmarks (Jon Atack) 566357f refactor: move GetRandomNodeEvictionCandidates() to test utilities (Jon Atack) Pull request description: This follow-up to #21261 improves `ProtectEvictionCandidatesByRatio()` for better performance. Benchmarks are added; the performance improvement is between 2x and 5x for the benchmarked cases (CPU 2.50GHz, Turbo off, performance mode, Debian Clang 11 non-debug build). ``` $ ./src/bench/bench_bitcoin -filter="EvictionProtection*.*" ``` The refactored code is well-covered by existing unit tests and also a fuzzer. - `$ ./src/test/test_bitcoin -t net_peer_eviction_tests` - `$ FUZZ=node_eviction ./src/test/fuzz/fuzz ../qa-assets/fuzz_seed_corpus/node_eviction` ACKs for top commit: klementtan: Tested and code review ACK b1d905c. vasild: ACK b1d905c jarolrod: ACK b1d905c Tree-SHA512: a3a6607b9ea2fec138da9780c03f63e177b6712091c5a3ddc3804b896a7585216446310280791f5e20cc023d02d2f03a4139237e12b5c1d7f2a1fa1011610e96
…P peers Summary: This pull updates and abstracts our inbound eviction protection to make it fully ratio-based and easily extensible to peers connected via high-latency privacy networks that we newly support, like I2P and perhaps others soon, as these peers are disadvantaged by the latency criteria of our eviction logic. It then adds eviction protection for peers connected over I2P. We've observed over the past few months that I2P peers have a min ping latency similar to or greater than that of onion peers. The algorithm is a basically a multi-pass knapsack: - Count the number of eviction candidates in each of the disadvantaged privacy networks. - Sort the networks from lower to higher candidate counts, so that a network with fewer candidates will have the first opportunity for any unused slots remaining from the previous iteration. In the case of a tie in candidate counts, priority is given by array member order from first to last, guesstimated to favor more unusual networks. - Iterate through the networks in this order. On each iteration, allocate each network an equal number of protected slots targeting a total number of candidates to protect, provided any slots remain in the knapsack. - Protect the candidates in that network having the longest uptime, if any in that network are present. - Continue iterating as long as we have non-allocated slots remaining and candidates available to protect. The goal of this logic is to promote the diversity of our peer connections. This is a backport of [[bitcoin/bitcoin#21261 | core#21261]] Depends on D11042 Test Plan: `ninja all check-all` Reviewers: #bitcoin_abc, Fabien Reviewed By: #bitcoin_abc, Fabien Subscribers: Fabien Differential Revision: https://reviews.bitcoinabc.org/D11051
…JDNS peers b7be28c test: add combined CJDNS/I2P/localhost/onion eviction protection tests (Jon Atack) 0a1bb84 test: add tests for inbound eviction protection of CJDNS peers (Jon Atack) 0c00c0c test: fix off-by-one logic in an eviction protection test (Jon Atack) f7b8094 p2p: extend inbound eviction protection by network to CJDNS peers (Jon Atack) Pull request description: Extend inbound eviction protection for peers connected over CJDNS, as is the case for peers connected via onion, localhost, and I2P since #21261 and #20197. CJDNS peers seem to have better min ping latency than onion and I2P peers but still higher than that of unencrypted IPv4/6 peers and can be disadvantaged under our eviction criteria. They are also very few in number, which is a further reason to protect them, as the goal of this logic is to favorise the diversity of our peer connections. CJDNS support was added in #23077 for the upcoming v23 release. ACKs for top commit: laanwj: Concept and code review ACK b7be28c w0xlt: tACK b7be28c Tree-SHA512: 89ebdd217602e16ae14b9bd0d5a25fc09f9b2384c951f820bc0f5a6d8452bbc9042065db817d5d5296c0ad22988491a83fc5b9a611e660c40ebd4f03448c4061
Continuing the work in #20197 and #20685, this pull updates and abstracts our inbound eviction protection to make it fully ratio-based and easily extensible to peers connected via high-latency privacy networks that we newly support, like I2P and perhaps others soon, as these peers are disadvantaged by the latency criteria of our eviction logic.
It then adds eviction protection for peers connected over I2P. As described in #20685 (comment), we've observed over the past few months that I2P peers have a min ping latency similar to or greater than that of onion peers.
The algorithm is a basically a multi-pass knapsack:
Count the number of eviction candidates in each of the disadvantaged
privacy networks.
Sort the networks from lower to higher candidate counts, so that
a network with fewer candidates will have the first opportunity
for any unused slots remaining from the previous iteration. In
the case of a tie in candidate counts, priority is given by array
member order from first to last, guesstimated to favor more unusual
networks.
Iterate through the networks in this order. On each iteration,
allocate each network an equal number of protected slots targeting
a total number of candidates to protect, provided any slots remain
in the knapsack.
Protect the candidates in that network having the longest uptime,
if any in that network are present.
Continue iterating as long as we have non-allocated slots
remaining and candidates available to protect.
The goal of this logic is to favorise the diversity of our peer connections.
The individual commit messages describe each change in more detail.
Special thank you to Vasil Dimov for the excellent review feedback and the algorithm improvement that made this change much better than it would have been otherwise. Thanks also to Antoine Riard, whose review feedback nudged this change to protect disadvantaged networks having fewer, rather than more, eviction candidates.