Google准实时数据仓库Mesa（一）

本文来自网易云社区

作者：王潘安

以下是本人在学习Google的Mesa数据仓库论文的记录，翻译出来给大家分享，翻译水平有限，请多多包涵。因论文比较长，本人将论文按照Mesa不同的模块分开翻译，方便阅读。

摘要：Mesa是一个可伸缩性的分析型数据仓库系统，它主要为Google的互联网广告业务服务。Mesa的设计是为了满足一系列的来自用户和系统的复杂的挑战。包括近乎实时的数据获取和查询，高可用性，可靠性，容错性以及伸缩性。Mesa每秒处理PB级的数据以及百万行的更新。每天服务十亿次查询，获取万亿行数据。Mesa是一个跨多个数据中心的数据仓库，它提供一致的，可重复，低延迟的查询服务，即使是在一个数据中心完全瘫痪的情况下。

一．介绍

　　随着业务量的增大，数据的处理，存储和查询都面临挑战。对数据存储的要求有如下几点（此处省略一堆废话）：

　　原子更新。一个单用户的操作就可能引起相关数据的多次更新，影响大量的定义在跨多维度上的多指标集的一致性视图。不允许存在对系统进行查询时，只有一部分数据更新成功的情况。

　　一致性和正确性。出于商业和法律上的考虑。系统必须返回一致和正确的数据。即使一个查询跨多个数据中心，我们也要提供强一致性和可重复的查询结果。

        可用性。系统不允许出现单点故障。不会出现由于计划中或非计划中的维护或故障所造成的停机，即使出现影响整个数据中心或地域性的断电也不能造成停机。      　　　

        近实时的更新。系统必须支持大约每秒几百万行规模的持续更新，包括添加新数据行和对现有数据行的增量更新。这些更新必须在几分钟内对跨不同视图和数据中心的查询可见。

        查询性能。系统必须对那些对时间延迟敏感的用户提供支持，按照超低延迟的要求为他们提供实时的客户报表，而进行批处理的用户需要非常高的吞吐量。总的来说，系统必须支持将99%的点查询的延迟控制在数百毫秒之内，并且整体查询控制在每天获取万亿行的吞吐量。

　　可伸缩性。系统规模必须可以随着数据规模和查询总量的增长而伸展。举个例子，它必须支持万亿行规模和PB级的数据。但是即使上述参数再出现显著增长，更新和查询的性能必须仍然得以保持。

　　在线的数据和元数据转换。为了支持新功能的发布或对现有数据粒度的变更，客户端经常需要对数据模式进行转换或对现有数据的值进行修改。这些变更必须对正常的查询和更新操作没有干扰。

　　Mesa是针对这些技术上和操作上的挑战的解决方案。尽管这些需求的某一部分已经被现有的数据仓库系统解决了。Mesa是一个能同时解决上述问题的解决方案。Mesa是一个针对结构化数据的分布式，可备份并且高可用的数据处理，存储和查询系统。Mesa从生成数据的流服务中获取数据，在内部进行聚合和持久化，通过查询给用户提供服务。尽管这篇论文主要讨论的是广告业务，但是Mesa是一个能满足上述所有需求的通用的数据仓库。　

　　Mesa利用谷歌的基础设施和服务，比如Colossus(谷歌下一代的分布式文件系统)，BigTable以及MapReduce，将数据被水平分片和备份，来实现存储的可扩展性和可用性。更新操作可能会发生在一个单表的粒度上或者跨多张表。为了实现一致性以及满足在更新的时候的反复查询，基础数据是多版本的。为了实现数据更新的可扩展性，数据是批量的，带版本号的，周期性的合并进入Mesa中的。为了实现跨多数据中心的更新一致性，Mesa使用基于Paxos的分布式一致性协议。

　　  许多基于关系型和数据立方体的数据仓库产品不支持在给用户提供近实时查询的同时，每几分钟就将数据仓库中的数据连续的集成和汇聚。通常，这些解决方法都是与传统企业数据仓库相关的。在传统企业数据仓库中，数据汇聚进入数据仓库的频率低，通常是按天或者周汇聚。类似的，谷歌内部的关于大数据的技术，比如说BigTable, Megastore, Spanner和F1，也都不能满足这个场景。BigTable不能满足Mesa提出的必要的原子性的需求。Megastore, Spanner和F1通常用来处理线上业务，他们支持跨地域的数据的强一致性，但是它们不能满足Mesa更新操作吞吐量的峰值。但是，Mesa确实使用了BigTable和Paxos技术以及Spanner的元数据存储的技术。

　　（这段实在不想翻译了。总之，目前市面上的大数据产品都不行！真是狂拽酷炫吊炸天！）

　　这篇论文的贡献主要如下：

• 我们展示了如何创建一个PB级数据仓库，同时又拥有ACID这些事物性处理功能的系统。并且它可伸缩，来满足谷歌高吞吐率的广告指标。

• 我们描述了一个版本管理系统，它使得高吞吐量的批量更新操作在可接受的延迟内完成，同时也支持大量的查询在低延迟下完成。

• 我们描述了一个高扩展性的分布式架构，在单数据中心中，它可以从宕机和网络故障中恢复。我们也展示了一个跨地域备份的架构来应对数据中心的瘫痪。这种设计的不同之处在于，业务数据是通过独立且冗余的进程在多数据中心间异步备份。只有关键的元数据是同步的拷贝到每个地方。这种技术可以使跨数据中心的同步代价最小，并且还可以提供高吞吐的更新操作。

• 我们展示了如何在不影响正确性和已存在应用的性能的条件下，动态和高效的处理大量表模型的变化。

• 我们描述了应对由硬件或者软件引起的数据错误的关键技术。

• 我们描述了这种规模的系统在保证正确性，一致性和性能上的挑战。并且提出几点供新的研究来改进。

二 .  Mesa存储子系统

       Mesa中的数据持续不断的生成，它是谷歌量级最大，价值最高的数据集。在这个数据集上的分析型查询包括简单的查询，诸如：“某一个特定的广告在某一天有多少点击量？”和涉及更多内容的查询，诸如：“某一个特定的广告，在十月份第一个星期的上午8点到11点间，通过移动设备在某个特定的地理位置，通过关键字decaf在google.com上搜索获得的点击量是多少？”

　　数据在Mesa中以多维模型存放，它依据不同的维度获取了所有谷歌广告平台上最细节的事实。这些事实由两部分属性组成：维度属性（我们称为键）和度量属性（我们称为值）。因为很多维度属性是分层的，甚至有多层，比如日期维度中年/月/日或者周/季度/年。那么单一事实就需要根据这些层次维度汇聚成多个物化视图，来满足数据分析中的上卷和下钻操作。一个谨慎的数据仓库设计要求一个事实在多个聚合和物化中保持一致性。

2.1 数据模型

　　在Mesa中，数据以表的形式存储。每张表有它的模型（schema）来描述它的结构。一个表模型有它的键空间Ｋ和相应的值空间Ｖ，Ｋ和Ｖ在这里都是集合。表模型也有它的聚合函数Ｆ: V × V -> V 用来聚合跟同一键相关的多个值。聚合函数必须满足结合律。在很多情况下，它也满足交换律，尽管Mesa中包含不满足交换律的聚合函数。表模型中也包含一个或者多个K的全序索引。

        键空间K和值空间V表现为列的二元组。他们都有固定的数据类型，表模型为每个单独的列指定了聚合函数F，F隐式的定义成如下形式（译者注：说白了，就是把V放在一起写，对应于每个二元组的聚合函数不单独写出来，统一写成个F）：

         F((x1,.....,xk),(y1,.....yk)) = (f1(x1, y1),......fk(xk, yk))

其中(x1,.....,xk)和(y1,.....yk)都属于V，f1....fk这种形式是聚合函数的显式表现形式。（真蛋疼）

        举个例子。图片1展示了Mesa中的三个表。这三张表都包含广告的点击量和费用，只不过被分散到不同的属性中，比如按天的点击量，（译者注：图中的Date, PublisherId, Country, AdvertiserId都是key， Clicks和Cost是value）。作用于所有列的聚合函数是SUM。假设相同的底层事件更新了这三张表的数据，那么所有的指标都被一致的表现在三个表中。表1只是简单的呈现了表模型。在生产环境中，Mesa包含上千张表，每张表包含上百列，使用多个聚合函数。

2.2 更新和查询

        为了实现大吞吐量的更新操作，Mesa采用批量更新。这些更新的批量包产生于Mesa系统外的上游系统，每隔几分钟产生（更小的频率更高的更新包可以使更新操作延迟低，但是它需要消耗更多的资源）。每次更新，Mesa都会指定一个版本号 n (从0开始的序列)以及这些更新行的构成（表名，键，值）。每一个（表名，键）至多包含一个汇聚值。

        Mesa上的一个查询包含一个版本号 n 和 键空间上的谓语P。返回值包含一行符合条件P的键，这些键出现在一些更新中并带上了版本号0到n。而数据值按照表结构中定义的聚合函数进行聚合后，返回聚合值。Mesa实际上支持更复杂的查询功能，但是所有的都可以看成对这种基本查询的预处理和后加工。

        举个例子，图片2中的展示了两次关于图片1中的表的更新操作。为了保证表的一致性，每个更新操作包含对两个表A,B的一致性的行（译者注：说白了，就是要同时更新两个表中的某一行），Mesa会自动算出表C的更新操作，这是因为它可以直接源自表B的更新操作。理论上说，一个单次的更新操作同时包含AdvertiserId和PublisherId属性也可以被用作更新这三张表，但是这个代价比较大，特别是在表包含大量的属性的情况下。

        注意表C与以下这个表B的物化视图的关系：SELECT SUM(Clicks), SUM(Cost) GROUP BY AdvertiserId, Country. 这个查询可以直接当作Mesa中的表，这是因为查询中的SUM函数就是对表B中所有度量值列的汇聚函数。Mesa约束在所有的度量列上使用相同的聚合函数，才能称作物化视图。

        为了使更新原子性，Mesa采用了多版本的方法。Mesa按版本号的顺序执行更新操作。通过在执行下一条更新操作之前完全合并此次更新操作来确保原子性。用户永远感受不到局部合并更新带来的影响。

        严格的按顺序更新带来的不仅仅是原子性的应用。Mesa中的有些聚合函数不满足交换律，比如在标准的Key-Value存储中，一个(Key, Value)的更新完全覆盖它之前的值。更细致的来看，按顺序的约束使得Mesa支持将错误的事实用相反的行为来表示。特别的，谷歌使用欺诈探测来决定广告的点击是否合法。欺诈性的点击可以用相反的事实来表示。比如在上图2中，就可以跟一个版本2的更新，这个更新包括负值的点击数和费用，去标记之前处理的点击数是非法的。通过严格的按顺序更新，Mesa保证了负的更新事实永远不会在它的正事实之前被合并。

2.3 数据版本管理

         数据版本在Mesa的更新和查询中扮演了十分重要的角色。但是它也带来了很多挑战。首先，对于那些可以被聚合的广告统计数据，单独存储每一个版本从存储的角度来看非常昂贵。聚合后的数据量就要小的多。其次，在查询的时候，遍历所有的版本并且聚合它们的代价也很大，并且会加大查询的延迟。再次，在每次更新时都提前聚合所有的版本也需要极高的代价。

        为了处理这个问题。Mesa提前聚合某些版本的数据并且使用deltas存储（译者注：说白了就是分版本区间存储），每一个delta包含一组不重复键的数据，以及一个delta版本号，用[V1, V2]表示，其中V1和V2是更新操作版本号，并且V1小于或等于V2。我们用版本号来表示delta就很清楚了。delta[V1, V2]中的行指的是那些出现在版本号为V1和V2之间的更新操作的键，值对应的就是这些更新操作聚合后的值。更新操作被当做是一个单例delta合并进Mesa。一个单例delta版本[V1, V2]满足V1=V2=n, 其中n就是此次更新的版本号。

        delta[V1, V2]和delta[V2+1, V3]可以通过简单的合并键/聚合值的方式合并成一个delta[V1, V3]（2.4章节中会讨论，所有的行都是以键的方式存储的，所以说，两个delta可以在线性时间内合并完成），这个计算的正确性是由聚合函数F确保的。这个正确性并不依赖函数F的交换律。无论何时Mesa通过一个给定的键合并两个值时，delta的版本都是形如[V1, V2]和[V2+1, V3]的，并且这个操作是在不断增长的有序版本号上进行的。

        Mesa仅仅允许用户查询一段时间以内的所有版本，比如24小时以内的。这就说明，早于这个时间的版本就可以聚合到一个基础delta中，设它的版本号为[0, B], 其中B大于或等于0，这样，任意一个delta[V1, V2]只要满足0 <= V1 <= V2 <= B就可以被删除。这个过程被称为base compaction（基础压缩聚合，译者注：真不知道该如何翻译这个专业名词）。Mesa同其他操作，比如查询和更新，并发的异步执行这个base compaction操作。

        注意一下，跟更新版本有关的的时间是由那个版本生成的，它独立于数据中的任何时间信息。举个例子，图1中的Mesa表，数据中的2014/01/01这个时间是永远不会被移除的。Mesa可能会拒绝超过某个时间后的版本的查询。数据中的时间数据其实是另外一个属性并且它对Mesa不透明（译者注：提醒读者数据中的时间和Mesa中记录版本的时间不要混为一谈）。

        有了base compaction， 回答某个版本n上的查询，我们可以聚合一个基本的delta[0, B]和一系列单例delta[B+1, B+1]. [B+2, B+2],...,[n,n]，然后返回值。虽然我们经常的聚合成一个基础delta（比如说每天），但是我们的单例delta个数很容易上百，甚至上千，特别是对于那些更新密集的表。为了支持更高效的查询，Mesa包含了一些形如[U,V]的累积delta D，其中B < U < V。这些累积的delta可以被用来求解一个版本n的delta划分，比如{[0, B],[B+1, V1],[V1+1, V2],...,[Vk+1, n]}，这样就比直接使用单例delta需要更少的聚合操作。当然，这些累积delta也需要一些处理和存储上的开销。但是这些开销被分摊到了所有的操作中去了，特别是查询操作。所以用这些delta代替单例delta是可行的。

         delta的聚合策略决定了每个时刻deta在Mesa上是如何维护的。它的基本目的是平衡那些查询操作，更新操作以及处理和存储累积delta的开销。这个delta的策略要考虑三件事情：1. 哪些delta（除了单例delta）需要优先生成来满足这些更新版本可以被查询到。这个操作是在更新路径上同步进行的，会降低更新的速度。2. 哪些delta是可以在更新路径以外异步的生成的。3. 那些delta是可以被删除的。

         如图3所示的一个delta汇聚策略就是一个双重级别的策略。在这种策略中，任何时刻都存在一个基本delta[0, B], 一系列的累积delta[B+1, B+10], [B+1, B+20],[B+1, B+30],...以及B以后的所有单例delta。每当第B+10X个版本合并时，就异步的生成delta[B+1, B+10X]。新的基础delta[0, B1]每天生成一次，但是这个新的基础delta在所有基于它的累积delta还没完全生成之前是不可用的。当基础delta B切换到B1时，这个策略就将老的基础delta，累积delta以及所有B1版本之前的单例delta删除。这样的话，一个查询就只需要一个基础delta，一个累积delta和几个单例delta组合完成，大大减少了查询时的工作量。

         Mesa目前所使用的是两级别delta的变种策略，它使用多种级别的累积delta，对于最近的版本，累积delta包含少量的单例delta，对于比较老的版本，累积delta包含较多的单例delta。一个delta层级可能包含一个基础delta，一个包含100个版本的delta，一个包含10个版本的累积delta，以及多个单例delta。类似的基于日志结构的存储引擎有LevelDB和BigTable。我们注意到，基于差异更新的Mesa维护数据的方式，是一个简单的对不同存储模型的适配。并且它可以被用于增长性视图和列存的更新。（译者注：我真看不懂这句话，随便翻译的。）

2.4 物理数据和索引形式

        Mesa中的delta是基于delta聚合策略来创建和删除的。一旦delta被创建，它就是不可变的，所以物理的存储结构不需要支持高效的增量更新。

        不可变的delta就允许Mesa使用一个相当简单的存储结构。因为存储是Mesa的主要开销，因此，对这种存储结构的基本要求就是省空间。Mesa还必须支持根据键的快速查找，因为一个查询往往关系几个delta，然后根据键将值聚合起来。为了使查询键变的高效，每个Mesa表包含一个或多个表索引，每个表索引都包含一个根据索引排序的数据的拷贝（译者注：空间换时间咯）。

        存储结构的细节比较偏向技术，所以我们只关注最重要的部分。delta中的行按顺序存储在有大小限制的数据文件中（这是针对文件系统文件大小限制的优化）。这些行本身被组织在行块中，每个行块被单独的变换和压缩。每个行块中的数据按列式存储来进行变换压缩，提高压缩率。因为存储是Mesa主要的开销，并且在查询时解压性能比写入时压缩性能重要。所以我们在选用压缩算法的时候更强调压缩比和解压速率。

        Mesa为每份数据文件存储一份索引文件。每个索引实例包含一个行块的短键，这个短键由这个行块第一个键的固定长度前缀以及这个压缩行块在数据文件中的偏移量组成。那么查询一个指定的键的算法就可以分为两步，首先通过二分法从索引文件中找出可能包含这个短键的行块，然后在这个压缩的行块中通过二分法找到想要的键。

这一篇就翻译到这里，其中的思想很值得借鉴，有些开源的项目已经采用了部分技术。下一篇我们一起看看Mesa的架构。

网易云免费体验馆，0成本体验20+款云产品！

更多网易研发、产品、运营经验分享请访问网易云社区。

相关文章：
【推荐】 #3.14 Piday#我的圆周率日
【推荐】 一个接口的性能问题定位和分析过程