Google Monarch，下一代内存时序数据库

对 Google Monarch 的了解，源于 LightSteps 中对于其引以为傲的时序数据库介绍。时序数据库在物联网(尤其是处于新基建的风口)蓬勃发展的今天尤其重要。时序数据库面临的主要问题之一就是数据洪流，而 Google Monarch 是目前业界公开的最大规模时序数据库集群(十万+主机)，其架构设计对于全球化的分布式系统设计有指导意义。

Google Monarch 并未开源，此处参考谷歌官方论文 Monarch: Google’s Planet-Scale In-Memory Time Series Database。

背景

谷歌原有的监控组件 Borgmon 在 2004～2014年爆发式增长中，遇到了以下问题:

• Borgmon 为去中心化组织架构，意味着每个团队单独维护自己的 Borgmon 实例，给业务团队造成了极大的负担
• Borgmon 没有 Schema, 会导致查询语句可能有语法歧义(semantic ambiguities), 降低了用户体验
• Borgmon 没有表达指标分布(distribution) 的字段类型，限制了快速进行类似 p99 查询的能力
• Borgmon 没有支撑全球化业务的能力，其要求客户手动处理将数据分区及构建查询。

于是 Google Monarch 从设计之处就肩负使命:

• 成为谷歌下一代监控系统，支撑超大规模数据
• 多租户(multi-tenant)，每个团队不必分开维护实例
• 数据有 Schema 并且支持 distribution 数据类型

最终，Google Monarch 从 2010 开始持续投入服务，目前已经存储了 PB 基本的压缩时序数据在内存中，并且每秒消费 TB 级别的原始监控数据，每秒钟进行上百万次查询。

架构

monarch-arch

Monarch 架构如上图所示。

其中 Zone 为区域性的集群，所有节点在同一地区。而 GLOBAL 则是总控集群，文中没有提到 GLOBAL 是否部署在同一区域。

Google 内部生产环境包括 38 个不同大小的 Zone，分布在 5 大洲，最大的 Zone 有 16000+ Leaves 实例

Monarch 将其服务分成了三个部分:

• state 部分
  • Global configuration server: 全局配置管理(存放在谷歌内部的 Spanner 数据库)，这是用户直接打交道的地方
  • Zonal configuration mirrors: 各个 Zone 内置的镜像配置服务器，对用户不可见，mirrors 和 global configuration server 保持同步。Mirror 的存在主要是为了防止 Zone 与 Global 直接的网络通路有问题导致配置完全不可用，可以更好的应对网络割裂(network partitions)
  • Leaves: 在内存中存储时序数据，通常一个 Zone 中有很多个 Leaves
  • Recovery logs: 负责内存时序数据的持久化存储
• data ingestion 部分
  • Ingestion routers: 这是系统最靠近用户的数据摄取组件。其作用是决定数据改被送往哪个 Zone, 注意其部署在 Monarch 核心集群之外，尽量靠近业务。
  • Leaf routers: 为 Zone 内部的服务。决定数据送往哪一个 Leaves
  • Range assigners: 为 Leaf routers 的辅助服务。决策数据所属的 Leaves，以均衡 Leaves 节点负载。
• query 部分
  • Mixers: 查询引擎
    • root mixers: 部署在 GLOBAL 区域，负责跨 Zone 的查询
    • zone mixers: 部署在 Zone 区域，负责 Zone 内的查询
    • 如果查询仅在 Zone 内便可以执行完成，便会下沉到 zone mixers 执行以减轻 root mixers 负载
  • Index servers: 索引服务，作为优化查询计划用
  • Evaluators: Monarch 允许用户定义 standing queries, 类似与 SQL 中的 View 视图，并定期执行后写回 Monarch，Evaluators 便是负责提交 standing queries 到 Mixers 执行

架构图中还包含了数据流向，在后文会详述。

设计思路

论文并未有这一节，个人根据论文事实，推演出来的 Monarch 团队解决问题的思路，以便对后面的细节有一定的心理预期。 Monarch 团队也提到: 架构设计并非是一开始就是如此，而是经过一步步演进成为现在的样子，所以这里仅供参考

首先，我们回想一下 Monarch 的设计目标

• 大规模，支撑全球化业务
• 多租户，进而意味着集群规模会非常大以及必要的隔离

首先，大规模集群是否意味着单中心的集群呢？

数据收集到一处意味着昂贵的带宽成本，这似乎不是非常好的选择，我们一般还是希望数据存放在靠近数据产生的地方。

这会导出第一个推论: 大规模集群需要由 N 个本地化集群构成，这就是前面所说的 Zone 集群。

那如果有些查询，需要跨 Zone 查询怎么办 ？根据大多数 MPP 架构的经验，将会需要一个称之为 Coordinator 的角色

• 接收查询请求
• 作为查询引擎，Parse Query => Logic Plan => Physical plan => Execute => Collect Result ... 这便是为何会需要 GLOBAL 集群。

有了大概的架构框架，我们来思考一下数据如何写入 Monarch。

首先，监控领域有两种数据摄取方式:

• Push: 被监控服务主动上报到监控后台
• Pull: 被监控服务提供接口，让监控系统主动拉取, 典型代表是 Prometheus 如何选型呢？思考一下，作为一个多租户监控系统，意味着要监控的服务个数可能十分巨大。这意味着:
• 如果选择 Pull，需要设计一个分布式系统去拉取数据
• 如果选择 Push，可以省下上面的服务 可见 Push 应该更好的选择，让我们选择 Push 方式，继续后续的讨论。

对于被监控服务，他们应该要有一个 SDK 来上报监控数据到 Monarch。

但是怎么确定上报到哪个 Zone 呢 ？这是谁决定呢 ？

我们是否可以给客户多个 Zone 的地址，由客户自己决定上报到哪里呢 ？这似乎不太好，增加了客户的心智负担。

Monarch 采取的策略是，客户上报数据中，有一个字段可以指示数据应该写入到哪个 Zone。

从此得出一个推论: 需要有一个服务接收客户上报的监控数据，并分发到合适的 Zone。这个服务便是 Ingestion routers

假设数据已经发送到了合适的 Zone，但 Zone 里面肯定不止一个主机可以承载数据，具体发送到哪个主机呢？这便是 Leaf routers 承担的职责。

站在 Leaf routers 的角度，我们思考三种可能性:

• 随机发送: 意味着每个主机都包含有各种各样的监控数据
• 按照 Hash 发送: 根据 key 的 Hash 值分发到固定一个主机
• 按照 Key Range 发送: key 位于一个范围的，发送到固定一台主机

这三种方式在写入上的区别不大(可能会影响压缩效率)，关键是会影响如何查询数据

• 随机发送: 意味着查询请求需要发送到所有存储节点
• 按照 Hash 发送: 意味着查询特定的key可以定位到节点，但是查询相连的多个key还是需要下沉到所有节点
• 按照 Key Range 发送: key 相似的可以集中到一个主机，但可能有数据热点，key 的分布不可能是平均的

做选择就可以知道，按照 Key Range 去决定存放位置，对查询是最友好的，但是不可避免数据热点，key 的分布不可能平均，会随着系统演进可能需要将 key range 进行重新分配。

这意味着:

• 需要有一个服务决策 key 的存储位置，即为 Range assigners
• 存储节点需要有进行负载均衡的能力，将在后文 Leavs 负载均衡 详述

假设数据终于送到了最终存储的节点，即为 Leaves

站在 Leaves 角度，我们思考一下，数据存放的几种可能性

• 本地 Disk
• 分布式文件系统 (如 HBase 写入 HDFS)
• 内存 + 分布式文件系统(持久化)

我们来思考这几种情况的优劣。

• 本地 Disk: 如果主机宕机会发生什么 ? 暂不考虑
• 分布式文件系统: 可靠性似乎没有问题，但是查询性能会不会很差呢 ?
• 内存 + 分布式文件系统(持久化): 似乎可以取得性能和数据可靠性的平衡

但是有几个问题需要面对。

• 内存是昂贵的资源，意味着数据需要尽可能压缩存储 (参考论文 4.1 Data Collection Overview)
• 是否可以采用 内存/分布式系统 冷热分离存储方案 ? Monarch 没有采用
• 是否可以进行预聚合，以减少写入到内存的数据量，这部分将在后文 数据预聚合 详述
• 内存数据刷鞋到分布式文件系统的时机是什么? 这部分将在后文 Admission window 详述

假设我们解决完这些问题，数据可以存放到内存。

那么，如何高效查询呢 ？我们在思考查询环节。

首先，由传统数据库对查询的优化思路，我们可以想到:

• 索引(Index): 对数据构建索引，以便快速查询
• 谓词下推(Predicate Pushdown): 尽量让查询在靠近数据位置的地方被计算，减少高昂的数据传输开销
• 构建多级缓存: Monarch 没有采用，因为数据已经在比较快速的内存了

我们来思考 索引(Index) 的可行性。

现代NoSQL系统为了高吞吐量，基本都舍弃了索引。因为要维护一个高速写入且不断更新的索引实在困难。

这一思路同样适用于 Monarch，构建传统的索引对于 Monarch 显得过于昂贵了。

我们来思考 谓词下推(Predicate Pushdown) 的可行性。

首先我们回想一下，Ingestion routers 可以根据数据中一个字段定位到特定的 Zone，意味着这个字段同样可以用于谓词下推(如果查询中使用了这个字段的话)。下推后可以将范围缩小到特定的 Zone。

现代的存储系统，一般都会支持一种叫 Bloom Filter 的特殊索引。

Bloom Filter 不能准确告诉你要查询的东西的位置，但是可以断言 一定不存在 于哪些位置。

这是一项十分优秀的能力，因为可以让查询引擎直接跳过一些存储单元。

最终，Monarch 并没有直接选取 Bloom Filter，而是选择了 Bloom Filter 相同思想的一种变体: trigrams，为了对模糊匹配查询更好的支持.

对于每个非value类型的字段，构建了称为 field hints index 的索引。提供这个索引的服务被 Monarch 命名为 index server。

field hints index 可以让查询下沉到 Leaves 层级，通常可以极大缩减查询规模，我们将在后文 Field Hints Index 详述。

Monarch 将负责查询的服务命名为 Mixers。

并且，为了实现多租户的特性，势必要对各个查询进行一定程度的隔离，我们将在后文 Query (查询) 详述。

至此，我们从 Monarch 设计者的角度出发，推导出 Monarch 架构的设计思路，后文将会针对其中未详述的部分展开。

DATA MODEL

Google 内部对 Schema 的认知随时间发生了极大变化。

这不只体现在 Borgmon 到 Monarch 的演变，也体现在 Borg => Omega => Kubernetes 的演变上。

似乎随着时间推移，Google 内部越来越重视 Schema，从我个人经验看，Schema 为工程定下约束的同时，也让工程朝着标准化的方向发展。

言归正传，Monarch 的 Schema 定义非常简单:

• 首先系统存储了无数个时间序列。
• 时间序列由两部分组成
  • Targets: 就是描述时间序列的主体，就是 Who
  • Metrics: 就是描述指标本身，指标由 一些维度 和 一个指标值(value)构成
• Target 和 Metric 都有名字，target_name 和 metric_name

示例如下:

Monarch-schema

此外，Targets 中所有字段和 Metrics 中维度相关的字段合在一起，构成了时间序列的 key

其中，value 字段类型可为下列一种:

• boolean
• int64
• double
• string
• distribution
• tuple of other types

其中 distribution 是 Monarch 定义的特殊类型，实际上为一个 double 列表。

distribution 由许多个 buckets 构成，每个 bucket 有一个 double 值，以延迟举例:

• 0 ～ 10 ms
• 10 ～ 20 ms
• 20 ～ 30 ms
• 30 + ms 可以定义上面 4 个 bucket，则 distribution 为 4 个 double 值组成。每个值代表落在 bucket 区间上的个数。

monarch-distribution

用户可以自定义 bucket 间隔和个数

Exemplars

每个 bucket 都可能携带 Exemplars，其实就是产生指标时现场更详细的现场信息，方便排查问题，对于延迟类指标，可能会附上 RPC tracing 作为 Exemplar

下图为 Exemplars 的使用示例:

monarch-examplar.png

数据摄取

前面 设计思路 小节已经简单叙述了数据流向，现在详细描述这一过程。

数据摄取分为四个步骤:

• 客户端发送数据到最近的 ingestion routers
• ingestion router 将数据发送到目标 Zone 的 leaf router，依据数据中可以判断 location 的字段
• leaf router 将数据依据 Target 将数据发送到合适的 leaves，数据可以有多个副本
• leaf 将数据写入 in-memory store，以及持久化存储为 recovery logs
  • 对 timestamp 进行优化编码
  • 对 value 值进行 delta 及 run-length 编码

leaf 写入 recovery logs 的存储介质为分布式文件系统(谷歌内部的Colossus), 并且有一个性能优化细节:

• leaf 将数据以针对写优化的格式写到 recovery logs
• 使用后台任务，将 recovery logs 周期性转换为读优化的格式方便快速加载

并且为了提高可用性，leaf 并不会等待数据写入 recovery logs。因为即使 recovery logs 完全不可用，系统也要正常提供服务。

Leavs 负载均衡 (Intra-zone Load Balancing)

前面我们说过，数据按照 key range 分布在多个 Leaves，而每个 Leaves 负责的 key range 并不是一成不变的，为了让各个 Leaves 的负载可以均衡，key range 可能会发生调整。

假设有一个高负载的 Leaf A，下面是调整的过程：

• 从 Leaf A 中已有的 key range 中分离一部分，我们称为 R
• 由 range assigner 选择一个负载轻的 Leaf B
• Leaf B 开始接收 R key range 中的数据
• Leaf B 等待 1 秒，待 Leaf A 中数据落盘到 recovery logs
• Leaf B 开始从 recovery logs 加载数据，优先加载最近的数据
• 等到 Leaf B 完全恢复数据后，Leaf A 解除对 R key range 的绑定，并删除相关的内存Store

期间，Leaf A 和 Leaf B 会同时采集数据，以保障数据可用性以及负载均衡操作失败时可回滚。

数据预聚合 (Collection Aggregation)

聚合收集的背景是，在源头处降低需要采集的时间序列个数。

文中举了 Disk I/O 例子，有数百万个磁盘服务实例，并且要区分处磁盘I/O具体由哪个员工负责(上万人)，从而可以产生最多百亿基本的时间序列。

但是实际使用中，可能只关心某个人在所有磁盘实例的I/O总量。

于是，在实际存入 Leaf 节点内存之前，可以进行一些预聚合来减少需要存储的数据量。

Delta time series

对于磁盘IO个数这种指标，通常是指从一个时间点开始的累计的(从操作系统视角就是累加的)。

但是累计值是无法聚合的，因为无法相加。

Monarch 的策略是将累计值切分成时间段的累加值，每个时间段上报最近时间段的 delta 值，而这个 delta 值是可以进行聚合的。

最终由 Leaf 节点进行最后的累加操作。

Bucketing

聚合是需要按照时间分片的，因为时间点无法做聚合，。

monarch-bucket

Admission window

既然按照时间分片聚合，意味着需要积攒旧的数据一小段时间(大于Bucket时长)，然后就可以执行聚合逻辑写入内存Store并且进一步持久化。

意味着，如果数据来的过晚，对应的 bucket 已经完成聚合，那么新到来的数据将无法得到处理而被丢弃。

处理这一过程被称之为 Admission window。

这个过程依赖各个节点有统一的时间基准，Google 使用内部的 TrueTime 技术来实现这项硬件约束。

此外，Bucket 时长TB是用户可以配置的(1s ≤ TB ≤ 60s)，实践中通常设置为 10 秒。

另外有一个实现细节，如果 Leaf 正在进行 Load Balancing，Bucket 时长TB会被临时调整为 1s 以便 Load Balancing 操作可以尽快完成。

经过上述的 Delta time series，Bucketing，Admission window 几个关键性技术，最终可以实现数据在收集时预聚合。

论文中未详述 delta 值是如何在 Leaf 节点聚合为累计值。

Query (查询)

monarch-query

Monarch 提供了类SQL的 DSL 语法来支持查询，如上图所示。

其实我个人有些质疑为何不直接使用 SQL 子集，这样可以使用庞大的 SQL 工具链。

查询部分有以下几个特征:

• Query tree: root mixer 接收查询请求，并下发给相关的 zone mixer，最终由 leaf 执行查询
• Level analysis: root => zone => leaf 三级，每级都尽量将查询下沉到子级，最终结果将最终汇总流回 root。各级之间使用令牌桶算法来限制上下级的数据传输速率以合理使用内存缓存
• Replica resolution: 为了提高可用性，可以设置多个副本，因为Leaf会进行会在均衡操作，因此一些Leaf可能会包含不完整的数据。最终会选择数据量最多的副本来查询
• User isolation: 因为 Monarch 被设计为多租户系统，用户之间的隔离就非常重要。再执行特定用户的查询时，查询线程会被分配到用户对应的 cgroups 中以此来限制CPU使用。查询使用的内存会被统计并且在达到阈值后取消查询执行

Query Pushdown

简而言之言之，Monarch 通过下面三种方式进行 Pushdown:

• 如果查询 Target 中的 location 字段，可以将查询下推到 Zone 级别，即 Pushdown to zone
• 通过 Target 计算 Key，从而确定所属的 key range，进而定位到对应的 Leaf，即 Pushdown to leaf
• 谓词下推，对于一个没有完全指定 Target 的全局聚合查询，如果一些字段指定了(如 filter cluster == "om"), 可以使用下文所述的 Field Hints Index 来缩小查询范围

Field Hints Index

field hints index (FHI)，顾名思义是对某一个字段做提示用的索引，用 hints 一词是因为其信息并不是非常精准。

如果我们直接索引对应的值在哪些zone/leaf，可能会消耗巨量的内存，因为这些值可能是无限多的。

而 Monarch 使用了一种 trigrams 方法，即只索引值的一组片段，这些片段的长度为3个字符，可能性为 26_26_26 = 17576 个(emmm, 似乎对中文不是非常友好)。

举例, 对 monarch 进行索引, ^^m, ^mo, mon, ona, nar, arc, rch, ch$, h$$ 被标记为 hit。对于查询 cluser=‘monarch’，那么需要同时满足上述所有 trigrams 都为 hit 才可以。

实际上这和 BloomFilter 有相似的思想，只是 trigrams 可以对模糊匹配有更好的支持。

需要注意的是 FHIs 在不同层级作用于不用的对象。在 Golbal 层级描述十分命中的对象是 Zone，在 Zone 层级则为 Leaf。

通过 FHIs，在 Zone 内部可以跳过 99.5% 的不相关 Leavs，在 root 层级这个比例为 80%。

monarch-FHI

上表显示了几个典型 zone， FHIs 占用存储的大小以及查询时裁剪比例以及裁剪后实际命中的比例。

此外，有一项巧妙的设计，Metric names 也被加入了索引(例如: /rpc/server/latency), 这使得 FHIs 可以在没有指定任何字段匹配条件的情况下进行下推。

配置管理

参考论文 6. CONFIGURATION MANAGEMENT 一节。

总结

下图可以观察到 Monarch 近几年显著的增长趋势。

monarch-scale

下图为查询时延分布，大多数查询时延为秒级(1秒内)，其中大量的查询为 Standing Query，即生成视图(猜测为聚合视图，便于观察和告警)

monarch-query-perf

对比 InfluxDB、OpenTSDB、Prometheus、tsdb 等业界常用的数据库，Monarch 将数据存放在内存而非二级存储，更能满足一些严苛的场景(critical monitoring), 且 Monarch 有更大的已验证集群体量及全球化部署特性 (论文中提及的优势 query aggregation 并非 Monarch 独有)

毫无疑问，Monarch 的体量成为了和其他时序数据库相比较时的一个巨大鸿沟。

在设计中，Monarch 采用了三层架构体系，root/zone/node，这使得 Monarch 可以扩展到非常大的量级。这种架构上的优势(复杂性)成为了其标榜自身为下一代内存时序数据库的资本。

此外，Monarch 团队贴心总结了几个架构设计关键点:

• 对时序数据的 key 进行 sharding 显著提升了系统的可伸缩性
• Push 而非 Pull，提升系统鲁棒性及让系统变简单(尝试过Pull)
• Schema 很重要
• 系统规模扩张是一个循序渐进的过程
• 多租户对用户是方便的，对于开发者面临很多挑战

细节可以阅读论文 9. LESSONS LEARNED 一节。

Monarch 的设计我个人觉得还是有一些局限性:

• 查询中以 Standing Query 为主(95%)，而这些 Standing Query 是否可以在其他阶段消化，而不用占用宝贵的查询资源呢 ？
• location 的概念过于隐性，既然其在系统承担了重要的作用，就应当在 schema 设计中显式声明
• 自定义查询语言不如直接使用SQL，降低用户学习成本

总之，Monarch 很强大，并且到处闪烁着精致的设计细节，值得学习～