Skip to main content

Issue #11

本期关键词: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 命令(如 CREATEALTERDROP)来管理表,执行结果会保存到 Metadata Store。用户可以在 schema 中指定如列名、数据类型、如何分区和排序、数据接入(data ingestion)方式等信息。Procella 支持两种数据接入方式:批量接入(batch ingestion)和实时接入(realtime ingestion),也就是 Lambda 架构,这一点和 DruidPinot 类似。「批量接入」时由外部批处理任务(如 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 最初由 PandasIbis 项目的作者 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 StorageAzure 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 一样(类似的故事还有很多)。每个城市都有属于这个城市的「角落」,正是这些角落的存在慰藉着形形色色的人们。