Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1tUzev-004Tld-03 for pgsql-hackers@arkaria.postgresql.org; Tue, 07 Jan 2025 02:49:34 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1tUzeu-00GDIC-CZ for pgsql-hackers@arkaria.postgresql.org; Tue, 07 Jan 2025 02:49:32 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1tUzet-00GDHz-PO for pgsql-hackers@lists.postgresql.org; Tue, 07 Jan 2025 02:49:31 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1tUzen-000GoU-34 for pgsql-hackers@postgresql.org; Tue, 07 Jan 2025 02:49:31 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1736218164; bh=M8kv9euAiy4lrl0YmPHm7WkymotKu7RQ1h65a/PSgIg=; h=From:Message-Id:Subject:Date:In-Reply-To:Cc:To:References:From; b=Avw4Kq0r59jHL6wxVdSXN8PmeQHqyVpu4us8SlmgVfkwCWKMzILndWO8Y9MxX8Agp uMy0VpjK8JWQ42kGr+kSojRw2J7oYKBcYfCrpJiLzZ0UE4hbvrQp45yZHGV6R24rNZ CG/q4X4KOfwMi6SIk4QHd56ogJomH6ReABvUbv3e6uQprpAnYAKNhcBnPRlsPt2PSP ZWUdchjZS+0Y4P9mBT2MuaYBOXtP2f+xJMgKqFRFUCHVufoHU2/GVgmpVGT9VpenGy ng+4PvRUgUCRxtgaY1NKhpYs8IC3QhNsKHxXjrh00nYffcN+PRXDIyyfU6bo1c4KIT rpVD9pmSoCmOw== Received: from smtpclient.apple (broadband-46-242-12-77.ip.moscow.rt.ru [46.242.12.77]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (Client did not present a certificate) (Authenticated sender: y.sokolov@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 723376099F; Tue, 7 Jan 2025 05:49:24 +0300 (MSK) From: =?utf-8?B?0K7RgNC40Lkg0KHQvtC60L7Qu9C+0LI=?= Message-Id: <80DD6982-98E1-45A5-A1D8-0C49965DD45D@postgrespro.ru> Content-Type: multipart/alternative; boundary="Apple-Mail=_ACFC1433-7029-4F32-AD89-34DC73F0D9F4" Mime-Version: 1.0 (Mac OS X Mail 16.0 \(3776.700.51\)) Subject: Re: [RFC] Lock-free XLog Reservation from WAL Date: Tue, 7 Jan 2025 05:49:13 +0300 In-Reply-To: Cc: wenhui qiu , "pgsql-hackers@postgresql.org" To: "Zhou, Zhiguo" References: <421eede5-0ecf-421f-9b56-f05d4f51e099@postgrespro.ru> X-Mailer: Apple Mail (2.3776.700.51) X-KSMG-AntiPhishing: NotDetected, bases: 2025/01/07 01:00:00 X-KSMG-AntiSpam-Interceptor-Info: not scanned X-KSMG-AntiSpam-Status: not scanned, disabled by settings X-KSMG-AntiVirus: Kaspersky Secure Mail Gateway, version 2.1.0.7854, bases: 2025/01/07 00:40:00 #26952653 X-KSMG-AntiVirus-Status: NotDetected, skipped X-KSMG-LinksScanning: not scanned, disabled by settings X-KSMG-Message-Action: skipped X-KSMG-Rule-ID: 1 List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk --Apple-Mail=_ACFC1433-7029-4F32-AD89-34DC73F0D9F4 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset=utf-8 > On 6 Jan 2025, at 09:46, Zhou, Zhiguo wrote: >=20 > Hi Yura and Wenhui, >=20 > Thanks for kindly reviewing this work! >=20 > On 1/3/2025 9:01 PM, wenhui qiu wrote: >> Hi >> Thank you for your path=EF=BC=8CNUM_XLOGINSERT_LOCKS increase to = 128=EF=BC=8CI think it will be challenged=EF=BC=8Cdo we make it guc =EF=BC= =9F >=20 > 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? >=20 >=20 >> On Fri, 3 Jan 2025 at 20:36, Yura Sokolov > = wrote: >> 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). >=20 > 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. >=20 >=20 >> Major issue: >> - `SetPrevRecPtr` and `GetPrevRecPtr` do non-atomic write/read = with on >> platforms where MAXALIGN !=3D 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. >=20 > 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? >=20 >=20 >> Readability issue: >> - It would be good to add `Assert(ptr >=3D 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). >=20 > 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. >=20 >=20 >> 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). >=20 > [1] = https://www.postgresql.org/message-id/2266698.1704854297%40sss.pgh.pa.us Good day, Zhiguo. Here=E2=80=99s my attempt to organise link to previous record without = messing with xlog buffers: - link is stored in lock-free hash table instead. I don=E2=80=99t 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. =E2=80=94=E2=80=94 regards Yura Sokolov aka funny-falcon =EF=BF=BC --Apple-Mail=_ACFC1433-7029-4F32-AD89-34DC73F0D9F4 Content-Type: multipart/mixed; boundary="Apple-Mail=_37A0EC0A-69DF-4012-9A03-449825DB0177" --Apple-Mail=_37A0EC0A-69DF-4012-9A03-449825DB0177 Content-Transfer-Encoding: quoted-printable Content-Type: text/html; charset=utf-8

On 6 Jan = 2025, at 09:46, Zhou, Zhiguo <zhiguo.zhou@intel.com> = wrote:

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=EF=BC=8CNUM_XLOGINSERT_LOCKS increase to 128=EF=BC=8CI think it = will be challenged=EF=BC=8Cdo we make it guc =EF=BC=9F
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 <y.sokolov@postgrespro.ru<<= a = href=3D"mailto:y.sokolov@postgrespro.ru">mailto:y.sokolov@postgrespro.ru>> wrote:
   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).

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:
   - `SetPrevRecPtr` and `GetPrevRecPtr` do = non-atomic write/read with on
   platforms where = MAXALIGN !=3D 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.

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:
   - It would be good to add `Assert(ptr >=3D = 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).

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.


   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).

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

Good day, = Zhiguo.

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

I = don=E2=80=99t 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.

=E2=80=94=E2=80=94
regards
Yura Sokolov aka = funny-falcon
= --Apple-Mail=_37A0EC0A-69DF-4012-9A03-449825DB0177 Content-Disposition: attachment; filename=v1-0001-Lock-free-XLog-Reservation-using-lock-free-hash-t.patch Content-Type: application/octet-stream; x-unix-mode=0644; name="v1-0001-Lock-free-XLog-Reservation-using-lock-free-hash-t.patch" Content-Transfer-Encoding: quoted-printable =46rom=20c41f7b72d57b4fa4211079f7637f0a8470ec9348=20Mon=20Sep=2017=20= 00:00:00=202001=0AFrom:=20= =3D?UTF-8?q?=3DD0=3DAE=3DD1=3D80=3DD0=3DB8=3DD0=3DB9=3D20=3DD0=3DA1=3DD0=3D= BE=3DD0=3DBA=3DD0=3DBE=3DD0=3DBB?=3D=0A=20=3D?UTF-8?q?=3DD0=3DBE=3DD0=3DB2= ?=3D=20=0ADate:=20Mon,=206=20Jan=202025=20= 21:54:06=20+0300=0ASubject:=20[PATCH=20v1]=20Lock-free=20XLog=20= Reservation=20using=20lock-free=20hash-table=0A=0ARemoved=20PrevBytePos=20= to=20eliminate=20lock=20contention,=20allowing=20atomic=20updates=0Ato=20= CurrBytePos.=20Use=20lock-free=20hash-table=20based=20on=204-way=20= Cuckoo=20Hashing=0Ato=20store=20link=20to=20PrevBytePos.=0A---=0A=20= src/backend/access/transam/xlog.c=20|=20346=20= ++++++++++++++++++++++++------=0A=201=20file=20changed,=20285=20= insertions(+),=2061=20deletions(-)=0A=0Adiff=20--git=20= a/src/backend/access/transam/xlog.c=20= b/src/backend/access/transam/xlog.c=0Aindex=20b9ea92a542..2f35e1645a=20= 100644=0A---=20a/src/backend/access/transam/xlog.c=0A+++=20= b/src/backend/access/transam/xlog.c=0A@@=20-68,6=20+68,8=20@@=0A=20= #include=20"catalog/pg_database.h"=0A=20#include=20= "common/controldata_utils.h"=0A=20#include=20"common/file_utils.h"=0A= +#include=20"common/hashfn.h"=0A+#include=20"common/pg_prng.h"=0A=20= #include=20"executor/instrument.h"=0A=20#include=20"miscadmin.h"=0A=20= #include=20"pg_trace.h"=0A@@=20-147,7=20+149,7=20@@=20int=09=09=09= wal_segment_size=20=3D=20DEFAULT_XLOG_SEG_SIZE;=0A=20=20*=20to=20happen=20= concurrently,=20but=20adds=20some=20CPU=20overhead=20to=20flushing=20the=20= WAL,=0A=20=20*=20which=20needs=20to=20iterate=20all=20the=20locks.=0A=20=20= */=0A-#define=20NUM_XLOGINSERT_LOCKS=20=208=0A+#define=20= NUM_XLOGINSERT_LOCKS=20=20128=0A=20=0A=20/*=0A=20=20*=20Max=20distance=20= from=20last=20checkpoint,=20before=20triggering=20a=20new=20xlog-based=0A= @@=20-384,6=20+386,36=20@@=20typedef=20union=20WALInsertLockPadded=0A=20=09= char=09=09pad[PG_CACHE_LINE_SIZE];=0A=20}=20WALInsertLockPadded;=0A=20=0A= +/*=0A+=20*=20It=20links=20current=20position=20with=20previous=20one.=0A= +=20*=20-=20CurrPosId=20is=20(CurrBytePos=20^=20(CurrBytePos>>32))=0A+=20= *=20=20=20Since=20CurrBytePos=20grows=20monotonically=20and=20it=20is=20= aligned=20to=20MAXALIGN,=0A+=20*=20=20=20CurrPosId=20correctly=20= identifies=20CurrBytePos=20for=20at=20least=204*2^32=20=3D=2032GB=20of=0A= +=20*=20=20=20WAL=20logs.=0A+=20*=20-=20PrevSize=20is=20difference=20= between=20CurrBytePos=20and=20PrevBytePos=0A+=20*/=0A+typedef=20struct=0A= +{=0A+=09uint32=09=09CurrPosId;=0A+=09uint32=09=09PrevSize;=0A+}=09=09=09= WALPrevPosLinkVal;=0A+=0A+/*=0A+=20*=20This=20is=20an=20element=20of=20= lock-free=20hash-table.=0A+=20*=20PrevSize's=20lowest=20bit=20is=20used=20= as=20a=20lock,=20relying=20on=20fact=20it=20is=20MAXALIGN-ed.=0A+=20*/=0A= +typedef=20struct=0A+{=0A+=09pg_atomic_uint32=20CurrPosId;=0A+=09= pg_atomic_uint32=20PrevSize;=0A+}=09=09=09WALPrevPosLink;=0A+=0A+#define=20= PREV_LINKS_HASH_CAPA=20256=0A+StaticAssertDecl(!(PREV_LINKS_HASH_CAPA=20= &=20(PREV_LINKS_HASH_CAPA=20-=201)),=0A+=09=09=09=09=20= "PREV_LINKS_HASH_CAPA=20should=20be=20power=20of=20two");=0A+=0A+#define=20= SWAP_ONCE_IN=20128=0A+=0A=20/*=0A=20=20*=20Session=20status=20of=20= running=20backup,=20used=20for=20sanity=20checks=20in=20SQL-callable=0A=20= =20*=20functions=20to=20start=20and=20stop=20backups.=0A@@=20-395,26=20= +427,31=20@@=20static=20SessionBackupState=20sessionBackupState=20=3D=20= SESSION_BACKUP_NONE;=0A=20=20*/=0A=20typedef=20struct=20XLogCtlInsert=0A=20= {=0A-=09slock_t=09=09insertpos_lck;=09/*=20protects=20CurrBytePos=20and=20= PrevBytePos=20*/=0A-=0A=20=09/*=0A=20=09=20*=20CurrBytePos=20is=20the=20= end=20of=20reserved=20WAL.=20The=20next=20record=20will=20be=0A-=09=20*=20= inserted=20at=20that=20position.=20PrevBytePos=20is=20the=20start=20= position=20of=20the=0A-=09=20*=20previously=20inserted=20(or=20rather,=20= reserved)=20record=20-=20it=20is=20copied=20to=20the=0A-=09=20*=20= prev-link=20of=20the=20next=20record.=20These=20are=20stored=20as=20= "usable=20byte=0A-=09=20*=20positions"=20rather=20than=20XLogRecPtrs=20= (see=20XLogBytePosToRecPtr()).=0A+=09=20*=20inserted=20at=20that=20= position.=0A+=09=20*=0A+=09=20*=20The=20start=20position=20of=20the=20= previously=20inserted=20(or=20rather,=20reserved)=0A+=09=20*=20record=20= (it=20is=20copied=20to=20the=20prev-link=20of=20the=20next=20record)=20= will=20be=0A+=09=20*=20stored=20in=20PrevLinksHash.=0A+=09=20*=0A+=09=20= *=20These=20are=20stored=20as=20"usable=20byte=20positions"=20rather=20= than=20XLogRecPtrs=0A+=09=20*=20(see=20XLogBytePosToRecPtr()).=0A=20=09=20= */=0A-=09uint64=09=09CurrBytePos;=0A-=09uint64=09=09PrevBytePos;=0A+=09= pg_atomic_uint64=20CurrBytePos=20= pg_attribute_aligned(PG_CACHE_LINE_SIZE);=0A=20=0A=20=09/*=0A-=09=20*=20= Make=20sure=20the=20above=20heavily-contended=20spinlock=20and=20byte=20= positions=20are=0A-=09=20*=20on=20their=20own=20cache=20line.=20In=20= particular,=20the=20RedoRecPtr=20and=20full=20page=0A-=09=20*=20write=20= variables=20below=20should=20be=20on=20a=20different=20cache=20line.=20= They=20are=0A-=09=20*=20read=20on=20every=20WAL=20insertion,=20but=20= updated=20rarely,=20and=20we=20don't=20want=0A-=09=20*=20those=20reads=20= to=20steal=20the=20cache=20line=20containing=20Curr/PrevBytePos.=0A+=09=20= *=20PrevLinksHash=20is=20a=20lock-free=20hash=20table=20based=20on=20= Cuckoo=20algorith.=20It=20is=0A+=09=20*=20mostly=204=20way:=20for=20= every=20element=20computed=20two=20positions=20h1,=20h2,=20and=0A+=09=20= *=20neighbour=20h1+1=20and=20h2+2=20are=20used=20as=20well.=20This=20way=20= even=20on=20collision=20we=0A+=09=20*=20have=203=20distinct=20position,=20= which=20provide=20us=20~75%=20fill=20rate=20without=0A+=09=20*=20= unsolvable=20cycles=20(due=20to=20Cuckoo's=20theory).=0A+=09=20*=0A+=09=20= *=20Certainly,=20we=20rely=20on=20the=20fact=20we=20will=20delete=20= elements=20with=20same=20speed=0A+=09=20*=20as=20we=20add=20them,=20and=20= even=20unsolvable=20cycles=20will=20be=20destroyed=20soon=20by=0A+=09=20= *=20concurrent=20deletions.=0A=20=09=20*/=0A-=09char=09=09= pad[PG_CACHE_LINE_SIZE];=0A+=09WALPrevPosLink=20= PrevLinksHash[PREV_LINKS_HASH_CAPA];=0A=20=0A=20=09/*=0A=20=09=20*=20= fullPageWrites=20is=20the=20authoritative=20value=20used=20by=20all=20= backends=20to=0A@@=20-700,6=20+737,15=20@@=20static=20void=20= CopyXLogRecordToWAL(int=20write_len,=20bool=20isLogSwitch,=0A=20=09=09=09= =09=09=09=09=09XLogRecData=20*rdata,=0A=20=09=09=09=09=09=09=09=09= XLogRecPtr=20StartPos,=20XLogRecPtr=20EndPos,=0A=20=09=09=09=09=09=09=09=09= TimeLineID=20tli);=0A+=0A+static=20bool=20= WALPrevPosLinkInsert(WALPrevPosLink=20*=20link,=20WALPrevPosLinkVal=20= val);=0A+static=20bool=20WALPrevPosLinkConsume(WALPrevPosLink=20*=20= link,=20WALPrevPosLinkVal=20*=20val);=0A+static=20bool=20= WALPrevPosLinkSwap(WALPrevPosLink=20*=20link,=20WALPrevPosLinkVal=20*=20= val);=0A+static=20void=20LinkAndFindPrevPos(XLogRecPtr=20StartPos,=20= XLogRecPtr=20EndPos,=0A+=09=09=09=09=09=09=09=20=20=20XLogRecPtr=20= *PrevPtr);=0A+static=20void=20LinkStartPrevPos(XLogRecPtr=20EndOfLog,=20= XLogRecPtr=20LastRec);=0A+static=20XLogRecPtr=20= ReadInsertCurrBytePos(void);=0A+=0A=20static=20void=20= ReserveXLogInsertLocation(int=20size,=20XLogRecPtr=20*StartPos,=0A=20=09=09= =09=09=09=09=09=09=09=20=20XLogRecPtr=20*EndPos,=20XLogRecPtr=20= *PrevPtr);=0A=20static=20bool=20ReserveXLogSwitch(XLogRecPtr=20= *StartPos,=20XLogRecPtr=20*EndPos,=0A@@=20-1086,6=20+1132,192=20@@=20= XLogInsertRecord(XLogRecData=20*rdata,=0A=20=09return=20EndPos;=0A=20}=0A= =20=0A+/*=0A+=20*=20Attempt=20to=20write=20into=20empty=20link.=0A+=20*/=0A= +static=20pg_attribute_always_inline=20bool=0A= +WALPrevPosLinkInsert(WALPrevPosLink=20*=20link,=20WALPrevPosLinkVal=20= val)=0A+{=0A+=09uint32=09=09empty=20=3D=200;=0A+=0A+=09/*=20first=20= check=20it=20read-only=20*/=0A+=09if=20= (pg_atomic_read_u32(&link->PrevSize)=20!=3D=200)=0A+=09=09return=20= false;=0A+=09if=20(!pg_atomic_compare_exchange_u32(&link->PrevSize,=20= &empty,=201))=0A+=09=09/*=20someone=20else=20occupied=20the=20entry=20*/=0A= +=09=09return=20false;=0A+=0A+=09pg_atomic_write_u32(&link->CurrPosId,=20= val.CurrPosId);=0A+=09/*=20This=20write=20acts=20as=20unlock=20as=20= well.=20*/=0A+=09pg_atomic_write_membarrier_u32(&link->PrevSize,=20= val.PrevSize);=0A+=09return=20true;=0A+}=0A+=0A+/*=0A+=20*=20Attempt=20= to=20consume=20matched=20link.=0A+=20*/=0A+static=20= pg_attribute_always_inline=20bool=0A= +WALPrevPosLinkConsume(WALPrevPosLink=20*=20link,=20WALPrevPosLinkVal=20= *=20val)=0A+{=0A+=0A+=09if=20(pg_atomic_read_u32(&link->CurrPosId)=20!=3D=20= val->CurrPosId)=0A+=09=09return=20false;=0A+=0A+=09/*=20Try=20lock=20*/=0A= +=09val->PrevSize=20=3D=20pg_atomic_fetch_or_u32(&link->PrevSize,=201);=0A= +=09if=20(val->PrevSize=20&=201)=0A+=09=09/*=20Lock=20failed=20*/=0A+=09=09= return=20false;=0A+=0A+=09if=20(pg_atomic_read_u32(&link->CurrPosId)=20= !=3D=20val->CurrPosId)=0A+=09{=0A+=09=09/*=20unlock=20with=20old=20value=20= */=0A+=09=09pg_atomic_write_u32(&link->PrevSize,=20val->PrevSize);=0A+=09= =09return=20false;=0A+=09}=0A+=0A+=09= pg_atomic_write_u32(&link->CurrPosId,=200);=0A+=09/*=20This=20write=20= acts=20as=20unlock=20as=20well.=20*/=0A+=09= pg_atomic_write_membarrier_u32(&link->PrevSize,=200);=0A+=09return=20= true;=0A+}=0A+=0A+/*=0A+=20*=20Attempt=20to=20swap=20entry:=20remember=20= existing=20link=20and=20write=20our.=0A+=20*=20It=20could=20happen=20we=20= consume=20empty=20entry.=20Caller=20will=20detect=20it=20by=20checking=0A= +=20*=20remembered=20value.=0A+=20*/=0A+static=20= pg_attribute_always_inline=20bool=0A+WALPrevPosLinkSwap(WALPrevPosLink=20= *=20link,=20WALPrevPosLinkVal=20*=20val)=0A+{=0A+=09uint32=09=09oldCur;=0A= +=09uint32=09=09oldPrev;=0A+=0A+=09/*=20Attempt=20to=20lock=20entry=20= against=20concurrent=20consumer=20or=20swapper=20*/=0A+=09oldPrev=20=3D=20= pg_atomic_fetch_or_u32(&link->PrevSize,=201);=0A+=09if=20(oldPrev=20&=20= 1)=0A+=09=09/*=20Lock=20failed=20*/=0A+=09=09return=20false;=0A+=0A+=09= oldCur=20=3D=20pg_atomic_read_u32(&link->CurrPosId);=0A+=09= pg_atomic_write_u32(&link->CurrPosId,=20val->CurrPosId);=0A+=09/*=20This=20= write=20acts=20as=20unlock=20as=20well.=20*/=0A+=09= pg_atomic_write_membarrier_u32(&link->PrevSize,=20val->PrevSize);=0A+=0A= +=09val->CurrPosId=20=3D=20oldCur;=0A+=09val->PrevSize=20=3D=20oldPrev;=0A= +=09return=20true;=0A+}=0A+=0A+static=20pg_attribute_always_inline=20= void=0A+CalcCuckooPositions(uint32=20ptr,=20uint32=20pos[4])=0A+{=0A+=09= uint32=09=09hash=20=3D=20murmurhash32(ptr);=0A+=0A+=09pos[0]=20=3D=20= hash=20%=20PREV_LINKS_HASH_CAPA;=0A+=09pos[1]=20=3D=20(pos[0]=20+=201)=20= %=20PREV_LINKS_HASH_CAPA;=0A+=09pos[2]=20=3D=20(hash=20>>=2016)=20%=20= PREV_LINKS_HASH_CAPA;=0A+=09pos[3]=20=3D=20(pos[2]=20+=202)=20%=20= PREV_LINKS_HASH_CAPA;=0A+}=0A+=0A+/*=0A+=20*=20Write=20new=20link=20= (EndPos,=20StartPos)=20and=20find=20PrevPtr=20for=20StartPos.=0A+=20*=0A= +=20*=20Links=20are=20stored=20in=20lock-free=20Cuckoo=20based=20= hash-table.=0A+=20*=20We=20use=20mostly-4=20way=20Cuckoo=20hashing=20= which=20provides=20high=20fill=20rate=20without=0A+=20*=20hard=20cycle=20= collisions.=20Also=20we=20rely=20on=20concurrent=20consumers=20of=20= existing=0A+=20*=20entry,=20so=20cycles=20will=20be=20broken=20in=20mean=20= time.=0A+=20*=0A+=20*=20Cuckoo=20hashing=20relies=20on=20re-insertion=20= for=20balancing,=20so=20we=20occasionally=0A+=20*=20swaps=20entry=20and=20= try=20to=20insert=20swapped=20instead=20of=20our.=0A+=20*/=0A+static=20= void=0A+LinkAndFindPrevPos(XLogRecPtr=20StartPos,=20XLogRecPtr=20EndPos,=20= XLogRecPtr=20*PrevPtr)=0A+{=0A+=09WALPrevPosLink=20*hashtable=20=3D=20= XLogCtl->Insert.PrevLinksHash;=0A+=09WALPrevPosLinkVal=20lookup=20=3D=20= {=0A+=09=09.CurrPosId=20=3D=20StartPos=20^=20(StartPos=20>>=2032),=0A+=09= };=0A+=09WALPrevPosLinkVal=20insert=20=3D=20{=0A+=09=09.CurrPosId=20=3D=20= EndPos=20^=20(EndPos=20>>=2032),=0A+=09=09.PrevSize=20=3D=20EndPos=20-=20= StartPos=0A+=09};=0A+=09pg_prng_state=20prng;=0A+=09uint32=09=09= lookup_pos[4];=0A+=09uint32=09=09insert_pos[4];=0A+=09uint32=09=09i;=0A+=09= bool=09=09inserted=20=3D=20false;=0A+=09bool=09=09found=20=3D=20false;=0A= +=0A+=09CalcCuckooPositions(lookup.CurrPosId,=20lookup_pos);=0A+=09= CalcCuckooPositions(insert.CurrPosId,=20insert_pos);=0A+=09= pg_prng_seed(&prng,=20StartPos);=0A+=0A+=09while=20(!inserted=20||=20= !found)=0A+=09{=0A+=09=09for=20(i=20=3D=200;=20!found=20&&=20i=20<=204;=20= i++)=0A+=09=09=09found=20=3D=20= WALPrevPosLinkConsume(&hashtable[lookup_pos[i]],=20&lookup);=0A+=0A+=09=09= if=20(inserted)=0A+=09=09=09goto=20next;=0A+=0A+=09=09for=20(i=20=3D=20= 0;=20!inserted=20&&=20i=20<=204;=20i++)=0A+=09=09=09inserted=20=3D=20= WALPrevPosLinkInsert(&hashtable[insert_pos[i]],=20insert);=0A+=0A+=09=09= if=20(inserted)=0A+=09=09=09goto=20next;=0A+=0A+=09=09if=20= (pg_prng_uint32(&prng)=20%=20SWAP_ONCE_IN=20!=3D=200)=0A+=09=09=09goto=20= next;=0A+=0A+=09=09i=20=3D=20pg_prng_uint32(&prng)=20%=204;=0A+=09=09if=20= (!WALPrevPosLinkSwap(&hashtable[insert_pos[i]],=20&insert))=0A+=09=09=09= goto=20next;=0A+=0A+=09=09if=20(insert.PrevSize=20=3D=3D=200)=0A+=09=09=09= /*=20Lucky=20case:=20entry=20become=20empty=20and=20we=20inserted=20into=20= */=0A+=09=09=09inserted=20=3D=20true;=0A+=09=09else=20if=20= (insert.CurrPosId=20=3D=3D=20lookup.CurrPosId)=0A+=09=09{=0A+=09=09=09/*=0A= +=09=09=09=20*=20We=20occasionally=20replaced=20entry=20we=20looked=20= for.=20No=20need=20to=20insert=0A+=09=09=09=20*=20it=20again.=0A+=09=09=09= =20*/=0A+=09=09=09inserted=20=3D=20true;=0A+=09=09=09Assert(!found);=0A+=09= =09=09found=20=3D=20true;=0A+=09=09=09lookup.PrevSize=20=3D=20= insert.PrevSize;=0A+=09=09=09break;=0A+=09=09}=0A+=09=09else=0A+=09=09=09= CalcCuckooPositions(insert.CurrPosId,=20insert_pos);=0A+=0A+next:=0A+=09=09= pg_spin_delay();=0A+=09}=0A+=0A+=09*PrevPtr=20=3D=20StartPos=20-=20= lookup.PrevSize;=0A+}=0A+=0A+static=20pg_attribute_always_inline=20void=0A= +LinkStartPrevPos(XLogRecPtr=20EndOfLog,=20XLogRecPtr=20LastRec)=0A+{=0A= +=09WALPrevPosLink=20*hashtable=20=3D=20XLogCtl->Insert.PrevLinksHash;=0A= +=09uint32=09=09insert_pos[4];=0A+=0A+=09CalcCuckooPositions(EndOfLog=20= ^=20(EndOfLog=20>>=2032),=20insert_pos);=0A+=09= pg_atomic_write_u32(&hashtable[insert_pos[0]].CurrPosId,=0A+=09=09=09=09=09= =09EndOfLog=20^=20(EndOfLog=20>>=2032));=0A+=09= pg_atomic_write_u32(&hashtable[insert_pos[0]].PrevSize,=0A+=09=09=09=09=09= =09EndOfLog=20-=20LastRec);=0A+}=0A+=0A+static=20= pg_attribute_always_inline=20XLogRecPtr=0A+ReadInsertCurrBytePos(void)=0A= +{=0A+=09return=20pg_atomic_read_u64(&XLogCtl->Insert.CurrBytePos);=0A+}=0A= +=0A=20/*=0A=20=20*=20Reserves=20the=20right=20amount=20of=20space=20for=20= a=20record=20of=20given=20size=20from=20the=20WAL.=0A=20=20*=20*StartPos=20= is=20set=20to=20the=20beginning=20of=20the=20reserved=20section,=20= *EndPos=20to=0A@@=20-1118,25=20+1350,9=20@@=20= ReserveXLogInsertLocation(int=20size,=20XLogRecPtr=20*StartPos,=20= XLogRecPtr=20*EndPos,=0A=20=09/*=20All=20(non=20xlog-switch)=20records=20= should=20contain=20data.=20*/=0A=20=09Assert(size=20>=20= SizeOfXLogRecord);=0A=20=0A-=09/*=0A-=09=20*=20The=20duration=20the=20= spinlock=20needs=20to=20be=20held=20is=20minimized=20by=20minimizing=0A-=09= =20*=20the=20calculations=20that=20have=20to=20be=20done=20while=20= holding=20the=20lock.=20The=0A-=09=20*=20current=20tip=20of=20reserved=20= WAL=20is=20kept=20in=20CurrBytePos,=20as=20a=20byte=20position=0A-=09=20= *=20that=20only=20counts=20"usable"=20bytes=20in=20WAL,=20that=20is,=20= it=20excludes=20all=20WAL=0A-=09=20*=20page=20headers.=20The=20mapping=20= between=20"usable"=20byte=20positions=20and=20physical=0A-=09=20*=20= positions=20(XLogRecPtrs)=20can=20be=20done=20outside=20the=20locked=20= region,=20and=0A-=09=20*=20because=20the=20usable=20byte=20position=20= doesn't=20include=20any=20headers,=20reserving=0A-=09=20*=20X=20bytes=20= from=20WAL=20is=20almost=20as=20simple=20as=20"CurrBytePos=20+=3D=20X".=0A= -=09=20*/=0A-=09SpinLockAcquire(&Insert->insertpos_lck);=0A-=0A-=09= startbytepos=20=3D=20Insert->CurrBytePos;=0A+=09startbytepos=20=3D=20= pg_atomic_fetch_add_u64(&Insert->CurrBytePos,=20size);=0A=20=09= endbytepos=20=3D=20startbytepos=20+=20size;=0A-=09prevbytepos=20=3D=20= Insert->PrevBytePos;=0A-=09Insert->CurrBytePos=20=3D=20endbytepos;=0A-=09= Insert->PrevBytePos=20=3D=20startbytepos;=0A-=0A-=09= SpinLockRelease(&Insert->insertpos_lck);=0A+=09= LinkAndFindPrevPos(startbytepos,=20endbytepos,=20&prevbytepos);=0A=20=0A=20= =09*StartPos=20=3D=20XLogBytePosToRecPtr(startbytepos);=0A=20=09*EndPos=20= =3D=20XLogBytePosToEndRecPtr(endbytepos);=0A@@=20-1172,26=20+1388,24=20= @@=20ReserveXLogSwitch(XLogRecPtr=20*StartPos,=20XLogRecPtr=20*EndPos,=20= XLogRecPtr=20*PrevPtr)=0A=20=09uint32=09=09segleft;=0A=20=0A=20=09/*=0A-=09= =20*=20These=20calculations=20are=20a=20bit=20heavy-weight=20to=20be=20= done=20while=20holding=20a=0A-=09=20*=20spinlock,=20but=20since=20we're=20= holding=20all=20the=20WAL=20insertion=20locks,=20there=0A-=09=20*=20are=20= no=20other=20inserters=20competing=20for=20it.=20GetXLogInsertRecPtr()=20= does=0A-=09=20*=20compete=20for=20it,=20but=20that's=20not=20called=20= very=20frequently.=0A+=09=20*=20Currently=20ReserveXLogInsertLocation=20= is=20protected=20with=20exclusive=0A+=09=20*=20insertion=20lock,=20so=20= there=20is=20no=20contention=20against=20CurrBytePos,=20But=20we=0A+=09=20= *=20still=20do=20CAS=20loop=20for=20being=20uniform.=0A+=09=20*=0A+=09=20= *=20Probably=20we'll=20get=20rid=20of=20exclusive=20lock=20in=20a=20= future.=0A=20=09=20*/=0A-=09SpinLockAcquire(&Insert->insertpos_lck);=0A=20= =0A-=09startbytepos=20=3D=20Insert->CurrBytePos;=0A+repeat:=0A+=09= startbytepos=20=3D=20pg_atomic_read_u64(&Insert->CurrBytePos);=0A=20=0A=20= =09ptr=20=3D=20XLogBytePosToEndRecPtr(startbytepos);=0A=20=09if=20= (XLogSegmentOffset(ptr,=20wal_segment_size)=20=3D=3D=200)=0A=20=09{=0A-=09= =09SpinLockRelease(&Insert->insertpos_lck);=0A=20=09=09*EndPos=20=3D=20= *StartPos=20=3D=20ptr;=0A=20=09=09return=20false;=0A=20=09}=0A=20=0A=20=09= endbytepos=20=3D=20startbytepos=20+=20size;=0A-=09prevbytepos=20=3D=20= Insert->PrevBytePos;=0A-=0A=20=09*StartPos=20=3D=20= XLogBytePosToRecPtr(startbytepos);=0A=20=09*EndPos=20=3D=20= XLogBytePosToEndRecPtr(endbytepos);=0A=20=0A@@=20-1202,10=20+1416,19=20= @@=20ReserveXLogSwitch(XLogRecPtr=20*StartPos,=20XLogRecPtr=20*EndPos,=20= XLogRecPtr=20*PrevPtr)=0A=20=09=09*EndPos=20+=3D=20segleft;=0A=20=09=09= endbytepos=20=3D=20XLogRecPtrToBytePos(*EndPos);=0A=20=09}=0A-=09= Insert->CurrBytePos=20=3D=20endbytepos;=0A-=09Insert->PrevBytePos=20=3D=20= startbytepos;=0A=20=0A-=09SpinLockRelease(&Insert->insertpos_lck);=0A+=09= if=20(!pg_atomic_compare_exchange_u64(&Insert->CurrBytePos,=0A+=09=09=09=09= =09=09=09=09=09=09&startbytepos,=0A+=09=09=09=09=09=09=09=09=09=09= endbytepos))=0A+=09{=0A+=09=09/*=0A+=09=09=20*=20Don't=20use=20spin=20= delay=20here:=20perform_spin_delay=20primary=20case=20is=20for=0A+=09=09=20= *=20solving=20single=20core=20contention.=20But=20on=20single=20core=20= we=20will=20succeed=0A+=09=09=20*=20on=20the=20next=20attempt.=0A+=09=09=20= */=0A+=09=09goto=20repeat;=0A+=09}=0A+=09= LinkAndFindPrevPos(startbytepos,=20endbytepos,=20&prevbytepos);=0A=20=0A=20= =09*PrevPtr=20=3D=20XLogBytePosToRecPtr(prevbytepos);=0A=20=0A@@=20= -1507,7=20+1730,6=20@@=20WaitXLogInsertionsToFinish(XLogRecPtr=20upto)=0A= =20=09XLogRecPtr=09inserted;=0A=20=09XLogRecPtr=09reservedUpto;=0A=20=09= XLogRecPtr=09finishedUpto;=0A-=09XLogCtlInsert=20*Insert=20=3D=20= &XLogCtl->Insert;=0A=20=09int=09=09=09i;=0A=20=0A=20=09if=20(MyProc=20=3D=3D= =20NULL)=0A@@=20-1522,9=20+1744,7=20@@=20= WaitXLogInsertionsToFinish(XLogRecPtr=20upto)=0A=20=09=09return=20= inserted;=0A=20=0A=20=09/*=20Read=20the=20current=20insert=20position=20= */=0A-=09SpinLockAcquire(&Insert->insertpos_lck);=0A-=09bytepos=20=3D=20= Insert->CurrBytePos;=0A-=09SpinLockRelease(&Insert->insertpos_lck);=0A+=09= bytepos=20=3D=20ReadInsertCurrBytePos();=0A=20=09reservedUpto=20=3D=20= XLogBytePosToEndRecPtr(bytepos);=0A=20=0A=20=09/*=0A@@=20-5017,12=20= +5237,18=20@@=20XLOGShmemInit(void)=0A=20=09= XLogCtl->InstallXLogFileSegmentActive=20=3D=20false;=0A=20=09= XLogCtl->WalWriterSleeping=20=3D=20false;=0A=20=0A-=09= SpinLockInit(&XLogCtl->Insert.insertpos_lck);=0A=20=09= SpinLockInit(&XLogCtl->info_lck);=0A+=09= pg_atomic_init_u64(&XLogCtl->Insert.CurrBytePos,=200);=0A=20=09= pg_atomic_init_u64(&XLogCtl->logInsertResult,=20InvalidXLogRecPtr);=0A=20= =09pg_atomic_init_u64(&XLogCtl->logWriteResult,=20InvalidXLogRecPtr);=0A=20= =09pg_atomic_init_u64(&XLogCtl->logFlushResult,=20InvalidXLogRecPtr);=0A=20= =09pg_atomic_init_u64(&XLogCtl->unloggedLSN,=20InvalidXLogRecPtr);=0A+=0A= +=09for=20(i=20=3D=200;=20i=20<=20PREV_LINKS_HASH_CAPA;=20i++)=0A+=09{=0A= +=09=09pg_atomic_init_u32(&XLogCtl->Insert.PrevLinksHash[i].CurrPosId,=20= 0);=0A+=09=09= pg_atomic_init_u32(&XLogCtl->Insert.PrevLinksHash[i].PrevSize,=200);=0A+=09= }=0A=20}=0A=20=0A=20/*=0A@@=20-6018,8=20+6244,13=20@@=20= StartupXLOG(void)=0A=20=09=20*=20previous=20incarnation.=0A=20=09=20*/=0A= =20=09Insert=20=3D=20&XLogCtl->Insert;=0A-=09Insert->PrevBytePos=20=3D=20= XLogRecPtrToBytePos(endOfRecoveryInfo->lastRec);=0A-=09= Insert->CurrBytePos=20=3D=20XLogRecPtrToBytePos(EndOfLog);=0A+=09{=0A+=09= =09XLogRecPtr=09endOfLog=20=3D=20XLogRecPtrToBytePos(EndOfLog);=0A+=09=09= XLogRecPtr=09lastRec=20=3D=20= XLogRecPtrToBytePos(endOfRecoveryInfo->lastRec);=0A+=0A+=09=09= pg_atomic_write_u64(&Insert->CurrBytePos,=20endOfLog);=0A+=09=09= LinkStartPrevPos(endOfLog,=20lastRec);=0A+=09}=0A=20=0A=20=09/*=0A=20=09=20= *=20Tricky=20point=20here:=20lastPage=20contains=20the=20*last*=20block=20= that=20the=20LastRec=0A@@=20-7005,7=20+7236,7=20@@=20= CreateCheckPoint(int=20flags)=0A=20=0A=20=09if=20(shutdown)=0A=20=09{=0A= -=09=09XLogRecPtr=09curInsert=20=3D=20= XLogBytePosToRecPtr(Insert->CurrBytePos);=0A+=09=09XLogRecPtr=09= curInsert=20=3D=20XLogBytePosToRecPtr(ReadInsertCurrBytePos());=0A=20=0A=20= =09=09/*=0A=20=09=09=20*=20Compute=20new=20REDO=20record=20ptr=20=3D=20= location=20of=20next=20XLOG=20record.=0A@@=20-9434,14=20+9665,7=20@@=20= register_persistent_abort_backup_handler(void)=0A=20XLogRecPtr=0A=20= GetXLogInsertRecPtr(void)=0A=20{=0A-=09XLogCtlInsert=20*Insert=20=3D=20= &XLogCtl->Insert;=0A-=09uint64=09=09current_bytepos;=0A-=0A-=09= SpinLockAcquire(&Insert->insertpos_lck);=0A-=09current_bytepos=20=3D=20= Insert->CurrBytePos;=0A-=09SpinLockRelease(&Insert->insertpos_lck);=0A-=0A= -=09return=20XLogBytePosToRecPtr(current_bytepos);=0A+=09return=20= XLogBytePosToRecPtr(ReadInsertCurrBytePos());=0A=20}=0A=20=0A=20/*=0A--=20= =0A2.39.3=20(Apple=20Git-146)=0A=0A= --Apple-Mail=_37A0EC0A-69DF-4012-9A03-449825DB0177 Content-Transfer-Encoding: 7bit Content-Type: text/html; charset=us-ascii
--Apple-Mail=_37A0EC0A-69DF-4012-9A03-449825DB0177-- --Apple-Mail=_ACFC1433-7029-4F32-AD89-34DC73F0D9F4--