列存引擎 Tianmu 如何实现 Delete？| StoneDB 研发分享 #3-低调大师

列存引擎 Tianmu 如何实现 Delete？| StoneDB 研发分享 #3

2022-12-08 390

作者：李红建

责编：宇亭

在第一期研发分享中，我们解释了，为什么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启航计划的源码解读活动，李红建老师也会带大家深入理解一下Tinamu 引擎工具类模块的源码，欢迎大家关注收看：

StoneDB 开源地址：https://github.com/stoneatom/stonedb

StoneDB 社区官网：https://stonedb.io

添加小助手，加入社区交流群

与数百位资深数据库从业人员深度交流

子查询优化之 Semi-join 优化 | StoneDB 研发分享 #2

HTAP 的下一步？SoTP 初探（下）：解读 Serving over TP 和其典型案例场景

2023 年十大战略技术趋势中哪一项最需要 HTAP ？

HTAP 的下一步？SoTP初探(上)：数据分析从“大”数据转向“小”而“宽”数据

存算一体 VS 存算分离，IT发展下的技术迭代

没有HTAP，机器学习和人工智能都是不切实际的

面向场景，HTAP到底是刚需还是炒作？

StoneDB 团队成员与 MySQL 之父 Monty 会面，共话未来数据库形态

实现HTAP的关键技术有哪些？

解读《Benchmarking Hybrid OLTP&OLAP Database Systems》

深度干货！一篇Paper带您读懂HTAP

本文分享自微信公众号 - StoneDB（StoneDB2021）。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。

微信关注我们

原文链接：https://my.oschina.net/StoneDB/blog/5606544

转载内容版权归作者及来源网站所有！

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

基于全志平台成功移植 Arm Ubuntu 桌面系统

以桌面应用为主的开源的Ubuntu桌面操作系统，为全球数百万的PC和笔记本电脑提供了生产力。为方便用户选择合适的版本进行应用软件开发，我们发布了基于Ubuntu 64bit系统构建的Ubuntu16.04和Ubuntu18.04两个版本的 Ubuntu Desktop系统。 Ubuntu16.04和Ubuntu18.04 均具有资源占用少，稳定性强的特点。采用简洁高效的轻量级Linux主流桌面环境Xfce4，为用户提供了一个默认GNOME 桌面环境之外的选择。 Ubuntu16.04和Ubuntu18.04 系统可定制性强，针对嵌入式平台，可以根据需求，增加裁剪系统服务。基于Ubuntu系统，已经打通各通用底层接口。提供基于Arm GE8300 GPU的OpenCL支持。支持G2D加速完美适配QT 目前宇芯已经应用Ubuntu16.04 和Ubuntu18.04 系统，开发了工业平板及智慧支付领域的系统解决方案，帮助客户产品快递开发并成功落地。

2022-12-09

446

摘要：随着各领域加快向数字化、移动化、互联网化的发展，企业信息环境变得庞大复杂，身份和权限管理面临巨大的挑战。本文分享自华为云社区《面对庞大复杂的身份和权限管理，企业该怎么办？》，作者：华为云PaaS服务小智。随着各领域加快向数字化、移动化、互联网化的发展，企业信息环境变得庞大复杂，身份和权限管理面临巨大的挑战：应用规模快速增长，存在信息孤岛。各个应用系统的访问入口和帐号孤立分散在各自系统中，缺乏统一的用户管理体系，造成在流程效率、信息安全、风控管理方面存在诸多风险问题。用户数快速增长，用户维度扩大。用户、组织生命周期管理无统一的IT工具，人工管理低效易错。用户身份和权限，缺乏统一管理平台。人员流动（离职、转岗等）后帐号和权限无法自动更新状态，造成帐号泄密；无审计日志，帐号操作无法追溯。信息化发展，认证要求提高。传统的应用系统仅支持静态密码一种认证方式，无法兼顾易用和不同等级应用的安全性。面对以上挑战，传统的身份和权限管理系统已无法应对，我们可以怎么做呢？这里先给大家介绍IAM和IDaaS，这两个与身份和权限管理系统息息相关的概念。什么是IAM和IDaaS IAM（I...

2022-12-09

498

资源下载

更多资源

优质分享App

近一个月的开发和优化，本站点的第一个app全新上线。该app采用极致压缩，本体才4.36MB。系统里面做了大量数据访问、缓存优化。方便用户在手机上查看文章。后续会推出HarmonyOS的适配版本。

腾讯云软件源

为解决软件依赖安装时官方源访问速度慢的问题，腾讯云为一些软件搭建了缓存服务。您可以通过使用腾讯云软件源站来提升依赖包的安装速度。为了方便用户自由搭建服务架构，目前腾讯云软件源站支持公网访问和内网访问。

Nacos

Nacos /nɑ:kəʊs/ 是 Dynamic Naming and Configuration Service 的首字母简称，一个易于构建 AI Agent 应用的动态服务发现、配置管理和AI智能体管理平台。Nacos 致力于帮助您发现、配置和管理微服务及AI智能体应用。Nacos 提供了一组简单易用的特性集，帮助您快速实现动态服务发现、服务配置、服务元数据、流量管理。Nacos 帮助您更敏捷和容易地构建、交付和管理微服务平台。

Rocky Linux

Rocky Linux（中文名：洛基）是由Gregory Kurtzer于2020年12月发起的企业级Linux发行版，作为CentOS稳定版停止维护后与RHEL（Red Hat Enterprise Linux）完全兼容的开源替代方案，由社区拥有并管理，支持x86_64、aarch64等架构。其通过重新编译RHEL源代码提供长期稳定性，采用模块化包装和SELinux安全架构，默认包含GNOME桌面环境及XFS文件系统，支持十年生命周期更新。