Re: Restructured Shared Buffer Hash Table

v4.0 is not so fancy, but it works.

No apparent bugs on this version, passing check-world [1]
The best test to stress this feature is in the recovery suite [2]
The main open question is whether we should add a second attempt if we have
a lookup miss and the partition is locked (who knows it was locked by
someone
inserting the tag we want).

I am curious to see the results of this with some real pgbench. So I would
be
grateful if some of you can stress that out.

This version keeps the lock for insertion (and deletions), on the first
failure at
lookup, it acquires a LW_SHARED there too. These failures are very rare
so the impact of that lock in performance should be negligible compared to
acquiring the lock for every lookup.

Not having to acquire a lock on its own can make the buffer lookup faster
(buffer hits).

I am pasting three tables from my own benchmarks, from which I would like
to highlight a few results.
LWLockAcquire, LWLockRelease (nothing in between)
Uncontended with 10 workers: 218ns
Contended with 10 workers : 555 microseconds in one run 1.03ms in the other

Notice that the average is above q3 (0.57 quantile), indicating that it is
very
skewed, it is fast, but when it gets slow it becomes very slow. And this is
precisely what I have seen with LWLock BufferMapping waits, they either
don't show up, or they take the cluster down (I am not a DBA, so it is
anecdotal
evidence).

Average uncontended hit and miss.
2 workers, with lock (36, 38)
10 workers, with lock (225,409)
10 workers, without lock (156,252)

workers | op / wait | avg | q1 | med | q3 | count
---------+------------+---------+---------+---------+---------+--------
2 | delete / 0 | 42.58 | 39.76 | 42.28 | 44.28 | 127999
2 | delete / 1 | 5625.00 | 5625.00 | 5625.00 | 5625.00 | 1
2 | hit / 0 | 36.01 | 33.86 | 35.81 | 37.77 | 128000
2 | insert / 0 | 36.59 | 35.11 | 36.47 | 38.41 | 128000
2 | LWLock / 0 | 35.59 | 33.23 | 35.17 | 37.14 | 128000
2 | miss / 0 | 37.63 | 35.78 | 37.72 | 39.09 | 128000

workers | op / wait | avg | q1 | med | q3 |
count
---------+------------+------------+-----------+-----------+------------+--------
10 | delete / 0 | 792.11 | 166.58 | 225.58 | 277.75 |
119522
10 | delete / 1 | 1844238.60 | 45823.00 | 470479.00 | 2568042.25 |
478
10 | hit / 0 | 224.66 | 76.42 | 121.50 | 187.42 |
120000
10 | insert / 0 | 952.21 | 104.25 | 180.58 | 246.42 |
119566
10 | insert / 1 | 2154981.29 | 76708.00 | 703666.00 | 3334916.00 |
434
10 | LWLock / 0 | 218.06 | 69.33 | 104.17 | 152.67 |
119987
10 | LWLock / 1 | 1029929.62 | 126708.00 | 488459.00 | 836708.00 |
13
10 | miss / 0 | 408.87 | 76.42 | 156.08 | 184.00 |
120000

workers | op / wait | avg | q1 | med | q3 |
count
---------+------------+------------+-----------+-----------+------------+--------
10 | delete / 0 | 628.94 | 166.58 | 236.08 | 291.85 |
119595
10 | delete / 1 | 2135859.85 | 80125.00 | 704750.00 | 3329688.00 |
405
10 | hit / 0 | 155.96 | 55.33 | 104.17 | 145.67 |
120000
10 | insert / 0 | 792.89 | 100.67 | 190.83 | 250.00 |
119634
10 | insert / 1 | 2272327.08 | 114083.00 | 666959.00 | 3580042.00 |
366
10 | LWLock / 0 | 305.68 | 69.50 | 107.58 | 159.75 |
119993
10 | LWLock / 1 | 555255.86 | 77437.50 | 390458.00 | 528979.50 |
7
10 | miss / 0 | 251.58 | 45.25 | 93.83 | 121.58 |
120000

1. With './configure' '--prefix' ... '--without-icu' '--without-readline'
'--enable-tap-tests' --enable-cassert && make -j -s clean && make -j -s &&
make check-world
2. make -C src/test/recovery check PROVE_TESTS="t/027_stream_regress.pl"

PS.: I nearly forgot to attach the patches 🤣