| 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<Integer, String> 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<String> r = s.openMap("data", |
| 143 |
new MVRTreeMap.Builder<String>()); |
| 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<SpatialKey> 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<String>().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<Integer, String> 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<Integer, String> 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<Integer, String> map = s.openMap("data"); |
| 491 |
for (int i = 0; i < 400; i++) { |
| 492 |
map.put(i, "Hello"); |
| 493 |
} |
| 494 |
s.commit(); |
| 495 |
for (int i = 0; i < 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> |