二手知识
文章 标签 分类
二手知识

Gorilla: 一个快速, 可扩展的, 内存式时序数据库

     约 6600 字   预计阅读 14 分钟 

本文基于内部分享 <“抄"能力养成系列 – Gorilla 的设计和实现> 整理.

Gorilla 是 Facebook 于 2015 年开放的一个快速, 可扩展的, 内存式时序数据库. 它的一些设计理念影响了后来的 Prometheus. 本文就其设计和实现进行深入分析希望能为各位后续在系统研发中提供灵感.

  • 针对一个大型系统, 监控和分析上千万个打点数据(measurements)是一件很有挑战的事情. 解决这个事情, 一个有效手段就是将这些打点数据存储到时序数据库(TSDB) 中. 而设计一个 TSDB 的关键挑战是如何让效率(efficiency)/扩展性(scalability)/可靠性(reliability)三者达成一个有效平衡. Facebook 的 Gorilla 就是一个达成这种平衡的 TSDB.
  • Gorilla 的设计基于这样一个洞察: 监控系统的用户不会太关注一个个单独的数据点, 而是关注聚合分析; 对于分析一个现有的问题, 最近的数据点比老的数据更有价值. Gorilla 为了读写的高可用而优化, 即使以丢失部分写操作为代价. 为了提升查询效率, fb 激进地采用压缩技术, 如 delta-of-delta 和浮点数 XOR, 来压缩存储大小, 以实现将 Gorilla 数据保存到内存中.
  • 最终效果是将查询时延减少 73X, 同时提升查询吞吐 14X, 两项均为和传统的基于 HBase 的时序数据库比较. 这个结果解锁了很多监控和调试功能, 比如可以在 Gorilla 上执行时序关联搜索.
  • Gorilla 也能很优雅地处理从单点到整个集群故障.

Figure 1 是 Facebook 内部的监控系统, 名叫 ODS(Operational Data Store, fb 内部广泛使用的一个老的监控系统), 其中 Gorilla 作为一个 write-through(即 cache 和 back store 同时修改保证多用户一致性) cache.

/images/fb-gorilla-20201205/1-fb-ods-架构图-gorilla作为writethoughcache.png

  • 写密集. 每秒可以写入上千万数据点, 一个查询可以毫秒级响应. 读比写少几个数量级, 主要是一些自动化监控系统或者用户查询.
  • 快速识别系统的重大状态变迁. 出现任何问题时都会导致系统状态发生变化, Gorilla 支持针对很小的窗口(几十秒)进行聚合, 以快速识别重大状态变化并触发自动化修复.
  • 高可用. 即使多个数据中心通信断开, 每个 DC(位于不同 region 的 DataCenter, 下同) 都能本地实例读写. 容错. 写入数据被复制到多个 DC, 确保某个 DC 挂掉数据仍在.

以上限制 Gorilla 均满足, 而且可以做到绝大多数查询在几十个毫秒内返回.

另外,

  • 统计发现, 针对 ODS 的至少 85% 的查询涉及过去 26 个小时的数据. 这就暗示我们如果将之前基于磁盘的存储改为内存式将会更好地服务用户. 再进一步, 我们将这个内存式数据库作为持久性磁盘存储系统的 cache, 我们就既可以获得高速插入速率, 同时还能获得数据持久性.
  • 2015 年春天, fb 的监控系统就生成了超过二十亿个 counter 类型的时间序列, 每秒产生大约 1200 万个数据点, 每天产生 1 万亿个数据点. 每个数据点 16 字节, 那就占用 16TB 内存, 这太多了. 但是通过采用基于 XOR 的浮点数压缩技术, 平均每个数据点 1.37 字节, 大小减少 12x.
  • 为了满足可靠性, 我们在不同 region 的 DC 都部署了 Gorilla 实例, 每个数据点都会写入每个 DC 的实例, 但是这多个副本并不保证一致性. 查询请求会被路由到最近的 DC. 以上基于一个观察, 即独立的数据点丢失不会对数据聚合结果产生大的影响, 除非不同 Gorilla 实例数据差异很大.
  • 目前 Gorilla 在 fb 用于生产环境, 而且和其它系统如 hive/scuba 一起检测和分析问题.

fb 内部有几百个系统, 分布在多个 DC, 这些系统的健康状况和性能是需要监测的, ODS 就是 fb 监控系统的重要组成部分. ODS 由 TSDB, 查询服务以及检测和告警服务构成; 其中 TSDB 是构建在 HBase 上的.

早在 2013 年, fb 的监控团队就意识到基于 hbase 的 TSDB 无法扩展应对将来的查询负载. 其中 90 分位数长达几秒, 这对于依赖 tsdb 的自动化监控系统非常不友好. 一个针对稀疏数据的大点的查询甚至会超时, 因为 hbase 是针对写操作优化的. 虽然 hbase 表现不行, 但是也不能整个替换掉, 因为 ODS 的 hbase 存了 2PB 的数据. 而且 fb 的数据仓库, hive 也不能胜任, 因为它的查询比 ODS 还要慢几个数量级, 而查询时延和效率是我们主要关注的. 接下来能做的就是内存式 cache 了. (ODS 其实本来就有 write-through cache, 只不过是用于制图系统.) 开始也考虑过基于 Memcached 来做, 但是因为针对已有时间序列追加新数据需要一个读写周期, 会导致 memcached 服务器产生极其高的流量, 所以否掉了这个方案.

  • 通过唯一 key 可以识别 20 亿时间序列.
  • 每分钟可追加 7 亿数据点(时间戳+具体值).
  • 可保存 26 个小时的数据.
  • 可支持每秒 4000 查询峰值.
  • 一个毫秒内完成读操作.
  • 支持 15 秒粒度的时间序列(即一分钟四个数据点).
  • 两个内存式副本(不能部署在同一个地方, 以应对故障).
  • 即使挂掉一个实例, 仍然可以正常支持查询.
  • 可以快速扫描整个内存数据的能力.
  • 支持每年至少 2x 的负载增长.

Gorilla 聚焦如何实时收集和存储海量数据. Gorilla 可以作为其它 tsdb 的 write-through cache.

  • 它基于 HBase, 无降采样功能.
  • 数据模型丰富, 针对一个时序有一组 key-value 对即 tags, Gorilla 仅有一个字符串 key 而且依赖更高级的工具抽取和识别时序的元数据.
  • 数据存储在本地磁盘, 所以查询速度不够快.
  • 数据格式为 whisper, 即 RRD 风格. 该文件格式要求时间序列数据都带固定间隔的时间戳. 如果时间戳间隔固定, Gorilla 表现更好(压缩率更高), 但是 Gorilla 也可以处理随机变化的时间间隔.
  • 每个时间序列保存到一个单独的文件中, 一段时间后新采集的数据会覆盖老的数据, 毕竟是 Round-Robin Database. Gorilla 也采用类似的方式, 仅在内存保存最近的数据.
  • 比 OpenTSDB 数据类型更加丰富, 每个数据点都有一组丰富的标签, 这也导致它更占磁盘.
  • 无需 hbase/hadoop 就能做到水平扩展.
  • 数据保存到本地磁盘, 所以查询不如内存式的快.
  • 内存式, 作为后端 hbase 的 write-through cache.
  • 每个数据点是一个三元组<字符串形式的 key, 64 比特的时间戳, 双精度浮点数类型的测量值>.
  • 所采用的压缩算法, 可以将 16 字节的数据点压缩到平均 1.37 字节, 减少 12x.
  • 内存数据结构既支持快速的全量数据扫描, 也支持高效地查询单个时序.
  • key 作为时序唯一标识, 写入时也是基于此在众多 Gorilla 实例之间做 sharding. 所以仅仅通过增加新机器就能实现 Gorilla 集群的水平扩展, 新写入的数据会被 sharding 到新机器上. 之所以这么简单, 就是因为 Gorilla 整体是一个 share-nothing 架构, 专注于水平扩展能力.(疑问, 一致性哈希咋做的? 论文没讲, 但提到了 ShardManager, 应该是它负责的).
  • Gorilla 可以处理单点故障, 网络分区甚至整个 DC 挂掉, 方法就是每个时间序列都被写入到两个不同地理 regions 中的实例中. 一旦检测到宕机, 针对目标序列的全部查询会被自动切换到另一个 region 的实例, 这个过程用户感觉不出来.

Gorilla 对压缩算法的诉求:

  • 支持针对浮点数进行压缩而非整数
  • 支持在数据流上进行压缩, 而不是针对静态完整的数据集
  • 无损, 保持整个时序精度不变

Gorilla 的压缩算法受科学计算中的浮点数压缩方案启发, 该方案利用当前值与前一个值的 XOR 比较来生成 delta 编码.

Gorilla 不支持跨时间序列进行压缩, 而是在每个时序内进行压缩. 时间戳和具体数值各自独立进行压缩, 压缩时都用到了前一个数据点的信息.

Figure 2 是 Gorilla 的压缩过程图示.

/images/fb-gorilla-20201205/2-压缩算法可视化.png

  • 2.a 显示了一个数据流, 每个点由两个 64 比特的数构成, 一个是时间戳一个是具体测量值. Gorilla 基于时间将数据流分成 block, 划分时会按照每两小时进行对齐. 可以看到每一个 block 以一个简单的 header 开始, 它含有所在 block 对齐的时间戳, 例子中是凌晨两点.
  • 2.b 是基于 delta-of-delta 压缩后的数据, 可以看到 delta-of-delta 等于 60-62=-2, 用 ‘10’ 两个比特表示(后面详述表示规则), 接下来 7 个比特存储测量值, 一共用了 9 比特.
  • 2.c 显示的是使用 XOR 算法压缩的浮点数, 可以看到当前值与前一个值 XOR 后的结果, 它有 11 个前导零, 整个结果仅有一个有效位 1, 这可以编码为 2 比特的 ‘11’. 存储当前浮点数测量值 24 共用了 14 比特. 具体编码细节后面详述.
  • 我们注意到, 在 ODS 中, 绝大多数数据点都是以固定时间间隔到达的. 后面可以看到这是一个非常重要的洞察.
  • 我们不会将时间戳完整存储, 而是采用 delta-of-delta. 假设一个 delta 序列为 60, 60, 59, 61, 那么 delta-of-delta 就是 0, -1, 2.
  • 然后我们按照下面的算法使用变长编码来编码这些 delta-of-delta:
    • block header 存储起始时间戳, 记为 $t_{-1}$, 它以两小时时间窗口来对齐. 当前 block 中第一个数据点的时间戳记为 $t_0$, 真正存储的是它减去 $t_{-1}$ 得到的 delta(只有第一个时间戳对应的存储值为 delta 而非 delta-of-delta, 因为前面就一个起始时间戳), 以 14 比特存储.
    • 接下来针对每个时间戳 $t_n$:
        1. 计算其对应的 delta-of-delta: $D=(t_n-t_{n-1})-(t_{n-1}-t_{n-2})$
        1. 如果 $D$ 为 0, 则用一个比特存储 ‘0’
        1. 如果 $D$ 在$[-63, 64]$ 之间, 用 2 个比特存储 ‘10’ , 然后接下来 7 比特存储 $D$ 的具体值.
        1. 如果 $D$ 在$[-255, 256]$ 之间, 用 3 个比特存储 ‘110’, 然后接下来 9 比特存储 $D$ 的具体值.
        1. 如果 $D$ 在$[-2047, 2048]$ 之间, 用 4 个比特存储 ‘1110’, 然后接下来 12 比特存储 $D$ 的具体值.
        1. 其它情况, 用 4 个比特存储 ‘1111’, 然后接下来 32 比特存储 $D$ 的具体值.
    • 上面的取值范围都是通过从生产系统统计出来的, 这几个范围可以帮助达到最大压缩率.

/images/fb-gorilla-20201205/3-时间戳压缩取值范围量化说明图.png

从 Figure 3 观察压缩效果: 可以发现大约 96% 的时间戳可以压缩到 1 个比特.

  • Gorilla 只允许存储双精度浮点数的测量值.
  • 根据统计, 时间序列中相邻的数据点大多数时候相差不大, 如果相邻的数据点对应的测量值的符号部分/指数部分/小数部分前半截都差不多一样, 那么我们就可以计算当前值和前一个值的 XOR 来存储而不是采用 delta 编码方案.
  • 当前值和前一个值进行 XOR 后按照下面变长编码方案来存储:
    • 第一个值不压缩
    • 如果 XOR 结果为 0, 则仅存 1 比特的 ‘0’
    • 如果 XOR 结果非 0, 计算其前导零和后缀零个数, 存储 1 比特 ‘1’, 然后后面跟着下面的 a 或者 b:
      • a. 首先是 1 比特的控制位 ‘0’, 如果当前 XOR 结果的前导零个数和后缀零个数与前一个 XOR 结果的对应部分一样, 仅存储当前 XOR 结果的中间有效位部分(该部分开头和结尾都为 1). 正是因为前述的特性, 可以让我们省去存储前导零长度和后缀零长度的空间, 根据前一个 XOR 结果就能复原当前这个.
      • b. 首先是 1 比特的控制位 ‘1’, 接下来 5 比特为前导零个数, 接下来 6 比特为当前 XOR 结果的有效位长度(该部分开头和结尾都为 1), 接下来为 XOR 结果的有效位部分.
  • 从上面方案来看, 测量值压缩不但用到了当前测量值和前一个测量值, 也用到了当前 XOR 结果和前一个 XOR 的结果, 因为计算出来的 XOR 序列, 相邻两个经常有相似的前导零和后缀零. 这可以通过 Figure 4 来观察.

/images/fb-gorilla-20201205/4-XOR序列前导零和后缀零以及有效部分聚集示意图.png

针对测量值的编码方案, 从 Figure 5 统计可以看到:

  • 大约 59.06% 数据点被压缩到仅剩 1 比特
  • 大约 28.3% 以控制位 ‘10’ 开头, 平均长度为 26.6 比特
  • 大约 12.64% 以控制位 ‘11’ 开头, 平均长度为 39.6 比特, 相比控制位 ‘10’ 方案多出来的 13 比特用于存储前导零长度和有效位部分长度了.

/images/fb-gorilla-20201205/5-测量值压缩后各种模式长度及其占比.png

测量值方案潜在的问题: 就是时序对应的数据流按多大的窗口划分 block 才能更好的利用这个压缩方案. 由于中间每个值压缩都与自己的前驱密切相关, block 肯定越大越好, 如果不划分 block 是最佳的. 但是如果 block 太大, 但是用户只想查询一个很小的时间窗口的数据, 就会涉及非常大的计算量来解压缩. 这就牵扯到 trade-off.

/images/fb-gorilla-20201205/6-数据流划分成block的大小权衡.png

从 Figure 6 可以看到 120 分钟也就是两个小时的 block 大小可以达到一个比较理想的压缩率, 平均每个数据点占 1.37 字节. 窗口再大, 压缩率变化不大了.

Figure 7 是针对 Gorilla 的内存数据结构相互关系和各个部分的图示.

/images/fb-gorilla-20201205/7-gorilla内存数据结构.png

Gorilla 实现涉及的核心数据结构是 Timeseries Map(TSmap), 如 Figure 7 中间部分所示.

  • 一个 C++ 标准库的 vector, 每个元素是一个 shared-pointer, 每个 shared-pointer 指向一个时间序列 TS. 该结构主要用于针对全量数据进行高效地分页扫描.
  • 一个从时间序列名称(大小写不敏感但是保留大小写)到指向时间序列 TS 的 shared-pointer 的无序 map. 该结构主要是用于在常数时间内根据名称查询某个时间序列.

关于 TSmap 的并发控制:

  • 有一个专用的 Read-Write 锁保护 map 和 vector 的访问
  • 每个 TS 有一个 1 字节的 spin lock, 由于每个时间序列写吞吐低(秒级或分钟级写一次), 所以针对 spin lock 的争用并不激烈.

C++ shared-pointer 使得扫描操作可以在微秒时间内拷贝 vector, 这避免了长时间锁住临界区(critical section)从而影响写入数据流. 当删除一个时间序列时, 其对应的在 vector 的元素会被标记为墓碑(相关内存不会返回系统而是等待重用), 对应的索引被放到池子里待新的时间序列重用之.

Gorilla 为了做到分布式存储采用了分片机制, 如 Figure 7 左边部分所示.

  • ShardMap 名字里有 map, 但它实际是一个 vector, 每个元素是一个指向 TSmap 的 unique_ptr.
  • 那它为什么叫 map 呢? 因为每个时间序列根据其名称先做 hash(具体算法同 TSmap 的 map 结构)后做 shard(即其被分到哪个 TSmap).
  • shards 即 TSmap 个数固定, 只有几千个.
  • 就像 TSmap, 针对 ShardMap 的访问也由一个 read-write spin lock 控制.
  • 因为 ShardMap 这一层做了 shard 了, 所以 TSmap 内部的 map 就比较小了, C++ 标准库里的 unordered-map 性能足够了.

说完了最外层的 ShardMap, 也说完了中间的 TSmap, 下面说说最里面的 TS 构成.

TS (即 time series), 为 Gorilla 存储每个时间序列的数据结构, 如 Figure 7 右边部分所示.

  • 每个时间序列的数据结构由一系列 closed blocks(每一个两个小时大小)和一个 open block (保存最近两个小时的数据).
  • open block 仅追加压缩过的(压缩算法前面讲过了) <时间戳, 测量值> 数据点. 超过 2 小时, open block 就会转成 closed block, 后者不可更改直至从内存被删除.
  • 一旦 closed, block 就会被拷贝到另外的内存(这些内存从大块的 slabs 分配)从而减少内存碎片. open block 经常因大小变化而重分配内存, 前述的拷贝过程可以减少 Gorilla 整体的内存碎片.
  • 当外部查询时, Gorilla 直接拷贝包含目标数据的 blocks 给客户端, 客户端自己去解压缩.

Gorilla 其中一个设计目标就是高可用, 不能因为单个 host 挂掉而导致集群不可用.

Gorilla 通过 GlusterFS 实现数据持久性, 该分布式文件系统支持三副本, 并且兼容 POSIX. 当然你也可以用 Hadoop 或者其它分布式文件系统. 注意这里是单个 host 上数据的持久性, 它们对 host 内存数据对应. 这些数据不用于响应客户查询, 而是用于 host 内存数据持久化以便在 host 挂掉后被重新加载到内存恢复对应数据结构.

Gorilla 每个 host 持有多个 shards, 每个 shard 一个目录. 每个目录中保存着如下四类信息:

  • key list 文件. key list 文件就是一个简单的 map, 即从时间序列的字符串类型的 key 到一个整数 ID 的映射. 这个整数 ID 就是对应时间序列在 Tsmap->vector 的索引. 新的 keys 会被追加到 key list 中, Gorilla 会周期性地扫描每个 shard 对应的全部 keys 以重写该文件.
  • 一组 append-only logs. 每个 shard 一个 append-only log. 类似 WAL(write-ahead log), 但因为它不保障 ACID 所以不是真正的 WAL. 新到达的数据点都是先写到这个文件. 由于每个 shard 一个 append-only log, 所以哈希到同一个 shard 的多个时间序列的数据点会交织在一起. 数据编码同内存格式, 但多了一个 32 比特的整数 ID 标识数据点属于哪个时间序列. 每当攒够 64KB 数据刷盘一次, 大约是一两秒的数据, 这可能因为宕机丢失一小部分数据, 不过为了获取更高的磁盘写入效率, 这个 trade-off 就不得不做了.
  • 一组完整的 block 文件. 每隔两小时 Gorilla 会拷贝内存中压缩过的 block 数据到磁盘, 它比 append-only log 文件小多了. 一个 block 文件就是两个小时的数据, 它包含两段: 一组连续的 64kB slabs(就是它们在内存中的样子), 一个 <time series ID, data block pointer> 列表.
  • checkpoint 文件. 每当一个完整的 block 文件生成, Gorilla 就会创建一个新的 checkpoint 文件同时删除对应的 append-only log. 这个 checkpoint 文件用于标记什么时候一个完整的 block 文件被刷入了磁盘. 如果因为进程崩溃导致 block 文件写入失败, 新进程启动后会发现对应的 checkpoint 文件不存在, 新进程就会认为这个 block 文件有问题, 转而仅从 append-only log 读取数据.

Gorilla 容忍两种故障:

  • 单机故障
  • 单集群故障

以上两种都可以通过多副本机制做到快速转移和处理, 也对频繁的版本升级很友好.

多副本机制: 针对同一份数据, Gorilla 会在不同 region 的 DC 里面部署相互独立的集群, 每次写操作同时写到这两个地方, 当然这个双写不保证一致性(还是回到前面讲到的, 时序数据不太注重单个数据点或者一小块数据, 关注的是整体), 一个挂了另一个还能用, 挂了的那个数据恢复到最近 26 个小时大小就继续对外提供服务.

单机挂掉后 Gorilla 处理流程:

  • ShardManager(一个基于 paxos 强一致系统)会将其负责的 shards 重分配给当前集群其它机器.
  • 重分配期间, 写客户端会自己缓冲这些 shards 的数据一分钟.
  • 一般 node 挂掉 30 秒后就启动重分配, 一分钟就可以完成, 如果超过一分钟, 缓冲的数据就会用新的覆盖老的.
  • shards 重分配时, 分到这些 shards 的 nodes 会去 GlusterFS 拉取数据, 一般五分钟内就可以全部恢复.
  • 注意, 前述过程可能会丢失部分数据, 这是可以容忍的.

注意, node 失效期间, 因为部分 shards 不可用, 读响应可能会被标记为 partial, 客户端转而请求另一个 DC 的同样数据, 如果两个 DC 相关均不可用, 则两个 DC 的部分结果和一个表示错误的标识会被返回给客户端.

最后, 如果 Gorilla 都挂了怎么办? 这时就靠 HBase 的 long-term 存储来响应客户请求了, 直到 Gorilla 集群恢复.

  • Gorilla 提供的关联搜索功能支持用户一次在一百万个时间序列上做交互式地暴力搜索.
  • 关联分析引擎支持针对某个序列和一组其它时间序列做 PPMCC(皮尔逊积矩相关系数), 从而找出形状相似地时间序列, 进而帮助做根因分析(root-cause analysis).
  • 计算 PPMCC 时, 测试时间序列会被广播到多个机器, 这些机器基于目标时序的 key 来确定, 每个机器独立计算相关时序, 然后基于 PPMCC 绝对值排序求出 topN. 最后返回结果.

在 Gorilla 上线之前, fb 在 hbase 上允许 map-reduce 任务来计算降采样数据. 有了 Gorilla, 后台进程每两个小时扫一遍全量数据来计算降采样, 不用再去全表扫描 HBase 了.

–End–

更新于 2020-12-05
阅读原始文档
 Gorilla, tsdb, distributed system, paper
返回 | 主页