时间序列分析论文 Facebook TSDB论文Gorilla分析

TSDB时序数据库用于存储时间相关的数据，常用于监控系统的数据存储，分布式的TSDB提供了海量的数据存储能力，如InfluxDB、OpenTSDB等。时间序列分析论文关于TSDB更多详情，可以参考该系列博客:时间序列数据的存储和计算。

随着监控数据量增长，对TSDB查询性能的要求越来越高，尤其是自动化运维系统，大量的查询操作让基于磁盘的TSDB系统难以满足。

Facebook基于此需求推出了TSDB论文，设计了一个基于内存的TSDB：Gorilla。并开源了Gorilla的原型项目beringei。

本文主要基于Facebook官方论文和相关解读分析Gorilla的架构和数据结构。

Gorilla是一个内存TSDB。它在监控数据写入HBase存储之前，起到一个write-through cache的作用。Gorilla的数据模型是一个简单的3元组，包括一个string类型的key、一个64-bit整型timestamp和一个双精度浮点类型value。Gorilla使用一种新的timeseries压缩算法，可以按照时间顺序将单条数据从16字节压缩到平均1.37字节，缩小12倍。Gorilla的内存数据结构设计使得在保持对单个时间序列进行时间段查找的同时也能快速和高效的进行全数据扫描。

Gorilla无状态的架构支持非常好的水平扩展能力。监控数据中定义的key用来唯一标识一个timeseries。根据key将timeseries数据进行shard（分片），每个timeseries数据集会被映射到一台单独的Gorilla主机上。因此扩展Gorilla主机时，可以通过调整分片算法将新的timeseries数据映射到新的主机上。

Gorilla支持高可用，通过将同一个timeseries数据写到2个不同地域的主机中，来应对单节点故障、网络切换、甚至是整个数据中心故障。在检测到故障时，所有读取操作会failed over到可用区域的主机，以确保用户不会感知到任何中断。

Gorilla引入了对timestamp和value的高压缩比算法，可大幅降低数据存储的大小。Timestamp根据时间关联的条目进行差值计算、以及差值的差值计算得到占用字节数非常小的数值并进行保存。同样Value使用XOR算法进行计算得到占用存储更小的数值进行保存。该算法在论文里描述的非常清楚，此处不再详述。

Timeseries Map (TSmap)是Gorilla实现的主要数据结构。如上图所示，TSmap包括一个C++ Vector和一个map（unordered_map）。Vector里保存指向timeseries的指针(shared_ptr)。Map里保存timeseries name(key)到timeseries指针(value)的映射，该map大小写不敏感并保留原有大小写。

Vector用于高效的分页扫描所有数据（根据vector下标）。Map用于特定时间的timeseries查询。该设计既满足快速按时间查询的需求，又能提供高效的数据扫描。

C++的shared-pointers可以在几毫秒时间内扫描拷贝整个vector（或者几个pages），可以有效避免对新写入数据流的影响。删除的timeseries会将对应的vector设置为“墓碑状态”，即对应的内存不释放，而是标记为dead，并用于新的timeseries重复使用。

Map和vector的并行访问使用一个简单的读写spin lock进行保护。每个timeseries上使用一个1-byte的spin lock实行互斥。单个timeseries相关很少的写流量，因此读写的锁争用较少。