MVStoreOverviewExample Code Features Similar Projects and Differences to Other Storage Engines Current State Requirements OverviewThe MVStore is work in progress, and is planned to be the next storage subsystem of H2. But it can be also directly within an application, without using JDBC or SQL.
Example CodeMap Operations and VersioningThe following sample code show how to create a store, open a map, add some data, and access the current and an old version:
import org.h2.mvstore.*;
// open the store (in-memory if fileName is null)
MVStore s = MVStore.open(fileName);
// create/get the map named "data"
MVMap<Integer, String> map = s.openMap("data");
// add some data
map.put(1, "Hello");
map.put(2, "World");
// 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)
map.put(1, "Hi");
map.remove(2);
// access the old data (before incrementVersion)
MVMap<Integer, String> oldMap =
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" and "World":
System.out.println(oldMap.get(1));
System.out.println(oldMap.get(2));
oldMap.close();
// print the newest version ("Hi")
System.out.println(map.get(1));
// close the store - this doesn't write to disk
s.close();
Store Builder
The
MVStore s = new MVStore.Builder().
cacheSize(10).
compressData().
encryptionKey("007".toCharArray()).
fileName(fileName).
readOnly().
writeBufferSize(8).
writeDelay(100).
open();
R-Tree
The
// create an in-memory store
MVStore s = MVStore.open(null);
// open an R-tree map
MVRTreeMap<String> r = s.openMap("data",
new MVRTreeMap.Builder<String>());
// 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
Iterator<SpatialKey> it =
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();
The default number of dimensions is 2. To use a different number of dimensions,
use FeaturesMapsEach store supports a set of named maps. A map is sorted by key, and supports the common lookup operations, including access to the first and last key, iterate over some or all keys, and so on. 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. In database terms, a map can be used like a table, where the key of the map is the primary key of the table, and the value is the row. A map can also represent an index, where the key of the map is the key of the index, and the value of the map is the primary key of the table (for non-unique indexes, the key of the map must also contain the primary key). Versions / TransactionsMultiple 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. 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, so that it can still be read. Old persisted versions are readable until the old data was explicitly overwritten. Creating a snapshot is fast: only the pages that are changed after a snapshot are copied. This behavior also called COW (copy on write). Rollback is supported (rollback to any old in-memory version or an old persisted version). In-Memory Performance and Usage
Performance of in-memory operations is comparable with The memory overhead for large maps is slightly better than for the regular map implementations, but there is a higher overhead per map. For maps with less than 25 entries, the regular map implementations use less memory on average. 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. Pluggable Data Types
Serialization is pluggable. The default serialization currently supports many common data types,
and uses Java serialization for other objects. The following classes are currently directly supported:
Parameterized data types are supported (for example one could build a string data type that limits the length for some reason). The storage engine itself does not have any length limits, so that keys, values, 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. BLOB SupportThere is a mechanism that stores large binary objects by splitting them into smaller blocks. 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). R-Tree and Pluggable Map ImplementationsThe map implementation is pluggable. In addition to the default MVMap (multi-version map), there is a multi-version R-tree map implementation for spatial operations (contain and intersection; nearest neighbor is not yet implemented). Concurrent Operations and CachingThe default map implementation supports concurrent reads on old versions of the data. All such read operations can occur in parallel. Concurrent reads from the page cache, as well as concurrent reads from the file system are supported.
Storing changes can occur concurrently to modifying the data,
as Caching is done on the page level. The page cache is a concurrent LIRS cache, which should be resistant against scan operations.
The default map implementation does not support concurrent modification
operations on a map (the same as
With the 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. Log Structured Storage
Currently, When storing, all changed pages are serialized, optionally compressed using the LZF algorithm, 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 (which is the entry point to read this version of the data). 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). 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. There is currently no transaction log, no undo log, and there are no in-place updates (however unused chunks are overwritten). 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. 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. 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. 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). File System Abstraction, File Locking and Online BackupThe 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. 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. The persisted data can be backed up to a different file at any time, even during write operations (online backup). To do that, automatic disk space reuse needs to be first disabled, so that new data is always appended at the end of the file. Then, the file can be copied (the file handle is available to the application). Encrypted FilesFile encryption ensures the data can only be read with the correct password. Data can be encrypted as follows:
MVStore s = new MVStore.Builder().
fileName(fileName).
encryptionKey("007".toCharArray()).
open();
The following algorithms and settings are used:
Tools
There is a tool ( Exception HandlingThis 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:
Similar Projects and Differences to Other Storage EnginesUnlike similar storage engines like LevelDB and Kyoto Cabinet, the MVStore is written in Java and can easily be embedded in a Java and Android application. The MVStore is somewhat similar to the Berkeley DB Java Edition because it is also written in Java, and is also a log structured storage, but the H2 license is more liberal. Like SQLite, the MVStore keeps all data in one file. Unlike SQLite, the MVStore uses is a log structured storage. The plan is to make the MVStore both easier to use as well as faster than SQLite. In a recent (very simple) test, the MVStore was about twice as fast as SQLite on Android. The API of the MVStore is similar to MapDB (previously known as JDBM) from Jan Kotek, and some code is shared between MapDB and JDBM. However, unlike MapDB, the MVStore uses is a log structured storage. The MVStore does not have a record size limit. Current StateThe 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). RequirementsThe MVStore is included in the latest H2 jar file. There are no special requirements to use it. The MVStore should run on any JVM as well as on Android. To build just the MVStore (without the database engine), run: ./build.sh jarMVStore
This will create the file |