File D:\maven-qcr-plugin-testsunitaires\qcr4java\h2-1.3.170-sources\target\site\qc\lecode\mvstore\MVStore.java.html

1 /*
2 * Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License,
3 * Version 1.0, and under the Eclipse Public License, Version 1.0
4 * (http://h2database.com/html/license.html).
5 * Initial Developer: H2 Group
6 */
7 package org.h2.mvstore;
8
9 import java.io.IOException;
10 import java.nio.ByteBuffer;
11 import java.nio.channels.FileChannel;
12 import java.nio.channels.FileLock;
13 import java.util.ArrayList;
14 import java.util.BitSet;
15 import java.util.Collections;
16 import java.util.Comparator;
17 import java.util.HashMap;
18 import java.util.Iterator;
19 import java.util.Map;
20 import org.h2.compress.CompressLZF;
21 import org.h2.compress.Compressor;
22 import org.h2.mvstore.cache.CacheLongKeyLIRS;
23 import org.h2.mvstore.cache.FilePathCache;
24 import org.h2.mvstore.type.DataType;
25 import org.h2.mvstore.type.DataTypeFactory;
26 import org.h2.mvstore.type.ObjectTypeFactory;
27 import org.h2.mvstore.type.StringType;
28 import org.h2.store.fs.FilePath;
29 import org.h2.store.fs.FileUtils;
30 import org.h2.util.New;
31
32 /*
33
34 File format:
35 header: (blockSize) bytes
36 header: (blockSize) bytes
37 [ chunk ] *
38 (there are two headers for security)
39 header:
40 H:3,...
41
42 TODO:
43 - store creation in file header, and seconds since creation
44 -- in chunk header (plus a counter) - ensure time never goes backwards
45 - recovery: keep some old chunks; don't overwritten
46 -- for 5 minutes (configurable)
47 - allocate memory with Utils.newBytes and so on
48 - unified exception handling
49 - concurrent map; avoid locking during IO (pre-load pages)
50 - maybe split database into multiple files, to speed up compact
51 - automated 'kill process' and 'power failure' test
52 - implement table engine for H2
53 - auto-compact from time to time and on close
54 - test and possibly improve compact operation (for large dbs)
55 - support background writes (concurrent modification & store)
56 - limited support for writing to old versions (branches)
57 - support concurrent operations (including file I/O)
58 - on insert, if the child page is already full, don't load and modify it
59 -- split directly (for leaves with 1 entry)
60 - performance test with encrypting file system
61 - possibly split chunk data into immutable and mutable
62 - compact: avoid processing pages using a counting bloom filter
63 - defragment (re-creating maps, specially those with small pages)
64 - write using ByteArrayOutputStream; remove DataType.getMaxLength
65 - file header: check formatRead and format (is formatRead
66 -- needed if equal to format?)
67 - chunk header: store changed chunk data as row; maybe after the root
68 - chunk checksum (header, last page, 2 bytes per page?)
69 - allow renaming maps
70 - file locking: solve problem that locks are shared for a VM
71 - online backup
72 - MapFactory is the wrong name (StorePlugin?) or is too flexible: remove?
73 - store file "header" at the end of each chunk; at the end of the file
74 - is there a better name for the file header,
75 -- if it's no longer always at the beginning of a file?
76 - maybe let a chunk point to possible next chunks
77 -- (so no fixed location header is needed)
78 - support stores that span multiple files (chunks stored in other files)
79 - triggers (can be implemented with a custom map)
80 - store write operations per page (maybe defragment
81 -- if much different than count)
82 - r-tree: nearest neighbor search
83 - use FileChannel by default (nio file system), but:
84 -- an interrupt close the FileChannel
85 - auto-save temporary data if it uses too much memory,
86 -- but revert it on startup if needed.
87 - map and chunk metadata: do not store default values
88 - support maps without values (non-unique indexes),
89 - and maps without keys (counted b-tree)
90 - use a small object cache (StringCache)
91 - dump values
92 - tool to import / manipulate CSV files (maybe concurrently)
93 - map split / merge (fast if no overlap)
94
95 */
96
97 /**
98 * A persistent storage for maps.
99 */
100 public class MVStore {
101
102 /**
103 * Whether assertions are enabled.
104 */
105 public static final boolean ASSERT = false;
106
107 /**
108 * The block size (physical sector size) of the disk. The file header is
109 * written twice, one copy in each block, to ensure it survives a crash.
110 */
111 static final int BLOCK_SIZE = 4 * 1024;
112
113 private final HashMap<String, Object> config;
114
115 private final String fileName;
116 private final DataTypeFactory dataTypeFactory;
117
118 private int pageSize = 6 * 1024;
119
120 private FileChannel file;
121 private FileLock fileLock;
122 private long fileSize;
123 private long rootChunkStart;
124
125 /**
126 * The cache. The default size is 16 MB, and the average size is 2 KB. It is
127 * split in 16 segments. The stack move distance is 2% of the expected
128 * number of entries.
129 */
130 private final CacheLongKeyLIRS<Page> cache;
131
132 private int lastChunkId;
133 private final HashMap<Integer, Chunk> chunks = New.hashMap();
134
135 /**
136 * The map of temporarily freed entries in the chunks. The key is the
137 * unsaved version, the value is the map of chunks. The maps of chunks
138 * contains the number of freed entries per chunk.
139 */
140 private final HashMap<Long, HashMap<Integer, Chunk>> freedChunks = New.hashMap();
141
142 private MVMap<String, String> meta;
143 private final HashMap<String, MVMap<?, ?>> maps = New.hashMap();
144
145 /**
146 * The set of maps with potentially unsaved changes.
147 */
148 private final HashMap<Integer, MVMap<?, ?>> mapsChanged = New.hashMap();
149
150 private HashMap<String, String> fileHeader = New.hashMap();
151
152 private final boolean readOnly;
153
154 private int lastMapId;
155
156 private volatile boolean reuseSpace = true;
157 private long retainVersion = -1;
158 private int retainChunk = -1;
159
160 private Compressor compressor;
161
162 private long currentVersion;
163 private int fileReadCount;
164 private int fileWriteCount;
165 private int unsavedPageCount;
166
167 MVStore(HashMap<String, Object> config) {
168 this.config = config;
169 this.fileName = (String) config.get("fileName");
170 DataTypeFactory parent = new ObjectTypeFactory();
171 DataTypeFactory f = (DataTypeFactory) config.get("dataTypeFactory");
172 if (f == null) {
173 f = parent;
174 } else {
175 f.setParent(parent);
176 }
177 this.dataTypeFactory = f;
178 this.readOnly = "r".equals(config.get("openMode"));
179 this.compressor = "0".equals(config.get("compression")) ? null : new CompressLZF();
180 if (fileName != null) {
181 Object s = config.get("cacheSize");
182 int mb = s == null ? 16 : Integer.parseInt(s.toString());
183 cache = CacheLongKeyLIRS.newInstance(
184 mb * 1024 * 1024, 2048, 16, mb * 1024 * 1024 / 2048 * 2 / 100);
185 } else {
186 cache = null;
187 }
188 }
189
190 /**
191 * Open a store in exclusive mode.
192 *
193 * @param fileName the file name (null for in-memory)
194 * @return the store
195 */
196 public static MVStore open(String fileName) {
197 HashMap<String, Object> config = New.hashMap();
198 config.put("fileName", fileName);
199 MVStore s = new MVStore(config);
200 s.open();
201 return s;
202 }
203
204 /**
205 * Open an old, stored version of a map.
206 *
207 * @param version the version
208 * @param name the map name
209 * @param template the template map
210 * @return the read-only map
211 */
212 @SuppressWarnings("unchecked")
213 <T extends MVMap<?, ?>> T openMapVersion(long version, String name, MVMap<?, ?> template) {
214 MVMap<String, String> oldMeta = getMetaMap(version);
215 String r = oldMeta.get("root." + template.getId());
216 long rootPos = r == null ? 0 : Long.parseLong(r);
217 MVMap<?, ?> m = template.openReadOnly();
218 m.setRootPos(rootPos, version);
219 return (T) m;
220 }
221
222 /**
223 * Open a map with the previous key and value type (if the map already
224 * exists), or Object if not.
225 *
226 * @param <K> the key type
227 * @param <V> the value type
228 * @param name the name of the map
229 * @return the map
230 */
231 @SuppressWarnings("unchecked")
232 public <K, V> MVMap<K, V> openMap(String name) {
233 return (MVMap<K, V>) openMap(name, Object.class, Object.class);
234 }
235
236 /**
237 * Open a map.
238 *
239 * @param <K> the key type
240 * @param <V> the value type
241 * @param name the name of the map
242 * @param keyClass the key class
243 * @param valueClass the value class
244 * @return the map
245 */
246 public <K, V> MVMap<K, V> openMap(String name, Class<K> keyClass, Class<V> valueClass) {
247 DataType keyType = getDataType(keyClass);
248 DataType valueType = getDataType(valueClass);
249 MVMap<K, V> m = new MVMap<K, V>(keyType, valueType);
250 return openMap(name, m);
251 }
252
253 /**
254 * Open a map using the given template. The returned map is of the same type
255 * as the template, and contains the same key and value types. If a map with
256 * this name is already open, this map is returned. If it is not open,
257 * the template object is opened with the applicable configuration.
258 *
259 * @param <T> the map type
260 * @param name the name of the map
261 * @param template the template map
262 * @return the opened map
263 */
264 @SuppressWarnings("unchecked")
265 public <T extends MVMap<K, V>, K, V> T openMap(String name, T template) {
266 MVMap<K, V> m = (MVMap<K, V>) maps.get(name);
267 if (m != null) {
268 return (T) m;
269 }
270 m = template;
271 String config = meta.get("map." + name);
272 long root;
273 HashMap<String, String> c;
274 if (config == null) {
275 c = New.hashMap();
276 c.put("id", Integer.toString(++lastMapId));
277 c.put("name", name);
278 c.put("createVersion", Long.toString(currentVersion));
279 m.open(this, c);
280 meta.put("map." + name, m.asString());
281 root = 0;
282 } else {
283 c = DataUtils.parseMap(config);
284 String r = meta.get("root." + c.get("id"));
285 root = r == null ? 0 : Long.parseLong(r);
286 }
287 m.open(this, c);
288 m.setRootPos(root, -1);
289 maps.put(name, m);
290 return (T) m;
291 }
292
293 /**
294 * Get the metadata map. This data is for informational purposes only. The
295 * data is subject to change in future versions. The data should not be
296 * modified (doing so may corrupt the store).
297 * <p>
298 * It contains the following entries:
299 *
300 * <pre>
301 * map.{name} = {map metadata}
302 * root.{mapId} = {root position}
303 * chunk.{chunkId} = {chunk metadata}
304 * </pre>
305 *
306 * @return the metadata map
307 */
308 public MVMap<String, String> getMetaMap() {
309 return meta;
310 }
311
312 private MVMap<String, String> getMetaMap(long version) {
313 Chunk c = getChunkForVersion(version);
314 if (c == null) {
315 throw new IllegalArgumentException("Unknown version: " + version);
316 }
317 c = readChunkHeader(c.start);
318 MVMap<String, String> oldMeta = meta.openReadOnly();
319 oldMeta.setRootPos(c.metaRootPos, version);
320 return oldMeta;
321 }
322
323 private Chunk getChunkForVersion(long version) {
324 for (int chunkId = lastChunkId;; chunkId--) {
325 Chunk x = chunks.get(chunkId);
326 if (x == null || x.version < version) {
327 return null;
328 } else if (x.version == version) {
329 return x;
330 }
331 }
332 }
333
334 /**
335 * Remove a map.
336 *
337 * @param name the map name
338 */
339 void removeMap(String name) {
340 MVMap<?, ?> map = maps.remove(name);
341 mapsChanged.remove(map.getId());
342 }
343
344 private DataType getDataType(Class<?> clazz) {
345 if (clazz == String.class) {
346 return StringType.INSTANCE;
347 }
348 if (dataTypeFactory == null) {
349 throw new RuntimeException("No data type factory set " +
350 "and don't know how to serialize " + clazz);
351 }
352 String s = dataTypeFactory.getDataType(clazz);
353 return dataTypeFactory.buildDataType(s);
354 }
355
356 /**
357 * Mark a map as changed (containing unsaved changes).
358 *
359 * @param map the map
360 */
361 void markChanged(MVMap<?, ?> map) {
362 mapsChanged.put(map.getId(), map);
363 }
364
365 /**
366 * Open the store.
367 */
368 void open() {
369 meta = new MVMap<String, String>(StringType.INSTANCE, StringType.INSTANCE);
370 HashMap<String, String> c = New.hashMap();
371 c.put("id", "0");
372 c.put("name", "meta");
373 c.put("createVersion", Long.toString(currentVersion));
374 meta.open(this, c);
375 if (fileName == null) {
376 return;
377 }
378 FileUtils.createDirectories(FileUtils.getParent(fileName));
379 try {
380 log("file open");
381 file = FilePathCache.wrap(FilePath.get(fileName).open("rw"));
382 if (readOnly) {
383 fileLock = file.tryLock(0, Long.MAX_VALUE, true);
384 if (fileLock == null) {
385 throw new RuntimeException("The file is locked: " + fileName);
386 }
387 } else {
388 fileLock = file.tryLock();
389 if (fileLock == null) {
390 throw new RuntimeException("The file is locked: " + fileName);
391 }
392 }
393 fileSize = file.size();
394 if (fileSize == 0) {
395 fileHeader.put("H", "3");
396 fileHeader.put("blockSize", "" + BLOCK_SIZE);
397 fileHeader.put("format", "1");
398 fileHeader.put("formatRead", "1");
399 writeFileHeader();
400 } else {
401 readFileHeader();
402 if (rootChunkStart > 0) {
403 readMeta();
404 }
405 }
406 } catch (Exception e) {
407 close();
408 throw convert(e);
409 }
410 }
411
412 private void readMeta() {
413 Chunk header = readChunkHeader(rootChunkStart);
414 lastChunkId = header.id;
415 chunks.put(header.id, header);
416 meta.setRootPos(header.metaRootPos, -1);
417 Iterator<String> it = meta.keyIterator("chunk.");
418 while (it.hasNext()) {
419 String s = it.next();
420 if (!s.startsWith("chunk.")) {
421 break;
422 }
423 Chunk c = Chunk.fromString(meta.get(s));
424 if (c.id == header.id) {
425 c.start = header.start;
426 c.length = header.length;
427 c.metaRootPos = header.metaRootPos;
428 c.maxLengthLive = header.maxLengthLive;
429 c.pageCount = header.pageCount;
430 c.maxLength = header.maxLength;
431 }
432 lastChunkId = Math.max(c.id, lastChunkId);
433 chunks.put(c.id, c);
434 }
435 }
436
437 private void readFileHeader() {
438 try {
439 byte[] headers = new byte[2 * BLOCK_SIZE];
440 fileReadCount++;
441 DataUtils.readFully(file, 0, ByteBuffer.wrap(headers));
442 for (int i = 0; i <= BLOCK_SIZE; i += BLOCK_SIZE) {
443 String s = new String(headers, i, BLOCK_SIZE, "UTF-8").trim();
444 fileHeader = DataUtils.parseMap(s);
445 rootChunkStart = Long.parseLong(fileHeader.get("rootChunk"));
446 currentVersion = Long.parseLong(fileHeader.get("version"));
447 lastMapId = Integer.parseInt(fileHeader.get("lastMapId"));
448 int check = (int) Long.parseLong(fileHeader.get("fletcher"), 16);
449 s = s.substring(0, s.lastIndexOf("fletcher") - 1) + " ";
450 byte[] bytes = s.getBytes("UTF-8");
451 int checksum = DataUtils.getFletcher32(bytes,
452 bytes.length / 2 * 2);
453 if (check == checksum) {
454 return;
455 }
456 }
457 throw new RuntimeException("File header is corrupt");
458 } catch (Exception e) {
459 throw convert(e);
460 }
461 }
462
463 private void writeFileHeader() {
464 try {
465 StringBuilder buff = new StringBuilder();
466 fileHeader.put("lastMapId", "" + lastMapId);
467 fileHeader.put("rootChunk", "" + rootChunkStart);
468 fileHeader.put("version", "" + currentVersion);
469 DataUtils.appendMap(buff, fileHeader);
470 byte[] bytes = (buff.toString() + " ").getBytes("UTF-8");
471 int checksum = DataUtils.getFletcher32(bytes, bytes.length / 2 * 2);
472 DataUtils.appendMap(buff, "fletcher", Integer.toHexString(checksum));
473 bytes = buff.toString().getBytes("UTF-8");
474 if (bytes.length > BLOCK_SIZE) {
475 throw new IllegalArgumentException("File header too large: " + buff);
476 }
477 ByteBuffer header = ByteBuffer.allocate(2 * BLOCK_SIZE);
478 header.put(bytes);
479 header.position(BLOCK_SIZE);
480 header.put(bytes);
481 header.rewind();
482 fileWriteCount++;
483 DataUtils.writeFully(file, 0, header);
484 fileSize = Math.max(fileSize, 2 * BLOCK_SIZE);
485 } catch (Exception e) {
486 throw convert(e);
487 }
488 }
489
490 private static RuntimeException convert(Exception e) {
491 throw new RuntimeException("Exception: " + e, e);
492 }
493
494 /**
495 * Close the file. Uncommitted changes are ignored, and all open maps are closed.
496 */
497 public void close() {
498 if (file != null) {
499 try {
500 shrinkFileIfPossible(0);
501 log("file close");
502 if (fileLock != null) {
503 fileLock.release();
504 fileLock = null;
505 }
506 file.close();
507 for (MVMap<?, ?> m : New.arrayList(maps.values())) {
508 m.close();
509 }
510 meta = null;
511 compressor = null;
512 chunks.clear();
513 cache.clear();
514 maps.clear();
515 mapsChanged.clear();
516 } catch (Exception e) {
517 throw convert(e);
518 } finally {
519 file = null;
520 }
521 }
522 }
523
524 /**
525 * Get the chunk for the given position.
526 *
527 * @param pos the position
528 * @return the chunk
529 */
530 Chunk getChunk(long pos) {
531 return chunks.get(DataUtils.getPageChunkId(pos));
532 }
533
534 /**
535 * Increment the current version.
536 *
537 * @return the new version
538 */
539 public long incrementVersion() {
540 return ++currentVersion;
541 }
542
543 /**
544 * Commit all changes and persist them to disk. This method does nothing if
545 * there are no unsaved changes, otherwise it stores the data and increments
546 * the current version.
547 *
548 * @return the new version (incremented if there were changes)
549 */
550 public long store() {
551 if (!hasUnsavedChanges()) {
552 return currentVersion;
553 }
554
555 int currentUnsavedPageCount = unsavedPageCount;
556 long storeVersion = currentVersion;
557 long version = incrementVersion();
558
559 // the last chunk was not completely correct in the last store()
560 // this needs to be updated now (it's better not to update right after
561 // storing, because that would modify the meta map again)
562 Chunk c = chunks.get(lastChunkId);
563 if (c != null) {
564 meta.put("chunk." + c.id, c.asString());
565 }
566 c = new Chunk(++lastChunkId);
567 c.maxLength = Long.MAX_VALUE;
568 c.maxLengthLive = Long.MAX_VALUE;
569 c.start = Long.MAX_VALUE;
570 c.length = Integer.MAX_VALUE;
571 c.version = version;
572 chunks.put(c.id, c);
573 meta.put("chunk." + c.id, c.asString());
574
575 int maxLength = 1 + 4 + 4 + 8;
576 for (MVMap<?, ?> m : mapsChanged.values()) {
577 if (m == meta || !m.hasUnsavedChanges()) {
578 continue;
579 }
580 Page p = m.openVersion(storeVersion).getRoot();
581 if (p.getTotalCount() == 0) {
582 meta.put("root." + m.getId(), "0");
583 } else {
584 maxLength += p.getMaxLengthTempRecursive();
585 meta.put("root." + m.getId(), String.valueOf(Long.MAX_VALUE));
586 }
587 }
588 applyFreedChunks();
589 ArrayList<Integer> removedChunks = New.arrayList();
590 do {
591 for (Chunk x : chunks.values()) {
592 if (x.maxLengthLive == 0 && (retainChunk == -1 || x.id < retainChunk)) {
593 meta.remove("chunk." + x.id);
594 removedChunks.add(x.id);
595 } else {
596 meta.put("chunk." + x.id, x.asString());
597 }
598 applyFreedChunks();
599 }
600 } while (freedChunks.size() > 0);
601 maxLength += meta.getRoot().getMaxLengthTempRecursive();
602
603 ByteBuffer buff = ByteBuffer.allocate(maxLength);
604 // need to patch the header later
605 c.writeHeader(buff);
606 c.maxLength = 0;
607 c.maxLengthLive = 0;
608 for (MVMap<?, ?> m : mapsChanged.values()) {
609 if (m == meta || !m.hasUnsavedChanges()) {
610 continue;
611 }
612 Page p = m.openVersion(storeVersion).getRoot();
613 if (p.getTotalCount() > 0) {
614 long root = p.writeUnsavedRecursive(c, buff);
615 meta.put("root." + m.getId(), "" + root);
616 }
617 }
618
619 meta.put("chunk." + c.id, c.asString());
620
621 if (ASSERT) {
622 if (freedChunks.size() > 0) {
623 throw new RuntimeException("Temporary freed chunks");
624 }
625 }
626
627 // this will modify maxLengthLive, but
628 // the correct value is written in the chunk header
629 meta.getRoot().writeUnsavedRecursive(c, buff);
630
631 buff.flip();
632 int length = buff.limit();
633 long filePos = allocateChunk(length);
634
635 // need to keep old chunks
636 // until they are are no longer referenced
637 // by an old version
638 // so empty space is not reused too early
639 for (int x : removedChunks) {
640 chunks.remove(x);
641 }
642
643 buff.rewind();
644
645 c.start = filePos;
646 c.length = length;
647 c.metaRootPos = meta.getRoot().getPos();
648 c.writeHeader(buff);
649 buff.rewind();
650 try {
651 fileWriteCount++;
652 DataUtils.writeFully(file, filePos, buff);
653 } catch (IOException e) {
654 throw new RuntimeException(e);
655 }
656 fileSize = Math.max(fileSize, filePos + buff.position());
657 rootChunkStart = filePos;
658 revertTemp();
659
660 // write the new version (after the commit)
661 writeFileHeader();
662 shrinkFileIfPossible(1);
663 // some pages might have been changed in the meantime (in the newest version)
664 unsavedPageCount = Math.max(0, unsavedPageCount - currentUnsavedPageCount);
665 return version;
666 }
667
668 private void applyFreedChunks() {
669 for (HashMap<Integer, Chunk> freed : freedChunks.values()) {
670 for (Chunk f : freed.values()) {
671 Chunk c = chunks.get(f.id);
672 c.maxLengthLive += f.maxLengthLive;
673 if (c.maxLengthLive < 0) {
674 throw new RuntimeException("Corrupt max length");
675 }
676 }
677 }
678 freedChunks.clear();
679 }
680
681 /**
682 * Shrink the file if possible, and if at least a given percentage can be
683 * saved.
684 *
685 * @param minPercent the minimum percentage to save
686 */
687 private void shrinkFileIfPossible(int minPercent) {
688 long used = getFileLengthUsed();
689 try {
690 if (used >= fileSize) {
691 return;
692 }
693 if (minPercent > 0 && fileSize - used < BLOCK_SIZE) {
694 return;
695 }
696 int savedPercent = (int) (100 - (used * 100 / fileSize));
697 if (savedPercent < minPercent) {
698 return;
699 }
700 file.truncate(used);
701 fileSize = used;
702 } catch (Exception e) {
703 throw convert(e);
704 }
705 }
706
707 private long getFileLengthUsed() {
708 int min = 2;
709 for (Chunk c : chunks.values()) {
710 if (c.start == Long.MAX_VALUE) {
711 continue;
712 }
713 int last = (int) ((c.start + c.length) / BLOCK_SIZE);
714 min = Math.max(min, last + 1);
715 }
716 return min * BLOCK_SIZE;
717 }
718
719 private long allocateChunk(long length) {
720 if (!reuseSpace) {
721 return getFileLengthUsed();
722 }
723 BitSet set = new BitSet();
724 set.set(0);
725 set.set(1);
726 for (Chunk c : chunks.values()) {
727 if (c.start == Long.MAX_VALUE) {
728 continue;
729 }
730 int first = (int) (c.start / BLOCK_SIZE);
731 int last = (int) ((c.start + c.length) / BLOCK_SIZE);
732 set.set(first, last +1);
733 }
734 int required = (int) (length / BLOCK_SIZE) + 1;
735 for (int i = 0; i < set.size(); i++) {
736 if (!set.get(i)) {
737 boolean ok = true;
738 for (int j = 0; j < required; j++) {
739 if (set.get(i + j)) {
740 ok = false;
741 break;
742 }
743 }
744 if (ok) {
745 return i * BLOCK_SIZE;
746 }
747 }
748 }
749 return set.size() * BLOCK_SIZE;
750 }
751
752 /**
753 * Check whether there are any unsaved changes.
754 *
755 * @return if there are any changes
756 */
757 public boolean hasUnsavedChanges() {
758 if (mapsChanged.size() == 0) {
759 return false;
760 }
761 for (MVMap<?, ?> m : mapsChanged.values()) {
762 if (m == meta || m.hasUnsavedChanges()) {
763 return true;
764 }
765 }
766 return false;
767 }
768
769 private Chunk readChunkHeader(long start) {
770 try {
771 fileReadCount++;
772 ByteBuffer buff = ByteBuffer.allocate(40);
773 DataUtils.readFully(file, start, buff);
774 buff.rewind();
775 return Chunk.fromHeader(buff, start);
776 } catch (IOException e) {
777 throw new RuntimeException(e);
778 }
779 }
780
781 /**
782 * Try to reduce the file size. Chunks with a low number of live items will
783 * be re-written. If the current fill rate is higher than the target fill
784 * rate, no optimization is done.
785 *
786 * @param fillRate the minimum percentage of live entries
787 * @return if anything was written
788 */
789 public boolean compact(int fillRate) {
790 if (chunks.size() == 0) {
791 // avoid division by 0
792 return false;
793 }
794 long maxLengthSum = 0, maxLengthLiveSum = 0;
795 for (Chunk c : chunks.values()) {
796 maxLengthSum += c.maxLength;
797 maxLengthLiveSum += c.maxLengthLive;
798 }
799 if (maxLengthSum <= 0) {
800 // avoid division by 0
801 maxLengthSum = 1;
802 }
803 int percentTotal = (int) (100 * maxLengthLiveSum / maxLengthSum);
804 if (percentTotal > fillRate) {
805 return false;
806 }
807
808 // calculate the average max length
809 int averageMaxLength = (int) (maxLengthSum / chunks.size());
810
811 // the 'old' list contains the chunks we want to free up
812 ArrayList<Chunk> old = New.arrayList();
813 for (Chunk c : chunks.values()) {
814 if (retainChunk == -1 || c.id < retainChunk) {
815 int age = lastChunkId - c.id + 1;
816 c.collectPriority = c.getFillRate() / age;
817 old.add(c);
818 }
819 }
820 if (old.size() == 0) {
821 return false;
822 }
823
824 // sort the list, so the first entry should be collected first
825 Collections.sort(old, new Comparator<Chunk>() {
826 public int compare(Chunk o1, Chunk o2) {
827 return new Integer(o1.collectPriority).compareTo(o2.collectPriority);
828 }
829 });
830
831 // find out up to were in the old list we need to move
832 // try to move one (average sized) chunk
833 long moved = 0;
834 Chunk move = null;
835 for (Chunk c : old) {
836 if (move != null && moved + c.maxLengthLive > averageMaxLength) {
837 break;
838 }
839 log(" chunk " + c.id + " " + c.getFillRate() + "% full; prio=" + c.collectPriority);
840 moved += c.maxLengthLive;
841 move = c;
842 }
843
844 // remove the chunks we want to keep from this list
845 boolean remove = false;
846 for (Iterator<Chunk> it = old.iterator(); it.hasNext();) {
847 Chunk c = it.next();
848 if (move == c) {
849 remove = true;
850 } else if (remove) {
851 it.remove();
852 }
853 }
854
855 // iterate over all the pages in the old pages
856 for (Chunk c : old) {
857 copyLive(c, old);
858 }
859
860 store();
861 return true;
862 }
863
864 private void copyLive(Chunk chunk, ArrayList<Chunk> old) {
865 ByteBuffer buff = ByteBuffer.allocate(chunk.length);
866 try {
867 DataUtils.readFully(file, chunk.start, buff);
868 } catch (IOException e) {
869 throw new RuntimeException(e);
870 }
871 Chunk.fromHeader(buff, chunk.start);
872 int chunkLength = chunk.length;
873 // mark a change, even if it doesn't look like there was a change
874 // as changes in the metadata alone are not detected
875 markChanged(meta);
876 while (buff.position() < chunkLength) {
877 int start = buff.position();
878 int pageLength = buff.getInt();
879 buff.getShort();
880 int mapId = DataUtils.readVarInt(buff);
881 @SuppressWarnings("unchecked")
882 MVMap<Object, Object> map = (MVMap<Object, Object>) getMap(mapId);
883 if (map == null) {
884 buff.position(start + pageLength);
885 continue;
886 }
887 buff.position(start);
888 Page page = new Page(map, 0);
889 page.read(buff, chunk.id, buff.position(), chunk.length);
890 for (int i = 0; i < page.getKeyCount(); i++) {
891 Object k = page.getKey(i);
892 Page p = map.getPage(k);
893 if (p == null) {
894 // was removed later - ignore
895 // or the chunk no longer exists
896 } else if (p.getPos() < 0) {
897 // temporarily changed - ok
898 // TODO move old data if there is an uncommitted change?
899 } else {
900 Chunk c = getChunk(p.getPos());
901 if (old.contains(c)) {
902 log(" move key:" + k + " chunk:" + c.id);
903 Object value = map.remove(k);
904 map.put(k, value);
905 }
906 }
907 }
908 }
909 }
910
911 private MVMap<?, ?> getMap(int mapId) {
912 if (mapId == 0) {
913 return meta;
914 }
915 for (MVMap<?, ?> m : maps.values()) {
916 if (m.getId() == mapId) {
917 return m;
918 }
919 }
920 return null;
921 }
922
923 /**
924 * Read a page.
925 *
926 * @param map the map
927 * @param pos the page position
928 * @return the page
929 */
930 Page readPage(MVMap<?, ?> map, long pos) {
931 Page p = cache.get(pos);
932 if (p == null) {
933 Chunk c = getChunk(pos);
934 if (c == null) {
935 throw new RuntimeException("Chunk " + DataUtils.getPageChunkId(pos) + " not found");
936 }
937 long filePos = c.start;
938 filePos += DataUtils.getPageOffset(pos);
939 fileReadCount++;
940 p = Page.read(file, map, pos, filePos, fileSize);
941 cache.put(pos, p, p.getMemory());
942 }
943 return p;
944 }
945
946 /**
947 * Remove a page.
948 *
949 * @param pos the position of the page
950 */
951 void removePage(long pos) {
952 // we need to keep temporary pages,
953 // to support reading old versions and rollback
954 if (pos == 0) {
955 unsavedPageCount--;
956 return;
957 }
958 // this could result in a cache miss
959 // if the operation is rolled back,
960 // but we don't optimize for rollback
961 cache.remove(pos);
962 Chunk c = getChunk(pos);
963 HashMap<Integer, Chunk>freed = freedChunks.get(currentVersion);
964 if (freed == null) {
965 freed = New.hashMap();
966 freedChunks.put(currentVersion, freed);
967 }
968 Chunk f = freed.get(c.id);
969 if (f == null) {
970 f = new Chunk(c.id);
971 freed.put(c.id, f);
972 }
973 f.maxLengthLive -= DataUtils.getPageMaxLength(pos);
974 }
975
976 /**
977 * Log the string, if logging is enabled.
978 *
979 * @param string the string to log
980 */
981 void log(String string) {
982 // TODO logging
983 // System.out.println(string);
984 }
985
986 /**
987 * Set the amount of memory a page should contain at most, in bytes. Larger
988 * pages are split. The default is 6 KB. This is not a limit in the page
989 * size (pages with one entry can get larger), it is just the point where
990 * pages are split.
991 *
992 * @param pageSize the page size
993 */
994 public void setPageSize(int pageSize) {
995 this.pageSize = pageSize;
996 }
997
998 /**
999 * Get the page size, in bytes.
1000 *
1001 * @return the page size
1002 */
1003 public int getPageSize() {
1004 return pageSize;
1005 }
1006
1007 Compressor getCompressor() {
1008 return compressor;
1009 }
1010
1011 public boolean getReuseSpace() {
1012 return reuseSpace;
1013 }
1014
1015 /**
1016 * Whether empty space in the file should be re-used. If enabled, old data
1017 * is overwritten (default). If disabled, writes are appended at the end of
1018 * the file.
1019 * <p>
1020 * This setting is specially useful for online backup. To create an online
1021 * backup, disable this setting, then copy the file (starting at the
1022 * beginning of the file). In this case, concurrent backup and write
1023 * operations are possible (obviously the backup process needs to be faster
1024 * than the write operations).
1025 *
1026 * @param reuseSpace the new value
1027 */
1028 public void setReuseSpace(boolean reuseSpace) {
1029 this.reuseSpace = reuseSpace;
1030 }
1031
1032 public int getRetainChunk() {
1033 return retainChunk;
1034 }
1035
1036 /**
1037 * Which chunk to retain. If not set, old chunks are re-used as soon as
1038 * possible, which may make it impossible to roll back beyond a save
1039 * operation, or read a older version before.
1040 * <p>
1041 * This setting is not persisted.
1042 *
1043 * @param retainChunk the earliest chunk to retain (0 to retain all chunks,
1044 * -1 to re-use space as early as possible)
1045 */
1046 public void setRetainChunk(int retainChunk) {
1047 this.retainChunk = retainChunk;
1048 }
1049
1050 /**
1051 * Which version to retain. If not set, all versions up to the last stored
1052 * version are retained.
1053 *
1054 * @param retainVersion the oldest version to retain
1055 */
1056 public void setRetainVersion(long retainVersion) {
1057 this.retainVersion = retainVersion;
1058 }
1059
1060 public long getRetainVersion() {
1061 return retainVersion;
1062 }
1063
1064 /**
1065 * Check whether all data can be read from this version. This requires that
1066 * all chunks referenced by this version are still available (not
1067 * overwritten).
1068 *
1069 * @param version the version
1070 * @return true if all data can be read
1071 */
1072 private boolean isKnownVersion(long version) {
1073 if (version > currentVersion || version < 0) {
1074 return false;
1075 }
1076 if (version == currentVersion || chunks.size() == 0) {
1077 // no stored data
1078 return true;
1079 }
1080 // need to check if a chunk for this version exists
1081 Chunk c = getChunkForVersion(version);
1082 if (c == null) {
1083 return false;
1084 }
1085 // also, all chunks referenced by this version
1086 // need to be available in the file
1087 MVMap<String, String> oldMeta = getMetaMap(version);
1088 if (oldMeta == null) {
1089 return false;
1090 }
1091 for (Iterator<String> it = oldMeta.keyIterator("chunk."); it.hasNext();) {
1092 String chunkKey = it.next();
1093 if (!chunkKey.startsWith("chunk.")) {
1094 break;
1095 }
1096 if (!meta.containsKey(chunkKey)) {
1097 return false;
1098 }
1099 }
1100 return true;
1101 }
1102
1103 /**
1104 * Get the estimated number of unsaved pages. The returned value is not
1105 * accurate, specially after rollbacks, but can be used to estimate the
1106 * memory usage for unsaved data.
1107 *
1108 * @return the number of unsaved pages
1109 */
1110 public int getUnsavedPageCount() {
1111 return unsavedPageCount;
1112 }
1113
1114 /**
1115 * Increment the number of unsaved pages.
1116 */
1117 void registerUnsavedPage() {
1118 unsavedPageCount++;
1119 }
1120
1121 /**
1122 * Get the store version. The store version is usually used to upgrade the
1123 * structure of the store after upgrading the application. Initially the
1124 * store version is 0, until it is changed.
1125 *
1126 * @return the store version
1127 */
1128 public int getStoreVersion() {
1129 String x = meta.get("setting.storeVersion");
1130 return x == null ? 0 : Integer.parseInt(x);
1131 }
1132
1133 /**
1134 * Update the store version.
1135 *
1136 * @param version the new store version
1137 */
1138 public void setStoreVersion(int version) {
1139 meta.put("setting.storeVersion", Integer.toString(version));
1140 }
1141
1142 /**
1143 * Revert to the beginning of the given version. All later changes (stored
1144 * or not) are forgotten. All maps that were created later are closed. A
1145 * rollback to a version before the last stored version is immediately
1146 * persisted.
1147 *
1148 * @param version the version to revert to
1149 */
1150 public void rollbackTo(long version) {
1151 if (!isKnownVersion(version)) {
1152 throw new IllegalArgumentException("Unknown version: " + version);
1153 }
1154 // TODO could remove newer temporary pages on rollback
1155 for (MVMap<?, ?> m : mapsChanged.values()) {
1156 m.rollbackTo(version);
1157 }
1158 for (long v = currentVersion; v >= version; v--) {
1159 if (freedChunks.size() == 0) {
1160 break;
1161 }
1162 freedChunks.remove(v);
1163 }
1164 meta.rollbackTo(version);
1165 boolean loadFromFile = false;
1166 Chunk last = chunks.get(lastChunkId);
1167 if (last != null) {
1168 if (last.version >= version) {
1169 revertTemp();
1170 loadFromFile = true;
1171 do {
1172 last = chunks.remove(lastChunkId);
1173 lastChunkId--;
1174 } while (last.version > version && chunks.size() > 0);
1175 rootChunkStart = last.start;
1176 writeFileHeader();
1177 readFileHeader();
1178 readMeta();
1179 }
1180 }
1181 for (MVMap<?, ?> m : maps.values()) {
1182 if (m.getCreateVersion() >= version) {
1183 m.close();
1184 removeMap(m.getName());
1185 } else {
1186 if (loadFromFile) {
1187 String r = meta.get("root." + m.getId());
1188 long root = r == null ? 0 : Long.parseLong(r);
1189 m.setRootPos(root, version);
1190 }
1191 }
1192 }
1193 this.currentVersion = version;
1194 }
1195
1196 private void revertTemp() {
1197 freedChunks.clear();
1198 for (MVMap<?, ?> m : mapsChanged.values()) {
1199 m.removeAllOldVersions();
1200 }
1201 mapsChanged.clear();
1202 }
1203
1204 /**
1205 * Get the current version of the data. When a new store is created, the
1206 * version is 0.
1207 *
1208 * @return the version
1209 */
1210 public long getCurrentVersion() {
1211 return currentVersion;
1212 }
1213
1214 /**
1215 * Get the number of file write operations since this store was opened.
1216 *
1217 * @return the number of write operations
1218 */
1219 public int getFileWriteCount() {
1220 return fileWriteCount;
1221 }
1222
1223 /**
1224 * Get the number of file read operations since this store was opened.
1225 *
1226 * @return the number of read operations
1227 */
1228 public int getFileReadCount() {
1229 return fileReadCount;
1230 }
1231
1232 /**
1233 * Get the file name, or null for in-memory stores.
1234 *
1235 * @return the file name
1236 */
1237 public String getFileName() {
1238 return fileName;
1239 }
1240
1241 /**
1242 * Get the file header. This data is for informational purposes only. The
1243 * data is subject to change in future versions. The data should not be
1244 * modified (doing so may corrupt the store).
1245 *
1246 * @return the file header
1247 */
1248 public Map<String, String> getFileHeader() {
1249 return fileHeader;
1250 }
1251
1252 /**
1253 * Get the file instance in use, if a file is used. The application may read
1254 * from the file (for example for online backup), but not write to it or
1255 * truncate it.
1256 *
1257 * @return the file, or null
1258 */
1259 public FileChannel getFile() {
1260 return file;
1261 }
1262
1263 public String toString() {
1264 return DataUtils.appendMap(new StringBuilder(), config).toString();
1265 }
1266
1267 }
1268