OPED 是 (我自己发起的) One Paper Each Day 挑战, 即每天(偶尔)读一篇 Paper, 领域不限.

这是 OPED 挑战的第八篇, 论文为 Procella: Unifying serving and analytical data at Youtube

好久没有读论文了… 虽然打印了几篇,但是回到家就想歇着… 今天终于又读了一篇来自 Google 的论文,描述了 Youtube 使用的一个同时支持线下分析和线上使用数据系统:Procella。

Procella 是一个很复杂的系统,我感觉这篇论文主要介绍了 Procella 的大致设计,和实现中的一些技巧。这篇博客只会包含论文中很小一部分内容,感兴趣的朋友们可以去阅读以下原论文。

背景

Google 这几年搞了很多类似的数据系统,内部使用的包括 Dremel,ProwerDrill,Spanner,Mesa,BigTable 等等。对外的有 BigQuery,Cloud Spanner 等等。这些系统往往都是面向某几个特定的使用场景,比如 Dremel 适合一些 Ad-Hoc 的分析场景。Spanner 作为一个 Planet-Scale 的数据库,则适合线上服务的实时查询。Youtube 作为一个全球知名的(但是并不存在的)的在线视频网站,每天产生的数据量贼大,Google 内部的 Dremel,F1 等等系统都满足不了他们了。所以他们搞出了 Mesa,一个专门做 Aggregation 的系统。现在看来,Mesa 也不能完全地满足需求,因此 Procella 诞生了。

需求

说了这么多(欲)需求不满,到底有哪些需求呢。这篇论文主要列举了以下几种:

  1. Report & Dashboard: 这类需求主要服务于 Youtube 的 Up 主和内部的管理者。他们往往需要关注他们发布的内容的实时状态。这就导致了这个系统需要满足 (1)新数据能及时得到反馈 (2)老数据也能被获取 (3)支持复杂的查询。
  2. Embedded Statistics: 说人话就是在视频界面嵌入的一些数据,比如赞数,评论等等。它的特点是请求量大,并且对延迟要求很高,实时性要求也高。
  3. Monitoring: 监控需求和 Dashboard 有些相似,但是主要面向内部的工程师,同时在查询方面会有一些别的需求,比如采样,retention,更高阶的 aggregation 等等。
  4. Ad-Hoc Analysis: 对于数据分析师来说,有时候他们需要执行一些特定的 Query 来帮助他们理解产品的情况。比如刚上线了一个 UI 改动,想看看这个改动对于评论是否有刺激。这种场景下,Query 量虽然少,但往往千奇百怪,同时会涉及到大量数据。

而就像这篇论文的标题所说的,Procella 满足了所有这些需求

Procella 简介

Procella Architecture

上图是 Procella 的大概架构。Procella 是一个计算和存储分离的架构。这种类型的架构中,我们可以独立于数据量来 Scale 我们的计算资源。

数据存储

Procella 将数据保存在 Colossus 中,它是一个分布式文件系统,是 GFS 的继承人。数据也是以 Table 的形式组织的。

对于 Batch 数据(Bounded 数据)导入,数据直接以文件的形式存入文件系统中,同时向 Registration Server 注册元数据。

对于 Realtime 数据(Unbounded 数据)导入,数据会首先进入 Ingestion Server 中。这个服务会将数据以 WAL 的形式写入文件系统,同时也会发送给 Data Server。就像 BigTable 一下,存在一个 Compation 的过程,将 WAL 数据压缩为一个文件写入文件系统,并向 Registration Server 注册。

元数据维护

元数据主要包括 Table 的 Schema 数据,Table 到文件的映射关系等等。这些数据被存储在 BigTable 或者 Spanner 中。

数据查询

数据查询请求会发送到 Root Server 中,经过 compile,analyze,rewrite 等过程,构造一个树状的 plan,然后将这个 plan 拆成若干个部分发送给 Data ServerData Server负责从 Colossus 中读取数据,执行查询,将结果返回给负责 plan 中父节点的 Data Server 继续处理,这样不断递归,直到全部完成。

核心

接下来主要讲一下,我觉得这篇论文中提到的比较有意思的点。

任务粒度

这一点我想大家都知道,就是在切割任务的时候,我们希望能够少量多个,而不是只有几个很大的任务。少量多个优点主要是:

  1. 更好地利用并行度
  2. Fail over 更廉价。遇到一个节点特别慢,将任务发到其他节点代价也很低。

缓存利用

Procella 做了大量的数据缓存,包括

  1. 关于表的元数据
  2. 每个文件的元数据
  3. 实际的数据

这三部分的缓存互相独立,保证每个部分都有一定的内存可以使用。Procella 的设计保证了,如果内存足够大使得所有数据都能放入缓存,Procella 就和一个 In Memory 的数据库等价。这个看上去是一个很自然的情况,但实际上这需要一定的设计才能做到。

为了提高缓存的命中率,在计算调度的时候,会尽可能的将要执行的任务发送到离数据更近的节点上去计算。

注意,由于底层文件是 Immutable 的,所有不存在缓存一致性的问题。

数据格式

Procella 实现了一种新的列存储格式 Artus。它的特点主要是:

  1. 通过多 pass 的 encoding,在文件中保存了更多的元数据(比如最大值,最小值等等)。同时也利用这些元数据动态的调整 encoding 的方式。
  2. encoding 的方式允许在不 decode 的情况下,快速的执行 binary search 和 scan。

文件的元数据可以在 query 过程中大大的减少数据的读取量。比如一个 query 需要一个范围,而元数据中可以发现这个文件和指定的范围不重合。由于文件的元数据会得到缓存,所以减少了一个 RPC 调用。

查询优化

为了支持更低延迟的查询,Procella 处理常见的优化手段之外,自己又实现了一个 adaptive optimizer。它做的事情就是通过在 query 中,对实际的数据做一些分析收集工作,来自适应的重写接下来的 query plan。比如,在 join 的之前会收集两个表的大小,来决定 join 的方式。

总结一下

Procella 又是一个有 Google 特色的系统,它解决了一个可能只有 Google (再加上其他几个大公司)才会遇到的问题。也许大部分人都用不上 Procella,但是它的设计中还是有一些地方可以借鉴。我觉得有意思的地方主要是文件格式中的元数据和 adaptive optimizer。两者实际上都是通过数据本身的性质来对 Query 做优化。

文件格式中的元数据和整个系统的元数据不同,它保存在文件中,优点是节省了 Meta Data 的存储。缺点是需要一个 RPC 才能获取。在实际项目中,可能需要考量一下哪些元数据需要保存在哪里。

Adapter Optimizer 和很多关系型数据库维护的一些 stats 很像。相较于关系型数据中预计算的 stats,在查询中计算更灵活,收集的数据也更有针对性。但随之而来的自然是延迟的增加。因此,这类优化比较适合 Ad-Hoc 的场景,不太适合关系型数据库。Procella 在 Embedded Statics 这个场景中好像也是关掉了这个功能。