Skip to main content

Issue #11

· 30 min read

本期关键词：Procella、PrestoDB@Facebook、Apache Arrow、S3 Consistency、Feast、Uptown Records

Procella: Unifying serving and analytical data at YouTube​

[链接]

Procella 是 YouTube 自研的 SQL 查询引擎，旨在用一个引擎满足多种使用场景的需求（有点像上一期介绍的 Tectonic），目前已经被广泛应用在 YouTube、Google Play、Firebase 等多个产品。论文发表在 2019 年的 VLDB 会议，第 4 期曾经介绍过同一年发表的 AliGraph。

虽说 Procella 自称 SQL 查询引擎，但其实它也包含一些与存储格式有关的技术，并且这个存储格式对于整体系统来说是不可或缺的一部分，关于这部分后面会单独介绍。先来了解一下 Procella 想要满足的几个场景：

  • 分析报告和 dashboard：YouTube 的创作者（现在应该流行叫 YouTuber）需要通过一个实时更新的 dashboard 来了解所有视频的统计信息，评估内容的影响力。这个场景对响应时间有较高要求（数十毫秒），处理的数据量也非常大（每天有千亿行的新增数据）。
  • 实时统计数据：这里的统计数据和上一个的区别是上一个还只是面向小部分用户，而这里的统计数据是所有用户在访问 YouTube 时都能看到的（比如点赞数、观看次数），因此请求量会更大，对响应时间的要求也更高。通常 OLAP 系统都是偏离线的，为了应对这种在线查询的场景 Procella 做了很多针对性的优化，后面会详细介绍。
  • 监控系统：这个场景面向的是内部工程团队，虽然数据量相对较小，但是对数据更新的实时性要求很高。常见的监控系统存储都是用 TSDB 来实现，Procella 因此也需要支持一些 TSDB 独有的特性，如自动降采样（downsampling）和过期旧数据。
  • Ad-hoc 分析：这也是面向内部团队的场景，ad-hoc 场景的挑战是查询不可预测，可大可小，可快可慢，系统怎么自适应这些千奇百怪的查询是一个难题。

从上面的场景介绍也能看出 Procella 不打算支持或者目前暂时不支持的场景，比如 OLTP、ETL、图计算。

Procella 的主要组件有：Root Server（RS）、Data Server（DS）、Metadata Server（MDS）、Ingestion Server（IgS）、Registration Server（RgS）、Compaction Server（CS）。除此之外还依赖一些外部组件：Metadata Store（Bigtable 和 Spanner）、分布式文件系统（Colossus，第 8 期曾经介绍过）、容器调度和编排（Borg）。

RS 是用户提交 SQL 的入口，负责分析、重写、计划和优化执行计划（execution plan）。RS 会和 MDS、Metadata Store 和 DS 直接通信，其中 Metadata Store 保存着表的 schema、表到文件的映射、统计信息、zone map 等元数据，MDS 保存着 zone map、bitmap、bloom filter、分区和排序键等索引信息（这些索引信息一部分在首次注册文件时生成，一部分在查询时生成），DS 负责运行 RS 或者其它 DS 发送的执行计划。不同 DS 之间通信使用 Stubby 这个 RPC 框架（也就是后来开源的 gRPC），同时通过 RDMA 来执行 shuffle 操作（复用了 BigQuery 的 shuffle 库）。

RgS 负责执行 DDL 命令（如 CREATE、ALTER、 DROP）来管理表，执行结果会保存到 Metadata Store。用户可以在 schema 中指定如列名、数据类型、如何分区和排序、数据接入（data ingestion）方式等信息。Procella 支持两种数据接入方式：批量接入（batch ingestion）和实时接入（realtime ingestion），也就是 Lambda 架构，这一点和 Druid、Pinot 类似。「批量接入」时由外部批处理任务（如 MapReduce）将数据导入并注册到 RgS，RgS 会从文件头（header）中提取相关信息并建立索引，某些没法直接通过文件头创建的索引（如 bloom filter）会在查询时通过 DS 来创建。「实时接入」时用户通过 RPC 或者 PubSub 的方式把数据导入 IgS，当 IgS 接收到数据以后可能会根据表结构转换数据格式，并写入 WAL 到 Colossus（后台会定期压缩）。IgS 同时还会把数据写入 DS，DS 会在内存中临时缓冲这些数据供用户查询，并定期 checkpoint 到 Colossus 以便在故障时恢复数据。IgS 可能也会将数据写入多个 DS，查询执行时会访问所有副本并使用最完整的集合。

CS 会定期压缩（compact）和重新分区（repartition）IgS 写入的 WAL 日志，转换成对于 DS 来说更高效的更大的分区。在 CS 压缩的过程中，可以执行一些由用户定义的逻辑以减少数据大小，这些逻辑包括过滤、聚合、淘汰旧数据、仅保留最新数据等，通过 SQL 来表示。当处理完以后 CS 会与 RgS 通信更新元数据，从元数据中删除旧文件然后插入新生成的文件。

为了满足不同场景对于性能的要求，Procella 在多个方面进行了优化，包括：缓存、数据格式、评估引擎（evaluation engine）、分区与索引、分布式操作、查询优化器（optimizer）等。本期不会对所有优化进行介绍，有兴趣的同学请查看原文。

对于存算分离的引擎，缓存是至关重要的，Procella 也不例外。Procella 包含以下几种类型的缓存：

  • Colossus 元数据缓存：DS 会缓存 Colossus 的文件句柄，这个句柄包含数据块到 Colossus 服务器的映射关系，可以优化打开文件的性能（减少 1 个或多个 RPC 请求）。
  • 文件头（header）缓存：Procella 的数据格式（后面会详细介绍）是类似 Parquet 这样的列存格式，因此文件头或者尾会包含很多重要的元信息，DS 会在一个单独的 LRU 缓存中保存这些信息，减少与 Colossus 的交互。
  • 数据缓存：Procella 的数据格式在内存和磁盘上是同样的结构（可能是能直接通过 mmap 映射到内存），因此数据缓存的管理很轻量。同时 DS 还会缓存一些衍生信息，如某些复杂操作的输出、bloom filter。因为 Colossus 的文件一旦关闭就是不可变的（immutable），所以不存在缓存不一致的问题。
  • 元数据缓存：Procella 的元数据依赖外部的分布式存储（Bigtable 和 Spanner），虽然元数据很容易进行横向扩展，但外部存储也可能成为系统瓶颈，因此 MDS 通过一个 LRU 缓存保存这些信息。
  • 亲和性（affinity）调度：当执行查询时，会把操作尽量调度到已经缓存了要处理的数据或者元数据的节点，提高缓存的命中率。这个调度策略不是强制的，有可能会调度到其它节点。

综合以上所有类型的缓存，Procella 大体上已经变成了一个全内存数据库。在其中一个分析报告的业务场景，虽然内存只能存放 2% 的数据，但是实际表现是文件句柄的缓存命中率达到了 99%+，数据缓存的命中率达到了 90%，基本不依赖外部系统。

第一版 Procella 的数据格式用的是和 Dremel 一样的 Capacitor，但由于 Capacitor 的设计主要面向大规模扫描场景，没法支持高效查找（lookup），因此 Procella 设计了一种新的数据格式「Artus」。Artus 主要有以下几个创新点：

  • 定制的编码方式：区别于传统列存格式使用的通用压缩方式（如 LZW），Artus 的编码方式可以在不解压数据块的前提下直接查找单行，进而更加适合小规模的点查和范围扫描场景。
  • 多轮自适应编码：第一轮先扫描数据收集轻量级的统计信息（如去重以后的数量、最小和最大值），第二轮使用这些统计信息选择最优的编码方式。这里「最优」的判断逻辑是基于各种编码方式提供的预估方法（estimation method），这个预估方法能给出处理对应数据的时间和空间，然后根据用户设定的目标函数（objective function）来自动选择。
  • 选择支持二分查找的编码方式：对于有序的列，查找所需的时间复杂度是 O(logN)。同时在列数据中查找某一行的时间复杂度可以做到 O(1)，因此查找 K 列的时间复杂度是 O(logN + K)。O(1) 是最优的时间复杂度，对于如 RLE（Run-Length Encoding）这样的编码需要每 B 行额外维护一些「跳块」（skip block）信息，实际的时间复杂度其实是 O(B)，但 B 的取值通常很小（如 32、128）。
  • 用一种创新性的方式表示嵌套和重复数据类型：对于查找嵌套（nested）和重复（repeated）数据类型的数据可以做到 O(1) 的时间复杂度。
  • 把字典索引、RLE 以及其它编码信息直接暴露给评估引擎：可以把过滤逻辑下推到数据格式，多数场景下都能有不错的性能提升。
  • 在文件头和列头记录丰富的元数据：这些元数据包括排序信息、最小和最大值、编码信息、bloom filter 等，可以在不读取实际数据的情况下实现剪枝（pruning）操作。
  • 支持存储倒排索引：Procella 主要在 A/B 实验分析场景用到倒排索引，这些倒排索引存储为 Roaring bitmaps 格式。Roaring bitmaps 已经被广泛应用于各种大数据引擎，包括 Spark、Druid、Kylin、Doris、ClickHouse 等。

在 YouTube Analytics 数据集的实际测试中，Artus 相比 Capacitor 最多能有 140 倍的性能提升，平均也有 50 倍的性能差距。

高性能的评估引擎（evaluation engine）对于低延时请求来说是至关重要的，很多现代分析系统会在查询时通过 LLVM 将执行计划编译为原生代码，以此来加速查询。但是 Procella 因为还要处理高 QPS 的在线服务场景，编译的耗时会成为这个场景的性能瓶颈。因此 Procella 研发了自己的评估引擎「Superluminal（超光速）」，它主要有以下几个特点：

  • 广泛使用 C++ 的模板元编程（template metaprogramming）特性在编译时生成代码
  • 以块（block）为单位处理数据，更好地利用向量化（vectorized）计算以及缓存感知（cache-aware）算法。每个块的大小会根据 L1 缓存的大小进行预估。
  • 直接原生操作底层数据编码，并在函数应用期间尽可能保留它。编码信息或者是从文件格式中获取，或者是在执行时生成。
  • 以列式存储的方式处理结构化数据，不会物化（materialized）中间结果。
  • 动态合并过滤器以及下推执行计划，使得每个节点仅仅扫描确切需要的数据。

前面提到 Procella 一个重要使用场景就是「实时统计数据」，通常意义上的 OLAP 系统都不太能应对这类实时场景的要求（不管是延时还是 QPS），所以一般会选用 OLTP 或者缓存系统（如 Redis）来解决。这类场景的查询非常简单：SELECT SUM(views) FROM Table WHERE video id = N，数据规模也不大（最多 10 亿级行），但是每个 Procella 实例需要在承载百万级 QPS 的同时实现毫秒级响应，数据也需要能够做到近实时更新，因此 Procella 专门设计了一个「stats serving」模式，这个模式包含以下一些优化：

  • 当新数据注册进来时，RgS 会通知 DS（主从 DS 都包括）新数据已经准备好了，然后 DS 就会立即将数据加载到内存中。这个优化是为了保证执行查询时不会访问远端存储，虽然会耗费一些内存但是按照业务的数据量这是可接受的。
  • MDS 被作为一个模块编译进 RS，尽可能减少 RPC 通信。
  • 所有元数据都会异步加载进内存，和数据一样确保不会产生远端访问。
  • 激进地缓存查询计划，降低分析和计划查询的开销。
  • RS 会将相同 key 的请求批量发送给 DS，减少 RPC 通信。
  • RS 和 DS 会监控每个任务的错误率和响应时间，如果发现异常高的任务会自动转移到其它机器。做这个优化一部分也是因为 Borg 的资源隔离做得不够好。
  • 关闭复杂的优化和操作（如自适应 join 和 shuffle），避免不必要的开销以及生产环境的风险。

最后是一些生产环境的实际数据。在 YouTube Analytics（YTA）业务中，一共有 5 组 Procella 集群，其中至少有 3 个在服务线上请求，每组集群有大约 6000 个核以及 20TB 的内存。YTA 业务每天有超过数十亿的请求，涉及数十 PB 的数据。YTA E2E 的响应时间 P50、P99、P99.9 分别是 25、412、2859 毫秒。「实时统计数据」业务每天有上千亿的请求，响应时间 P50、P99、P99.99 分别是 1.6、3.3、21.7 毫秒。

以上就是 Procella 的全部介绍，熟悉 Google 的同学可能关心为什么 YouTube 团队不直接用 Google 现有的一些基础设施呢。论文中也对相关系统做了简单介绍和比较，其中：

  • Dremel（VLDB 2010）是一个为 ad-hoc 场景优化的列式 SQL 查询引擎，支持多种后端（如 ColumnIO、Capacitor、Bigtable），同时 Dremel 也是 Google Cloud BigQuery 的底层引擎。Procella 与 Dremel 有诸多相似之处，如 RPC 协议、SQL 分析器、底层存储（Colossus）、容器编排（Borg）。但也有很多不一样的地方，如大量使用缓存（Dremel 基本是无状态的）、为不同业务场景部署不同的集群（Dremel 是一个多租系统）、可索引的数据格式（Capacitor 不可索引）。Dremel 影响了后续很多大数据开源项目，如 Parquet（Parquet 最初叫做 RedElm，是由 Dremel 的字母重新排列组成）。
  • PowerDrill（VLDB 2012）是一个全内存列式分布式 SQL 查询引擎。PowerDrill 适合小 QPS 以及简单查询的场景，主要应用在日志数据分析以及内部 dashboard。
  • F1（VLDB 2013）是一个分布式查询引擎，支持多种后端（如 ColumnIO、Capacitor、Bigtable、Spanner、Mesa）。F1 和 Procella 最大的不同是，因为 F1 本身只是一个查询引擎，用户需要根据场景选用合适的后端存储，如 OLTP 场景选 Spanner、ad-hoc 分析场景选 Capacitor 等。但是 Procella 用一套系统同时满足了多种场景的需求，计算和数据格式也是强绑定的。
  • Mesa（VLDB 2014）是一个集存储和查询一体的数据系统。Mesa 最初是为了满足 Google 广告业务的需求而设计，因此在设计上有很多独特的地方，如预聚合数据、基于 delta 的数据接入（更新时效在分钟级）。Mesa 并不支持 SQL 查询，而是通过 F1 来实现。百度开源的 Doris 即是基于 Mesa 来设计（一个题外话，Doris 的 SQL 查询是基于 Impala 实现）。

Presto at Facebook: State of the Union​

[链接]

今年 3 月 24 日 PrestoDB 举办了 PrestoCon Day（第 6 期曾经介绍过「Presto: SQL on Everything」这篇论文），这个视频来自前面 Procella 论文的第一作者 Biswapesh Chattopadhyay，从他的 LinkedIn 上看他于 2019 年从 Google 离职并加入了 Facebook，领导整个大数据基础设施团队。Biswapesh 首先总结了 PrestoDB 目前为止的一些进展，如 Disaggregated coordinator、CBO、RaptorX、Velox（原生代码加速器，有点类似 Procella 的 Superluminal）、CoreSQL。这些特性有些已经在 Facebook 生产环境稳定运行，有些还在灰度测试，有些还处于早期设计阶段。未来规划中列举了一些 PrestoDB 的目标，如支持更多类型的 SQL（HQL 等）、更多运行模式（流式、批处理、交互式查询、图计算）、更多元数据存储（Hive Metastore、Iceberg、Delta Lake）、更多格式（ORC、Parquet）。

Origin and History of Apache Arrow​

[链接]

2016 年 2 月 Cloudera 公开宣布了 Apache Arrow 项目（以下简称 Arrow），距今这个项目已经发展了 5 年时间。Arrow 最初由 Pandas 和 Ibis 项目的作者 Wes McKinney 在 2014 年发起，当时他还在 Cloudera 工作，项目名也还不叫做 Arrow。2015 年 Wes 和 Jacques Nadeau 及 Apache Drill 团队有了一些接触，Jacques 等人对于这个项目表示了浓厚的兴趣。这里稍微扯远一些，Apache Drill 是由 Tomer Shiran 在 MapR 工作时发起，很大程度上是受 Google Dremel 启发和影响，2015 年那会儿 Tomer 和 Jacques 正在准备创立 Dremio（Tomer 是 CEO，Jacques 是 CTO）。后来经过早期参与者投票，正式确定了使用 Arrow 作为项目名（因为向量的数学符号是箭头）。这里提到向量，是因为 Arrow 是受现在很火的向量化（vectorization）影响。提到向量化往往还会讲到列式存储，我们熟知的列式存储格式如 Parquet 已经定义了数据如何在磁盘上组织，但是当把这些数据从磁盘中读取出来处理时，它们在内存以及 CPU 中应该以何种格式存在呢？是继续以列式格式处理还是转成行式呢？目前大部分计算引擎其实还是以行式进行处理，但是向量化证明了以列式进行处理在 OLAP 场景是更加高效的。因此 Arrow 的目标是制定一种语言无关的内存中的列式存储格式，并以库的形式集成到各种计算引擎中，避免重复造轮子。理想情况下，数据从磁盘 → 内存 → CPU 不需要经过任何格式转换和拷贝，最大化处理效率。Arrow 官方目前已经支持 12 种编程语言，如果想拓展到新语言，可以很方便地在 C++ 实现之上扩展。现在 Arrow 已经不仅仅是一种存储格式，还包括 RPC 框架（Flight）、高性能执行内核（Gandiva）、查询引擎（DataFusion）等组件，逐渐丰富 Arrow 的生态。有了这些基础组件，使得实现一个新的 OLAP 系统的门槛大大降低，也难怪 InfluxDB 创始人 Paul Dix 要大肆鼓吹。Arrow 是一个非常有野心的项目，值得长期关注。

Diving Deep on S3 Consistency​

[链接]

去年 12 月 1 日，AWS 宣布在 S3 发布 14 年后终于支持强一致性。作为对象存储的创造者，S3 一直是这个领域的标杆，基本就是对象存储的代名词（一个不太一样的地方是，国内通常用 OSS 来指代对象存储）。但对象存储的「最终一致性」一直被人所诟病，特别是随着越来越多业务场景依赖对象存储（比如大数据），这是 S3 诞生时完全预料不到的。而 AWS 的竞争者们虽然是后来者，但已经纷纷支持强一致性，比如 Google Cloud Storage、Azure Storage。Amazon 的 CTO Werner Vogels 近期发布的这篇博客披露了更多有关 S3 如何实现强一致性的细节，以 S3 目前的体量增加新特性必须做到小心翼翼，不能对现有系统造成任何影响。具体的，S3 在元数据子系统中新增了一个叫做 Witness 的组件通过事件通知的机制来确保缓存的一致性，这样既实现了强一致性的目标，也确保了 S3 整体的稳定性没有受到影响。有趣的是这篇博客的评论中有人也对这个设计提出了一些质疑，怀疑 S3 是否真的能做到强一致性，毕竟这次改进并没有改变 S3 系统的核心设计。

A State of Feast​

[链接]

Feast 项目由 Willem Pienaar 在 Gojek（一家面向东南亚市场的「啥都做」公司）工作时发起，并和 Google Cloud 合作，在 2019 年联合发表了一篇介绍文章。Feast 的定位很好理解，就是做开源的特征存储框架，叫存储系统可能不太合适，毕竟实际的数据存储还是要依靠外部系统，Feast 专注在如何统一管理和使用特征。说到特征管理，有过相关经验的同学一定知道「训练/服务偏斜」（Training-Serving Skew），这一点在著名的「Rules of Machine Learning」中也有提到。数据科学家可能有 80% 的时间都在清洗和准备数据，特征工程（feature engineering）对于模型质量也至关重要。大公司可能都会自己造各种轮子来管理特征，比如 Uber 的 Michelangelo，现在 Uber 的这几位也出来创业，成立了一家叫做 Tecton 的公司。Feast 的作者 Willem Pienaar 也加入了 Tecton，不过他还会继续负责 Feast 开源社区。未来 Feast 会朝着更易用、更模块化、更云厂商中立的定位去发展，同时补足与 Tecton 闭源版本之间的一些功能差异。如果你对什么是特征存储感兴趣，也推荐阅读这篇文章。

Uptown Records 十年，不只是一家唱片店​

[链接]

Uptown 是一家位于上海以黑胶为主的独立唱片店，如果你曾经在上海生活过并且喜爱音乐一定听说过它。Uptown 的诞生得追溯到 2011 年，在平武路和幸福路交叉口的一间地下室，原本想要做成一间酒吧，后来阴差阳错地变成了一家独立唱片店，老板 Sacco 和老板娘 Sophia 就这样一直经营到了现在。大概 5、6 年前我初到上海时，就和叶子一起慕名前往了这间没有任何招牌的地下室，走下阴暗的楼梯，然后穿过长长的狭窄的昏暗过道，尽头的一间小房子就是 Uptown。店里当时只有一名员工，屋里放着音乐，顾客只有我们两个，基本把店里陈列的唱片都翻了一遍，印象比较深的是看到了几张 Carsick Cars 的唱片，大部分还是国外的我不认识的艺术家。后来听说 Uptown 开了分店，在永福路，也终于不是在地下，但一直没有造访。2019 年因为要给一个好朋友送礼物特地去了一次永福路的 Uptown，虽说在地上但招牌依然不明显，黑色招牌上只有 RnB（Records & Beer）这几个字，不仔细留意的话很容易错过。这次买了两张唱片，一张是 New Order 的《Movement》，一张是 JAMC 的《Automatic》，成色都还不错。这篇文章来自「BIE 别的」公众号，介绍了很多 Uptown 早期不为人知的故事，比如上海胶圈另一个著名的组织 Daily Vinyl 的联合创始人曾经也是 Uptown 的员工。现在平武路的这间地下室租约到期，因为无法承担涨价以后的房租，Uptown 不得不发起了「Save Uptown」的筹款活动，试图保住这个对于城市音乐场景有着重大意义的地方。从大众点评的信息看，平武路的 Uptown 最终还是没能延续，就像几年前的另一家上海音乐地标 Shelter 一样（类似的故事还有很多）。每个城市都有属于这个城市的「角落」，正是这些角落的存在慰藉着形形色色的人们。