H2 存储内核解析

原创

用户5383110

修改于 2023-03-31 15:19:26

4710

修改于 2023-03-31 15:19:26

文章被收录于专栏：DawnSqlDawnSql

概述

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 选择 h2 的存储内核，而不是去重新做一个？这里主要是为了高用性！h2 作为成熟的数据库存储内核，已经在实际的项目中应用了多年，它是经得起考验的。如果新做存储内核，可能会给使用者带来高可用性上面的顾虑，所以我们再三权衡后选择更稳定可用性更高的方案。当然随着 DawnSql 的发展和根据企业方的要求，我们也可以对其进行修改和重构！

原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。

如有侵权，请联系 cloudcommunity@tencent.com 删除。

存储