Skip to content

Commit 88554c0

Browse files
macdicemacdice
committed
Move RecoveryLockList into a hash table.
Standbys frequently need to release all locks held by a given xid. Instead of searching one big list linearly, let's create one list per xid and put them in a hash table, so we can find what we need in O(1) time. Earlier analysis and a prototype were done by David Rowley, though this isn't his patch. Back-patch all the way. Author: Thomas Munro Diagnosed-by: David Rowley, Andres Freund Reviewed-by: Andres Freund, Tom Lane, Robert Haas Discussion: https://postgr.es/m/CAEepm%3D1mL0KiQ2KJ4yuPpLGX94a4Ns_W6TL4EGRouxWibu56pA%40mail.gmail.com Discussion: https://postgr.es/m/CAKJS1f9vJ841HY%3DwonnLVbfkTWGYWdPN72VMxnArcGCjF3SywA%40mail.gmail.com
1 parent 324076a commit 88554c0

File tree

1 file changed

+87
-77
lines changed

1 file changed

+87
-77
lines changed

‎src/backend/storage/ipc/standby.c

Lines changed: 87 additions & 77 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,8 @@
2929
#include "storage/procarray.h"
3030
#include "storage/sinvaladt.h"
3131
#include "storage/standby.h"
32+
#include "utils/hsearch.h"
33+
#include "utils/memutils.h"
3234
#include "utils/ps_status.h"
3335
#include "utils/timeout.h"
3436
#include "utils/timestamp.h"
@@ -38,14 +40,22 @@ int vacuum_defer_cleanup_age;
3840
int max_standby_archive_delay = 30 * 1000;
3941
int max_standby_streaming_delay = 30 * 1000;
4042

41-
static List *RecoveryLockList;
43+
static HTAB *RecoveryLockLists;
4244

4345
static void ResolveRecoveryConflictWithVirtualXIDs(VirtualTransactionId *waitlist,
4446
ProcSignalReason reason);
4547
static void SendRecoveryConflictWithBufferPin(ProcSignalReason reason);
4648
static XLogRecPtr LogCurrentRunningXacts(RunningTransactions CurrRunningXacts);
4749
static void LogAccessExclusiveLocks(int nlocks, xl_standby_lock *locks);
4850

51+
/*
52+
* Keep track of all the locks owned by a given transaction.
53+
*/
54+
typedef struct RecoveryLockListsEntry
55+
{
56+
TransactionId xid;
57+
List *locks;
58+
} RecoveryLockListsEntry;
4959

5060
/*
5161
* InitRecoveryTransactionEnvironment
@@ -63,6 +73,19 @@ void
6373
InitRecoveryTransactionEnvironment(void)
6474
{
6575
VirtualTransactionId vxid;
76+
HASHCTL hash_ctl;
77+
78+
/*
79+
* Initialize the hash table for tracking the list of locks held by each
80+
* transaction.
81+
*/
82+
memset(&hash_ctl, 0, sizeof(hash_ctl));
83+
hash_ctl.keysize = sizeof(TransactionId);
84+
hash_ctl.entrysize = sizeof(RecoveryLockListsEntry);
85+
RecoveryLockLists = hash_create("RecoveryLockLists",
86+
64,
87+
&hash_ctl,
88+
HASH_ELEM | HASH_BLOBS);
6689

6790
/*
6891
* Initialize shared invalidation management for Startup process, being
@@ -107,6 +130,10 @@ ShutdownRecoveryTransactionEnvironment(void)
107130
/* Release all locks the tracked transactions were holding */
108131
StandbyReleaseAllLocks();
109132

133+
/* Destroy the hash table of locks. */
134+
hash_destroy(RecoveryLockLists);
135+
RecoveryLockLists = NULL;
136+
110137
/* Cleanup our VirtualTransaction */
111138
VirtualXactLockTableCleanup();
112139
}
@@ -586,8 +613,8 @@ StandbyLockTimeoutHandler(void)
586613
* We only keep track of AccessExclusiveLocks, which are only ever held by
587614
* one transaction on one relation.
588615
*
589-
* We keep a single dynamically expandible list of locks in local memory,
590-
* RecoveryLockList, so we can keep track of the various entries made by
616+
* We keep a hash table of lists of locks in local memory keyed by xid,
617+
* RecoveryLockLists, so we can keep track of the various entries made by
591618
* the Startup process's virtual xid in the shared lock table.
592619
*
593620
* List elements use type xl_standby_lock, since the WAL record type exactly
@@ -601,8 +628,10 @@ StandbyLockTimeoutHandler(void)
601628
void
602629
StandbyAcquireAccessExclusiveLock(TransactionId xid, Oid dbOid, Oid relOid)
603630
{
631+
RecoveryLockListsEntry *entry;
604632
xl_standby_lock *newlock;
605633
LOCKTAG locktag;
634+
bool found;
606635

607636
/* Already processed? */
608637
if (!TransactionIdIsValid(xid) ||
@@ -616,58 +645,68 @@ StandbyAcquireAccessExclusiveLock(TransactionId xid, Oid dbOid, Oid relOid)
616645
/* dbOid is InvalidOid when we are locking a shared relation. */
617646
Assert(OidIsValid(relOid));
618647

648+
/* Create a new list for this xid, if we don't have one already. */
649+
entry = hash_search(RecoveryLockLists, &xid, HASH_ENTER, &found);
650+
if (!found)
651+
{
652+
entry->xid = xid;
653+
entry->locks = NIL;
654+
}
655+
619656
newlock = palloc(sizeof(xl_standby_lock));
620657
newlock->xid = xid;
621658
newlock->dbOid = dbOid;
622659
newlock->relOid = relOid;
623-
RecoveryLockList = lappend(RecoveryLockList, newlock);
660+
entry->locks = lappend(entry->locks, newlock);
624661

625662
SET_LOCKTAG_RELATION(locktag, newlock->dbOid, newlock->relOid);
626663

627664
LockAcquireExtended(&locktag, AccessExclusiveLock, true, false, false);
628665
}
629666

630667
static void
631-
StandbyReleaseLocks(TransactionId xid)
668+
StandbyReleaseLockList(List *locks)
632669
{
633-
ListCell *cell,
634-
*prev,
635-
*next;
636-
637-
/*
638-
* Release all matching locks and remove them from list
639-
*/
640-
prev = NULL;
641-
for (cell = list_head(RecoveryLockList); cell; cell = next)
670+
while (locks)
642671
{
643-
xl_standby_lock *lock = (xl_standby_lock *) lfirst(cell);
672+
xl_standby_lock *lock = (xl_standby_lock *) linitial(locks);
673+
LOCKTAG locktag;
674+
elog(trace_recovery(DEBUG4),
675+
"releasing recovery lock: xid %u db %u rel %u",
676+
lock->xid, lock->dbOid, lock->relOid);
677+
SET_LOCKTAG_RELATION(locktag, lock->dbOid, lock->relOid);
678+
if (!LockRelease(&locktag, AccessExclusiveLock, true))
679+
{
680+
elog(LOG,
681+
"RecoveryLockLists contains entry for lock no longer recorded by lock manager: xid %u database %u relation %u",
682+
lock->xid, lock->dbOid, lock->relOid);
683+
Assert(false);
684+
}
685+
pfree(lock);
686+
locks = list_delete_first(locks);
687+
}
688+
}
644689

645-
next = lnext(cell);
690+
static void
691+
StandbyReleaseLocks(TransactionId xid)
692+
{
693+
RecoveryLockListsEntry *entry;
646694

647-
if (!TransactionIdIsValid(xid) || lock->xid == xid)
695+
if (TransactionIdIsValid(xid))
696+
{
697+
if ((entry = hash_search(RecoveryLockLists, &xid, HASH_FIND, NULL)))
648698
{
649-
LOCKTAG locktag;
650-
651-
elog(trace_recovery(DEBUG4),
652-
"releasing recovery lock: xid %u db %u rel %u",
653-
lock->xid, lock->dbOid, lock->relOid);
654-
SET_LOCKTAG_RELATION(locktag, lock->dbOid, lock->relOid);
655-
if (!LockRelease(&locktag, AccessExclusiveLock, true))
656-
elog(LOG,
657-
"RecoveryLockList contains entry for lock no longer recorded by lock manager: xid %u database %u relation %u",
658-
lock->xid, lock->dbOid, lock->relOid);
659-
660-
RecoveryLockList = list_delete_cell(RecoveryLockList, cell, prev);
661-
pfree(lock);
699+
StandbyReleaseLockList(entry->locks);
700+
hash_search(RecoveryLockLists, entry, HASH_REMOVE, NULL);
662701
}
663-
else
664-
prev = cell;
665702
}
703+
else
704+
StandbyReleaseAllLocks();
666705
}
667706

668707
/*
669708
* Release locks for a transaction tree, starting at xid down, from
670-
* RecoveryLockList.
709+
* RecoveryLockLists.
671710
*
672711
* Called during WAL replay of COMMIT/ROLLBACK when in hot standby mode,
673712
* to remove any AccessExclusiveLocks requested by a transaction.
@@ -689,30 +728,16 @@ StandbyReleaseLockTree(TransactionId xid, int nsubxids, TransactionId *subxids)
689728
void
690729
StandbyReleaseAllLocks(void)
691730
{
692-
ListCell *cell,
693-
*prev,
694-
*next;
695-
LOCKTAG locktag;
731+
HASH_SEQ_STATUS status;
732+
RecoveryLockListsEntry *entry;
696733

697734
elog(trace_recovery(DEBUG2), "release all standby locks");
698735

699-
prev = NULL;
700-
for (cell = list_head(RecoveryLockList); cell; cell = next)
736+
hash_seq_init(&status, RecoveryLockLists);
737+
while ((entry = hash_seq_search(&status)))
701738
{
702-
xl_standby_lock *lock = (xl_standby_lock *) lfirst(cell);
703-
704-
next = lnext(cell);
705-
706-
elog(trace_recovery(DEBUG4),
707-
"releasing recovery lock: xid %u db %u rel %u",
708-
lock->xid, lock->dbOid, lock->relOid);
709-
SET_LOCKTAG_RELATION(locktag, lock->dbOid, lock->relOid);
710-
if (!LockRelease(&locktag, AccessExclusiveLock, true))
711-
elog(LOG,
712-
"RecoveryLockList contains entry for lock no longer recorded by lock manager: xid %u database %u relation %u",
713-
lock->xid, lock->dbOid, lock->relOid);
714-
RecoveryLockList = list_delete_cell(RecoveryLockList, cell, prev);
715-
pfree(lock);
739+
StandbyReleaseLockList(entry->locks);
740+
hash_search(RecoveryLockLists, entry, HASH_REMOVE, NULL);
716741
}
717742
}
718743

@@ -724,22 +749,17 @@ StandbyReleaseAllLocks(void)
724749
void
725750
StandbyReleaseOldLocks(int nxids, TransactionId *xids)
726751
{
727-
ListCell *cell,
728-
*prev,
729-
*next;
730-
LOCKTAG locktag;
752+
HASH_SEQ_STATUS status;
753+
RecoveryLockListsEntry *entry;
731754

732-
prev = NULL;
733-
for (cell = list_head(RecoveryLockList); cell; cell = next)
755+
hash_seq_init(&status, RecoveryLockLists);
756+
while ((entry = hash_seq_search(&status)))
734757
{
735-
xl_standby_lock *lock = (xl_standby_lock *) lfirst(cell);
736758
bool remove = false;
737759

738-
next = lnext(cell);
760+
Assert(TransactionIdIsValid(entry->xid));
739761

740-
Assert(TransactionIdIsValid(lock->xid));
741-
742-
if (StandbyTransactionIdIsPrepared(lock->xid))
762+
if (StandbyTransactionIdIsPrepared(entry->xid))
743763
remove = false;
744764
else
745765
{
@@ -748,7 +768,7 @@ StandbyReleaseOldLocks(int nxids, TransactionId *xids)
748768

749769
for (i = 0; i < nxids; i++)
750770
{
751-
if (lock->xid == xids[i])
771+
if (entry->xid == xids[i])
752772
{
753773
found = true;
754774
break;
@@ -764,19 +784,9 @@ StandbyReleaseOldLocks(int nxids, TransactionId *xids)
764784

765785
if (remove)
766786
{
767-
elog(trace_recovery(DEBUG4),
768-
"releasing recovery lock: xid %u db %u rel %u",
769-
lock->xid, lock->dbOid, lock->relOid);
770-
SET_LOCKTAG_RELATION(locktag, lock->dbOid, lock->relOid);
771-
if (!LockRelease(&locktag, AccessExclusiveLock, true))
772-
elog(LOG,
773-
"RecoveryLockList contains entry for lock no longer recorded by lock manager: xid %u database %u relation %u",
774-
lock->xid, lock->dbOid, lock->relOid);
775-
RecoveryLockList = list_delete_cell(RecoveryLockList, cell, prev);
776-
pfree(lock);
787+
StandbyReleaseLockList(entry->locks);
788+
hash_search(RecoveryLockLists, entry, HASH_REMOVE, NULL);
777789
}
778-
else
779-
prev = cell;
780790
}
781791
}
782792

0 commit comments

Comments
 (0)