Facebook的时序数据库技术(上)

本文介绍Facebook内部监控系统所用到的时序数据库技术,为了避免文章过长,将拆成两篇文章来介绍,此为上篇。

声明:此文核心内容源自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 CacheRead-Through Cache

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

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

现有的其它时序数据库技术,典型如OpenTSDB,InfluxDB,都是基于Disk的设计,显然无法满足Facebook的监控需求。Gorilla可以说很好的利用了监控数据/时序数据的特点,其关键技术点可以总结为如下几个方面:

  • 基于内存的设计。针对时序数据,设计了高效的内存数据结构,可支持高效的时序数据扫描,针对单个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(64位), point value(64位双精度浮点数)}

与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,简称为TSmapTSmap的组成结构如下图所示:

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

  • Vector存放了所有Time Series的指针,有利于高效扫描。基于C++标准库的Shared 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中最关键的组成部分是TimestampPoint 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编码算法的最适用场景。编码原理如下:

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

  • 对于接下来的Data Point的Timestamp T(N), 按如下算法计算Delta Of Delta值:

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

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

    • 如果D为0,那么,存储一个bit ‘0’

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

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

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

    • 如果D位于其它区间则存储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.1) 如果Leading Zeros与Trailing Zeros与前一个XOR值相同,则第2个bit值存为’0’,而后,紧跟着去掉Leading Zeros与Trailing Zeros以后的有效XOR值部分。

    2.2) 如果Leading Zeros与Trailing Zeros与前一个XOR值不同,则第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的双活方案。

Leave a Reply

电子邮件地址不会被公开。 必填项已用*标注