Debian Codegraph @

src/docsrc/html/mvstore.html

raw
1 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
2 <!--
3 Copyright 2004-2019 H2 Group. Multiple-Licensed under the MPL 2.0,
4 and the EPL 1.0 (http://h2database.com/html/license.html).
5 Initial Developer: H2 Group
6 -->
7 <html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
8 <head>
9 <meta http-equiv="Content-Type" content="text/html;charset=utf-8" />
10 <meta name="viewport" content="width=device-width, initial-scale=1" />
11 <title>
12 MVStore
13 </title>
14 <link rel="stylesheet" type="text/css" href="stylesheet.css" />
15 <!-- [search] { -->
16 <script type="text/javascript" src="navigation.js"></script>
17 </head><body onload="frameMe();">
18 <table class="content"><tr class="content"><td class="content"><div class="contentDiv">
19 <!-- } -->
20
21 <h1>MVStore</h1>
22 <a href="#overview">
23 Overview</a><br />
24 <a href="#example_code">
25 Example Code</a><br />
26 <a href="#store_builder">
27 Store Builder</a><br />
28 <a href="#r_tree">
29 R-Tree</a><br />
30
31 <a href="#features">
32 Features</a><br />
33 <a href="#maps">- Maps</a><br />
34 <a href="#versions">- Versions</a><br />
35 <a href="#transactions">- Transactions</a><br />
36 <a href="#inMemory">- In-Memory Performance and Usage</a><br />
37 <a href="#dataTypes">- Pluggable Data Types</a><br />
38 <a href="#blob">- BLOB Support</a><br />
39 <a href="#pluggableMap">- R-Tree and Pluggable Map Implementations</a><br />
40 <a href="#caching">- Concurrent Operations and Caching</a><br />
41 <a href="#logStructured">- Log Structured Storage</a><br />
42 <a href="#offHeap">- Off-Heap and Pluggable Storage</a><br />
43 <a href="#fileSystem">- File System Abstraction, File Locking and Online Backup</a><br />
44 <a href="#encryption">- Encrypted Files</a><br />
45 <a href="#tools">- Tools</a><br />
46 <a href="#exceptionHandling">- Exception Handling</a><br />
47 <a href="#storageEngine">- Storage Engine for H2</a><br />
48
49 <a href="#fileFormat">
50 File Format</a><br />
51
52 <a href="#differences">
53 Similar Projects and Differences to Other Storage Engines</a><br />
54 <a href="#current_state">
55 Current State</a><br />
56 <a href="#requirements">
57 Requirements</a><br />
58
59 <h2 id="overview">Overview</h2>
60 <p>
61 The MVStore is a persistent, log structured key-value store.
62 It is planned to be the next storage subsystem of H2,
63 but it can also be used directly within an application, without using JDBC or SQL.
64 </p>
65 <ul><li>MVStore stands for "multi-version store".
66 </li><li>Each store contains a number of maps that can be accessed using the <code>java.util.Map</code> interface.
67 </li><li>Both file-based persistence and in-memory operation are supported.
68 </li><li>It is intended to be fast, simple to use, and small.
69 </li><li>Concurrent read and write operations are supported.
70 </li><li>Transactions are supported (including concurrent transactions and 2-phase commit).
71 </li><li>The tool is very modular.
72 It supports pluggable data types and serialization,
73 pluggable storage (to a file, to off-heap memory),
74 pluggable map implementations (B-tree, R-tree, concurrent B-tree currently),
75 BLOB storage,
76 and a file system abstraction to support encrypted files and zip files.
77 </li></ul>
78
79 <h2 id="example_code">Example Code</h2>
80 <p>
81 The following sample code shows how to use the tool:
82 </p>
83 <pre>
84 import org.h2.mvstore.*;
85
86 // open the store (in-memory if fileName is null)
87 MVStore s = MVStore.open(fileName);
88
89 // create/get the map named "data"
90 MVMap&lt;Integer, String&gt; map = s.openMap("data");
91
92 // add and read some data
93 map.put(1, "Hello World");
94 System.out.println(map.get(1));
95
96 // close the store (this will persist changes)
97 s.close();
98 </pre>
99
100 <h2 id="store_builder">Store Builder</h2>
101 <p>
102 The <code>MVStore.Builder</code> provides a fluid interface
103 to build a store if configuration options are needed.
104 Example usage:
105 </p>
106 <pre>
107 MVStore s = new MVStore.Builder().
108 fileName(fileName).
109 encryptionKey("007".toCharArray()).
110 compress().
111 open();
112 </pre>
113 <p>
114 The list of available options is:
115 </p>
116 <ul><li>autoCommitBufferSize: the size of the write buffer.
117 </li><li>autoCommitDisabled: to disable auto-commit.
118 </li><li>backgroundExceptionHandler: a handler for
119 exceptions that could occur while writing in the background.
120 </li><li>cacheSize: the cache size in MB.
121 </li><li>compress: compress the data when storing
122 using a fast algorithm (LZF).
123 </li><li>compressHigh: compress the data when storing
124 using a slower algorithm (Deflate).
125 </li><li>encryptionKey: the key for file encryption.
126 </li><li>fileName: the name of the file, for file based stores.
127 </li><li>fileStore: the storage implementation to use.
128 </li><li>pageSplitSize: the point where pages are split.
129 </li><li>readOnly: open the file in read-only mode.
130 </li></ul>
131
132 <h2 id="r_tree">R-Tree</h2>
133 <p>
134 The <code>MVRTreeMap</code> is an R-tree implementation
135 that supports fast spatial queries. It can be used as follows:
136 </p>
137 <pre>
138 // create an in-memory store
139 MVStore s = MVStore.open(null);
140
141 // open an R-tree map
142 MVRTreeMap&lt;String&gt; r = s.openMap("data",
143 new MVRTreeMap.Builder&lt;String&gt;());
144
145 // add two key-value pairs
146 // the first value is the key id (to make the key unique)
147 // then the min x, max x, min y, max y
148 r.add(new SpatialKey(0, -3f, -2f, 2f, 3f), "left");
149 r.add(new SpatialKey(1, 3f, 4f, 4f, 5f), "right");
150
151 // iterate over the intersecting keys
152 Iterator&lt;SpatialKey&gt; it =
153 r.findIntersectingKeys(new SpatialKey(0, 0f, 9f, 3f, 6f));
154 for (SpatialKey k; it.hasNext();) {
155 k = it.next();
156 System.out.println(k + ": " + r.get(k));
157 }
158 s.close();
159 </pre>
160 <p>
161 The default number of dimensions is 2. To use a different number of dimensions,
162 call <code>new MVRTreeMap.Builder&lt;String&gt;().dimensions(3)</code>.
163 The minimum number of dimensions is 1, the maximum is 32.
164 </p>
165
166 <h2 id="features">Features</h2>
167
168 <h3 id="maps">Maps</h3>
169 <p>
170 Each store contains a set of named maps.
171 A map is sorted by key, and supports the common lookup operations,
172 including access to the first and last key, iterate over some or all keys, and so on.
173 </p><p>
174 Also supported, and very uncommon for maps, is fast index lookup:
175 the entries of the map can be efficiently accessed like a random-access list
176 (get the entry at the given index), and the index of a key can be calculated efficiently.
177 That also means getting the median of two keys is very fast,
178 and a range of keys can be counted very quickly.
179 The iterator supports fast skipping.
180 This is possible because internally, each map is organized in the form of a counted B+-tree.
181 </p><p>
182 In database terms, a map can be used like a table, where the key of the map is the primary key of the table,
183 and the value is the row. A map can also represent an index, where the key of the map is the key
184 of the index, and the value of the map is the primary key of the table (for non-unique indexes,
185 the key of the map must also contain the primary key).
186 </p>
187
188 <h3 id="versions">Versions</h3>
189 <p>
190 A version is a snapshot of all the data of all maps at a given point in time.
191 Creating a snapshot is fast: only those pages that are changed after a snapshot are copied.
192 This behavior is also called COW (copy on write).
193 Old versions are readable.
194 Rollback to an old version is supported.
195 </p><p>
196 The following sample code show how to create a store, open a map, add some data,
197 and access the current and an old version:
198 </p>
199 <pre>
200 // create/get the map named "data"
201 MVMap&lt;Integer, String&gt; map = s.openMap("data");
202
203 // add some data
204 map.put(1, "Hello");
205 map.put(2, "World");
206
207 // get the current version, for later use
208 long oldVersion = s.getCurrentVersion();
209
210 // from now on, the old version is read-only
211 s.commit();
212
213 // more changes, in the new version
214 // changes can be rolled back if required
215 // changes always go into "head" (the newest version)
216 map.put(1, "Hi");
217 map.remove(2);
218
219 // access the old data (before the commit)
220 MVMap&lt;Integer, String&gt; oldMap =
221 map.openVersion(oldVersion);
222
223 // print the old version (can be done
224 // concurrently with further modifications)
225 // this will print "Hello" and "World":
226 System.out.println(oldMap.get(1));
227 System.out.println(oldMap.get(2));
228
229 // print the newest version ("Hi")
230 System.out.println(map.get(1));
231 </pre>
232
233 <h3 id="transactions">Transactions</h3>
234 <p>
235 To support multiple concurrent open transactions, a transaction utility is included,
236 the <code>TransactionStore</code>.
237 The tool supports "read committed" transaction isolation
238 with savepoints, two-phase commit, and other features typically available in a database.
239 There is no limit on the size of a transaction
240 (the log is written to disk for large or long running transactions).
241 </p><p>
242 Internally, this utility stores the old versions of changed entries in a separate map, similar to a transaction log,
243 except that entries of a closed transaction are removed, and the log is usually not stored for short transactions.
244 For common use cases, the storage overhead of this utility is very small compared to the overhead of a regular transaction log.
245 </p>
246
247 <h3 id="inMemory">In-Memory Performance and Usage</h3>
248 <p>
249 Performance of in-memory operations is about 50% slower than
250 <code>java.util.TreeMap</code>.
251 </p><p>
252 The memory overhead for large maps is slightly better than for the regular
253 map implementations, but there is a higher overhead per map.
254 For maps with less than about 25 entries, the regular map implementations need less memory.
255 </p><p>
256 If no file name is specified, the store operates purely in memory.
257 Except for persisting data, all features are supported in this mode
258 (multi-versioning, index lookup, R-tree and so on).
259 If a file name is specified, all operations occur in memory (with the same
260 performance characteristics) until data is persisted.
261 </p><p>
262 As in all map implementations, keys need to be immutable, that means
263 changing the key object after an entry has been added is not allowed.
264 If a file name is specified, the value may also not be changed after
265 adding an entry, because it might be serialized
266 (which could happen at any time when autocommit is enabled).
267 </p>
268
269 <h3 id="dataTypes">Pluggable Data Types</h3>
270 <p>
271 Serialization is pluggable. The default serialization currently supports many common data types,
272 and uses Java serialization for other objects. The following classes are currently directly supported:
273 <code>Boolean, Byte, Short, Character, Integer, Long, Float, Double, BigInteger, BigDecimal,
274 String, UUID, Date</code> and arrays (both primitive arrays and object arrays).
275 For serialized objects, the size estimate is adjusted using an exponential moving average.
276 </p><p>
277 Parameterized data types are supported
278 (for example one could build a string data type that limits the length).
279 </p><p>
280 The storage engine itself does not have any length limits, so that keys, values,
281 pages, and chunks can be very big (as big as fits in memory).
282 Also, there is no inherent limit to the number of maps and chunks.
283 Due to using a log structured storage, there is no special case handling for large keys or pages.
284 </p>
285
286 <h3 id="blob">BLOB Support</h3>
287 <p>
288 There is a mechanism that stores large binary objects by splitting them into smaller blocks.
289 This allows to store objects that don't fit in memory.
290 Streaming as well as random access reads on such objects are supported.
291 This tool is written on top of the store, using only the map interface.
292 </p>
293
294 <h3 id="pluggableMap">R-Tree and Pluggable Map Implementations</h3>
295 <p>
296 The map implementation is pluggable.
297 In addition to the default <code>MVMap</code> (multi-version map),
298 there is a multi-version R-tree map implementation for spatial operations.
299 </p>
300
301 <h3 id="caching">Concurrent Operations and Caching</h3>
302 <p>
303 Concurrent reads and writes are supported.
304 All such read operations can occur in parallel. Concurrent reads from the page cache,
305 as well as concurrent reads from the file system are supported.
306 Write operations first read the relevant pages from disk to memory
307 (this can happen concurrently), and only then modify the data.
308 The in-memory parts of write operations are synchronized.
309 Writing changes to the file can occur concurrently to modifying the data,
310 as writing operates on a snapshot.
311 </p><p>
312 Caching is done on the page level.
313 The page cache is a concurrent LIRS cache, which should be resistant against scan operations.
314 </p><p>
315 For fully scalable concurrent write operations to a map (in-memory and to disk),
316 the map could be split into multiple maps in different stores ('sharding').
317 The plan is to add such a mechanism later when needed.
318 </p>
319
320 <h3 id="logStructured">Log Structured Storage</h3>
321 <p>
322 Internally, changes are buffered in memory, and once enough changes have accumulated,
323 they are written in one continuous disk write operation.
324 Compared to traditional database storage engines,
325 this should improve write performance for file systems and storage systems
326 that do not efficiently support small random writes, such as Btrfs, as well as SSDs.
327 (According to a test, write throughput of a common SSD increases with write block size,
328 until a block size of 2 MB, and then does not further increase.)
329 By default, changes are automatically written when more than a number of pages are modified,
330 and once every second in a background thread, even if only little data was changed.
331 Changes can also be written explicitly by calling <code>commit()</code>.
332 </p><p>
333 When storing, all changed pages are serialized,
334 optionally compressed using the LZF algorithm,
335 and written sequentially to a free area of the file.
336 Each such change set is called a chunk.
337 All parent pages of the changed B-trees are stored in this chunk as well,
338 so that each chunk also contains the root of each changed map
339 (which is the entry point for reading this version of the data).
340 There is no separate index: all data is stored as a list of pages.
341 Per store, there is one additional map that contains the metadata (the list of
342 maps, where the root page of each map is stored, and the list of chunks).
343 </p><p>
344 There are usually two write operations per chunk:
345 one to store the chunk data (the pages), and one to update the file header (so it points to the latest chunk).
346 If the chunk is appended at the end of the file, the file header is only written at the end of the chunk.
347 There is no transaction log, no undo log,
348 and there are no in-place updates (however, unused chunks are overwritten by default).
349 </p><p>
350 Old data is kept for at least 45 seconds (configurable),
351 so that there are no explicit sync operations required to guarantee data consistency.
352 An application can also sync explicitly when needed.
353 To reuse disk space, the chunks with the lowest amount of live data are compacted
354 (the live data is stored again in the next chunk).
355 To improve data locality and disk space usage, the plan is to automatically defragment and compact data.
356 </p><p>
357 Compared to traditional storage engines (that use a transaction log, undo log, and main storage area),
358 the log structured storage is simpler, more flexible, and typically needs less disk operations per change,
359 as data is only written once instead of twice or 3 times, and because the B-tree pages are
360 always full (they are stored next to each other) and can be easily compressed.
361 But temporarily, disk space usage might actually be a bit higher than for a regular database,
362 as disk space is not immediately re-used (there are no in-place updates).
363 </p>
364
365 <h3 id="offHeap">Off-Heap and Pluggable Storage</h3>
366 <p>
367 Storage is pluggable. Unless pure in-memory operation is used, the default storage is to a single file.
368 </p>
369 <p>
370 An off-heap storage implementation is available. This storage keeps the data in the off-heap memory,
371 meaning outside of the regular garbage collected heap. This allows to use very large in-memory
372 stores without having to increase the JVM heap, which would increase Java garbage collection
373 pauses a lot. Memory is allocated using <code>ByteBuffer.allocateDirect</code>.
374 One chunk is allocated at a time (each chunk is usually a few MB large), so that
375 allocation cost is low. To use the off-heap storage, call:
376 </p>
377 <pre>
378 OffHeapStore offHeap = new OffHeapStore();
379 MVStore s = new MVStore.Builder().
380 fileStore(offHeap).open();
381 </pre>
382
383 <h3 id="fileSystem">File System Abstraction, File Locking and Online Backup</h3>
384 <p>
385 The file system is pluggable. The same file system abstraction is used as H2 uses.
386 The file can be encrypted using a encrypting file system wrapper.
387 Other file system implementations support reading from a compressed zip or jar file.
388 The file system abstraction closely matches the Java 7 file system API.
389 </p>
390 <p>
391 Each store may only be opened once within a JVM.
392 When opening a store, the file is locked in exclusive mode, so that
393 the file can only be changed from within one process.
394 Files can be opened in read-only mode, in which case a shared lock is used.
395 </p>
396 <p>
397 The persisted data can be backed up at any time,
398 even during write operations (online backup).
399 To do that, automatic disk space reuse needs to be first disabled, so that
400 new data is always appended at the end of the file.
401 Then, the file can be copied. The file handle is available to the application.
402 It is recommended to use the utility class <code>FileChannelInputStream</code> to do this.
403 For encrypted databases, both the encrypted (raw) file content,
404 as well as the clear text content, can be backed up.
405 </p>
406
407 <h3 id="encryption">Encrypted Files</h3>
408 <p>
409 File encryption ensures the data can only be read with the correct password.
410 Data can be encrypted as follows:
411 </p>
412 <pre>
413 MVStore s = new MVStore.Builder().
414 fileName(fileName).
415 encryptionKey("007".toCharArray()).
416 open();
417 </pre>
418 <p>
419 </p><p>
420 The following algorithms and settings are used:
421 </p>
422 <ul><li>The password char array is cleared after use,
423 to reduce the risk that the password is stolen
424 even if the attacker has access to the main memory.
425 </li><li>The password is hashed according to the PBKDF2 standard,
426 using the SHA-256 hash algorithm.
427 </li><li>The length of the salt is 64 bits,
428 so that an attacker can not use a pre-calculated password hash table (rainbow table).
429 It is generated using a cryptographically secure random number generator.
430 </li><li>To speed up opening an encrypted stores on Android,
431 the number of PBKDF2 iterations is 10.
432 The higher the value, the better the protection against brute-force password cracking attacks,
433 but the slower is opening a file.
434 </li><li>The file itself is encrypted using the standardized disk encryption mode XTS-AES.
435 Only little more than one AES-128 round per block is needed.
436 </li></ul>
437
438 <h3 id="tools">Tools</h3>
439 <p>
440 There is a tool, the <code>MVStoreTool</code>, to dump the contents of a file.
441 </p>
442
443 <h3 id="exceptionHandling">Exception Handling</h3>
444 <p>
445 This tool does not throw checked exceptions.
446 Instead, unchecked exceptions are thrown if needed.
447 The error message always contains the version of the tool.
448 The following exceptions can occur:
449 </p>
450 <ul><li><code>IllegalStateException</code> if a map was already closed or
451 an IO exception occurred, for example if the file was locked, is already closed,
452 could not be opened or closed, if reading or writing failed,
453 if the file is corrupt, or if there is an internal error in the tool.
454 For such exceptions, an error code is added
455 so that the application can distinguish between different error cases.
456 </li><li><code>IllegalArgumentException</code> if a method was called with an illegal argument.
457 </li><li><code>UnsupportedOperationException</code> if a method was called that is not supported,
458 for example trying to modify a read-only map.
459 </li><li><code>ConcurrentModificationException</code> if a map is modified concurrently.
460 </li></ul>
461
462 <h3 id="storageEngine">Storage Engine for H2</h3>
463 <p>
464 For H2 version 1.4 and newer, the MVStore is the default storage engine
465 (supporting SQL, JDBC, transactions, MVCC, and so on).
466 For older versions, append
467 <code>;MV_STORE=TRUE</code>
468 to the database URL.
469 </p>
470
471 <h2 id="fileFormat">File Format</h2>
472 <p>
473 The data is stored in one file.
474 The file contains two file headers (for safety), and a number of chunks.
475 The file headers are one block each; a block is 4096 bytes.
476 Each chunk is at least one block, but typically 200 blocks or more.
477 Data is stored in the chunks in the form of a
478 <a href="https://en.wikipedia.org/wiki/Log-structured_file_system">log structured storage</a>.
479 There is one chunk for every version.
480 </p>
481 <pre>
482 [ file header 1 ] [ file header 2 ] [ chunk ] [ chunk ] ... [ chunk ]
483 </pre>
484 <p>
485 Each chunk contains a number of B-tree pages.
486 As an example, the following code:
487 </p>
488 <pre>
489 MVStore s = MVStore.open(fileName);
490 MVMap&lt;Integer, String&gt; map = s.openMap("data");
491 for (int i = 0; i &lt; 400; i++) {
492 map.put(i, "Hello");
493 }
494 s.commit();
495 for (int i = 0; i &lt; 100; i++) {
496 map.put(i, "Hi");
497 }
498 s.commit();
499 s.close();
500 </pre>
501 <p>
502 will result in the following two chunks (excluding metadata):
503 </p>
504 <p>
505 <b>Chunk 1:</b><br />
506 - Page 1: (root) node with 2 entries pointing to page 2 and 3<br />
507 - Page 2: leaf with 140 entries (keys 0 - 139)<br />
508 - Page 3: leaf with 260 entries (keys 140 - 399)<br />
509 </p>
510 <p>
511 <b>Chunk 2:</b><br />
512 - Page 4: (root) node with 2 entries pointing to page 5 and 3<br />
513 - Page 5: leaf with 140 entries (keys 0 - 139)<br />
514 </p>
515 <p>
516 That means each chunk contains the changes of one version:
517 the new version of the changed pages and the parent pages, recursively, up to the root page.
518 Pages in subsequent chunks refer to pages in earlier chunks.
519 </p>
520
521 <h3>File Header</h3>
522 <p>
523 There are two file headers, which normally contain the exact same data.
524 But once in a while, the file headers are updated, and writing could partially fail,
525 which could corrupt a header. That's why there is a second header.
526 Only the file headers are updated in this way (called "in-place update").
527 The headers contain the following data:
528 </p>
529 <pre>
530 H:2,block:2,blockSize:1000,chunk:7,created:1441235ef73,format:1,version:7,fletcher:3044e6cc
531 </pre>
532 <p>
533 The data is stored in the form of a key-value pair.
534 Each value is stored as a hexadecimal number. The entries are:
535 </p>
536 <ul><li>H: The entry "H:2" stands for the H2 database.
537 </li><li>block: The block number where one of the newest chunks starts
538 (but not necessarily the newest).
539 </li><li>blockSize: The block size of the file; currently always hex 1000, which is decimal 4096,
540 to match the <a href="https://en.wikipedia.org/wiki/Disk_sector">disk sector</a>
541 length of modern hard disks.
542 </li><li>chunk: The chunk id, which is normally the same value as the version;
543 however, the chunk id might roll over to 0, while the version doesn't.
544 </li><li>created: The number of milliseconds since 1970 when the file was created.
545 </li><li>format: The file format number. Currently 1.
546 </li><li>version: The version number of the chunk.
547 </li><li>fletcher: The <a href="https://en.wikipedia.org/wiki/Fletcher's_checksum">
548 Fletcher-32 checksum</a> of the header.
549 </li></ul>
550 <p>
551 When opening the file, both headers are read and the checksum is verified.
552 If both headers are valid, the one with the newer version is used.
553 The chunk with the latest version is then detected (details about this see below),
554 and the rest of the metadata is read from there.
555 If the chunk id, block and version are not stored in the file header,
556 then the latest chunk lookup starts with the last chunk in the file.
557 </p>
558 <p>
559 </p>
560
561 <h3>Chunk Format</h3>
562 <p>
563 There is one chunk per version.
564 Each chunk consists of a header, the pages that were modified in this version, and a footer.
565 The pages contain the actual data of the maps.
566 The pages inside a chunk are stored right after the header, next to each other (unaligned).
567 The size of a chunk is a multiple of the block size.
568 The footer is stored in the last 128 bytes of the chunk.
569 </p>
570 <pre>
571 [ header ] [ page ] [ page ] ... [ page ] [ footer ]
572 </pre>
573 <p>
574 The footer allows to verify that the chunk is completely written (a chunk is written as one write operation),
575 and allows to find the start position of the very last chunk in the file.
576 The chunk header and footer contain the following data:
577 </p>
578 <pre>
579 chunk:1,block:2,len:1,map:6,max:1c0,next:3,pages:2,root:4000004f8c,time:1fc,version:1
580 chunk:1,block:2,version:1,fletcher:aed9a4f6
581 </pre>
582 <p>
583 The fields of the chunk header and footer are:
584 </p>
585 <ul><li>chunk: The chunk id.
586 </li><li>block: The first block of the chunk (multiply by the block size to get the position in the file).
587 </li><li>len: The size of the chunk in number of blocks.
588 </li><li>map: The id of the newest map; incremented when a new map is created.
589 </li><li>max: The sum of all maximum page sizes (see page format).
590 </li><li>next: The predicted start block of the next chunk.
591 </li><li>pages: The number of pages in the chunk.
592 </li><li>root: The position of the metadata root page (see page format).
593 </li><li>time: The time the chunk was written, in milliseconds after the file was created.
594 </li><li>version: The version this chunk represents.
595 </li><li>fletcher: The checksum of the footer.
596 </li></ul>
597 <p>
598 Chunks are never updated in-place. Each chunk contains the pages that were
599 changed in that version (there is one chunk per version, see above),
600 plus all the parent nodes of those pages, recursively, up to the root page.
601 If an entry in a map is changed, removed, or added, then the respective page is copied,
602 modified, and stored in the next chunk, and the number of live pages in the old chunk is decremented.
603 This mechanism is called copy-on-write, and is similar to how the
604 <a href="https://en.wikipedia.org/wiki/Btrfs">Btrfs</a> file system works.
605 Chunks without live pages are marked as free, so the space can be re-used by more recent chunks.
606 Because not all chunks are of the same size, there can be a number of free blocks in front of a chunk
607 for some time (until a small chunk is written or the chunks are compacted).
608 There is a <a href="http://stackoverflow.com/questions/13650134/after-how-many-seconds-are-file-system-write-buffers-typically-flushed">
609 delay of 45 seconds</a> (by default) before a free chunk is overwritten,
610 to ensure new versions are persisted first.
611 </p>
612 <p>
613 How the newest chunk is located when opening a store:
614 The file header contains the position of a recent chunk, but not always the newest one.
615 This is to reduce the number of file header updates.
616 After opening the file, the file headers, and the chunk footer of the very last chunk
617 (at the end of the file) are read.
618 From those candidates, the header of the most recent chunk is read.
619 If it contains a "next" pointer (see above), those chunk's header and footer are read as well.
620 If it turned out to be a newer valid chunk, this is repeated, until the newest chunk was found.
621 Before writing a chunk, the position of the next chunk is predicted based on the assumption
622 that the next chunk will be of the same size as the current one.
623 When the next chunk is written, and the previous
624 prediction turned out to be incorrect, the file header is updated as well.
625 In any case, the file header is updated if the next chain gets longer than 20 hops.
626 </p>
627
628 <h3>Page Format</h3>
629 <p>
630 Each map is a <a href="https://en.wikipedia.org/wiki/B-tree">B-tree</a>,
631 and the map data is stored in (B-tree-) pages.
632 There are leaf pages that contain the key-value pairs of the map,
633 and internal nodes, which only contain keys and pointers to leaf pages.
634 The root of a tree is either a leaf or an internal node.
635 Unlike file header and chunk header and footer, the page data is not human readable.
636 Instead, it is stored as byte arrays, with long (8 bytes), int (4 bytes), short (2 bytes),
637 and <a href="https://en.wikipedia.org/wiki/Variable-length_quantity">variable size int and long</a>
638 (1 to 5 / 10 bytes). The page format is:
639 </p>
640 <ul><li>length (int): Length of the page in bytes.
641 </li><li>checksum (short): Checksum (chunk id xor offset within the chunk xor page length).
642 </li><li>mapId (variable size int): The id of the map this page belongs to.
643 </li><li>len (variable size int): The number of keys in the page.
644 </li><li>type (byte): The page type (0 for leaf page, 1 for internal node;
645 plus 2 if the keys and values are compressed with the LZF algorithm, or
646 plus 6 if the keys and values are compressed with the Deflate algorithm).
647 </li><li>children (array of long; internal nodes only): The position of the children.
648 </li><li>childCounts (array of variable size long; internal nodes only):
649 The total number of entries for the given child page.
650 </li><li>keys (byte array): All keys, stored depending on the data type.
651 </li><li>values (byte array; leaf pages only): All values, stored depending on the data type.
652 </li></ul>
653 <p>
654 Even though this is not required by the file format, pages are stored in the following order:
655 For each map, the root page is stored first, then the internal nodes (if there are any),
656 and then the leaf pages.
657 This should speed up reads for media where sequential reads are faster than random access reads.
658 The metadata map is stored at the end of a chunk.
659 </p>
660 <p>
661 Pointers to pages are stored as a long, using a special format:
662 26 bits for the chunk id, 32 bits for the offset within the chunk, 5 bits for the length code,
663 1 bit for the page type (leaf or internal node).
664 The page type is encoded so that when clearing or removing a map, leaf pages don't
665 have to be read (internal nodes do have to be read in order to know where all the pages are;
666 but in a typical B-tree the vast majority of the pages are leaf pages).
667 The absolute file position is not included so that chunks can be
668 moved within the file without having to change page pointers;
669 only the chunk metadata needs to be changed.
670 The length code is a number from 0 to 31, where 0 means the maximum length
671 of the page is 32 bytes, 1 means 48 bytes, 2: 64, 3: 96, 4: 128, 5: 192, and so on until 31 which
672 means longer than 1 MB. That way, reading a page only requires one
673 read operation (except for very large pages).
674 The sum of the maximum length of all pages is stored in the chunk metadata (field "max"),
675 and when a page is marked as removed, the live maximum length is adjusted.
676 This allows to estimate the amount of free space within a block, in addition to the number of free pages.
677 </p>
678 <p>
679 The total number of entries in child pages are kept to allow efficient range counting,
680 lookup by index, and skip operations.
681 The pages form a <a href="https://www.chiark.greenend.org.uk/~sgtatham/algorithms/cbtree.html">counted B-tree</a>.
682 </p>
683 <p>
684 Data compression: The data after the page type are optionally compressed using the LZF algorithm.
685 </p>
686
687 <h3>Metadata Map</h3>
688 <p>
689 In addition to the user maps, there is one metadata map that contains names and
690 positions of user maps, and chunk metadata.
691 The very last page of a chunk contains the root page of that metadata map.
692 The exact position of this root page is stored in the chunk header.
693 This page (directly or indirectly) points to the root pages of all other maps.
694 The metadata map of a store with a map named "data", and one chunk,
695 contains the following entries:
696 </p>
697 <ul><li>chunk.1: The metadata of chunk 1. This is the same data as the chunk header,
698 plus the number of live pages, and the maximum live length.
699 </li><li>map.1: The metadata of map 1. The entries are: name, createVersion, and type.
700 </li><li>name.data: The map id of the map named "data". The value is "1".
701 </li><li>root.1: The root position of map 1.
702 </li><li>setting.storeVersion: The store version (a user defined value).
703 </li></ul>
704
705 <h2 id="differences">Similar Projects and Differences to Other Storage Engines</h2>
706 <p>
707 Unlike similar storage engines like LevelDB and Kyoto Cabinet,
708 the MVStore is written in Java
709 and can easily be embedded in a Java and Android application.
710 </p><p>
711 The MVStore is somewhat similar to the Berkeley DB Java Edition
712 because it is also written in Java,
713 and is also a log structured storage, but the H2 license is more liberal.
714 </p><p>
715 Like SQLite 3, the MVStore keeps all data in one file.
716 Unlike SQLite 3, the MVStore uses is a log structured storage.
717 The plan is to make the MVStore both easier to use as well as faster than SQLite 3.
718 In a recent (very simple) test, the MVStore was about twice as fast as SQLite 3 on Android.
719 </p><p>
720 The API of the MVStore is similar to MapDB (previously known as JDBM) from Jan Kotek,
721 and some code is shared between MVStore and MapDB.
722 However, unlike MapDB, the MVStore uses is a log structured storage.
723 The MVStore does not have a record size limit.
724 </p>
725
726 <h2 id="current_state">Current State</h2>
727 <p>
728 The code is still experimental at this stage.
729 The API as well as the behavior may partially change.
730 Features may be added and removed (even though the main features will stay).
731 </p>
732
733 <h2 id="requirements">Requirements</h2>
734 <p>
735 The MVStore is included in the latest H2 jar file.
736 </p><p>
737 There are no special requirements to use it.
738 The MVStore should run on any JVM as well as on Android.
739 </p><p>
740 To build just the MVStore (without the database engine), run:
741 </p>
742 <pre>
743 ./build.sh jarMVStore
744 </pre>
745 <p>
746 This will create the file <code>bin/h2mvstore-${version}.jar</code> (about 200 KB).
747 </p>
748
749 <!-- [close] { --></div></td></tr></table><!-- } --><!-- analytics --></body></html>