net: Add unit testing of node eviction logic #20477

Please move this doc-comment to the header, it's an exported function now.

Good point. Done!

Would it be valuable to break this out into the various reasons the peers are protected from eviction? For example:

In src/net.h

const int PEERS_PROTECTED_BY_NET_GROUP = 4                

In src/net.cpp

EraseLastKElements(vEvictionCandidates, CompareNetGroupKeyed, PEERS_PROTECTED_BY_NET_GROUP);

In src/test/net_tests.cpp:

GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE = PEERS_PROTECTED_BY_NET_GROUP + ... + 1

constexpr int GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE{29};

That is nicer. Addressed!

I think that is a good idea but I kind of like that this PR doesn't touch the actual selection code (keeping the diff at a minimum). I'd like to keep it that way but I'd be glad to review a change like the one suggested in a trivial "introduce constants" PR:).

Is this the highest such number at which non-eviction is guaranteed? If so, could you help me understand how we get 20?

Yes, but I'm afraid I cannot help you with that at the moment: so far it is a purely an empirical/experimental result :D

Counterexamples or proofs welcome! :)

Would it make sense to use emplace_back here?

I'm afraid that won't be possible until C++20¹ :) See P0960: "Allow initializing aggregates from a parenthesized list of values" .

¹ Assuming you mean without adding a new ctor to NodeEvictionCandidate.

This is a silent merge conflict with master. NODISCARD should be replaced with [[nodiscard]]

Why return a NodeEvictionCandidate optional here, when only the NodeId is used? I think it'd be better to return an Optional<NodeId>

Thanks! Fixed!

Makes sense. Feedback addressed!

Why is this called with cs_vNodes held? Previously, we'd release the lock before running through this logic.

What's the reason for the std::move here? Why not just pass this as an lvalue reference?

Good point. It can be moved to the outer scope. Thanks!

Context: #19972 (review)

rvalue ref was suggested by @sipa: see #19972 (review) for rationale.

I understand why you'd want to pass by ref, but there's no benefit to passing by rvalue. This code suggests to me that SelectNodeToEvict() is going to keep ownership of vEvictionCandidates and you're using move semantics to avoid a copy, but that's not actually happening here.

There's no harm in using && and move here, but it's unnecessary and possibly confusing.

This can create duplicate node ids, which isn't possible in the product code.

Now setting id to i directly making it unique. Instead of relying on the caller doing this :)

Does this break if there are multiple eviction candidates with the same id?

Yes, the code was relying on the caller making sure the candidate ids are unique. Now doing that in GetRandomNodeEvictionCandidates as suggested.

I think if you just constructed the NodeEvictionCandidates with sequential node id numbers, you wouldn't need to do this here.

Good point. Done!

No longer needed since you removed NODISCARD

Fixed!

I think this function and the other IsEvicted() could use a very short comment to explain the interface (here: returns true if any of the node ids in node_ids are selected for eviction).

Fixed!

Any reason not to shuffle in place?

bool IsEvicted(std::vector<NodeEvictionCandidate>& candidates, const std::vector<NodeId> node_ids, FastRandomContext& random_context)
{
    Shuffle(candidates.begin(), candidates.end(), random_context);
    const Optional<NodeId> evicted_node_id = SelectNodeToEvict(candidates);

Please add some justification for these numbers, even if it's a description of the simulation/test you ran to get them. I don't understand how this 29 is guaranteed and the 20 is guaranteed below.

This reply makes it sound like it's not guaranteed?

#20477 (review)

Good discussion in PR review club about it today and @jonatack pointed out justification for the 20 is in test/functional/p2p_eviction.py.

I think you're not running the following checks if the number of nodes is between the min and the max because of this continue. Is that the intention?

Edit: ignore me! I'm looking at the wrong for loop.

Edit again: Nope, I think I was right the first time...

I don't get this either

I've proposed an alternative that might be easier to parse. https://github.com/bitcoin/bitcoin/pull/20477/files#r539574518

It's "don't run the checks if the number of nodes is less than the max". But, I'm not sure why we would do this...

@narula Oh, good catch! The continue should be dropped. I don't remember what the apparently incorrect reasoning behind it was TBH :)

Thanks for catching it!

I'm a HUGE supporter of the early return pattern (AKA bouncer pattern) that you're using here. However, maybe this alternative is a little easier to parse.

(Maybe not in this annoyingly narrow GitHub window though...)

            if (number_of_nodes < GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE) {
            	// Verify correctness of GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW
            	if (number_of_nodes <= GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW) {
            		// At this number of nodes, we're guaranteed to never evict any of them
                	BOOST_CHECK(!SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));
                }
            	// There is no need to run the sub-tests for fewer than the number of nodes guaranteed for eviction
            	// ^ FWIW I don't agree with this, see below
            	continue;
            }
            // number_of_nodes >= GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE
            // Verify correctness of GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE
            BOOST_CHECK(SelectNodeToEvict(GetRandomNodeEvictionCandidates(number_of_nodes, random_context)));  

Honestly though, I think it's just the similarity between the names of GUARANTEED_EVICTION_AT_N_CANDIDATES_OR_ABOVE and GUARANTEED_NON_EVICTION_AT_N_CANDIDATES_OR_BELOW that is making this so difficult. Maybe (maybe...) EVICTION_THRESHOLD and NON_EVICTION_THRESHOLD and put the fact that it's inclusive on both ends in the comments? Or follow the half-open convention of "lower bounds are inclusive, upper bounds are exclusive". Popular in Python, not sure about C++.

All of this said, why have the early return at all? All of the tests below check for non-eviction. Can't we run them regardless of the number of nodes?

(Feel free to reword my code comments)

The comment here says 'four', but the code below is asserting that 8 non-tx-relay candidates are protected.

Good catch. There are two nLastBlockTime based protections: that's why more than four are protected in practice in this specific test case. Now testing the two different nLastBlockTime protections a.) independently and b.) jointly.

nit: could use ranged for loop?

Oh, of course. A prior version used the index. Thanks!

how is this different from a less verbose

    return node_ids.find(*evicted_node_id) != node_ids.end();

std::vector doesn't have a find function. Perhaps you were thinking of std::map or std::set? :)

style-nit: Adding a trailing comma here would not only make future diffs smaller if they add a new member, but also eat the extraneous whitespace at the beginning of the line.

Good point! Thanks!

In the previous version of the test, we tested:

1. No eviction happens with <= 20 peers
2. An eviction happens with >= 29 peers
3. If an eviction happens, the protected peers are not evicted

In the new version, we are checking that the protected peers are not evicted in any situation (3). The last test case covers for (1). However, the test will not alert if an eviction does not happen when it should (>= 29 peers). Am I missing something?

Personally, I found the GUARANTEED_EVICTION_THRESHOLD and GUARANTEED_NON_EVICTION_THRESHOLD valuable to test and also as documentation.

@dhruv I can re-add it if someone has time to figure out the actual logic behind the constant 29. I haven't had time to back my empirical observation (via simulation) with proper analysis. Help welcome! :)

From PR Review club:

Q: Why is eviction guaranteed if we have at least 29 eviction candidates?

The code in net.cpp (https://github.com/bitcoin/bitcoin/blob/fabecce/src/net.cpp#L954-L968) protects at most 28 peers from eviction (4 by net group, 8 by lowest ping time, 4 by last time of novel tx, up to 8 non-tx-relay peers by last novel block time, and 4 more peers by last novel block time). So any additional peers are guaranteed to be candidates for eviction.

Q: Why is non-eviction guaranteed if we have no more than 20 eviction candidates? Is 20 the highest number of nodes that guarantees non-eviction?

The protection at net.cpp::961 for up to 8 non-tx-relay peers may, or may not apply to the randomly generated eviction candidates since !n.fRelayTxes && n.fRelevantServices will evaluate to randbool. So we cannot count them in the guaranteed non-eviction?

So, guaranteed non-eviction is only on 4(CompareNetGroupKeyed) + 8(ReverseCompareNodeMinPingTime) + 4(CompareNodeTXTime) + 4(CompareNodeBlockTime) = 20.

@practicalswift the review club meeting log about your PR is here, if useful: https://bitcoincore.reviews/20477

Thanks! Now assert eviction at >= 29 candidates and non-eviction at <= 20 candidates. Please re-review :)

I don't think these <=20/>=29 tests are very useful, will need to be updated whenever any changes are made to the eviction logic, and aren't very realistic (in general, nodes have many more than 29 inbound slots).

I'll happily adjust to the consensus opinion, but I'll let others chime in before changing anything in order to avoid another round of change+revert :)

Even if we remove the <=20 assertion, we are already checking non-eviction <=20 (it's implicit in the tests). So the tests will need need to updated when changes are made anyway. I am not sure I understand why that's undesirable.

I think it is useful to test that eviction does indeed happen (not just that protections are provided) when it should. After all, SelectNodeToEvict should select a node to evict :) Without the >=29 assertion, does this test guarantee that?

All that said, @jnewbery is infinitely more qualified than I am. I'm happy with whatever you all decide and will learn from it.

fbba7d8aada5b1d7a63ad4133 add #include <optional.h> header

perhaps call this SelectConnectionToEvict() for symmetry with AttemptToEvictConnection(), or SelectPeerToEvict() as a peer is a node that is not ours

Now including optional.h.

Regarding the naming: I see your point but given NodeEvictionCandidate inputs I think SelectNodeToEvict works.

fbba7d8aada5b1d7a63ad4 could be const

Good catch! Fixed!

6767d63d02cc8a670f3d409db1 ref to const?

bool IsEvicted(std::vector<NodeEvictionCandidate> candidates, const std::vector<NodeId>& node_ids, FastRandomContext& random_context)

Good catch! Fixed!

6767d63d02cc8a670f3d409 ref to const here as well

bool IsEvicted(const int number_of_nodes, std::function<void(NodeEvictionCandidate&)> candidate_setup_fn, const std::vector<NodeId>& node_ids, FastRandomContext& random_context)

Good catch! Fixed!