You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@ignite.apache.org by "Ivan Bessonov (Jira)" <ji...@apache.org> on 2021/11/25 07:26:00 UTC
[jira] [Created] (IGNITE-15990) AssertionError in B+Tree under load
Ivan Bessonov created IGNITE-15990:
--------------------------------------
Summary: AssertionError in B+Tree under load
Key: IGNITE-15990
URL: https://issues.apache.org/jira/browse/IGNITE-15990
Project: Ignite
Issue Type: Bug
Components: data structures
Reporter: Ivan Bessonov
Assignee: Ivan Bessonov
Fix For: 2.13
Following exception has occurred in GridGain CE 8.7.29:
{code:java}
class org.apache.ignite.internal.processors.cache.persistence.tree.CorruptedTreeException: B+Tree is corrupted [pages(groupId, pageId)=[IgniteBiTuple [val1=-830802122, val2=844420635165316]], cacheId=-112787658, cacheName=TABLEDSS, indexName=TABLEDSS_TTL_DESC_IDX, msg=Runtime failure on search row: Row@28da1b19[ ... ]
at org.apache.ignite.internal.processors.query.h2.database.H2Tree.corruptedTreeException(H2Tree.java:927)
at org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree.doRemove(BPlusTree.java:2103)
at org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree.removex(BPlusTree.java:1899)
at org.apache.ignite.internal.processors.query.h2.database.H2TreeIndex.removex(H2TreeIndex.java:515)
at org.apache.ignite.internal.processors.query.h2.opt.GridH2Table.remove(GridH2Table.java:822)
at org.apache.ignite.internal.processors.query.h2.IgniteH2Indexing.remove(IgniteH2Indexing.java:420)
at org.apache.ignite.internal.processors.query.GridQueryProcessor.remove(GridQueryProcessor.java:2952)
at org.apache.ignite.internal.processors.cache.query.GridCacheQueryManager.remove(GridCacheQueryManager.java:437)
at org.apache.ignite.internal.processors.cache.IgniteCacheOffheapManagerImpl$CacheDataStoreImpl.finishRemove(IgniteCacheOffheapManagerImpl.java:2703)
at org.apache.ignite.internal.processors.cache.IgniteCacheOffheapManagerImpl$CacheDataStoreImpl.invoke0(IgniteCacheOffheapManagerImpl.java:1727)
at org.apache.ignite.internal.processors.cache.IgniteCacheOffheapManagerImpl$CacheDataStoreImpl.invoke(IgniteCacheOffheapManagerImpl.java:1694)
at org.apache.ignite.internal.processors.cache.persistence.GridCacheOffheapManager$GridCacheDataStore.invoke(GridCacheOffheapManager.java:2643)
at org.apache.ignite.internal.processors.cache.IgniteCacheOffheapManagerImpl.invoke(IgniteCacheOffheapManagerImpl.java:435)
at org.apache.ignite.internal.processors.cache.GridCacheMapEntry.innerUpdate(GridCacheMapEntry.java:2329)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.updateSingle(GridDhtAtomicCache.java:2596)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.update(GridDhtAtomicCache.java:2056)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.updateAllAsyncInternal0(GridDhtAtomicCache.java:1873)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.updateAllAsyncInternal(GridDhtAtomicCache.java:1674)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridNearAtomicAbstractUpdateFuture.sendSingleRequest(GridNearAtomicAbstractUpdateFuture.java:319)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridNearAtomicSingleUpdateFuture.map(GridNearAtomicSingleUpdateFuture.java:496)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridNearAtomicSingleUpdateFuture.mapOnTopology(GridNearAtomicSingleUpdateFuture.java:454)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridNearAtomicAbstractUpdateFuture.map(GridNearAtomicAbstractUpdateFuture.java:267)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.remove0(GridDhtAtomicCache.java:1192)
at org.apache.ignite.internal.processors.cache.distributed.dht.atomic.GridDhtAtomicCache.remove0(GridDhtAtomicCache.java:728)
at org.apache.ignite.internal.processors.cache.GridCacheAdapter.remove(GridCacheAdapter.java:2858)
at org.apache.ignite.internal.processors.cache.GridCacheAdapter.remove(GridCacheAdapter.java:2835)
at org.apache.ignite.internal.processors.cache.IgniteCacheProxyImpl.remove(IgniteCacheProxyImpl.java:1431)
at org.apache.ignite.internal.processors.cache.GatewayProtectedCacheProxy.remove(GatewayProtectedCacheProxy.java:913)
at org.apache.ignite.internal.processors.platform.cache.PlatformCache.processInStreamOutLong(PlatformCache.java:521)
at org.apache.ignite.internal.processors.platform.PlatformTargetProxyImpl.inStreamOutLong(PlatformTargetProxyImpl.java:66)
at org.apache.ignite.internal.processors.platform.callback.PlatformCallbackUtils.inLongOutLong(Native Method)
at org.apache.ignite.internal.processors.platform.callback.PlatformCallbackGateway.computeJobExecute(PlatformCallbackGateway.java:328)
at org.apache.ignite.internal.processors.platform.compute.PlatformClosureJob.execute0(PlatformClosureJob.java:75)
at org.apache.ignite.internal.processors.platform.compute.PlatformAbstractJob.execute(PlatformAbstractJob.java:79)
at org.apache.ignite.internal.processors.job.GridJobWorker$2.call(GridJobWorker.java:570)
at org.apache.ignite.internal.util.IgniteUtils.wrapThreadLoader(IgniteUtils.java:7121)
at org.apache.ignite.internal.processors.job.GridJobWorker.execute0(GridJobWorker.java:564)
at org.apache.ignite.internal.processors.job.GridJobWorker.body(GridJobWorker.java:491)
at org.apache.ignite.internal.util.worker.GridWorker.run(GridWorker.java:119)
at org.apache.ignite.internal.processors.job.GridJobProcessor.processJobExecuteRequest(GridJobProcessor.java:1344)
at org.apache.ignite.internal.processors.job.GridJobProcessor$JobExecutionListener.onMessage(GridJobProcessor.java:2102)
at org.apache.ignite.internal.managers.communication.GridIoManager.invokeListener(GridIoManager.java:1721)
at org.apache.ignite.internal.managers.communication.GridIoManager.processRegularMessage0(GridIoManager.java:1328)
at org.apache.ignite.internal.managers.communication.GridIoManager.access$4600(GridIoManager.java:157)
at org.apache.ignite.internal.managers.communication.GridIoManager$8.execute(GridIoManager.java:1213)
at org.apache.ignite.internal.managers.communication.TraceRunnable.run(TraceRunnable.java:54)
at java.base/java.util.concurrent.ThreadPoolExecutor.runWorker(ThreadPoolExecutor.java:1128)
at java.base/java.util.concurrent.ThreadPoolExecutor$Worker.run(ThreadPoolExecutor.java:628)
at java.base/java.lang.Thread.run(Thread.java:834)
Caused by: java.lang.AssertionError: tail=Tail[pageId=0002ffff00000284, cnt= 1, lvl=2, sibling=null], res=NOT_FOUND
at org.apache.ignite.internal.processors.cache.persistence.tree.BPlusTree.doRemove(BPlusTree.java:2083)
... 47 more {code}
The reason behind it is a broken tree invariant that last leaf item must also be present in one of inner nodes (unless it’s a last element in the entire tree). In the assertion above it’s implied that all inner nodes chain from the leaf to the root have been checked and an item has not been found.
Bug appears when Ignite node experiences slow inserts and very rapid deletions (caused by TTL, for example). Let’s examine the following tree configuration (assuming that 2 items in the node is the max):
{code:java}
[ R:0 ]
/ \
[ X:0 | K:1 ] ...
/ | \
... [ K:1 ] [ R:0 ] {code}
Key {{K}} appears twice in the tree and update {{K=2}} would be performed in two steps: inner node first, leaf node last. Code that does that can be found in {{BPlusTree.Put#found}} method. These is a time gap between these two modifications where none of tree’s pages are locked, and other threads are free to attempt any other tree updates. Corruption happens when other thread tries to remove {{R}} during the gap. Here are tree states during these operations:
{code:java}
// First half of replace operation.
[ R:0 ]
/ \
[ X:0 | K:2 ] ... // Replace happed in inner node at first.
/ | \
... [ K:1 ] [ R:0 ]
// Remove R starts deleting an item from the leaf.
[ R:0 ]
/ \
[ X:0 | K:2 ] ...
/ | \
... [ K:1 ] [ ] // Leaf is empty, merge it about to happen.
// Empty branch is merged with its left neighbour.
[ R:0 ]
/ \
[ X:0 ] ... // K:2 item has been removed during the merge.
/ \
... [ K:1 ]
// R in the root is finally replaced with appropriate item and removal is complete.
[ K:1 ] // K:1 is copied from the leaf as the closest left item.
/ \
[ X:0 ] ...
/ \
... [ K:1 ]
// K:2 thread wakes up and continues updating downwards, changing the value in the leaf. Operation completed.
[ K:1 ]
/ \
[ X:0 ] ...
/ \
... [ K:2 ] {code}
As a result of these events, root points to a nonexistent value {{{}1{}}}, which is most likely an invalid pointer. In case of H2 indexes, everything seems to be working, because actual columns are inlined and the pointer is never read. {{AssertionError}} from the beginning happens when one tries to delete {{{}K{}}}. As a last item in the leaf, it must have a copy in inner node, but it’s not the case since {{K:1}} is not equal to {{{}K:2{}}}.
--
This message was sent by Atlassian Jira
(v8.20.1#820001)