Skip to content

Conversation

jonatack
Copy link
Member

@jonatack jonatack commented Feb 22, 2021

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.

@DrahtBot
Copy link
Contributor

DrahtBot commented Feb 22, 2021

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

Conflicts

Reviewers, 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.

@vasild
Copy link
Contributor

vasild commented Feb 25, 2021

Concept ACK

@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch from 486b7a3 to c228f1b Compare April 19, 2021 21:27
@jonatack jonatack changed the title p2p, test: add inbound eviction protection for I2P peers p2p: update inbound eviction protection for multiple networks, add I2P peers Apr 20, 2021
@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch 2 times, most recently from bf882d2 to 831b329 Compare April 22, 2021 18:13
@jonatack jonatack marked this pull request as ready for review April 22, 2021 18:45
@mzumsande
Copy link
Contributor

Concept ACK, will review more closely soon.

Copy link
Contributor

@vasild vasild left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Approach ACK 831b329

@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch 5 times, most recently from 76850b4 to f5ba441 Compare May 8, 2021 10:38
@laanwj
Copy link
Member

laanwj commented May 10, 2021

Concept ACK

@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch from ba5e750 to 4890e2f Compare May 16, 2021 13:55
Copy link
Contributor

@vasild vasild left a 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.

@jonatack
Copy link
Member Author

Approach ACK 4890e2f

Some squashing is warranted.

Thanks! Indeed. Re-arranging.

Copy link

@ariard ariard left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Approach ACK 831b329

@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch from 4890e2f to dd6f8c4 Compare June 2, 2021 21:46
jonatack added 3 commits June 13, 2021 20:15
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.
@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch from ce211cd to a457f34 Compare June 13, 2021 18:27
Copy link
Contributor

@vasild vasild left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK a457f34

@laanwj
Copy link
Member

laanwj commented Jun 14, 2021

I've been running this PR (various versions) on a busy node for the last weeks. Unfortunately this node has a really high maxconnections (500, while average number of connected peers is 200) so I just realize I haven't been actually testing the eviction behavior 😊

In any case
Code review (and lightly tested) ACK a457f34
Code review re-ACK 1b1088d

jonatack and others added 9 commits June 14, 2021 13:57
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.
@jonatack jonatack force-pushed the protect-i2p-peers-from-eviction branch from a457f34 to 1b1088d Compare June 14, 2021 12:13
@jonatack
Copy link
Member Author

jonatack commented Jun 14, 2021

Thanks @vasild and @laanwj. Updated per git diff a457f34 1b1088d --color-words for the review suggestion and to add 4 test cases, and updated the PR description to thank/credit @vasild and @ariard.

Copy link
Contributor

@vasild vasild left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ACK 1b1088d

@laanwj laanwj merged commit 5c4f0c4 into bitcoin:master Jun 14, 2021
@jonatack jonatack deleted the protect-i2p-peers-from-eviction branch June 14, 2021 13:16
@laanwj
Copy link
Member

laanwj commented Jun 14, 2021

Wow! How long does it take to get up to 200 peers? Mine is restarted a lot but never gets above 35-40.

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 🙂

sidhujag pushed a commit to syscoin/syscoin that referenced this pull request Jun 14, 2021
…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
laanwj added a commit that referenced this pull request Jul 15, 2021
…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
Fabcien pushed a commit to Bitcoin-ABC/bitcoin-abc that referenced this pull request Feb 17, 2022
…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
laanwj added a commit that referenced this pull request Mar 2, 2022
…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
gwillen pushed a commit to ElementsProject/elements that referenced this pull request Jun 1, 2022
@bitcoin bitcoin locked as resolved and limited conversation to collaborators Aug 16, 2022
Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
Projects
None yet
Development

Successfully merging this pull request may close these issues.

9 participants