作者：李红建
责编：宇亭
在第一期研发分享中，我们解释了，为什么Tinamu作为一款列式存储引擎在初期不支持 Delete 功能的原因，然后对一些友商列式存储引擎的 Delete 方案进行了一些调研和总结，感兴趣的同学可以查看我们上一期的分享：关于列式数据库实现 Delete 功能的调研之旅。
本期文章，我将向社区小伙伴们详细地介绍一下给 StoneDB 的 Tianmu 存储引擎添加 Delete 功能的开发思路，希望对感兴趣的同学提供帮助。
Tianmu 引擎的存储结构
首先我们需要知道 Tianmu 引擎的数据是怎么样存储的，这样才知道应该怎么删除数据，所以我们先研究下 Tianmu 引擎的存储结构。Tianmu 为每个表单独建立了一个文件夹，以表名+tianmu 命名，每个表的文件夹下面又为各个列分别建立了对应列的文件夹，以列编号为名从 0 开始依次递增，列文件夹下面存储元数据 DN 文件和实际列数据的 DATA 文件。
如上图所示，可以看到每个列文件夹下面有这么几个文件夹，其中：DATA 文件夹存储对应列 pack 的文件；DN 文件夹存储元数据 DPN 的文件；filters 文件夹下存放着直方图、映射表、布隆过滤器（Bloom Filter）等中间数据的文件；META 文件夹存储了列的一些固有属性，如数据类型、版本、压缩类型等；v文件下存储了列数据的版本。
当然，可能一些同学乍一看上面的什么 DN、DPN 都不知道什么意思，其实是因为我们的 Tianmu 引擎使用了非常重要的知识网格（Knowledge Grid）技术，后面我们有时间会单独出更详细的文章来分享知识网格相关的最新研究。
如上图所示，DPN（Data Pack Node） 是知识网格的数据元信息节点在代码中的数据结构，数据持久化在各个列文件夹下面的 DN 文件中，初始化数据元信息节点时从利用 mmap机制把DN文件映射到内存中。pack 是物理的数据块，每个pack存储着对应列中多个列数据，pack 对象跟 DPN 对象 1:1 对应，负责从 各个列文件夹下面的 DATA 文件写入数据 和读取数据。pack 中的数据经过高度压缩后存储到 DATA 文件中。
Tianmu 的数据都是根据列按照行数据紧密排序进行存储的，从文件中读取和写入的单位是 pack，其中：
行号与 DPN & pack 的关系：
DPN id 由 row_id 进行位移右移运行得出， pss 的值一般为 16 ，也就是说每 65536 行的数据组成一个 pack，数据包结构的信息比如行与数据包的偏移量 pss, 数据化结构体为 COL_META 持久化在 META 文件中。
行号与 pack 中数据 id 的关系：
数据 ID 由 row_id 对 1 左移 pss 为后的值 取余后得出，基本上数据ID也都是在 0~65536 之间。
可以看以下这幅图：
好了，以上就是我们对 Tianmu 引擎存储结构的一个简单介绍。
MySQL 的多引擎架构和执行接口
了解完 Tianmu 的存储结构后，我们就要去想如何进行删除的操作了，这个时候就需要用到 MySQL 的多引擎架构和执行接口了，因为我们要让用户使用 MySQL 客户端来进行 Tianmu 引擎里的删除操作。下图是 MySQL 的多引擎架构图：
可以看到，MySQL 架构的最大特点之一，就是支持可插拔存储引擎。再来看一下MySQL 的执行接口逻辑图：
这个部分，网络上的一些基础知识分享很多了，大家可以学习了解一下，我们这边特别要去讲解的是代码部分的逻辑，下面是我在 GDB 中调试的几个重要代码逻辑：
insert 调用堆栈：
#0 Tianmu::handler::ha_tianmu::write_row (this=0x7fdcec0107b0, buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:455
#1 0x0000000001d6e5a1 in handler::ha_write_row (this=0x7fdcec0107b0, buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8189
#2 0x00000000025ebf12 in write_record (thd=0x7fdcec000bc0,table=0x7fdcec00fdf0,info=0x7fe0c81c9b00, update=0x7fe0c81c9a80)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:1904
#3 0x00000000025e8fdd in Sql_cmd_insert::mysql_insert (this=0x7fdcec006ab0,thd=0x7fdcec000bc0, table_list=0x7fdcec006518)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:778
#4 0x00000000025ef9b3 in Sql_cmd_insert::execute (this=0x7fdcec006ab0, thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:3151
#5 0x00000000023cb967 in mysql_execute_command (thd=0x7fdcec000bc0,first_level=true)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3645
#6 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#7 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#8 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#9 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#10 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#11 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#12 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
update 调用堆栈：
#0 Tianmu::handler::ha_tianmu::update_row (this=0x7fdcec0107b0,
old_data=0x7fdcec09eb18 "\374\002", new_data=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:508
#1 0x0000000001d6ea41 in handler::ha_update_row (this=0x7fdcec0107b0,
old_data=0x7fdcec09eb18 "\374\002", new_data=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8230
#2 0x000000000247ed8c in mysql_update (thd=0x7fdcec000bc0, fields=...,
values=..., limit=18446744073709551615, handle_duplicates=DUP_ERROR,
found_return=0x7fe0c81c9c58, updated_return=0x7fe0c81c9c50)
at /home/Code/GitHub/stonedb/sql/sql_update.cc:894
#3 0x0000000002484ead in Sql_cmd_update::try_single_table_update (
this=0x7fdcec006808, thd=0x7fdcec000bc0,
switch_to_multitable=0x7fe0c81c9cff)
at /home/Code/GitHub/stonedb/sql/sql_update.cc:2927
#4 0x00000000024853d7 in Sql_cmd_update::execute (this=0x7fdcec006808,
thd=0x7fdcec000bc0) at /home/Code/GitHub/stonedb/sql/sql_update.cc:3058
#5 0x00000000023cba0c in mysql_execute_command (thd=0x7fdcec000bc0,
first_level=true) at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3655
#6 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,
parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#7 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,
com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#8 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#9 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#10 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#11 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#12 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
delete调用堆栈：
#0 Tianmu::handler::ha_tianmu::delete_row (this=0x7fdcec0107b0,
buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:581
#1 0x0000000001d6ee3f in handler::ha_delete_row (this=0x7fdcec0107b0,
buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8263
#2 0x00000000025e053f in Sql_cmd_delete::mysql_delete (this=0x7fdcec006e28,
thd=0x7fdcec000bc0, limit=18446744073709551615)
at /home/Code/GitHub/stonedb/sql/sql_delete.cc:497
#3 0x00000000025e3268 in Sql_cmd_delete::execute (this=0x7fdcec006e28,
thd=0x7fdcec000bc0) at /home/Code/GitHub/stonedb/sql/sql_delete.cc:1411
#4 0x00000000023cba0c in mysql_execute_command (thd=0x7fdcec000bc0,
first_level=true) at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3655
#5 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,
parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#6 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,
com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#7 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#8 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#9 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#10 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#11 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
由调用堆栈可知，insert、update和delete的相关代码指令都会调用到Tianmu::dbhandler::TianmuHandler 类中各自功能的函数，而 TianmuHandler 继承自 handler，MySQL 以 handler 为基类，各个引擎的 handler 类为子类，利用多态的原理实现对不同引擎的调用。
如果要实现Tianmu的单表 delete 功能，就需要在 TianmuHandler :: delete_row() 中进行实现。同时 handler 类还提供了删除所有行的虚函数 delete_all_rows() 如需支持删除所有行的数据，可在TianmuHandler :: delete_all_rows() 中进行实现。
Tianmu 引擎删除数据的过程
由此，我们便可以对 Tianmu 的delete功能进行设计和研发了。下面是我调研实现 delete 功能的流程图：
单表 delete all 功能：
目前我们是支持 truncate 功能的，单表 delete all 的功能就直接复用 truncate 的逻辑。
条件 delete 功能：
条件 delete 这里我们采用标记删除的策略。列式数据库的存储结构决定了对真实的数据进行删除时必须要对整个表的数据进行重新移动整理，因为除了删除无用的行，还需要合并数据块。这样的话，在数据量非常多的情况下，对真实的数据进行删除将会是非常大的动作，不仅会消耗机器大量的IO资源和CPU资源，同时删除的速度也会比较慢。这也是目前主流支持列式数据库的厂商都使用标记删除的原因。
注意看上面的执行流程图，我们会发现一个很重要的节点——Deletebitmap（Delete位图），这个 Delete 位图是什么呢？这里要重点讲解一下。
位图（bitmap）的实际存储形式是个 int32 类型的数组，原理是使用 int32 类型的值占用的 32 位空间使用 0 或 1 存储并记录这 32 个值的状态。位图中的比特总数等于包中的行的总数。数据在 pack 中的位置和位图中的位置是一一对应的，这样可以有效地节省空间。
那么 Delete 位图应该存放在哪个位置呢？一般有这么四种方案：
方案1.存放在pack里：
优点：进行标记删除的时候同时可对数据置空，可有效的释放字符串类型的空间，同时可优化 select ,insert ,update 带where子句的数据过滤场景。不需要修改上层逻辑。整体逻辑简单。修改面主要集中在pack层。
缺点：每次删除都需要对 涉及的pack进行读取 解压缩/压缩。（其他方案在修改元数据时也需要对pack进行读取解压缩）
方案2.存放DPN里：
优点：删除不需要对 pack 进行读取保存，只需要修改元数据即可，且 delete 位图大小是固定的。
缺点：delete 位图过大，一般是 8192 个字节，远远超过原本元数据的大小，会极大的影响原 DPN 的读写效率。
方案3. RCAttr::hdr 中：
优点：
一个列中只需要维护一个delete位图即可，节省存储空间。
缺点：
因为列的数据数量是会随时变化的，不像 pack 和DPN 维护的单独一个包数据的数量是固定的，这就造成了 ，delete位图的大小也需要随时变化。
方案4. 为每列新增 deleteBitMap 文件：
在 DPN中增加 deletBitMap 索引，与 deleteBitMap 文件中的 deleteBitMap 对应，如下图：
优点：
可以与 DPN 一 一对应，且 delete 位图大小固定。
缺点：
需要新增一个文件专门维护 delete bitmap ,读取 DPN 文件的同时也需要读取 delelte bitmap 文件，会增加一次 IO。
我们最后的选择
最后，经过综合考量，我们这里使用了方案 1 进行了把 delete 位图放到 pack 里进行标记 delete 功能的开发。
数据过滤的流程和涉及逻辑的改造
经过上述的思路梳理，我们应该大致能清晰地了解到增加 Delete 功能的流程，因为涉及的东西比较多，我这里做了一个脑图，具体的代码，大家可以访问我们的Github 代码仓库进行了解：https://github.com/stoneatom/stonedb
其中Tianmu引擎存储的元数据和pack数据是支持多版本的，这样可以保障数据的原子性，而且可以支持并发的读取数据，也就是说，在执行delete时并不会堵塞select，用户访问的数据是最终确定的版本。关于多版本和并发访问控制会在以后单独出文章进行详细的讲解。
好了，以上就是目前 StoneDB 自研列式引擎 Tianmu 对 Delete的实现思路，希望这两期分享能给大家带来帮助。当然，由于是文章，里面很多图片的细节，我们没有展开描述，之前我们有开展过技术分享公开课，大家也可以前往B站观看这两期视频：
【StoneDB每日讲】Tianmu 引擎 Delete 方案的调研-第一讲
https://www.bilibili.com/video/BV1Q14y1t7ZC
【StoneDB每日讲】Tianmu 引擎 Delete 功能的诞生-第二讲
https://www.bilibili.com/video/BV1Cg411S7tt
StoneDB 开源地址：https://github.com/stoneatom/stonedb
StoneDB 社区官网：https://stonedb.io
