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
