概述
MVStore是“多版本存储”（Multi-Version Store）的缩写，是一种持久化的基于日志结构的键值存储。它是H2的默认存储引擎，支持SQL、JDBC、事务、MVCC等。但也可以直接在应用程序中使用，而不使用JDBC或SQL。
以下是MVStore的特点：
- 内部包含多个Map，可以使用Java中的java.util.Map接口访问。
- 支持基于文件的持久化和内存操作，旨在快速、简单易用且小巧。
- 支持并发读写操作和事务（包括并发事务和两阶段提交）。
- 支持插件式数据类型和序列化、插件式存储（文件、离堆内存）、插件式Map实现（B树、R树、并发B树）、BLOB存储和文件系统抽象以支持加密文件和zip文件。
例子
代码语言：java复制 String fileName = "/Users/chenfei/temp/my_store.db";
//
FileUtils.delete(fileName);
MVStore.Builder builder = new MVStore.Builder();
builder.fileName(fileName);
builder.pageSplitSize(1000);
MVStore store = builder.open();
MVMap<Integer, String> m = store.openMap("data");
int count = 2;
for (int i = 0; i < count; i ) {
m.put(i, "hello " i);
System.out.println(m.get(i));
}
store.commit();
store.close();文件格式(File)
文件（File）包含两个文件头和若干个数据块（Chunk）。每个数据块（Chunk）至少为一个块（Block），但通常为200个块（Block）或更多。数据以日志结构存储的形式存储在数据块（Chunk）中。每个版本（Version）都有一个数据块（Chunk）。
代码语言：java复制[ file header 1 ] [ file header 2 ] [ chunk ] [ chunk ] ... [ chunk ]文件头 (File Header)
文件头 (File Header)：为了安全起见，文件头有两个，通常包含完全相同的数据。以便在写入期间部分失败时不会破坏文件头。只有文件头才支持原地更新"in-place update"。
文件头包含以下信息：
代码语言：java复制H:2,block:2,blockSize:1000,chunk:7,created:1441235ef73,format:1,version:7,fletcher:3044e6ccH | “H：2”代表 H2 数据库 |
|---|---|
块（block） | 最新（不必是最新的）数据块(chunks)的起始块（block）号 |
块大小（blockSize） | 文件块的块大小；当前始终为十六进制1000，即十进制4096，以匹配现代硬盘的磁盘扇区长度。 |
数据块（chunk） | 数据块id，通常与版本号相同；但是，数据块id可能会回滚到0，而版本不会。 |
created | 创建文件时距1970年以来的毫秒数 |
format | 文件格式版本（当前为1） |
version | 文件版本 |
fletcher | 校验和 |
在打开文件时，会读取两个文件头并验证校验和。如果两个文件头都有效，则使用版本更新的文件头。然后检测具有最新版本的数据块（chunk），并从其中读取其余元数据。如果文件头中没有数据块 ID，块（block）和版本，则最新数据块（chunk）的查找将从文件中的最后一个数据块（chunk）开始。
数据块格式(Chunk Format)
每个版本都有一个数据块（chunk），每个数据块（chunk）由一个 header、在此版本中修改的页面（page）和 footer组成。页面（page）包含以 map 形式的实际数据。数据块（chunk）中的页面（page）在 header 后紧挨着存储（未对齐）。数据块（chunk）的大小是块（block）大小的倍数。footer 存储在数据块（chunk）的最后128字节中。
代码语言：java复制[ header ] [ page ] [ page ] ... [ page ] [ footer ]chunk foot 用于验证chunk是否完整写入，以及查找文件中最后一个chunk的起始位置。chunk中的页面 (page) 存储着 map 形式的实际数据。chunk中的页面 (page) 存储在 header 的后面，相邻存放。chunk 的大小是 block 大小的倍数。每个 chunk 只包含在该版本中被修改的页面 (page) ，以及这些页面 (page) 的所有父节点，递归到根页面 (page) 。如果map中的条目被更改、删除或添加，则会复制相应的页面 (page)并在下一个chunk中存储修改后的页面 (page)。没有活页面 (page)的chunk被标记为空，以便更近期的chunk可以重复使用它们的空间。
chunk header
代码语言：java复制chunk:1,block:2,len:1,map:6,max:1c0,next:3,pages:2,root:4000004f8c,time:1fc,version:1chunk footer
代码语言：java复制chunk:1,block:2,version:1,fletcher:aed9a4f6chunk | chunk的ID |
|---|---|
block | chunk的第一个block的编号（乘以block大小可以得到文件中的位置） |
len | chunk包含的页面 (page)数 |
map | 最新map的ID，每次创建新map时递增 |
max | chunk中页面(page)的最大数量 |
pages | chunk中页面(page)的数量 |
next | 下一个chunk的ID |
root | 元数据根页面(page)的位置 |
time | chunk被写入的时间，从文件创建后的毫秒数开始计算 |
version | chunk的版本号 |
每个版本都有一个 chunk，chunk 永远不会被原地更新。每个 chunk 包含了在该版本中更改的页面(page)（每个版本有一个 chunk），以及递归地包含了所有这些页面(page)的父节点，一直到根页面(page)。如果 map 中的条目被更改、删除或添加，则相应的页面(page)将被复制、修改并存储在下一个 chunk 中，旧 chunk 中的活动页面(page)数将减少。这种机制被称为写时复制，类似于 Btrfs 文件系统的工作方式。那些没有活动页面的 chunks 被标记为空闲状态，因此空间可以被最近的 chunks 重复使用。因为不是所有的 chunk 都是相同大小的，所以在某段时间内，一些 chunk 前面可能会有一些空闲 blocks（直到写入小块或压缩块）。默认情况下，在空闲 blocks 被覆盖之前会有45秒的延迟，以确保新版本首先被持久化.
如何在打开存储时找到最新的 chunk：文件头包含最近chunk的位置，但不总是最新的chunk。这是为了减少文件头更新的次数。打开文件后，读取文件头和最后一个chunk的块尾。从这些候选chunk中，读取最新chunk的头。如果它包含一个“next”指针，则也读取这些chunk的头和尾。如果它是一个新的有效chunk，则重复这个过程，直到找到最新的chunk。在写入chunk之前，基于下一个chunk与当前chunk相同的假设，预测下一个chunk的位置。当写入下一个chunk并且前一个预测是不正确的时，文件头也会更新。在任何情况下，如果下一个链的跳数超过20次，则文件头将被更新。
页面格式(Page Format)
每个Map都是一棵B树，Map数据存储在（B树）页面中。页面(page)分为叶子页面和内部节点页面。叶子页面包含Map的键值对，而内部节点只包含键和指向叶子页面的指针。树的根节点可以是叶子页面或内部节点。不同于文件头，数据块 header和 foot 的数据，页面数据是存储为字节数组的，其中包含长整型（8个字节）、整型（4个字节）、短整型（2个字节）和可变大小的整型和长整型（1到5/10个字节）。
页面格式的参数
length | 页面的字节数 |
|---|---|
checksum | 计算方法为 chunk id 异或 page 在 chunk 中的偏移量 offset 异或 page 大小。 |
mapId | 该页面所属 map 的 ID |
len | 该页面中 key 的数量。 |
type (byte) | 页面的类型。叶节点：0。内部节点：1。 |
children | 子节点位置 (long 类型数组；仅仅是内部节点) |
childCounts | Child 页面的数量 |
keys | （字节数组）数组存储了该节点的所有键，类型取决于数据类型 |
values | （字节数组）（仅适用于叶子节点）存储了该节点的所有值，类型取决于数据类型 |
尽管文件格式不要求这样做，但页面(page)按以下顺序存储：对于每个映射，首先存储根页面(root page)，然后是内部节点（如果有的话），然后是叶子页面(page)。metadata map 存储在chunk的末尾。
在MVStore中，页面(page)的指针以一个长整型的特殊格式存储：26位用于chunk ID，32位用于chunk 内偏移量，5位用于长度编码，1位用于页面(page)类型（叶节点或内部节点）。页面(page)类型被编码，以便在清除或删除映射时，不必读取叶节点页面(page)（内部节点必须读取，以便知道所有页面(page)的位置；但在典型的B树中，绝大多数页面(page)都是叶节点页面）。绝对文件位置不包括在内，以便可以在文件中移动chunk而无需更改页指针；只需要更改chunk元数据。 长度代码是从0到31的数字，其中0表示页面(page)的最大长度为32个字节，1表示48个字节，2表示64，3表示96，4表示128，5表示192，以此类推，直到31表示超过1 MB。这样，只需要一个读取操作即可读取页面(page)（除非是非常大的页面）。所有页面(page)的最大长度之和存储在chunk元数据中（字段“max”），当将页面标记为已删除时，会调整实时最大长度。这允许估计 block 内的可用空间量，以及可用页面的数量。
Metadata Map
在MVStore中，除了用户 map 之外，还有一个元数据map (metadata map)，其中包含用户map的名称和位置以及chunk元数据。chunk的最后一页包含该元数据chunk的根页。该根页的确切位置存储在chunk头中。该页（直接或间接）指向所有其他map的根页。元数据map有一个名为 "data" 的map，它包含如下信息：
chunk.1 | chunk 1 的元数据。这是与chunk头相同的数据，加上活动页面的数量和最大活动页面长度。 |
|---|---|
map.1 | map 1的元数据。条目包括名称，创建版本和类型。 |
name.data | 名为“data”的map的map ID。值为“1” |
root.1 | map 1 的根位置 |
setting.storeVersion | store版本（用户定义的值） |
可以通过调用getMetaMap()方法来获取metadata
代码解析
生成 MVStore 对象
fileName 不存在的时，执行 writeStoreHeader()，存在的时候读取 readStoreHeader()；
代码语言：java复制 String fileName = "/Users/chenfei/temp/my_store.db";
MVStore.Builder builder = new MVStore.Builder();
builder.fileName(fileName);
builder.pageSplitSize(1000);
MVStore store = builder.open();MVStore 对象创建成功后，它就包括了如下属性：
获取 meta map
通过 MVStore 对象
代码语言：java复制MVMap<String, String> metaMap = store.getMetaMap();获取第一个 chunk
在 readStoreHeader 方法中的 readChunkHeaderAndFooter(block); 会通过 setLastChunk 方法设置 chunk。
代码语言：java复制 /**
* 获取最新的 chunk
*/
public Chunk setLastChunk(Chunk last) {
chunks.clear();
lastChunk = last;
if (last == null) {
// no valid chunk
lastMapId.set(0);
currentVersion = 0;
lastStoredVersion = MVMap.INITIAL_VERSION;
meta.setRootPos(0, MVMap.INITIAL_VERSION);
} else {
lastMapId.set(last.mapId);
currentVersion = last.version;
chunks.put(last.id, last);
lastStoredVersion = currentVersion - 1;
meta.setRootPos(last.metaRootPos, lastStoredVersion);
}
return last;
}获取 chunk 的根 page
代码语言：java复制 String name = "my_data_1";
MVMap.MapBuilder mapBuilder = new MVMap.Builder();
int id = store.getMapId(name);
MVMap map = store.getMap(id);
if (map == null) {
String configAsString = store.getMetaMap().get(MVMap.getMapKey(id));
HashMap<String, Object> config;
if (configAsString != null) {
config = new HashMap<String, Object>(DataUtils.parseMap(configAsString));
} else {
config = new HashMap<>();
}
config.put("id", id);
map = mapBuilder.create(store, config);
long root = store.getRootPos(store.getMetaMap(), id);
// 该方法执行的就是从文件中提取出 page
map.setRootPos(root, MVMap.INITIAL_VERSION);
store.maps.put(id, map);
// 提取出 page
Page p = map.getRootPage();
System.out.println(p);
}Page 类是操作数据的核心类
输入 Page 和要查询的索引，通过 tree 来查询结果
代码语言：java复制 /**
* Get the value for the given key, or null if not found.
* Search is done in the tree rooted at given page.
*
* @param key the key
* @param p the root page
* @return the value, or null if not found
*/
public static Object get(Page p, Object key) {
while (true) {
int index = p.binarySearch(key);
if (p.isLeaf()) {
return index >= 0 ? p.getValue(index) : null;
} else if (index < 0) {
index = -index;
}
p = p.getChildPage(index);
}
}插入 key-value 到叶子节点
代码语言：java复制 public void insertLeaf(int index, Object key, Object value) {
int keyCount = getKeyCount();
insertKey(index, key);
if(values != null) {
Object[] newValues = createValueStorage(keyCount 1);
DataUtils.copyWithGap(values, newValues, keyCount, index);
values = newValues;
setValueInternal(index, value);
if (isPersistent()) {
addMemory(MEMORY_POINTER map.getValueType().getMemory(value));
}
}
}到这里，读者基本上就了解了 h2 的存储内核了，这个还是比较简单，容易掌握和扩展的。
说明一点：有些朋友有疑问，为什么 DawnSql 选择 h2 的存储内核，而不是去重新做一个？这里主要是为了高用性！h2 作为成熟的数据库存储内核，已经在实际的项目中应用了多年，它是经得起考验的。如果新做存储内核，可能会给使用者带来高可用性上面的顾虑，所以我们再三权衡后选择更稳定可用性更高的方案。当然随着 DawnSql 的发展和根据企业方的要求，我们也可以对其进行修改和重构！
