Doris实现原理之高效存取varchar字符串

Doris 存储层设计有点复杂，怎么存数据，怎么建索引，索引怎么生效的，直接看代码有点废脑，笔者花了不少时间看这部分的代码，为了便于理解， 本文尝试一个案例尽可能的把相关知识点串起来，选择字符串来作为切入点去了解存储引擎主要是字符串涉及的内容比较多，比较复杂，也比较全面。

万丈高楼平地起，复杂的事情往往要从简单东西开始分析，我们先建一个表，同时为理解索引怎么存储的,添加 2 个索引布隆过滤器索引和 Bitmap 索引，建表语句如下:

# 一个user表，包含2个字段名称和年龄
CREATE TABLE t_user (
   username varchar(20) NULL,
   age int 
) ENGINE=OLAP
# 指定排序的key
DUPLICATE KEY(username)
COMMENT 'OLAP'
DISTRIBUTED BY HASH(username) BUCKETS 1
PROPERTIES (
"replication_allocation" = "tag.location.default: 1",
"bloom_filter_columns"="username"  # 添加布隆过滤索引
);
# 添加
CREATE INDEX bitmap_index ON t_user (username) USING BITMAP COMMENT 'test for bitmap';

随后我们插入6条数据:

MySQL [test_db]> insert into t_user values("u2",10),("u4",20),("u1",30),("u3",13),(NULL,0),("u4","12")


MySQL [test_db]> select * from t_user;
+----------+------+
| username | age  |
+----------+------+
| NULL     |    0 |
| u1       |   30 |
| u2       |   10 |
| u3       |   13 |
| u4       |   12 |
| u4       |   20 |
+----------+------+
6 rows in set (0.17 sec)

可以看到我们的插入的 username 无序的，但查出来是有序，因为在doris中同一批数据导入时会自动按照我们定义的key排序

实现行号读取

我们知道 Doris 是列存结构，因为分析场景主要是对某列进行聚合操作，按列加载数据可以降低 io 计算效率更高，所谓列存就是把同一列的数据存储拼在一起存储在文件中,所以上面 username 字段列存格式如下

但是直接存起来显然还不行因为没法读取，不知道有多少行，每行从那里读，读多少长度，经过思考你想到了在后面追加一些额外的信息,增加了每个元素的 offset、总个数、总长度，我们把这种编方式称为 plain 编码，意思是直接打平

其中每个红色数字占4个字节，对应的含义是

• 14: 表示数据部分占有14个字节

• 6：表示有6个元素

• 12: 表示第6个value的offset的是12

• 10: 表示第5个value的offset的是10

• 8:表示第4个value的offset是8

• 6:表示第3个value的offset是6

• 4:表示第2个value的offset是4

• 0: 表示第1个value的offset是0

然后每个value的长度=下一个 value 的 offset -当前 value 的offset，所以得到每个 value的在文件位置信息 offset 和 len

有了每个 value 的 offset 和 len 后，就实现了读取任意一行的 username 值

NULL值存储

上面一列中有 NULL值，这个NULL是以字符串的方式存储下来，占比4个字节，这种设计并不是合理，空间浪费而且如果要真存"NULL"字符串时会有冲突， 所以业内标准的做法是采用标记法，不存储，具体的实现就是通过维护一个 nullbitmap 来标记哪个值为空哪个值不为空，用body来表示存储的数据，引入 nullbitmap后存储结构变为：

其中：

• nullbitmap：占用1个字节，因为只有6个元素，6个bit就够了，第一个元素值为null，所以第一个bit为1

• body：只存储5个元素，还是沿用打平编码，红色部分每个值占4个字节

引入 nullbitmap 后我们会发现一个问题，由于null值不存储后， body元素的所在的位置跟行号对不上了，比如 body 的元素值 u1 对应是应该是第二行，但在 body 中位置第1个，为了还是能实现根据进行号读取值，需要对行号跟元素的 offset 关系进行修正

offset = 行号 - skipnullbits (前面有几个null值)

比如要读第2行的值，首先定位到 nullbitmap 第2个bit，统计前面有几个1，这里为1个1，那么对应body中的元素位置为 2-1=1,即body中的第一个元素， offset=0,len=2

空值存储

上面讲了null值，那么空值怎么处理呢，其实空值可以看做是一个长度为0的值，前面提到字符串的长度=后一个元素offset-前一个元素的offset，如果前后两个offset一样得到的长度就是0，从而实现空值的存储，比如：插入1个空值后 insert into t_user values("",15)，存储结构：

读取第2行过程：

• 定位到nullbitmap第2个bit，统计前面有1个1，即有1个null值，对应body中第一个元素

• 计算body中第一个元素的len=offset[1]-offset[0]=0-0，判断为空值

拆分

为了提升读取的效率， 读取的时候需要把文件中全部数据加载到内存，然后把每个value的offset还原出来，现在只存了7个值，如果有70亿个，这种处理方式是不行的， 本质问题还是存储的粒度过粗,不能把一列的所有数据放一起直接存储，这样没办法按需加载，所以自然想到进行拆分，拆分为多组，我们把每一组称为一页

为了叙述方便，假设后每一页的大小仅能容纳3个值（实际1页大小默认64KB），则上面数据需要分2组，页作为基本单位存放内容，每页存储数据如下: page1存放NULLu1u2 page2存放u3u4u4

当然还需要知道每个value对应原来是第几行，所以每页还需要保存第一个值的行号(行号从0开始)，当然除了行号还有额外的信息需要保存，关于页的描述信息我们统称为Pagefooter,加上footer后结构如下

footer字段说明：

• type：页类型，包括数据页和索引页，不同的页类型的有不同的footer信息

• uncompressed_size: 记录data写盘前未压缩的大小，读时候如果从磁盘读取的data大小和这个值不一样则说明进行了压缩，读取时需要进行解压

• data_page_footer: 对应type为数据页

• first_ordinal: 当前页第一个元素开始的行号（从0开始算）

• num_values: 元素个数

页地址

page1,page2写到磁盘文件后会记录一个位置，这个位置再doris中称为PagePointer, 读取的时候需要拿到这个pointer就可以读取整个page，PagePointer 有2个属性

struct PagePointer {
// 在文件的offset
 uint64_t offset;
// page大小
 uint32_t size;
}

序号索引

到这里实现了分页存储，要找某一个值首先需要找到page，然后在page中进一步读取，那么怎么知道每一行在哪个page呢?

为了实现行号能快速定位到page，需要保存行号跟PagePointer的对应关系，这种关系称为序号索引，在doris中叫做OrdinalIndex，ordinalindex只有1页

ordinalindexpage页的footer字段说明：

• type: index_page表示这是索引页

• uncompressed_size: body为压缩前的大小，如果读取后的大小跟这个值不一样则说明写时进行了压缩，需要解压

• index_page_footer: 索引页对应的footer信息

• num_entries: 记录了多少个page

有了OrdinalIndex后假设找4行的过程是怎么样的？主要经过4个步骤

• 行号定位page：在ordinalindexpage中通过二分查找，找到PagePointer2

• 计算page中行号：page2的first_ordernal为3，第4行对应page2中的第一个元素

• page行号得到offset和len：跟进body的offset信息，得到第一个元素的offset和length

• 读取内容：跟进offset和length从body中读取内容

到此我们了解了分页后怎么根据行号找到任意一个值，OrdinalIndex是一个非常重要的索引，提供任意行号定位到page能力，读取列数据都要经过Ordinalindex索引

SegmentFooter

那么怎么找到每一列的ordinalindex呢？ordinalindex也是需要存到数据文件中的，orinalindex写到文件后，也会有一个pagepointer，需要把pagepointer保存起来，这个信息会保存在会数据文件的SegmentFooter信息里面，通过segmentfooter可以找到每个字段meta信息，包括类型，编码，索引，等等, footer数据结构有点复杂，如图所示

图中有3个虚线表示的框，代表一个数据文件的3个不同的区域， 从上到下，分别是数据区、索引区、footer区。下面区域生成时字段的信息依赖上面区域的数据， 位置不能反，footer区的结构都是PB的格式，索引区和数据区的footer部分也是PB格式，body部分和nullbitmap部分有自己的编码和解码格式

SegmentFooterPB最终会序列化后保存在数据文件的末尾格式如下，格式如下：

其中magiccode为一个固定字符串,用来标记是一个doris是数据文件，字符串默认是"D0R1"，占4个字节

到此我们再总结下doris从文件中读根据某个字段过程

• 读取文件尾部4个字节，识别是segment文件

• 读取4个字节的pbchecksum

• 读取4个字节的PBlength，得到segmentfooter序列化的长度

• 读取serializeedSegmentFooterPB内容，checksum校验通过后，反序列化得到SegmentFooterPB

• 根据SegmentFooterPB得到对应字段的ColumnMetaPB

• 根据ColumnMetaPB进一步得到ordinalindex，有了ordinalindex，进而可以读取任意一行数据

为了加深理解，可以思考下假设读取第3行的需要几次io操作？

字典编码

上面数据中我们注意到了字符串u4有2行的，在page2中存了两份，如果有100w行都是相同的，那么按照目前这种打平编码存储，就得存100w个相同值，存储利用率不高， 为了解决这个问题，引入了字典编码，通过给字符串指定编号，这个编号是一个int类型，从0开始自增,0表示空字符串，数据页只需要存储对应的编号，来减少存储的空间，这个字典存在单独存在字典页中，字典页在存储的时候用的页是plain编码

有了字典编码后，page1,page2中存储的内容实际是编码后的结果，字段的meta信息columMetaPB里面指定了编码格式，同时也记录了字典编码页保存的位置

到这里解决了重复字符串的优化存储，但同时引入了一个新问题，字典编码只适合重复度比较高的，如果字符串本身无重复或者重复度很低，就达不到减少存储空间的目的，因为字典本身也是要存到磁盘，而且可能会影响性能 ， 因为打平编码的时候只需要读取一页，字典编码则需要读取两页才能获取到值，所以怎么到底如何选择用哪种编码就称成为了不得不思考的问题？

doris采用的是试探法，优先先采用字典编码，随着数据增加， 如果字典大小超过一定的阈值退回plan编码，目前这个阈值是dict_page大小超过64KB，我们看看有了这个退回机制后，数据是怎么存储的， 假设我们开始开插入的是6行数据，一开始采用字典编码，插入到第6行的时候字典满了，则7，8两行退回采用plain编码,之后也采用plain编码

-> insert into t_user values("u5",15),("u6",20)

压缩&bitshuffle

到这里我们知道了字符串在doris内部是怎么存储的，先优先走字典编码，如果字典满了就回退了为plain编码，自适应比较完美了解决高基数和低基数场景下的存储效率问题，接下来讨论下怎么能高效的压缩进一步降低存储的空间

这个就没有什么悬念了，上压缩，直接每个page的body数据部分进行压缩然后再存储，doris支持的压缩算法有5种，lz4/lz4F/zlib/zstd/snppy,默认为lz4，可以在建表的时候指定

如果对 lz4算法熟悉就清楚该算法原理是判断当前的字段与之前是否重复，如果有，则保存重复字段之间的距离（offset）和重复长度（length），以此替代重复字段，从而达到压缩数据的效果，也就是相邻的字符串重复度越高压缩效率越好， 简单举例如下（详细的压缩流程和数据结构可以自行搜索）：

对于数字怎么进一步优化呢？数字前后可能都较少重复，直接使用lz4可能效果不太好

Doris引入Bitshuffle算法来对数字按照bit重新进行打散排序，该算法的原理是：

bitshuffle重新排列一组值以存储每个值的最高有效位，其次是每个值的第二个最高有效位，依此类推。

Bitshuffle本身并不压缩数据，而只是重新排列以提高压缩效率，实际的压缩是通过另外的压缩算法来执行的，由于bitshuffle的设计与lz4压缩算法匹配，因此，在使用Bitshuffle后，用lz4对每个数据块进行压缩，加上压缩后存储意图

到此doris怎么存储字符串，怎么高效的压缩介绍就结束了，我们来总结下：

• 列式分页存储，NULL值用bitmap来标记

• OrdinalIndex记录每个分页的位置

• 页内采用plain编码或者字典编码

• 字典编码时，会结合bitsshuffle来提升压缩效率

接下来会重点介绍下怎么提升查询效率，也就是怎么实现各种类型的索引

读数据流程

从上面介绍，我们知道doris内部维护了一个行号，这个行号对用户是不可见的，主要用于读数据方便，每个独立存储的列可以用行号串起来，读取的时候，首先生成会生成一个row_bitmap，代表本次要读取的行集合，有了这个集合就可以根据OrdinalIndex把数据读上来

row_bitmap初始大小为SegmentFooterPB.num_rows, 前面num_rows为8，则row_bitmap为8个bit，1表示对应位置要读取，为0表示不读取 ，初始时都为1，表示都要读取

索引过滤

索引目的就是根据条件快速找到需要读取行或者过滤掉不需要读取的行，然后不需要行读取在row_bitmap对应的位置设置为0

前缀索引

前面我们看到doris在存储时会先把所有行按照指定key字段进行排序，然后存储， key字段可以是1个字段或者多个字段，前缀索引在实现上就是基于排序的行，每间隔固定行记录下key和行号的对应关系，假设固定行数为3，则前缀索引结构如图

可以看到前缀索引相比原来减少了很多行数，变得更为稀疏，所以前缀索引也可以叫稀疏索引，索引怎么存储呢？doris有一个单独页来保存前缀索引，页footer记录了间隔的行数，结构如图：

前缀索引不是某个字段独有，作用范围是整个segment，所以页的地址记录在segmentfooter里面，如图

有了前缀索引后，我们看下是怎么过滤的，假设有条sql

select username from t_user where username="u3"

首先发现username是key列，先查询前缀索引(SegmentFooterPB->short_key_index_page->body)，通过二分查找发现u3在u2与u4之间，通过num_rows_per_block计算出u2对应的行号是3，u4对应的行号是5，那么u3对应的行号范围应该在[3-5],把这个范围合并到row_bitmap中，原来要查8行的，现在只有查3行就行了

当然前缀索引不仅仅能进行等值过滤，非等于过滤也是支持，原理跟等值的一样，都是基于key有序来缩小查找范围

前缀索引虽然过滤效果不错，但是只能用于有key列作为查询条件且顺序符合匹配要求时才能生效，如果查询条件是非key列怎么加速呢？

ZoneMap索引

为了加速在页内的查找效率， 写入时会收集每个页的关键信息，比如是否有NULL值，最大值和最小值分别是什么，基于这些信息起到快速过滤页的作用，关键信息称为zonemap索引，除了每个页会有一个zonemap索引，同时也会维护每个列的segment粒度zonemap索引，起到快速过滤segment文件的作用

zonemap信息怎么存储的，每一个zonemap是pb格式，序列化后作为字符串存储，页级别zonemap信息存储复用了字符串分页存储的逻辑，采用plain编码，segment的zonemap信息直接保存在segmentfooter的元信息里

有了zonemap，我们再看下过滤的过程是怎么样的，假设有如下sql:

1、select * from username where username is null
2、select * from username wehre username="u4"
3、select * from username wehre username="u8"

对于sql1，首先拿到segment粒度的zonemap (路径: ColumnMetaPB.indexs[1].zone_map_index.segment_zonemap）,取has_null 字段，为true说明这个segment的username字段存在为null的行，需要进行读取， 然后进一步确定哪些page存在null，根据page_zone_maps.ordinal_index_meta找到并遍历所有zonemappages里的每个元素，反序列化，找hash_null=true的元素，发现只有元素page1zonemapseralize结果符合要求，这个元素对应zonemappages编号为0，也就是数据页第一页，然后计算得到第一页的行范围，怎么找到页对应的行的范围呢？利用ordinalindex，回顾下ordinalindex的内容

里面记录了每个页的开始行号first_ordinal，那么每页的行范围就是=(当前页的first_ordinal,下页的first_ordinal-1)=(0,2) 把这个范围合并到row_bitmap中，最终读取0，1，2行，读上来之后再进行进一步过滤

对于sql2，流程跟上面一样，不同的是根据min,max判断是否要读取segment或页，username="u4" 确定只需要读取page2，page2对应的行范围是(3,5)，最终读取3，4，5行，读上来之后再进行进一步过滤

对于sql3，流程跟上面一样，不同的是在segment粒度的min,max判断后发现max<u8,索引不需要读segment，直接忽略，返回空

Bloom过滤器

实际上zonemap索引的过滤效果对于字符串还是比较有限，不同的内容，min/max的范围可能会比较大，导致能过滤的页有限，比如：就算是页内只有a,z两个元素，zonemap的min=a,max=z，那么查询b,c,d,e,f等时都不能过滤这个页，如果一个索引能直接告诉我们，这个值在不在该页内，不在则直接过滤，那么查询的效果会显著提升。bloom过滤器就是来这个实现需求的

doris会为每个数据页生成bloom过滤器，当有等值的查询条件，可以快速过滤掉不需要的页，bloom过滤器的原理网上比较多，这里就不做介绍，记住一个结论就行：给定输入bloom过滤器判断不存在那就肯定不存在，直接跳过这页， 如果判断存在那有可能存在，这页需要保留

bloomfilter信息怎么存储的，序列化后作为字符串存储，跟zonemap一样存储复用了字符串分页存储的逻辑，采用plain编码，结构如图

过滤流程跟zonemap差不多，这里就不在重复了， 遍历每个pagebloomfilterserialze，反序列化后，进行判断过滤，如果判断不在，则跳过对应的页，判断在则把相关的页的编号转成对应的行号范围合并到row_bitmap中

Bitmap索引

不管是zonemap，还是bloomfilter索引都是研究怎么更快的过滤不需要页的，不是精确到某一行，而bitmap索引是直接定位到行的索引，相比zonemap、bloomfilter效果会更好，bitmap索引有个map表会记录每个value的对应的行号集合，行号集合是以bitmap方式存储的，这大概是叫bitmap索引原因，结构如下

value在map中是排好序的，这样做的目的是可以根据某个value可以通过二分法快速找到，实现索引从磁盘按需加载，map表在存储的时候分2部分，字典部分和行号部分，2者是分开存储的且都复用了前面的分页存储方式，有点区别的是字典部分在保存页地址的时候记录是page的首个value和pagepointer，行号部分用的记录是first_oridnal和pagepointer

上面存的是value， 下面存储的行号，NULL对应的行号集合固定存储在末尾

假设有条sql: select username from t_user where username="u3" bitmap索引过滤过程是怎么样？

• 在DictIndexPage中根据二分查找，发现u3在第1页BitpageDictPage1中

• 在BitpageDictPage1中再通过二分查找，发现是第3个元素，对应BitmapIndexPage第3个值

• 然后在BitmapIndexPage中根据二分查找第三个值，发现在第1页BitmapPage1中，取最后一个值[3]

• 然后把这个行号集合[3]合并到row_bitmap中

主键索引

开始给的例子，表t_user的模型是明细表，如果是uniq表，doris 1.2版本后，会根据主键建立主键索引，通过主键直接一步导致找到行号，这个主键索引主要用于实现mow功能，其存储结构跟前面bitmap索引的字典部分实现差不多，这里不在过多介绍

全景图

为了有个更直观的认识，把上面提到存储结构整理了一张全景图，如果doris的存储部分的源码感兴趣，按图索骥看代码会丝滑些~

图有点模糊，上传后被压缩了，为了看得清晰，把原图上传一份了到了百度网盘，

链接: pan.baidu.com/s/1-PlNo7I0提取码: 2024

行读效率问题

笔者在看代码的时候一直有个疑问，doris的是根据行读取的，感觉有些场景下效率上会上不去，索引过滤后，中间存在空洞的，效率怎么保证的

doris 对应空洞情况做了优化，会进行分段读，每一段内的行是连续的，这样可以进行批量读取，从而提升效率

当然对于极端情况，每段只有1行，效率确实会不行的，比如过滤后 row_bitmap 是这样的

从实际的情况看，分段优化后 ，读取的效率性能还是比较好的~~

总结

• 字符串采用列存，切分为不同的page，page是存储和读取的最小单位

• 自适应识别高基数列和低基数列，低基数列采用字典编码，高基数列采用plain编码

• 当采用字典编码，会结合bitshuffle算法来提升lz4压缩效率

• segment内部维护了一个行号，OrdinalIndex记录了行号与page位置的关系

• segment内部自动维护2个索引，前缀索引和zonemap索引

• 用户可以额外的创建bloomfilter索引和bitmap索引，来加速查询

以上内容基于doris-2.0版本(commit-id:767b5a1770e33cf)整理