Block

block 就是一个字节数组

1
2
/// A block is simply a [`Bytes`] array.
pub type Block = Bytes;
  • blob block
  • char block
  • dict block
  • nullable block
  • primitive block
  • rle block

RisingLight 提供了一些列 Block Builder trait 来构建 block，这些 build 都需要实现 BlockBuilder trait。BlockBuilder 定义了构建一个 block 需要实现的基本操作。除了 BlockBuilder trait，还定义了 NonNullableBlockBuilder trait 为不为空的类型的 block 定义了相关操作。

classDiagram direction LR BlockBuilder <|.. PlainBlobBlockBuilder BlockBuilder <|.. PlainCharBlockBuilder BlockBuilder <|.. PlainPrimitiveBlockBuilder BlockBuilder <|.. NullableBlockBuilder BlockBuilder <|.. DictBlockBuilder BlockBuilder <|.. RelBlockBuilder NonNullableBlockBuilder <|.. PlainBlobBlockBuilder NonNullableBlockBuilder <|.. PlainCharBlockBuilder NonNullableBlockBuilder <|.. PlainPrimitiveBlockBuilder <<trait>> NonNullableBlockBuilder <<trait>> BlockBuilder namespace trait { class BlockBuilder { + append(&mut self, item: Option<&A::Item>) + estimated_size(&self) usize + get_statistics(&self) Vec<BlockStatistics> + should_finish(&self, next_item: &Option<&A::Item>) bool + finish(self) Vec<u8> + get_target_size(&self) usize } class NonNullableBlockBuilder { + append_value(&mut self, item: &A::Item) + append_default(&mut self) + get_statistics_with_bitmap(&self, selection: &BitVec<u8, Lsb0>) Vec<BlockStatistics> + estimated_size_with_next_item(&self, next_item: &Option<&A::Item>) usize + is_empty(&self) : bool } } namespace implement { class DictBlockBuilder { } class NullableBlockBuilder { - inner_builder: B, - bitmap: BitVec<u8, Lsb0>, - target_size: usize, } class PlainPrimitiveBlockBuilder { - data: Vec<u8>, - target_size: usize, } class PlainCharBlockBuilder { - data: Vec<u8>, - char_width: usize, - target_size: usize, } class PlainBlobBlockBuilder { - data: Vec<u8>, - offsets: Vec<u32>, - target_size: usize, } class RelBlockBuilder }

一个编码后的 Block 的格式如下所示，其中 block_type, cksum_type, cksum 可以用 BlockMeta 结构表示

1
2
|    data     | block_type | cksum_type | cksum  |
|  variable   |    4B      |     4B     |   8B   |

为了能够迭代 block，RisingLight 还定义了 BlockIterator 和 NonNullableBlockIterator trait 来指定一些操作

由于一个 Column 可能包含多个 block，为了能够快速访问 block，还定义了 BlockIndex 结构。

classDiagram class BlockIndex { + offset: u64, + length: u64, + first_rowid: u32, + row_count: u32, + first_key: ::prost::alloc::vec::Vec<u8>, + stats: ::prost::alloc::vec::Vec<BlockStatistics>, + is_first_key_null: bool, }

index block 的存储格式如下所示

1
| index | index | index | ... | magic number (4B) | block count (8B) | checksum type (4B) | checksum (8B) |

每生成一个 Block，就会构建一个 BlockIndex 结构，这个过程是在 BlockIndexBuilder#finish_block() 中实现的

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/// Record information of a block and produce a new index entry.
pub fn finish_block(
    &mut self,
    block_type: BlockType,
    column_data: &mut Vec<u8>,
    block_data: &mut Vec<u8>,
    stats: Vec<BlockStatistics>,
    first_key: Option<Vec<u8>>,
) {
    self.indexes.push(BlockIndex { // 添加一个 index entry
        offset: column_data.len() as u64,
        length: block_data.len() as u64 + BLOCK_META_SIZE as u64,
        first_rowid: self.last_row_count as u32,
        row_count: (self.row_count - self.last_row_count) as u32,
        /// TODO(chi): support sort key
        is_first_key_null: first_key.is_none(),
        first_key: first_key.unwrap_or_default(),
        stats,
    });

    // the new block will begin at the current row count
    self.last_row_count = self.row_count;

    // 构建 block header(包括 block type， checksum type 和 checksum)
    self.block_header.resize(BLOCK_META_SIZE, 0);
    let mut block_header_nonchecksum = &mut self.block_header[..BLOCK_META_NON_CHECKSUM_SIZE];

    let checksum_type = self.options.checksum_type;

    let mut header = BlockMeta {
        block_type,
        checksum_type,
        checksum: 0,
    };
    header.encode_except_checksum(&mut block_header_nonchecksum);
    debug_assert!(block_header_nonchecksum.is_empty());
    // add block_type to block_data
    block_data.extend_from_slice(&self.block_header[..BLOCK_META_NON_CHECKSUM_SIZE]);

    // calculate checksum and add
    header.checksum = build_checksum(header.checksum_type, block_data);
    let mut block_header_checksum = &mut self.block_header[BLOCK_META_NON_CHECKSUM_SIZE..];
    header.encode_checksum(&mut block_header_checksum); // 编码 checksum
    debug_assert!(block_header_checksum.is_empty());
    block_data.extend_from_slice(&self.block_header[BLOCK_META_NON_CHECKSUM_SIZE..]);

    // add data to the column file
    column_data.append(block_data);
}

Column

和 Block 一样，构建 Column 时必须使用 Column Builder 来构建，不同类型的 Column 必须实现 ColumnBuilder trait。ColumnBuilder 接受一个泛型 A，其必须实现 Array trait，否则就不是一个合法的 column 类型

classDiagram direction LR ColumnBuilder <|.. BlobColumnBuilder ColumnBuilder <|.. CharColumnBuilder ColumnBuilder <|.. PrimitiveColumnBuilder <<trait>> ColumnBuilder class ColumnBuilder { + append(&mut self, array: &A) + finish(self) (Vec<BlockIndex>, Vec<u8>) } class PrimitiveColumnBuilder { - data: Vec<u8>, - options: ColumnBuilderOptions, - current_builder: Option<BlockBuilderImpl<T>>, - nullable: bool, - block_index_builder: BlockIndexBuilder, - first_key: Option<Vec<u8>>, + new(nullable: bool, options: ColumnBuilderOptions) Self - finish_builder(&mut self) } class EncodedColumn { + index: Vec<u8>, + data: Vec<u8>, }

Column 表示 row 中的一个 attribute，当数据量很大时，数据会水平切分为 row groups(RisingLight 中使用术语 rowset)， 在 row group 内部又会进行垂直切分，将row 拆分为 column。也就是说每个 row group 中的 column 都是一个单独的文件。而每个 column 文件又被划分为多个 block，为了快速访问 block，RisingLight 在 col 文件中存储了 index 结构。data + index 组成了 EncodedColumn 结构，这也是 column 在 col 文件中的存储的数据。需要注意的是，data 和 index 是分开存储的，即 data 对应一个 .col 文件，idx 对应一个 .idx 文件

RowSet

我们知道，一个 rowset 包含多个 column，为了识别 column，还需要存储一些其他的信息，比如 Column 的 scheme

classDiagram class EncodedRowset { + size: usize, + columns_info: Arc<[ColumnCatalog]> + columns: Vec<EncodedColumn> + cardinality(&self) usize + is_empty(&self) bool }

需要注意的是并不需要将 column 的 scheme 存储在 col 或者 idx 文件中，RisingLight 选择使用 <column_id>.col/idx 对 col 或者 idx 文件命令（比如 1.col, 1.idx)，这样就可以知道某个文件是 row 中的第几列了。

还有一点需要注意的是每个 rowset 都对应一个目录，其命名格式是 <table_id>_<rowset_id>，这样就能识别出某个目睹对应哪个 table 的那个 rowset 了。同时结合 col 和 idx 文件的命名，我们可以通过文件名唯一地确定 col 或者 idx

既然 col 和 rowset 都没有存储 column schemes 信息，那么就必然需要将这些信息存储到一个位置，否则当系统崩溃是就无法恢复数据了。RisingLight 选择将 column schems 信息存储到 manifest 文件中。manifest 是一个 json 文件，记录了所有操作（包括创建/修改表的 scheme 信息)。manifest 记录的信息示例如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
{
  "CreateTable": {
    "schema_id":0,
    "table_name":"t2",
    "column_descs": [
      {
        "id":0,
        "desc": {
          "datatype": {
            "kind": "Int32",
            "nullable":true
          },
          "name":"a",
          "is_primary":false
        }
      },
    ],
    "ordered_pk_ids":[]
  }
}
{"AddRowSet":{"table_id":{"schema_id":0,"table_id":1},"rowset_id":15}}
{"AddDV":{"table_id":{"schema_id":0,"table_id":1},"dv_id":0,"rowset_id":15}
{"DropTable":{"table_id":{"schema_id":0,"table_id":0}}}
{"DeleteRowSet":{"table_id":{"schema_id":0,"table_id":0},"rowset_id":23}}

下图是 Insert 数据的存储过程（图源官方)