H2 存储内核解析
概述
MVStore 是“多版本存储”（Multi-Version Store）的缩写，是一种持久化的基于日志结构的键值存储。它是 H2 的默认存储引擎，支持 SQL、JDBC、事务、MVCC 等。但也可以直接在应用程序中使用，而不使用 JDBC 或 SQL。以下是 MVStore 的特点：
内部包含多个 Map，可以使用 Java 中的 java.util.Map 接口访问。
支持基于文件的持久化和内存操作，旨在快速、简单易用且小巧。
支持并发读写操作和事务（包括并发事务和两阶段提交）。
支持插件式数据类型和序列化、插件式存储（文件、离堆内存）、插件式 Map 实现（B 树、R 树、并发 B 树）、BLOB 存储和文件系统抽象以支持加密文件和 zip 文件。
例子
文件格式(File)
文件（File）包含两个文件头和若干个数据块（Chunk）。每个数据块（Chunk）至少为一个块（Block），但通常为 200 个块（Block）或更多。数据以日志结构存储的形式存储在数据块（Chunk）中。每个版本（Version）都有一个数据块（Chunk）。
文件头 (File Header)
文件头 (File Header)：为了安全起见，文件头有两个，通常包含完全相同的数据。以便在写入期间部分失败时不会破坏文件头。只有文件头才支持原地更新"in-place update"。
文件头包含以下信息：
在打开文件时，会读取两个文件头并验证校验和。如果两个文件头都有效，则使用版本更新的文件头。然后检测具有最新版本的数据块（chunk），并从其中读取其余元数据。如果文件头中没有数据块 ID，块（block）和版本，则最新数据块（chunk）的查找将从文件中的最后一个数据块（chunk）开始。
数据块格式(Chunk Format)
每个版本都有一个数据块（chunk），每个数据块（chunk）由一个 header、在此版本中修改的页面（page）和 footer 组成。页面（page）包含以 map 形式的实际数据。数据块（chunk）中的页面（page）在 header 后紧挨着存储（未对齐）。数据块（chunk）的大小是块（block）大小的倍数。footer 存储在数据块（chunk）的最后 128 字节中。
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 footer
每个版本都有一个 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 个字节）。
页面格式的参数
尽管文件格式不要求这样做，但页面(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，它包含如下信息：
可以通过调用 getMetaMap()方法来获取 metadata
代码解析
生成 MVStore 对象
fileName 不存在的时，执行 writeStoreHeader()，存在的时候读取 readStoreHeader()；
MVStore 对象创建成功后，它就包括了如下属性：
获取 meta map
通过 MVStore 对象
获取第一个 chunk
在 readStoreHeader 方法中的 readChunkHeaderAndFooter(block); 会通过 setLastChunk 方法设置 chunk。
获取 chunk 的根 page
Page 类是操作数据的核心类
输入 Page 和要查询的索引，通过 tree 来查询结果
插入 key-value 到叶子节点
到这里，读者基本上就了解了 h2 的存储内核了，这个还是比较简单，容易掌握和扩展的。如果大家对存储内核有兴趣的话，可以加入 DawnSql 交流群，告诉我，我会继续写下去。DawnSql 交流群，在 https://docs.dawnsql.com/ 的首页可以查看（打开有点慢，稍等一下就可以了）
说明一点：有些朋友有疑问，为什么 DawnSql 选择 h2 的存储内核，而不是去重新做一个？这里主要是为了高用性！h2 作为成熟的数据库存储内核，已经在实际的项目中应用了多年，它是经得起考验的。如果新做存储内核，可能会给使用者带来高可用性上面的顾虑，所以我们再三权衡后选择更稳定可用性更高的方案。当然随着 DawnSql 的发展和根据企业方的要求，我们也可以对其进行修改和重构
DawnSql开源分布式数据库的作者 2020-02-13 加入
还未添加个人简介
评论