暂无图片
暂无图片
暂无图片
暂无图片
暂无图片
首页 / DuckDB: Row-Group Based Storage

DuckDB: Row-Group Based Storage

coredump 2021-06-19
3040

SingleFile

DuckDB 支持内存型和持久化型两种工作模式。

其中，内存型不持久化数据，采用 InMemoryBlockManager[1] 来管理数据，后面不讨论内存型的数据存储。

DuckDB 采用 SingleFileBlockManager [2]来管理外存上的数据。看这个名字就可以猜到，DuckDB 把所有数据都保存在了一个文件中。

下面，我们称这个文件为 SingleFile。

SingleFile 的基本结构

DuckDB 把 SingleFile 的数据划分成定长块，包括两大类：header 和 block。

Header

  • Header 目前有 3 个，包括 1 个 MainHeader[3] 和 2 个 DatabaseHeader[4]，每个固定大小为 4KB（FILE_HEADER_SIZE[5]）。
  • MainHeader
    保存了 magic_bytes
    、version_number
    和 flag 列表
    ，主要用来做一些版本校验，对总体逻辑没什么影响，暂且可以忽略。
  • DatabaseHeader
    的核心是保存了 meta_block
    的 id，后续会从这个 meta_block
    开始读取整个实例的元数据（表结构等）。

Block

  • Block 固定长度为 256KB（BLOCK_ALLOC_SIZE[6]），其中前 8 个字节（BLOCK_HEADER_SIZE[7]）是 checksums。
  • Block 大体上可以分成两种，这里简单称之为 MetaBlock 和 DataBlock。

MetaBlock

  • MetaBlock 除去 checksums 部分的前 8 个字节是 next_block_id
    —— 相关的 MetaBlock 通过这个字段串连在一起——比如，表结构的信息很多，超过 256KB，一个 block 存不下，需要两个以上的 block，此时就用这个 next_block_id 将这些 block 串连成一个链表。
  • MetaBlock 是通过 MetaBlockReader[8]/MetaBlockWriter [9]进行读写的，next_block_id
    的细节也被封装在这里面。
MetaBlock 组成的链表
  • MetaBlock 可以分成两种，这里也简单称之为 Schema MetaBlock 和 TableData MetaBlock。
    • Schema MetaBlock 保存了表结构等信息。
    • TableData MetaBlock 保存了对应表的数据的所有 block_id。
  • DatabaseHeader
    中的 meta_block_id
    就是 Schema MetaBlock 的第一个 block_id。DuckDB 元数据的加载就是从这个 block 开始的，代码在 CheckPointManager::LoadFromStorage[10]。

Schema MetaBlock

Schema MetaBlock 的逻辑结构
  • 最前面是 schema count，类型为 uint32，占用 4 字节。
  • 后面跟一个 schema 列表。DuckDB 中的一个 schema 其实就是 MySQL 中的一个 database。具体可以参考 DuckDB 的官方文档：Create Schema[11]。

CheckpointManager::ReadSchema[12] 函数展示了如何读取、解析一个 schema。一个 schema 的逻辑结构如下：

  • Sequence 是 DuckDB 提供的一个创建 sequence number 生成器的功能，具体可以参考Create Sequence[13]。
  • Table 就是数据库常说的表，具体可以参考 Create Table[14]。
  • View 就是数据库中常说的视图。DuckDB 的视图是逻辑视图，具体可以参考 Create View[15]。
  • Macro 是用户自定义的（类似）存储过程的东西，具体可以参考 Create Macro[16]。

Sequence、View 和 Macro 都只有元数据，其读取相对简单，感兴趣的话，可以参考下面的代码：

  • ReadSequence[17]
  • ReadView[18]
  • ReadMacro[19]

重点看看 ReadTable[20]。除了表结构本身的元数据，还会涉及加载指向实际数据的”指针“，相对复杂一些。

一个 table 的元数据如下：

  • ColumnDefinition[21] 是表结构的列定义，主要有列名 name、列索引 oid、列类型 type 和默认值 defaule_value。
  • Constraint[22] 列表是 table 定义的一些限制。DuckDB 目前支持 NOT NULL、CHECK、UNIQUE、FOREIGN KEY 四种 constraints。
  • block_id 指向了这个 table 的第一个 TableData MetaBlock。
  • offset 是指在这个 TableData MetaBlock 上的偏移。

TableData MetaBlock

TableDataReader::ReadTableData[23] 函数负责读取、解析 TableData MetaBlock 。

TableData MetaBlock 的逻辑结构
  • 通过 BaseStatistics::Deserialize[24] 反序列化整个表的每一列的统计信息，不同数据类型的统计信息可能不太一样，具体可以看这个函数。
  • 通过 RowGroup::Deserialize[25] 反序列化每一个 RowGroup[26] 的信息。

DuckDB 将一个表的数据按行划分成一个个 group，称之为 RowGroup。RowGroup 内部的数据按列进行存储。目前 DuckDB 将 122880[27] 行数据划分为一个 RowGroup。

RowGroup 的逻辑结构
  • row_start 是这个 RowGroup 第一行数据的 ID。
  • tuple_count 是这个 RowGroup 的行数。
  • 接下来是这个 RowGroup 中每一列的统计信息，一般都有保存最大、最小值，可以在查询的时候起到比较粗粒度的过滤作用。
  • 一个 BlockPointer[28] 指向这个 RowGroup 中一列数据的第一个 block。
  • VersionNode[29] 保存了这个 RowGroup 中的数据的 delete 信息。

小结

本文介绍了 DuckDB 底层存储的数据基本格式 —— Row-Group Based Storage。这个存储格式其实是 DuckDB 在几天前（2020 年 6 月 14 日）发布的 0.2.7 版本[30]时才引入的，之前的存储格式是存列存的，具体可以看这个 DuckDB 的 PR/1808: Row-Group Based Storage[31]。

DuckDB 这种将数据划分成一块一块的方式，再通过 block_id 串连起来的方式，感觉如果同一个表的数据分得比较散，可能会造成大量扫描数据的时候局部性不佳？

不过，这种分块方式，感觉天然很适合接入 S3 这类对象存储。

关于 DuckDB 的存储的问题还有很多，比如，索引[32]的实现、Update/Delete 的实现等，本文也还没触及到。

参考资料

[1]

InMemoryBlockManager: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/in_memory_block_manager.hpp

[2]

SingleFileBlockManager : https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/single_file_block_manager.cpp

[3]

MainHeader: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/storage_info.hpp#L29-L42

[4]

DatabaseHeader: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/storage_info.hpp#L44-L61

[5]

FILE_HEADER_SIZE: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/common/constants.hpp#L78

[6]

BLOCK_ALLOC_SIZE: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/common/constants.hpp#L73

[7]

BLOCK_HEADER_SIZE: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/common/constants.hpp#L70

[8]

MetaBlockReader: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/meta_block_reader.cpp

[9]

MetaBlockWriter : https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/meta_block_writer.cpp

[10]

CheckPointManager::LoadFromStorage: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L105-L122

[11]

Create Schema: https://duckdb.org/docs/sql/statements/create_schema

[12]

CheckpointManager::ReadSchema: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L175-L204

[13]

Create Sequence: https://duckdb.org/docs/sql/statements/create_sequence

[14]

Create Table: https://duckdb.org/docs/sql/statements/create_table

[15]

Create View: https://duckdb.org/docs/sql/statements/create_view

[16]

Create Macro: https://duckdb.org/docs/sql/statements/create_macro

[17]

ReadSequence: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L227-L232

[18]

ReadView: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L213-L218

[19]

ReadMacro: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L241-L246

[20]

ReadTable: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint_manager.cpp#L263-L281

[21]

ColumnDefinition: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/parser/column_definition.hpp#L18

[22]

Constraint: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/parser/constraint.hpp#L30

[23]

TableDataReader::ReadTableData: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/checkpoint/table_data_reader.cpp#L22

[24]

BaseStatistics::Deserialize: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/statistics/base_statistics.cpp#L79-L113

[25]

RowGroup::Deserialize: https://github.com/duckdb/duckdb/blob/v0.2.7/src/storage/table/row_group.cpp#L660-L680

[26]

RowGroup: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/table/row_group.hpp#L31

[27]

122880: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/table/row_group.hpp#L38

[28]

BlockPointer: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/block.hpp#L24-L27

[29]

VersionNode: https://github.com/duckdb/duckdb/blob/v0.2.7/src/include/duckdb/storage/table/row_group.hpp#L149

[30]

0.2.7 版本: https://github.com/duckdb/duckdb/releases/tag/v0.2.7

[31]

PR/1808: Row-Group Based Storage: https://github.com/duckdb/duckdb/pull/1808

[32]

索引: https://duckdb.org/docs/sql/indexes


数据库
文章转载自coredump，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

评论