文件包括:
文件中的数据按照page的方式进行组织,page是编码和压缩的基本单位。现在的page类型包括以下几种:
DataPage分为两种:nullable和non-nullable的data page。
nullable的data page内容包括:
+----------------+ | value count | |----------------| | first row id | |----------------| | bitmap length | |----------------| | null bitmap | |----------------| | data | |----------------| | checksum | +----------------+
non-nullable data page结构如下:
|----------------| | value count | |----------------| | first row id | |----------------| | data | |----------------| | checksum | +----------------+
其中各个字段含义如下:
针对每个bloom filter列,会在page的粒度相应的生成一个bloom filter的page,保存在bloom filter pages区域
针对每个列,都会按照page粒度,建立行号的稀疏索引。内容为这个page的起始行的行号到这个block的指针(包括offset和length)
我们会每隔N行(可配置)生成一个short key的稀疏索引,索引的内容为:short key->行号(ordinal)
该格式设计支持后续扩展其他的索引信息,比如bitmap索引,spatial索引等等,只需要将需要的数据写到现有的列数据后面,并且添加对应的元数据字段到FileFooterPB中
FileFooterPB的定义为:
message ColumnPB { optional uint32 column_id = 1; // 这里使用column id,不使用column name是因为计划支持修改列名 optional string type = 2; // 列类型 optional string aggregation = 3; // 是否聚合 optional uint32 length = 4; // 长度 optional bool is_key = 5; // 是否是主键列 optional string default_value = 6; // 默认值 optional uint32 precision = 9 [default = 27]; // 精度 optional uint32 frac = 10 [default = 9]; optional bool is_nullable = 11 [default=false]; // 是否有null optional bool is_bf_column = 15 [default=false]; // 是否有bf词典 optional bool is_bitmap_column = 16 [default=false]; // 是否有bitmap索引 } // page偏移 message PagePointerPB { required uint64 offset; // page在文件中的偏移 required uint32 length; // page的大小 } message MetadataPairPB { optional string key = 1; optional bytes value = 2; } message ColumnMetaPB { optional ColumnMessage encoding; // 编码方式 optional PagePointerPB dict_page // 词典page repeated PagePointerPB bloom_filter_pages; // bloom filter词典信息 optional PagePointerPB ordinal_index_page; // 行号索引数据 optional PagePointerPB page_zone_map_page; // page级别统计信息索引数据 optional PagePointerPB bitmap_index_page; // bitmap索引数据 optional uint64 data_footprint; // 列中索引的大小 optional uint64 index_footprint; // 列中数据的大小 optional uint64 raw_data_footprint; // 原始列数据大小 optional CompressKind compress_kind; // 列的压缩方式 optional ZoneMapPB column_zone_map; //文件级别的过滤条件 repeated MetadataPairPB column_meta_datas; } message FileFooterPB { optional uint32 version = 2 [default = 1]; // 用于版本兼容和升级使用 repeated ColumnPB schema = 5; // 列Schema optional uint64 num_values = 4; // 文件中保存的行数 optional uint64 index_footprint = 7; // 索引大小 optional uint64 data_footprint = 8; // 数据大小 optional uint64 raw_data_footprint = 8; // 原始数据大小 optional CompressKind compress_kind = 9 [default = COMPRESS_LZO]; // 压缩方式 repeated ColumnMetaPB column_metas = 10; // 列元数据 optional PagePointerPB key_index_page; // short key索引page }
大体的写入流程如下:
相关的问题:
short key的索引如何生成?
ordinal索引里面应该存什么?
不同encoding类型的page里存什么?
相关的问题:
如何实现在page内部快速的定位到某一行?
page内部是的数据是经过encoding的,无法快速进行行级数据的定位。不同的encoding方式,在内部进行快速的行号定位的方案不一样,需要具体分析:
如何实现块的高效读取?可以考虑将相邻的块在读取的时候进行merge,一次性读取? 这个需要在读取的时候,判断block是否连续,如果连续,就一次性的读取
现有的doris存储中,针对string类型的编码,采用plain encoding的方式,效率比较低。经过对比,发现在百度统计的场景下,数据会因为string类型的编码膨胀超过一倍。所以,计划引入基于词典的编码压缩。
实现可扩展的压缩框架,支持多种压缩算法,方便后续添加新的压缩算法,计划引入zstd压缩。