Repository: asterixdb
Updated Branches:
refs/heads/master 543a4bb72 -> 4cb617a21
[ASTERIXDB-2012][TX] Fix Sporadic double release in btree search
- user model changes: no
- storage format changes: no
- interface changes: no
details:
- LSMBTreeRangeSearchCursor sometimes unlocks twice producing
illegal state exception. This happens if:
1. the proceed call failed (causing instant lock to fail)
2. the lock was acquired and then released. This happens if:
a. the priority queue head was not coming from memory component.
b. the priority queue head was from memory component and it didn't
change when search was re-performed
3. the tuple was found to be antimatter.
- Moreover, locks that are acquired in case the mutable component is not
part of the search anymore are not released until the job completes.
Change-Id: I497ec7c14074390bd6408a3854202159bec5f1cf
Reviewed-on: https://asterix-gerrit.ics.uci.edu/1912
Tested-by: Jenkins <[email protected]>
Contrib: Jenkins <[email protected]>
Integration-Tests: Jenkins <[email protected]>
Reviewed-by: Murtadha Hubail <[email protected]>
Project: http://git-wip-us.apache.org/repos/asf/asterixdb/repo
Commit: http://git-wip-us.apache.org/repos/asf/asterixdb/commit/4cb617a2
Tree: http://git-wip-us.apache.org/repos/asf/asterixdb/tree/4cb617a2
Diff: http://git-wip-us.apache.org/repos/asf/asterixdb/diff/4cb617a2
Branch: refs/heads/master
Commit: 4cb617a216ec3909ce87f8eef7a6c4d355ad1a24
Parents: 543a4bb
Author: Abdullah Alamoudi <[email protected]>
Authored: Thu Aug 3 09:57:41 2017 -0700
Committer: abdullah alamoudi <[email protected]>
Committed: Thu Aug 3 14:30:04 2017 -0700
----------------------------------------------------------------------
.../btree/impls/LSMBTreeRangeSearchCursor.java | 117 +++++++++----------
1 file changed, 54 insertions(+), 63 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/asterixdb/blob/4cb617a2/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
----------------------------------------------------------------------
diff --git
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
index 3b8b160..29d7c60 100644
---
a/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
+++
b/hyracks-fullstack/hyracks/hyracks-storage-am-lsm-btree/src/main/java/org/apache/hyracks/storage/am/lsm/btree/impls/LSMBTreeRangeSearchCursor.java
@@ -20,6 +20,7 @@
package org.apache.hyracks.storage.am.lsm.btree.impls;
import java.util.Iterator;
+import java.util.PriorityQueue;
import org.apache.hyracks.api.exceptions.HyracksDataException;
import org.apache.hyracks.dataflow.common.comm.io.ArrayTupleBuilder;
@@ -49,7 +50,6 @@ public class LSMBTreeRangeSearchCursor extends
LSMIndexSearchCursor {
private BTreeAccessor[] btreeAccessors;
private ArrayTupleBuilder tupleBuilder;
private boolean canCallProceed = true;
- private boolean resultOfSearchCallBackProceed = false;
public LSMBTreeRangeSearchCursor(ILSMIndexOperationContext opCtx) {
this(opCtx, false);
@@ -86,76 +86,55 @@ public class LSMBTreeRangeSearchCursor extends
LSMIndexSearchCursor {
*/
@Override
protected void checkPriorityQueue() throws HyracksDataException {
- while (!outputPriorityQueue.isEmpty() || needPushElementIntoQueue ==
true) {
+ while (!outputPriorityQueue.isEmpty() || needPushElementIntoQueue) {
if (!outputPriorityQueue.isEmpty()) {
- PriorityQueueElement checkElement = outputPriorityQueue.peek();
+ PriorityQueueElement queueHead = outputPriorityQueue.peek();
if (canCallProceed) {
- resultOfSearchCallBackProceed =
searchCallback.proceed(checkElement.getTuple());
- if (!resultOfSearchCallBackProceed) {
- // In case proceed() fails and there is an in-memory
component,
- // we can't simply use this element since there might
be a change.
- if (includeMutableComponent) {
- PriorityQueueElement mutableElement = null;
- boolean mutableElementFound = false;
- // Scans the PQ for the mutable component's
element and delete it
- // since it can be changed.
- // (i.e. we can't ensure that the element is the
most current one.)
- Iterator<PriorityQueueElement> it =
outputPriorityQueue.iterator();
- while (it.hasNext()) {
- mutableElement = it.next();
- if (mutableElement.getCursorIndex() == 0) {
- mutableElementFound = true;
- it.remove();
- break;
- }
- }
- if (mutableElementFound) {
- // Copies the in-memory tuple.
+ // if there are no memory components. no need to lock at
all
+ // since whatever the search reads will never changes
+ if (includeMutableComponent) {
+ if (!searchCallback.proceed(queueHead.getTuple())) {
+ // In case proceed() fails and there is an
in-memory component,
+ // we can't simply use this element since there
might be a change.
+ PriorityQueueElement mutableElement =
removeMutable(outputPriorityQueue);
+ if (mutableElement != null) {
+ // Copies the current queue head
if (tupleBuilder == null) {
tupleBuilder = new
ArrayTupleBuilder(cmp.getKeyFieldCount());
}
- TupleUtils.copyTuple(tupleBuilder,
mutableElement.getTuple(), cmp.getKeyFieldCount());
+ TupleUtils.copyTuple(tupleBuilder,
queueHead.getTuple(), cmp.getKeyFieldCount());
copyTuple.reset(tupleBuilder.getFieldEndOffsets(), tupleBuilder.getByteArray());
-
// Unlatches/unpins the leaf page of the index.
rangeCursors[0].reset();
-
- // Tries to reconcile.
- if (checkElement.getCursorIndex() == 0) {
- searchCallback.reconcile(copyTuple);
- } else {
- // If this element is from the disk
component, we can call complete()
- // after reconcile() since we can
guarantee that there is no change.
-
searchCallback.reconcile(checkElement.getTuple());
-
searchCallback.complete(checkElement.getTuple());
- }
+ // Reconcile.
+ searchCallback.reconcile(copyTuple);
// Re-traverses the index.
reusablePred.setLowKey(copyTuple, true);
btreeAccessors[0].search(rangeCursors[0],
reusablePred);
- boolean isNotExhaustedCursor =
-
pushIntoQueueFromCursorAndReplaceThisElement(mutableElement);
-
- if (checkElement.getCursorIndex() == 0) {
- if (!isNotExhaustedCursor
- || cmp.compare(copyTuple,
mutableElement.getTuple()) != 0) {
- // The searched key no longer exists.
We call cancel() to
- // reverse the effect of reconcile()
method.
- searchCallback.cancel(copyTuple);
- continue;
- }
- // The searched key is still there.
- // TODO: do we need to call or not call
complete() in this case?
- searchCallback.complete(copyTuple);
+ //------
+ includeMutableComponent =
pushIntoQueueFromCursorAndReplaceThisElement(mutableElement);
+ // now that we have completed the search and
we have latches over the pages,
+ // it is safe to complete the operation.. but
as per the API of the callback
+ // we only complete if we're producing this
tuple
+ // get head again
+ queueHead = outputPriorityQueue.peek();
+ /*
+ * We need to restart in one of two cases:
+ * 1. no more elements in the priority queue.
+ * 2. the key of the head has changed (which
means we need to call proceed)
+ */
+ if (queueHead == null ||
cmp.compare(copyTuple, queueHead.getTuple()) != 0) {
+ // cancel since we're not continuing
+ searchCallback.cancel(copyTuple);
+ continue;
}
+ searchCallback.complete(copyTuple);
+ // it is safe to proceed now
} else {
- // The mutable cursor is exhausted and it
couldn't find the element.
- // The failed element did not come from the
in-memory component.
-
searchCallback.reconcile(checkElement.getTuple());
+ // There are no more elements in the memory
component.. can safely skip locking for the
+ // remaining operations
+ includeMutableComponent = false;
}
- } else {
- // proceed() failed. However, there is no
in-memory component.
- // So just call reconcile.
- searchCallback.reconcile(checkElement.getTuple());
}
}
}
@@ -163,14 +142,11 @@ public class LSMBTreeRangeSearchCursor extends
LSMIndexSearchCursor {
// If there is no previous tuple or the previous tuple can be
ignored.
// This check is needed not to release the same tuple again.
if (outputElement == null) {
- if (isDeleted(checkElement) && !returnDeletedTuples) {
+ if (isDeleted(queueHead) && !returnDeletedTuples) {
// If the key has been deleted then pop it and set
needPush to true.
// We cannot push immediately because the tuple may be
// modified if hasNext() is called
outputElement = outputPriorityQueue.poll();
- if (!resultOfSearchCallBackProceed) {
- searchCallback.cancel(checkElement.getTuple());
- }
needPushElementIntoQueue = true;
canCallProceed = false;
} else {
@@ -178,12 +154,11 @@ public class LSMBTreeRangeSearchCursor extends
LSMIndexSearchCursor {
}
} else {
// Compare the previous tuple and the head tuple in the PQ
- if (compare(cmp, outputElement.getTuple(),
checkElement.getTuple()) == 0) {
+ if (compare(cmp, outputElement.getTuple(),
queueHead.getTuple()) == 0) {
// If the previous tuple and the head tuple are
// identical
// then pop the head tuple and push the next tuple from
// the tree of head tuple
-
// the head element of PQ is useless now
PriorityQueueElement e = outputPriorityQueue.poll();
pushIntoQueueFromCursorAndReplaceThisElement(e);
@@ -206,6 +181,22 @@ public class LSMBTreeRangeSearchCursor extends
LSMIndexSearchCursor {
canCallProceed = true;
}
}
+
+ }
+
+ private PriorityQueueElement
removeMutable(PriorityQueue<PriorityQueueElement> outputPriorityQueue) {
+ // Scans the PQ for the mutable component's element and delete it
+ // since it can be changed.
+ // (i.e. we can't ensure that the element is the most current one.)
+ Iterator<PriorityQueueElement> it = outputPriorityQueue.iterator();
+ while (it.hasNext()) {
+ PriorityQueueElement mutableElement = it.next();
+ if (mutableElement.getCursorIndex() == 0) {
+ it.remove();
+ return mutableElement;
+ }
+ }
+ return null;
}
@Override
