Re: Restructured Shared Buffer Hash Table - Mailing list pgsql-hackers
| From | Alexandre Felipe |
|---|---|
| Subject | Re: Restructured Shared Buffer Hash Table |
| Date | |
| Msg-id | CAE8JnxOcd+J0A8iM=BwwhovXoih5AOtvUcxPRbqgtn9CNAjPXQ@mail.gmail.com Whole thread |
| In response to | Re: Restructured Shared Buffer Hash Table (Alexandre Felipe <o.alexandre.felipe@gmail.com>) |
| List | pgsql-hackers |
I am withdrawing my attempt on lock-free buffer mapping.
And I will try to address some of Andres questions.
And I will try to address some of Andres questions.
On Tue, Aug 11, 2026 at 9:50 PM Andres Freund <andres@anarazel.de> wrote:
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.
Using pointers makes it easier to move a buffer from one bucket to another.
Having P partitions and N buffers, and no dynamic allocation we would need
to allocate N * P entries, because all the buffers can be mapped into one partition.
Additionally, I would expect the memory copy to have a noticeable impact.
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.
In the current implementation that is a modest gain. And that agrees with theory
If num_buckets = NBuffers, about (1 - 1/e) of the buckets are
is expected to 63%, without hashcode we can expect
5*0.63 + 10*(1 - 0.63) = 6.85 comparisons per entry
with hashcode 6 * 0.63 + 7 * (1 - 0.63) = 6.37 comparisons
lower occupation ratios favours noo hashcode.
On a different implementation where one would read the tag from the
buffer descriptor instead of storing in the buffer mapping, this hash code would
make more difference.
Additionally, one could store a different hashcode, not the one used to map
on the buckets, because at NBuffers = INT_MAX/2-1, the using the same
32-bit hash code leads to 25% false matches.
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
A solution for this would be having an additional Map<Relation, List<Buffer> >
To be conservative the same number of buckets as BufTable
Storage: ~16 bytes per buffer
Insert: 1 hash lookup, 1 list insertion.
Lookup: unchanged
Deletion: 1 list removal (two pointer dereferences, and two pointer updates)
2) I think any buffer mapping lookup datastructure with 20 byte keys is going
to considerably not great for performance.
Will we relax the limits, it was proposed to reduce the number of databases.
I think we could reduce the number of tablespaces instead, I think that its
limit is not documented. What I like about 16 is that it could be copied and
compared as 2 x 64-bit, or a single simd vector.
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.
This is an upgrade from 1, ordered data structures are very powerful, a red-black
three in javascript works beautifully, but in C the cost of the pointer lookups is
huge. In postgres world probably one would want an in-memory B-tree (as everyone
is familiar with that algorithm). Probably pages aligned to cache lines
(currently declared as 128 bytes), reserving a few bytes for prev, parent, next, and count
we would end up with 28 block numbers per page. Maybe one could use a
special encoding for N..N+k, but I don't have any good insight on how to do that on fixed
32-bit entries.
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
You might be interested in [1]
This is unfortunate. Initially I saw this as a reason for the linked lists bucket.
I tried a custom design, then I tried to go by the book with a Harris wait-free
design. The problem is that under buffer reuse and a backend that can sleep
an arbitrarily long while walking the chain. If while one backend holds a given
buffer, that buffer can be removed and then inserted again, in the same bucket
with a larger hash code, ending up after of some buffer that were initially after
it, e.g. if a bucket has a, -b-, c, d, and while a backend walks that list on b, that
gets deleted and reinserted after c changes to a, c, -b-, d, the backend holding
-b- doesn't notice that it was deleted.
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.
How common? How much do you think is there to gain?
Once 3 is implemented this might be doable.
I have seen a lot in this list, when a new idea is proposed, someone will have
questions about the worst case scenario. And if we apply that to this feature
I think it is very hard to beat Dhruv's implementation.
The lion share of the gain comes from not using dynhash.
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.
Below relation?
We would have to assign a global identifier to the relation, across all backends.
So I think that is another hashmap
At a given moment we can have one buffer of each relation, so the lookup
of one single relation would be as complex as the buffer lookup today.
When scanning many buffers of one relation this could help. For one single
buffer it would be about twice as slow.
(there's plenty complexity here, don't get me wrong)
Exactly
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).
OK, a radix tree with blocks of size 16 would have deepth 8, and if it is sparse
would require ~16x more memory. It might be a win for long sequential scans,
but would be much slower for random access (as mentioned before the hash
table does about 1.6 sequential pointer dereference on average, a 8GB table here
would do 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 missed this suggestion when I tried to do my lock-free implementation.
One thing here is that it would drop the entry[id] => buffer[id] invariant,
but if we can do it lock-free that is totally worth it.
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...
Dhruv's patch is trivial, and gives a noticeable improvement compared to the previous
dynhash based algorithm algorithm. The only potential downside is requiring two
relatively large contiguous blocks of shared memory, one of 24GB and one of 4GB.
Buffer descriptors already allocate a 64GB continuous block at the shared_buffers
GUC limit.
Attachment
pgsql-hackers by date: