关于数据库:HTAP的关键技术有哪些-StoneDB学术分享会第③期

在最新一届国内数据库顶级会议 ACM SIGMOD 2022 上，来自清华大学的李国良和张超两位老师发表了一篇论文：《HTAP Database: What is New and What is Next》, 并做了《HTAP Database：A Tutorial》的专项报告。这几期学术分享会的文章，StoneDB 将系统地梳理一下两位老师的报告，带读者理解 HTAP 的倒退现状和将来趋势。

在第一期分享中：StoneDB：深度干货！一篇 Paper 带您读懂 HTAP | StoneDB 学术分享会第①期
咱们曾经把 HTAP 产生的背景和现有的 HTAP 数据库及其技术栈做了一个简略的介绍，这一期，咱们将着重讲一讲报告中对 HTAP 关键技术的解读。

在正式开始前，先给上期简略收个尾，报告中提到 HTAP 数据库除了以下四种：

• Primary Row Store + InMemory Column Store
• Distributed Row Store + Column Store Replica
• Disk Row Store + Distributed Column Store
• Primary Column Store + Delta Row Store

还补充了 3 种，感兴趣的读者能够自行理解：

• Row-based HTAP systems：如 Hyper（Row）、BatchDB 等
• Column-based HTAP systems：如 Caldera、RateupDB 等
• Spark-based HTAP systems：如 Splice Machine、Wildfire 等

上面进入注释，本篇报告中次要介绍了 HTAP 的五大类关键技术，别离是：

1. Transaction Processing（事务处理技术）
2. Analytical Processing（查问剖析技术）
3. Data Synchronization（数据同步技术）
4. Query Optimization（查问优化技术）
5. Resource Scheduling（资源调度技术）

Overview of HTAP Techniques

这些关键技术被最先进的 HTAP 数据库采纳。然而，它们在各种指标上各有利弊，例如效率、可扩展性和数据新鲜度。

An Overview of HTAP Techniques

Part1 事务处理 (TP) 技术

HTAP 数据库中的 OLTP 工作负载是通过行存储解决的，但不同的架构会导致不同的 TP 技术。它次要由两种类型组成。

1. 应用内存增量更新的单机事务处理

Standalone Transaction Processing with In-Memory Delta Update
关键技术点：

• 通过 MVCC 协定进行单机事务处理
• 通过内存增量更新进行 insert/delete/update 操作

相干数据库：Oracle、SQL Server 和 SAP HANA 等

Standalone TP for insert/delete/update operations

下面这张图介绍了单机事务处理执行 insert/delete/operations 操作的一个逻辑过程，总体上是借助 MVCC+logging，它依赖于 MVCC 协定和日志记录技术来处理事务。具体来说，每个插入首先写入日志和行存储，而后附加到内存中的增量存储。更新创立具备新生命周期的行的新版本，即开始工夫戳和完结工夫戳，即旧版本在删除位图中被标记为删除行。因而，事务处理是高效的，因为 DML 操作是在内存中执行的。请留神，某些办法可能会将数据写入行存储 或增量行存储，并且它们可能仅在事务提交时写入日志。
个别有三种形式来实现内存增量存储，别离是：Heaptable(堆表)、Index organized table（索引组织表） 和 L1 cache（一级缓存），具体区别如下表：

Three implementations for an in-memory delta store

三者次要的区别在于插入（insertion）速度、查问（lookup）速度和容量（capacity）大小上。

2. 应用日志回放的分布式事务处理

Distributed Transaction Processing with Log Replay

关键技术点：

• Two-Phase Commit(2PC)`+Paxos 用于分布式 TP 和数据复制
• 应用 Log replay(日志回放)更新行存储和列存储

相干数据库：F1 Lightning
注：这里有稍有不同的分布式 TP 计划，就是采纳主从复制（Master-slave replication）的形式实现 HTAP，比方 Singlestore。

如上图所示，这种主从复制的形式下，主节点处理事务，而后将日志复制到从节点再做剖析。

另外就是通过 2PC+Raft+logging，它依赖于分布式架构。

Modified Raft Protocol for TP and AP nodes

它通过分布式事务处理提供了高可扩展性。ACID 事务在分布式节点上应用两阶段提交 (2PC) 协定、基于 Raft 的共识算法和预写日志 (WAL) 技术进行解决。特地是 leader 节点接管到 SQL 引擎的申请，而后在本地追加日志，异步发送日志给 follower 节点。如果大多数节点（即法定人数）胜利附加日志，则领导者提交申请并在本地利用它。与第一种内存增量更新的形式相比，这种基于日志的形式因为分布式事务处理效率较低。

3. 比照

最初咱们将提到事务处理技术做一个比照：

Comparisons of TP techniques in HTAP Databases

Part2 查问剖析（AP）技术

对于 HTAP 数据库，OLAP 负载应用面向列的技术执行，例如压缩数据上的聚合和单指令多数据 (SIMD) 指令。这里介绍两大类型和三种形式：

1. 内存增量遍历 + 单机列扫描

Standalone Columnar Scan with In-Memory Delta Traversing
关键技术点：

• 单指令多数据(SIMD)，向量化解决
• 内存增量遍历（In-Memory Delta Traversing）相干数据库：Oracle、SQL Server

举几个例子：

在（a）里，咱们查问订单表中名称为 JASON 的花了多少钱，那么基于 SIMD 的查问形式，是能够通过 CPU 把数据 Load 到寄存器中，只须要一个 CPU 执行的周期，就能够同时去扫描查到满足条件的两个数据。

如果基于传统的火山模型，用的是一种迭代模型，就须要拜访四行数据，而基于这种列存的形式，只有拜访一次就能够失去后果。

同样的，还能够通过这种形式做基于 Bloom Filter 的向量化连贯，也能够提交查问剖析的效率。

在增量表中获取可见值，并跳过删除表中的古老数据

除此之外，咱们在做列存扫描的同时要去扫描一些可见的增量数据来实现实时数据的剖析，也去扫描删除表中是否有过期的数据，最终达到数据是陈腐的。

2. 日志文件扫描 + 分布式列扫描

Distributed Columnar Scan with Log File Scanning
关键技术点：

• 列段上的分布式查询处理
• 基于磁盘的日志文件归并与扫描 相干数据库：F1 Lightning

Distributed Columnar Scan

Samwel, Bart, et al. “F1 query: Declarative querying at scale.”PVLDB 11(12) , 2018: 1835-1848.

如上图所示的分布式列扫描，传统办法就是基于多个 Worker 来做并发的多节点下进行算子下推，扫描之后，在下层做一些汇集、HASH、排序等一些操作。

Log File Scanning

Yang, Jiacheng, et al. “F1 Lightning: HTAP as a Service.” PVLDB 13(12), 2020: 3313-3325.

与分布式列扫描同时进行的还有日志文件扫描，咱们还要基于列存储来做算子下推来查到以后增量存储中最新的数据，再进行数据合并。上图里的 F1 Lighting 就能够反对把 10 个小时的数据合并到 Delta 中。

3. 技术总结

内存中增量和列扫描

将内存中的增量和列数据一起扫描，因为增量存储可能包含尚未合并到列存储的更新记录。因为它曾经扫描了最近可见的 delta tuples in 内存，因而 OLAP 的数据新鲜度很高。

基于日志的增量和列扫描

将基于日志的增量数据和列数据一起扫描以获取传入查问。与第一种相似，第二种应用列存储扫描最新的增量用于 OLAP。然而，因为读取可能尚未合并的 delta 文件，这样的过程更加低廉。因而，数据新鲜度较低，因为发送和合并 delta 文件的高提早。

列扫描

只扫描列数据以取得高效率，因为没有读取任何增量数据的开销。然而，当数据在行存储中常常更新时，这种技术会导致新鲜度低。

4. 比照

Comparisons of AP techniques in HTAP Databases

对于第一种单机列扫描 + 内存增量遍历来说，长处是数据新鲜度较高，毛病是须要比拟多的内存空间。对第二种分布式列扫描 + 日志文件扫描来说，长处是扩展性高，毛病是效率比拟低。

Part3 数据同步 (DS) 技术

因为在查问时读取增量数据的老本很高，因而须要定期将增量数据合并到主列存储中。这个时候，数据同步（Data Synchronization）技术，就十分重要了，也是分为两大类型。

类型一：内存增量合并

关键技术：

• 基于阈值的合并（Threshold-based merging）
• 两阶段数据迁徙（Two-phase data migration）
• 基于字典的迁徙（Dictionary-based migration）

相干数据库：Oracle、SQL Server、SAP HANA
Threshold-based merging

举个例子，如果阈值达到列存储 90% 的容量时，咱们就把 Delta Table 中的数据合并到 Column Store 当中，当然这种形式有个毛病——如果阈值设置的太大可能会导致 AP 的性能产生抖动，所以看到图里咱们加了一个 Trick-based，最好是定小量按期地去合并，做一个衡量。

Two-phase data migration

两阶段数据的迁徙，能够拿 SQL Server 举例，如图所示：

• 第一阶段：迁徙筹备

  • 第（1）步先插入 RID 去把须要暗藏的数据写入到删除表当中；
  • 第（2）步把这些数据调配 RID 后生成 Delta Colunm Store；

• 第二阶段：迁徙操作

  • 第（3）步，把刚刚插入进去的 RID 删除；
  • 第（4）步，最初真正把 Delta 中相干的数据删除，最初才把生成的增量列存合并到主列存中，达到了数据迁徙的成果。

Dictionary-based migration

第三种基于字典的迁徙，SAP HANA 就是采纳这种形式。如图所示，它第一阶段次要是针对每一列的数据做一个本地字典的形式映射过来减少对应的数据向量，第二阶段，才会把这个字典退出到全局的字典，做一个全局的排序，最初合并到数据向量当中。

类型二：基于日志的增量合并

关键技术:LSM-tree 和 B-tree
相干数据库：F1 Lighting
这种类型分两层：

• Memory-resident deltas（驻留内存的增量），次要是 row-wise
• Disk-resident deltas（驻留磁盘的增量），次要是 column-wise

Log-based delta merge

如图所示，第一阶段会把小文件、小 delta 按它到来的程序合并到增量的文件当中，第二阶段会通过查找 B 树来做一个有序合并，最终让合并的 Chunk 是有序的。这次要波及解决基于多版本的一些 Log 怎么去做合并和折叠，其中 B 树次要的作用就是在有序合并时去减速数据查找的过程。

3. 技术总结

可归类为有 3 种数据合并技术。别离是：

1. 内存中增量合并；
2. 基于磁盘的增量合并；
3. 从主行存储重建。

第一个类别定期将新插入的内存中增量数据合并到主列存储。引入了几种技术来优化合并过程，包含两阶段基于事务的数据迁徙、字典编码排序合并和基于阈值的变动流传。
第二类 将基于磁盘的增量文件合并到主列存储。为了放慢合并过程，增量数据能够通过 B 树进行索引，因而能够通过键查找无效地定位增量项。
第三类从主行存储重建内存列存储。这对于增量更新超过某个阈值的状况很典型，因而重建列存储比合并这些具备大内存占用的更新更无效。

4. 比照

Comparisons of DS techniques in HTAP Databases

总体来看，基于内存的增量合并效率比拟高，扩展性差点儿；基于日志的合并，扩展性好，然而多重合并的代价会比拟高。

Part4 查问优化技术

HTAP 中查问优化技术次要波及三个维度，包含：

Query Optimization in HTAP databases

1. In-Memory Column Selection

• 解决的问题：要从行存储区中抉择哪些列进入内存呢？简略的做法是全副抉择进去，但那样存储和更新的代价会很高，所以个别是基于历史的统计信息和现有内存的估算来做衡量抉择。
• 解决形式：有两种，第一种是热力求（Heatmap），第二种是整数布局（Integer programming）·

基于 Heatmap，比方 Oracle
通过拜访频度来治理列存并进行热力求的制作。

Oracle 21c. Automating Management of In-Memory Objects., 2021.

如图所示，首先依据最下方长久化行存（Persistent Storage）来选定一些候选列集（Candidate Columns），通过记录候选集的拜访频度。有些列就会变为 Hot Columns，那么就能够把最新的数据 Load 进去（图中左下方的 Populating）来达到减速查问的成果；缓缓地也有一些列会变为 Cold Columns，那么就把这些冷列进行压缩（Compressed Columnar data），而后最初排除（图中右下方的 Evicating）到内存当中，再选取其余被高频拜访的列反复进行。

基于 Integer programming，比方 Hyrise

Integer programming for 0/1 Knapsack problem，第一种基于热力求的形式齐全没有思考抉择列的代价，那么第二种就是把代价函数（cost-based optimization problem）思考进去，再从二级存储中抉择列。

Boissier, Martin, et al. “Hybrid data layouts for tiered HTAP databases with paretooptimal data placements.” ICDE, 2018.

这个指标函数 F(x→)就是要去优化所有的查问代价函数 fj(x→)，而每个查问代价函数要去掂量所抉择列的代价。总指标是最小化这个代价，要小于这个最大的 A 估算。（这里不开展讲了，感兴趣能够浏览这篇论文，也比拟经典）

2. Hybrid Row and Column Scan

• 解决的问题：内存中抉择好列之后，如何利用混合行 / 列扫描减速查问呢？这个比拟前沿了，像 Google 的 AlloyDB 也反对这个个性。
• 解决形式：基于规定的打算抉择（Rule-based）或者基于代价（Cost-based）的打算抉择。次要决定查问优化器要把哪些算子下推到列存引擎当中。

Rule-based Optimization(RBO)

先定义一些扫描的规定，比方先看列扫描，再看行扫描。相干数据库：Oracle、SQL server。

举个例子，上图中咱们查找一些北京车子注册的证书和色彩，在这种规定下就能够生成一个逻辑打算树，在这个逻辑打算树里，咱们先去查找底层表到底是行存还是列存，如果是列存，就做列存的形式解决，如果是行存就做一个 B 树的扫描。最初合并做一个连贯再返回最终后果。

Cost-based Optimization(CBO)

基于代价的形式，解决的形式是先去比照 列存扫描 和行存 / 索引扫描 的代价别离是多少，而后再决定查问算子在哪里执行。

Compare the cost of row/index scan with the cost of columnar scan

3. CPU/GPU Acceleration for HTAP

这个基于硬件去做 HTAP 的减速。比方，基于 CPU/GPU 异构处理器的形式进行 HTAP 的解决。相干数据库：RateupDB、Caldera。

CPU/GPU processors for HTAP

• Task-parallel nature of CPUs for handling OLTP

  • CPU 工作并行的个性能够用来解决 OLTP

• Data-parallel nature of GPUs for handling OLAP

  • GPU 数据并行的个性能够用来解决 OLAP

波及到一些并行计算的常识，感兴趣能够理解理解~

4. 技术总结

1. HTAP 的列抉择；
2. 混合行 / 列扫描；
3. HTAP 的 CPU/GPU 减速。

第一种类型依附历史工作负载和统计数据来抉择从主存储中提取的频繁拜访的列到内存中。因而，能够将查问下推到内存中的列存储以进行减速。毛病是可能没有抉择新查问的列，导致基于行的查询处理。现有办法依附历史工作负载的拜访模式来加载热数据并驱赶冷数据。
第二种类型利用混合行 / 列扫描来减速查问应用这些技术，能够合成简单的查问以在行存储或列存储上执行，而后组合后果。这对于能够应用基于行的索引扫描和残缺的基于列的扫描执行的 SPJ 查问来说是典型的。咱们引入了基于老本的办法来抉择混合行 / 列拜访门路。
第三种技术利用异构 CPU/GPU 架构来减速 HTAP 工作负载。这些技术别离利用 CPU 的工作并行性和 GPU 的数据并行性来解决 OLTP 和 OLAP。然而，这些技术有利于高 OLAP 吞吐量，同时具备低 OLTP 吞吐量。

5. 比照

Query Optimization in HTAP databases

Part5 资源调度技术

对于 HTAP 数据库，资源调度是指为 OLTP 和 OLAP 工作负载分配资源。以后能够动态控制 OLTP 和 OLAP 工作负载的执行模式，以更好地利用资源。

Resource Scheduling

1. 基于工作负载驱动的调度

Workload-driven Scheduling for HTAP，就是依据 HTAP 工作负载的执行性能进行动静的调度，线程和内存这些依据 OLTP 和 OLAP 的性能需求动态分配资源。相干数据库: SAP HANA。

• Assign more threads to OLTP or OLAP

Psaroudakis, Iraklis, et al. “Task scheduling for highly concurrent analytical and transactional main-memory workloads.” In ADMS, 2013.

举个栗子，第一种形式会调配更多的线程给 OLTP 或者 OLAP，怎么调配呢？会在 Scheduler 里配置一个 Watch-dog 监测器，来监测以后的 Worker，有一些被阻塞的 Worker 就调配多一些 Thread，有一些比拟沉闷的的，就让它继续执行。

• Isolate the workload execution and assign more cache for OLAP

Sirin, Utku, Sandhya Dwarkadas, and Anastasia Ailamaki. “Performance Characterization of HTAP Workloads.” In ICDE, 2021.

如表所示，在第三层 Cache 当中进行一些调度，通过试验能够得悉减少 OLTP 存储资源时，OLAP 的色彩是会变深的，这意味着影响越重大，所以还是倡议在第三层尽量给 OLAP 多调配一些资源。

2. 基于新鲜度驱动的调度

Freshness-driven Scheduling for HTAP

• Switches the execution modes {S1, S2, S3}
• Default S2; When freshness < threshold, jump to S1 or S3

Raza, Aunn, et al. “Adaptive HTAP through elastic resource scheduling.” In SIGMOD, 2020.

3. 技术总结

调度技术有两种类型，工作负载驱动的办法和新鲜度驱动的办法。前者依据执行工作负载的性能调整 OLTP 和 OLAP 工作的并行度。例如，当 CPU 资源被 OLAP 线程饱和时，任务调度器能够在增大 OLTP 线程的同时升高 OLAP 的并行度。后一个切换了 OLTP 和 OLAP 的资源分配和数据交换的执行模式。例如，调度程序独自管制 OLTP 和 OLAP 的执行以实现高吞吐量，而后定期同步数据。一旦数据新鲜度变低，它就会切换到共享 CPU、内存和数据的执行模式。其余与 HTAP 相干的技术，还有新的 HTAP 索引技术和横向扩大技术。

4. 比照

Resource Scheduling in HTAP databases

第一种长处是比拟容易实现，然而新鲜度较低；第二种形式长处是新鲜度高，但来回切换容易导致系统震荡。

Part6 其余相干的 HTAP 技术

这里不开展介绍了，感兴趣能够看看相干的 Paper。

1. Multi-Versioned Indexes for HTAP

• Parallel Binary Tree (P-Tree)

Sun, Yihan, et al. “On supporting efficient snapshot isolation for hybrid workloads with multiversioned indexes.” PVLDB 13(2), 2019.

• Multi-Version Partitioned B-Tree (MV-PBT)

Riegger, Christian, et al. “MV-PBT: multi-version indexing for large datasets and HTAP workloads.” In EDBT, 2020.

2. Adaptive Data Organization for HTAP

• H2O [Alagiannis et al, SIGMOD 2014], Casper [Athanassoulis et al, VLDB 2019]
• Peloton [Arulraj et al, SIGMOD 2016], Proteus [Abebe et al, SIGMOD 2022]

Abebe, Michael, Horatiu Lazu, and Khuzaima Daudjee. Proteus: Autonomous Adaptive Storage for Mixed Workloads. In SIGMOD, 2022.

Part7 HTAP 的基准测试

下一期咱们将介绍针对 HTAP 基准测试的相干停顿，在咱们的第二期学术分享会里，也介绍过来自慕尼黑工业大学（TMU）数据库组的钻研：StoneDB：解读《Benchmarking Hybrid OLTP&OLAP Database Systems》| StoneDB 学术分享会
感兴趣能够返回查看，这篇文章只是其中一种基准测试的办法，想理解还有哪些办法么？欢送关注 StoneDB 公众号，咱们下期见~