Re: Restructured Shared Buffer Hash Table

Hi Hackers,

Did a multi-process benchmark, and a lock-free implementation.

The `hit` and `miss` lookup tests never contend, that is why they
have a different shape. Inline is previous Dhruv's implementation
atomics is the lock-free algorithm benchmarked with locks for a
fair comparison. lock-free is atomics removing benchmark locks.

The y axis is the total time spent on each operation, the reduction
in the lock paths is likely due to a smaller number waiting.

A contended lock is 1000x to 10000x slower than an uncontended lock

[image: image.png]

The limitation of this that I thought would not be a problem is that when
deleting
an entry and reinserting on a different bucket, scans that hold that entry
will follow
a link to another bucket. Currently I am just retrying, but the problem is
that if the
buffer is repeatedly deleted and inserted we might repeatedly fail to end
the bucket
scan.

To make it fair, we could prevent the reinsertion of one entry until all
the scans
that might use it finish. It would be preferable to have this on insert as
it doesn't
hold a lock and lookups are in the buffer hit path.

BuftableDelete
save bucket.start,finished
remove link
return when bucket.finished > saved start
if start > finished but they are not changing
consider strategies to align them if a process was killed during a scan.

This version is missing a HOLD_INTERRUPTS, would be considered enough
to prevent stale started > finished

One problem that I noticed, and I think affects all implementations (even
master)
is that there is no explicit memory synchronisation, the only thing that
prevents
us from ending up in the same situation I described here, is timing. Any
scan
must finish after a delete starts, any scan starting after the deletion
starts will be
put to sleep, and since waking up takes ~1000ns (and maybe context
switching helps),
by the time the next scan is attempted.

Q. general questions about atomics is there something like
pg_atomic_fetch(u32)
to indicate, I want this line, but I won't write to it?
Does a failed CAS steal the cache line? What about pg_atomic_fetch_add(p,
0)?

Regards,
Alexandre

On Sun, Aug 16, 2026 at 7:14 AM Alexandre Felipe <
o(dot)alexandre(dot)felipe(at)gmail(dot)com> wrote:

>
> On Tue, Jul 7, 2026 at 8:14 PM Heikki Linnakangas <hlinnaka(at)iki(dot)fi> wrote:
>
>> > bufmgr.c also changed slightly to prevent a race condition.
>>
>> Hmm, we're now holding the buffer header lock much longer than before,
>> in InvalidateBuffer(). It's a spinlock, it really should not be held for
>> more than a few instructions. BufTableDelete() is very fast in the new
>
> implementation, but still.
>
>
> As Andres later clarified the problem is not the duration of the lock, is
> the complexity of the safety risk of what we do under it.
>
> Could we perhaps do some of
>> BufTableDelete()'s work ahead of time, before we acquire the buffer
>> header lock?
>
>
> This is a better approach in my opinion, we can do the buffer search before
> acquiring the spin-lock and just break the chain link under the spin-lock.
> It is easier to prove the safety of the later operation, and hopefully get
> an
> agreement on the suitability of the change.
>
> I am adding a patch on top of Dhruv's work with that change.
>
> I also implemented the deletion by Buffer (del-buf), about 30% faster than
> original deletion by BufferTag (del-tag).
>
> I added the buffer header lock (spin-lock), partition lock (LWLock),
> and BufferHashCode to the benchmark. To see when we are entering
> the diminishing returns zone.
>
> 0003 - 2-step deletion (indistinguishable from 0002), del-buf faster than
> del-tag.
>
> op | avg | min | [q1 | median | q3] | p99 | std
> -----------+------+------+------+--------+------+------+------
> insert | 4.45 | 4.30 | 4.36 | 4.37 | 4.41 | 5.56 | 0.28
> hit | 5.96 | 5.81 | 5.86 | 5.88 | 5.93 | 6.82 | 0.27
> del-buf | 4.95 | 4.86 | 4.88 | 4.90 | 4.94 | 5.55 | 0.17
> insert | 4.46 | 4.39 | 4.41 | 4.42 | 4.45 | 4.86 | 0.10
> miss | 5.96 | 5.83 | 5.88 | 5.90 | 5.96 | 6.52 | 0.15
> del-tag | 7.32 | 7.14 | 7.18 | 7.20 | 7.28 | 8.49 | 0.61
> LWLock-ex | 7.88 | 7.78 | 7.78 | 7.79 | 7.88 | 8.70 | 0.23
> LWLock | 7.88 | 7.77 | 7.78 | 7.79 | 7.87 | 8.58 | 0.20
> HdrLock | 4.99 | 4.74 | 4.80 | 5.03 | 5.08 | 5.68 | 0.19
> hash | 4.44 | 4.37 | 4.38 | 4.39 | 4.44 | 4.97 | 0.16
> compare | 1.37 | 1.31 | 1.34 | 1.35 | 1.35 | 1.52 | 0.34
> nop | 0.91 | 0.88 | 0.90 | 0.90 | 0.91 | 1.03 | 0.04
>
> 0002 - Inline hash (Dhruv's original patch)
> op | avg | min | [q1 | median | q3] | p99 | std
> -----------+------+------+------+--------+------+------+------
> insert | 5.32 | 4.87 | 5.13 | 5.33 | 5.45 | 6.00 | 0.30
> hit | 7.15 | 6.53 | 6.92 | 7.16 | 7.32 | 7.77 | 0.30
> miss | 7.59 | 6.96 | 7.32 | 7.61 | 7.76 | 8.19 | 0.52
> del-tag | 8.59 | 7.85 | 8.30 | 8.60 | 8.78 | 9.32 | 0.50
> LWLock-ex | 8.43 | 7.78 | 8.15 | 8.46 | 8.63 | 9.17 | 0.31
> LWLock | 8.44 | 7.78 | 8.15 | 8.47 | 8.64 | 9.12 | 0.32
> HdrLock | 5.34 | 4.78 | 5.19 | 5.32 | 5.51 | 5.82 | 0.25
> hash | 4.74 | 4.38 | 4.59 | 4.75 | 4.85 | 5.17 | 0.20
> compare | 1.48 | 1.37 | 1.42 | 1.47 | 1.53 | 1.67 | 0.08
> nop | 0.98 | 0.90 | 0.94 | 0.97 | 1.02 | 1.11 | 0.05
>
> 0001 - Benchmark (master)
> op | avg | min | [q1 | median | q3] | p99 | std
> -----------+-------+-------+-------+--------+-------+-------+------
> insert | 16.28 | 15.48 | 15.65 | 15.75 | 16.18 | 23.91 | 2.61
> hit | 13.31 | 12.51 | 12.72 | 12.76 | 12.99 | 17.45 | 7.70
> miss | 13.29 | 12.65 | 12.94 | 12.98 | 13.20 | 16.34 | 2.21
> del-tag | 10.31 | 9.66 | 9.96 | 9.99 | 10.15 | 15.33 | 1.72
> LWLock-ex | 7.94 | 7.59 | 7.79 | 7.80 | 7.93 | 9.17 | 0.63
> LWLock | 7.92 | 7.65 | 7.78 | 7.79 | 7.91 | 10.00 | 0.46
> HdrLock | 5.01 | 4.65 | 4.81 | 5.03 | 5.10 | 5.70 | 0.32
> hash | 4.56 | 4.39 | 4.47 | 4.51 | 4.57 | 5.18 | 0.20
> compare | 1.40 | 1.34 | 1.37 | 1.37 | 1.39 | 1.68 | 0.09
> nop | 0.92 | 0.88 | 0.90 | 0.90 | 0.92 | 1.10 | 0.05
>
>
> Regards,
> Alexandre
>
>