Page 391 - 《软件学报》2024年第6期

胡梓锐 等: HTAP 数据库系统数据共享模型和优化策略 2967

段树的树状结构, 基于数据旧版本可见性与活跃事务所在的时间分段 (Epoch) 的比较进行适时批量的垃圾回收.
这种解耦式设计以引入额外的存储和维护代价换取了 AP 的处理效率.
Sharma 等人 [57] 提出在一套系统内 TP 与 AP 负载不应该共享同一套版本链, 通过在 TP 端维护最新的版本和
在 AP 端维护一系列版本快照的方式来解决 MVCC 的弊端. 具体来说, TP 负载的执行仍基于 MVCC 维护版本链,
而当 AP 负载到来时, 系统会基于最新的版本在 TP 端建立一份虚拟快照以便修改, 而原有的版本链会逻辑地移动
到 AP 端. 最终在不阻塞 TP 写入的情况下, 通过在 AP 端维护多个快照版本链服务于 AP 负载的访问请求, 实现对
混合负载的支持. 这种方式一方面大大缩减了版本链搜寻的长度, 另一方面垃圾回收机制可以自然地对过期的快
照进行所有版本的回收清理, 避免了在原版本链中定位垃圾版本的繁复工作. 但该方法可能会因为建立快照期间
需要大量的互斥锁而降低系统吞吐. 同时, 也出现了一系列针对快照维护粒度的研究工作. 对于版本链完全分离的
追踪优化, Shen 等人 [16] 基于真实业务中 AP 查询一般会访问最新数据版本的判断, 提出可以在 AP 端为每个版本
以表的粒度独立维护一个快照, 这样当 AP 查询到来时, 可以线性地针对某个稳定版本进行扫描, 避免多版本链的
扫描代价. 但这种设计的劣势主要在于尽管表的快照会以增量的形式进行维护, 但其粗粒度带来的额外存储代价
依然是非常可观的. Boroumand 等人 [17] 则提出 TP 的更新往往会呈现一定的业务特征, 如对同一列的数据进行数
中增加了版本信息, 其维护代价也有所提高. 为此, Sun
据更新. 所以 AP 端可以以列为粒度维护版本链, 而不需要更新未被修改的列版本, 从而避免为这些列重复生成相
同的快照, 适当降低了创建快照的频率. 其本质属于对表粒度和行粒度维护版本链的一种权衡实现.
一些 HTAP 数据库系统的 AP 端与 TP 端一样使用 LSM-Tree 进行数据组织, 但也针对 AP 负载的特性对其结
构进行优化, 以加快读取的性能. 由于 LSM-Tree 天然会随着时间将数据向底层迁移压缩, 在这种机制下, 上层的
数据版本较新, 但会面临频繁的更新, 低层的数据版本较旧但稳定. 对此, Saxena 等人 [58] 优化了 LSM-Tree 的结构,
使其每层支持不同的存储格式, 使用行存的方式存储上层的数据, 便于快速修改; 在合并上层的数据进入下层级
时, 数据的存储格式变为列存, 并使 AP 查询直接访问下层的旧版本. 尽管降低了数据访问新鲜度但可以提高 AP
的读取性能. Dai 等人 [59] 则通过逐层训练预测模型的方式快速预测需要读取的数据位置. Zhong 等人 [60] 则提出一
种称为 REMIX 的索引数据结构, 通过在 LSM-Tree 存储结构中加入层内和层间的跳转指针支持了数据的有序访
问, 包括范围扫描和多粒度的二分查找, 减少了遍历的代价, 最终加速 AP 数据读取.
3.2.2 索引扫描
除却顺序扫描, 索引扫描也是支持高效访问数据的技术之一. 但在数据库中建立索引也会带来额外的维护代
价. 与传统的数据相对稳定的 OLAP 数据库索引维护代价相比, 混合负载中 TP 负载会引入大量的数据版本更新,
增加索引的存储和维护代价 [61] . 与此同时, 存在多个数据版本时, 存储需要判定每个数据项的各个版本的可见性,
这大大降低了索引访问性能. 因此, 需要设计考虑版本信息的新型索引结构来提高数据读取效率.
为了避免对数据版本的遍历, 需要将版本信息引入索引, 进而产生了多种不同的优化方法. 时间分割 B 树 [62]
在 B 树的基础上扩展了版本维度, 支持从版本和主键两个维度分别对索引进行分割. 当数据项的版本更新时, 在
版本维度上基于 B 树追加版本而非修改数据, 以提高检索版本的效率. MVBT [61] 则在 B 树的基础上增加了版本链,
在索引中维护数据项的多个版本, 并顺序连接以方便检索. MV-IDX [63] 则将版本链直接连接在索引对应的数据项
后, 可以直接检索的同时减少了索引维护的代价. 受到这些改进的启发, Riegger 等人 [64] 在分区 B 树的基础上实现
了版本可感知的多版本分区 B 树 (MV-PBT), 这一数据结构将版本作为分区的依据, 将不同版本的数据划分在不
同的索引分区中. 当发生了版本更新时, 数据库将新的版本数据插入最新分区, 并同时维护对应的旧版本映射. 当
需要进行搜索时, MV-PBT 按分区从新到旧进行扫描, 直到找到满足可见性的版本. 这些优化通过将版本信息维护
在索引中, 在面对混合负载导致的频繁版本更新时有效减免了判断版本可见性带来的开销. 但另一方面, 由于索引
等人 [65] 提出一个新的索引结构 P 树, 既将版本信息引入索
引结构中, 又通过对多个索引的嵌套实现对索引中部分数据项的复用, 降低了修改索引的成本. 当数据库产生一个
新版本时, 索引采用 COW 的方式生成一棵新的索引树, 并将没有修改的数据项指针指向旧版本索引, 更新新版本
数据对应的指针, 从而轻量地维护版本信息. 通过这种方式, 数据库将索引与版本一一对应, 便于根据版本搜索索
引, 从而避免了在判定可见性时遍历数据项的所有版本.