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

6次阅读

共计 4611 个字符，预计需要花费 12 分钟才能阅读完成。

分享人：印才华（恒义），阿里云数据库高级技术专家，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、测试数据分析

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