偶然机会下接触到
H2数据库
，了解到其支持内存、文件模式，能够运行在内嵌模式，服务器模式和集群模式。H2数据库麻雀虽小但五脏俱全，支持事务，MVCC等。回忆起自己读书的时候一直想了解一个数据库具体的运行原理，想了解它是怎么把一个sql从解释到执行的过程。无奈时间有限水平不够便搁置了，直到看到这个H2便决定从它开始入手，这篇文章记录的是关于H2数据库的存储引擎部分MVStore的一点介绍（内容可参考官网，结合了我自己的一点理解）顺便给自己整理下相关知识。水平不够，欢迎各位指正。
一、测试方法用例
Oracle的数据存储有表空间、段、区、块、数据文件；MySQL InnoDB的存储管理也类似，但是MySQL增加了一个共享表空间和独立表空间的概念。
跟Mysql，Oracle等相似，H2的储存结构其实也是分了层次的，分别为：file，chunk，page，存储的基本单位是block(一般是4k个字节)。flie中包含了多个chunk，每次有新版本的写入都会有一个chunk，一个chunk由多个block组成。
h2用的是一种copy on write btree的方法来，每次修改btree都会得到一个新的root page写在这个chunk中，每个事务只要保存好自己的root page就可以。
Mysql InnoDB存储结构
在阅读H2源码的时候，自上而下和自下而上的方法都有用到。刚开始看到源码的时候无从下手，于是便先整体了解下它是怎么启动，运行，执行sql的。有了大概了解之后在debug进去一部分一部分代码自下而上地了解各模块是怎么组织运作的。另外，UT是个好东西。H2源码中包含了很多单元测试代码。测试文件里面有很多单元测试，每个测试方法粒度都比较细，从方法名就知道是测了什么功能。我就从其中一个叫做testExample()的方法入手，逐步梳理MVStore的逻辑。有兴趣阅读的伙伴建议也可以从这个测试方法入手，减少走弯路。
H2源码中的单元测试
H2源码中的单元测试
testExample（）方法
private void testExample () {
String fileName = getBaseDir() + "/" + getTestName();
FileUtils.delete(fileName);
try (MVStore s = MVStore.open(fileName)) {
MVMap<Integer, String> map = s.openMap("data" );
map.put(1 , "Hello World" );
try (MVStore s = MVStore.open(fileName)) {
MVMap<Integer, String> map = s.openMap("data" );
assertEquals("Hello World" , map.get(1 ));
二 、存储文件形式介绍
H2数据库的数据都存储在一个文件中。该文件为了安全包含了两个文件头 还有一系列的chunks 。每一个文件头都占用了一个block ，一个block是4096字节。每一个chunk至少一个block，但通常是200个blocks或者更多。数据以log structured storage 的形式存储在chunks中。每一个版本(version)都会有一个chunk 。
H2存储文件的形式会是这样：
[ file header 1 ] [ file header 2 ] [ chunk ] [ chunk ] ... [ chunk ]
每一个chunk包含了若干个B+树的page 。比如下面的例子，就会有两个chunks。
MVStore s = MVStore.open(fileName);
MVMap<Integer, String> map = s.openMap("data" );
for (int i = 0 ; i < 400 ; i++) {
map.put(i, "Hello" );
s.commit();
for (int i = 0 ; i < 100 ; i++) {
map.put(i, "Hi" );
s.commit();
s.close();
Chunk 1：
-Page 1 ： 根节点，指向两个子节点page 2和page 3
-Page 2： 叶结点，包含了140个元素（键0 ~键139）
-Page 3： 叶结点，包含了260个元素(键140~键399)
Chunk 2：
-Page 4： 根节点，指向两个子节点page 5 和 page 3
-Page 5： 叶结点，包含了140个元素（键0~键139）
这说明了每一个chunk包含了每个版本的变化：新版本的那一页还有它的根节点。像这里的例子，Page2被改变了就会有新的一个Page，然后它的父节点一直到根节点的那些页也会有新版本的Page 。
第一次commit
第二次commit
三、文件头
存储文件中有两个文件头，两个文件头内容都一样。当文件头被更新的时候，会出现“部分失败”的情况，这样的话其中一个文件头就会被破坏。所以第二个文件头的作用就是当两个文件头都被成功更新(被称为“原地更新”)才算成功更新。文件头的形式如下：
H:2 ,block:2 ,blockSize:1000 ,chunk:7 ,created:1441235 ef73,format :1 ,version:7 ,fletcher:3044e6 cc
数据是一种“键值对”的形式，其中“值”是十六进制形式的数字。形式如下：
H: "H:2"表示的是H2数据库
block: 其中一块最新的chunks开始的block位置（不需要是最新的chuncks) ----没太搞懂这个意思
blockSize：文件的大小（以字节为单位)，当前是十六进制的1000， 亦即十进制的4096。正好和磁盘扇区的大小一致。
chunk：chunk id。通常和版本号一致。但是chunk id有可能回滚为0，但是版本号不会。
created：文件创建时间（从1970到当前的毫秒数）
format：文件格式号，当前为1
version：chunk的版本号
fletcher：弗莱切检验和
当文件被打开的时候，两个文件头会被读入并且检验和要用来验证。如果两个文件头都符合，那么有着更新版本号的文件头会被使用。最新版本号的chunk就能够被知道（具体是怎么知道的下面会讲），剩下的元数据(metadata)能够从chunk中知道。如果头文件中没有存储chunk id，block，和 版本号。那么最新的chunk 会从文件中的最后一个chunk开始找
四、chunk 格式
每个版本都会有chunk。每一个chunk包含了一个头，在这个版本被修改的页(page)，还有一个尾。页（page）包含了表(map)的实际数据。在一个chunk中的页存储在header的后面(right after)。一个chunk的大小是一个block的大小的倍数。尾部存储在chunk的最后128字节中。
[ header ] [ page ] [ page ] ... [ page ] [ footer ]
尾(footer)能被用来校验chunk是否被完整地写完。每一个写操作都会有一个chunk，并且能够找到文件中的最后一个chunk的起始位置。chunk的头部和尾部包含下面的数据：
chunk:1 ,block:2 ,len :1 ,map:6 ,max :1 c0,next :3 ,pages:2 ,root:4000004 f8c,time :1 fc,version:1
chunk:1 ,block:2 ,version:1 ,fletcher:aed9a4f6
chunk：chunk id
block：chunk中的第一个block位置（要乘以block的大小来得到在文件中的位置）
len：chunk的大小，用block的数量来表示
map：最新的map的id，当一个map被创建的时候这个id就会加一
max：所有最大页的大小之和(没搞懂)
next：下一个chunk的预测起始位置
pages：chunk中的页的数量
root：元数据(metadata)的根页的位置。
time：chunk被写入时的时间。以文件被写入后的毫秒来算
version：这个chunk表示的版本号
fletcher：校验和
Chunks永远不会被原地更新，每一个chunk包含了在那个版本中被修改的页(每一个版本都有一个页)，还有这些页的父亲节点页，直至到根页。如果一个map中的元素被修改，删除或添加，那么相应的页就会被复制，修改和存储在下一个chunk中，并且旧的chunk中的活页(live pages)将会减少。这种机制被称为copy-on-write，与Btrfs 文件系统的工作方式相似。没有live pages的Chunks会被标记为free， 因此chunk能够被重复利用。因为不是所有chunk都是相同的大小，所以会有一些空闲(free)的chunks在某个chunk的前面。在一个空闲的(stackoverflow.com/questions/1…
最新那个chunk在打开h2的持久化文件的时候确定下来的方法：文件头中包含了一个最近的chunk的位置，这个chunk不一定是最新的chunk。这样子是为了减少文件头更新的次数。当打开文件的时候，文件头还有最新一个chunk的尾将会被读入。如果第一次读入的那个chunk有一个next的指针，next指针指向的chunk也会被读入。直到最新的那个chunk被读入。
这段话有点费解，可以直接看源码中的实现，稍后通过源码看是如何读入最新版本的chunk的。其中一个文件头长这样
正如前面所说，前面两个block是用来放存储文件的header的
打开文件头的时候，首先会去读取chunk的头和尾。其中参数中的block和chunkId都是在文件头上有。
读取Chunk的尾
chunk的头和尾作校验
下面讲下打开一个MVStore的过程如下 ：
MVStore s = MVStore.open(fileName)
先去读取文件头。
读到第一个文件头后根据文件头中block字段去文件中的对应位置（block * bolck_size）。读取对应的Chunk头
下面是文件头和chunk头的例子
file头
chunk
private Chunk readChunkHeaderAndFooter (long block, int expectedId) {
Chunk header = readChunkHeaderOptionally(block, expectedId);
if (header != null ) {
Chunk footer = readChunkFooter(block + header.len);
if (footer == null || footer.id != expectedId || footer.block != header.block) {
return null ;
return header;
private Chunk readChunkHeaderOptionally (long block, int expectedId) {
Chunk chunk = readChunkHeaderOptionally(block);
return chunk == null || chunk.id != expectedId ? null : chunk;
private Chunk readChunkHeaderOptionally (long block) {
try {
Chunk chunk = readChunkHeader(block);
return chunk.block != block ? null : chunk;
} catch (Exception ignore) {
return null ;
private Chunk readChunkHeader (long block) {
long p = block * BLOCK_SIZE;
ByteBuffer buff = fileStore.readFully(p, Chunk.MAX_HEADER_LENGTH);
return Chunk.readChunkHeader(buff, p);
static Chunk readChunkHeader (ByteBuffer buff, long start) {
int pos = buff.position();
byte [] data = new byte [Math.min(buff.remaining(), MAX_HEADER_LENGTH)];
buff.get(data);
try {
for (int i = 0 ; i < data.length; i++) {
if (data[i] == '\n' ) {
buff.position(pos + i + 1 );
String s = new String (data, 0 , i, StandardCharsets.ISO_8859_1).trim();
return fromString(s);
} catch (Exception e) {
throw DataUtils.newMVStoreException(
DataUtils.ERROR_FILE_CORRUPT,
"File corrupt reading chunk at position {0}" , start, e);
throw DataUtils.newMVStoreException(
DataUtils.ERROR_FILE_CORRUPT,
"File corrupt reading chunk at position {0}" , start);
读取chunk的尾做检验
private Chunk readChunkHeaderAndFooter (long block, int expectedId) {
Chunk header = readChunkHeaderOptionally(block, expectedId);
if (header != null ) {
Chunk footer = readChunkFooter(block + header.len);
if (footer == null || footer.id != expectedId || footer.block != header.block) {
return null ;
return header;
读取第二个文件头。如果其中的version字段大于第一个文件头读取出来的chunk的version，则继续像上面步骤一样去读取chunk
回顾前面说的
打开文件的时候，文件头还有最新一个chunk的尾将会被读入。如果第一次读入的那个chunk有一个next的指针，next指针指向的chunk也会被读入。直到最新的那个chunk被读入。
看下面，在while循环里，会把当前的chunk（next指向的下一个chunk读入），如果下一个chunk的版本小于等于当前版本就结束。由此newest就指向了最新版本的那个chunk。
上一部分确定了最新的chunk （newest)之后，就到了下面这里。
if (assumeCleanShutdown) {
Queue<Chunk> chunksToVerify = new PriorityQueue <>(20 , Collections.reverseOrder(chunkComparator));
try {
setLastChunk(newest);
Cursor<String, String> cursor = layout.cursor(DataUtils.META_CHUNK);
while (cursor.hasNext() && cursor.next().startsWith(DataUtils.META_CHUNK)) {
Chunk c = Chunk.fromString(cursor.getValue());
assert c.version <= currentVersion;
chunks.putIfAbsent(c.id, c);
chunksToVerify.offer(c);
if (chunksToVerify.size() == 20 ) {
chunksToVerify.poll();
Chunk c;
while (assumeCleanShutdown && (c = chunksToVerify.poll()) != null ) {
Chunk
test = readChunkHeaderAndFooter(c.block, c.id);
assumeCleanShutdown = test != null ;
if (assumeCleanShutdown) {
validChunksByLocation.put(test.block, test);
} catch (MVStoreException ignored) {
assumeCleanShutdown = false ;
看注释：quickly check latest 20 chunks referenced in meta table
可以看出来是为了读取最新的20个chunk。其中用到了一个优先队列来对chunk排序。但是这里是按照变量chunkComparator的倒序来排序的。chunkComparator的定义如下：
Comparator<Chunk> chunkComparator = (one, two) -> {
int result = Long.compare(two.version, one.version);
if (result == 0 ) {
result = Long.compare(one.block, two.block);
return result;
首先比较两个chunk的版本，谁的版本大就排在前面。如果版本相同，则比较block的大小，谁的block小就排在前面。于是乎，它的倒叙就是谁的版本小就先排在前面，谁的block大就排在前面。
注意到方法：
setLastChunk(newest);
由上一步确定出来的最新的chunk会用来初始化layout这个MVMap。具体细节这里先不介绍，等后面讲了Page的结构会容易理解一点
经过setLastChunk之后，layout这个MVMap将会有类似于下面的这种结构
先看下面这一步：
Cursor<String, String> cursor = layout.cursor(DataUtils.META_CHUNK);
while (cursor.hasNext() && cursor.next().startsWith(DataUtils.META_CHUNK)) {
Chunk c = Chunk.fromString(cursor.getValue());
assert c.version <= currentVersion;
chunks.putIfAbsent(c.id, c);
chunksToVerify.offer(c);
if (chunksToVerify.size() == 20 ) {
chunksToVerify.poll();
DataUtils.META_CHUNK是字符串常量”chunk.“ 。由此可以猜出来，这里的while循环是为了把layout的"chunk."开头的键都读出来，放到chunks这个map和优先队列chunksToVerify中。并且让优先队列数量保存在最多19个。
接着是下面的循环：
依次从优先队列中读取出chunk，放到validChunksByLocation这个map中
while (assumeCleanShutdown && (c = chunksToVerify.poll()) != null ) {
Chunk test = readChunkHeaderAndFooter(c.block, c.id);
assumeCleanShutdown = test != null ;
if (assumeCleanShutdown) {
validChunksByLocation.put(test.block, test);
6.最后一步，是一些清理性的工作
fileStore.clear();
for (Chunk c : chunks.values()) {
if (c.isSaved()) {
long start = c.block * BLOCK_SIZE;
int length = c.len * BLOCK_SIZE;
fileStore.markUsed(start, length);
if (!c.isLive()) {
deadChunks.offer(c);
复制代码 65.2w
11150
程序员老鱼
掘金·日新计划
ChatGPT
OpenAI
71.1w
程序员DHL
Android Jetpack
