added LRU strategy to index lifecycle manager
git-svn-id: https://hyracks.googlecode.com/svn/branches/hyracks_lsm_tree@1789 123451ca-8445-de46-9d55-352943316053
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
index 17b072e..0432f79 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IIndex.java
@@ -127,6 +127,11 @@
public IndexType getIndexType();
/**
+ * @return the size, in bytes, of pre-allocated memory space that this index was allotted.
+ */
+ public long getInMemorySize();
+
+ /**
* @param fillFactor
* @param verifyInput
* @throws IndexException
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexLifecycleManager.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexLifecycleManager.java
index e2bf2aa..852c8a8 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexLifecycleManager.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/dataflow/IndexLifecycleManager.java
@@ -1,6 +1,7 @@
package edu.uci.ics.hyracks.storage.am.common.dataflow;
import java.io.IOException;
+import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
@@ -12,117 +13,138 @@
import edu.uci.ics.hyracks.storage.common.file.IIndexArtifactMap;
public class IndexLifecycleManager implements IIndexLifecycleManager {
+ private static final long DEFAULT_MEMORY_BUDGET = 1024 * 1024 * 100; // 100 megabytes
- private final IndexRegistry<IIndex> indexRegistry;
- private final Map<Long, Integer> refCountMap = new HashMap<Long, Integer>();
+ private final Map<Long, IndexInfo> indexInfos;
+ private final long memoryBudget;
+
+ private long memoryUsed;
public IndexLifecycleManager() {
- this.indexRegistry = new IndexRegistry<IIndex>();
+ this(DEFAULT_MEMORY_BUDGET);
+ }
+
+ public IndexLifecycleManager(long memoryBudget) {
+ this.indexInfos = new HashMap<Long, IndexInfo>();
+ this.memoryBudget = memoryBudget;
+ this.memoryUsed = 0;
}
@Override
- public void create(IIndexDataflowHelper helper) throws HyracksDataException {
+ public synchronized void create(IIndexDataflowHelper helper) throws HyracksDataException {
IHyracksTaskContext ctx = helper.getHyracksTaskContext();
IIOManager ioManager = ctx.getIOManager();
IIndexArtifactMap indexArtifactMap = helper.getOperatorDescriptor().getStorageManager()
.getIndexArtifactMap(ctx);
+ IIndex index = helper.getIndexInstance();
- IIndex index;
- synchronized (indexRegistry) {
- long resourceID = helper.getResourceID();
- index = indexRegistry.get(resourceID);
-
- boolean generateResourceID = false;
- boolean register = false;
- if (index == null) {
- generateResourceID = true;
- register = true;
- index = helper.getIndexInstance();
+ boolean generateResourceID = helper.getResourceID() == -1 ? true : false;
+ if (generateResourceID) {
+ try {
+ indexArtifactMap.create(helper.getFileReference().getFile().getPath(), ioManager.getIODevices());
+ } catch (IOException e) {
+ throw new HyracksDataException(e);
}
+ }
- index.create();
+ index.create();
+ }
- if (generateResourceID) {
- try {
- resourceID = indexArtifactMap.create(helper.getFileReference().getFile().getPath(),
- ioManager.getIODevices());
- } catch (IOException e) {
- throw new HyracksDataException(e);
+ @Override
+ public synchronized void destroy(IIndexDataflowHelper helper) throws HyracksDataException {
+ IHyracksTaskContext ctx = helper.getHyracksTaskContext();
+ IIOManager ioManager = ctx.getIOManager();
+ IIndexArtifactMap indexArtifactMap = helper.getOperatorDescriptor().getStorageManager()
+ .getIndexArtifactMap(ctx);
+ IIndex index = helper.getIndexInstance();
+
+ indexArtifactMap.delete(helper.getFileReference().getFile().getPath(), ioManager.getIODevices());
+ index.destroy();
+ }
+
+ @Override
+ public synchronized IIndex open(IIndexDataflowHelper helper) throws HyracksDataException {
+ long resourceID = helper.getResourceID();
+ IndexInfo info = indexInfos.get(resourceID);
+
+ if (info == null) {
+ IIndex index = helper.getIndexInstance();
+ if (memoryUsed + index.getInMemorySize() > memoryBudget) {
+ if (!evictCandidateIndex()) {
+ throw new HyracksDataException("Cannot activate index since memory budget would be exceeded.");
}
}
- if (register) {
- indexRegistry.register(resourceID, index);
- refCountMap.put(resourceID, 0);
- }
- }
- }
- @Override
- public void destroy(IIndexDataflowHelper helper) throws HyracksDataException {
- IHyracksTaskContext ctx = helper.getHyracksTaskContext();
- IIOManager ioManager = ctx.getIOManager();
- IIndexArtifactMap indexArtifactMap = helper.getOperatorDescriptor().getStorageManager()
- .getIndexArtifactMap(ctx);
-
- IIndex index;
- long resourceID = helper.getResourceID();
-
- synchronized (indexRegistry) {
- index = indexRegistry.get(resourceID);
- if (index == null) {
- index = helper.getIndexInstance();
- }
- indexArtifactMap.delete(helper.getFileReference().getFile().getPath(), ioManager.getIODevices());
- indexRegistry.unregister(resourceID);
- index.destroy();
- refCountMap.remove(resourceID);
- }
- }
-
- @Override
- public IIndex open(IIndexDataflowHelper helper) throws HyracksDataException {
- IIndex index;
- long resourceID = helper.getResourceID();
-
- synchronized (indexRegistry) {
- index = indexRegistry.get(resourceID);
-
- boolean register = false;
- if (index == null) {
- refCountMap.put(resourceID, 1);
- register = true;
- index = helper.getIndexInstance();
- } else {
- int count = refCountMap.get(resourceID);
- refCountMap.put(resourceID, ++count);
- }
+ info = new IndexInfo(index, resourceID);
+ indexInfos.put(resourceID, info);
index.activate();
-
- if (register) {
- indexRegistry.register(resourceID, index);
- }
+ memoryUsed += index.getInMemorySize();
}
- return index;
+
+ info.touch();
+ return info.index;
+ }
+
+ private boolean evictCandidateIndex() throws HyracksDataException {
+ IndexInfo info = Collections.min(indexInfos.values());
+ if (info.referenceCount != 0) {
+ return false;
+ }
+
+ info.index.deactivate();
+ indexInfos.remove(info.resourceID);
+
+ return true;
}
@Override
- public void close(IIndexDataflowHelper helper) throws HyracksDataException {
- IIndex index;
- long resourceID = helper.getResourceID();
-
- synchronized (indexRegistry) {
- index = indexRegistry.get(resourceID);
- int count = refCountMap.get(resourceID);
- refCountMap.put(resourceID, --count);
- if (index == null) {
- throw new IllegalStateException("Trying to close an index that was not registered.");
- }
-
- if (count == 0) {
- indexRegistry.unregister(resourceID);
- index.deactivate();
- }
- }
+ public synchronized void close(IIndexDataflowHelper helper) throws HyracksDataException {
+ indexInfos.get(helper.getResourceID()).untouch();
}
-}
+ private class IndexInfo implements Comparable<IndexInfo> {
+ private final IIndex index;
+ private final long resourceID;
+ private int referenceCount;
+ private long lastAccess;
+
+ public IndexInfo(IIndex index, long resourceID) {
+ this.index = index;
+ this.resourceID = resourceID;
+ this.lastAccess = -1;
+ this.referenceCount = 0;
+ }
+
+ public void touch() {
+ lastAccess = System.currentTimeMillis();
+ referenceCount++;
+ }
+
+ public void untouch() {
+ lastAccess = System.currentTimeMillis();
+ referenceCount--;
+ }
+
+ @Override
+ public int compareTo(IndexInfo i) {
+ // sort by (referenceCount, lastAccess), ascending
+ if (referenceCount < i.referenceCount) {
+ return -1;
+ } else if (referenceCount > i.referenceCount) {
+ return 1;
+ } else {
+ if (lastAccess < i.lastAccess) {
+ return -1;
+ } else if (lastAccess > i.lastAccess) {
+ return 1;
+ } else {
+ return 0;
+ }
+ }
+ }
+
+ public String toString() {
+ return "{lastAccess: " + lastAccess + ", refCount: " + referenceCount + "}";
+ }
+ }
+}
\ No newline at end of file
diff --git a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/AbstractTreeIndex.java b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/AbstractTreeIndex.java
index 358481e..5c6c913 100644
--- a/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/AbstractTreeIndex.java
+++ b/hyracks-storage-am-common/src/main/java/edu/uci/ics/hyracks/storage/am/common/impls/AbstractTreeIndex.java
@@ -345,4 +345,9 @@
}
+ @Override
+ public long getInMemorySize() {
+ return 0;
+ }
+
}
diff --git a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
index 44aad7b..44cc1b1 100644
--- a/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
+++ b/hyracks-storage-am-invertedindex/src/main/java/edu/uci/ics/hyracks/storage/am/invertedindex/impls/InvertedIndex.java
@@ -260,8 +260,8 @@
private final MultiComparator tokenCmp;
private final MultiComparator invListCmp;
- public InvertedIndexBulkLoader(float btreeFillFactor, boolean verifyInput, int startPageId, int fileId) throws IndexException,
- HyracksDataException {
+ public InvertedIndexBulkLoader(float btreeFillFactor, boolean verifyInput, int startPageId, int fileId)
+ throws IndexException, HyracksDataException {
this.tokenCmp = MultiComparator.create(btree.getComparatorFactories());
this.invListCmp = MultiComparator.create(invListCmpFactories);
this.btreeTupleBuilder = new ArrayTupleBuilder(btree.getFieldCount());
@@ -476,4 +476,9 @@
public void validate() throws HyracksDataException {
throw new UnsupportedOperationException("Validation not implemented for Inverted Indexes.");
}
+
+ @Override
+ public long getInMemorySize() {
+ return 0;
+ }
}
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 aa6ef70..e1a745c 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
@@ -431,25 +431,25 @@
@Override
public void add(ITupleReference tuple) throws IndexException, HyracksDataException {
- try {
- bulkLoader.add(tuple);
- } catch (IndexException e) {
- handleException();
- throw e;
- } catch (HyracksDataException e) {
- handleException();
- throw e;
- } catch (RuntimeException e) {
+ try {
+ bulkLoader.add(tuple);
+ } catch (IndexException e) {
+ handleException();
+ throw e;
+ } catch (HyracksDataException e) {
+ handleException();
+ throw e;
+ } catch (RuntimeException e) {
handleException();
throw e;
}
}
protected void handleException() throws HyracksDataException {
- diskBTree.deactivate();
- diskBTree.destroy();
+ diskBTree.deactivate();
+ diskBTree.destroy();
}
-
+
@Override
public void end() throws HyracksDataException {
bulkLoader.end();
@@ -597,4 +597,10 @@
btree.validate();
}
}
+
+ @Override
+ public long getInMemorySize() {
+ InMemoryBufferCache memBufferCache = (InMemoryBufferCache) memBTree.getBufferCache();
+ return memBufferCache.getNumPages() * memBufferCache.getPageSize();
+ }
}
diff --git a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
index d3ee9ce..f2b22ac 100644
--- a/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
+++ b/hyracks-storage-am-lsm-common/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/common/freepage/InMemoryBufferCache.java
@@ -89,7 +89,7 @@
@Override
public int getNumPages() {
- return pages.length;
+ return numPages;
}
@Override
diff --git a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
index 6c1395c..9473fef 100644
--- a/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
+++ b/hyracks-storage-am-lsm-rtree/src/main/java/edu/uci/ics/hyracks/storage/am/lsm/rtree/impls/AbstractLSMRTree.java
@@ -401,4 +401,10 @@
public void validate() throws HyracksDataException {
throw new UnsupportedOperationException("Validation not implemented for LSM R-Trees.");
}
+
+ @Override
+ public long getInMemorySize() {
+ InMemoryBufferCache memBufferCache = (InMemoryBufferCache) memComponent.rtree.getBufferCache();
+ return memBufferCache.getNumPages() * memBufferCache.getPageSize();
+ }
}