Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita4adc31

Browse files
committed
lwlock: Fix quadratic behavior with very long wait lists
Until now LWLockDequeueSelf() sequentially searched the list of waiters to seeif the current proc is still is on the list of waiters, or has already beenremoved. In extreme workloads, where the wait lists are very long, this leadsto a quadratic behavior. #backends iterating over a list #backendslong. Additionally, the likelihood of needing to call LWLockDequeueSelf() inthe first place also increases with the increased length of the wait queue, asit becomes more likely that a lock is released while waiting for the wait listlock, which is held for longer during lock release.Due to the exponential back-off in perform_spin_delay() this is surprisinglyhard to detect. We should make that easier, e.g. by adding a wait event aroundthe pg_usleep() - but that's a separate patch.The fix is simple - track whether a proc is currently waiting in the wait listor already removed but waiting to be woken up in PGPROC->lwWaiting.In some workloads with a lot of clients contending for a small number oflwlocks (e.g. WALWriteLock), the fix can substantially increase throughput.As the quadratic behavior arguably is a bug, we might want to decide tobackpatch this fix in the future.Author: Andres Freund <andres@anarazel.de>Reviewed-by: Bharath Rupireddy <bharath.rupireddyforpostgres@gmail.com>Discussion:https://postgr.es/m/20221027165914.2hofzp4cvutj6gin@awork3.anarazel.deDiscussion:https://postgr.es/m/CALj2ACXktNbG=K8Xi7PSqbofTZozavhaxjatVc14iYaLu4Maag@mail.gmail.com
1 parent061bf98 commita4adc31

File tree

5 files changed

+42
-27
lines changed

5 files changed

+42
-27
lines changed

‎src/backend/access/transam/twophase.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -485,7 +485,7 @@ MarkAsPreparingGuts(GlobalTransaction gxact, TransactionId xid, const char *gid,
485485
proc->roleId=owner;
486486
proc->tempNamespaceId=InvalidOid;
487487
proc->isBackgroundWorker= false;
488-
proc->lwWaiting=false;
488+
proc->lwWaiting=LW_WS_NOT_WAITING;
489489
proc->lwWaitMode=0;
490490
proc->waitLock=NULL;
491491
proc->waitProcLock=NULL;

‎src/backend/storage/lmgr/lwlock.c

Lines changed: 30 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -982,6 +982,15 @@ LWLockWakeup(LWLock *lock)
982982
wokeup_somebody= true;
983983
}
984984

985+
/*
986+
* Signal that the process isn't on the wait list anymore. This allows
987+
* LWLockDequeueSelf() to remove itself of the waitlist with a
988+
* proclist_delete(), rather than having to check if it has been
989+
* removed from the list.
990+
*/
991+
Assert(waiter->lwWaiting==LW_WS_WAITING);
992+
waiter->lwWaiting=LW_WS_PENDING_WAKEUP;
993+
985994
/*
986995
* Once we've woken up an exclusive lock, there's no point in waking
987996
* up anybody else.
@@ -1039,7 +1048,7 @@ LWLockWakeup(LWLock *lock)
10391048
* another lock.
10401049
*/
10411050
pg_write_barrier();
1042-
waiter->lwWaiting=false;
1051+
waiter->lwWaiting=LW_WS_NOT_WAITING;
10431052
PGSemaphoreUnlock(waiter->sem);
10441053
}
10451054
}
@@ -1060,15 +1069,15 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
10601069
if (MyProc==NULL)
10611070
elog(PANIC,"cannot wait without a PGPROC structure");
10621071

1063-
if (MyProc->lwWaiting)
1072+
if (MyProc->lwWaiting!=LW_WS_NOT_WAITING)
10641073
elog(PANIC,"queueing for lock while waiting on another one");
10651074

10661075
LWLockWaitListLock(lock);
10671076

10681077
/* setting the flag is protected by the spinlock */
10691078
pg_atomic_fetch_or_u32(&lock->state,LW_FLAG_HAS_WAITERS);
10701079

1071-
MyProc->lwWaiting=true;
1080+
MyProc->lwWaiting=LW_WS_WAITING;
10721081
MyProc->lwWaitMode=mode;
10731082

10741083
/* LW_WAIT_UNTIL_FREE waiters are always at the front of the queue */
@@ -1095,8 +1104,7 @@ LWLockQueueSelf(LWLock *lock, LWLockMode mode)
10951104
staticvoid
10961105
LWLockDequeueSelf(LWLock*lock)
10971106
{
1098-
boolfound= false;
1099-
proclist_mutable_iteriter;
1107+
boolon_waitlist;
11001108

11011109
#ifdefLWLOCK_STATS
11021110
lwlock_stats*lwstats;
@@ -1109,18 +1117,13 @@ LWLockDequeueSelf(LWLock *lock)
11091117
LWLockWaitListLock(lock);
11101118

11111119
/*
1112-
* Can't just remove ourselves from the list, but we need to iterate over
1113-
* all entries as somebody else could have dequeued us.
1120+
* Remove ourselves from the waitlist, unless we've already been
1121+
* removed. The removal happens with the wait list lock held, so there's
1122+
* no race in this check.
11141123
*/
1115-
proclist_foreach_modify(iter,&lock->waiters,lwWaitLink)
1116-
{
1117-
if (iter.cur==MyProc->pgprocno)
1118-
{
1119-
found= true;
1120-
proclist_delete(&lock->waiters,iter.cur,lwWaitLink);
1121-
break;
1122-
}
1123-
}
1124+
on_waitlist=MyProc->lwWaiting==LW_WS_WAITING;
1125+
if (on_waitlist)
1126+
proclist_delete(&lock->waiters,MyProc->pgprocno,lwWaitLink);
11241127

11251128
if (proclist_is_empty(&lock->waiters)&&
11261129
(pg_atomic_read_u32(&lock->state)&LW_FLAG_HAS_WAITERS)!=0)
@@ -1132,8 +1135,8 @@ LWLockDequeueSelf(LWLock *lock)
11321135
LWLockWaitListUnlock(lock);
11331136

11341137
/* clear waiting state again, nice for debugging */
1135-
if (found)
1136-
MyProc->lwWaiting=false;
1138+
if (on_waitlist)
1139+
MyProc->lwWaiting=LW_WS_NOT_WAITING;
11371140
else
11381141
{
11391142
intextraWaits=0;
@@ -1157,7 +1160,7 @@ LWLockDequeueSelf(LWLock *lock)
11571160
for (;;)
11581161
{
11591162
PGSemaphoreLock(MyProc->sem);
1160-
if (!MyProc->lwWaiting)
1163+
if (MyProc->lwWaiting==LW_WS_NOT_WAITING)
11611164
break;
11621165
extraWaits++;
11631166
}
@@ -1308,7 +1311,7 @@ LWLockAcquire(LWLock *lock, LWLockMode mode)
13081311
for (;;)
13091312
{
13101313
PGSemaphoreLock(proc->sem);
1311-
if (!proc->lwWaiting)
1314+
if (proc->lwWaiting==LW_WS_NOT_WAITING)
13121315
break;
13131316
extraWaits++;
13141317
}
@@ -1473,7 +1476,7 @@ LWLockAcquireOrWait(LWLock *lock, LWLockMode mode)
14731476
for (;;)
14741477
{
14751478
PGSemaphoreLock(proc->sem);
1476-
if (!proc->lwWaiting)
1479+
if (proc->lwWaiting==LW_WS_NOT_WAITING)
14771480
break;
14781481
extraWaits++;
14791482
}
@@ -1689,7 +1692,7 @@ LWLockWaitForVar(LWLock *lock, uint64 *valptr, uint64 oldval, uint64 *newval)
16891692
for (;;)
16901693
{
16911694
PGSemaphoreLock(proc->sem);
1692-
if (!proc->lwWaiting)
1695+
if (proc->lwWaiting==LW_WS_NOT_WAITING)
16931696
break;
16941697
extraWaits++;
16951698
}
@@ -1767,6 +1770,10 @@ LWLockUpdateVar(LWLock *lock, uint64 *valptr, uint64 val)
17671770

17681771
proclist_delete(&lock->waiters,iter.cur,lwWaitLink);
17691772
proclist_push_tail(&wakeup,iter.cur,lwWaitLink);
1773+
1774+
/* see LWLockWakeup() */
1775+
Assert(waiter->lwWaiting==LW_WS_WAITING);
1776+
waiter->lwWaiting=LW_WS_PENDING_WAKEUP;
17701777
}
17711778

17721779
/* We are done updating shared state of the lock itself. */
@@ -1782,7 +1789,7 @@ LWLockUpdateVar(LWLock *lock, uint64 *valptr, uint64 val)
17821789
proclist_delete(&wakeup,iter.cur,lwWaitLink);
17831790
/* check comment in LWLockWakeup() about this barrier */
17841791
pg_write_barrier();
1785-
waiter->lwWaiting=false;
1792+
waiter->lwWaiting=LW_WS_NOT_WAITING;
17861793
PGSemaphoreUnlock(waiter->sem);
17871794
}
17881795
}

‎src/backend/storage/lmgr/proc.c

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -397,7 +397,7 @@ InitProcess(void)
397397
/* NB -- autovac launcher intentionally does not set IS_AUTOVACUUM */
398398
if (IsAutoVacuumWorkerProcess())
399399
MyProc->statusFlags |=PROC_IS_AUTOVACUUM;
400-
MyProc->lwWaiting=false;
400+
MyProc->lwWaiting=LW_WS_NOT_WAITING;
401401
MyProc->lwWaitMode=0;
402402
MyProc->waitLock=NULL;
403403
MyProc->waitProcLock=NULL;
@@ -579,7 +579,7 @@ InitAuxiliaryProcess(void)
579579
MyProc->isBackgroundWorker=IsBackgroundWorker;
580580
MyProc->delayChkptFlags=0;
581581
MyProc->statusFlags=0;
582-
MyProc->lwWaiting=false;
582+
MyProc->lwWaiting=LW_WS_NOT_WAITING;
583583
MyProc->lwWaitMode=0;
584584
MyProc->waitLock=NULL;
585585
MyProc->waitProcLock=NULL;

‎src/include/storage/lwlock.h

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,14 @@
2323

2424
structPGPROC;
2525

26+
/* what state of the wait process is a backend in */
27+
typedefenumLWLockWaitState
28+
{
29+
LW_WS_NOT_WAITING,/* not currently waiting / woken up */
30+
LW_WS_WAITING,/* currently waiting */
31+
LW_WS_PENDING_WAKEUP,/* removed from waitlist, but not yet signalled */
32+
}LWLockWaitState;
33+
2634
/*
2735
* Code outside of lwlock.c should not manipulate the contents of this
2836
* structure directly, but we have to declare it here to allow LWLocks to be

‎src/include/storage/proc.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -217,7 +217,7 @@ struct PGPROC
217217
boolrecoveryConflictPending;
218218

219219
/* Info about LWLock the process is currently waiting for, if any. */
220-
boollwWaiting;/*true if waiting for an LW lock */
220+
uint8lwWaiting;/*see LWLockWaitState */
221221
uint8lwWaitMode;/* lwlock mode being waited for */
222222
proclist_nodelwWaitLink;/* position in LW lock wait list */
223223

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp