关于数据库:Paper-Reading-深度解读SingleStore在HTAP和云原生的核心技术和创新亮点

分享人：印才华（恒义），阿里云数据库高级技术专家，AnalyticDB PostgreSQL 存储引擎和执行引擎团队研发负责人。

摘要：HTAP & 云原生是现在数据库技术演进的两大热点方向。HTAP 代表既有传统的 HANA Delta RowStore+Main ColumnStore，Oracle In-MemoryColumnStore 等计划，也有像 TiDB，Snowflake Unistore 这样新的技术架构；云原生代表则是以 S3 为低成本主存的 Snowflake，Redshift RA3，提供灵便弹性和 Serverless 能力。SingleStore 则是首次把两者联合起来，基于计算存储拆散的云原生架构，用一份存储提供低成本高性能的 HTAP 能力。本次论文分享围绕 SingleStore 在 HTAP 和云原生的核心技术和翻新亮点开展，同时包含和业界技术比照探讨。

目录：
一、HTAP – 对立数据存储
二、云原生 – 存储和计算拆散
三、总结 – SingleStore 的云原生 HTAP

一、HTAP – 对立数据存储

1、业界的 HTAP 解决方案
2022 发表在 SIGMOD 的这篇论文《HTAP Database: What is New and What is Next》中，介绍了 HTAP 数据库的架构。HTAP 数据库次要分为四局部：

• 主行存储 + 内存中列式存储（Primary Row Store + In-Memory Column Store）
• 分布式行式存储 + 列式存储正本（Distributed Row Store + Column Store Replica）
• 磁盘行式存储 + 分布式列式存储（Disk Row Store + Distributed Column Store）
• 主列存储 + 增量行式存储（Primary Column Store + Delta Row Store）

论文下载地址：https://dl.acm.org/doi/pdf/10…

值得注意的是，在下表中列出的典型数据库，在论文发表后，其中一些数据库有了新的倒退方向：
SingleStore 数据库曾经不再是“分布式行式存储 + 列式存储正本”，而属于第四局部“主列存储 + 增量行式存储”数据云公司 Snowflake 于近期公布 Unistore 存储引擎，属于第二局部“分布式行式存储 + 列式存储正本”

2、SingleStore 的 HTAP 个性

• 一份对立存储

  • In-Memory 行存储
  • On-Disk 列存储
• 主键唯一性束缚
• 二级索引
• 细粒度数据读取
• Row-Level Locking（行级锁）

a. 一份对立存储正本

SingleStore 的解决方案与 HANA 相似。下图列举了 HANA、TiDB、MySQL HeatWave 和 Snowflake 四个数据库的架构，从架构中能够看到，只有 HANA 是一份存储，而 TiDB、MySQL HeatWave 和 Snowflake 都是两份存储。

相干内容参考：

• V. Sikka, et al., Efficient Transaction Processing in SAP HANA Database – The End of a Column Store Myth, in SIGMOD, 2012，地址：https://15799.courses.cs.cmu….
• Dongxu Huang, et al., TiDB: A Raft-based HTAP Database, in VLDB 2020，地址：https://www.vldb.org/pvldb/vo…
• P. Larson, et al., Real-Time Analytical Processing with SQL Server, in VLDB, 2015，地址：https://dl.acm.org/doi/pdf/10…
• T. Lahiri, et al., Oracle Database In-Memory: A Dual Format In-Memory Database, in IEEE, 2015，地址：https://ieeexplore.ieee.org/d…

b. 基于 Skiplist 的内存中行存储和基于 LSM 树的磁盘列存储

如下图所示，右边是基于 Skiplist 的 In-Memory 行式存储架构，左边是基于 LSM 树的磁盘列式存储架构：

• 基于 Skiplist 的 In-Memory 行存储，具备的能力包含：

  • 内存优化
  • MVCC（多版本并发管制）
  • Row-Level Locking（行级锁）
  • Redo Log 反对
  • 提供给用户表 Delta 局部和列存储 Meta 局部

• 基于 LSM 树的 On-Disk 列存储

  • 内存中行存储被 flush 到磁盘造成以列存组织的 segment 文件；
  • segment 文件会被组织到不同的 Sorted Run 中，每个 Sorted Run 有 min/max 值，一个 Sorted Run 中能够蕴含一个或多个 segment 文件，如果蕴含多个 segment 文件，须要确保文件之间的 min/max 不会重叠
  • Sorted Run 的劣势在于，如果扫描过滤列中带有排序列，每个 Sorted Run 只须要拜访一次 segment 文件即可；
  • 当有闲暇资源时，Sorted Run 之间会进行 background merge，确保每个 Sorted Run 中的 segment 文件足够大，实现最佳的扫描过滤成果。

相干参考：
SingleStore 公布的另一篇文章：A. Skidanov, et al., A Column Store Engine for Real-Time Streaming Analytics, in IEEE, 2016，地址：https://www.singlestore.com/r…

c. 列式存储的主键和二级索引

SingleStore 数据库采纳的索引形式，是 2 层构造的组合形式，如下图所示，包含：Data Segment 和 Global Hash index。

• Data Segment

  • 在每个 segment 外部，对索引列建设一个 Inverted Index（倒排索引），每个列存文件都对应一个倒排索引
  • Segment 的 flush 或合并都会生成新的 segment，同时随同生成新的索引

• Global Hash Index

  • 每个 segment 创立时都会对应创立一个 Hash table，记录每个列存文件所在的 segment 以及 offset 值
  • Segment 创立或合并后会创立新的 Hash table

• SingleStore 的索引形式与 Btree 的不同在于：

  • 基于 LSM，Immutable，实用于云存储
  • O(log(N))写放大
  • 二级定址：global hash -> segment-level inverted
  • 主键的唯一性强制执行
  • 二级索引与主键具备雷同的性能

这种索引形式对于高性能点查必不可少。

d. 细粒度 Subsegment 拜访实现无效的点查找

可搜寻的列式存储：

• 搜寻地位由主键或二级索引确定
• 列编码反对 bit-packing、字典编码 (dictionary)、游程长度编码(run-length encoding) 和 LZ4 编码等
• 一个列反对跨 segment 抉择不同编码
• 压缩单位是紫色的 subsegment 层级（见下图）。

e. 行级锁在并发更新 / 删除和后端合并中的利用

从表级锁到行级锁的转变：

• 传统形式中，列存储的更新 / 删除是在表级别（或 delete bitmap 级别），这会引起前端并发更新 / 删除的会话之间的抵触，以及后端合并的抵触
• 基于 Skiplist 的 In-Memory 行式存储原生的反对 level locking，并且列式存储能够利用这一点，首先将须要更新 / 删除的行挪动到行存中（同时在 delete bitmap 中标记），而后只对行存储进行操作
• 因而，利用行式存储实现列式存储的行级锁，让列式存储也能够进行并发更新 / 删除

二、云原生 – 存储和计算拆散

1、业界的云原生解决方案

业界的云原生解决方案中，比拟典型的有以下三个：

• Snowflake：B. Dageville, et al., The Snowflake Elastic Data Warehouse, in SIGMOD, 2016，地址：https://event.cwi.nl/lsde/pap…
• Redshift：N. Armenatzoglou, et al., Amazon Redshift Re-invented, in SIGMOD, 2022，地址：https://assets.amazon.science…
• Aurora：A. Verbitski, et al., Amazon Aurora: Design Considerations for High Throughput CloudNative Relational Databases, in SIGMOD, 2017，地址：https://web.stanford.edu/clas…

2、SingleStore 的云原生架构的个性

• 通过综合利用本地内存 + 本地 SSD+ 基于数据热度的近程云存储以反对 HTAP 工作负载

  • 这里的云存储指 S3/OSS 这类低成本对象存储器

• 为了实现高吞吐低提早的 TP 需要，事务提交门路不会写穿到近程云存储

  • OSS 提早大略是 20 毫秒
• 反对在云存储中的快照和 redo log 存储的疾速 PITR
• 反对多种只读正本（在 SingleStore 称作 workspace，与 Snowflake 的虚构仓库相似），以实现 HTAP 工作负载的隔离和扩大

a. 低提早事务和低成本数据规模

• 低提早：事务写入本地 SSD 磁盘 redo log 以确保持久性，并同步到近程 HA 节点内存中

• 低成本：

  • In-Memory 行式存储会定期 flush 到本地盘的 Segment，并且异步上传到近程云存储，同时本地冷数据会定期移除，以缩小本地空间占用
  • 将行存储 flush 之前的 redo log 密封并上传到远端云存储，本地盘只保留 tail redo log
  • 快照也会定期被整顿并存储到云上，提供 PITR 和只读正本能力以及 redo log
• 基于以上能力能够实现有限的数据规模、低提早事务和高吞吐量剖析

b. PITR 和 Workspace 扩大能力

• 快照指向一堆定期获取的历史 segment 文件
• 每个 partition 的事务一致性点（称为 LP，Logpoint )都会定期写入 redo log

• PITR（Point-in-Time Recovery，工夫点复原）

  • 删除数据库以后的本地状态
  • 从指定 LP 前的第一个快照文件中获取数据
  • 依据这个快照的 redo log 起始点始终重放 log 直到达到 LP
  • 因为快照和 redo log 都在云上存储，因而比传统的备份和复原速度快得多

• Workspace 扩大能力（只读正本）

  • 抉择最初一个快照并重放到最近的一个 LP
  • 同时从 HA 主节点复制 tail log

三、总结：SingleStore 的云原生 HTAP

1、SingleStore 零碎架构

SingleStore 将 HTAP 和云原生很好的联合在一起。下图右边是 SingleStore 的整体架构图，其中包含两种节点：aggregators 节点和负责计算的 leaf 节点，两个 workspace：主 workspace 和只读 workspace，以及对象存储（云存储）：其中蕴含数据文件、logs、快照文件。

2、测试数据分析

在上图左边是两个测试数据表：

• 表 1：TPC-C 测试后果；
• 表 2：TPC-H 测试后果；
• S2DB：SingleStore；
• CDB（Cloud Database）：云 TP 数据库；
• CDW（Cloud Data Warehouse）：云 AP 数仓；

从两个测试后果能够看到，比照同类产品，SingleStore 数据库，在扩大能力和综合解决能力方面有不错的体现。