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

2966 软件学报 2024 年第 35 卷第 6 期

点, 让中心化的日志记录更快、扩展性更好.
Boroumand 等人 [17] 提出 Polynesia 优化回放日志更新到列存数据的时延. 对于日志同步阶段, 其将列存数据上
的日志同步分为 3 个阶段, 分别为合并, 定位和复制. 合并阶段首先通过扫描各个线程的日志, 按提交 ID 顺序排序
成一个最终日志; 定位阶段, 将最终日志上的每一项通过哈希映射逐个发送到各自需要修改的列对应的列缓冲区
中; 复制阶段, 将这些列缓冲区中的日志传输至 AP 端副本进行数据更新. 接下来, 对于日志回放阶段, 为了维护列
式存储的有序且解决列规模太大易带来的排序代价过高问题, 该工作通过将原先为了压缩而维护的字典和日志回
放的更新字典进行合并, 用于原来的列存数据, 最终将原先排序更新的时间压缩至线性空间, 且该工作通过软硬件
协同的方式加速了回放的速率.
3.1.2 基于数据拷贝的同步优化
基于日志回放的同步方式, 虽然比较灵活且在空间开销上获得了较大优势, 但是无法避免日志存取的 IO 开
销, 而基于数据拷贝的同步方式往往按批实现 AP 与 TP 端数据的一致性, 以磁盘块为单位的读取在 IO 开销上有
其独特的优势, 因此对于改动量小且分布位置不集中的场景来说, 回放日志引起的数据复制传输量小, 较为灵活,
而对于修改位置集中的批量更改来说, 使用全表级或分区级别的数据复制传输能够有效减少 IO 开销 [46] , 更适合
合概率模型改进了跳表, 将搜索时间复杂度缩减为
在 Epoch、ETL 或者类 ETL 的批量同步中使用.
IBM 的 IDAA [46] 在混合负载处理上, 除了通过 CDC 监视事务日志、对日志以指定时间间隔的微批次实现增
量更新外, 对于 AP 端数据的大批量初始化、大变更、无法明确一个分区是否被更改情况, 可以以不同粒度 (以表
或分区为单位) 进行数据同步. 所以是否使用大批量数据同步和数据修改量的大小、分布等有关系工作 [55] 提出同
步回放时增量数据和历史数据的合并时间受多种因素影响难以预测, 且合并时需要考虑不同分区负载的平衡, 设
计了一种基于学习的 (learning-based) 框架和多轮平衡策略, 以实现自适应的同步数据合并.
3.2 版本追踪优化

MVCC 和 LSM-Tree 正被广泛应用于各类数据库中, 并面向 OLTP 负载展开了一系列优化. MVCC 有效地控
制了 TP 写入的数据版本和 AP 读取版本的数据可见性, 提高了事务并发; 而 LSM-Tree 良好的顺序写入磁盘的优
势也极大优化了写密集的 TP 场景性能. 但这两种技术都无法高效地支持 AP 大规模扫描任务.
首先, 传统的 MVCC 机制并没有对 TP 和 AP 负载进行明确区分, 混合负载往往共享一套版本链, 这使得在实
际执行时会面临诸多挑战. TP 负载大多是单点读写而 AP 负载大多有范围扫描, 这种差异使得版本管理本身存在
矛盾, 优化很难兼顾. 并且随着 TP 负载的写入增加, 版本数量急剧增长, AP 负载在遍历和选择版本时就将会遇到
较大的扫描代价 [57,66] . 另一方面, AP 查询若长期持有某个版本快照, 使得垃圾回收机制无法及时有效地进行版本
清理, 版本的持续积累也已被论证会给系统带来极大性能降级 [28] , 进而影响 TP 负载写入性能.
其次, LSM-Tree 设计的分层结构会随着时间的推移将较冷的数据向底层迁移, 由于数据的不同版本可能由于
合并时间的不同分散在 LSM-Tree 的不同层中, 难以直接定位和访问. 因此对数据进行读取常会涉及多次随机访
问, 降低了数据的读取性能 [58] , 不利于对批量数据的扫描和定位.
3.2.1 顺序扫描
针对版本链追踪的问题, 传统的 MVCC 设计会以每一个元组为单位独立构建版本链. 当进行扫描时, 其追溯
的代价非常大. 所以 Kim 等人 [29] 设计了一个被称为 vWeaver 的数据结构, 在面向同一个数据项的版本链追踪上结
O(lgN); 在不同数据记录之间的版本链中引入额外的指针连接,
基于搜索大概率会发生在相邻数据版本之间的假设, 将记录间的相邻版本进行连接, 因此整体的版本链就被编织
串接起来, 在一定程度上加速了版本链的追踪和扫描.
Kim 等人 [56] 同时考虑了版本链扫描和版本回收两个问题, 指出传统的 MVCC 设计中快速的版本清理会导致
频繁的磁盘 IO, 同时造成版本链断裂使得版本链需要修复重组才能继续检索, 也会影响版本的追踪与定位效率.
因此他们提出可以将版本追踪和版本清理两个动作分离开, 一方面沿袭了将最新版本与正在修改的数据置放在一
起并将剩余的旧版本独立存储于额外空间的思想 [67] ; 另一方面借鉴传统 UNIX 文件系统中 Inode 索引的设计理念 [68] ,
构建了一套轻量的版本索引结构加速对旧版本块的搜索, 将数据版本与索引版本分离开; 同时设计了一种类似线