技术干货｜云原生数仓AnalyticDB MySQL实时存储引擎演进之路

【先打一波小广告】

阿里云AnalyticDB MySQL升级为湖仓一体架构，支持高吞吐离线处理和高性能在线分析，可无缝替换CDH/TDH/Databricks/Presto/Spark/Hive等。试用活动（5000ACU时+100GB存储）正在火热申请中，申请链接：https://free.aliyun.com/?searchKey=AnalyticDB%20MySQL，群号：33600023146

背景

AnalyticDB MySQL作为一款实时数仓产品，在传统数仓的能力基础上为了支持低延迟的写入、更新场景，架构上设计了实时存储引擎；用户的写入、更新会以append_only的方式写入实时存储引擎，经过compact之后构建索引以支持复杂的计算场景。

从架构上看，很庆幸SAP HANA、SingleStore有着类似的设计。在线上服务大客户的同时，实时存储引擎也遇到了一些设计、性能上的瓶颈。

• 1.在一些大宽表场景下，单行的更新带来了严重的写放大问题；
• 2.实时存储引擎内存高频换入换出，cache miss高的同时，大量的压缩、解压缩带来cpu瓶颈。

针对以上的几类问题，我们设计了新一代的实时存储引擎：

1. 1.存储格式上，在确定的IO单位上设计行列混存格式，使得单行的IO大小可控
2. 2.学习学术界、工业界对Memory-centric架构的研究，在内存控制上实现了基于Anti-Caching的BufferPool

存储格式

AnalyticDB MySQL实时存储引擎在最初的设计上仍然是一个列存实现，在宽表的更新（游戏业务中留存率计算、零售业务中订单统计等）场景下，IO放大导致的latency问题尤为明显。

RowGroup作为行列混存的一个典型设计，在列存的基础上以行数对齐的方式使得一个group内逻辑行号对齐；这样的设计在宽表场景下出现了比较严重的弊端，当访问一行数据时，磁盘的IO单位变得不可控（列数*block_size）。

针对IO的优化，我们在固定大小的Page上以PAX layout组织数据格式，page头部维护列数、当前记录数以及空闲大小；其次记录每个列起始offset和行粒度的bitmap信息。

每个列会在各个定长minipage中维护（变长的组织在下个小节介绍），同时每个F-minipage的分配上保证cacheline对齐。

基于PAX layout的设计，能够确保每个page的刷盘落到磁盘上都是确定的IO单位；同时同一个列的数据仍然保持在一个minipage上的连续布局，在顺序扫描的场景上仍然能够充分利用cache的能力。

VarlenEntry的设计

针对变长字段的存储，AnalyticDB MySQL用16-byte来存储和表示；前4个字节存储字符串长度，对于超过12个字节的字段会记录4个字节的prefix之后，记录指向V-minipage中对应记录的起始地址。

内存控制

在内存控制的演进上，AnalyticDB MySQL实时存储引擎从最初的LRU-based Cache逐步走向以内存为中心的架构。

与传统数据库的Caching机制不同，AnalyticDB MySQL基于Anti-Caching的设计，将内存作为主存，仅将冷数据淘汰到磁盘上，磁盘的角色更像一个“backup”。学术界对于Anti-Caching的研究也是层出不穷，从H-Store孵化出的商业数据库VoltDB到微软的Siberia in Hekaton都提出了各自的解决方案。

Anti-Caching

Caching和Anti-Caching设计上都是为了解决内存和磁盘速度和容量上的gap。Caching为了加速数据的访问速度缓存了磁盘数据到内存中；Anti-Caching则是为了容量将内存数据“anti-cache”到磁盘上。

Anti-Caching的实现上可以分为以下三类：

• 1.User-space在User-space上实现Anti-Caching目前是比较广泛的，同时能够基于应用语义实现Ad-hoc的优化；另一方面从User-space实现Anti-Caching需要绕过OS，带来了一定的overhead。最早提出Anti-Caching的H-Store，是面向高性能的行存内存数据库，它去掉了传统面向磁盘数据库里的Lock、Buffer Management这类比较重的组件，同时基于LRU来做冷数据的Anti-Caching。H-Store维护了tuple级别的LRU访问，同时淘汰粒度上为了减少overhead，将tuple聚合到block级别。为了维护tuple的状态（磁盘还是内存）H-Store用了一张内存的evict table来存储这些meta信息，整体上来看，为了维护LRU对性能不可避免地带来了一定程度上的overhead。Siberia项目也在Hekaton中采用了Anti-Caching的技术，与H-Store维护LRU不同的是，Siberia采用离线分析logging的方式来为tuple的冷热做分类；同时维护了bloom filter来筛选需要访问磁盘的tuple。Siberia的实现在性能上避免了LRU的开销，但是实时性存在一定欠缺，对于内存并不能做到完全精准的控制上界。
• 
  
• 2.Kernel-spaceVirtual memory management(VMM)是大部分OS都支持的功能，可以作为Anti-Caching的一种简单实现手段，但是缺乏了应用层面的语义，Kernel-space的淘汰可能并不能很准确。大体上有两种实现OS Paging的方式，一个是提前配置好swap分区，OS自动做Paging的换入换出应用程序不需要感知。另一种方式是使用memory-mapped文件，这个在MongoDB、MonetDB中广泛使用。
• 3.Hybrid of user- and kernel-spaceUser-space的方式能够使用应用层的语义优化Ad-hoc的性能；Kernel-space能够针对I/O进行调度同时充分利用硬件特性。AnalyticDB MySQL采用了将user-和kernel-space结合到一起的实现方式。

AnalyticDB MySQL的BufferManager在文件系统之上，通过mmap维护了一个buffer pool，不同大小的page都可以加载到buffer manager中。当一个page被淘汰出buffer manager时，首先保证该page被写回磁盘成功，随后通过madvise中的MADV_DONTNEED标记来通知内核立刻重用相关的物理内存。

Swizzling Pointer
当page被序列化到磁盘后，系统需要通过逻辑ID (PID)来再次访问对应的page。业界通常的设计是用全局的hashtable来维护PID的映射关系，老版本的AnalyticDB MySQL也不例外。

然而这类设计在数据规模较大时，存在明显的性能瓶颈；同时早在08年Harizopoulos在SIGMOD发表的paper中就指出TPC-C场景下BufferManager在指令集层面的开销就占用了34.6%。

为了避免Hash的开销，AnalyticDB MySQL采用了Swizzling Pointer的实现方案，以64bit来存储page的唯一标识；当page在内存中时，头部第一个bit标记为0，其余bit用来表征page的物理地址；当page在磁盘中时，头部第一bit标记为1，后6个bit记录page的size class来计算具体的page大小，剩余的57个bit记录page的PID。

Swizzling Pointer技术上本身带有一定的去中心化属性，避免了全局Hash的开销；同时在新版本的实时存储引擎中，page写盘没有采用传统的lz4、zstd等压缩算法，使得在cpu密集的场景下，性能有大幅的提升。

实时存储引擎性能对比

针对点查以及更新场景，我们选择YCSB测试集来做性能的测试对比。

相比列存版本的实现，新版本的实时引擎存储格式的优化上对IO的控制有着明显的优势；同时内存控制的优化上大大减少了Cache Miss带来的CPU开销。

引用
1OLTP Through the Looking Glass, and What We Found There
2Weaving Relations for Cache Performance
3In-Memory Performance for Big Data
4Cloud-Native Transactions and Analytics in SingleStore