Test Details Overview

Make fair queue pops scale with the active origins instead of the peer count (#5252)

* Benchmark the fair queue as the peer count grows

nano/benchmarks/fair_queue.cpp measures a fair queue keyed by source and
channel over 200 to 5000 peers, without a node: steady arrivals popped one
at a time, a backlog drained in one batch, a storm with every queue full,
the ready-only pop of the reply servers with a share of the channels out
of room, a peer's first contact and maintenance. The channel stand-in
costs what the tcp channel does, an atomic load for alive and a mutex for
max, behind a virtual call. Profiles copy the caps, shares and dead origin
policies of the message processor, the vote processor and the vote
replier, and the queues are created in random order so the map's nodes
are scattered in memory as a node's are. Every run reports time and
allocations per request.

allocation_counter::report takes the units of work done, for a benchmark
whose iteration pops a whole batch.

* Walk a ring of the non-empty queues instead of every queue on a pop

A pop sought the next non-empty queue by stepping through the map of
every origin, so each request cost a walk past the idle peers between the
cursor and its sender: linear in the peer count, 344 ns per request at
200 peers and 17 µs at 5000 in the steady benchmark, and the same walk
once per batch under load.

The non-empty queues now form an intrusive ring which the cursor walks,
so a pop never visits an idle origin and costs the same at 5000 peers as
at 200: 109 ns per request in the steady benchmark, 2 to 20 times less on
a backlog, unchanged in a storm. A queue joins the ring with its first
request, just behind the cursor, which is the end of the round under way,
so a round stays bounded by the queues it started with and a stream of
refills cannot keep an origin with a backlog from its turn. A drained
queue leaves the ring at once, and so does a dead origin's queue that
the discard policy purges with its requests, the cursor moving past it as
past a drained queue. Origins are served in the order they joined rather
than in key order, and maintenance no longer restarts the round.

Tests pin those down and cover a discarded origin wherever the round is:
under the cursor at the end of its share or in the middle of it, waiting
for its turn, last in the ring, every origin at once, and purged by the
maintenance of a new origin or of a ready batch pop; under serve a dead
origin keeps its turns until it drains. A seeded random run under both
policies checks every step against a model of what each origin holds.

The origin is bound by reference in next and next_ready; a copy there
cost two atomic operations per pop.

* Look up an origin's queue through a hash map

The queues were held in a std::map, so every push paid a tree walk of
log2 (peers) comparisons across scattered nodes to find its origin's
queue, and the cost grew with the peer count: 109 ns per request at 200
peers and 188 ns at 5000 in the steady benchmark. The order the map kept
is not needed, since the ring decides the order of service.

The queues now live in a boost::unordered_node_map keyed by a hash of the
source and the channel pointer. A node map keeps every entry and its key
at a fixed address, which the ring hooks and the key pointers rely on. A
push costs about the same at 5000 peers as at 200: 100 to 137 ns per
request in the steady benchmark, 1.4 to 1.7 times less on a first contact
and on maintenance.

* Pop batches into a small vector instead of a deque

next_batch and next_ready_batch returned a std::deque, which allocates
its block map and a 4 KB block for the first element, so every bulk pop
paid two allocations whatever its size, and a consumer keeping up with a
trickle paid them per request.

They now return fair_queue::batch, a boost::container::small_vector with
room for 256 requests inline, the block processor's batch size, which a
larger batch outgrows onto the heap once, reserved up front from the
smaller of the limit and the queued count. The vote replier and the
bootstrap server name the type as queue_type::batch, the other owners
take it by auto. The alias is named only in declarations in the owners'
headers and the vector is instantiated in their sources, where the
request types are complete.

In the steady benchmark a request costs 64 ns instead of 102 at 200
peers and 93 instead of 155 at 5000, with no allocation; a storm drains
up to 1.2 times faster and a backlog is unchanged.

* Serve a fair queue's origin before deciding whether its turn is over

A pop asked whether the queue under the cursor had used its share before
serving it. When a drained or purged queue left the ring the cursor
moved on to the next queue with a count of 0, and for a share of 0 that
count already read as a share used up, so that queue was passed over
without a request served; behind an origin that drains and fills again
on every turn it was never served at all. A share of 0 can come from
pr_priority, priority_live, priority_bootstrap, priority_local and
priority_coefficient, and before the ring it took one request per turn
like a share of 1.

pop_current now serves the queue under the cursor first and decides its
turn afterwards: a drained queue leaves the ring, one that has taken its
share passes the turn on, and the cursor rests on the queue whose turn
it is. No check runs before a queue is served, so every queue the cursor
reaches takes at least one request whatever its share, and should_seek,
seek_next, seek_next_ready and after_cursor go. next_ready walks one
round from the cursor's queue and leaves the round as it was when
nothing is ready.

Two things change in the order of service. An origin that fills while
another has just used its share joins behind that origin rather than
ahead of it, still served once per round. A share that maintenance
lowers in the middle of a turn ends the turn one request later.

That the cursor is not off the end is checked once, in pop_current,
before anything is dereferenced. A queue's link state is checked in
release builds where it joins and leaves the ring, since a queue linked
twice or unlinked while out of the ring corrupts the list and Boost
checks that in debug builds only.

Tests cover a share of 0 through both pops, ready pops resuming a round
and passing a turn on, clear in the middle of a round and shares
refreshed by maintenance; the purge tests are reworked so the dying
origin is the one the round is on, and the random test also pushes with
push_evicting and holds every batch to the shares.

The steady, backlog, storm, ready and first contact benchmarks measure
the same as before, with no allocation added.

__________

Type: commit

Hash: 18f1a02cfee5feaeca68dda94819f2e0ccd9a5c4

Created: today

__________

gr0v1ty/nano-node:18f1a02cfee5feaeca68dda94819f2e0ccd9a5c4

Test Results

Test Case Status Duration Median Deviation Log Graph
No test results available yet. Check the GitHub test run for job status and logs.