From: Alexander Korotkov <a.korotkov@postgrespro.ru>
To: Peter Geoghegan <pg@bowt.ie>
Cc: chenhj <chjischj@163.com>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Subject: Re: Connections hang indefinitely while taking a gin index's LWLock buffer_content lock(PG10.7)
Date: Sun, 17 Nov 2019 21:18:43 +0300
Message-ID: <CAPpHfdvtwJbPSRWMfhXfvd4ZMb7GCxc77Su=u9WdTobWZEpvgA@mail.gmail.com> (raw)
In-Reply-To: <CAPpHfdvLVvO8FSCenRG3JVSLrMpaMpWTvJD3ueuC3EUdfE4mXA@mail.gmail.com>
References: <5c332bd1.87b6.16d7c17aa98.Coremail.chjischj@163.com>
<CAPpHfduQdEVcZrJhceU01zfa5dYrw8oc5f1m8NNGSYM8VFS3GA@mail.gmail.com>
<CAPpHfdvws2_cCqsZOB14j253saCH-B33Yy0saYEQsAUsXu6xFA@mail.gmail.com>
<CAH2-WznOPWrgLbWucU=cZznAZmhAH8u4m7yhFLGQY_vB-YDEfw@mail.gmail.com>
<CAPpHfduEXg9GHACU7hPef+KwELfQu2yUSoxoGRrK2CuuuY9QXA@mail.gmail.com>
<CAPpHfdvMvsw-NcE5bRS7R1BbvA4BxoDnVVjkXC5W0Czvy9LVrg@mail.gmail.com>
<CAPpHfduXR_ywyaVN4+OYEGaw=cPLzWX6RxYLBncKw8de9vOkqw@mail.gmail.com>
<CAH2-Wz=qi7P40nWZ8J5GSbE=1DrY=1QP2xvGPdWAaePD=DfAfQ@mail.gmail.com>
<CAPpHfdvLVvO8FSCenRG3JVSLrMpaMpWTvJD3ueuC3EUdfE4mXA@mail.gmail.com>
On Mon, Nov 11, 2019 at 2:42 AM Alexander Korotkov
<a.korotkov@postgrespro.ru> wrote:
> I'm sorry for late reply. I was busy with various things. Also
> digging into these details took some time. Please find my explanation
> below.
>
> On Wed, Oct 30, 2019 at 2:34 AM Peter Geoghegan <pg@bowt.ie> wrote:
> > In general, it seems very important to be clear about exactly how the
> > key space works. The nbtree work for v12 greatly benefitted from
> > defining comparisons in a way that didn't really change how nbtree
> > worked, while at the same time minimizing I/O and making nbtree
> > faithful to Lehman & Yao's original design. It isn't obvious how
> > valuable it is to really carefully define how invariants and key
> > comparisons work, but it seems possible to solve a lot of problems
> > that way.
>
> gin packs downlinks and pivot key into tuples in the different way
> than nbtree does. Let's see the logical structure of internal B-tree
> page. We can represent it as following.
>
> downlink_1, key_1_2, downlink_2, key_2_3, .... , downlink_n, highkey
>
> key_{i-1}_i is pivot key, which splits key space between
> downlink_{i-1} and downlink_i. So, every key under downlink_{i-1} is
> <= key_{i-1}_i. Every key under downlink_i is > key_{i-1}_i. And all
> underlying keys are <= highkey.
>
> nbtree packs that into tuples as followings (tuples are shown in parentheses).
>
> (highkey), (-inf, downlink_1), (key_1_2, downlink_2), ...
> (key_{n-1}_n, downlink_n)
>
> So, we store highkey separately. key_{i-1}_i and downlink_i form a
> tuple together. downlink_1 is coupled with -inf key.
>
> gin packs tuples in a different way.
>
> (downlink_1, key_1_2), (downlink_2, key_2_3), ... , (downlink_n, highkey)
>
> So, in GIN key_{i-1}_i and downlink_{i-1} form a tuple. Highkey is
> coupled with downlink_n. And -inf key is not needed here.
>
> But there is couple notes about highkey:
> 1) In entry tree rightmost page, a key coupled with downlink_n doesn't
> really matter. Highkey is assumed to be infinity.
> 2) In posting tree, a key coupled with downlink_n always doesn't
> matter. Highkey for non-rightmost pages is stored separately and
> accessed via GinDataPageGetRightBound().
>
> I think this explains following:
> 1) The invariants in gin btree are same as they are in nbtree. Just
> page layout is different.
> 2) The way entryLocateEntry() works. In particular why it's OK to go
> the mid downlink if corresponding key equals.
> 3) There is no "negative infinity" item in internal pages.
>
> Does the explanation of above looks clear for you? If so, I can put
> it into the README.
So, I've put this explanation into README patch. I just change
designation to better match with Lehman & Yao paper and did some minor
enchantments.
I'm going to push this patchset if no objections.
------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company
Attachments:download all (3 files, .tar.gz)0002-Fix-traversing-to-the-deleted-GIN-page-via-downlin-4.patch (application/octet-stream, 3.1K) download
From 5e8f16e120ebf4f388bf16efc29e0cc27428ced7 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <akorotkov@postgresql.org>
Date: Sun, 17 Nov 2019 21:10:45 +0300
Subject: [PATCH 2/3] Fix traversing to the deleted GIN page via downlink
Current GIN code appears to don't handle traversing to the deleted page via
downlink. This commit fixes that by stepping right from the delete page like
we do in nbtree.
This commit also fixes setting 'deleted' flag to the GIN pages. Now other page
flags are not erased once page is deleted. That helps to keep our assertions
true if we arrive deleted page via downlink.
Discussion: https://postgr.es/m/CAPpHfdvMvsw-NcE5bRS7R1BbvA4BxoDnVVjkXC5W0Czvy9LVrg%40mail.gmail.com
Author: Alexander Korotkov
Reviewed-by: Peter Geoghegan
Backpatch-through: 9.4
---
src/backend/access/gin/ginbtree.c | 7 -------
src/backend/access/gin/gindatapage.c | 3 +++
src/backend/access/gin/ginvacuum.c | 2 +-
src/backend/access/gin/ginxlog.c | 2 +-
4 files changed, 5 insertions(+), 9 deletions(-)
diff --git a/src/backend/access/gin/ginbtree.c b/src/backend/access/gin/ginbtree.cindex 20adfa21948..8f8cd85db6a 100644--- a/src/backend/access/gin/ginbtree.c+++ b/src/backend/access/gin/ginbtree.c@@ -187,13 +187,6 @@ ginStepRight(Buffer buffer, Relation index, int lockmode)
if (isLeaf != GinPageIsLeaf(page) || isData != GinPageIsData(page))
elog(ERROR, "right sibling of GIN page is of different type");
- /*- * Given the proper lock sequence above, we should never land on a deleted- * page.- */- if (GinPageIsDeleted(page))- elog(ERROR, "right sibling of GIN page was deleted");-
return nextbuffer;
}
diff --git a/src/backend/access/gin/gindatapage.c b/src/backend/access/gin/gindatapage.cindex e8c34d6b1f6..e497210b4c0 100644--- a/src/backend/access/gin/gindatapage.c+++ b/src/backend/access/gin/gindatapage.c@@ -238,6 +238,9 @@ dataIsMoveRight(GinBtree btree, Page page)
if (GinPageRightMost(page))
return false;
+ if (GinPageIsDeleted(page))+ return true;+
return (ginCompareItemPointers(&btree->itemptr, iptr) > 0) ? true : false;
}
diff --git a/src/backend/access/gin/ginvacuum.c b/src/backend/access/gin/ginvacuum.cindex 72169bb0bdc..11e050171ad 100644--- a/src/backend/access/gin/ginvacuum.c+++ b/src/backend/access/gin/ginvacuum.c@@ -186,7 +186,7 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
* we shouldn't change rightlink field to save workability of running
* search scan
*/
- GinPageGetOpaque(page)->flags = GIN_DELETED;+ GinPageSetDeleted(page);
MarkBufferDirty(pBuffer);
MarkBufferDirty(lBuffer);
diff --git a/src/backend/access/gin/ginxlog.c b/src/backend/access/gin/ginxlog.cindex c945b282721..387102f21a1 100644--- a/src/backend/access/gin/ginxlog.c+++ b/src/backend/access/gin/ginxlog.c@@ -500,7 +500,7 @@ ginRedoDeletePage(XLogReaderState *record)
{
page = BufferGetPage(dbuffer);
Assert(GinPageIsData(page));
- GinPageGetOpaque(page)->flags = GIN_DELETED;+ GinPageSetDeleted(page);
GinPageSetDeleteXid(page, data->deleteXid);
PageSetLSN(page, lsn);
MarkBufferDirty(dbuffer);
--
2.14.3
0001-Fix-deadlock-between-ginDeletePage-and-ginStepRigh-4.patch (application/octet-stream, 11.3K) download
From a73d0636c9c0c8363a6cae2815c938cf7d76ef5c Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <akorotkov@postgresql.org>
Date: Sun, 17 Nov 2019 21:10:34 +0300
Subject: [PATCH 1/3] Fix deadlock between ginDeletePage() and ginStepRight()
When ginDeletePage() is about to delete page it locks its left sibling to revise
the rightlink. So, it locks pages in right to left manner. Int he same time
ginStepRight() locks pages in left to right manner, and that could cause a
deadlock.
This commit makes ginScanToDelete() keep exclusive lock on left siblings of
currently investigated path. That elimites need to relock left sibling in
ginDeletePage(). Thus, deadlock with ginStepRight() can't happen anymore.
Reported-by: Chen Huajun
Discussion: https://postgr.es/m/5c332bd1.87b6.16d7c17aa98.Coremail.chjischj%40163.com
Author: Alexander Korotkov
Reviewed-by: Peter Geoghegan
Backpatch-through: 9.4
---
src/backend/access/gin/README | 79 ++++++++++++++++++++++----------------
src/backend/access/gin/ginvacuum.c | 54 +++++++++++++++++---------
2 files changed, 81 insertions(+), 52 deletions(-)
diff --git a/src/backend/access/gin/README b/src/backend/access/gin/READMEindex 76c12ae2f6b..e4152500cc6 100644--- a/src/backend/access/gin/README+++ b/src/backend/access/gin/README@@ -277,50 +277,63 @@ followed by the packed items.
Concurrency
-----------
-The entry tree and each posting tree is a B-tree, with right-links connecting+The entry tree and each posting tree are B-trees, with right-links connecting
sibling pages at the same level. This is the same structure that is used in
the regular B-tree indexam (invented by Lehman & Yao), but we don't support
scanning a GIN trees backwards, so we don't need left-links.
To avoid deadlocks, B-tree pages must always be locked in the same order:
-left to right, and bottom to top. When searching, the tree is traversed from-top to bottom, so the lock on the parent page must be released before+left to right, and bottom to top. The exception is page deletion during vacuum,+which would be considered separately. When searching, the tree is traversed+from top to bottom, so the lock on the parent page must be released before
descending to the next level. Concurrent page splits move the keyspace to
right, so after following a downlink, the page actually containing the key
we're looking for might be somewhere to the right of the page we landed on.
In that case, we follow the right-links until we find the page we're looking
-for.--To delete a page, the page's left sibling, the target page, and its parent,-are locked in that order, and the page is marked as deleted. However, a-concurrent search might already have read a pointer to the page, and might be-just about to follow it. A page can be reached via the right-link of its left-sibling, or via its downlink in the parent.+for. In spite of searches, insertions keeps pins on all pages in path from+root to the current page. These pages potentially requies downlink insertion,+while pins prevent them from being deleted.++Vacuum never deletes tuples or pages from the entry tree. It traverses entry+tree leafs in logical order by rightlinks and removes deletable TIDs from+posting lists. Posting trees are processed by links from entry tree leafs. They+are vacuumed in two stages. At first stage, deletable TIDs are removed from+leafs. If first stage detects at least one empty page, then at the second stage+ginScanToDelete() deletes empty pages.++ginScanToDelete() scans posting tree to delete empty pages, while vacuum holds+cleanup lock on the posting tree root. This lock prevent concurrent inserts,+because inserters hold a pin on the root page. In spite of inserters searches+don't hold pin on root page. So, while new searches cannot begin while root page+is locked, any already-in-progress scans can continue concurrently with vacuum.++ginScanToDelete() does depth-first tree scanning while keeping each page in path+from root to current page exclusively locked. It also keeps left sibling of+each page in the path locked. Thus, if current page is to be removed, all+required pages to remove both downlink and rightlink are already locked.+Therefore, page deletion locks pages top to bottom and left to right breaking+our general rule. But assuming there is no concurrent insertions, this can't+cause a deadlock.++During replay od page deletion at standby, the page's left sibling, the target+page, and its parent, are locked in that order. So it follows bottom to top and+left to right rule.++A search concurrent to page deletion might already have read a pointer to the+page to be deleted, and might be just about to follow it. A page can be reached+via the right-link of its left sibling, or via its downlink in the parent.
To prevent a backend from reaching a deleted page via a right-link, when
-following a right-link the lock on the previous page is not released until-the lock on next page has been acquired.--The downlink is more tricky. A search descending the tree must release the-lock on the parent page before locking the child, or it could deadlock with-a concurrent split of the child page; a page split locks the parent, while-already holding a lock on the child page. So, deleted page cannot be reclaimed-immediately. Instead, we have to wait for every transaction, which might wait-to reference this page, to finish. Corresponding processes must observe that-the page is marked deleted and recover accordingly.--The previous paragraph's reasoning only applies to searches, and only to-posting trees. To protect from inserters following a downlink to a deleted-page, vacuum simply locks out all concurrent insertions to the posting tree,-by holding a super-exclusive lock on the posting tree root. Inserters hold a-pin on the root page, but searches do not, so while new searches cannot begin-while root page is locked, any already-in-progress scans can continue-concurrently with vacuum. In the entry tree, we never delete pages.--(This is quite different from the mechanism the btree indexam uses to make-page-deletions safe; it stamps the deleted pages with an XID and keeps the-deleted pages around with the right-link intact until all concurrent scans-have finished.)+following a right-link the lock on the previous page is not released until the+lock on next page has been acquired.++The downlink is more tricky. A search descending the tree must release the lock+on the parent page before locking the child, or it could deadlock with a+concurrent split of the child page; a page split locks the parent, while already+holding a lock on the child page. So, deleted page cannot be reclaimed+immediately. Instead, we have to wait for every transaction, which might wait to+reference this page, to finish. Corresponding processes must observe that the+page is marked deleted and recover accordingly.
Predicate Locking
-----------------
diff --git a/src/backend/access/gin/ginvacuum.c b/src/backend/access/gin/ginvacuum.cindex dc46f2460e2..72169bb0bdc 100644--- a/src/backend/access/gin/ginvacuum.c+++ b/src/backend/access/gin/ginvacuum.c@@ -117,7 +117,8 @@ typedef struct DataPageDeleteStack
struct DataPageDeleteStack *parent;
BlockNumber blkno; /* current block number */
- BlockNumber leftBlkno; /* rightest non-deleted page on left */+ Buffer leftBuffer; /* pinned and locked rightest non-deleted page+ * on left */
bool isRoot;
} DataPageDeleteStack;
@@ -139,11 +140,8 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
/*
* This function MUST be called only if someone of parent pages hold
* exclusive cleanup lock. This guarantees that no insertions currently
- * happen in this subtree. Caller also acquire Exclusive lock on deletable- * page and is acquiring and releasing exclusive lock on left page before.- * Left page was locked and released. Then parent and this page are- * locked. We acquire left page lock here only to mark page dirty after- * changing right pointer.+ * happen in this subtree. Caller also acquires Exclusive locks on+ * deletable and left pages.
*/
lBuffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, leftBlkno,
RBM_NORMAL, gvs->strategy);
@@ -152,8 +150,6 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
pBuffer = ReadBufferExtended(gvs->index, MAIN_FORKNUM, parentBlkno,
RBM_NORMAL, gvs->strategy);
- LockBuffer(lBuffer, GIN_EXCLUSIVE);-
page = BufferGetPage(dBuffer);
rightlink = GinPageGetOpaque(page)->rightlink;
@@ -227,7 +223,7 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
}
ReleaseBuffer(pBuffer);
- UnlockReleaseBuffer(lBuffer);+ ReleaseBuffer(lBuffer);
ReleaseBuffer(dBuffer);
END_CRIT_SECTION();
@@ -237,7 +233,11 @@ ginDeletePage(GinVacuumState *gvs, BlockNumber deleteBlkno, BlockNumber leftBlkn
/*
- * scans posting tree and deletes empty pages+ * Scans posting tree and deletes empty pages. Caller must lock root page for+ * cleanup. During scan path from root to current page is kept exclusively+ * locked. Also keep left page exclusively locked, because ginDeletePage()+ * needs it. If we try to relock left page later, it could deadlock with+ * ginStepRight().
*/
static bool
ginScanToDelete(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
@@ -260,7 +260,7 @@ ginScanToDelete(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
me = (DataPageDeleteStack *) palloc0(sizeof(DataPageDeleteStack));
me->parent = parent;
parent->child = me;
- me->leftBlkno = InvalidBlockNumber;+ me->leftBuffer = InvalidBuffer;
}
else
me = parent->child;
@@ -288,6 +288,12 @@ ginScanToDelete(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
if (ginScanToDelete(gvs, PostingItemGetBlockNumber(pitem), false, me, i))
i--;
}
++ if (GinPageRightMost(page) && BufferIsValid(me->child->leftBuffer))+ {+ UnlockReleaseBuffer(me->child->leftBuffer);+ me->child->leftBuffer = InvalidBuffer;+ }
}
if (GinPageIsLeaf(page))
@@ -298,21 +304,31 @@ ginScanToDelete(GinVacuumState *gvs, BlockNumber blkno, bool isRoot,
if (isempty)
{
/* we never delete the left- or rightmost branch */
- if (me->leftBlkno != InvalidBlockNumber && !GinPageRightMost(page))+ if (BufferIsValid(me->leftBuffer) && !GinPageRightMost(page))
{
Assert(!isRoot);
- ginDeletePage(gvs, blkno, me->leftBlkno, me->parent->blkno, myoff, me->parent->isRoot);+ ginDeletePage(gvs, blkno, BufferGetBlockNumber(me->leftBuffer),+ me->parent->blkno, myoff, me->parent->isRoot);
meDelete = true;
}
}
- if (!isRoot)- LockBuffer(buffer, GIN_UNLOCK);+ if (!meDelete)+ {+ if (BufferIsValid(me->leftBuffer))+ UnlockReleaseBuffer(me->leftBuffer);+ me->leftBuffer = buffer;+ }+ else+ {+ if (!isRoot)+ LockBuffer(buffer, GIN_UNLOCK);- ReleaseBuffer(buffer);+ ReleaseBuffer(buffer);+ }- if (!meDelete)- me->leftBlkno = blkno;+ if (isRoot)+ ReleaseBuffer(buffer);
return meDelete;
}
@@ -409,7 +425,7 @@ ginVacuumPostingTree(GinVacuumState *gvs, BlockNumber rootBlkno)
LockBufferForCleanup(buffer);
memset(&root, 0, sizeof(DataPageDeleteStack));
- root.leftBlkno = InvalidBlockNumber;+ root.leftBuffer = InvalidBuffer;
root.isRoot = true;
ginScanToDelete(gvs, rootBlkno, true, &root, InvalidOffsetNumber);
--
2.14.3
0003-Revise-GIN-README-4.patch (application/octet-stream, 12.1K) download
From addee9d8a1c0d596377fa5989ce6d6daa876a6a1 Mon Sep 17 00:00:00 2001
From: Alexander Korotkov <akorotkov@postgresql.org>
Date: Sun, 17 Nov 2019 21:11:22 +0300
Subject: [PATCH 3/3] Revise GIN README
We find GIN concurrency bugs from time to time. One of the problems here is
that concurrency of GIN isn't well-documented in README. So, it might be even
hard to distinguish design bugs from implementation bugs.
This commit revised concurrency section in GIN README providing more details.
Some examples are illustrated in ASCII art.
Also, this commit add the explanation of how is tuple layout in internal GIN
B-tree page different in comparison with nbtree.
Discussion: https://postgr.es/m/5c332bd1.87b6.16d7c17aa98.Coremail.chjischj%40163.com
Author: Alexander Korotkov
Reviewed-by: Peter Geoghegan
Backpatch-through: 9.4
---
src/backend/access/gin/README | 214 ++++++++++++++++++++++++++++++++++--------
1 file changed, 176 insertions(+), 38 deletions(-)
diff --git a/src/backend/access/gin/README b/src/backend/access/gin/READMEindex e4152500cc6..125a82219b9 100644--- a/src/backend/access/gin/README+++ b/src/backend/access/gin/README@@ -215,6 +215,35 @@ fit on one pending-list page must have those pages to itself, even if this
results in wasting much of the space on the preceding page and the last
page for the tuple.)
+GIN packs downlinks and pivot keys into internal page tuples in a different way+than nbtree does. Lehman & Yao defines it as following.++P_0, K_1, P_1, K_2, P_2, ... , K_n, P_n, K_{n+1}++There P_i is a downlink and K_i is a key. K_i splits key space between P_{i-1}+and P_i (0 <= i <= n). K_{n+1} is high key.++In internal page tuple is key and downlink grouped together. nbtree packs+keys and downlinks into tuples as following.++(K_{n+1}, None), (-Inf, P_0), (K_1, P_1), ... , (K_n, P_n)++There tuples are shown in parentheses. So, highkey is stored separately. P_i+is grouped with K_i. P_0 is grouped with -Inf key.++GIN packs keys and downlinks into tuples in a different way.++(P_0, K_1), (P_1, K_2), ... , (P_n, K_{n+1})++P_i is grouped with K_{i+1}. -Inf key is not needed.++There are couple of additional notes regarding K_{n+1} key.+1) In entry tree rightmost page, a key coupled with P_n doesn't really matter.+Highkey is assumed to be infinity.+2) In posting tree, a key coupled with P_n always doesn't matter. Highkey for+non-rightmost pages is stored separately and accessed via+GinDataPageGetRightBound().+
Posting tree
------------
@@ -278,21 +307,86 @@ Concurrency
-----------
The entry tree and each posting tree are B-trees, with right-links connecting
-sibling pages at the same level. This is the same structure that is used in+sibling pages at the same level. This is the same structure that is used in
the regular B-tree indexam (invented by Lehman & Yao), but we don't support
-scanning a GIN trees backwards, so we don't need left-links.--To avoid deadlocks, B-tree pages must always be locked in the same order:-left to right, and bottom to top. The exception is page deletion during vacuum,-which would be considered separately. When searching, the tree is traversed-from top to bottom, so the lock on the parent page must be released before-descending to the next level. Concurrent page splits move the keyspace to-right, so after following a downlink, the page actually containing the key-we're looking for might be somewhere to the right of the page we landed on.-In that case, we follow the right-links until we find the page we're looking-for. In spite of searches, insertions keeps pins on all pages in path from-root to the current page. These pages potentially requies downlink insertion,-while pins prevent them from being deleted.+scanning a GIN trees backwards, so we don't need left-links. The entry tree+leaves don't have dedicated high keys, instead greatest leaf tuple serves as+high key. That works because tuples are never deleted from the entry tree.++The algorithms used to operate entry and posting trees are considered below.++### Locating the leaf page++When we search for leaf page in GIN btree to perform a read, we descend from+the root page to the leaf through using downlinks taking pin and shared lock on+one page at once. So, we release pin and shared lock on previous page before+getting them on the next page.++The picture below shows tree state after finding the leaf page. Lower case+letters depicts tree pages. 'S' depicts shared lock on the page.++ a+ / | \+ b c d+ / | \ | \ | \+ eS f g h i j k++### Steping right++Concurrent page splits move the keyspace to right, so after following a+downlink, the page actually containing the key we're looking for might be+somewhere to the right of the page we landed on. In that case, we follow the+right-links until we find the page we're looking for.++During stepping right we take pin and shared lock on the right sibling before+releasing them from the current page. This mechanism was designed to protect+from stepping to delete page. We step to the right sibling while hold lock on+the rightlink pointing there. So, it's guaranteed that nobody updates rightlink+concurrently and doesn't delete right sibling accordingly.++The picture below shows two pages locked at once during stepping right.++ a+ / | \+ b c d+ / | \ | \ | \+ eS fS g h i j k++### Insert++While finding appropriate leaf for insertion we also descend from the root to+leaf, while shared locking one page at once in. But during insertion we don't+release pins from root and internal pages. That could save us some lookups to+the buffers hash table for downlinks insertion assuming parents are not changed+due to concurrent splits. Once we reach leaf we re-lock the page in exclusive+mode.++The picture below shows leaf page locked in exclusive mode and ready for+insertion. 'P' and 'E' depict pin and exclusive lock correspondingly.+++ aP+ / | \+ b cP d+ / | \ | \ | \+ e f g hE i j k+++If insert causes a page split, the parent is locked in exclusive mode before+unlocking the left child. So, insertion algorithm can exclusively lock both+parent and child pages at once starting from child.++The picture below shows tree state after leaf page split. 'q' is new page+produced by split. Parent 'c' is about to have downlink inserted.++ aP+ / | \+ b cE d+ / | \ / | \ | \+ e f g hE q i j k+++### Page deletion
Vacuum never deletes tuples or pages from the entry tree. It traverses entry
tree leafs in logical order by rightlinks and removes deletable TIDs from
@@ -301,39 +395,83 @@ are vacuumed in two stages. At first stage, deletable TIDs are removed from
leafs. If first stage detects at least one empty page, then at the second stage
ginScanToDelete() deletes empty pages.
-ginScanToDelete() scans posting tree to delete empty pages, while vacuum holds-cleanup lock on the posting tree root. This lock prevent concurrent inserts,-because inserters hold a pin on the root page. In spite of inserters searches-don't hold pin on root page. So, while new searches cannot begin while root page-is locked, any already-in-progress scans can continue concurrently with vacuum.+ginScanToDelete() traverses the whole tree in depth-first manner. It starts+from the super-exclusive lock on the tree root. This lock prevents all the+concurrent insertions into this tree while we're deleting pages. However,+there are still might be some in-progress readers, who traversed root before+we locked it.++The picture below shows tree state after page deletion algorithm traversed to+leftmost leaf of the tree.-ginScanToDelete() does depth-first tree scanning while keeping each page in path-from root to current page exclusively locked. It also keeps left sibling of-each page in the path locked. Thus, if current page is to be removed, all-required pages to remove both downlink and rightlink are already locked.-Therefore, page deletion locks pages top to bottom and left to right breaking-our general rule. But assuming there is no concurrent insertions, this can't-cause a deadlock.+ aE+ / | \+ bE c d+ / | \ | \ | \+ eE f g h i j k-During replay od page deletion at standby, the page's left sibling, the target-page, and its parent, are locked in that order. So it follows bottom to top and-left to right rule.+Deletion algorithm keeps exclusive locks on left siblings of pages comprising+currently investigated path. Thus, if current page is to be removed, all+required pages to remove both downlink and rightlink are already locked. That+evades potential right to left page locking order, which could deadlock with+concurrent stepping right.
A search concurrent to page deletion might already have read a pointer to the
-page to be deleted, and might be just about to follow it. A page can be reached+page to be deleted, and might be just about to follow it. A page can be reached
via the right-link of its left sibling, or via its downlink in the parent.
-To prevent a backend from reaching a deleted page via a right-link, when-following a right-link the lock on the previous page is not released until the-lock on next page has been acquired.+To prevent a backend from reaching a deleted page via a right-link, stepping+right algorithm doesn't release lock on the current page until lock of the+right page is acquired.-The downlink is more tricky. A search descending the tree must release the lock+The downlink is more tricky. A search descending the tree must release the lock
on the parent page before locking the child, or it could deadlock with a
concurrent split of the child page; a page split locks the parent, while already
-holding a lock on the child page. So, deleted page cannot be reclaimed-immediately. Instead, we have to wait for every transaction, which might wait to-reference this page, to finish. Corresponding processes must observe that the-page is marked deleted and recover accordingly.+holding a lock on the child page. So, deleted page cannot be reclaimed+immediately. Instead, we have to wait for every transaction, which might wait+to reference this page, to finish. Corresponding processes must observe that+the page is marked deleted and recover accordingly.++The picture below shows tree state after page deletion algorithm further+traversed the tree. Currently investigated path is 'a-c-h'. Left siblings 'b'+and 'g' of 'c' and 'h' correspondingly are also exclusively locked.++ aE+ / | \+ bE cE d+ / | \ | \ | \+ e f gE hE i j k++The next picture shows tree state after page 'h' was deleted. It's marked with+'deleted' flag and newest xid, which might visit it. Downlink from 'c' to 'h'+is also deleted.++ aE+ / | \+ bE cE d+ / | \ \ | \+ e f gE hD iE j k++However, it's still possible that concurrent reader has seen downlink from 'c'+to 'h' before we deleted it. In that case this reader will step right from 'h'+to till find non-deleted page. Xid-marking of page 'h' guarantees that this+page wouldn't be reused till all such readers gone. Next leaf page under+investigation is 'i'. 'g' remains locked as it becomes left sibling of 'i'.++The next picture shows tree state after 'i' and 'c' was deleted. Internal page+'c' was deleted because it appeared to have no downlinks. The path under+investigation is 'a-d-j'. Pages 'b' and 'g' are locked as self siblings of 'd'+and 'j'.++ aE+ / \+ bE cD dE+ / | \ | \+ e f gE hD iD jE k++During the replay of page deletion at standby, the page's left sibling, the+target page, and its parent, are locked in that order. This order guarantees+no deadlock with concurrent reads.
Predicate Locking
-----------------
--
2.14.3
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-hackers@postgresql.org
Cc: a.korotkov@postgrespro.ru, pg@bowt.ie, chjischj@163.com, pgsql-hackers@lists.postgresql.org
Subject: Re: Connections hang indefinitely while taking a gin index's LWLock buffer_content lock(PG10.7)
In-Reply-To: <CAPpHfdvtwJbPSRWMfhXfvd4ZMb7GCxc77Su=u9WdTobWZEpvgA@mail.gmail.com>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox