Fixed a bug in the LSMRTree search cursor related to the timing of opening the RTree cursors which can cause deadlocks.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1188 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
index 0a364f2..e746c02 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTree.java
@@ -98,7 +98,7 @@
private final LinkedList<Object> diskComponents = new LinkedList<Object>();
// Helps to guarantees physical consistency of LSM components.
private final ILSMComponentFinalizer componentFinalizer;
-
+
private IBinaryComparatorFactory[] btreeCmpFactories;
private IBinaryComparatorFactory[] rtreeCmpFactories;
@@ -159,7 +159,7 @@
LSMRTreeComponent dummyComponent = new LSMRTreeComponent(dummyRTree, dummyBTree);
List<Object> validFileNames = fileManager.cleanupAndGetValidFiles(dummyComponent, componentFinalizer);
for (Object o : validFileNames) {
- LSMRTreeFileNameComponent component = (LSMRTreeFileNameComponent) o;
+ LSMRTreeFileNameComponent component = (LSMRTreeFileNameComponent) o;
FileReference rtreeFile = new FileReference(new File(component.getRTreeFileName()));
FileReference btreeFile = new FileReference(new File(component.getBTreeFileName()));
RTree rtree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, false);
@@ -187,7 +187,7 @@
memComponent.getBTree().close();
}
- private LSMRTreeFileNameComponent getMergeTargetFileName(List<Object> mergingDiskTrees) throws HyracksDataException {
+ private LSMRTreeFileNameComponent getMergeTargetFileName(List<Object> mergingDiskTrees) throws HyracksDataException {
RTree firstTree = ((LSMRTreeComponent) mergingDiskTrees.get(0)).getRTree();
RTree lastTree = ((LSMRTreeComponent) mergingDiskTrees.get(mergingDiskTrees.size() - 1)).getRTree();
FileReference firstFile = diskFileMapProvider.lookupFileName(firstTree.getFileId());
@@ -197,7 +197,7 @@
return component;
}
- @SuppressWarnings("rawtypes")
+ @SuppressWarnings("rawtypes")
protected ITreeIndex createDiskTree(TreeFactory diskTreeFactory, FileReference fileRef, boolean createTree)
throws HyracksDataException {
// File will be deleted during cleanup of merge().
@@ -217,15 +217,15 @@
@Override
public IIndexBulkLoadContext beginBulkLoad(float fillFactor) throws TreeIndexException, HyracksDataException {
- // Note that by using a flush target file name, we state that the new
+ // Note that by using a flush target file name, we state that the new
// bulk loaded tree is "newer" than any other merged tree.
- LSMRTreeFileNameComponent fileNames = (LSMRTreeFileNameComponent) fileManager.getRelFlushFileName();
- FileReference rtreeFile = fileManager.createFlushFile(fileNames.getRTreeFileName());
+ LSMRTreeFileNameComponent fileNames = (LSMRTreeFileNameComponent) fileManager.getRelFlushFileName();
+ FileReference rtreeFile = fileManager.createFlushFile(fileNames.getRTreeFileName());
RTree diskRTree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, true);
// For each RTree, we require to have a buddy BTree. thus, we create an
// empty BTree.
FileReference btreeFile = fileManager.createFlushFile(fileNames.getBTreeFileName());
- BTree diskBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
+ BTree diskBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
LSMRTreeBulkLoadContext bulkLoadCtx = new LSMRTreeBulkLoadContext(diskRTree, diskBTree);
bulkLoadCtx.beginBulkLoad(fillFactor);
return bulkLoadCtx;
@@ -326,48 +326,31 @@
LSMRTreeOpContext ctx = (LSMRTreeOpContext) ictx;
int numDiskTrees = diskComponents.size();
int numTrees = (includeMemComponent) ? numDiskTrees + 1 : numDiskTrees;
+
+ ITreeIndexAccessor[] rTreeAccessors = new ITreeIndexAccessor[numTrees];
ITreeIndexAccessor[] bTreeAccessors = new ITreeIndexAccessor[numTrees];
- int diskBTreeIx = 0;
+ int diskTreeIx = 0;
if (includeMemComponent) {
+ rTreeAccessors[0] = ctx.memRTreeAccessor;
bTreeAccessors[0] = ctx.memBTreeAccessor;
- diskBTreeIx++;
+ diskTreeIx++;
}
- ListIterator<Object> diskBTreesIter = diskComponents.listIterator();
- while (diskBTreesIter.hasNext()) {
- LSMRTreeComponent component = (LSMRTreeComponent) diskBTreesIter.next();
+ ListIterator<Object> diskTreesIter = diskComponents.listIterator();
+ while (diskTreesIter.hasNext()) {
+ LSMRTreeComponent component = (LSMRTreeComponent) diskTreesIter.next();
+ RTree diskRTree = component.getRTree();
BTree diskBTree = component.getBTree();
- bTreeAccessors[diskBTreeIx] = diskBTree.createAccessor();
- diskBTreeIx++;
+ rTreeAccessors[diskTreeIx] = diskRTree.createAccessor();
+ bTreeAccessors[diskTreeIx] = diskBTree.createAccessor();
+ diskTreeIx++;
}
LSMRTreeSearchCursor lsmRTreeCursor = (LSMRTreeSearchCursor) cursor;
LSMRTreeCursorInitialState initialState = new LSMRTreeCursorInitialState(numTrees, rtreeLeafFrameFactory,
- rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), bTreeAccessors,
- searcherRefCount, includeMemComponent, lsmHarness);
+ rtreeInteriorFrameFactory, btreeLeafFrameFactory, ctx.getBTreeMultiComparator(), rTreeAccessors,
+ bTreeAccessors, searcherRefCount, includeMemComponent, lsmHarness);
lsmRTreeCursor.open(initialState, pred);
-
- int cursorIx;
- if (includeMemComponent) {
- ctx.memRTreeAccessor.search(((LSMRTreeSearchCursor) lsmRTreeCursor).getCursor(0), pred);
- cursorIx = 1;
- } else {
- cursorIx = 0;
- }
-
- // Open cursors of on-disk RTrees
- ITreeIndexAccessor[] diskRTreeAccessors = new ITreeIndexAccessor[numDiskTrees];
- ListIterator<Object> diskRTreesIter = diskComponents.listIterator();
-
- int diskRTreeIx = 0;
- while (diskRTreesIter.hasNext()) {
- LSMRTreeComponent component = (LSMRTreeComponent) diskRTreesIter.next();
- RTree diskRTree = component.getRTree();
- diskRTreeAccessors[diskRTreeIx] = diskRTree.createAccessor();
- diskRTreeAccessors[diskRTreeIx].search(lsmRTreeCursor.getCursor(cursorIx), pred);
- cursorIx++;
- diskRTreeIx++;
- }
}
@Override
@@ -447,7 +430,7 @@
FileReference btreeFile = fileManager.createMergeFile(fileNames.getBTreeFileName());
RTree mergedRTree = (RTree) createDiskTree(diskRTreeFactory, rtreeFile, true);
BTree mergedBTree = (BTree) createDiskTree(diskBTreeFactory, btreeFile, true);
-
+
IIndexBulkLoadContext bulkLoadCtx = mergedRTree.beginBulkLoad(1.0f);
try {
while (cursor.hasNext()) {
@@ -459,11 +442,11 @@
cursor.close();
}
mergedRTree.endBulkLoad(bulkLoadCtx);
-
+
// Load an empty BTree tree.
IIndexBulkLoadContext btreeBulkLoadCtx = mergedBTree.beginBulkLoad(1.0f);
mergedBTree.endBulkLoad(btreeBulkLoadCtx);
-
+
return new LSMRTreeComponent(mergedRTree, mergedBTree);
}
@@ -548,13 +531,13 @@
return rtreeCmpFactories;
}
- @Override
- public IBufferCache getBufferCache() {
- return diskBufferCache;
- }
+ @Override
+ public IBufferCache getBufferCache() {
+ return diskBufferCache;
+ }
- @Override
- public ILSMComponentFinalizer getComponentFinalizer() {
- return componentFinalizer;
- }
+ @Override
+ public ILSMComponentFinalizer getComponentFinalizer() {
+ return componentFinalizer;
+ }
}
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
index f4a00a0..d55ffdb 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeCursorInitialState.java
@@ -31,6 +31,7 @@
private ITreeIndexFrameFactory rtreeLeafFrameFactory;
private ITreeIndexFrameFactory btreeLeafFrameFactory;
private MultiComparator btreeCmp;
+ private ITreeIndexAccessor[] rTreeAccessors;
private ITreeIndexAccessor[] bTreeAccessors;
private AtomicInteger searcherRefCount;
private final boolean includeMemRTree;
@@ -38,13 +39,14 @@
public LSMRTreeCursorInitialState(int numberOfTrees, ITreeIndexFrameFactory rtreeLeafFrameFactory,
ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
- MultiComparator btreeCmp, ITreeIndexAccessor[] bTreeAccessors, AtomicInteger searcherRefCount, boolean includeMemRTree,
- LSMHarness lsmHarness) {
+ MultiComparator btreeCmp, ITreeIndexAccessor[] rTreeAccessors, ITreeIndexAccessor[] bTreeAccessors,
+ AtomicInteger searcherRefCount, boolean includeMemRTree, LSMHarness lsmHarness) {
this.numberOfTrees = numberOfTrees;
this.rtreeLeafFrameFactory = rtreeLeafFrameFactory;
this.rtreeInteriorFrameFactory = rtreeInteriorFrameFactory;
this.btreeLeafFrameFactory = btreeLeafFrameFactory;
this.btreeCmp = btreeCmp;
+ this.rTreeAccessors = rTreeAccessors;
this.bTreeAccessors = bTreeAccessors;
this.searcherRefCount = searcherRefCount;
this.includeMemRTree = includeMemRTree;
@@ -80,6 +82,10 @@
public void setPage(ICachedPage page) {
}
+ public ITreeIndexAccessor[] getRTreeAccessors() {
+ return rTreeAccessors;
+ }
+
public ITreeIndexAccessor[] getBTreeAccessors() {
return bTreeAccessors;
}
@@ -87,13 +93,13 @@
public boolean getIncludeMemRTree() {
return includeMemRTree;
}
-
+
public AtomicInteger getSearcherRefCount() {
- return searcherRefCount;
+ return searcherRefCount;
}
public LSMHarness getLSMHarness() {
return lsmHarness;
}
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
index fa72596..3249f3d 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/LSMRTreeSearchCursor.java
@@ -32,6 +32,7 @@
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeInteriorFrame;
import edu.uci.ics.hyracks.storage.am.rtree.api.IRTreeLeafFrame;
import edu.uci.ics.hyracks.storage.am.rtree.impls.RTreeSearchCursor;
+import edu.uci.ics.hyracks.storage.am.rtree.impls.SearchPredicate;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.buffercache.ICachedPage;
@@ -39,10 +40,12 @@
private RTreeSearchCursor[] rtreeCursors;
private BTreeRangeSearchCursor[] btreeCursors;
+ private ITreeIndexAccessor[] diskRTreeAccessors;
private ITreeIndexAccessor[] diskBTreeAccessors;
private int currentCursror;
private MultiComparator btreeCmp;
private int numberOfTrees;
+ private SearchPredicate rtreeSearchPredicate;
private RangePredicate btreeRangePredicate;
private ITupleReference frameTuple;
private AtomicInteger searcherRefCount;
@@ -64,51 +67,55 @@
foundNext = false;
}
+ private void searchNextCursor() throws HyracksDataException {
+ if (currentCursror < numberOfTrees) {
+ rtreeCursors[currentCursror].reset();
+ try {
+ diskRTreeAccessors[currentCursror].search(rtreeCursors[currentCursror], rtreeSearchPredicate);
+ } catch (TreeIndexException e) {
+ throw new HyracksDataException(e);
+ }
+ }
+ }
+
@Override
public boolean hasNext() throws HyracksDataException {
if (foundNext) {
return true;
}
while (currentCursror < numberOfTrees) {
- try {
- while (rtreeCursors[currentCursror].hasNext()) {
- rtreeCursors[currentCursror].next();
- ITupleReference currentTuple = rtreeCursors[currentCursror].getTuple();
+ while (rtreeCursors[currentCursror].hasNext()) {
+ rtreeCursors[currentCursror].next();
+ ITupleReference currentTuple = rtreeCursors[currentCursror].getTuple();
- boolean killerTupleFound = false;
- for (int i = 0; i <= currentCursror; i++) {
-
- try {
- btreeCursors[i].reset();
- btreeRangePredicate.setHighKey(currentTuple, true);
- btreeRangePredicate.setLowKey(currentTuple, true);
- diskBTreeAccessors[i].search(btreeCursors[i], btreeRangePredicate);
- } catch (TreeIndexException e) {
- throw new HyracksDataException(e);
- }
- try {
- if (btreeCursors[i].hasNext()) {
- killerTupleFound = true;
- break;
- }
- } finally {
- btreeCursors[i].close();
- }
-
+ boolean killerTupleFound = false;
+ for (int i = 0; i <= currentCursror; i++) {
+ try {
+ btreeCursors[i].reset();
+ btreeRangePredicate.setHighKey(currentTuple, true);
+ btreeRangePredicate.setLowKey(currentTuple, true);
+ diskBTreeAccessors[i].search(btreeCursors[i], btreeRangePredicate);
+ } catch (TreeIndexException e) {
+ throw new HyracksDataException(e);
}
- if (!killerTupleFound) {
- frameTuple = currentTuple;
- foundNext = true;
- return true;
+ try {
+ if (btreeCursors[i].hasNext()) {
+ killerTupleFound = true;
+ break;
+ }
+ } finally {
+ btreeCursors[i].close();
}
}
- } finally {
- if (!foundNext) {
- rtreeCursors[currentCursror].close();
+ if (!killerTupleFound) {
+ frameTuple = currentTuple;
+ foundNext = true;
+ return true;
}
}
+ rtreeCursors[currentCursror].close();
currentCursror++;
-
+ searchNextCursor();
}
return false;
}
@@ -126,6 +133,7 @@
includeMemRTree = lsmInitialState.getIncludeMemRTree();
lsmHarness = lsmInitialState.getLSMHarness();
numberOfTrees = lsmInitialState.getNumberOfTrees();
+ diskRTreeAccessors = lsmInitialState.getRTreeAccessors();
diskBTreeAccessors = lsmInitialState.getBTreeAccessors();
rtreeCursors = new RTreeSearchCursor[numberOfTrees];
@@ -139,7 +147,9 @@
btreeCursors[i] = new BTreeRangeSearchCursor((IBTreeLeafFrame) lsmInitialState.getBTreeLeafFrameFactory()
.createFrame(), false);
}
+ rtreeSearchPredicate = (SearchPredicate) searchPred;
btreeRangePredicate = new RangePredicate(null, null, true, true, btreeCmp, btreeCmp);
+ searchNextCursor();
}
@Override
@@ -181,4 +191,4 @@
public boolean exclusiveLatchNodes() {
return false;
}
-}
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
index 0e1dd23..800d64f 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTree.java
@@ -335,7 +335,6 @@
if (!writeLatched) {
node.releaseReadLatch();
readLatched = false;
- // TODO: do we need to un-pin and pin again?
bufferCache.unpin(node);
node = bufferCache.pin(BufferedFileHandle.getDiskPageId(fileId, pageId), false);
@@ -345,8 +344,7 @@
if (ctx.interiorFrame.getPageLsn() != pageLsn) {
// The page was changed while we unlocked it;
- // thus,
- // retry (re-choose best child)
+ // thus, retry (re-choose best child)
ctx.pathList.moveLast();
continue;
diff --git a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
index 0b1722c..c9cbf7e 100644
--- a/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
+++ b/hyracks-storage-am-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/impls/RTreeSearchCursor.java
@@ -78,7 +78,7 @@
}
private boolean fetchNextLeafPage() throws HyracksDataException {
- boolean succeed = false;
+ boolean succeeded = false;
if (readLatched) {
page.releaseReadLatch();
bufferCache.unpin(page);
@@ -125,11 +125,11 @@
page = node;
leafFrame.setPage(page);
tupleIndex = 0;
- succeed = true;
+ succeeded = true;
return true;
}
} finally {
- if (!succeed) {
+ if (!succeeded) {
if (readLatched) {
node.releaseReadLatch();
readLatched = false;
diff --git a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeMultiThreadTest.java b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeMultiThreadTest.java
index ddb8a73..cb5cb59 100644
--- a/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeMultiThreadTest.java
+++ b/hyracks-test-support/src/main/java/edu/uci/ics/hyracks/storage/am/rtree/AbstractRTreeMultiThreadTest.java
@@ -130,7 +130,7 @@
}
}
- //@Test
+ @Test
public void fourDimensionsDouble() throws InterruptedException, HyracksException, TreeIndexException {
ISerializerDeserializer[] fieldSerdes = { DoubleSerializerDeserializer.INSTANCE,
DoubleSerializerDeserializer.INSTANCE, DoubleSerializerDeserializer.INSTANCE,