Re: Restructured Shared Buffer Hash Table

Hi,

On 2026-07-07 11:41:47 -0700, Dhruv Aron wrote:
> At Databricks, we’ve found that the existing dynahash table structure is
> leaving performance gains on the table when it comes to shared buffer
> lookups: the multi-level structure (directory, segment, bucket chain,
> freelist) appears excessive for the shared buffers and could be simplified
> to boost performance and lower memory overhead. As such, we are proposing a
> specialized hash table just for this purpose and would appreciate feedback
> on this approach.

Agreed, it's quite terrible.

> To give a brief overview, our new table operates primarily on two arrays,
> one for the entries and one for the bucket heads, and it enforces the
> invariant that *entries[x]* describes the page in buffer *x*. Each entry
> stores only a BufferTag and a ‘next’ index (representing the next entry in
> the same bucket chain), with each bucket head only storing a ‘head’ index
> (representing the first entry in the bucket chain). At a high-level, the
> table essentially creates a logical linked list for each bucket on top of
> the flat physical arrays.

Why did you choose a design that is effectively pointered? Pointered conflict
handling tends to be a good bit slower due to the typically unprefetchable
accesses. That's also - I suspect at least - part of what's pushing you
towards having both buckets[] and entries[], which seems like an unnecessary
indirection to me. Although admittedly the partition locking handling would
be more complicated without the separate array.

I also suspect that it'd be better to store a hash value in the buckets,
BufferTagsEqual() is decidedly not cheap, and you'll obviously get a lot of
"false" matches from hashcode % num_buckets that would be much cheaper to
detect with a stored hash value.

My higher level problems with the current architecture of the buffer mapping
infrastructure are the following:

1) We need a way to iterate over all buffers for a relation in an efficient
way

The fact that today stuff like dropping storage requires scanning all of
the buffer pool is probably the most problematic for using decently sized
buffer pools. We've made it a bit less bad by combining multiple such
scans into one, but fundamentally it's still O(NBuffers).

2) I think any buffer mapping lookup datastructure with 20 byte keys is going
to considerably not great for performance.

3) We should have efficient ordered lookup, to make things like "are there any
not-present blocks in the next N blocks" cheap. Today we need to do full
buffer lookups for readahead, which requires us to be very minimal about
lookahead when having a high cache hit ratio, to avoid performance
regressions - but that also prevents us from avoiding synchronous misses in
such cases.

4) Acquiring a lock for every lookup scales badly on larger machines, even if
the lock itself is not contended, due to the cacheline contention it
creates

5) The datastructure should benefit from spatial locality

It's much more common for subsequent buffer mapping lookups to look up
nearby blocks than blocks very far away. But with hash tables, the
likelihood of finding blocks N and N+1 in the CPU cache is no better than
looking up two entirely independent blocks.

For 1-3), I think we should move towards a two-layer datastructure:

a) a mapping from relation+fork to a per-"logical file" datastructure

Keyed by database, tablespace, relfilenode, fork (although the fork
could be handled differently).

This lookup would be cached somewhere below Relation, so we only would need
to occasionally do it, so the size of the key would not matter for
performance.

This addresses 1+2.

(there's plenty complexity here, don't get me wrong)

b) A block-number keyed lookup datastructure returning buffer IDs

If this datastructure is ordered, it addresses 3).

Due to the small key, something like a radix tree is viable (not a plain
one, but something like what we have in radixtree.h, with the missing
optimization from the referenced paper added).

A radix tree would also address 5).

To address 4) I think we should eventually allow to make lookups in b)
lock-free, using something like RCU or EBR (arguably a form of RCU). I would
definitely not tackle that at the same time, but I think it's worth keeping in
mind.

I'm of a somewhat split mind about improving the efficiency of the current
design without addressing any of the architectural problems. It's of course
nice to make it faster, but it also takes bandwidth that can't be spent on
the architectural problems...

> The attached patch implements this functionality and passes the existing
> regression tests; the buf_table.c functions were modified directly, with
> bufmgr.c also changed slightly to prevent a race condition.

As mentioned elsewhere, it's not OK to keep spinlocks held across nontrivial
operations, which both lwlocks and hash table lookup certainly are.

Sspinlocks (neither plain ones nor the buffer header lock variant) have no
error recovery whatsoever, so any error that is thrown will make the system
unusable. It's hard to guarantee that nothing can throw an error unless you
keep the covered code very small. Adding error recovery (like lwlocks have
via LWLockReleaseAll()), would make spinlocks slower.

In this case I'm pretty sure this is also a undetected deadlock, as other
places acquire the buffer header spinlock while holding the buffer partition
lock. You can't just change the nesting in one place, you'd have to change it
everywhere (but don't, I'm quite certain that we're never going to allow
holding spinlocks that long).

I don't really understand the race condition this is trying to address:

> + /* Unlock buffer header after the entry is deleted to avoid a race condition:
> + * If unlocked prior, a concurrent GetVictimBuffer() could insert a new entry
> + * for the same buffer and overwrite the entry slot. Then, the BufTableDelete()
> + * would be unable to find the entry and would corrupt the hashtable. */
> + UnlockBufHdrExt(buf, buf_state,
> + 0,
> + BUF_FLAG_MASK | BUF_USAGECOUNT_MASK,
> + 0);

How could there be a concurrent insertion while the buffer partition lock is
held?

Also, GetVictimBuffer() doesn't insert anything into the buffer mapping table,
it just calls InvalidateVictimBuffer(), which deletes from the buffer mapping
table?

Is the concern that two GetVictimBuffer() calls landing on the same buffer
would be a problem? If so, I don't see the problem, at least one of the
GetVictimBuffer()s would fail due to the refcount in InvalidateVictimBuffer()
being seen as != 1.

> My testing (helper script also attached) indicates that all three standard
> hash table operations (insert, lookup, and delete) generally execute
> significantly faster than the existing PG18 dynahash counterparts:

FWIW, on machines with the necessary hardware support, postgres' instr_time.h
should now be quite fast, it's using rdtsc[p] if available.

Greetings,

Andres Freund