Gorilla：一种快速、可扩展的内存时间序列数据库（2016）

# Gorilla: 快速、可扩展的内存型时间序列数据库 来源：https://blog.acolyer.org/2016/05/03/gorilla-a-fast-scalable-in-memory-time-series-database/ Gorilla: 快速、可扩展的内存型时间序列数据库 (http://www.vldb.org/pvldb/vol8/p1816-teller.pdf) – Pelkonen 等人，2015年 Facebook 某个站点的错误率曾一度飙升 (https://www.usenix.org/conference/srecon15/program/presentation/nishtala)。问题最初是由一个名为 Gorilla 的内存型时间序列数据库触发的自动告警发现的，时间仅比问题出现晚了几分钟。一组工程师立即缓解了眼前的故障。另一组工程师则着手定位根本原因。他们启动了 Facebook 基于 Gorilla 构建的时间序列关联引擎，搜索与错误率相关的指标。结果发现，将发布版本的二进制文件复制到 Facebook 的 Web 服务器（这是一个常规操作）导致了整个站点的内存出现异常下降…… 在这篇论文发表前的18个月里，Gorilla 帮助 Facebook 的工程师发现并调试了多个类似的生产环境问题。 > 运营大规模服务的一个重要要求，就是准确监控底层系统的健康状况和性能，并在问题出现时快速发现并诊断。Facebook 使用时间序列数据库来存储系统测量数据点，并在其上提供快速的查询功能。 截至2015年春季，Facebook 的监控系统生成了超过20亿个独立的计数器时间序列，每秒新增约1200万个数据点——*每天超过1万亿个数据点*。以下是 Gorilla 的设计目标： - 存储20亿个独立时间序列，可通过字符串键标识 - 每分钟插入7亿个数据点（时间戳和浮点数值） - 保留最近26小时的数据以供快速查询 - 峰值查询量达到每秒40,000次 - 读取操作在一毫秒内完成 - 支持粒度最细为15秒的时间序列（每个时间序列每分钟4个点） - 两个内存副本（不同位置）用于灾难恢复 - 在服务器崩溃时仍能继续提供读取服务 - 支持对所有内存数据的快速扫描 - 处理时间序列数据每年翻倍的增长量 为了满足性能要求，Gorilla 被构建为一个*内存型*时间序列数据库，作为监控数据的*写穿缓存*，最终数据会写入 HBase 数据存储。为了满足在内存中存储26小时数据的需求，Gorilla 采用了一种新的时间序列压缩算法，平均可将数据大小压缩12倍。内存数据结构允许快速高效地扫描所有数据，同时保持对单个时间序列的常数时间查找。 > 监控数据中指定的键用于唯一标识一个时间序列。通过基于这些唯一的字符串键对所有监控数据进行分片，每个时间序列数据集可以映射到单个 Gorilla 主机。因此，我们只需添加新主机并调整分片函数，将新的时间序列数据映射到扩展后的主机集，即可扩展 Gorilla。18个月前，Gorilla 上线时，过去26小时内插入的所有时间序列数据集仅占用1.3TB 内存，均匀分布在20台机器上。此后，由于数据增长，我们不得不两次扩大集群规模，现在每个 Gorilla 集群运行在80台机器上。由于采用无共享架构并专注于水平扩展，这一过程非常简单。 内存数据结构基于 C++ 标准库中的无序映射。事实证明，这具有足够的性能，并且没有锁竞争问题。为了持久化，Gorilla 将数据存储在 GlusterFS 中，这是一个符合 POSIX 标准的分布式文件系统，具有3倍复制。"HDFS 或其他分布式文件系统也能轻松满足需求。"有关数据结构和 Gorilla 如何处理故障的更多详细信息，请参见论文的第4.3和4.4节。我在这里重点介绍 Gorilla 用于时间序列压缩以将所有数据装入内存的技术！ ### Gorilla 中的时间序列压缩 > Gorilla 对时间序列内的数据点进行压缩，而不对*跨*时间序列进行额外压缩。每个数据点是一对64位值，分别表示时间戳和该时间点的值。时间戳和值利用先前的信息分别进行压缩。 关于时间戳，一个关键观察是大多数源以固定间隔记录数据点（例如，每60秒一个点）。偶尔，数据点可能会提前或延迟一点记录（例如，一两秒），但这个偏差通常是有界的。现在我们进入了每个*比特*都很重要的世界，因此如果我们能用非常小的数字来表示连续的时间戳，我们就赢了……每个数据块用于存储两小时的数据。块头存储起始时间戳，对齐到两小时窗口。块中的第一个时间戳（两小时窗口开始后的第一个条目）然后作为与块开始时间的差值存储，使用14位。14位足以覆盖超过4小时的时间（以秒为单位），因此我们知道不需要更多。 对于所有后续时间戳，我们比较*差值*。假设块开始时间是02:00:00，第一个时间戳在62秒后，即02:01:02。下一个数据点在02:02:02，又过了60秒。比较这两个差值，第二个差值（60秒）比第一个差值（62秒）短2秒。所以我们记录 -2。我们应该用多少位来记录 -2？理想情况下越少越好！我们可以使用标记位来告诉我们实际值编码用了多少位。方案如下： 1. 计算*差值的差值*：*D = (tn – tn-1) – (tn-1 – tn-2)* 2. 根据下表对值进行编码： 这些时间范围的具体值是通过对生产系统中的一组真实时间序列进行采样，并选择能提供最佳压缩比的范围来确定的。 这产生了如下所示的数据流： > 图3显示了Gorilla中时间戳压缩的结果。我们发现大约96%的时间戳可以压缩到一个比特。 （即，96%的时间戳以规则间隔出现，因此差值的差值为零。） 时间戳说完了，数据值本身呢？ > 我们发现大多数时间序列中的值与其相邻数据点相比变化不大。此外，许多数据源只存储整数。这使我们能够将[25]中昂贵的预测方案调整为一个更简单的实现，仅比较当前值和前一个值。如果值相近，那么符号、指数和尾数的前几位将是相同的。我们利用这一点，计算当前值和前一个值的简单 XOR，而不是采用差值编码方案。 然后按如下方式对值进行编码： - 第一个值未压缩存储 - 对于所有后续值，与上一个值进行 XOR。如果 XOR 结果为0（即值相同），则存储单个比特 '0'。 - 如果 XOR 结果不为0，它仍然可能在“有效位”周围有多个前导零和尾随零。计算前导零的数量和尾随零的数量。例如，0x0003200000000000 有3个前导零和11个尾随零。存储单个比特 '1'，然后…… - 如果前一个存储的值也具有相同或更少的前导零，以及相同或更少的尾随零，那么我们知道当前要存储的值的所有有效位都落在前一个值的有效位范围内： 存储控制位 '0'，然后存储 XOR 后的有效位（例如上面的 032）。 - 如果有效位不在前一个值的有效位范围内，则存储控制位 '1'，然后在接下来的5位中存储前导零的数量，在接下来的6位中存储 XOR 后有效位的长度，最后存储 XOR 后值的有效位。 > 大约51%的值被压缩成一个比特，因为当前值和前一个值相同。大约30%的值使用控制位 '10' 压缩，平均压缩大小为26.6比特。其余19%的值使用控制位 '11' 压缩，平均大小为36.9比特，这是因为编码前导零位和有效位的长度需要额外的开销。 ### 在 Gorilla 之上构建 Gorilla 的低延迟处理（比其取代的旧系统快70倍以上）使 Facebook 团队能够在其上构建许多工具，包括：水平图；基于所有已完成存储桶每两小时更新一次的聚合汇总；以及在开篇案例研究中使用的关联引擎。 > 关联引擎计算皮尔逊积矩相关系数（PPMCC），该系数将测试时间序列与大量时间序列进行比较。我们发现，PPMCC 能够发现形状相似的时间序列之间的相关性，而无论其尺度如何，这极大地帮助了根因分析的自动化，并回答了“我的服务出问题时发生了什么？”这个问题。我们发现，这种方法给出了令人满意的答案，并且比文献中描述的其他类似方法[10, 18, 16]更容易实现。为了计算 PPMCC，测试时间序列连同所有时间序列键一起分发给每个 Gorilla 主机。然后，每个主机独立计算前 N 个相关的时间序列，按与目标序列的 PPMCC 绝对值排序，并返回时间序列值。未来，我们希望 Gorilla 能够在我们的监控时间序列数据上实现更高级的数据挖掘技术，例如文献中描述的聚类和异常检测技术[10, 11, 16]。 总结所学到的经验，作者提出了三个进一步的要点： 1. 优先考虑近期数据而非历史数据。当前为什么出问题比两天前为什么出问题更紧迫。 2. 读取延迟至关重要——没有这一点，建立在之上的更高级工具将不可行。 3. 高可用性优先于资源效率。 > 我们发现，构建一个可靠、容错的系统是这个项目中最耗时的部分。虽然团队在很短的时间内就原型化了一个高性能、压缩的内存型时间序列数据库，但使其具有容错性却花了几个月的艰苦工作。然而，当系统成功经受住真实和模拟故障时，容错性的优势显而易见。