Google Mesa 项目论文笔记

Google Mesa 是指标分析型数据仓库,主要服务于 Google AD 业务。本文抽离自 Apache Doris 的研究笔记,因此仅记录了论文中核心设计部分,省略了前置背景说明以及没有太关注的地方,原始全文是Mesa: Geo-Replicated, Near Real-Time, Scalable Data Warehousing

存储结构

版本管理

  • 定义 $deltas$ 为数据存储的一系列物理文件,每个 $delta$ 中包含数据行和以 $\rm [V1, V2]$ 形式描述的版本号,代表着该 $delta$ 是从 $\rm V1 \sim V2$ 版本的指标列聚合结果;
  • 定义 $singleton \ delta$ (简称 $singleton$)为版本号形如 $\rm [V1, V1]$,代表着该 $singleton$ 记录的是 $\rm V1$ 单版本的未被聚合的明细数据。
  • 对于 Mesa,仅提供查询当天明细(原文表述方式是 24 小时内用户可以查询特定的版本),24 小时之前只能查询聚合结果,因此 Google 给出其独特的 Compaction 实现,
    1. Base Compaction,实施合并的周期是每一天,其合并后的版本号从 0 开始。
    2. Cumulative Compaction,每更新 10 版本进行增量构建。
  • 分析可得,
    1. 在查询历史聚合结果时,只需查询 1 份 Base Compaction 的 $delta$ 、1 份 Cumulative Compaction 的 $delta$ 以及最多不超过 10 份的 $singletons$。
    2. 在查询当天明细结果时,只需返回当天特定版本的 $singletons$ 中的明细数据即可。

前缀索引

  • 在记录数据的同时,同时写入名为 $short \ key$ 的前缀索引,索引键取自固定长度的前缀。

系统架构

单实例模型

每个 Mesa 实例由两个子系统组成,更新&维护子系统、查询子系统。

  • 更新与维护子系统,用于保障当前实例数据的版本更新、查询优化等功能,采用 Controller 与 Workers 架构,物理数据存储在 Google 新一代文件系统 Colossus 上(相当于 S3,据有限的资料显示是基于 BigTable 实现元数据存储,而物理数据则被优化地存储在 GFS)。
  • 查询子系统,不支持 Join。
  • 把相似的查询请求(比如查询同一张表),发送到同一组查询服务器,以提高缓存命中率。

跨数据中心多实例模型

在单实例的背景下,增加了两个部件,Committer 版本提交器角色与像 ZK 一样的 Versions Database 版本信息数据库,通过控制版本的可见性以实现一致性更新,这个方法也同样适用于,一张表中有多物化视图时,相关联表的更新一致性控制。

高级特性

查询优化

  • 非前缀键的查询,尝试补充前缀键去检验索引,检验的性能取决于前缀键的基数
  • 在查询时使用 $resume \ key$,当查询服务器 Fault 的时候可以继续从上次中断处恢复

Workers 并行化

Workers 是更新与维护子系统的执行节点,执行 Compaction、表结构变更、数据校验任务,这些任务的共性都是依赖顺序扫描,然后形成一份新的全量数据,于是借鉴 MapReduce 思想,分解任务,再分配给 Workers 集合。

这里有一个困难点 —— 如何平均分配每个 Worker 任务的分区范围?

方法是基于采样,

  • 定义 $n$ 为某一任务所需扫描的总行数(总任务量)
  • 定义 $m$ 为某一任务中关联的 $deltas$ 文件集
  • 定义 $p$ 是期望的分区数(并行度)
  • 定义 $s$ 为采样密度(缩放倍率),比如 $s = 1024$,代表采集每 1024 的整倍数行

理想情况下,每个分区扫描的行数应为 $n/p$,但这需要一次全量顺序扫描以决定分区键。

采样的方法是,假设 $s=1024$,只需要对 $m$ 集合的每个 $delta$ 文件,单点查询第 $[0, 1024, ..]$ 行,构建 <行键,权重> 映射(权重 = s * 此行键出现次数,理想情况下,总权重 = 总行数 n),通过行集的键排序,辅以权重,可计算出分区键。

并且可计算得最坏情况是,一个键在采样时,只出现 1 次,但事实上,每个 $deltas$ 内部都重复了 $s$ 行(但不会超过 $s$ 行,因为超过必然会被采集到),也就是错误量被限定为 $(m-1)s$,因此,单分区最大扫描行数是理想情况与错误量之和,即 $(n/p)+(m-1)s$。

由于通常 $m$ 在现实上会控制得非常小(为了查询速度),所以 $s$ 可以非常大,因此在该 MapReduce 任务启动时的准备工作的耗时也是非常短的。

另外,由于并行化,每个 Reducer 将写出单独的一份文件,因此,合并过程并不会像 HBase 那样只生成一份文件,而是生成全局有序的多份文件,在点查时二分。实际上,在 Apache Doris 也是如此设计,但未实现 Worker 并行化。

快速在线的表结构变更

在 Mesa 中,表结构变更的首要需求是在线,即,操作不能阻塞用户的所有查询或更新。

一个常规的方法是,

  1. 创建表的副本,并赋予新的版本号
  2. 重放(Replay)创建副本时的更新操作
  3. 切换读写到新表,即修改 Mesa 元数据,把操作路由到新表

另一种更快速的方法 $Linked \ Schema \ Change$,但论文中并没有说具体实现,大致想法是把表结构变更变成一种可合并的更新操作,在查询时,根据新的表结构对新增的列填充默认值返回结果。(根据这个想法,或许可以直接添加转换层,对旧版的 $deltas$ 通过转换层的映射函数实现表结构变更)

数据一致性检测

由于 Mesa 通常是多数据中心多实例部署,如何比对多实例的数据一致性就成了核心问题。

论文中提出两种方法,分别是全面的离线检测方法与轻量级检测方法,

  • 全面的离线检测方法
    • 基于行序依赖的强一致性检测(Strong Row-order-dependent Checksum)
      它是 hash( hash( hash( row1 ) + row2 ) + row3 )..结构,
      在每次求校验码的时候传入上一行求得的校验码,因此得到行序依赖的校验码。
    • 基于索引的行序无关的弱一致性检测(Weak Row-order-independent Checksum)
      仅用于检测索引,由于行序无关,文中无详细记载,可能是索引抽样比对。
  • 轻量级检测方法
    • 基于元数据中聚合值的一致性检测(Global Aggregate Value Checker)
      仅用于检测上一次更新的数据,通过对比 $delta$ 文件中元数据的聚合值判断一致性。
      (原文并没有展开说聚合值包含什么,但大概猜测是行数、最大最小值之类的)

其他的,像单实例内部的有序性检测(比如刷写磁盘之前数据是否有序)、损坏的数据可以从不同实例中拷贝恢复的特性就不说了,它们都是显而易见的。

发表评论

您的电子邮箱地址不会被公开。