DWS下传统列存到HStore再到LStore的存储演进史（1）

作者简介：2014-2021年在gaussdb开发列存、elk产品、分布式事务相关模块，构筑基础AP分析能力底座，2021年-2025年在dws作为owner从头设计推出了HStore存储引擎，2025年-2026年接手LStore存储引擎作为owner实现商用落地。

DWS的前身就是gaussdb，作者一直在DWS数据库项目的开发第一线，这篇文章就从存储引擎的角度回顾一下DWS数据库底层的演进，包括很多设计上的经验教训。

gaussdb最早是在美研做的原型，早期的北京几位大佬也深度参与其中，基于PG开源数据库做了列存，线程化改造，向量执行引擎，streaming等基础能力。心声上很多人会说gaussdb不就是pg开源的魔改版本，这么多年做下来，其实我们和PG开源社区的差异之大不亚于重新写一个新数据库。我一直认为基于开源是一个很好的切入方式，逐渐熟悉内核能力，一步一个脚印才能真正理解数据库内核，现在即便有AI的辅助，但数据库内核方方面面的经验依然必不可少。由于作者一直都在存储引擎领域，对于执行器、优化器等其他模块理解深度难登大堂，故后续只就存储引擎方面展开。

我们为什么要做列存？

列存的出现是AP业务推动的必然结果，数据量越来越大，查询的复杂度越来越高，纵使SSD也在当时那个时期开始快速普及，但IO整体能力依然追不上数据量增长的速度和客户业务对于查询性能提高的诉求。列存出发点就是给类似工行金融跑批业务设计的，优势点如下：

1. 列的数据特征比较相似，适合压缩，压缩比很高
2. 表列的个数比较多，但是访问的列个数比较少, 列存可以大大减少不必要的IO读, 提高性能
3. 基于列批量数据的运算，CPU的cache命中率比较高，性能比较好
4. 列存储引擎更适合OLAP大数据统计分析的场景。

主要概念包括：

• CU：压缩单元（Compress Unit）， 列存储最小单位，导入数据时生成，生成后数据固定不可更改，单个CU最多存储1列60,000行。同一列的CU连续存储在一个文件中，当大于1G时，切换到新文件中。
• CUDesc：行存表，每行记录描述一个CU，包括最大最小值，以及CU在文件中偏移量和大小。其中col_id=-10的行称为VCU，cu_pointer记录这一组CU (cu_id相同) 中哪些行被删除 (Delete Bitmap)。
• Delete Bitmap：当CU中某行被删除，则对应bit置为1。
• Ctid：标识列存表的一行，由cu_id和CU内行号 (cu_id, offset) 组成。兼容行存表。

DWS列存优化点

因为上述优势点，列存储在很短的时间就变成了数据AP分析领域的主流，但单纯列存并不能实现领先，友商也都有列存。那dws在列存领域又做了啥特殊优化呢？简单列了几个作者觉着有代表性的点：

1. 利用cudesc描述表把原有行存的强事务一致性完整带到了列存上，利用deletemap合并了删除信息，CU数据就完全和事务信息解耦，每列数据元信息独立且物理上单独存储。
2. CU+ctid的概念组合，即做到了物理文件的append only，又实现了ctid可快速定位追踪，二级索引点查加速是很多友商不具备的。
3. 基于列存储的psort索引加速，用列存本身存储索引信息，空间相比btree节省3-5倍。
4. append only模式下的列存储空间回收机制，重写CU到新文件，独创优势有：重写以CU为单位搬迁IO效率高，重写过程不改ctid不变索引，和DML操作完全无锁并发。

好的方面说完了，下面说说我们都踩了那些坑：

1. 实时入库场景无法支持
传统列存由于数据集合的诉求，天然对于批量场景非常友好，但无法支持单条实时入库的场景（会产生海量的小CU，空间严重膨胀）。为了解决该场景，我们陆续设计实现了列存delta、elk，但都差强人意，下面简单说一下痛点：

• 列存delta是设计原型时就预留好的方案，预留了1000个cu给delta，预留方案优势在于简单，核心问题有下面两个：
  （1）预留1000个CU可能会被用完
  （2）cuid复用需要上大锁确保前面的cuid已经不被使用
• elk是在sql on hadoop场景需求下做的一个产品形态，为了解决上面的问题，做了新的列存delta，不用预留的1000个CU，单独的一个行存表+单独分配一套cuid，查询的时候通过union all的方式将列存表和delta行存表查询结果合并到一起，更新操作也是对两个表分别update和delete，虽然可以解决上面的问题，但又带来新的问题：
  （1）delta表的数据需要定期merge到主表，merge过程需要删除delta记录，和并发的DML操作会产生锁冲突，影响正常业务
  （2）union all的特殊操作，对于优化器带来了巨大复杂度，复杂查询下经常会产生很差的计划，调优和维护难度大

2. 小文件爆炸
列存最开始设计，考虑的是极致的列式存储，每一列都会产生一个独立的文件，这样可以让一列的数据全都连续的存储，这样对于查询的IO确实是最佳方式，但并没有考虑下面三个场景：

• 大宽表列数非常多数据量并不大场景下，每列一个文件会产生非常多的小文件，导致本地磁盘性能下降严重，类似备份恢复，build等涉及文件拷贝的操作也会变的很慢
• 小表很多的场景下，每个表每列都会产生一个文件，同上也会产生过多的小文件
• 全表扫描，扩容重分布场景下，因为扫描顺序天然是按照CU的，这种情况下把一个CU所有列的数据按利存储到一起IO效率更高

针对这种情况，我们已经推出了列存2.0格式，所有列的CU合并存储到一个文件中，综合表现优于之前。

3. 并发更新锁
deletemap解决列存储下并发一致性的问题，但成也它败也它，由于一个CU的删除信息用一个delete字段存储，导致并发更新同一个CU的多个DML操作就必然出现互锁等待的情况，这个问题属于列存设计框架的约束，不重新设计整个框架是没有办法解决的。

4. 压缩效率低
其实这个不能说是问题，只能说是最开始设计列存时期的局限性，那会还没有特别多的新压缩算法出来，随着时间的推移，不断有新的更好的压缩算法出来情况下，我们也得与时俱进，提供更好的压缩选项给客户。

5. upsert入库性能极差
upsert遇到冲突时涉及recheck，列存基础框架没有recheck的能力，导致upsert无法并发，再加上前面说的锁和小CU问题，upsert基本就没法使用

6. 不支持增量数据同步
核心在于不支持binlog能力，行存还能通过xlog逻辑解码实现增量同步，但是列存CU数据由于不记录xlog，只能依赖类似binlog的能力。

7. 执行引擎算子能力和存储格式能力缺少组合
列存格式天然适合向量化执行，但我们没有把执行算子的能力和存储引擎的能力深度结合，比如filter下推到解压缩之前，字典过滤，hashjoin下推过滤等等，也都在后续存储引擎设计的时候考虑进去了。

带着上面这些问题，我们在传统列存储引擎的基础上又设计实现了HStore存储引擎，篇幅有限，本文就先只介绍列存，后续再推出HStore，LStore的相关介绍文章。