Implemented new file naming scheme for LSM indexes based on timestamp intervals. Relying on the file names alone, an LSM index can always determine whether an LSM component is valid or not. Still TODO: Implement flushing/merging into a temp file, followed by an atomic rename upon success.
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1143 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-api/src/main/java/edu/uci/ics/hyracks/api/io/FileReference.java b/hyracks-api/src/main/java/edu/uci/ics/hyracks/api/io/FileReference.java
index 9e27077..b1a5008 100644
--- a/hyracks-api/src/main/java/edu/uci/ics/hyracks/api/io/FileReference.java
+++ b/hyracks-api/src/main/java/edu/uci/ics/hyracks/api/io/FileReference.java
@@ -31,7 +31,7 @@
}
public File getFile() {
- return file;
+ return file;
}
@Override
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
index ae7eb51..cec8f76 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/impls/LSMBTree.java
@@ -16,9 +16,6 @@
package edu.uci.ics.hyracks.storage.am.lsm.btree.impls;
import java.io.File;
-import java.io.FilenameFilter;
-import java.util.Arrays;
-import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
@@ -46,7 +43,7 @@
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTree;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMHarness;
@@ -64,7 +61,7 @@
private final InMemoryFreePageManager memFreePageManager;
// On-disk components.
- private final ILSMFileNameManager fileNameManager;
+ private final ILSMFileManager fileManager;
// For creating BTree's used in flush and merge.
private final BTreeFactory diskBTreeFactory;
// For creating BTree's used in bulk load. Different from diskBTreeFactory
@@ -82,7 +79,7 @@
public LSMBTree(IBufferCache memBufferCache, InMemoryFreePageManager memFreePageManager,
ITreeIndexFrameFactory interiorFrameFactory, ITreeIndexFrameFactory insertLeafFrameFactory,
- ITreeIndexFrameFactory deleteLeafFrameFactory, ILSMFileNameManager fileNameManager, BTreeFactory diskBTreeFactory,
+ ITreeIndexFrameFactory deleteLeafFrameFactory, ILSMFileManager fileNameManager, BTreeFactory diskBTreeFactory,
BTreeFactory bulkLoadBTreeFactory, IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] cmpFactories) {
memBTree = new BTree(memBufferCache, fieldCount, cmpFactories, memFreePageManager, interiorFrameFactory,
insertLeafFrameFactory);
@@ -95,7 +92,7 @@
this.bulkLoadBTreeFactory = bulkLoadBTreeFactory;
this.cmpFactories = cmpFactories;
this.diskBTrees = new LinkedList<Object>();
- this.fileNameManager = fileNameManager;
+ this.fileManager = fileNameManager;
lsmHarness = new LSMHarness(this);
}
@@ -123,19 +120,8 @@
@Override
public void open(int indexFileId) throws HyracksDataException {
memBTree.open(indexFileId);
- File dir = new File(fileNameManager.getBaseDir());
- FilenameFilter filter = new FilenameFilter() {
- public boolean accept(File dir, String name) {
- return !name.startsWith(".");
- }
- };
- String[] files = dir.list(filter);
- if (files == null) {
- return;
- }
- Comparator<String> fileNameCmp = fileNameManager.getFileNameComparator();
- Arrays.sort(files, fileNameCmp);
- for (String fileName : files) {
+ List<String> validFileNames = fileManager.cleanupAndGetValidFiles();
+ for (String fileName : validFileNames) {
BTree btree = createDiskBTree(diskBTreeFactory, fileName, false);
diskBTrees.add(btree);
}
@@ -292,17 +278,21 @@
private BTree bulkLoadTargetBTree() throws HyracksDataException {
// Note that by using a flush target file name, we state that the new
// bulk loaded tree is "newer" than any other merged tree.
- String fileName = fileNameManager.getFlushFileName();
+ String fileName = fileManager.getFlushFileName();
return createDiskBTree(bulkLoadBTreeFactory, fileName, true);
}
private BTree createFlushTargetBTree() throws HyracksDataException {
- String fileName = fileNameManager.getFlushFileName();
+ String fileName = fileManager.getFlushFileName();
return createDiskBTree(diskBTreeFactory, fileName, true);
}
- private BTree createMergeTargetBTree() throws HyracksDataException {
- String fileName = fileNameManager.getMergeFileName();
+ private BTree createMergeTargetBTree(List<Object> mergingDiskBTrees) throws HyracksDataException {
+ BTree firstBTree = (BTree) mergingDiskBTrees.get(0);
+ BTree lastBTree = (BTree) mergingDiskBTrees.get(mergingDiskBTrees.size() - 1);
+ FileReference firstFile = diskFileMapProvider.lookupFileName(firstBTree.getFileId());
+ FileReference lastFile = diskFileMapProvider.lookupFileName(lastBTree.getFileId());
+ String fileName = fileManager.getMergeFileName(firstFile.getFile().getName(), lastFile.getFile().getName());
return createDiskBTree(diskBTreeFactory, fileName, true);
}
@@ -368,7 +358,7 @@
mergedComponents.addAll(mergingDiskBTrees);
// Bulk load the tuples from all on-disk BTrees into the new BTree.
- BTree mergedBTree = createMergeTargetBTree();
+ BTree mergedBTree = createMergeTargetBTree(mergedComponents);
IIndexBulkLoadContext bulkLoadCtx = mergedBTree.beginBulkLoad(1.0f);
try {
while (cursor.hasNext()) {
diff --git a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
index 23f986a..a440f04 100644
--- a/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
+++ b/hyracks-storage-am-lsm-btree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/btree/util/LSMBTreeUtils.java
@@ -27,10 +27,10 @@
import edu.uci.ics.hyracks.storage.am.lsm.btree.impls.LSMBTree;
import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeCopyTupleWriterFactory;
import edu.uci.ics.hyracks.storage.am.lsm.btree.tuples.LSMBTreeTupleWriterFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
-import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileManager;
import edu.uci.ics.hyracks.storage.common.buffercache.IBufferCache;
import edu.uci.ics.hyracks.storage.common.file.IFileMapProvider;
@@ -55,7 +55,7 @@
typeTraits.length, interiorFrameFactory, copyTupleLeafFrameFactory);
BTreeFactory bulkLoadBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, cmpFactories,
typeTraits.length, interiorFrameFactory, insertLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMBTree lsmTree = new LSMBTree(memBufferCache, memFreePageManager, interiorFrameFactory,
insertLeafFrameFactory, deleteLeafFrameFactory, fileNameManager, diskBTreeFactory,
bulkLoadBTreeFactory, diskFileMapProvider, typeTraits.length, cmpFactories);
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileNameManager.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileManager.java
similarity index 67%
rename from hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileNameManager.java
rename to hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileManager.java
index c48c48e..752d2bd 100644
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileNameManager.java
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/api/ILSMFileManager.java
@@ -16,9 +16,12 @@
package edu.uci.ics.hyracks.storage.am.lsm.common.api;
import java.util.Comparator;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
/**
- * Provides file names for LSM on-disk components.
+ * Provides file names for LSM on-disk components. Also cleans up invalid files.
*
* There are separate methods to get file names for merge and flush, because we
* need to guarantee the correct order of on-disk components (i.e., the
@@ -27,12 +30,16 @@
*
*
*/
-public interface ILSMFileNameManager {
+public interface ILSMFileManager {
public String getFlushFileName();
- public String getMergeFileName();
+ public String getMergeFileName(String firstFileName, String lastFileName) throws HyracksDataException;
public String getBaseDir();
+ // Deletes invalid files, and returns list of valid files from baseDir.
+ // The returned valid files are correctly sorted (based on the recency of data).
+ public List<String> cleanupAndGetValidFiles() throws HyracksDataException;
+
public Comparator<String> getFileNameComparator();
}
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileManager.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileManager.java
new file mode 100644
index 0000000..e44e6e5
--- /dev/null
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileManager.java
@@ -0,0 +1,154 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.lsm.common.impls;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.text.Format;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Date;
+import java.util.List;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
+
+public class LSMTreeFileManager implements ILSMFileManager {
+
+ private static final String SPLIT_STRING = "_";
+
+ private final String baseDir;
+ private final Format formatter = new SimpleDateFormat("yyyy-MM-dd-HH-mm-ss-SSS");
+ private final Comparator<String> cmp = new FileNameComparator();
+ private final Comparator<String[]> intervalCmp = new IntervalComparator();
+
+ public LSMTreeFileManager(String baseDir) {
+ if (!baseDir.endsWith(System.getProperty("file.separator"))) {
+ baseDir += System.getProperty("file.separator");
+ }
+ this.baseDir = baseDir;
+ }
+
+ @Override
+ public String getFlushFileName() {
+ Date date = new Date();
+ String ts = formatter.format(date);
+ // Begin timestamp and end timestamp are identical.
+ return baseDir + ts + SPLIT_STRING + ts;
+ }
+
+ @Override
+ public String getMergeFileName(String firstFileName, String lastFileName) throws HyracksDataException {
+ String[] firstTimestampRange = firstFileName.split(SPLIT_STRING);
+ String[] lastTimestampRange = lastFileName.split(SPLIT_STRING);
+ // Enclosing timestamp range.
+ return baseDir + firstTimestampRange[0] + SPLIT_STRING + lastTimestampRange[1];
+ }
+
+ @Override
+ public Comparator<String> getFileNameComparator() {
+ return cmp;
+ }
+
+ /**
+ * Sorts strings in reverse lexicographical order. The way we construct the
+ * file names above guarantees that:
+ *
+ * 1. Flushed files (sort lower than merged files
+ *
+ * 2. Flushed files are sorted from newest to oldest (based on the timestamp
+ * string)
+ *
+ */
+ private class FileNameComparator implements Comparator<String> {
+ @Override
+ public int compare(String a, String b) {
+ // Consciously ignoring locale.
+ return -a.compareTo(b);
+ }
+ }
+
+ private class IntervalComparator implements Comparator<String[]> {
+ @Override
+ public int compare(String[] a, String[] b) {
+ int startCmp = a[0].compareTo(b[0]);
+ if (startCmp != 0) {
+ return startCmp;
+ }
+ return b[1].compareTo(a[1]);
+ }
+ }
+
+ @Override
+ public String getBaseDir() {
+ return baseDir;
+ }
+
+ @Override
+ public List<String> cleanupAndGetValidFiles() throws HyracksDataException {
+ List<String> validFiles = new ArrayList<String>();
+ File dir = new File(baseDir);
+ FilenameFilter filter = new FilenameFilter() {
+ public boolean accept(File dir, String name) {
+ return !name.startsWith(".");
+ }
+ };
+ String[] files = dir.list(filter);
+ // Trivial cases.
+ if (files == null) {
+ return validFiles;
+ }
+ if (files.length == 1) {
+ validFiles.add(files[0]);
+ return validFiles;
+ }
+
+ List<String[]> intervals = new ArrayList<String[]>();
+ for (String fileName : files) {
+ intervals.add(fileName.split(SPLIT_STRING));
+ }
+ // Sorts files from earliest to latest timestamp.
+ Collections.sort(intervals, intervalCmp);
+
+ String[] lastInterval = intervals.get(0);
+ validFiles.add(getFileNameFromInterval(intervals.get(0)));
+ for (int i = 1; i < intervals.size(); i++) {
+ String[] currentInterval = intervals.get(i);
+ // Current start timestamp is greater than last stop timestamp.
+ if (currentInterval[0].compareTo(lastInterval[1]) > 0) {
+ validFiles.add(getFileNameFromInterval(currentInterval));
+ lastInterval = currentInterval;
+ } else if (currentInterval[0].compareTo(lastInterval[0]) >= 0
+ && currentInterval[1].compareTo(lastInterval[1]) <= 0) {
+ // Invalid files are completely contained in last interval.
+ File invalidFile = new File(getFileNameFromInterval(currentInterval));
+ invalidFile.delete();
+ } else {
+ // This scenario should not be possible.
+ throw new HyracksDataException("Found LSM files with overlapping but not contained timetamp intervals.");
+ }
+ }
+ // Sort valid files in reverse lexicographical order, such that newer files come first.
+ Collections.sort(validFiles, cmp);
+ return validFiles;
+ }
+
+ private String getFileNameFromInterval(String[] interval) {
+ return baseDir + interval[0] + SPLIT_STRING + interval[1];
+ }
+}
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileNameManager.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileNameManager.java
deleted file mode 100644
index 628fbf3..0000000
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/impls/LSMTreeFileNameManager.java
+++ /dev/null
@@ -1,79 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * you may obtain a copy of the License from
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package edu.uci.ics.hyracks.storage.am.lsm.common.impls;
-
-import java.text.Format;
-import java.text.SimpleDateFormat;
-import java.util.Comparator;
-import java.util.Date;
-
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
-
-public class LSMTreeFileNameManager implements ILSMFileNameManager {
-
- private final String baseDir;
- private final Format formatter = new SimpleDateFormat("yyyy_MM_dd_HH_mm_ss_SSS");
- private final Comparator<String> cmp = new FileNameComparator();
-
- public LSMTreeFileNameManager(String baseDir) {
- if (!baseDir.endsWith(System.getProperty("file.separator"))) {
- baseDir += System.getProperty("file.separator");
- }
- this.baseDir = baseDir;
- }
-
- @Override
- public String getFlushFileName() {
- Date date = new Date();
- // "Z" prefix to indicate flush. Relies on "Z" sorting higher than "A".
- return baseDir + "Z" + formatter.format(date);
- }
-
- @Override
- public String getMergeFileName() {
- Date date = new Date();
- // "A" prefix to indicate merge. Relies on "A" sorting lower than "Z".
- return baseDir + "A" + formatter.format(date);
- }
-
- @Override
- public Comparator<String> getFileNameComparator() {
- return cmp;
- }
-
- /**
- * Sorts strings in reverse lexicographical order. The way we construct the
- * file names above guarantees that:
- *
- * 1. Flushed files ("Z" prefix) sort lower than merged files ("A" prefix)
- *
- * 2. Flushed files are sorted from newest to oldest (based on the timestamp
- * string)
- *
- */
- private class FileNameComparator implements Comparator<String> {
- @Override
- public int compare(String a, String b) {
- // Consciously ignoring locale.
- return -a.compareTo(b);
- }
- }
-
- @Override
- public String getBaseDir() {
- return baseDir;
- }
-}
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 17fcc3d..dc37aeb 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
@@ -43,7 +43,7 @@
import edu.uci.ics.hyracks.storage.am.common.api.IndexType;
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.IndexOp;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMTree;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
@@ -86,7 +86,7 @@
private final static int MEM_BTREE_FILE_ID = 1;
// On-disk components.
- private final ILSMFileNameManager fileNameManager;
+ private final ILSMFileManager fileNameManager;
protected final IBufferCache diskBufferCache;
protected final IFileMapProvider diskFileMapProvider;
// For creating RTree's used in flush and merge.
@@ -109,7 +109,7 @@
public LSMRTree(IBufferCache memBufferCache, InMemoryFreePageManager memFreePageManager,
ITreeIndexFrameFactory rtreeInteriorFrameFactory, ITreeIndexFrameFactory rtreeLeafFrameFactory,
ITreeIndexFrameFactory btreeInteriorFrameFactory, ITreeIndexFrameFactory btreeLeafFrameFactory,
- ILSMFileNameManager fileNameManager, RTreeFactory diskRTreeFactory, BTreeFactory diskBTreeFactory,
+ ILSMFileManager fileNameManager, RTreeFactory diskRTreeFactory, BTreeFactory diskBTreeFactory,
IFileMapProvider diskFileMapProvider, int fieldCount, IBinaryComparatorFactory[] rtreeCmpFactories,
IBinaryComparatorFactory[] btreeCmpFactories) {
RTree memRTree = new RTree(memBufferCache, fieldCount, rtreeCmpFactories, memFreePageManager,
@@ -156,7 +156,8 @@
*/
@Override
public void open(int indexFileId) throws HyracksDataException {
- memComponent.getRTree().open(MEM_RTREE_FILE_ID);
+ // TODO: Port to new naming scheme.
+ memComponent.getRTree().open(MEM_RTREE_FILE_ID);
memComponent.getBTree().open(MEM_BTREE_FILE_ID);
File dir = new File(fileNameManager.getBaseDir());
FilenameFilter rtreeFilter = new FilenameFilter() {
@@ -437,7 +438,8 @@
mergedComponents.addAll(mergingComponents);
// Bulk load the tuples from all on-disk RTrees into the new RTree.
- String fileName = fileNameManager.getMergeFileName();
+ // TODO: Passing dummy values for now. Switch to naming scheme.
+ String fileName = fileNameManager.getMergeFileName("dummy", "dummy");
RTree mergedRTree = (RTree) createDiskTree(diskRTreeFactory, fileName + "-rtree", true);
BTree mergedBTree = (BTree) createDiskTree(diskBTreeFactory, fileName + "-btree", true);
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
index d2e2e4f..4ec80e0 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/utils/LSMRTreeUtils.java
@@ -24,11 +24,11 @@
import edu.uci.ics.hyracks.storage.am.common.api.ITreeIndexMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryBufferCache;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.RTreeFactory;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.tuples.LSMTypeAwareTupleWriterFactory;
@@ -63,7 +63,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories,
typeTraits.length, btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, typeTraits.length, rtreeCmpFactories,
diff --git a/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileManagerTest.java b/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileManagerTest.java
new file mode 100644
index 0000000..f2964c9
--- /dev/null
+++ b/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileManagerTest.java
@@ -0,0 +1,196 @@
+/*
+ * Copyright 2009-2010 by The Regents of the University of California
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * you may obtain a copy of the License from
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package edu.uci.ics.hyracks.storage.am.lsm.common;
+
+import static org.junit.Assert.assertEquals;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.io.IOException;
+import java.text.SimpleDateFormat;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.Date;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.junit.After;
+import org.junit.Before;
+import org.junit.Test;
+
+import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileManager;
+
+public class LSMTreeFileManagerTest {
+ protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
+ protected final static String tmpDir = System.getProperty("java.io.tmpdir");
+ protected final static String sep = System.getProperty("file.separator");
+ protected String baseDir;
+
+ @Before
+ public void setUp() throws HyracksDataException {
+ baseDir = tmpDir + sep + "lsm_tree" + simpleDateFormat.format(new Date()) + sep;
+ File f = new File(baseDir);
+ f.mkdirs();
+ }
+
+ @After
+ public void tearDown() throws HyracksDataException {
+ baseDir = tmpDir + sep + "lsm_tree" + simpleDateFormat.format(new Date()) + sep;
+ File f = new File(baseDir);
+ f.deleteOnExit();
+ }
+
+ public void sortOrderTest(boolean testFlushFileName) throws InterruptedException, HyracksDataException {
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(baseDir);
+ LinkedList<String> fileNames = new LinkedList<String>();
+
+ int numFileNames = 100;
+ long sleepTime = 5;
+ for (int i = 0; i < numFileNames; i++) {
+ String flushFileName = fileNameManager.getFlushFileName();
+ if (testFlushFileName) {
+ fileNames.addFirst(flushFileName);
+ }
+ Thread.sleep(sleepTime);
+ if (!testFlushFileName) {
+ String secondFlushFileName = fileNameManager.getFlushFileName();
+ String mergeFileName = getMergeFileName(fileNameManager, flushFileName, secondFlushFileName);
+ fileNames.addFirst(mergeFileName);
+ Thread.sleep(sleepTime);
+ }
+ }
+
+ List<String> sortedFileNames = new ArrayList<String>();
+ sortedFileNames.addAll(fileNames);
+
+ // Make sure the comparator sorts in the correct order (i.e., the
+ // reverse insertion order in this case).
+ Comparator<String> cmp = fileNameManager.getFileNameComparator();
+ Collections.sort(sortedFileNames, cmp);
+ for (int i = 0; i < numFileNames; i++) {
+ assertEquals(fileNames.get(i), sortedFileNames.get(i));
+ }
+ }
+
+ //@Test
+ public void flushAndMergeFilesSortOrderTest() throws InterruptedException, HyracksDataException {
+ sortOrderTest(true);
+ sortOrderTest(false);
+ }
+
+ @Test
+ public void cleanInvalidFilesTest() throws InterruptedException, IOException {
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(baseDir);
+ List<String> flushFileNames = new ArrayList<String>();
+ List<String> allFiles = new ArrayList<String>();
+
+ int numFileNames = 100;
+ long sleepTime = 5;
+ // Generate a bunch of flush files.
+ for (int i = 0; i < numFileNames; i++) {
+ String flushFileName = fileNameManager.getFlushFileName();
+ flushFileNames.add(flushFileName);
+ Thread.sleep(sleepTime);
+ }
+ allFiles.addAll(flushFileNames);
+
+ // Simulate merging some of the flush files.
+ // Merge range 0 to 4.
+ String mergeFile1 = getMergeFileName(fileNameManager, flushFileNames.get(0), flushFileNames.get(4));
+ allFiles.add(mergeFile1);
+ // Merge range 5 to 9.
+ String mergeFile2 = getMergeFileName(fileNameManager, flushFileNames.get(5), flushFileNames.get(9));
+ allFiles.add(mergeFile2);
+ // Merge range 10 to 19.
+ String mergeFile3 = getMergeFileName(fileNameManager, flushFileNames.get(10), flushFileNames.get(19));
+ allFiles.add(mergeFile3);
+ // Merge range 20 to 29.
+ String mergeFile4 = getMergeFileName(fileNameManager, flushFileNames.get(20), flushFileNames.get(29));
+ allFiles.add(mergeFile4);
+ // Merge range 50 to 79.
+ String mergeFile5 = getMergeFileName(fileNameManager, flushFileNames.get(50), flushFileNames.get(79));
+ allFiles.add(mergeFile5);
+
+ // Simulate merging of merge files.
+ String mergeFile6 = getMergeFileName(fileNameManager, mergeFile1, mergeFile2);
+ allFiles.add(mergeFile6);
+ String mergeFile7 = getMergeFileName(fileNameManager, mergeFile3, mergeFile4);
+ allFiles.add(mergeFile7);
+
+ // Create all files.
+ for (String fileName : allFiles) {
+ File f = new File(fileName);
+ f.createNewFile();
+ f.deleteOnExit();
+ }
+
+ // Populate expected valid flush files.
+ List<String> expectedValidFiles = new ArrayList<String>();
+ for (int i = 30; i < 50; i++) {
+ expectedValidFiles.add(flushFileNames.get(i));
+ }
+ for (int i = 80; i < 100; i++) {
+ expectedValidFiles.add(flushFileNames.get(i));
+ }
+
+ // Populate expected valid merge files.
+ expectedValidFiles.add(mergeFile5);
+ expectedValidFiles.add(mergeFile6);
+ expectedValidFiles.add(mergeFile7);
+
+ // Sort expected files.
+ Collections.sort(expectedValidFiles, fileNameManager.getFileNameComparator());
+
+ List<String> validFiles = fileNameManager.cleanupAndGetValidFiles();
+
+ // Check actual files against expected files.
+ assertEquals(expectedValidFiles.size(), validFiles.size());
+ for (int i = 0; i < expectedValidFiles.size(); i++) {
+ assertEquals(expectedValidFiles.get(i), validFiles.get(i));
+ }
+
+ // Make sure invalid files were removed from baseDir.
+ File dir = new File(baseDir);
+ FilenameFilter filter = new FilenameFilter() {
+ public boolean accept(File dir, String name) {
+ return !name.startsWith(".");
+ }
+ };
+ String[] files = dir.list(filter);
+ Arrays.sort(files, fileNameManager.getFileNameComparator());
+ // Check actual files in directory against expected files.
+ assertEquals(expectedValidFiles.size(), files.length);
+ for (int i = 0; i < expectedValidFiles.size(); i++) {
+ assertEquals(expectedValidFiles.get(i), baseDir + files[i]);
+ }
+
+ // Cleanup.
+ for (String fileName : files) {
+ File f = new File(fileName);
+ f.deleteOnExit();
+ }
+ }
+
+ private String getMergeFileName(ILSMFileManager fileNameManager, String firstFile, String lastFile) throws HyracksDataException {
+ File f1 = new File(firstFile);
+ File f2 = new File(lastFile);
+ return fileNameManager.getMergeFileName(f1.getName(), f2.getName());
+ }
+}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileNameManagerTest.java b/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileNameManagerTest.java
deleted file mode 100644
index d43f34f..0000000
--- a/hyracks-tests/hyracks-storage-am-lsm-common-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/common/LSMTreeFileNameManagerTest.java
+++ /dev/null
@@ -1,125 +0,0 @@
-/*
- * Copyright 2009-2010 by The Regents of the University of California
- * Licensed under the Apache License, Version 2.0 (the "License");
- * you may not use this file except in compliance with the License.
- * you may obtain a copy of the License from
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
- */
-
-package edu.uci.ics.hyracks.storage.am.lsm.common;
-
-import static org.junit.Assert.assertEquals;
-import static org.junit.Assert.fail;
-
-import java.text.SimpleDateFormat;
-import java.util.ArrayList;
-import java.util.Collections;
-import java.util.Comparator;
-import java.util.Date;
-import java.util.HashSet;
-import java.util.LinkedList;
-import java.util.List;
-
-import org.junit.Before;
-import org.junit.Test;
-
-import edu.uci.ics.hyracks.api.exceptions.HyracksDataException;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
-import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
-
-public class LSMTreeFileNameManagerTest {
- protected final static SimpleDateFormat simpleDateFormat = new SimpleDateFormat("ddMMyy-hhmmssSS");
- protected final static String tmpDir = System.getProperty("java.io.tmpdir");
- protected final static String sep = System.getProperty("file.separator");
- protected String baseDir;
-
- @Before
- public void setUp() throws HyracksDataException {
- baseDir = tmpDir + sep + "lsm_tree" + simpleDateFormat.format(new Date()) + sep;
- }
-
- public void flushFileNamesTest(boolean testFlushFileName) throws InterruptedException {
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(baseDir);
- LinkedList<String> fileNames = new LinkedList<String>();
-
- int numFileNames = 100;
- long sleepTime = 5;
- for (int i = 0; i < numFileNames; i++) {
- String fileName = null;
- if (testFlushFileName) {
- fileName = fileNameManager.getFlushFileName();
- } else {
- fileName = fileNameManager.getMergeFileName();
- }
- fileNames.addFirst(fileName);
- Thread.sleep(sleepTime);
- }
-
- List<String> sortedFileNames = new ArrayList<String>();
- sortedFileNames.addAll(fileNames);
-
- // Make sure the comparator sorts in the correct order (i.e., the
- // reverse insertion order in this case).
- Comparator<String> cmp = fileNameManager.getFileNameComparator();
- Collections.sort(sortedFileNames, cmp);
- for (int i = 0; i < numFileNames; i++) {
- assertEquals(fileNames.get(i), sortedFileNames.get(i));
- }
- }
-
- @Test
- public void individualFileNamesTest() throws InterruptedException {
- flushFileNamesTest(true);
- flushFileNamesTest(false);
- }
-
- @Test
- public void mixedFileNamesTest() throws InterruptedException {
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(baseDir);
- List<String> fileNames = new ArrayList<String>();
- HashSet<String> flushFileNames = new HashSet<String>();
- HashSet<String> mergeFileNames = new HashSet<String>();
-
- int numFileNames = 100;
- long sleepTime = 5;
- for (int i = 0; i < numFileNames; i++) {
- String fileName = null;
- if (i % 2 == 0) {
- fileName = fileNameManager.getFlushFileName();
- flushFileNames.add(fileName);
- } else {
- fileName = fileNameManager.getMergeFileName();
- mergeFileNames.add(fileName);
- }
- fileNames.add(fileName);
- Thread.sleep(sleepTime);
- }
-
- // Make sure the comparator sorts in the correct order.
- // We only need to check whether the flushed files and merged files are
- // clustered.
- // We verified the secondary sort order (based on timestamp) in the
- // individualFileNamesTest().
- Comparator<String> cmp = fileNameManager.getFileNameComparator();
- Collections.sort(fileNames, cmp);
- // We expect flush file names at the front.
- int i = 0;
- while (flushFileNames.contains(fileNames.get(i))) {
- i++;
- }
- // We expect only merge file names from here on.
- while (i < numFileNames) {
- if (!mergeFileNames.contains(fileNames.get(i))) {
- fail("Expected a merge file name at position: " + i);
- }
- i++;
- }
- }
-}
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeSerachTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeSerachTest.java
index d7eec38..d004073 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeSerachTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeSerachTest.java
@@ -52,10 +52,10 @@
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
import edu.uci.ics.hyracks.storage.am.common.ophelpers.MultiComparator;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeInMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeSearchCursor;
@@ -127,7 +127,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories, fieldCount,
btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmRTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories);
diff --git a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeTest.java b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeTest.java
index 5a57386..f4f72ea 100644
--- a/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeTest.java
+++ b/hyracks-tests/hyracks-storage-am-lsm-rtree-test/src/test/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/LSMRTreeTest.java
@@ -45,10 +45,10 @@
import edu.uci.ics.hyracks.storage.am.common.api.TreeIndexException;
import edu.uci.ics.hyracks.storage.am.common.frames.LIFOMetaDataFrameFactory;
import edu.uci.ics.hyracks.storage.am.common.freepage.LinkedListFreePageManagerFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.api.ILSMFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.freepage.InMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.common.impls.BTreeFactory;
-import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileNameManager;
+import edu.uci.ics.hyracks.storage.am.lsm.common.impls.LSMTreeFileManager;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTree;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.LSMRTreeInMemoryFreePageManager;
import edu.uci.ics.hyracks.storage.am.lsm.rtree.impls.RTreeFactory;
@@ -121,7 +121,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories, fieldCount,
btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmRTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories);
@@ -267,7 +267,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories, fieldCount,
btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmRTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories);
@@ -464,7 +464,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories, fieldCount,
btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmRTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories);
@@ -615,7 +615,7 @@
BTreeFactory diskBTreeFactory = new BTreeFactory(diskBufferCache, freePageManagerFactory, btreeCmpFactories, fieldCount,
btreeInteriorFrameFactory, btreeLeafFrameFactory);
- ILSMFileNameManager fileNameManager = new LSMTreeFileNameManager(onDiskDir);
+ ILSMFileManager fileNameManager = new LSMTreeFileManager(onDiskDir);
LSMRTree lsmRTree = new LSMRTree(memBufferCache, memFreePageManager, rtreeInteriorFrameFactory,
rtreeLeafFrameFactory, btreeInteriorFrameFactory, btreeLeafFrameFactory, fileNameManager,
diskRTreeFactory, diskBTreeFactory, diskFileMapProvider, fieldCount, rtreeCmpFactories, btreeCmpFactories);