概述
MVStore是“多版本存储”（Multi-Version Store）的缩写，是一种持久化的基于日志结构的键值存储。它是H2的默认存储引擎，支持SQL、JDBC、事务、MVCC等。但也可以直接在应用程序中使用，而不使用JDBC或SQL。
以下是MVStore的特点：
- 内部包含多个Map，可以使用Java中的java.util.Map接口访问。
- 支持基于文件的持久化和内存操作，旨在快速、简单易用且小巧。
- 支持并发读写操作和事务（包括并发事务和两阶段提交）。
- 支持插件式数据类型和序列化、插件式存储（文件、离堆内存）、插件式Map实现（B树、R树、并发B树）、BLOB存储和文件系统抽象以支持加密文件和zip文件。
例子
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）。
[ file header 1 ] [ file header 2 ] [ chunk ] [ chunk ] ... [ chunk ]
复制
文件头 (File Header)
文件头 (File Header)：为了安全起见，文件头有两个，通常包含完全相同的数据。以便在写入期间部分失败时不会破坏文件头。只有文件头才支持原地更新"in-place update"。
文件头包含以下信息：
H:2,block:2,blockSize:1000,chunk:7,created:1441235ef73,format:1,version:7,fletcher:3044e6cc
复制
H |
“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字节中。
[ 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
chunk:1,block:2,len:1,map:6,max:1c0,next:3,pages:2,root:4000004f8c,time:1fc,version:1
复制
chunk footer
chunk:1,block:2,version:1,fletcher:aed9a4f6
复制
chunk |
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()；
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 对象
MVMap<String, String> metaMap = store.getMetaMap();
复制
获取第一个 chunk
在 readStoreHeader 方法中的 readChunkHeaderAndFooter(block); 会通过 setLastChunk 方法设置 chunk。
/** * 获取最新的 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
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 来查询结果
/** * 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 到叶子节点
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 交流群，告诉我，我会继续写下去。DawnSql 交流群，在 https://docs.dawnsql.com/ 的首页可以查看（打开有点慢，稍等一下就可以了）
说明一点：有些朋友有疑问，为什么 DawnSql 选择 h2 的存储内核，而不是去重新做一个？这里主要是为了高用性！h2 作为成熟的数据库存储内核，已经在实际的项目中应用了多年，它是经得起考验的。如果新做存储内核，可能会给使用者带来高可用性上面的顾虑，所以我们再三权衡后选择更稳定可用性更高的方案。当然随着 DawnSql 的发展和根据企业方的要求，我们也可以对其进行修改和重构！
