Snowflake NSDI'20 | Building An Elastic Query Engine on Disaggregated Storage

要点概括

本文链接：Building-An-Elastic-Query-Engine-on-Disaggregated-Storage | NSDI’ 20

这篇文章是 snowflake 在实际数据分析下对于 snowflake 设计的一篇总结分析，并不是整体架构的设计和介绍。

主要介绍了临时存储系统的设计，任务调度，资源弹性和多租户的一些设计和数据分析上的结果和未来的展望，这个时候 snowflake 已经很成功了，相比四年之前刚提出论文发现了更多实际的问题。

不清楚 snowflake 架构可以先看2016年的第一篇论文 The Snowflake Elastic Data Warehouse

下面用一些话总结下本文的要点：

• 临时存储系统（Ephemeral Storage System）主要缓存中间计算结果（join）和远程表文件数据，同时为了一致性也作为写入的 write-through cache
• 任务调度也是和临时存储系统的特性相耦合的，在临时存储系统上进行 locality-aware 的调度 + work stealing
• 计算资源/临时存储的弹性是在 VW 之间使用惰性一致性哈希进行的，防止数据 reshuffle 产生大量流量
• 多租户下的资源共享主要是计算和存储，云环境下计算隔离已经解决，现在挑战是设计一个共享的临时存储系统，主要挑战来自于在支持细粒度的弹性，而不会牺牲跨租户的隔离属性（很难决策如何 evict 哪些租户的哪些数据）

这篇文章最好的一点就是从数据分析出发，能够给现在很多云数仓的设计和实现提供很多避坑的参考，但是本文由于篇幅也没有介绍更多的细节了，比较笼统。

Abstract

这篇文章介绍了在 snowflake 的一些使用经验，snowflake 是一个支持SQL的云原生数据仓库，是最先进的数据库之以，snowflake 的设计有三个主要的设计目标：1. 计算和存储的弹性 2. 支持多租户 3. 高性能。

这篇文章介绍了snowflake的设计与实现，也介绍了这些年云上基础设施（新硬件，细粒度的计费）的一些变化是如何影响snowflake系统的设计和优化的。这篇文章使用系统收集了每14天一个周期的七千万的queries的数据来说明现在存在的问题，以及突出了多个方面的新研究上的挑战，包括存储系统和高性能查询执行引擎的设计。

1 Introduction

shared-nothing 的架构一直是传统的查询执行引擎和数据仓库的基础，在这种架构下，持久化的数据被划分到一个个的计算节点上，每个都只负责他自己保存的本地数据。这种shared-nothing的架构让计算能够变得很容易scale-out，能够提供不错的任务隔离性和比较好的数据亲和性，从而在各种 workload 下都能比较好的工作。但是也有以下的一些缺点：

• Hardware-workload mismatch
  • Shared-nothing 的架构尝试在计算节点上的 CPU, memory, storage, bandwidth resources 之间寻求一个完美的平衡来适应不同的 workload。例如，一个高带宽轻量的计算节点可能不适合重计算轻带宽的查询，但是很多人希望执行在同一套配置上各种不同类型的query，而不是给每种查询配置一个新的集群。所以为了达到这个性能目标，通常来说资源都必须被过度配置，这会导致平均资源利用严重不足以及更高的成本。
• Lack of Elasticity
  • 即使硬件资源可以达到对workload的需求，shared-nothing架构本身的 static-parallelism 和数据分片也会限制 data skew 和随时间变化的 workload。shared-nothing 的弹性不够，例如在计算中通常需要通过增加、删除节点来提供弹性，但是在这种架构下添加删除节点将会导致数据的 reshuffle，会消耗很大的网络带宽，同时也会带来性能的下降，因为进行 data reshuffle 的节点通常也用于计算

传统的数仓处理的query通常都有可预测的模式和速率，例如数据一般都来在OLTP系统中的交易数据。但是这种情况今天被改变了，因为有了大量难以控制的外部数据源（Logs, social media, web applications …），这将导致很多临时的、随时间变化并且难以预测的查询。对于这种查询，shared-nothing的架构将导致成本过高、不灵活、性能差以及效率低下的特点。

为了突破这个限制，设计并实现了 snowflake，一个弹性、具有事务查询特点的SQL查询引擎。snowflake 的主要目标是为了解决在 shared-nothing 架构中存储和计算的耦合，解决方法就是将二者解耦。snowflake 将数据存放在 Amazon S3 类似的系统中，这些系统能够提高高可用和按需付费的弹性。计算弹性采用了一些提前预热的计算节点池，能够根据需求分配给用户来使用。

snowflake 的系统设计有两个关键点：

1. 使用了定制存储系统用来管理和交换在计算节点之间的临时/中间数据（tables exchanged during joins），这种临时存储系统很有必要，因为现有的存储有两个大的限制存在
   1. 现有的存储（S3）不能提供必要的低延迟和高吞吐，会让计算节点再交换中间数据的时候被阻塞住
   2. S3 等提供了更强的可用性和持久性语义，这是中间数据所不需要的
2. snowflake 也将这种临时存储系统用作持久化数据的 write-through cache，结合自己实现的查询调度机制，Snowflake 能够减少由计算存储分解引起的额外网络负载，并减轻减少数据局部性的性能开销。

这篇文章将会讲 snowflake 的系统设计，着重于 临时存储系统的设计，查询调度，支持多租户的弹性和效率。下面是一些重要的发现：

• 用户的查询种类有多样性。read-only: 28%, write-only: 13%, read-write: 59%
• 查询生成的中间数据量大小相差多个数量级，可能从 GB -> TB，而且查询生成的中间数据量和读取的持久化数据量 or 查询执行时间没有直接的关系
• 在DW 中常见的 data skew 和临时访问模式下，即使本地存储容量很小，也能为其提供平均很高的cache hit rate（60%~80%）
• 有些客户利用了对弹性资源的需求（20%左右），计算节点的数量可能发生多达两个数量级的变化
• 虽然峰值利用率很高，但是平均资源利用率很低，CPU、内存、网络 Tx 和网络 Rx 的平均利用率分别为～51%、～19%、～11%、～32%。

本文的研究也证实了目前社区中有些很棒的研究方向：

• 解耦计算和临时存储
  • 计算和持久存储解耦以获得存储和计算资源的弹性，但是目前计算和临时存储仍然是紧耦合的。临时存储和计算资源的比例可能相差几个数量级，导致CPU利用率不足或者临时存储抖动。
• 深层次存储结构
  • snowflake 的临时存储系统也使用类似存算分离的cache思路，采用双层存储系统（内存主要，SSD/HDD作为第二层），生产集群中的存储系统结构越来越深，需要新的机制来有效利用。
• Pricing at sub-second timescales
  • snowflake 采用预热的节点池为客户提供服务，通常是在小时为粒度的层次上具有成本效应，但是大多数云厂商已经能够提供更细粒度的定价，这将导致在多租户之间的资源弹性和资源共享之间面临新的挑战。

#2 Design Overview

snowflake 针对持久化存储和临时存储是不一样的策略。

2.1 Persistent and Intermediate data

像大多数 DW 系统一样，snowflake 有三种类型的数据

• 持久化的数据：用户在数据库中存储的表的数据，每张表都可能同时被多个查询访问，需要长时间存在并且需要强持久性和高可用性的保证
• 中间数据：由查询运算符产生（join），通常由参与该查询的节点使用。中间数据是临时存在的，为了避免访问中间数据被阻塞，对中间数据的低延迟、高吞吐的要求高于对于持久性的要求，因为如果中间数据产生问题，只需要再次计算即可
• 元数据：例如 object catalogs，从数据库的表到持久化文件存储的映射，statics, transaction logs 等，大部分数据量小，没有什么系统上有趣的挑战

2.2 End-to-end System Architecture

这是 snowflake 高层次的架构图，分为下面四个部分

• 集中控制的云服务：所有客户端都通过向该 snowflake cloud services 提交查询，该层负责访问控制、查询优化、调度、事务管理，并发控制等。CS 被设计为需要提供多租户的能力，需要有多个复制来实现高可用和高拓展性。
• 通过 Virtual Warehouse 抽象来进行弹性计算：每个 VW 本质上是一组 AWS EC2 实例，查询以分布式的方式在上面运行。
• 弹性的临时存储：与持久化数据存储的要求不一样，需要低延迟、高吞吐来保证计算节点的最小阻塞。该临时存储系统和 VW 的计算节点处于同一位置，并明确设计为在添加、删除节点时自动拓展，不需要数据 reshuffle 或者重组，每个VW都运行自己独立的分布式临时存储系统。
• 弹性的持久化存储：snowflake将数据存储在一个远程的、分解、持久化的S3存储中。S3支持存储不可变文件，为了将表存储在 S3 中，Snowflake 将它们水平分区为大的、不可变的文件，这些文件相当于传统数据库系统中的块。 在每个文件中，每个单独的属性或列的值被组合在一起并压缩，如 PAX中那样。 每个文件都有一个 header，用于存储文件中每一列的偏移量，使snowflake能够使用 S3 的部分读取功能来仅读取执行查询所需的列。

2.3 End-to-end query execution

query 执行从客户查询提交给 CS，然后进行查询解析、优化和调度，生成需要执行的任务，随后在 VW 节点上安排这些任务。CS 将跟踪每个查询的进度，收集性能，并在出现故障的时候重新启动节点进行计算。

3 Dataset

数据集在 https://github.com/resource-disaggregation/snowset 公布，这里的数据集不看语义信息，只看统计特征。

• Read-only: 28%
• Write-only: 13%
• Read-write: 59%

4 Ephemeral Storage System

4.1 Storage Architecture, and Provisioning

临时存储中有两个重要的设计原则：

• 同时使用内存和SSD：内存已满时溢出到SSD，因为内存的限制太多，容量可能不够
• 允许将中间数据溢出到持久化存储S3中，以防止本地SSD容量耗尽

未来的发展方向: 将计算和临时存储解耦

对于性能关键的查询，希望中间数据都在内存orSSD中，而不是溢出到S3，这需要准确的资源配置，有两个原因导致无法实现：

1. 可用节点的数量有限，每个节点提供了固定数量的CPU、内存、存储
2. 中间数据的大小无法预测，很难根据先验知识预测，

所以为了解决第一个问题，希望将计算和临时存储解耦；第二个问题更难阶段，对于此类查询，同时实现高性能和高资源利用率将需要计算和临时存储的解耦，以及临时存储系统的细粒度弹性的有效技术。

4.2 Persistent Data Caching

在临时存储系统中的一个重要发现：中间数据是 short-lived。虽然存储中间数据需要大量的内存和磁盘，但是平均很低，所以临时存储系统的容量需要在中间数据和经常访问的持久化数据之间进行统计复用。有两点比较好：1. DW 查询出现了对于持久化数据的显著倾斜 2. 临时存储系统的性能远高于持久数据存储。

Snowflake 通过“机会主义（opportunistically）”缓存频繁访问的持久数据文件，实现中间数据和持久数据之间的临时存储系统容量的统计复用，这里的机会主义指的是中间数据存储始终优先于缓存持久数据文件。持久数据文件采用一致性哈希进行分配到节点中，每个节点采用LRU策略决定持久数据文件的缓存和驱逐。这种缓存改进了许多查询的时间，而且由于优先缓存中间数据，因此可以在不影响中间数据访问性能的情况下实现查询执行时间的性能改进。

需要注意的是持久数据的缓存为了保证正确的语义需要仔细设计。首先是 数据的一致性，为了确保数据的一致性，通过将临时存储系统当做持久存储系统的 write-through cache 来实现，其次，使用基础的一致性哈希时需要在VW弹性拓展时 reshuffle 数据，通过惰性一致性哈希完全避免这种数据的 reshuffle。

持久化数据被缓存在临时存储系统中意味着持久数据访问的请求的某些子集可以由临时存储系统提供服务。临时存储系统的 write-through 策略导致写入到临时存储系统的数据和写入持久存储的数据量大概相等。

尽管临时存储容量远小于持久数据（大约为 0.1%），但是 DW 中的cache 命中率非常高，只读查询接近 80%，读写约为 60%。

未来发展方向：需要在缓存方面做更细致的工作。

除了访问位置以外，缓存命中率还取决于 查询可用的缓存大小相较于查询访问的持久数据量，反过来说，有效的缓存大小取决于 VW 的大小和并发查询执行生成的中间数据量。

另外两个技术问题：

1. 端到端的查询性能取决于持久文件命中率和中间数据的I/O吞吐，因此优化临时存储系统如何在两者之间分配容量非常重要。例如优先缓存被许多查询缓存的持久文件，而不是只被一个查询使用的中间数据
2. 现有的存储机制是为了双层存储系统设计的（内存第一层，HDD/SSD作为第二层）在 snowflake 中已经有了三个层次，本地计算内存、临时存储系统、远程持久化存储。云上的存储层次结构变得越来越深。Snowflake 使用传统的两层机制：每个节点实现一个本地 LRU 策略用于从本地内存到本地 SSD 的逐出，以及一个独立的 LRU 策略用于从本地 SSD 到远程持久数据存储的逐出。 然而，为了有效地利用加深的存储层次结构，snowflake需要新的缓存机制来有效地协调跨多个层的缓存。

5 Query (Task) Scheduling

Locality-arare task scheduling

为了充分利用临时存储系统， snowflake 的调度系统是在持久化的数据文件上 locality-aware 的（这些文件可能在临时存储系统中），具体来说，snowflake 使用 table file name 的一致性哈希来将持久数据文件分配给计算节点。调度系统将计算任务分配给其文件被散列到的节点上。

这种调度决策下，查询的并行性将和数据文件的一致性哈希结果紧密相连。也就是说假设在有 10 个节点的 VW 中，涉及到 100,000 个文件的查询和涉及到 100 个文件的查询都将分布在这十个节点上。

work stealing

一致性哈希会导致分区不平衡，所以为了避免这个问题，snowflake 将使用 work-stealing，如果任务的完成时间（执行时间 + 等待时间）早于预期，那么将从另一个节点窃取任务。注意：窃取任务时，读取数据将从远程数据存储中读取，避免了在已经发生过载的节点上增加负载。

Future Directions

调度决策有两种方案，

• 将任务尽可能与数据缓存结合到一起
  • 优点：最大限度减少了读取持久数据的网络流量
  • 缺点：导致中间数据交换的网络流量增加
• 将所有任务都放在一个节点上
  • 优点：消除中间数据交换的网络流量
  • 缺点：增加读取持久数据的网络流量

直接选择两种调度程序可能都不是最好的选择，所以需要在两种调度策略种进行中和，然后将任务调度到各个节点上。

6 Resource Elasticity

存算分离的架构导致能够独立的拓展计算和存储的弹性。

计算弹性：通过预热的节点池实现，能够在几十秒的粒度上提供弹性

存储弹性：存储弹性的实现交给了数据存储（S3……）

6.1 Lazy Consistent Hashing

实现弹性的一个大的问题就是临时存储中的数据管理，临时存储系统将会缓存持久数据文件，每个文件只能缓存在VW中始终散列的节点上，所以还是有点类似 shared-nothing 架构了，任何固定分区的架构都需要在拓展节点时进行大量的数据 reshuffle，此外这些节点还会同时跑计算。

snowflake 采用了惰性一致性哈希解决了这个问题，整体思路很好理解，利用了缓存数据一定存储在远程存储中这一事实进行实现，完全避免了在节点弹性时增加的对数据的 reshuffle。

例子如下：开始 VW 中五个节点，File1 File6 在 node1 上，这个时候 Task6 将会在 node1 上执行，之后集群增加一个节点 node6，这个时候本应该将 File6 reshuffle 到 node6 上，但是这里先不进行操作，当下次计算任务安排到 node6 的时候，node6 直接从远程存储中读取，node1 中的 file6 将不再被访问，也不需要进行数据的 reshuffle。

6.2 Elasticity Characteristics

大约 20% 的用户会使用到计算弹性的需求，然后这些弹性会在 VW 的生命周期内会产生多达两个数量级的变化。

未来发展方向

目前客户并没有利用超过80% VW的弹性。即使确实有对 VW 进行弹性的用户，也有进一步优化的机会。例如有些客户的 query 间隔要比 snowflake 当前 VW 计算节点弹性的时间更长，snowflake 认为产生这个问题的主要原因在于用户对于需求的错误估计（例如设置了太少的节点，查询的频率又太高），导致二者不匹配。

个人感觉有点像计算资源申请上的某种 “抖动”

两个未来的工作：

1. 希望实现查询内粒度的弹性。具体来说，即使在单个查询的生命周期内，资源消耗也会有很大差异。 这在具有许多内部阶段的长时间运行的查询中尤为普遍。 因此，除了以查询到达间隔的粒度自动缩放 VW 之外，理想情况下，即使在执行查询期间，snowflake也希望支持某种级别的任务级弹性。

2. 尝试类似 serverless-less 的平台，类似 AWS Lambda，Azure Functions 以及 Google Cloud Functions 这些自动拓展、高弹性以及细粒度的计费功能。目前 snowflake 很难过渡的原因是：安全性和性能都缺乏对于隔离的支持，所以 snowflake 可能自己来定制一种类似 serverless-less 的平台，但是需要解决高效远程临时存储访问的问题。

7 Multi-tenancy

snowflake 当前通过 VW 的抽象来支持多租户。每个 VW 都在一组独立的节点上运行，都具有自己的临时存储系统，这让 snowflake 能够为其客户提供性能隔离。

snowflake 的 VW 架构导致了一个问题：性能隔离和利用率上的 trade off。

下面的前四个图可以看到不错的CPU利用率，但是其他的利用率，例如 memory, network 等利用率比较低。观察发现高达 30% 的VW在 CPU 上的利用率的标准差和均值一样大……，这导致利用率不足。

最近云厂商的发展让 pre-warmed node pool 变得成本效益很差，过去 infra 通过小时计费，具有成本效益，但是现在计价越来越精确，从snowflake 的角度来说更精细的管理意味着成本的降低利润增多，客户也需要这种计价方式来提供更低的成本。

以前在按小时计费的模型中，只要至少有一个客户 VW 在一小时内使用了一个特定节点， 可以在整个期间向该客户收费。 但是，对于按秒计费，无法向任何特定客户收取预热节点上未使用的周期费用。 这种成本效率低下的情况为转向基于共享的模型提供了强有力的理由，其中计算和临时存储资源在客户之间共享：在这样的模型中，可以通过跨共享资源集统计复用客户需求来提供弹性，避免 需要维护大量预热节点。

7.1 Resource Sharing

VW 资源使用随时间变化的变化表明snowflake的一些客户工作负载本质上是突发性的。 因此，转向共享架构将使 Snowflake 能够通过细粒度统计多路复用实现更好的资源利用。

目前的主要挑战是提供接近当前架构的隔离性。

从客户的角度来看，他们感兴趣的关键指标是查询性能，即端到端查询完成时间。 虽然纯粹的共享架构可能会提供良好的平均情况性能，但在尾部保持良好的性能比较难搞。 需要在 VW 中隔离的两个关键资源是计算和临时存储。 Snowflake 可以利用数据中心环境中计算隔离方面的一些工作。 此外，Snowflake 中的集中式任务调度程序和统一执行运行时使问题比在通用集群中隔离计算更容易。 在这里，转而关注隔离 memory 和 storage 隔离的问题。

主要的目标是设计一个 共享的临时存储系统，（同时使用内存和 SSD），该系统支持细粒度的弹性，而不会牺牲跨租户的隔离属性。实现这个系统有两个主要挑战：

1. 首先，由于临时存储系统多路复用缓存的持久数据和中间数据，因此这两个部分数据需要共同共享，同时确保跨租户隔离。 虽然 Snowflake 可以利用现有技术来共享缓存，但snowflake需要一种额外了解中间数据共存的机制。 不幸的是，预测缓存条目的有效生命周期很困难。 在确保硬隔离的同时从租户中驱逐空闲缓存条目并将它们提供给其他租户是不可能的，因为snowflake无法预测租户下一次访问缓存条目的时间。 既要定义更合理的隔离保证，又要设计可以提供此类保证的生命周期感知缓存共享机制。
2. 第二个挑战是在没有跨租户干扰的情况下实现弹性：扩展共享的临时存储系统容量以满足特定客户的需求不应影响共享该系统的其他租户。 例如，如果简单的使用 Snowflake 当前的临时存储系统，隔离属性将会被马上违反。 由于 Snowflake 中的所有缓存条目都一致地散列到相同的全局地址空间中，因此扩展临时存储系统容量最终会触发所有租户的惰性一致性散列机制。 这可能会导致多个租户看到缓存未命中率增加，从而导致性能下降。 解决这一挑战需要临时存储系统为每个单独的租户提供私有地址空间，并且在资源扩展时，仅为那些已分配额外资源的租户重组数据。

Memory Disaggregation

VW 的内存平均利用率很低，这点很难顶，因为 DRAM 很贵，虽然共享资源会提高 CPU 和 memory 的利用率，但是不太可能在两个维度上实现最佳利用率，此外 CPU 和 memory 的特点非常不同，需要独立拓展这些资源，准确配置资源是困难的； 由于过度配置内存的成本很高，snowflake需要有效的机制来在多个租户之间共享分解内存，同时提供隔离保证。

8 Related Work

• SQL-as-a-Service systems
  • 还有其他几个系统在云中提供 SQL 功能作为服务。 其中包括 Amazon Redshift 、Aurora 、Athena 、Google BigQuery 和 Microsoft Azure Synapse Analytics 。 虽然有一些论文描述了其中一些系统的设计和操作经验，但是这些系统并没有从数据角度分析工作负载和系统特征。
  • Redshift 将持久数据的主要副本存储在计算 VM 集群中（S3 仅用于备份）； 因此，它可能无法实现 Snowflake 通过将计算与持久存储解耦而获得的好处。 Aurora和 BigQuery（基于 Dremel的架构）类似于 Snowflake 将计算和持久存储解耦。 然而，Aurora 依赖于定制设计的持久存储服务，该服务能够分离数据库日志处理，而不是传统的 blob 存储。
• 存算分离的系统
  • Facebook 的key-value 的存储下的 workload 在 flash 存储上进行了分离。 snowflake 发现了这种思路，并在数据仓库工作负载的背景下进一步扩展了它。 Pocket 和 Locus 是为无服务器分析应用程序设计的临时存储系统。 如果我们要在 Snowflake 中分解计算和临时存储，这样的系统将是很好的选择。 然而，这些系统在查询的生命周期内不提供细粒度的资源弹性。 因此，他们要么必须先验地了解中间数据大小（用于在提交查询时配置资源），要么如果事先无法获得此类知识，则会遭受性能下降的困扰。 如 4.1 中所述，预测中间数据大小非常困难。 最好扩展这些系统以提供细粒度的弹性和交叉查询隔离。 对远程闪存存储进行高性能访问的技术 也将是有效实现计算和临时存储系统解耦的重要组成部分。
• 多租户资源共享
  • ESX 服务器开创了虚拟机环境中多租户内存共享的技术，包括 ballooning 和 idle-memory taxation。 Memshare 考虑在单机上下文中 DRAM 缓存中的缓存容量的多租户共享，以最大化命中率的方式在应用程序之间共享未保留的容量。 FairRide 同样考虑分布式中的多租户缓存共享，同时考虑租户之间的数据共享。 类似于这些系统中使用的缓存资源共享和隔离机制对于使 Snowflake 采用资源共享架构非常重要。 如前所述，扩展这些机制以使其了解中间数据和持久数据的不同特征和要求会很有趣。

9 Conclusion

我们展示了运行 Snowflake 的操作经验，Snowflake 是一种具有最先进的 SQL 支持的数据仓库系统。 我们在本文中涵盖的关键设计和实现方面涉及 Snowflake 如何实现计算和存储弹性，以及多租户环境中的高性能。 随着 Snowflake 已经成长为每天对数 PB 数据执行数百万次查询的数千名客户提供服务，我们认为自己至少取得了部分成功。 然而，使用在 14 天内执行约 7000 万次查询期间从我们系统的各个组件收集的数据，我们的研究强调了我们当前设计和实现的一些缺点，并强调了可能感兴趣的新研究挑战更广泛的系统和网络社区。