I am withdrawing my attempt on lock-free buffer mapping. And I will try to address some of Andres questions.
On Tue, Aug 11, 2026 at 9:50 PM Andres Freund <[email protected]> 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. [1] https://www.postgresql.org/message-id/flat/cae8jnxogu4pt19z6jrvw9w0ins1cxt_prppcn0dadtueo_g...@mail.gmail.com
v6-0001-Inline-SharedBufHash.patch
Description: Binary data
