Subject: Re: [RFC] Lock-free XLog Reservation from WAL

From: wenhui qiu <[email-masked]>
Date: Fri, 3 Jan 2025 21:01:30 +0800

Hi
    Thank you for your path，NUM_XLOGINSERT_LOCKS increase to 128，I think it
will be challenged，do we make it guc ？

On Fri, 3 Jan 2025 at 20:36, Yura Sokolov <[email-masked]> wrote:

> 02.01.2025 10:05, Zhou, Zhiguo wrote:
> > Hi all,
> >
> > I am reaching out to solicit your insights and comments on a recent
> proposal regarding the "Lock-free XLog Reservation from WAL." We have
> identified some challenges with the current WAL insertions, which require
> space reservations in the WAL buffer which involve updating two
> shared-memory statuses in XLogCtlInsert: CurrBytePos (the start position of
> the current XLog) and PrevBytePos (the prev-link to the previous XLog).
> Currently, the use of XLogCtlInsert.insertpos_lck ensures consistency but
> introduces lock contention, hindering the parallelism of XLog insertions.
> >
> > To address this issue, we propose the following changes:
> >
> > 1. Removal of PrevBytePos: This will allow increments of the CurrBytePos
> (a single uint64 field) to be implemented with an atomic operation
> (fetch_add).
> > 2. Updating Prev-Link of next XLog: Based on the fact that the prev-link
> of the next XLog always points to the head of the current Xlog,we will
> slightly exceed the reserved memory range of the current XLog to update the
> prev-link of the next XLog, regardless of which backend acquires the next
> memory space. The next XLog inserter will wait until its prev-link is
> updated for CRC calculation before starting its own XLog copy into the WAL.
> > 3. Breaking Sequential Write Convention: Each backend will update the
> prev-link of its next XLog first, then return to the header position for
> the current log insertion. This change will reduce the dependency of XLog
> writes on previous ones (compared with the sequential writes).
> > 4. Revised GetXLogBuffer: To support #3, we need update this function to
> separate the LSN it intends to access from the LSN it expects to update in
> the insertingAt field.
> > 5. Increase NUM_XLOGINSERT_LOCKS: With the above changes, increasing
> NUM_XLOGINSERT_LOCKS, for example to 128, could effectively enhance the
> parallelism.
> >
> > The attached patch could pass the regression tests (make check, make
> check-world), and in the performance test of this POC on SPR (480 vCPU)
> shows that this optimization could help the TPCC benchmark better scale
> with the core count and as a result the performance with full cores enabled
> could be improved by 2.04x.
> >
> > Before we proceed with further patch validation and refinement work, we
> are eager to hear the community's thoughts and comments on this
> optimization so that we can confirm our current work aligns with
> expectations.
>
> Good day, Zhiguo.
>
> Idea looks great.
>
> Minor issue:
> - you didn't remove use of `insertpos_lck` from `ReserveXLogSwitch`.
>
> I initially thought it became un-synchronized against
> `ReserveXLogInsertLocation`, but looking closer I found it is
> synchronized with `WALInsertLockAcquireExclusive`.
> Since there are no other `insertpos_lck` usages after your patch, I
> don't see why it should exists and be used in `ReserveXLogSwitch`.
>
> Still I'd prefer to see CAS loop in this place to be consistent with
> other non-locking access. And it will allow to get rid of
> `WALInsertLockAcquireExclusive`, (though probably it is not a big issue).
>
> Major issue:
> - `SetPrevRecPtr` and `GetPrevRecPtr` do non-atomic write/read with on
> platforms where MAXALIGN != 8 or without native 64 load/store. Branch
> with 'memcpy` is rather obvious, but even pointer de-referencing on
> "lucky case" is not safe either.
>
> I have no idea how to fix it at the moment.
>
> Readability issue:
> - It would be good to add `Assert(ptr >= upto)` into `GetXLogBuffer`.
> I had hard time to recognize `upto` is strictly not in the future.
> - Certainly, final version have to have fixed and improved comments.
> Many patch's ideas are strictly non-obvious. I had hard time to
> recognize patch is not a piece of ... (excuse me for the swear sentence).
>
> Indeed, patch is much better than it looks on first sight.
> I came with alternative idea yesterday, but looking closer to your patch
> today I see it is superior to mine (if atomic access will be fixed).
>
> ----
>
> regards,
> Yura Sokolov aka funny-falcon
>
>
>

---

From: "Zhou, Zhiguo" <[email-masked]>
Date: Mon, 6 Jan 2025 14:46:03 +0800

Hi Yura and Wenhui,

Thanks for kindly reviewing this work!

On 1/3/2025 9:01 PM, wenhui qiu wrote:
> Hi
>      Thank you for your path，NUM_XLOGINSERT_LOCKS increase to 128，I 
> think it will be challenged，do we make it guc ？
> 

I noticed there have been some discussions (for example, [1] and its 
responses) about making NUM_XLOGINSERT_LOCKS a GUC, which seems to be a 
controversial proposal. Given that, we may first focus on the lock-free 
XLog reservation implementation, and leave the increase of 
NUM_XLOGINSERT_LOCKS for a future patch, where we would provide more 
quantitative evidence for the various implementations. WDYT?

> On Fri, 3 Jan 2025 at 20:36, Yura Sokolov <[email-masked] 
> <mailto:[email-masked]>> wrote:
> 
>     Good day, Zhiguo.
> 
>     Idea looks great.
> 
>     Minor issue:

Exactly, it should be safe to remove `insertpos_lck`. And I agree with 
you on getting rid of `WALInsertLockAcquireExclusive` with CAS loop 
which should significantly reduce the synchronization cost here 
especially when we intend to increase NUM_XLOGINSERT_LOCKS. I will try 
it in the next version of patch.

>     I have no idea how to fix it at the moment.

Indeed, non-atomic write/read operations can lead to safety issues in 
some situations. My initial thought is to define a bit near the 
prev-link to flag the completion of the update. In this way, we could 
allow non-atomic or even discontinuous write/read operations on the 
prev-link, while simultaneously guaranteeing its atomicity through 
atomic operations (as well as memory barriers) on the flag bit. What do 
you think of this as a viable solution?

>     recognize patch is not a piece of ... (excuse me for the swear

Thanks for the suggestion and patience. It's really more readable after 
inserting the assertion, I will fix it and improve other comments in the 
following patches.

>     Yura Sokolov aka funny-falcon

Regards,
Zhiguo

[1] https://www.postgresql.org/message-id/2266698.1704854297%40sss.pgh.pa.us

---

From: wenhui qiu <[email-masked]>
Date: Mon, 6 Jan 2025 16:35:31 +0800

HI Zhiguo
    Thank you for your reply ,Then you'll have to prove that 128 is the
optimal value, otherwise they'll have a hard time agreeing with you on this
patch.

Thanks

On Mon, Jan 6, 2025 at 2:46 PM Zhou, Zhiguo <[email-masked]> wrote:

> [1]
> https://www.postgresql.org/message-id/2266698.1704854297%40sss.pgh.pa.us
>
>

---

From: Юрий Соколов <[email-masked]>
Date: Tue, 7 Jan 2025 05:49:13 +0300

> On 6 Jan 2025, at 09:46, Zhou, Zhiguo <[email-masked]> wrote:
> 
> Hi Yura and Wenhui,
> 
>>     Thank you for your path，NUM_XLOGINSERT_LOCKS increase to 128，I think it will be challenged，do we make it guc ？
> 
> I noticed there have been some discussions (for example, [1] and its responses) about making NUM_XLOGINSERT_LOCKS a GUC, which seems to be a controversial proposal. Given that, we may first focus on the lock-free XLog reservation implementation, and leave the increase of NUM_XLOGINSERT_LOCKS for a future patch, where we would provide more quantitative evidence for the various implementations. WDYT?
> 
> 
>> On Fri, 3 Jan 2025 at 20:36, Yura Sokolov <[email-masked] <mailto:[email-masked]><mailto:[email-masked]>> wrote:
>>    Good day, Zhiguo.
>>    Idea looks great.
>>    Minor issue:
> Exactly, it should be safe to remove `insertpos_lck`. And I agree with you on getting rid of `WALInsertLockAcquireExclusive` with CAS loop which should significantly reduce the synchronization cost here especially when we intend to increase NUM_XLOGINSERT_LOCKS. I will try it in the next version of patch.
> 
> 
>>    Major issue:
> Indeed, non-atomic write/read operations can lead to safety issues in some situations. My initial thought is to define a bit near the prev-link to flag the completion of the update. In this way, we could allow non-atomic or even discontinuous write/read operations on the prev-link, while simultaneously guaranteeing its atomicity through atomic operations (as well as memory barriers) on the flag bit. What do you think of this as a viable solution?
> 
> 
>>    Readability issue:
> Thanks for the suggestion and patience. It's really more readable after inserting the assertion, I will fix it and improve other comments in the following patches.
> 
> 

Good day, Zhiguo.

Here’s my attempt to organise link to previous record without messing with xlog buffers:
- link is stored in lock-free hash table instead.

I don’t claim it is any better than using xlog buffers.
It is just alternative vision.

Some tricks in implementation:
- Relying on byte-position nature, it could be converted to 32 bit unique
  value with `(uint32)(pos ^ (pos>>32))`. Certainly it is not totally unique,
  but it is certainly unique among 32GB consecutive log.
- PrevBytePos could be calculated as a difference between positions, and
  this difference is certainly less than 4GB, so it also could be stored as 32
  bit value (PrevSize).
- Since xlog records are aligned we could use lowest bit of PrevSize as a lock.
- While Cuckoo Hashing could suffer from un-solvable cycle conflicts, this implementation relies on concurrent deleters which will eventually break such cycles if any.

I have a version without 32bit conversion trick, and it is a bit lighter on atomic instructions count, but it performs badly in absence of native 64bit atomics.

——
regards
￼

---

From: "Zhou, Zhiguo" <[email-masked]>
Date: Fri, 10 Jan 2025 00:03:46 +0800

On 1/7/2025 10:49 AM, Юрий Соколов wrote:
>> responses) about making NUM_XLOGINSERT_LOCKS a GUC, which seems to be 
>> a controversial proposal. Given that, we may first focus on the lock- 
>> free XLog reservation implementation, and leave the increase of 
>>> <mailto:[email-masked]><mailto:[email-masked] 
>>> <mailto:[email-masked]>>> wrote:
>>>    Good day, Zhiguo.
>>>    Idea looks great.
>>>    Minor issue:
>> some situations. My initial thought is to define a bit near the prev- 
>> link to flag the completion of the update. In this way, we could allow 
>> non-atomic or even discontinuous write/read operations on the prev- 
>> link, while simultaneously guaranteeing its atomicity through atomic 
>> operations (as well as memory barriers) on the flag bit. What do you 
>> think of this as a viable solution?
>>
>>
>>>    Readability issue:
>> Thanks for the suggestion and patience. It's really more readable 
>> after inserting the assertion, I will fix it and improve other 
>> comments in the following patches.
>>
>>
>> [1]https://www.postgresql.org/message- 
>> id/2266698.1704854297%40sss.pgh.pa.us <https://www.postgresql.org/ 
>> message-id/2266698.1704854297%40sss.pgh.pa.us>
> 
> Good day, Zhiguo.
> 
> - While Cuckoo Hashing could suffer from un-solvable cycle conflicts, 
> this implementation relies on concurrent deleters which will eventually 
> break such cycles if any.
> 
> I have a version without 32bit conversion trick, and it is a bit lighter 
> on atomic instructions count, but it performs badly in absence of native 
> 64bit atomics.
> 
> ——
> regards

Good day, Yura!

Your implementation based on the lock-free hash table is truly 
impressive! One of the aspects I particularly admire is how your 
solution doesn't require breaking the current convention of XLog 
insertion, whose revision is quite error-prone and ungraceful. My minor 
concern is that the limited number of entries (256) in the hash table 
would be a bottleneck for parallel memory reservation, but I believe 
this is not a critical issue.

I will soon try to evaluate the performance impact of your patch on my 
device with the TPCC benchmark and also profile it to see if there are 
any changes that could be made to further improve it.

BTW, do you have a plan to merge this patch to the master branch? Thanks!

Regards,
Zhiguo