Paper翻译 AnalyticDB Real-time OLAP Database System at Alibaba Cloud

摘要

随着数据在规模和多样性方面的爆炸式增长，OLAP数据库在提供低延时（比如几百毫秒）的实时分析服务方面发挥着越来越重要的作用，尤其是当接入的查询天生就是复杂的和即席的。而且，这些系统被期望能够提供高查询并发和写入吞吐量，以及支持结构化和复杂数据类型（比如，JSON、Vector和文本）上的查询。

本文我们将介绍由阿里巴巴开发的实时OLAP数据库系统AnalyticDB（以下简称ADB）。ADB在可接受的负载下通过异步的方式维护所有的列索引，来提供低延时的复杂即席查询。它的存储引擎针对快速检索结构化和复杂类型的数据扩展了混合行列布局。为了以高并发查询和写入吞吐来处理大规模数据，ADB分离了读写路径。为了进一步降低查询延迟，为了充分利用底层存储和索引的优势，开发了一种新的存储感知SQL优化器和执行引擎。ADB已经成功部署在阿里云上，服务更多的消费者。它能够容纳100万亿行记录，即10PB+大小，同时每秒能够提供10m+的写和100k+的查询，在数百毫秒内完成复杂查询。

1. 引言

ADB是一个提供PB级数据规模高并发、低延时、实时分析的OLAP数据库，运行在阿里云2000+物理节点之上。服务于广泛的阿里云业务场景，包括电子商务、金融、物流、公共交通、气象分析、娱乐等，以及阿里集团内部商业运营。

近期的工作(见文献 [35, 28, 29, 36, 25] )总结了开发一个具备低查询延时、数据实时性、灵活性、低成本、高扩展和高可用性OLAP数据库的主要挑战。相对这些工作，ADB实现的主要挑战在于PB级别的分析负载、万级表数量以及万亿级数据量。

第一个挑战，当今的用户面对比之前更加复杂的分析场景，但是对低查询延时还是有高的期望，用户无能容忍较长的分析时间。然而，ADB的用户来自各个领域，他们的分析需求大不相同而且经常变化，这使得他们多样和复杂的查询难以优化。这些包括了全表扫描、点查、多表关联、多条件组合，虽然构建索引是提高查询最直接的方式，但为每个列构建索引通常不再是有效的。

第二个挑战，新兴的复杂分析趋向于不同类型的查询，同时数据在存储层具备友好的、统一的数据布局。传统的OLAP查询和点查要求不同的数据布局，即分别为列存和行存[34, 12]。此外，我们的用户超过一半的数据是复杂类型，如文本、json串、向量和其他多媒体资源。一个实用的存储结构需要能够提供多个数据类型的快速检索，来提供高效的结构化和复杂类型的数据查询。

第三个挑战，系统在处理低延时实时查询时，还需要处理每秒数百万行在线写入请求。传统的设计( [6, 8, 10, 29, 5])读写在一个进程中，使得数据一旦提交就可以直接读到。然而，这样的设计并不适合我们的场景，为了保证读取性能需要消耗大量的资源从而影响写入性能，反之亦然。所以，一个谨慎的设计需要考虑查询性能、写入性能和数据可见性的权衡。

为了解决以上的挑战，我们在ADB中提出了很多新颖的设计与实现，并作出了如下的贡献：

• 高效的索引管理

ADB内嵌了一个高效的索引引擎，利用两个关键点在可接受的开销范围内提供低延时的方法。第一，在每一个表上所有列建立索引来获得即席复杂查询关键性能。我们进一步提出了一种基于运行时过滤比的索引路径选择机制来避免索引滥用导致性能下降。第二，因为在关键按路径上更新大量索引是被禁止的，索引是在非高峰期异步构建的。我们也维护了一个轻量级排序索引来降低增量数据（索引开始构建后新写入的数据）异步索引构建过程中带来的影响。

• 结构化数据和复杂类型数据的存储结构

我们设计一个底层存储来支持混合行列布局。尤其，我们使用了磁盘快速的顺序读写IO特性，实现在可接受的开销下运行OALP式和点查式工作负载。在存储层面，我们进一步将复杂类型数据和结构化数据整合在一起，来提供复杂类型数据的检索能力。

• 读写分离

为了支持高吞吐写入和低延时查询，我们的系统采用了读写分离的架构，分别通过读节点和写节点提供。这两种类型的节点是相互独立的，可以独自扩容。尤其，在写节点中，将写请求持久化到可靠的分布式存储Pangu中([3])。为了保持数据的实时性，版本验证机制引入到读节点中，使得读节点对写节点上之前写入的数据是可见的。

• 增强的优化器和执行引擎

为了进一步改善查询延时和并发度，我们增强了ADB的优化器和执行引擎，来充分发挥出存储和索引的优势。具体来说，我们提出了一种存储感知的SQL优化机制，它根据存储的特性，并为成本优化器的基数估计进行有效的实时采样，来生成最佳执行计划。此外，我们还为混合存储设计了高性能向量执行引擎来提升计算密集型的查询分析。

本论文其他章节安排如下标题所示。

2. 相关工作

ADB是从零构建的基于云平台的大规模、实时分析系统。本章节，将ADB和其他系统做一个对比。

• OLTP数据库

针对OLTP数据库，例如MySQL[6]、PostgreSQL[8]被设计用来支持事务查询，同时也考虑一行或多行的点查。因此，在OLTP数据库中的存储引擎是面向行的，并且通过构建B+树索引来提高查询性能。然而，行存并不适合分析查询，当查询只要求返回部分列时，行存会造成读写放大。而且，OLTP数据库通常在写入路径中更新索引比较活跃，这个操作代价很高，会影响写入吞吐和查询延时。

• OLAP数据库

为了提高分析查询的效率，开发了许多OLAP数据库像Vertica[29]，Teradata DB[10]和Greenplum[5]。Vertica使用projection提高查询性能，取代了在列上构建常规索引，仅仅保存min/max信息，由于修剪效率较低而导致高延迟。Teradata DB和Greenplum采用列式存储，用户可以设置索引列。然而，它们有两个主要的局限：一是写路径中修改列索引，针对所有列索引来说是禁止的。二是列存针对点查需要大量随机IO。

• 大数据系统

随着MR模型[18]的出现，像Hive[35]、SparkSQL[37, 13]等批处理引擎，在多个机器上处理大数据变得很流行。但是，这些查询的执行是离线的，整个执行持续分钟或小时级别，并不适合实时查询。Impala[28]采用pipeline模型和列存将离线查询转为交互式查询，将一般查询延时降低到秒级。但是，Impala没有列索引，只有min/max统计信息，也不能处理复杂查询。

• 实时OLAP系统

最近，实时OLAP系统包括Druid [36]和Pinot [25]都采用了列存。Druid在纬度列上，Pinot在所有列上都构建了基于位图的倒排索引。如果Druid上的查询不在纬度列上，会产生更高的延时。它们在写流程中都需要更新索引，影响写入性能。同时，缺乏对UPDATE、JOIN和DELETE的支持。由于是列存的，点查的效率也不高。

• 云分析服务

近期又出现许多云服务，比如Amazon Redshift和Google BigQuery。其中，Amazon Redshift是完全托管的云数据库服务，采用列式存储和MPP结构将查询分布到多个节点，具有两个或多个计算节点，通过leader节点来协调。ADB与此相比，ADB引入读写分离的架构，具有多个读写节点且是独立的，并且有一系列协调器节点与它们通信。Google BigQuery是Google核心技术（Dremel [31]）的外部实现，采用高存储率的列式存储、树形拓扑结构分发查询、秒级内跨数千个节点聚合结果。和它不同的是，ADB采用了索引引擎和DAG执行框架。

3. 系统设计

作为一个云数据库，ADB运行在Apsara（飞天）上，它是阿里云自2009年开始开发的大型通用高可靠性计算基础设施。Apsara管理数万物理机器的所有资源，维护多个阿里云服务，包括检索、计算和存储。ADB采用了Apsara两个核心组件，分别为Pangu(盘古，可靠的分布式存储系统)和Fuxi（伏羲，资源管理和作业调度），如下图一所示。本章节，我们将给出ADB的关键技术选型，包括数据模型和系统架构。

图1 ADB架构

3.1 数据模型和查询语言

ADB遵循标准的关系数据模型，即数据记录有固定的模式。主流的复杂类型，像JSON、Vector和Text等，需要支持来满足实际应用日益增长的分析需求。ADB支持ANSI SQL 2003，以及增强了一些额外功能，比如分区规范、复杂类型的数据操作。

3.2 表分区

在ADB中，每张表都有两级分区，即一级分区和二级分区。如下一个DDL SQL样例所示，创建一个有两级分区的表。一级分区在字段id上有50个分区，二级分区在字段dob上有12个分区。

CREATE TABLE db_name.table_name (
	id int,
	city varchar,
	dob date,
	primary key (id)
)
PARTITION BY HASH KEY(id) -- 散列到不同节点cluster by
PARTITION NUM 50
SUBPARTITION BY LIST (dob) -- 节点内部的划分 partition by
SUBPARTITION OPTIONS (available_partition_num = 12);

一级分区基于用户指定的列进行hash，因此所有行被分布到所有一级分区中来最大化并发度。实际上，任何高基数的列（NDV大）都可以作为分区列，这样可以使每个分区均衡。同时，用户还可以设置二级分区（可选的），二级分区是一个列表分区，设置了最大分区数为12，用于自动数据保存和回收。通常，表示时间间隔的字段（如，天、周、月）作为二级分区字段，可以将同一个时间间隔的数据分到同一个分区。一旦分区的数量超过指定阈值，就会自动将最旧的分区剔除。

3.3 总体架构

如图1所示的系统架构，ADB中节点共有三种类型，协调器、写节点和读节点。客户端通过JDBC/ODBC连接发送请求（读写），协调器负责接收并分发到相应的读写节点。写节点负责处理写请求（如INSERT、DELETE、UPDATE）和将SQL描述持久化到Pangu。读节点负责处理查询请求（如SELECT）。在这种方式下，读写节点是相互分离的。Fuxi将利用所有节点中可利用的资源为异步任务执行提供计算worker，此外ADB的pipeline执行引擎（如下图2所示）就运行在计算worker上。数据以列block为单位（称为page）从存储流向客户端。所有数据的处理都在内存中，通过网络在不同阶段之间进行pipeline连接。这个pipeline工作流以高吞吐和低延时提供用户的复杂查询。

图2 pipeline执行引擎

3.4 读写分离

传统的OLAP将读写合在一起，即一个数据库实例在同一个执行流程中处理所有请求，不区分读还是写。因此，所有并发的请求共享一个资源池会相互影响。当读写并发都很高的情况下，由于资源竞争会导致较低的性能。为了解决这个问题，我们提出了一个读写分离的架构。写节点负责写，读节点负责读，读写节点相互隔离，使得读写完全在不同流程中执行。

3.4.1 高吞吐写

write节点中选择一个作为master节点，其他作为worker节点，它们之间通过Zookeeper[24]的锁服务相互协调。当写节点初次启动，master会配置表分区到各个worker上。基于配置，coordinators会将写请求分发到相应的workers。当一个写请求到达，coordinator会解析SQL，识别为写入操作，然后派发到相应的write节点。针对接收到的SQL，每个write节点作为memory buffer，然后周期性地写入日志到Pangu（跟传统数据库日志写入线程类似）。一旦buffer完成flush，这个node就会返回一个版本号（log seq num）给coordinators，然后针对每个提交的写入返回用户一个成功的消息。

3.4.2 实时读

每个读取节点都由协调器分配若干个分区，其中具有相同哈希值的分区是放置在一个节点中。如下图3所示：

图3 读节点中的数据放置

分区在读节点中的位置，利用存储感知优化器，这种布局有助于节省数据重新分布的成本超过80%，这是从我们生产服务中测量的。而且，为了并发和可靠性，读节点是可以被复制的。每个读节点从Pangu加载初始分区，然后周期性地从相应的写节点拉取后续的更新。然后，将更新应用在本地数据副本，这些副本不会写回Pangu中。我们选择持续从写节点拉取数据而不是Pangu，是为了减少同步的延迟。因此，写节点作为缓存提供不同读节点副本并发拉取更新数据。

由于近期写入的数据读节点需要远程拉取，因此读节点给用户提供两种可见性级别：一是实时读，数据写入后可以立即读到；二是有界过时读，在一定的延时内数据是可见的。为了保证查询的低延时，默认采用第二种方式，在大部分OLAP场景下是可以接受的。对于实时性要求高的用户，可以开启实时读，不过可能引发读写节点数据同步的问题。

为了解决这个问题，我们采用了版本验证机制。具体来说，在写节点中每个一级分区都有它自己的版本。在分区上多个写入请求被flush后，写节点将增加分区的版本并附加到响应消息中。如下图4所示，拿读写请求流程作为例子。

图4 实时读流程

一个用户写入一条记录到表里（步骤1和2），立刻下发查询检索数据。当协调器收到这个请求，将查询和上一次flush响应（有界延时读或从写节点实时拉取，步骤3）的版本（V1）缓存都发送到相应的读节点（步骤4）。针对每个分区，读节点将本地版本（标记为V2）与V1版本比较。如果版本V1没有V2大，则读取节点直接执行查询操作。否则，读节点必须从写节点拉取最新的数据（步骤5），优先更新本地副本。

遵循上述的操作，针对实时查询，我们可以确保读写节点之间数据的可见性。然而，如果读节点向写节点发送拉取请求，需要等待所需的数据，这个延迟将会比较高。我们这里进行了优化，将读节点拉取改为了写节点推送。当写节点监测到有新写入的数据时，将主动附上版本号推送给相应的读节点。

3.4.3 可靠性和可扩展性

ADB为读写节点提供了高可靠性。针对写节点，当worker失败时，master会平滑地将该worker上的分区分发给其他可用的写节点。当master失败时，会从活跃的workers中选举出一个新的master。

针对读节点，用户可以指定副本因子（默认为2），同一个节点的不同副本可以部署在不同的物理机器上。当一个读节点在执行查询时失败，协调器会自动地重新发送查询给其他副本，这对用户来说是透明的。注意当读节点从写节点拉取数据时出现失败，读节点是不会被阻塞的。如果读节点不能访问写节点，它们将直接从Pangu（更高的延迟）中读取数据，继续执行查询（步骤6）。

ADB也可以保证读写节点的高可扩展性。当加入一个新的写节点时，master将会调整表分区的位置来保证负载均衡。新的位置被更新到zookeeper，然后协调器会根据新的信息来发送后续的写请求。读节点的扩展是类似的，除了表分区位置是通过coordinators调整的。

3.5 集群管理

ADB的集群管理支持多租户，也就是说在一个集群中有多个ADB实力。我们设计并实现了一个集群管理组件Gallardo，利用CGroup技术隔离不同ADB的实例的资源（CPU、内存、网络带宽），来保证它们的稳定性。当一个新的ADB被创建，Gallardo会分配它所需要的资源。在分配期间，Gallardo会谨慎地将不同的角色（协调器、写节点和读节点）和读节点副本放置到不同的物理机器上，来遵循可靠性的要求。注意这里Gallardo和Fuxi是不冲突的，Gallardo负责为不同ADB实例分配和隔离资源，而Fuxi是为计算任务使用所有ADB实例的可用资源。

4. 存储

ADB的存储模型支持结构化数据和其他复杂数据类型，比如JSON和向量。我们首先讨论混合行列存储结构，其次是它快速和强大的索引引擎。

4.1 物理数据结构

本章节首先描述ADB数据结构和元数据结构，然后说明数据是如何管理的。

4.1.1 混合行列存储

ADB设计的一个主要目标是支持OLAP和精确查询。OLAP的查询一般会涉及一个宽表中的部分列，列存比较适合这样的查询，由于它高效的数据压缩和IO减少。但对于精确查询是比较困难的，因为这类查询需要返回一个或多个整行。行存在精确查询中比较适合，但是针对OLAP查询访问成本增大了很多。为了解决这个问题，我们提出了行列混合存储布局，如下图5所示。

图5 包含元数据和索引的混合行列存储数据格式

在这个设计中，每个表分区的数据都维护在一个单一的文件中（称为detail file），内部分为多个行组，每个行组包含固定行数（生产环境默认为30000，是可配置的）。在一个行组中，同一列的所有值是连续的且分组在一个数据块（data block）中，所有的数据块按序存储。数据块是ADB中基本的操作单元（拉取和缓存），有助于获得较高的压缩比来节省存储空间。像这样的混合设计能够在可接受的工作负载下，平衡OLAP和精确查询[12, 20, 34]。和列存类似，混合存储也会根据列来划分数据，有助于ADB的OLAP查询。虽然一整个列属于不同行组的多个数据块中，仅仅有一小部分顺序检索要求获取所有数据。通过我们对真实ADB服务的观察，这个负载占比小于整个查询延时的5%。针对精确查询，为了保留好的性能，将一行的所有列存储在同一个行组当中。行集合只涉及短距离顺序查找[23]，而不是列存中的跨段查找。

复杂类型数据。混合行列存储适合较小的列，例如数值型和短字符类型，但不适合复杂类型数据（比如JSON和向量），因为这些数据大小可变和通常都比较大。如果把这些行分为固定数量的行组会导致不可预期的大数据块。为了解决这个问题，针对复杂类型数据设计了一个固定大小的存储模型。利用另外一个级别的块，名为FBlock，固定大小为32KB。特别地，一个含有30000行的数据块，会进一步拆分为多个FBlocks，并存储指向这些FBlocks的指针。在这个方式下，数据块还是固定行数，所有的FBlocks都存在一个单独的文件中，如下图6所示：

图6 复杂类型数据格式

然而，一个FBlock中包含的行数各有不同，少于一行（即部分行）到多行。为了支持快速检索，我们在datablock中为每个FBlock维护了一个block entry，每个entry包含两个标识符，即对应FBlock的起始行和结束行。一行被切分为多个连续的FBlocks。图中，FBlock1和FBlock2分别存储0-99行和99-200行，同时第99行被分为两个FBlock。为了访问到该行，需要首先从数据块中扫描block entrie定位到FBlock1和FBlock2，然后提取和合并其中的部分行。

4.1.2 元数据

在detail文件中每个列都有自己的元数据信息，用于加速在这个列上进行海量数据的检索。这些为每个列单独存储元数据的文件，称为detail meta文件（如图六所示），它的大小非常小，一般小于1MB，由于频繁访问一般缓存在内存中。每列的元数据由四个部分组成：

• header: 包含一个版本号和detail meta文件总大小；
• summary：包含查询优化需要的统计信息，如行数、NULL数量、NDV、sum、max和min；
• dictionary：对于ndv数较低的列，将会自动开启字典功能，来节省空间。还包含在文件中的偏移量和长度用于快速访问；
• block map：持有每个data block的entry，包含在文件中的偏移量和长度用于快速访问。

4.1.3 数据操作

ADB底层存储采用Lamda架构，如图7所示，包含基线数据和增量数据。基线数据存储历史数据，包括索引和行列数据。增量数据保持新写入的数据，不包含全部索引只是一个简单的排序索引。增量数据仅仅在读节点上出现，当它们从写节点拉取并重放日志的时候。基线和增量数据遵循相同的数据格式和和元数据格式。

图7 在存储之上的操作和查询执行

查询执行**。为了支持update我们采用bit-set来记录要删除数据的row-ids。通过Copy-on-Write技术来实现MVCC（多版本并发控制）[15]。当一行数据被更新或删除时，一个带有版本的bit-set快照保存在内存map中用于后续的查询。这个用于delete的bit-set被划分为多个小的经过压缩的segment，使得快照可以共享那些没有变化的segment，提高空间利用率。此外，新版本的快照被创建，一旦没有查询，旧版本的快照将被删除。算法1、2、3描述了在基线数据和增量数据上执行INSERT、DELETE和过滤查询，流程见图七。为了查询，首先根据给定的版本号，来获取相应的基线数据和增量数据的删除标记位bit-set快照。基线数据可以从全量索引中获取限定的row-ids，增量数据可以从排序索引中获取限定的row-ids。最后，我们会从bit-set中过滤出要删除的行获得最后的结果。

算法一 INSERT(SQL, version)
--------------------------------------------------
输入：SQL语句和版本号
//从sql中解析多个列的值values
values = parse(SQL);
//将values追加到增量数据的尾部
row_id = incremental_data.append(values);
//在delete_bits新增一个新的bit
delete_bitset[row_id] = 0;
//为delete_bitset创建快照
delete_bit_snap = create_snap(delete_bitset);
//以快照版本作为key，存入snap_map中
snap_map.put(version, delete_bitset_snap);

算法二 DELETE(SQL, version)
--------------------------------------------------
输入：SQL语句和版本号
//根据where条件检索row_ids
row_ids = search(baseline_data, incremental_data, sql.where)
//遍历delete_bitset,将命中的row_ids剔除
for row_id in row_ids do
    delete_bitset[row_id] = 1;
//为delete_bitset创建快照
delete_bit_snap = create_snap(delete_bitset);
//以快照版本作为key，存入snap_map中
snap_map.put(version, delete_bitset_snap);

算法三 FILTER(conditions, version)
--------------------------------------------------
输入：过滤条件和版本号
输出：命中的row_ids
delete_bitset_snap = snap_map.get(version);
row_ids = search(baseline_data, incremental_data, conditions);
return minus(row_ids, delete_bitset_snap);

基线数据和增量数据合并。随着新数据持续写入，在increment_data上的检索会变得很慢。因此，build进程异步启动来讲增量数据合并到基线数据。在build过程中，忽略删除的数据和创建新的索引。如图8所示，合并的过程如下：

图8 基线和增量数据合并处理

当合并开始，增量数据置为不可变，创建另外一个新的增量数据实例，来接收新数据。在数据合并完成之前，所有查询都基于基线数据、老增量数据和新增量数据。一旦新版本的基线数据合并完成，老的基线数据和老的增量数据将被安全地移除。此时，后续的查询都是基于新的基线数据和新的增量数据。

4.2 索引管理

在所有数据库中，索引是很关键的组件，可以用来提高查询性能。然而，已有的一些索引方案，并不能很好地满足OLAP的查询需求。例如，由于节点切分，B+树的更新代价高昂，因此只能在精心选择的列上使用。像Druid这样的系统，采用基于位图的倒排索引，在更多的列上构建，但是只适用于简单类型（如string）。越来越多的查询需求需要支持复杂数据类型（如json、vector、text等），这些数据类型的索引也需要支持创建。而且，大部分系统都是在写入过程中[8,6,5,10]构建索引，会极大地限制写入性能。

因此，我们设计并实现了一个索引引擎，支持结构化和复杂数据类型的数据创建索引，并且不影响写入性能。该引擎可以在所有列上建立索引，全部支持ad-hoc查询，并且将索引构建从写入流程中移出来。许多复杂的设计，就是为了最小化存储负载和最大化性能。

4.2.1 索引过滤

在一个分区中每个列创建一个倒排索引，存储在一个单独的文件中。倒排索引中，key是字段原始值，value为相应行号列表。根据4.1.1章节，我们可以很容易通过行号定位到一行，因为每个行组的数量是固定的。

基于每个列上的索引，ADB可以支持高性能的ad-hoc查询。图9给了一个SQL过滤的例子，过滤条件包含结构化数据和复杂类型数据。对于每个条件，索引引擎基于相应的索引进行过滤获取结果集（也就是row ids）。最后，所有的row ids通过交、并、差的操作，合并成最终的结果。大部分数据库都是采用二路归并来合并结果，该方式需要耗费大量内存且并发度低。为了减轻影响，我们采用了K路归并来合并数据，来达到在大数据集下的亚秒级查询延迟。

图9 全字段索引查询

索引路径选择。然而，在所有列上的索引过度使用反而会降低查询的性能。例如，有A and B这个条件，A的过滤的结果远小于B过滤的结果，则应该先过滤A再过滤B，而不是把A和B结果都过滤出来再合并。为了解决这个问题，我们提出了一个基于运行时过滤选择率索引路径选择机制，通过评估每个条件的选择率来决定是否采用该索引，这个选择率=根据索引限定的行数/总行数。ADB选择索引来过滤条件是根据索引选择率降序来排的。如果所有的处理条件（比率相乘）的联合过滤比足够小（比如总行数1%），这个过程停止和之前获取的结果进行K路合并。后续的条件直接基于row ids过滤而不是索引。

4.2.2 复杂数据类型索引

JSON。当插入一个json对象，会将层级结构的json属性扁平化为多个字段，为每个字段构建倒排索引。例如，给定一个json对象{id, product_name, properties{color, size}}，扁平化后的字段为id, product_name, properties.color, properties.size，为每一个列构建一个索引。我们将采用PForDelta算法[39]来压缩每个索引下的row ids。而且，一个json对象可能包含上千个属性（也就是上千个索引）。我们将一个json对象的所有索引打包在一个单独的文件中，来限制文件的数量。利用这个索引，ADB能够直接以json格式的谓词条件来获取json对象，比起从磁盘上直接读取和解析json数据块要更加高效。

Full-Text。针对全文数据，ADB通过存储更多的信息来扩展倒排索引，包括词频、doc和term的映射。我们使用TF/IDF公式打分来计算查询和文本之间的相似度，只有那些排名在设置阈值前面的记录才会返回给用户。

Vector Data。特征向量是计算视觉任务中常见的组件，如物体和场景识别、机器学习中用到的高维向量，是通过训练的AI模型从图片中提出来的。两个物体之间的相似度是通过计算特征向量距离来度量的。在向量数据查询中，用户要求最近邻搜索（NNS），为了能够找到数据库中和该查询点最相近的对象。（部分内容跳过…）

4.2.3 索引空间节省

我们采用自适应方式来减少索引的大小。针对索引中的每个key_value, 根据空间消耗来选择使用bitmap还是integer数组来存储value。例如，索引的值为[1, 2, 8, 12],bitmap（2个字节）比起integer数组（4个字节）要好。但如果是[1, 12, 35, 67]，integer数组（4个字节）要比bitmap（9个字节）要好。通过采用这种方式，整个索引大小可以减少50%。我么也可以允许关闭指定列的索引，通过延时来换取空间。

4.2.4 异步索引构建

ADB需要支持每秒上千万写请求，因此不可以在写请求的过程中创建索引。换种方式，就是要索引引擎异步构建索引。回忆一下3.4.1章节，在写请求结束后，写节点会将写日志flush到pangu。索引引擎会周期性为新写入的数据（increment data）构建倒排索引，之后在后台把它们合并到存在的全量索引中。这种异步的方式完全屏蔽了从用户侧构建的工作负载，保证了查询性能和写入吞吐。构建和合并索引会被翻译为许多的Map-Reduce任务，在借助于Fuxi[38]，在非高峰期并发地、自动地执行这些任务，达到可接受的工作负载。

表1给出了ADB和Greenplum（一个列存的OLAP系统）在1 TB数据上构建全列索引的对比。我们可以看到ADB只使用了0.66 TB的额外空间存储索引，而Greenplum使用了2.17 TB的大小。虽然ADB构建索引花了双倍的时间，但异步的处理方式并不会影响在线读写性能。如表1所示，在Greenplumn中实时INSERT 1 TB数据时间大约是ADB的4倍。因此，ADB为了ad-hoc查询的较大性能提升（第6章节具体说明），在交换数据过程中产生了一些开销。

	ADB	GP
索引空间	0.66 TB	2.71 TB
索引构建时间	1 h	0.5 h
是否异步	是	否
数据实时INSERT时间	4015 s	20910 s

表1 ADB和GP在1TB数据上构建全列索引的对比

4.2.5 增量数据索引

采用异步索引的方式会带来一定的性能差距，在新索引上线之前，增量数据缺乏索引的支持，因此需要scan数据提供高延迟的查询。为了取消这个差距，索引引擎在读节点上为增量数据独立构建sorted index。这个sorted index在数据块中其实就是一个row id的数组。如图10所示，一个升序排列的索引，第i个元素Ti表示在数据块中第i小的值在行Ti。

图10 增量数据的排序索引

因此，在增量数据上的查找转为了二分查找，复杂度从O(n)将O(logn)。为了保存sorted index，我们在每个数据块中开辟了附加的header信息。由于一个数据块的行数为30000行，因此行号为短整型。header（排序索引）的大小，大约是60 KB。在flush数据之前，索引引擎构建sorted index，并dump到文件的header中。这个构建过程在读节点本地执行，是非常轻量的。

4.2.6 条件索引缓存

传统数据库在内存中缓存索引（粒度为index page）是为了减少磁盘IO。查询条件缓存将查询条件（例如id<23)作为key，查询结果作为值（即row ids)。因此，可以完全避免在index page上重复过滤。当查询条件缓存失效了，我们可以在index page缓存中访问索引来计算查询结果。

在采用两层缓存策略中存在一个挑战就是用户条件持续变化且相差很大，导致缓存频繁失效。然而，根据我们的观察，对整个缓存的有效性影响不是很大。一个是大查询结果的条件比较少且变化不频繁（比如where city=’Beijing’），所以它们的缓存能够持续较长时间；第二个小查询结果的条件比较多且变化较大（比如where userid=’xxx’)，但是它们的查询结果重新构建，代价较小。总之，计算成本较高的结果可以很好地被缓存来节省资源，轻量级的查询重新计算不会带来太多额外开销。可以保证索引缓存的有效性。

5. 优化器和执行引擎

本章节，我们将讨论优化器和执行引擎采用各种新式的优化方式，来进一步优化查询延时和并发。

5.1 优化器

ADB优化器提供了CBO（基于成本的优化）和RBO（基于规则的优化），目标是实时在线分析，具备低延时和高并发。它包含了大量的关系代数转换规则，保证总是能够选择到较优的计划。这些规则包括：

• 基础优化规则（如裁剪、下推/合并、重复消除、常量折叠/谓词派生）；
• 针对不同JOIN的probe优化规则（广播HASH JOIN、重分布HASH JOIN、嵌套循环Index JOIN），Aggregate，Join-Reorder，GroupBy下推，Exchage下推，SortBy下推等；
• 高级优化规则（如Common Table Expresssion，即with clause的使用）。

除了上述提到的通用RBO和CBO规则，还开发了两个关键特性：存储感知优化和高效实时采样。

5.1.1 存储感知计划优化

Predicate下推。谓词（即条件）为了将SQL中的关系代数计算抽取出来，充分利用底层存储的特性，将查询计划转为两个等价的部分（分别针对计算层和存储层）。因为在原始的查询计划中，没有清晰的边界来支持这种操作，完全依赖于优化器。在许多分布式数据库中已经实现谓词下推，但主要集中在单列的AND操作上。他们并没有考虑其他通用操作，比如function和join，这些一般在计算层实现。这是因为许多已有的数据库并没有为存储层提供接口来注册高级的能力。因此，存储仅仅能够做到单个列或列组合的过滤。

ADB引入STARS（策略替换规则）框架[30, 14]，来扩展优化器支持谓词下推，如图11所示。STARS针对查询执行提供了高级的、声明式的、独立于实现的合法性策略。每个STAR定义了一系列高级的构建，来自低级的数据库操作或其他STARS。基于STARs框架，ADB从关系代数的维度，抽象出异构数据源的能力，将存储能力描述为可用的关系代数。另外，ADB也会提供成本计算。执行谓词下推，不仅仅依赖于存储的能力，也要考虑关系代数的能力成本。在动态规划的过程中，成本和执行能力都会作为参考因素，避免盲目的谓词下推带来性能衰减。这在低延时和高并发的环境中，是非常重要的。在优化器完成初始的分布式执行计划之后，作用在目标数据源上的关系代数算子会通过动态编程的方式进行封装，转为相应的存储API的调用。

图11 ADB的STARS框架

Join下推。数据重新分布是分布式数据库执行计划的另一个重要方面。这个不同于传统数据库，主要是因为物理数据分布特征和关系代数的逻辑语义之间的不匹配。例如，SQL语句SELECT T.tid, count(*) FROM T JOIN S ON T.sid = S.sid GROUP BY T.tid，T和S基于同一个字段来hash，分区放置在同一个读节点上（如3.4.2章节）。ADB能够选择到最好的JOIN下推策略。避免数据的重新分布式是非常重要的，因为重分布的代价非常高，比如涉及序列化、反序列化以及网络负载等。如果T和S不是基于同一个字段hash，则ADB会清楚的知道shuffle哪个表是最高效的，通过获取T和S底层存储的大小。正如上面提到的，优化器扩展和计算了所有可能执行计划的成本，ADB通过这种方式来选择适合不同数据量下的，适合于数据特点的最优执行计划。

基于Index的Join和Aggregation。在所有列上构建索引，可以减少构建hash索引的开销，通过查找已存在的索引来取代。当调整Join的顺序后，优化器可以避免构建Bushy Tree，倾向于Left Deep Tree，这样ADB可以更好地使用索引，如图12所示。而且，我们也会下推谓词和聚合。例如，count的聚合操作可以直接从索引返回，filter也可以在索引上直接计算。所有的这些优化，都可以降低查询的延时，来提升集群利用率，使得ADB更容易支持高并发。

图12 Join Order优化

5.1.2 高效实时采样

成本估算是CBO的基石，同时又取决于基数估算，基数估算重度依赖可获得的统计信息。在现代数据库中，统计信息的收集和使用非常有限，使得数据倾斜和相关性得不到很好的处理，从而导致获取次优的查询计划。另外，我们的系统设计目标之一是查询（简单查询或复杂查询）短时间响应，传统的做法（实时统计、谓词选择率、执行结果反馈）由于负载和复杂度显得不太适合。取而代之，我们实现了一个基于高效采样的cardinality估算框架。我们的框架，充分利用了ADB高性能存储引擎提供的高效数据访问，以及通过丰富的索引类型、缓存和优化计算进行估算。在优化的时候，优化器通过框架API发送采样谓词请求（单个或多个，取决于优化器）给存储引擎。存储引擎通过适当的索引或缓存来访问采样数据，通过优化后的计算路径来估算谓词，返回基数结果。优化器利用采样的基数结果来估算候选的执行计划，选择其中最优的一个。

虽然我们的框架可以很高效地估算基数，但是进一步的优化可以减少负载，尤其是那些关键的业务场景，需要亚秒级查询。这些优化包含了缓存预先采样（基数估算）、优化的采样算法、改进的derived基数等等。通过采样这些方式，我们的cardinality估算框架在估算的时候，可以降低负载以及提供更高的估算准确度。

5.2 执行引擎

ADB提供了一个通用的、管道模型的执行引擎，以及在这个引擎之上的DAG[27]（有向无环图）执行框架。因此，它适合于小规模（低延时）和大规模（高吞吐）的workloads。ADB的执行引擎是面向列的，充分利用了底层存储引擎将数据按列进行聚集的特点。与基于行存的执行引擎相比，向量化引擎是cache友好的，不会load一些没有必要的数据到内存。

像许多OLAP系统，CodeGen[32]被用于提升CPU密集型操作的执行性能。ADB的CodeGen是基于ANTLR ASM，为Expression Tree动态生成代码。这个CodeGen引擎也会考虑运行时因素，允许我们在任务级别的粒度上，充分利用异构硬件的能力。例如，在向量化引擎中，大部分数据类型为int或double。在异构集群中，有支持AVX-512指令集的CPU，我们能够使用SIMD指令生成字节码来提升性能。而且，通过固化存储引擎和执行引擎之间内部数据表现形式，这样ADB能够在序列化后的二进制数据上直接操作而不是JAVA对象，这样有助于减少序列化和反序列化的开销，当shuffle大量数据时，可以节省20%的时间。

6. 实验评估

本章节，我们将从实际workload和TPC-H基准测试[11]来评估ADB，并给出不同查询类型和写入能力下的ADB性能。

6.1 实验设置

实验集群由8台物理机构成，每台机器配置如下表2所示。集群上，启动4个coordinators，4个write节点，32个read节点。

配置	参数说明
CPU	Intel Xeon Platinum 8163 CPU(@2.50GHz)
RAM	300GB MEM
DISK	3TB SSD
NIC	10Gbps Ethernet network

表2 物理机配置

类型	查询语句
Full Scan (Q1)	SELECT * FROM orders ORDER BY o_trade_time LIMIT 10
Point Lookup (Q2)	SELECT * FROM orders WHERE o_trade_time BETWEEN ‘2018-11-13 15:15:21’ AND ‘2018-11-13 16:15:21’ AND o_trade_prize BETWEEN 50 AND 60 AND o_seller_id=9999 LIMIT 1000
Multi-table Join(Q3)	SELECT o_seller_id, SUM(o_trade_prize) AS c FROM orders JOIN users ON orders.o_user_id = users.u_id WHERE u_age=10 AND o_trade_time BETWEEN ‘2018-11-13 15:15:2’ AND ‘2018-11-13 16:15:21’ GROUP BY o_seller_id ORDER BY c DESC LIMIT 10

表3 三种查询评估

实际workload。在我们的生产环境中，使用了两张实际的表。第一个表示users表，使用user_id作为主键，有64个一级分区，没有分二级分区；第二个表为orders表，使用order_id作为主键，有64个一级分区，10个二级分区。这两张表通过user_id进行关联。通过表3给出三种查询进行测试，三种查询都包含o_trade_time，是一个timestamp的类型。由于Druid必须使用timestamp的字段作为分区键。没有指定这个分区键，查询会更慢[36]。

与其他系统对比。我们将ADB和4个OLAP系统进行对比。PrestoDB[9]，SparkSQL[13]，Druid[36]和GreenPlum[5]。GreenPlum在所有列上建立索引；Druid不支持在数值类型列上建立索引；PrestoDB和SparkSQL采用ORC文件存储数据，任意列上都没有索引。所有系统都运行在默认配置上，其中Druid不支持复杂查询如Join，是TPC-H的大部分查询和表3的Q3无法执行，因此我们跳过这些实验。在整个实验中，concurrency number表示并发查询数量。

6.2 真实workload

本章节，首先表述在1TB和10TB数据量的查询性能，其次是写入吞吐。

6.2.1 1TB数据查询

首先，我们在1TB数据上运行表3的3个查询。图13和图14分别给出了AnalyticDB、PrestoDB、Druid、SparkSQL以及GreenPlum的50%和95%的查询延时。如图中可以看到，ADB具有较低的延时，比其他系统至少快一个数据量级。

图13 1TB 50%的查询时延

图14 1TB 95%的查询时延

Q1。借助于索引引擎，ADB避免了在全表的scan和sort，这不同于PrestoDB和SparkSQL。特别地，ADB会将Order By和Limit算子分发到含有o_trade_time字段索引的二级分区上。因为索引是有序的，所以每个分区只需要遍历整个索引就可以获取到对应的row ids，只涉及几十个index entries。虽然，GP也在所有列上建立了索引，担不是不能执行Order By算子只能full scan，所以会比ADB慢一些。Druid使用o_trade_time作为range分区[36]，可以在大量的range分区中进行过滤，所以会比GP的性能好一些。但是还是比ADB要慢一些，因为Druid要在每个分区上进行scan所有行。

Q2。在我们的数据集中，满足条件o_trade_time, o_trade_prize和o_seller_id的行数分别为306,340,963，209,994,127和210,408。在没有索引的情况下，PresotDB和SparkSQL必须scan所有行来进行过滤。Druid和GreenPlum由于在索引列上的快速检索获得了更好的性能。 但是，Druid只能在string类型列上构建索引，GreenPlum虽然可以在所有列上获得索引，但必须按顺序筛选多个条件，并且对于未更改的条件没有缓存。与它们相比，ADB直接在三个列上并行scan索引，并分别缓存命中的row ids（4.2.6章节）。因此，后续的同样条件的查询，就可以使用条件索引缓存了。

Q3。如图13和14，在50%和95%的查询时延上，不同并发下，Q3都要高于Q1和Q2。是因为Q3是复杂的多表join，以及group by和orde by算子的组合。虽然，由于查询较为复杂，时延较高，但是ADB还是保证了较优的执行。特别地，ADB将join转为了子查询，并使用索引来完成这些子查询。并且，进一步使用索引来执行Group By和Order By算子，避免构建hash表的开销。GreenPlum比ADB慢，就是因为承担了hash join中的hash表构建的开销。为了公平起见，我们也聘评估了在hash join模式下，ADB能够获得与GreenPlum相当的性能。

6.2.2 10TB数据查询

我们进一步构建了10TB的数据集，并提高了并发度。这些系统比较下来，在大数据集和更高并发下，比ADB更慢，后面分析我们将跳过这些。

图15 ADB在1TB和10TB数据集上50%的时延

如图15所示，说明了ADB在1TB和10TB数据集上三种查询的50%时延。我们可以看到，在不同并发下，Q1和Q2的时延都在百毫秒以内。对于Q3的查询，200并发的时延比40并发要更高。原因是8个机器下的计算能力已经饱和，具体来说，64个一级分区和10个二级分区下，200并发下实际的并发线程数达到了128000个。8个机器上，cpu核数总共为48×8=384个。因为Q3查询是计算密集型的，遇到高并发时，频繁的上下文切换，导致性能急剧下降。

从图15中，我们也能看到，在不同并发下10TB数据的变化趋势和1TB变化趋势是类似的。随着数据量的增加，性能受到的影响不是很大。10TB的数据量查询时延仅仅是1TB的两倍，因为ADB优先检索row ids的索引，仅仅需要拉取命中的rows。借助于index cache，索引查找较好的成本收益，并降低了整个开销。总而言之，ADB受表的大小影响很小，主要受控于索引的计算以及命中的行数。

6.2.3 写入吞吐

为了评估ADB的写入性能，我们采用每500字节大小的数据，insert到orders表。表4给出了写入吞吐说明（每秒写入请求）。

分类	参数1	参数2	参数3	参数4	参数5
写节点数量	2	4	6	8	10
写入吞吐	130 KB	250 KB	381 KB	498 KB	625 KB

由于采用读写分离的架构和异步索引构建，写入吞吐随着写入节点的添加而线性增加，直到Pangu达到饱和。当写入节点达到10，写入吞吐是625000，带宽是300 MB/S。索引构建任务是在可以接受的负载下，分配到整个集群执行的，不会影响查询性能和写入吞吐。

6.3 TPC-H基准测试

我们采用1TB数据，进行TPC-H的测试。图16描述了4种系统的性能对比，ADB、PrestoDB、Spark-SQL和GreenPlum。

图16 TPC-H测试对比

ADB在22个查询中20个获得了更小的运行时间，表现优于第二好的GreenPlum，是Spark-SQL的两倍。ADB采用了pipeline的处理模型和索引，比基于stage的处理更快。PrestoDB也采用了pipeline模型，但是缺乏列上的索引。虽然，GreenPlum也有pipeline处理和全列的索引，ADB具备以下4个优势：

• ADB采用混合行列存储，而GreenPlum采用列存，在TPC-H的测试中，表中大约有一半的字段涉及到，ADB可以通过单次IO获取到更多的列；
• ADB基于运行时成本的index path选择可以获取更好的表执行计划，而GreenPlum采用的是基于统计信息的执行计划；
• ADB在组合谓词下推中采用了K路归并；
• ADB采用了向量化执行引擎和将经过优化的CodeGen应用在所有的算子和表达式上。

针对Q2，ADB比PrestoDB和GreenPlum慢，是因为ADB采用了不同的JOIN顺序。

7. 总结

本论文阐述了ADB，作为一个高并发、低延时和实时的OLAP数据库。ADB有一个高效的索引引擎来异步构建所有列的索引，有助于提升查询性能和隐藏索引的构建开销。经过仔细的设计，全列索引只额外占用了66%的存储。ADB扩展了混合行列布局，支持结构化和其他复杂类型数据。为了达到高吞吐写入和高并发查询，ADB采用了读写分离的架构。而且，我们增强了优化器和执行引擎，来充分利用我们的存储和索引的优势。实验表明，所有这些设计有助于ADB相比主流的OLAP系统可以获得更好的性能。

8. 参考文献

[1] Alibaba Cloud. https://www.alibabacloud.com.

[2] ANTLR ASM. https://www.antlr.org.

[3] Apache ORC File. https://orc.apache.org/.

[4] Benchmarking Nearest Neighbours. https://github.com/erikbern/ann-benchmarks.

[5] Greenplum. https://greenplum.org/.

[6] MySQL. https://www.mysql.com/.

[7] Pangu. https://www.alibabacloud.com/blog/pangu—the-high performance-distributed-file-system-by-alibaba-cloud 594059.

[8] PostgreSQL. https://www.postgresql.org/.

[9] Presto. https://prestodb.io/.

[10] Teradata Database. http://www.teradata.com.

[11] TPC-H Benchmark. http://www.tpc.org/tpch/.

[12] D. J. Abadi, S. R. Madden, and N. Hachem. Column-stores vs. row-stores: how difffferent are they really? In SIGMOD, pages 967–980. ACM, 2008.

[13] M. Armbrust, R. S. Xin, C. Lian, Y. Huai, D. Liu, J. K. Bradley, X. Meng, T. Kaftan, M. J. Franklin, A. Ghodsi, et al. Spark sql: Relational data processing in spark. In SIGMOD, pages 1383–1394. ACM, 2015.

[14] J. Backus. Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs. ACM, 2007.

[15] P. A. Bernstein and N. Goodman. Multiversion concurrency control-theory and algorithms. ACM Transactions on Database Systems (TODS)*, 8(4):465–483, 1983.

[16] D. Comer. Ubiquitous b-tree. ACM Computing Surveys (CSUR), 11(2):121–137, 1979.

[17] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT press, 2009.

[18] J. Dean and S. Ghemawat. Mapreduce: simplified data processing on large clusters. Communications of the ACM, 51(1):107–113, 2008.

[19] A. Eisenberg, J. Melton, K. Kulkarni, J.-E. Michels, and F. Zemke. Sql: 2003 has been published. ACM SIGMOD Record, 33(1):119–126, 2004.

[20] M. Grund, J. Kr¨uger, H. Plattner, A. Zeier, P. Cudre-Mauroux, and S. Madden. Hyrise: a main memory hybrid storage engine. PVLDB, 4(2):105–116, 2010.

[21] A. Gupta, D. Agarwal, D. Tan, J. Kulesza, R. Pathak, S. Stefani, and V. Srinivasan. Amazon redshift and the case for simpler data warehouses. In SIGMOD, pages 1917–1923. ACM, 2015.

[22] K. Hajebi, Y. Abbasi-Yadkori, H. Shahbazi, and H. Zhang. Fast approximate nearest-neighbor search with k-nearest neighbor graph. In IJCAI, pages 1312–1317, 2011.

[23] S. Harizopoulos, V. Liang, D. J. Abadi, and S. Madden. Performance tradeoffs in read-optimized databases. In VLDB, pages 487–498. VLDB Endowment, 2006.

[24] P. Hunt, M. Konar, F. P. Junqueira, and B. Reed. Zookeeper: Wait-free coordination for internet-scale systems. In USENIX ATC, volume 8. Boston, MA, USA, 2010.

[25] J.-F. Im, K. Gopalakrishna, S. Subramaniam, M. Shrivastava, A. Tumbde, X. Jiang, J. Dai, S. Lee, N. Pawar, J. Li, et al. Pinot: Realtime olap for 530 million users. In SIGMOD, pages 583–594. ACM, 2018.

[26] H. J´egou, M. Douze, and C. Schmid. Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell., 33(1):117–128, 2011.

[27] F. V. Jensen. An introduction to Bayesian networks, volume 210. UCL press London, 1996.

[28] M. Kornacker, A. Behm, V. Bittorf, T. Bobrovytsky, C. Ching, A. Choi, J. Erickson, M. Grund, D. Hecht, M. Jacobs, et al. Impala: A modern, open-source sql engine for hadoop. In Cidr, volume 1, page 9, 2015.

[29] A. Lamb, M. Fuller, R. Varadarajan, N. Tran, B. Vandiver, L. Doshi, and C. Bear. The vertica analytic database: C-store 7 years later. PVLDB, 5(12):1790–1801, 2012.

[30] G. M. Lohman. Grammar-like functional rules for representing query optimization alternatives, volume 17. ACM, 1988.

[31] S. Melnik, A. Gubarev, J. J. Long, G. Romer, S. Shivakumar, M. Tolton, and T. Vassilakis. Dremel: interactive analysis of web-scale datasets. PVLDB, 3(1-2):330–339, 2010.

[32] T. Neumann. Efficiently compiling efficient query plans for modern hardware. PVLDB, 4(9):539–550, 2011.

[33] K. Sato. An inside look at google bigquery.(2012). Retrieved Jan, 29:2018, 2012.

[34] M. Stonebraker, D. J. Abadi, A. Batkin, X. Chen, M. Cherniack, M. Ferreira, E. Lau, A. Lin, S. Madden, E. O’Neil, et al. C-store: a column-oriented dbms. In VLDB, pages 553–564. VLDB Endowment, 2005.

[35] A. Thusoo, J. S. Sarma, N. Jain, Z. Shao, P. Chakka, S. Anthony, H. Liu, P. Wyckoffff, and R. Murthy. Hive: a warehousing solution over a map-reduce framework. PVLDB, 2(2):1626–1629, 2009.

[36] F. Yang, E. Tschetter, X. L´eaut´e, N. Ray, G. Merlino, and D. Ganguli. Druid: A real-time analytical data store. In SIGMOD, pages 157–168. ACM, 2014.

[37] M. Zaharia, M. Chowdhury, T. Das, A. Dave, J. Ma, M. McCauley, M. J. Franklin, S. Shenker, and I. Stoica.

Resilient distributed datasets: A fault-tolerant abstraction for in-memory cluster computing. In NSDI, pages 2–2. USENIX Association, 2012.

[38] Z. Zhang, C. Li, Y. Tao, R. Yang, H. Tang, and J. Xu. Fuxi: a fault-tolerant resource management and job scheduling system at internet scale. PVLDB, 7(13):1393–1404, 2014.

[39] M. Zukowski, S. Heman, N. Nes, and P. Boncz. Super-scalar RAM-CPU cache compression. IEEE, 2006.