Hi
Thomas, this is a preliminary patch which attempts to solve the problem.
I've also added Igor's test case to the TestMVStore class.
It still has bugs, and I'm not sure if this strategy is OK with you.
Posting it now in case you already have another solution, and because I
won't get a chance to debug it further until tomorrow.
Points to note
(*) you need to run it under a 64-bit VM or Igor's test case will fail
with OutOfMemoryError.
(*) The pageCount field of Chunk confused me for a while, because it's
not the count of pages, it's the number of times the page has been written
(*) MVStore#store(boolean) is confusing me with all of it's different
length values floating around. I can't work out which ones do what.
Regards, Noel Grandin.
On 2013-03-24 18:45, Igor castang wrote:
It seems that it's not possible to attach file so here is the log and
after the test case
--
You received this message because you are subscribed to the Google Groups "H2
Database" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/h2-database?hl=en.
For more options, visit https://groups.google.com/groups/opt_out.
Index: src/main/org/h2/mvstore/Chunk.java
===================================================================
--- src/main/org/h2/mvstore/Chunk.java (revision 4708)
+++ src/main/org/h2/mvstore/Chunk.java (working copy)
@@ -42,7 +42,7 @@
int length;
/**
- * The number of pages.
+ * The number of times the page has been written.
*/
int pageCount;
Index: src/main/org/h2/mvstore/FreeSpaceList.java
===================================================================
--- src/main/org/h2/mvstore/FreeSpaceList.java (revision 0)
+++ src/main/org/h2/mvstore/FreeSpaceList.java (working copy)
@@ -0,0 +1,132 @@
+package org.h2.mvstore;
+
+import java.util.ArrayList;
+import java.util.List;
+
+public class FreeSpaceList {
+
+ // the first 2 pages are occupied by the file header
+ private static final int FIRST_FREE_PAGE = 3;
+
+ private List<PageRange> freeSpaceList = new ArrayList<PageRange>();
+
+ public FreeSpaceList() {
+ freeSpaceList.add(new PageRange(FIRST_FREE_PAGE, Integer.MAX_VALUE));
+ }
+
+ private static final class PageRange {
+ /** the start point, in pages */
+ public long start;
+ /** the length, in pages */
+ public int length;
+
+ public PageRange(long start, int length) {
+ this.start = start;
+ this.length = length;
+ }
+
+ @Override
+ public String toString() {
+ return "start:" + start + " length:" + length;
+ }
+ }
+
+ /**
+ * @return position in pages
+ */
+ public synchronized long allocatePages(long length) {
+ long required = (length / MVStore.BLOCK_SIZE) + 1;
+ System.out.println("allocatePages : required " + required);
+ for (PageRange pr : freeSpaceList) {
+ if (pr.length >= required) {
+ return pr.start;
+ }
+ }
+ throw new IllegalStateException();
+ }
+
+ public synchronized void markUsed(Chunk c) {
+ long chunkStart = c.start / MVStore.BLOCK_SIZE;
+ int required = (c.length / MVStore.BLOCK_SIZE) + 1;
+ new Throwable("markUsed : chunk ID: " + c.id + " chunkStart:" +
chunkStart + " required:" + required).printStackTrace();
+ PageRange found = null;
+ int i = 0;
+ for (PageRange pr : freeSpaceList) {
+ if (pr.start <= chunkStart) {
+ found = pr;
+ break;
+ }
+ i++;
+ }
+ if (found == null) {
+ throw new IllegalStateException("cannot find spot to mark chunk as
used in free list, " + c.toString());
+ }
+ if (found.start == chunkStart) {
+ // if the used-chunk is at the beginning of a free-space-range
+ found.start += required;
+ } else if (found.start + found.length == chunkStart + required) {
+ // if the used-chunk is at the end of a free-space-range
+ found.length -= required;
+ } else {
+ // it's in the middle, so split the existing entry
+ int length1 = (int) (chunkStart - found.start);
+ long start2 = chunkStart + required;
+ int length2 = (int) (found.start + found.length - chunkStart -
required);
+
+ found.length = length1;
+ PageRange newRange = new PageRange(start2, length2);
+ freeSpaceList.add(i, newRange);
+ }
+ }
+
+ public synchronized void markUnused(Chunk c) {
+ long chunkStart = c.start / MVStore.BLOCK_SIZE;
+ int required = (c.length / MVStore.BLOCK_SIZE) + 1;
+ PageRange found = null;
+ int i = 0;
+ for (PageRange pr : freeSpaceList) {
+ if (pr.start > chunkStart) {
+ found = pr;
+ break;
+ }
+ i++;
+ }
+ if (found == null) {
+ throw new IllegalStateException("cannot find spot to mark chunk as
unused in free list, " + c.toString());
+ }
+ if (chunkStart + required + 1 == found.start) {
+ // if the used-chunk is adjacent to the beginning of a
+ // free-space-range
+ found.start = chunkStart;
+ found.length += required;
+ // merge the previous entry into this one if they are now adjacent
+ if (i > 0) {
+ PageRange previous = freeSpaceList.get(i - 1);
+ if (previous.start + previous.length + 1 == found.start) {
+ previous.length += found.length;
+ freeSpaceList.remove(i);
+ }
+ }
+ } else if (found.start + found.length + 1 == chunkStart) {
+ // if the used-chunk is adjacent to the end of a free-space-range
+ found.length += required;
+ // merge the next entry into this one if they are now adjacent
+ if (i < freeSpaceList.size() - 1) {
+ PageRange next = freeSpaceList.get(i + 1);
+ if (found.start + found.length + 1 == next.start) {
+ found.length += next.length;
+ freeSpaceList.remove(i + 1);
+ }
+ }
+ } else {
+ // it's somewhere between 2 entries, so add an existing one
+ PageRange newRange = new PageRange(chunkStart, required);
+ freeSpaceList.add(i - 1, newRange);
+ }
+ }
+
+ public synchronized void clear() {
+ freeSpaceList.clear();
+ freeSpaceList.add(new PageRange(FIRST_FREE_PAGE, Integer.MAX_VALUE));
+ }
+}
Index: src/main/org/h2/mvstore/MVStore.java
===================================================================
--- src/main/org/h2/mvstore/MVStore.java (revision 4708)
+++ src/main/org/h2/mvstore/MVStore.java (working copy)
@@ -12,12 +12,12 @@
import java.nio.channels.FileLock;
import java.util.ArrayList;
import java.util.Arrays;
-import java.util.BitSet;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
+import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
import org.h2.compress.CompressLZF;
import org.h2.compress.Compressor;
@@ -148,7 +148,12 @@
*/
private final ConcurrentHashMap<Integer, Chunk> chunks =
new ConcurrentHashMap<Integer, Chunk>();
+ /**
+ * The list of free spaces between the chunks.
+ */
+ private FreeSpaceList freeSpaceList = new FreeSpaceList();
+
/**
* The map of temporarily freed entries in the chunks. The key is the
* unsaved version, the value is the map of chunks. The maps of chunks
@@ -545,6 +550,7 @@
Chunk header = readChunkHeader(rootChunkStart);
lastChunkId = header.id;
chunks.put(header.id, header);
+ freeSpaceList.markUsed(header);
meta.setRootPos(header.metaRootPos, -1);
Iterator<String> it = meta.keyIterator("chunk.");
while (it.hasNext()) {
@@ -563,6 +569,7 @@
}
lastChunkId = Math.max(c.id, lastChunkId);
chunks.put(c.id, c);
+ freeSpaceList.markUsed(c);
}
}
@@ -694,6 +701,7 @@
}
meta = null;
chunks.clear();
+ freeSpaceList.clear();
cache.clear();
maps.clear();
} catch (Exception e) {
@@ -845,7 +853,7 @@
}
applyFreedChunks(storeVersion);
- ArrayList<Integer> removedChunks = New.arrayList();
+ Set<Integer> removedChunks = New.hashSet();
// do it twice, because changing the meta table
// could cause a chunk to become empty
for (int i = 0; i < 2; i++) {
@@ -900,7 +908,7 @@
buff.limit(length);
long fileLength = getFileLengthUsed();
- long filePos = reuseSpace ? allocateChunk(length) : fileLength;
+ long filePos = reuseSpace ? allocateChunk(chunkLength) : fileLength;
boolean storeAtEndOfFile = filePos + length >= fileLength;
// need to keep old chunks
@@ -908,11 +916,13 @@
// by an old version
// so empty space is not reused too early
for (int x : removedChunks) {
+ freeSpaceList.markUnused(chunks.get(x));
chunks.remove(x);
}
c.start = filePos;
c.length = chunkLength;
+ freeSpaceList.markUsed(c);
c.metaRootPos = meta.getRoot().getPos();
buff.position(0);
c.writeHeader(buff);
@@ -1024,33 +1034,7 @@
}
private long allocateChunk(long length) {
- BitSet set = new BitSet();
- set.set(0);
- set.set(1);
- for (Chunk c : chunks.values()) {
- if (c.start == Long.MAX_VALUE) {
- continue;
- }
- int first = (int) (c.start / BLOCK_SIZE);
- int last = (int) ((c.start + c.length) / BLOCK_SIZE);
- set.set(first, last + 2);
- }
- int required = (int) (length / BLOCK_SIZE) + 1;
- for (int i = 0; i < set.size(); i++) {
- if (!set.get(i)) {
- boolean ok = true;
- for (int j = 0; j < required; j++) {
- if (set.get(i + j)) {
- ok = false;
- break;
- }
- }
- if (ok) {
- return i * BLOCK_SIZE;
- }
- }
- }
- return set.size() * BLOCK_SIZE;
+ return freeSpaceList.allocatePages(length) * BLOCK_SIZE;
}
/**
@@ -1488,6 +1472,7 @@
}
meta.clear();
chunks.clear();
+ freeSpaceList.clear();
maps.clear();
synchronized (freedChunks) {
freedChunks.clear();
@@ -1517,6 +1502,7 @@
revertTemp(version);
loadFromFile = true;
do {
+ freeSpaceList.markUnused(chunks.get(lastChunkId));
last = chunks.remove(lastChunkId);
lastChunkId--;
} while (last.version > version && chunks.size() > 0);
Index: src/test/org/h2/test/store/TestMVStore.java
===================================================================
--- src/test/org/h2/test/store/TestMVStore.java (revision 4708)
+++ src/test/org/h2/test/store/TestMVStore.java (working copy)
@@ -79,6 +79,10 @@
testIterate();
testCloseTwice();
testSimple();
+ // this test will run out of memory on a 32-bit VM
+ if ("64".equals(System.getProperty("sun.arch.data.model"))) {
+ testLargerThan2G();
+ }
}
private void testAtomicOperations() {
@@ -1392,7 +1396,33 @@
}
s.close();
}
+
+ private void testLargerThan2G() {
+ String fileName = getBaseDir() + "/testLargerThan2G.h3";
+ FileUtils.delete(fileName);
+
+ MVStore store = new
MVStore.Builder().cacheSize(800).fileName(fileName).writeBufferSize(0).writeDelay(-1)
+ .open();
+ MVMap<String, String> map = store.openMap("test");
+ int totalWrite = 15000000;
+ int lineStored = 0;
+ while (lineStored <= totalWrite) {
+ lineStored++;
+ String actualKey = lineStored + " just for length
hhhhhhhhhhhhhhhhh" + lineStored;
+ String value = "Just a a string that is kinda longgggggggggggg but
not too much AAAAAAAAAAAAAAAAAAAAA hhhhhhhhhhhhhhhhhh"
+ + lineStored;
+
+ map.put(actualKey, value);
+
+ if (lineStored % 1000000 == 0) {
+ store.store();
+ }
+ }
+ store.store();
+ store.close();
+ }
+
/**
* Open a store for the given file name, using a small page size.
*
