mvstore.html 16.0 KB
Newer Older
1 2 3 4 5 6 7 8 9
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<!--
Copyright 2004-2011 H2 Group. Multiple-Licensed under the H2 License, Version 1.0,
and under the Eclipse Public License, Version 1.0
(http://h2database.com/html/license.html).
Initial Developer: H2 Group
-->
<html xmlns="http://www.w3.org/1999/xhtml" lang="en" xml:lang="en">
<head><meta http-equiv="Content-Type" content="text/html;charset=utf-8" /><title>
10
MVStore
11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
</title><link rel="stylesheet" type="text/css" href="stylesheet.css" />
<!-- [search] { -->
<script type="text/javascript" src="navigation.js"></script>
</head><body onload="frameMe();">
<table class="content"><tr class="content"><td class="content"><div class="contentDiv">
<!-- } -->

<h1>MVStore</h1>
<a href="#overview">
    Overview</a><br />
<a href="#example_code">
    Example Code</a><br />
<a href="#features">
    Features</a><br />
<a href="#differences">
    Similar Projects and Differences to Other Storage Engines</a><br />
<a href="#current_state">
    Current State</a><br />
<a href="#requirements">
    Requirements</a><br />

<h2 id="overview">Overview</h2>
33 34
<p>
The MVStore is work in progress, and is planned to be the next storage subsystem of H2.
Thomas Mueller's avatar
Thomas Mueller committed
35
But it can be also directly within an application, without using JDBC or SQL.
36
</p>
37 38
<ul><li>MVStore stands for multi-version store.
</li><li>Each store contains a number of maps (using the <code>java.util.Map</code> interface).
Thomas Mueller's avatar
Thomas Mueller committed
39
</li><li>Both file based persistence and in-memory operation are supported.
40 41
</li><li>It is intended to be fast, simple to use, and small.
</li><li>Old versions of the data can be read concurrently with all other operations.
42
</li><li>Transaction are supported (currently only one transaction at a time).
43 44 45
</li><li>Transactions (even if they are persisted) can be rolled back.
</li><li>The tool is very modular. It supports pluggable data types / serialization,
pluggable map implementations (B-tree and R-tree currently), BLOB storage,
46
and a file system abstraction to support encryption and compressed read-only files.
47 48 49
</li></ul>

<h2 id="example_code">Example Code</h2>
50 51 52 53 54
<h3>Map Operations and Versioning</h3>
<p>
The following sample code show how to create a store,
open a map, add some data, and access the current and an old version.
</p>
55
<pre>
Thomas Mueller's avatar
Thomas Mueller committed
56 57
import org.h2.mvstore.*;

58 59 60
// open the store (in-memory if fileName is null)
MVStore s = MVStore.open(fileName);

61
// create/get the map named "data"
62
MVMap&lt;Integer, String&gt; map = s.openMap("data");
63 64

// add some data
65 66
map.put(1, "Hello");
map.put(2, "World");
67 68 69 70 71 72 73 74 75 76

// get the current version, for later use
long oldVersion = s.getCurrentVersion();

// from now on, the old version is read-only
s.incrementVersion();

// more changes, in the new version
// changes can be rolled back if required
// changes always go into 'head' (the newest version)
77 78
map.put(1, "Hi");
map.remove(2);
79 80

// access the old data (before incrementVersion)
81
MVMap&lt;Integer, String&gt; oldMap =
82 83 84 85 86 87 88 89
        map.openVersion(oldVersion);

// store the newest data to disk
s.store();

// print the old version (can be done
// concurrently with further modifications)
// this will print Hello World
90 91 92
System.out.println(oldMap.get(1));
System.out.println(oldMap.get(2));
oldMap.close();
93 94

// print the newest version ("Hi")
95
System.out.println(map.get(1));
96 97 98 99 100

// close the store - this doesn't write to disk
s.close();
</pre>

101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124
<h3>Store Builder</h3>
<p>
The <code>MVStoreBuilder</code> provides a fluid interface
to build a store if more complex configuration options are used.
</p>
<pre>
MVStore s = MVStoreBuilder.
    fileBased(fileName).
    cacheSizeMB(10).
    readOnly().
    open();
</pre>

<h3>R-Tree</h3>
<p>
The <code>MVRTreeMap</code> is an R-tree implementation
that supports fast spatial queries.
</p>
<pre>
// create an in-memory store
MVStore s = MVStore.open(null);

// create an R-tree map
// the key has 2 dimensions, the value is a string
125
MVRTreeMap&lt;String&gt; r = MVRTreeMap.create(2, new ObjectType());
126 127 128 129 130 131 132 133 134 135 136

// open the map
r = s.openMap("data", r);

// add two key-value pairs
// the first value is the key id (to make the key unique)
// then the min x, max x, min y, max y
r.add(new SpatialKey(0, -3f, -2f, 2f, 3f), "left");
r.add(new SpatialKey(1, 3f, 4f, 4f, 5f), "right");

// iterate over the intersecting keys
137
Iterator&lt;SpatialKey&gt; it =
138 139 140 141 142 143 144 145
        r.findIntersectingKeys(new SpatialKey(0, 0f, 9f, 3f, 6f));
for (SpatialKey k; it.hasNext();) {
    k = it.next();
    System.out.println(k + ": " + r.get(k));
}
s.close();
</pre>

146 147 148 149 150 151

<h2 id="features">Features</h2>

<h3>Maps</h3>
<p>
Each store supports a set of named maps.
152
A map is sorted by key, and supports the common lookup operations,
153 154
including access to the first and last key, iterate over some or all keys, and so on.
</p><p>
155 156 157 158 159 160 161
Also supported, and very uncommon for maps, is fast index lookup.
The keys of the map can be accessed like a list
(get the key at the given index, get the index of a certain key).
That means getting the median of two keys is trivial,
and it allows to very quickly count ranges.
The iterator supports fast skipping.
This is possible because internally, each map is organized in the form of a counted B+-tree.
162
</p><p>
163
In database terms, a map can be used like a table, where the key of the map is the primary key of the table,
164
and the value is the row. A map can also represent an index, where the key of the map is the key
Thomas Mueller's avatar
Thomas Mueller committed
165
of the index, and the value of the map is the primary key of the table (for non-unique indexes,
166
the key of the map must also contain the primary key).
167 168 169 170 171 172 173 174 175 176
</p>

<h3>Versions / Transactions</h3>
<p>
Multiple versions are supported.
A version is a snapshot of all the data of all maps at a given point in time.
A transaction is a number of actions between two versions.
</p><p>
Versions / transactions are not immediately persisted; instead, only the version counter is incremented.
If there is a change after switching to a new version, a snapshot of the old version is kept in memory,
Thomas Mueller's avatar
Thomas Mueller committed
177
so that it can still be read.
178 179
</p><p>
Old persisted versions are readable until the old data was explicitly overwritten.
Thomas Mueller's avatar
Thomas Mueller committed
180
Creating a snapshot is fast: only the pages that are changed after a snapshot are copied.
181 182 183 184 185 186 187 188 189 190 191
This behavior also called COW (copy on write).
</p><p>
Rollback is supported (rollback to any old in-memory version or an old persisted version).
</p>

<h3>In-Memory Performance and Usage</h3>
<p>
Performance of in-memory operations is comparable with <code>java.util.TreeMap</code>
(many operations are actually faster), but usually slower than <code>java.util.HashMap</code>.
</p><p>
The memory overhead for large maps is slightly better than for the regular
192 193
map implementations, but there is a higher overhead per map.
For maps with less than 25 entries, the regular map implementations
194
use less memory on average.
Thomas Mueller's avatar
Thomas Mueller committed
195 196 197 198 199 200
</p><p>
If no file name is specified, the store operates purely in memory.
Except for persisting data, all features are supported in this mode
(multi-versioning, index lookup, R-tree and so on).
If a file name is specified, all operations occur in memory (with the same
performance characteristics) until data is persisted.
201 202 203 204
</p>

<h3>Pluggable Data Types</h3>
<p>
205
Serialization is pluggable. The default serialization currently supports many common data types,
206 207 208 209
and uses Java serialization for other objects. The following classes are currently directly supported:
<code>Boolean, Byte, Short, Character, Integer, Long, Float, Double, BigInteger, BigDecimal,
byte[], char[], int[], long[], String, UUID</code>.
The plan is to add more common classes (date, time, timestamp, object array).
210 211 212 213
</p><p>
Parameterized data types are supported
(for example one could build a string data type that limits the length for some reason).
</p><p>
214
The storage engine itself does not have any length limits, so that keys, values,
215 216 217 218 219 220 221
pages, and chunks can be very big (as big as fits in memory).
Also, there is no inherent limit to the number of maps and chunks.
Due to using a log structured storage, there is no special case handling for large keys or pages.
</p>

<h3>BLOB Support</h3>
<p>
222
There is a mechanism that stores large binary objects by splitting them into smaller blocks.
223 224 225 226 227 228 229 230
This allows to store objects that don't fit in memory.
Streaming as well as random access reads on such objects are supported.
This tool is written on top of the store (only using the map interface).
</p>

<h3>R-Tree and Pluggable Map Implementations</h3>
<p>
The map implementation is pluggable.
231
In addition to the default MVMap (multi-version map),
232 233 234 235 236 237
there is a multi-version R-tree map implementation
for spatial operations (contain and intersection; nearest neighbor is not yet implemented).
</p>

<h3>Concurrent Operations and Caching</h3>
<p>
238
The default map implementation supports concurrent reads on old versions of the data.
239
All such read operations can occur in parallel. Concurrent reads from the page cache,
240 241
as well as concurrent reads from the file system are supported.
</p><p>
242 243 244
Storing changes can occur concurrently to modifying the data,
as <code>store()</code> operates on a snapshot.
</p><p>
245
Caching is done on the page level.
246
The page cache is a concurrent LIRS cache, which should be resistant against scan operations.
247
</p><p>
248 249
The default map implementation does not support concurrent modification 
operations on a map (the same as <code>HashMap</code> and <code>TreeMap</code>).
250
</p><p>
251 252 253 254 255 256 257 258 259 260 261 262
With the <code>MVMapConcurrent</code> implementation, 
read operations even on the newest version can happen concurrently with all other
operations, without risk of corruption.
This comes with slightly reduced speed in single threaded mode, 
the same as with other <code>ConcurrentHashMap</code> implementations.
Write operations first read the relevant area from disk to memory
(this can happen concurrently), and only then modify the data. The in-memory part of write
operations is synchronized.
</p><p>
For fully scalable concurrent write operations to a map (in-memory and to disk), 
the map could be split into multiple maps in different stores ('sharding'). 
The plan is to add such a mechanism later when needed.
263 264
</p>

Thomas Mueller's avatar
Thomas Mueller committed
265 266 267 268 269
<h3>Log Structured Storage</h3>
<p>
Currently, <code>store()</code> needs to be called explicitly to save changes.
Changes are buffered in memory, and once enough changes have accumulated
(for example 2 MB), all changes are written in one continuous disk write operation.
270 271
(According to a test, write throughput of a common SSD gets higher the larger the block size, 
until a block size of 2 MB, and then does not further increase.)
Thomas Mueller's avatar
Thomas Mueller committed
272 273 274 275 276
But of course, if needed, changes can also be persisted if only little data was changed.
The estimated amount of unsaved changes is tracked.
The plan is to automatically store in a background thread once there are enough changes.
</p><p>
When storing, all changed pages are serialized,
277
optionally compressed using the LZF algorithm,
Thomas Mueller's avatar
Thomas Mueller committed
278 279 280 281
and written sequentially to a free area of the file.
Each such change set is called a chunk.
All parent pages of the changed B-trees are stored in this chunk as well,
so that each chunk also contains the root of each changed map
282
(which is the entry point to read this version of the data).
Thomas Mueller's avatar
Thomas Mueller committed
283 284 285 286
There is no separate index: all data is stored as a list of pages.
Per store, the is one additional map that contains the metadata (the list of
maps, where the root page of each map is stored, and the list of chunks).
</p><p>
287 288 289
There are usually two write operations per chunk:
one to store the chunk data (the pages), and one to update the file header (so it points to the latest chunk).
If the chunk is appended at the end of the file, the file header is only written at the end of the chunk.
Thomas Mueller's avatar
Thomas Mueller committed
290 291 292
</p><p>
There is currently no transaction log, no undo log,
and there are no in-place updates (however unused chunks are overwritten).
293 294
To save space when persisting very small transactions, the plan is to use a transaction log
where only the deltas are stored, until enough changes have accumulated to persist a chunk.
Thomas Mueller's avatar
Thomas Mueller committed
295
</p><p>
296 297 298
Old data is kept for at least 45 seconds (configurable),
so that there are no explicit sync operations required to guarantee data consistency,
but an application can also sync explicitly when needed.
Thomas Mueller's avatar
Thomas Mueller committed
299 300 301 302 303 304 305 306 307 308 309 310
To reuse disk space, the chunks with the lowest amount of live data are compacted
(the live data is simply stored again in the next chunk).
To improve data locality and disk space usage, the plan is to automatically defragment and compact data.
</p><p>
Compared to regular databases (that use a transaction log, undo log, and main storage area),
the log structured storage is simpler, more flexible, and typically needs less disk operations per change,
as data is only written once instead of twice or 3 times, and because the B-tree pages are
always full (they are stored next to each other) and can be easily compressed.
But temporarily, disk space usage might actually be a bit higher than for a regular database,
as disk space is not immediately re-used (there are no in-place updates).
</p>

311 312 313 314 315 316 317 318 319 320 321 322 323 324
<h3>File System Abstraction, File Locking and Online Backup</h3>
<p>
The file system is pluggable (the same file system abstraction is used as H2 uses).
Support for encryption is planned using an encrypting file system.
Other file system implementations support reading from a compressed zip or tar file.
</p>
<p>
Each store may only be opened once within a JVM.
When opening a store, the file is locked in exclusive mode, so that
the file can only be changed from within one process.
Files can be opened in read-only mode, in which case a shared lock is used.
</p>
<p>
The persisted data can be backed up to a different file at any time,
325
even during write operations (online backup).
326
To do that, automatic disk space reuse needs to be first disabled, so that
327
new data is always appended at the end of the file.
328
Then, the file can be copied (the file handle is available to the application).
329 330
</p>

331 332
<h3>Tools</h3>
<p>
333
There is a builder for store instances (<code>MVStoreBuilder</code>)
334 335 336 337 338
with a fluent API to simplify building a store instance.
</p>
<p>
There is a tool (<code>MVStoreTool</code>) to dump the contents of a file.
</p>
339

340 341 342 343 344 345 346
<h3>Exception Handling</h3>
<p>
This tool does not throw checked exceptions. 
Instead, unchecked exceptions are thrown if needed. 
The error message always contains the version of the tool.
The following exceptions can occur:
</p>
347 348
<ul><li><code>IllegalStateException</code> if a map was already closed or
    an IO exception occurred, for example if the file was locked, is already closed, 
349 350 351 352 353 354 355
    could not be opened or closed, if reading or writing failed, 
    if the file is corrupt, or if there is an internal error in the tool. 
</li><li><code>IllegalArgumentException</code> if a method was called with an illegal argument.
</li><li><code>UnsupportedOperationException</code> if a method was called that is not supported,
    for example trying to modify a read-only map or view.
</ul>

356 357 358 359 360
<h2 id="differences">Similar Projects and Differences to Other Storage Engines</h2>
<p>
Unlike similar storage engines like LevelDB and Kyoto Cabinet, the MVStore is written in Java
and can easily be embedded in a Java application.
</p><p>
361
The MVStore is somewhat similar to the Berkeley DB Java Edition because it is also written in Java,
362
and is also a log structured storage, but the H2 license is more liberal.
363 364
</p><p>
Like SQLite, the MVStore keeps all data in one file.
365
The plan is to make the MVStore easier to use than SQLite and faster, including faster on Android
366 367 368
(this was not recently tested, however an initial test was successful).
</p><p>
The API of the MVStore is similar to MapDB (previously known as JDBM) from Jan Kotek,
369
and some code is shared between MapDB and JDBM.
370
However, unlike MapDB, the MVStore uses is a log structured storage.
Thomas Mueller's avatar
Thomas Mueller committed
371
The MVStore does not have a record size limit.
372 373 374 375 376 377 378 379 380 381 382
</p>

<h2 id="current_state">Current State</h2>
<p>
The code is still very experimental at this stage.
The API as well as the behavior will probably change.
Features may be added and removed (even thought the main features will stay).
</p>

<h2 id="requirements">Requirements</h2>
<p>
Thomas Mueller's avatar
Thomas Mueller committed
383 384 385
The MVStore is included in the latest H2 jar file.
</p><p>
There are no special requirements to use it.
386 387 388 389 390
The MVStore should run on any JVM as well as on Android
(even thought this was not tested recently).
</p>

<!-- [close] { --></div></td></tr></table><!-- } --><!-- analytics --></body></html>