声明：此文核心内容源自Facebook在2015年发表的论文《Gorilla: A Fast, Scalable, In-Memory Time Series DataBase》, 但本文大部分内容为笔者在精读论文以后做的总结，内容组织形式也有较大的出入。本文所有的图片均源自该论文。

基本概念

以监控数据为例，介绍时序数据库的两个重要概念“Time Series”与“Data Point”：

• Time Series

一个数据源的一个指标，按固定时间间隔产生的源源不断的监控数据，称之为Time Series，中文通常将其翻译成”时间线”。”按固定时间间隔”是一种理想假设，会存在少量的异常情形。

例如： 我们希望收集每一台物理机上的CPU使用率信息，物理机Host A上的CPU 1，就是一个确定的数据源，而CPU使用率就是指标信息，假设我们收集指标的时间间隔为5秒钟，那么，Host A上CPU 1上按5秒钟间隔产生的所有指标数据，就称之为一个Time Series，而物理机Host A上的CPU 2的CPU使用率信息则属于另外一个独立的Time Series。从这个定义上来看，一个Time Series本身是无时间边界的，只能说，在某一个时刻，最老的与最新的指标数据是什么。

• Data Point

Time Series中按固定时间间隔产生的每一条监控数据，称之为一个Data Point。即，Data Point是构成Time Series的基本数据单元。继续上面的例子，Host A的CPU 1的每一条CPU使用率信息，就是一个Data Point。

一个Data Point中至少包含两个关键组成部分：Timestamp信息，Point Value信息（具体的指标值）。

正文内容

对于一个数据库系统而言，保障用户数据不丢失通常是设计的第一要则，而数据可靠性的提升往往是以牺牲系统吞吐量为代价的。

今天，我们要谈论的，就是一款在故障场景下允许丢失少量数据的时序数据库技术，即Facebook的Gorilla。

Facebook在2015年发表的一篇论文详细介绍了Gorilla的技术细节，这篇论文名为《Gorilla: A Fast, Scalable, In-Memory Time Series DataBase》，此文正是对这篇论文的详细解读。Gorilla的部分设计思路非常值得借鉴，而且已被应用于其它的时序数据库技术中。

Gorilla源自Facebook对于内部基础设施的近乎”变态”的监控需求，我们先来看看这些数据：

• 20亿个不同的Time Series

• 每分钟产生7亿个Data Points，即每秒钟产生1200万个Data Points

• 数据需要存储26个小时

• 高峰期的查询高达40000次每秒

• 查询时延需要小于1ms

• 每个 Time Series每分钟可产生4个Data Points

• 每年的数据增长率为200%

对于监控数据，本身还具有如下几个典型特点：

• 重写轻读

• 以聚合分析为主，几乎不存在针对单Data Point的点查场景。因此，即使丢失个别的Data Points，一般不会影响到整体的分析结果。

• 越老的数据价值越低，而应用通常只读取最近发生的数据。Facebook的统计表明，85%的查询与最近26个小时的数据写入有关。

Facebook的监控系统主要依赖于ODS(Operational Data Store)，它提供了基础的TSDB能力，查询服务，问题发现与告警系统。在Gorilla之前，ODS完全基于HBase构建，Time Series数据由ODS Write Service收集后写到HBase中。但直接基于HBase的读取，P90时延过高，应用不得不在查询场景上做一些舍弃。如果在ODS中添加一层Read-Through Cache，当Cache未命中时直接读取HBase代价依然是过高的。在Gorilla之前，Facebook也考虑过基于Memcached作为Write-Through Cache的方案，但新增Data Point需要先读取已有的Time Series，更新后再写回到Memcached，这会导致Memcached的负载过重。

Write-Through Cache与Read-Through Cache

Write-Through Cache: 新数据写入到Cache的同时也写入到后端持久化存储系统中。

Read-Through Cache: 读取时先读取Cache，如果Cache中不存在，则触发一次后端持久化存储系统的读取操作，从而将数据加载到Cache中，而后返回给客户端。

现有的其它时序数据库技术，典型如OpenTSDB，InfluxDB，都是基于Disk的设计，显然无法满足Facebook的监控需求。

Gorilla可以说在深刻理解了的监控数据/时序数据的特点基础上，很好的满足了Facebook自身的需求。纵观整篇论文，其关键技术点可以总结为如下几个方面：

- 基于内存的设计。针对时序数据，设计了高效的内存数据结构，可支持高效的时序数据扫描，针对单个Time Series查询时可提供稳定的低时延保障。

- 高效的压缩算法。对DataPoint中的Timestamp与Point Value的数据特点提出了针对性的压缩编码机制，压缩效果显著，存储空间节省90%以上，单个Data Point平均只占用1.37 Bytes。该压缩机制有力支撑了基于内存的整体设计方案。

- 先缓存后批量写日志。流式写入到Gorilla中的数据，先缓存到一个64KB大小后，写入到一个Append-Only的日志文件中。如果在数据未写满64KB之前，进程故障会导致数据丢失，而Gorilla容忍这种数据丢失场景。以少量的数据丢失换取写入的高吞吐量。

- 无状态易扩展。基于Shared-Nothing的设计，可以轻易实现数据节点的横向扩展。

- 跨Region双活集群。利用部署在两个Region区的两个集群来提升服务的高可用性

Gorilla/ODS的一个Data Point由如下的三元组构成：

{string key, timestamp, point value}

与OpenTSDB、InfluxDB的模型相对比，Gorilla因舍弃了Tag的设计而显得更加简洁。Gorilla依赖于额外的元数据信息去索引string key，与Time Series数据相比，这部分数据显得非常轻量级，但在整篇论文中，这里并没有过多提及。

Gorilla的数据分片称之为Shard，数据节点称之为Gorilla Host。Shard被分配在一个Host中提供读写服务，Shard与Host的关系，类似于HBase中的Region与RegionServer的关系。Shard分配工作由基于Paxos实现的ShardManager负责。

一个Data Point，按照string key进行Hash运算后，匹配到对应的Shard，再由Shard的路由信息找到对应的Host。随着时间的不断推移，新的Time Series不断被加入，而Gorilla的Hosts可以轻易扩展，扩展后，只需要简单的调整分片规则让新的Time Series映射到新的Hosts中即可。

基于磁盘的读取方式，是无法满足高并发、低时延的查询需求的。Facebook统计了ODS中的查询后发现，85%的查询与最近26个小时的数据写入有关，如果将最近26个小时的数据全部缓存在内存中，将是一个理想的方案。

内存中的数据组织结构，称之为Time Series Map，简称为TSmap。TSmap的组成结构如下图所示：

由上图可以看出来，TSmap的核心构成包含一个Vector以及一个Map：

- Vector存放了所有Time Series的指针，有利于高效扫描。基于C++标准库的Shard Pointer实现。

- Map以Time Series Name为Key，以Time Series指针为Value。可按Time Series Name快速查询，提供稳定的低时延保障。

上图中的右侧部分的TS，是一个Time Series的核心数据部分。一个TS包含0个或多个2小时以前的Blocks，以及一个当前正在接收新数据的Block。正在被写入的Block，其实就是一个append-only的string, 经压缩编码后的Data Point数据，都被append到这个Block中，当超过2小时以后，这个Block被关闭，此后，这个Block在被移除之前不会再发生任何变更。Close时，这个Block被复制到一个较大的Slaps中以期有效降低内存碎片。

既然整个设计围绕内存展开，对于整体数据的内存占用大小是至关重要的，这既涉及到方案的可行性，又涉及整个方案的性价比。

一个Data Point按照16 Bytes计算，而1秒钟产生的Data Points数量为1200W，那么，在不考虑任何压缩算法的前提下，一天的数据总量约为16TB。因此，一个高效的压缩算法显得至关重要。

我们知道一个Data Point中最关键的组成部分是Timestamp与Point Value，这两部分数据具有如下典型特点：

- Data Point通常按固定的时间间隔产生。

- 在很多Time Series中，Point Value的变化通常是平缓的，甚至在很多情形中保持不变。

Gorilla针对Timestamp与Point Value的不同特点，采用了不同的压缩编码算法。我们可以先从下图中获取一些直观的认识：

Timestamp压缩(Delta-Of-Delta)

Facebook通过分析存放于ODS中的Time Series数据后，发现绝大部分Data Points都按固定的时间周期采集。例如，某一个Time Series可能固定按照60秒产生一个Data Point。当然也会出现一定的时间偏差，但这个偏差值在受限的范围内。也就是说，在大多数情形下，可以将一个Time Series中的连续的Data Points的Timestamp列表视作一个等差数列，这是Delta-Of-Delta编码算法的最适用场景。编码原理如下：

1. 在Block Header中，存放起始Timestamp T(-1)，一个Block对应2个小时的时间窗口。假设第一个Data Point的Timestamp为T(0)，那么，实际存放时，我们只需要存T(0)与T(-1)的差值。

2. 对于接下来的Data Point的Timestamp T(N)， 首先计算Delta Of Delta值：

  D = (T(N) - T(N-1)) - (T(N-1) - T(N-2))

而后，按照D的值所处的区间范围，分别有5种不同情形的处理：

Case 1: 如果D为0，那么，存储一个bit '0'

Case 2: 如果D位于区间[-63, 64]，存储2个bits '10'，后面跟着用7个bits表示的D值

Case 3: 如果D位于区间[-255, 256]，存储3个bits '110'，后面跟着9个bits表示的D值

Case 4: 如果D位于区间[-2047, 2048]，存储4个bits '1110'，后面跟着12个bits表示的D值

Case 5: 如果D位于其它区间255, 256]，存储4个bits '1111'，后面跟着32个bits表示的D值

关于这些Range的选取，是出于个别Data Points可能会缺失的考虑。例如：

假设正常的Interval为每60秒产生一个Data Point，如果缺失一个Data Point，那么，相邻的两个Data Points之间的Delta值为：60, 60, 121 and 59，此时，Delta Of Delta值将变为： 0, 61, -62。

这恰好落在区间[-63, 64]之间。

如果缺失4个Data Point，那么，Delta Of Delta值将落在区间[-255, 256]之间。

下图针对Gorilla中的440,000条真实的Data Points采样数据，对Timestamp数据应用了Delta-Of-Delta编码之后的效果：

96.39%的Timestamps只需要占用一个Bit的空间，这样看来，压缩的效果非常明显。

Point Value压缩（XOR）

Gorilla中限制Point Value的类型为双精度浮点数，在未启用任何压缩编码的前提下，每个Point Value理应占用64个Bits。

同样，Facebook在认真调研了ODS中的数据特点以后也有了这样一个关键发现：在大多数Time Series中，相邻的Data Points的Value变化比较轻微。这一点比较好理解，假设某一个Time Series关联某个仪器温度指标的监控，那么，温度的变化应该是渐进式的而非跳跃式的。XOR编码就是用来描述相邻两条Point Value的变化部分，下图直观描述了Point Value 24.0与12.0的变化部分：

XOR编码详细原理如下：

1.第一个Value存储时不做任何压缩。

2.后面产生的每一个Value与前一个Value计算XOR值：

如果XOR值为0，即两个Value相同，那么存为'0'，只占用一个bit。

如果XOR为非0，首先计算XOR中位于前端的和后端的0的个数，即Leading Zeros与Trailing Zeros。

1) 第一个bit值存为'1'。

2) 比较Leading Zeros与Trailing Zeros部分是否与前一个XOR值相同：

2.1) 相同，则第2个bit值存为'0'，而后，紧跟着去掉Leading Zeros与Trailing Zeros以后的有效XOR值部分。

2.2) 不同，则第2个bit值存为'1'，而后，紧跟着5个bits用来描述Leading Zeros的值，再用6个bits来描述有效XOR值的长度，最后再存储有效XOR值部分（这种情形下，至少产生了13个bits的冗余信息）

如下是针对Gorilla中1,600,000个Point Value采样数据采用了XOR压缩编码后的效果：

从结果来看：

- 只占用1个bit的Value比例高达59.06%，这说明约一半以上的Point Value较之上一个Value并未发生变化。

- 30%比例的Value平均占用26.6 bits，即上面的情形2.1。

- 余下的12.64%的Value平均占用39.6 bits，即上面的情形2.2。

另外，XOR压缩编码机制，对于Integer类型的Point Value效果尤为显著。

Block大小

压缩算法通常都是基于Block进行的，Block越大，效果越明显。对于时序数据的压缩，则需要选择一个合理的时间窗大小的数据进行压缩。Facebook测试了不同的时间窗大小的压缩效果：

可以看出来，随着时间窗的逐步变大，压缩效果的确越显著。但超过2个小时(120 minutes)的时间窗大小以后，随着时间窗口的逐步变大，压缩效果的改善并不明显。时间窗口为2小时的每个Data Point平均只占用1.37 bytes。

本文总结

本文先从Facebook的内需监控需求出发，讨论了Gorilla的设计初衷。简单介绍了Gorilla的数据模型、分片与路由机制以后，详细介绍了Gorilla的基于内存的数据结构设计，以及针对Timestamp与Point Value的压缩编码机制。下篇文章将介绍Gorilla的数据持久化机制，故障处理机制以及跨Region的双活方案。

本文转载自微信公众号【Nosql漫谈】。

原文链接:https://mp.weixin.qq.com/s/6-xS8p2CrPT8HK07wqgLfg