概要：刚刚结束的2020天猫双11中，MaxCompute交互式分析（Hologres）+实时计算Flink搭建的云原生实时数仓首次在核心数据场景落地，为大数据平台创下一项新纪录。借此之际，我们将陆续推出云原生实时数仓双11实战系列内容。本文将会首次对外公开介绍Hologres的存储引擎，深度剖析其实现原理和核心技术优势。
一、背景介绍
MaxCompute 交互式分析（Hologres）是阿里云自研开发的HSAP（Hybrid Serving/Analytical Processing）服务/分析一体化系统 ，融合了实时服务和分析大数据的场景，全面兼容PostgreSQL协议并与大数据生态无缝打通。它的出现简化了业务的架构，与此同时为业务提供实时做出决策的能力，让大数据发挥出更大的商业价值。关于架构更详细的介绍，请看文末VLDB论文 。
跟传统的大数据和OLAP系统相比，HSAP系统面临下面的挑战：
- 高并发的混合工作负载：HSAP系统需要面对远远超出传统的OLAP系统的并发查询。在实践中，数据服务的并发远远超出OLAP的查询。比如说，我们在现实的应用中见到数据服务需要处理高达每秒钟数千万个查询，这比OLAP查询的并发高出了5个数量级。同时，和OLAP查询相比，数据服务型查询对延迟有着更加苛刻的要求。复杂的混合查询负载对系统的延迟和吞吐有着非常不同的取舍。如何在高效地利用系统的资源同时处理好这些非常不一样的查询，并且保证每个查询的SLO是个巨大的挑战。
- 高吞吐实时数据导入：在处理高并发的查询负载的同时，HSAP系统还需要处理海量的实时数据导入。从传统的OLTP同步过来的数据只是这其中的一小部分，其他还有大量的数据来自日志等没有强事务语意的系统。实时导入的数据量远远超过了传统的HTAP或者OLAP系统。和传统的OLAP系统的另外一个区别是对数据的实时性有着很高的要求，导入的数据需要在秒级甚至亚秒级可见，这样才能保证我们服务和分析结果的时效性。
- 弹性和可扩展性：数据导入和查询负载可能会有突发的高峰，这对HSAP系统提出了很高的弹性和可扩展性的要求。在现实的应用中，我们注意到数据导入峰值能达到是平均的2.5倍，查询的峰值可能达到平均的3倍。数据导入和查询的峰值可能不一定同时出现，这也需要系统有根据不同的峰值做迅速调整的能力。
基于上诉背景，我们自研了一款存储引擎（Storage Engine），主要负责管理和处理数据， 包括创建，查询，更新，和删除（简称 CRUD）数据的方法。存储引擎的设计和实现提供了HSAP场景所需要的高吞吐，高并发，低延迟，弹性化，可扩展性的能力。根据阿里集团业务和云上客户的需求，我们不断创新和打磨，发展到今天，能支持单表PB级存储，并完美支撑2020年天猫双11核心场景千亿个级别的点查询和千万个级别的实时复杂查询 。
下面，我们将会对Hologres底层的存储引擎做详细的介绍，并介绍存储引擎落地Hologres的具体实现原理和技术亮点。
二、数据模型
Hologres存储引擎的基本抽象是分布式的表，为了让系统可扩展，我们需要把表切分为分片（Shard）。 为了更高效地支持JOIN以及多表更新等场景，用户可能需要把几个相关的表存放在一起，为此Hologres引入了表组（Table Group）的概念。分片策略完全一样的一组表就构成了一个表组，同一个表组的所有表有同样数量的分片。用户可以通过“shard_count"来指定表的分片数，通过“distribution_key"来指定分片列。目前我们只支持Hash的分片方式。
表的数据存储格式分为两类，一类是行存表，一类是列存表，格式可以通过“orientation"来指定。
每张表里的记录都有一定的存储顺序，用户可以通过“clustering_key"来指定。如果没有指定排序列，存储引擎会按照插入的顺序自动排序。选择合适的排序列能够大大优化一些查询的性能。
表还可以支持多种索引，目前我们支持了字典索引和位图索引。用户可以通过“dictionary_encoding_columns"和“bitmap_columns"来指定需要索引的列。
下面是一个示例：
这个例子建了LINEITEM 和 ORDERS两个表，由于LINEITEM表还指定了主键（PRIMARY KEY），存储引擎会自动建立索引来保证主键的唯一。用户通过指定“colocate_with“把这两个表放到了同一个表组。这个表组被分成24个分片（由shard_count指定）。 LINEITEM将根据L_ORDERKEY的数据值来分片，而ORDERS将根据O_ORDERKEY的数据值来分片。LINEITEM的L_SHIPINSTRUCT以及ORDERS的O_ORDERSTATUS字段将会创建字典。LINEITEM的L_ORDERKEY, L_LINENUMBER, L_SHIPINSTRUCT字段以及ORDERS的O_ORDERKEY,O_CUSTKEY,O_ORDERSTATUS字段将会建立位图索引。
三、存储引擎架构
1）总体架构
每个分片（Table Group Shard， 简称Shard）构成了一个存储管理和恢复的单元 （Recovery Unit）。上图显示了一个分片的基本架构。一个分片由多个tablet组成，这些tablet会共享一个日志（Write-Ahead Log，WAL）。存储引擎用了Log-Structured Merge （LSM）的技术，所有的新数据都是以append-only的形式插入的。 数据先写到tablet所在的内存表 (MemTable)，积累到一定规模后写入到文件中。当一个数据文件关闭后，里面的内容就不会变了。新的数据以及后续的更新都会写到新的文件。 与传统数据库的B+-tree数据结构相比，LSM减少了随机IO，大幅的提高了写的性能。
当写操作不断进来，每个tablet里会积累出很多文件。当一个tablet里小文件积累到一定数量时，存储引擎会在后台把小文件合并起来 （Compaction），这样系统就不需要同时打开很多文件，能减少使用系统资源，更重要的是合并后， 文件减少了，提高了读的性能。
在DML的功能上，存储引擎提供了单条或者批量的创建，查询，更新，和删除（CRUD操作）访问方法的接口，查询引擎可以通过这些接口访问存储的数据。
2）存储引擎组件
下面是存储引擎几个重要的的组件：
- WAL 和 WAL Manager
WAL Manager是来管理日志文件的。存储引擎用预写式日志(WAL) 来保证数据的原子性和持久性。当CUD操作发生时，存储引擎先写WAL，再写到对应tablet的MemTable中，等到MemTable积累到一定的规模或者到了一定的时间，就会把这个MemTable切换为不可更改的flushing MemTable， 并新开一个 MemTable接收新的写入请求。 而这个不可更改的flushing MemTable就可以刷磁盘，变成不可更改的文件； 当不可更改的文件生成后，数据就可以算持久化。 当系统发生错误崩溃后，系统重启时会去WAL读日志，恢复还没有持久化的数据。 只有当一个日志文件对应的数据都持久化后，WAL Manager才会把这个日志文件删除。
- 文件存储
每个tablet会把数据存在一组文件中，这些文件是存在DFS里 （阿里巴巴盘古或者Apache HDFS ）。 行存文件的存储方式是Sorted String Table（SST） 格式。 列存文件支持两种存储格式： 一种是类似PAX的自研格式， 另外一种是改进版的Apache ORC格式 （在AliORC的基础上针对Hologres的场景做了很多优化）。 这两种列存格式都针对文件扫描的场景做了优化。
- Block Cache (Read Cache)
为了避免每次读数据都用IO到文件中取，存储引擎通过BlockCache把常用和最近用的数据放在内存中，减少不必要的IO，加快读的性能。在同一个节点内，所有的Shard共享一个Block Cache。 Block Cache有两种淘汰策略： LRU （Least Recently Used，最近最少使用） 和 LFU （Least Frequently Used, 最近不常用）。 顾名思义，LRU算法是首先淘汰最长时间未被使用的Block，而LFU是先淘汰一定时间内被访问次数最少的Block。
3）读写原理
Hologres支持两种类型的写入：单分片写入和分布式批量写入。两种类型的写入都是原子的（Atomic Write)，即写入或回滚。单分片写入一次更新一个Shard，但是需要支持极高的写入频率。另一方面，分布式批写用于将大量数据作为单个事务写到多个Shard中的场景，并且通常以低得多的频率执行。
- 单分片写入
如上图所示，WAL管理器在接收到单分片写请求后，（1）为写请求分配一条Log Sequence Number （LSN），这个LSN是由时间戳和递增的序号组成，并且（2）创建一条新的日志，并在文件系统中的持久化这条日志。这条日志包含了恢复写操作所需的信息。在完全保留这条日志后，才向tablet提交写入。之后，（3）我们会在相应tablet的内存表（MemTable) 中执行这个写操作，并使其对新的读请求可见。值得注意的是，不同tablet上的更新可以并行化。当一个MemTable满了以后，（4）将其刷新到文件系统中，并初始化一个新的MemTable。最后，（5）将多个分片文件在后台异步合并（Compaction）。在合并或MemTable刷新结束时，管理tablet的元数据文件将相应更新。 - 分布式批量写入
接收到写入请求的前台节点会将写请求分发到所有相关的分片。这些分片通过两阶段提交机制（Two Phase Commit) 来保证分布式批量写入的写入原子性。 - 多版本读
Hologres支持在tablet中多版本读取数据。读请求的一致性是read-your-writes，即客户端始终能看到自己最新提交的写操作。每个读取请求都包含一个读取时间戳，用于构造读的snapshot LSN。如果有一行数据的LSN大于snapshot LSN的记录， 这行数据就会被过滤掉， 因为他是在读的snapshot产生后才被插入到这个tablet的。
四. Hologres存储引擎技术亮点
1）存储计算分离
存储引擎采取存储计算分离的架构，所有的数据文件存在一个分布式文件系统(DFS, 例如阿里巴巴盘古或者Apache HDFS)的里面。当查询负载变大需要更多的计算资源的时候可以单独扩展计算资源； 当数据量快速增长的时候可以快速单独扩展存储资源。计算节点和存储节点可以独立扩展的架构保证了不需要等待数据的拷贝或者移动就能快速扩展资源； 而且，可以利用DFS存多副本的机制保证数据的高可用性。 这种架构不但极大地简化了运维，而且为系统的稳定性提供了很大的保障。
2）异步执行流程
存储引擎采用了基于事件触发, 非阻塞的纯异步执行架构, 这样能够充分发挥现代CPU多core的处理能力，提高了吞吐量， 支持高并发的写入和查询。这种架构得益于HOS（HoloOS) 框架，HOS在提供高效的异步执行和并发能力的同时，还能自动地做CPU的负载均衡提升系统的利用率。
3）统一的存储
在HSAP场景下，有两类查询模式，一类是简单的点查询（数据服务Serving类场景），另一类是扫描大量数据的复杂查询（分析Analytical类场景）。 当然，也有很多查询是介于两者之间的。这两种查询模式对数据存储提出了不同的要求。行存能够比较高效地支持点查询，而列存在支持大量扫描的查询上有明显的优势。
为了能够支持各种查询模式，统一的实时存储是非常重要的。存储引擎支持行存和列存的存储格式。根据用户的需求，一个tablet可以是行存的存储格式 （适用于Serving的场景）； 也可以是列存的存储格式（适用于Analytical的场景）。 比如，在一个典型HSAP的场景，很多用户会把数据存在列存的存储格式下，便于大规模扫描做分析；与此同时，数据的索引存在行存的存储格式下，便于点查。并通过定义primary key constraint （我们是用行存来实现的）用来防止数据重复·。不管底层用的是行存还是列存，读写的接口是一样的，用户没有感知，只在建表的时候指定即可。
4）读写隔离
存储引擎采用了snapshot read的语意，读数据时采用读开始时的数据状态，不需要数据锁，读操作不会被写操作block住； 当有新的写操作进来的时候，因为写操作是append-only，所有写操作也不会被读操作block住。这样可以很好的支持HSAP的高并发混合工作负载场景。
5）丰富的索引
存储引擎提供了多种索引类型，用于提升查询的效率。一个表可以支持clustered index 和 non-clustered index这两类索引。一个表只能有一个clustered index， 它包含表里所有的列。一个表可以有多个non-clustered indices。在non-clustered indexes里，除了排序用的non-clustered index key外，还有用来找到全行数据的Row Identifier (RID)。 如果clustered index存在， 而且是独特的，clustered index key就是RID； 否则存储引擎会产生一个独特的RID。 为了提高查询的效率，在non-clustered index中还可以有其他的列， 这样在某些查询时，扫一个索引就可以拿到所有的列的值了 （covering index)。
在数据文件内部，存储引擎支持了字典和位图索引。字典可以用来提高处理字符串的效率和提高数据的压缩比，位图索引可以帮助高效地过滤掉不需要的记录。
五. 结语
存储引擎的设计思路和研发方向是为了更好的支持HSAP的场景，能高效的支持高吞吐的实时写入和交互式查询，而且对离线的批量写入做了优化。在写入量和存储量每年都成倍的增长下，Hologres经受住了严苛的考验，完美地度过了多个双11。 “Hologres顶住了5.96亿每秒的实时数据洪峰，单表存储高达2.5PB。基于万亿级数据对外提供多维分析和服务，99.99%的查询可以在80ms以内返回结果”。这组数据充分显示了存储引擎的技术能力， 同时也印证了我们技术架构和实现的优势。
当然，Hologres还是一个新产品，HSAP是个新理念， “今天的最好只是明天的开始”， 我们还在不断地精益求精，聆听客户的反馈，今后会在稳定性，易用性，以及功能和性能上持续提升。
另，后续还会持续推出有关HSAP存储引擎和其他核心系统的技术揭秘，敬请期待！
论文：《Alibaba Hologres: A cloud-Native Service for Hybrid Serving/Analytical Processing》。
作者：江渊，阿里巴巴资深技术专家，在数据库和大数据领域有多年丰富的经验。
