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

Commite472b92

Browse files
committed
Avoid deadlocks during insertion into SP-GiST indexes.
SP-GiST's original scheme for avoiding deadlocks during concurrent indexinsertions doesn't work, as per report from Hailong Li, and there isn't anyevident way to make it work completely. We could possibly lock individualinner tuples instead of their whole pages, but preliminary experimentationsuggests that the performance penalty would be huge. Instead, if we failto get a buffer lock while descending the tree, just restart the treedescent altogether. We keep the old tuple positioning rules, though, inhopes of reducing the number of cases where this can happen.Teodor Sigaev, somewhat edited by Tom Lane
1 parentc62866e commite472b92

File tree

4 files changed

+71
-18
lines changed

4 files changed

+71
-18
lines changed

‎src/backend/access/spgist/README

Lines changed: 25 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -201,17 +201,31 @@ space utilization, but doesn't change the basis of the algorithm.
201201
CONCURRENCY
202202

203203
While descending the tree, the insertion algorithm holds exclusive lock on
204-
two tree levels at a time, ie both parent and child pages (parent and child
205-
pages can be the same, see notes above). There is a possibility of deadlock
206-
between two insertions if there are cross-referenced pages in different
207-
branches. That is, if inner tuple on page M has a child on page N while
208-
an inner tuple from another branch is on page N and has a child on page M,
209-
then two insertions descending the two branches could deadlock. To prevent
210-
deadlocks we introduce a concept of "triple parity" of pages: if inner tuple
211-
is on page with BlockNumber N, then its child tuples should be placed on the
212-
same page, or else on a page with BlockNumber M where (N+1) mod 3 == M mod 3.
213-
This rule guarantees that tuples on page M will have no children on page N,
214-
since (M+1) mod 3 != N mod 3.
204+
two tree levels at a time, ie both parent and child pages (but parent and
205+
child pages can be the same, see notes above). There is a possibility of
206+
deadlock between two insertions if there are cross-referenced pages in
207+
different branches. That is, if inner tuple on page M has a child on page N
208+
while an inner tuple from another branch is on page N and has a child on
209+
page M, then two insertions descending the two branches could deadlock,
210+
since they will each hold their parent page's lock while trying to get the
211+
child page's lock.
212+
213+
Currently, we deal with this by conditionally locking buffers as we descend
214+
the tree. If we fail to get lock on a buffer, we release both buffers and
215+
restart the insertion process. This is potentially inefficient, but the
216+
locking costs of a more deterministic approach seem very high.
217+
218+
To reduce the number of cases where that happens, we introduce a concept of
219+
"triple parity" of pages: if inner tuple is on page with BlockNumber N, then
220+
its child tuples should be placed on the same page, or else on a page with
221+
BlockNumber M where (N+1) mod 3 == M mod 3. This rule ensures that tuples
222+
on page M will have no children on page N, since (M+1) mod 3 != N mod 3.
223+
That makes it unlikely that two insertion processes will conflict against
224+
each other while descending the tree. It's not perfect though: in the first
225+
place, we could still get a deadlock among three or more insertion processes,
226+
and in the second place, it's impractical to preserve this invariant in every
227+
case when we expand or split an inner tuple. So we still have to allow for
228+
deadlocks.
215229

216230
Insertion may also need to take locks on an additional inner and/or leaf page
217231
to add tuples of the right type(s), when there's not enough room on the pages

‎src/backend/access/spgist/spgdoinsert.c

Lines changed: 30 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1836,9 +1836,13 @@ spgSplitNodeAction(Relation index, SpGistState *state,
18361836
}
18371837

18381838
/*
1839-
* Insert one item into the index
1839+
* Insert one item into the index.
1840+
*
1841+
* Returns true on success, false if we failed to complete the insertion
1842+
* because of conflict with a concurrent insert. In the latter case,
1843+
* caller should re-call spgdoinsert() with the same args.
18401844
*/
1841-
void
1845+
bool
18421846
spgdoinsert(Relationindex,SpGistState*state,
18431847
ItemPointerheapPtr,Datumdatum,boolisnull)
18441848
{
@@ -1927,12 +1931,32 @@ spgdoinsert(Relation index, SpGistState *state,
19271931
&isNew);
19281932
current.blkno=BufferGetBlockNumber(current.buffer);
19291933
}
1930-
elseif (parent.buffer==InvalidBuffer||
1931-
current.blkno!=parent.blkno)
1934+
elseif (parent.buffer==InvalidBuffer)
19321935
{
1936+
/* we hold no parent-page lock, so no deadlock is possible */
19331937
current.buffer=ReadBuffer(index,current.blkno);
19341938
LockBuffer(current.buffer,BUFFER_LOCK_EXCLUSIVE);
19351939
}
1940+
elseif (current.blkno!=parent.blkno)
1941+
{
1942+
/* descend to a new child page */
1943+
current.buffer=ReadBuffer(index,current.blkno);
1944+
1945+
/*
1946+
* Attempt to acquire lock on child page. We must beware of
1947+
* deadlock against another insertion process descending from that
1948+
* page to our parent page (see README). If we fail to get lock,
1949+
* abandon the insertion and tell our caller to start over. XXX
1950+
* this could be improved; perhaps it'd be worth sleeping a bit
1951+
* before giving up?
1952+
*/
1953+
if (!ConditionalLockBuffer(current.buffer))
1954+
{
1955+
ReleaseBuffer(current.buffer);
1956+
UnlockReleaseBuffer(parent.buffer);
1957+
return false;
1958+
}
1959+
}
19361960
else
19371961
{
19381962
/* inner tuple can be stored on the same page as parent one */
@@ -2131,4 +2155,6 @@ spgdoinsert(Relation index, SpGistState *state,
21312155
SpGistSetLastUsedPage(index,parent.buffer);
21322156
UnlockReleaseBuffer(parent.buffer);
21332157
}
2158+
2159+
return true;
21342160
}

‎src/backend/access/spgist/spginsert.c

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,10 @@ spgistBuildCallback(Relation index, HeapTuple htup, Datum *values,
4545
/* Work in temp context, and reset it after each tuple */
4646
oldCtx=MemoryContextSwitchTo(buildstate->tmpCtx);
4747

48-
spgdoinsert(index,&buildstate->spgstate,&htup->t_self,*values,*isnull);
48+
/* No concurrent insertions can be happening, so failure is unexpected */
49+
if (!spgdoinsert(index,&buildstate->spgstate,&htup->t_self,
50+
*values,*isnull))
51+
elog(ERROR,"unexpected spgdoinsert() failure");
4952

5053
MemoryContextSwitchTo(oldCtx);
5154
MemoryContextReset(buildstate->tmpCtx);
@@ -219,7 +222,17 @@ spginsert(PG_FUNCTION_ARGS)
219222

220223
initSpGistState(&spgstate,index);
221224

222-
spgdoinsert(index,&spgstate,ht_ctid,*values,*isnull);
225+
/*
226+
* We might have to repeat spgdoinsert() multiple times, if conflicts
227+
* occur with concurrent insertions. If so, reset the insertCtx each time
228+
* to avoid cumulative memory consumption.That means we also have to
229+
* redo initSpGistState(), but it's cheap enough not to matter.
230+
*/
231+
while (!spgdoinsert(index,&spgstate,ht_ctid,*values,*isnull))
232+
{
233+
MemoryContextReset(insertCtx);
234+
initSpGistState(&spgstate,index);
235+
}
223236

224237
SpGistUpdateMetaPage(index);
225238

‎src/include/access/spgist_private.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -652,7 +652,7 @@ extern void spgPageIndexMultiDelete(SpGistState *state, Page page,
652652
OffsetNumber*itemnos,intnitems,
653653
intfirststate,intreststate,
654654
BlockNumberblkno,OffsetNumberoffnum);
655-
externvoidspgdoinsert(Relationindex,SpGistState*state,
655+
externboolspgdoinsert(Relationindex,SpGistState*state,
656656
ItemPointerheapPtr,Datumdatum,boolisnull);
657657

658658
#endif/* SPGIST_PRIVATE_H */

0 commit comments

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