Re: [PATCH] Batched clock sweep to reduce cross-socket atomic contention

Hello again,

Removing the freelist [1] turned out to be a good idea, so why not remove
and simplify more?

Included is a three-patch series (v3, on 2e6578292a9 cf-7000) that
replaces the 0..5 usage_count clock sweep with a cooling-stage clock,
and because this evictor algorithm is scan resistance 0003 removes
the BufferAccessStrategy ring buffers entirely. The net is slightly
faster (TPS), hotter buffers (fewer misses) and a lot less code to
maintain (no special case for scan resistant work) going forward.

0001 Batch the clock sweep to reduce nextVictimBuffer atomic contention
0002 Replace the usage_count clock sweep with a cooling-stage evictor
0003 Remove BufferAccessStrategy; scan resistance is now intrinsic

Net it is +510/-1642 over 83 files; almost all of the deletion is 0003.

On a 6-NUMA-node r8i.metal-96xl under continuous eviction, this change is
a consistent +4–5% on read-heavy pgbench with equal-or-better hit ratios.
The same test on a 2-node box is flat, which is the tell that the win
is the cross-socket clock-hand contention the batched sweep removes. Under
real storage IO (working set > RAM on local NVMe), the scan-resistance
path is +1.6–3.9% with measurably fewer heap reads.

I'll put the design decisions and the benchmark methodology on the table
first, then talk through the results because if the model is wrong on
principle, or the benchmarks are measuring the wrong thing, I would much
rather hear it now.

Contention arises on high core-count systems from the of cost advancing
nextVictimBuffer in StrategyGetBuffer() via a fetch-add of 1 per tick.
This contention is exacerbated on a multi-socket box. That one cache
line bounces over the interconnect on every eviction; under pressure
with hundreds of backends it is the dominant cost of the sweep. This is
why we're investing time on NUMA optimizations.

== What each patch does, and why ==

0001 -- Batch the clock sweep.

This is the setup/baseline commit and is an incremental improvement
over the existing batched approach, but it is not the final goal and
should not be committed without 0002.

Each backend will claim a run of consecutive buffer IDs with a single
fetch-add and iterate them privately. Global sweep order is preserved
-- each buffer is visited exactly once per pass -- only the intra-pass
ordering of visits changes, which the algorithm does not depend on.
The atomic fires ~1/batch as often.

The batch is one cache line's worth of hand values (PG_CACHE_LINE_SIZE
/ sizeof(uint32)), capped at NBuffers. It is gated on multi-node NUMA
(pg_numa_get_max_node() >= 1); on a single socket the batch is 1 and
the path is byte-identical to today. This is essentially Jim's patch;
the only substantive change from his v1/v2 is deriving the batch size
from the cache-line size rather than a fixed 64/tiered constant.

0002 -- Replace usage_count with a cooling-stage evictor.

This is the heart of the series and where I most want the design
attacked.

A buffer is HOT (recently used) or COOL (an eviction candidate);
"pinned" is the existing refcount. There is no per-buffer 0..5
counter. A demand-loaded page is admitted COOL (probationary); a
second access promotes it COOL->HOT. So a page touched once -- as is
the case with a sequential scan -- fills and drains the COOL stage and
is evicted from it without displacing the HOT working set. This is
the LeanStore / 2Q-A1 idea, and it is the whole reason 0003 can exist:
scan resistance stops being a ring-buffer bolt-on and becomes a
property of the replacement algorithm.

The 4-bit usage_count field is reinterpreted in place -- bit 0
HOT/COOL, bit 1 a reference bit, the top 2 bits unused -- so the 64-bit
buffer-state layout, its refcount / flag / lock offsets. The only
change to the StaticAsserts is a new one asserting the field is at
least 2 bits wide, since we now use two of its bits. The eviction
claim (COOL, unpinned -> pinned) stays a CAS so a racing PinBuffer
always wins; promotion and demotion are single-bit transitions.

The one non-obvious decision, which I got wrong first and want to flag
loudly: *Who* demotes HOT->COOL. My first cut was "prefer-COOL": the
foreground sweep skips HOT buffers hunting for an already-COOL victim
and only cools HOT buffers once a full pass finds none. That
collapses under an ordinary OLTP workload where the working set is
larger than shared_buffers (no scan at all). Every access promotes
its buffer to HOT, so there are almost no COOL buffers, the "cool a
full pass" fallback fires on nearly every allocation, and each victim
search becomes a ~2x full-pool scan of scattered BufferDescs. I
measured 3-17x throughput loss vs stock -- a cliff.

HOT->COOL demotion is done during the background writer's existing LRU
scan, which already runs ahead of the clock hand. It demotes just
enough HOT buffers to keep a supply of COOL victims (bounded by the
predicted next-cycle allocation, so it does not cool the whole pool),
under the buffer header lock it already holds. A single reference bit
gives a recently-accessed buffer one reprieve before it is cooled,
which keeps the genuinely-hot set out of the COOL stage under scan
pressure. With that, the foreground finds a victim in a single pass
and the cliff is gone (data below).

I chose prefer-COOL-plus-bgwriter-precooling because it can protect a
hot buffer slightly longer (the pre-cooler, tuned to a budget, decides
when to demote rather than demoting on contact), which should help hit
ratio on a stable hot set -- IF the pre-cooler keeps up. When it lags
(bgwriter off or behind), the foreground force_cool is still there as
a correctness fallback, but it is the expensive path.

0003 -- Remove BufferAccessStrategy.

With scan resistance intrinsic, the BAS_BULKREAD/BULKWRITE/VACUUM
rings are dead weight, so this removes them end to end: the type and
enum, the ring machinery in freelist.c, the strategy parameter
threaded through ReadBufferExtended / the ExtendBufferedRel* family /
read_stream / every scan/vacuum/analyze/index-AM caller, the strategy
fields on the scan and bulk-insert descriptors, and
_hash_getbuf_with_strategy. pg_stat_io's per-strategy IO contexts
collapse to normal/init (IOOP_REUSE only ever happened while recycling
a ring buffer, so it is gone), and the vacuum_buffer_usage_limit GUC /
VACUUM (BUFFER_USAGE_LIMIT ...) option / vacuumdb --buffer-usage-limit
go with it.

This is the patch most likely to be contentious for reasons unrelated
to the sweep: it removes a user-visible GUC and changes pg_stat_io's
shape. I have kept it as its own commit precisely so 0001+0002 can be
judged on the algorithm without swallowing the removal. If the
consensus is that the cooling model is fine but the ring machinery
should stay for other reasons (BUFFER_USAGE_LIMIT as an operator
control, say), 0003 can simply be dropped and 0002 still stands -- the
rings just become redundant rather than removed. I would like to know
if that is where people land.

== Benchmarks ==

I want to be careful here, because Andres's central criticism of the
original batched-sweep numbers [2] was that they measured the wrong
thing -- an all-in-page-cache config where the only bottleneck left is
the atomic, which is not how anyone runs a 384-vCPU box. That criticism
is correct and I have tried to design around it, but I have almost
certainly not fully escaped it, so the methodology is laid out below in
enough detail to shoot at.

I refer to the COOL/HOT approach (the changes in this patch set) as
"bcs", I've forgotten what that stands for... "buffer cache solution?"
I really don't remember (ha!).

Hardware / method (both instances bare-metal, Amazon Linux 2023):

- m6i.metal -- 128 vCPU, 2 sockets, 2 NUMA nodes (distances 10/20), 503GB
- r8i.metal-96xl -- 384 vCPU, 2 sockets, 6 NUMA nodes via SNC3, 3TB

Builds: --buildtype=debugoptimized (-O2), cassert off, --with-libnuma,
both branches from the same tree. Postmaster pinned with numactl
--cpunodebind=0 --membind=0 (without it stock TPS varied ~30% by launch
node -- worth flagging for anyone reproducing). pgbench dataset loaded
once per build into its own datadir.

The regime I settled on: a dataset that fits fully in OS page cache but
exceeds shared_buffers, warmed before each cell, caches NOT dropped
between cells. The point is a sweep that runs continuously with
sub-millisecond read latency and NO storage IO in the critical path --
so what I am measuring is the eviction machinery itself, not the disk
(as best as I can tell).

I sweep the ratio (working-set / shared_buffers) from 0.8 (fits, no
eviction, a control) up to 8x by varying shared_buffers against a fixed
63GB dataset.

3 iterations per cell, medians reported, 256 clients on m6i / 384 on r8i.

Two workloads: uniform pgbench -S (the pure eviction-churn case, and the
worst case for the cooling model -- no hot set to protect), and
"hotscan" (a Zipfian hot set plus a handful of clients running large
range scans -- the scan-resistance case).

I want the regime itself critiqued. It deliberately removes storage IO
to expose the sweep; the flip side is it is not a production
configuration, and the read-path win (fewer misses under scan
resistance) shows up as read count, not TPS, because a "miss" here is an
OS-cache memcpy, not a device read.

r8i.metal-96xl, uniform pgbench -S, 384 clients, TPS (median of 3):

ratio SB(GB) stock bcs delta stock/bcs hit%
0.8 ~400 1,623,536 1,692,090 +4.2% 99.2 / 99.9
1.25 ~320 1,443,343 1,519,290 +5.3% 94.8 / 95.2
1.5 ~266 1,344,051 1,417,462 +5.5% 91.9 / 92.1
2 ~200 1,293,871 1,358,550 +5.0% 87.9 / 87.8
4 ~100 1,194,405 1,240,334 +3.8% 77.1 / 78.5
8 ~50 1,090,873 1,140,839 +4.6% 69.7 / 70.6

Consistent +4-5% across the eviction range, growing with pressure, with
equal-or-better hit ratio (better at 4x/8x). bcs also showed lower
cache-miss rate in perf stat (~28-35% vs ~31-37%), which is the batched
sweep's reduced cross-node line bouncing showing through.

r8i, hotscan (Zipfian hot set + range scanners), TPS / hit% / heap reads:

ratio stock TPS bcs TPS stock hit bcs hit stock reads bcs reads
1.25 1,833,675 1,871,289 99.43 99.57 7,309,457 5,503,927
1.5 1,876,846 1,942,877 99.35 99.42 8,335,144 7,565,667
2 1,868,591 1,853,547 99.12 99.15 11,173,831 10,987,371

The scan-resistance signal: at 1.25-1.5x, bcs holds a higher hit ratio
and does up to 25% fewer heap reads (24.7% at 1.25x, ~9% at 1.5x) -- it
is keeping the hot set resident through the scans where stock lets them
flush it. Muted in TPS only because everything is in OS cache (a miss
is cheap); on real storage this read reduction is where the win would
land. At 2x it washes out (enough pressure that both evict heavily).

m6i.metal (2 nodes), uniform, 256 clients -- the smaller box, for contrast:
essentially parity, bcs -2% to +1% across ratios. The 2-node box barely
exercises the atomic, so 0001's contention win does not appear; that it does
not regress is the result that matters here.

Huge pages on vs off (r8i, uniform, medians): I ran this because the
original thread flagged it as uncharacterized. bcs won by +3-7% both
ways, no regression without huge pages -- the win is from cutting the
frequency of atomic ops on the counter line, which does not depend on
where the descriptors physically live. (This is why the batching gate
is NUMA-only and not also huge-pages-gated.)

The "prefer-COOL cliff" I mentioned under 0002, so the failure mode is
on the record: BEFORE moving cooling into the bgwriter, the m6i uniform
run at 256 clients was bcs 274K vs stock 840K at ratio 2 (-67%), and
42.8K vs 762K at 8x (-94%), with cache-miss rate exploding to ~40%.
That is the shape of getting the demotion policy wrong; the r8i +5%
table above is after the fix.

Reproduction: the whole harness (instance launch, OS tuning, per-build
load, the ratio sweep, perf stat capture) is scripted; I will attach it
as a DO-NOT-MERGE commit / put it in the CF entry so the methodology can
be reproduced and picked apart rather than taken on faith. Raw per-run
CSVs and perf output likewise.

A Real IO (working set > RAM, evictions hitting storage) Benchmark

This is the regime Andres asked for, and the one I flagged earlier as not yet
done cleanly. The earlier attempt was EBS-latency-bound; this one uses local
NVMe so eviction reads hit real storage at ~microsecond, not ~15ms, latency --
during the run the array sat at 100% utilization and ~145K read IOPS, so the
eviction path is genuinely storage-bound, not cache-served.

m6id.metal -- 128 vCPU, 2 sockets, 2 NUMA nodes, 503GB, 4x1.9TB local NVMe in
RAID0. Dataset ~700GB (pgbench scale 47000), i.e. LARGER than RAM, so the
working set cannot sit in the OS page cache. shared_buffers is a small window
over it -- 63GB (11x) and 31GB (22x) -- caches dropped per cell, 256 clients, 3
iterations, medians. Same builds/method as the in-cache runs otherwise.

hotscan (Zipfian hot set + range scanners), median of 3:

ratio SB(GB) stock TPS bcs TPS dTPS stock/bcs hit reads d
11 63 877,357 911,363 +3.9% 96.30 / 96.43 -2.2%
22 31 873,880 888,010 +1.6% 94.02 / 94.22 -1.5%

This is the result the in-cache runs could only hint at: under real storage IO
the scan-resistance read reduction converts to throughput. The bcs approach
keeps a higher hit ratio and does 1.5-2.2% fewer heap reads, and here -- unlike
in cache, where a miss is a cheap memcpy -- a read it avoids is an NVMe round
trip, so the read reduction shows up as +1.6-3.9% TPS.

uniform pgbench -S (pure eviction churn, no hot set to protect), median of 3:

ratio SB(GB) stock TPS bcs TPS dTPS stock/bcs hit
11 63 605,656 616,247 +1.7% 67.0 / 67.3
22 31 605,517 611,312 +1.0% 63.5 / 63.6

Hit ratio here is 63-67% -- a third of accesses miss and hit NVMe (190M-220M
evictions per run), so this is deep, genuinely storage-bound churn. bcs is
+1-1.7%, i.e. flat-to-slightly-positive, which is the honest production picture:
with no hot set to protect, scan resistance has nothing to do, and the win is
just the batched sweep's reduced contention showing faintly through the IO wait.
Notably bcs does not regress even when its policy has no advantage to exploit.

== Side note for the curious... ==

Separately, Dhruv Aron has proposed restructuring the shared-buffer lookup table
[2], replacing dynahash with a flat two-array structure. That attacks the
other hot cost on a buffer miss — resolving a page to its buffer — where this
series attacks the eviction that a miss triggers. They touch buf_table.c and a
lock-ordering change in InvalidateBuffer(); this series touches freelist.c and
the per-buffer replacement state, and removes BufferAccessStrategy. The two are
complementary and should compound on the miss path; the only overlap is
InvalidateBuffer()/GetVictimBuffer(), where their extended buffer-header-lock
hold and this series' CAS-claim + bgwriter pre-cooling both take that lock, and
would want reconciling if both land. I have not benchmarked them together (yet).

== What I have not done, honestly ==

- Hardening the foreground force_cool fallback to be cheap when it
fires, rather than relying on the bgwriter pre-cooler never lagging.

- Anything on single-socket beyond "does not regress"; the design is
not trying to help there.

== The ask ==

1. 0002's demotion policy: is prefer-COOL + bgwriter pre-cooling the
right call, or is the other team's cool-in-place the more robust
default given it has no cliff and no background-process dependency?
This is the decision everything else hangs on.

2. Is admitting demand-loaded pages COOL (probationary,
promote-on-second- touch) an acceptable basis for scan resistance
in the core buffer manager, i.e. is it OK to make scan resistance
an algorithm property and retire the strategy rings (0003)? Or
should the rings stay and 0002 ride alongside them?

3. The benchmark methodology: where is the in-OS-cache regime
misleading, and what would you want measured instead? I am most
worried I am flattering the sweep by removing the IO that would
otherwise hide it.

4. Reinterpreting the usage_count field as {HOT/COOL, ref} bits and
collapsing pg_stat_io's contexts -- acceptable, or is there a
cleaner representation the project would want before this is worth
pursuing?

I have measured that the 0..5 count is overhead and provides no
meaningful signal at all, that a HOT/COLD approach provides a simpler
more stable and better performing eviction model for the buffer pool.
If you dispute that, let's dig in and compare notes. :)

I would be remiss if I didn't point out the thread [3] by Tomas et. al.,
whose NUMA investigation targets the same bottlenecks, and inspired the
work that led to this set of ideas.

Thanks for reading this far. I look forward to the critique.

best.

-greg

[1] Reconsidering the freelist
https://www.postgresql.org/message-id/f0e3c02e-e217-4f04-8dab-1e7e80a228c0%40burd.me
[2] Re: Restructured Shared Buffer Hash Table
https://www.postgresql.org/message-id/dbbd1998-19ff-4ac2-b4b1-a39f4ec1b0f5@iki.fi
[3] Adding basic NUMA awareness (Tomas Vondra)
https://www.postgresql.org/message-id/099b9433-2855-4f1b-b421-d078a5d82017%40vondra.me