NoSQL学习——时间序列数据库
# 时间序列数据
时间序列数据是一系列按时间排序并索引的数据点的组合，通常时间序列具有较为一致的结构。常见的时间序列数据有财经数据如股票、医疗数据如心电图、工程数据如软件日志等。对时间数据的分析主要集中于通过过去数据的统计学分析预测趋势或发掘某些共性特征。通常使用机器学习、统计学习等方式处理，此处不做讨论。
实际应用中，时间序列数据具有规整性和扩展性两种特质，即数据存在相对一致的生成标准，且由于时间间隔小，生成的数据量极大。如何高效地在这些数据上进行存储、查询和分析是时间序列数据库的主要考量。例如对于Facebook之类的大型网络应用而言，大量的用户会在极短的时间内生成大量的数据和写入请求，因此需要提供高可用性；在持久性上需要提供容错机制；另外还需要提供针对最近数据的窗口聚合函数用于进行分析。为此，强一致性如ACID就不再是考虑的因素，可以牺牲；而主要用于分析的场景下，单点数据也不如聚合结果重要；同时由于数据的时效性，新数据比旧数据更有价值。
结合上述讨论对时间序列性质的描述，如果你已经了解过LSM及其相关的设计理念，相信对于时间序列数据如何处理你已有了一些想法。
# Facebook Gorilla
尽管我们可以在HBase/BigTable中看到处理时间序列数据的方法，但这个系统在面对新的数据量时性能不够好。一方面是写入时的日志操作的原因，另一方面是HDFS/GFS存储的原因。
为此，Facebook提出了Gorilla这种新型的内存型时间序列数据库，这种数据库主要用于监视某一服务的量化结果随时间发生的变化。在该数据库中，存储的数据是按照3元组的方式组织，其形式为(key: string, timestamp: int64, value: double)，其中的key即为监控的服务指标，timestamp为时间戳（但与正常的时间戳有一些差距，在后文展开），value即为监控的量化结果。
在整体的组织上，Gorilla首先在内存中建立一个(unique_ptr<TSmap>)的列表，然后对于每个TSmap都有一个读写锁（控制并发）、一张时间序列TS的列表（顺序遍历）以及一个无序的(key: string, TS映射表)。需要注意，Gorilla中的key是大小写不敏感但保留大小写的。在TS表中，内部会使用一个自旋锁控制并发，然后内部由两个部分组成，其一是只能追加的开放数据块，其二是完成了记录的封闭数据块（不再可变）。
# 时间戳压缩
在实际存储时，key不会存储到序列数据中，因为对一个序列来说其key都是一致的。key在存储时的作用是将数据进行分片，这一步通过结合元数据实现。因此，实际存储的数值只有16字节（128位），但要注意这是原始数据的尺寸。在此基础上，Gorilla使用了一种基于变化的变化的压缩算法压缩时间戳，极大地压缩了写入尺寸（约12倍的压缩）。另外这种基于结构规则的压缩也便于扫描并查找数据，还提供了常数级的单点数据查找。
压缩算法的假设是，相近数据的记录间隔通常在较小范围内浮动，则其变化值（近似一阶导数）的变化（近似二阶导数）在极小的时间内不会显著变化，该压缩算法使用的表示值被称为delta of deltas。假如有一个时间序列(t0, t1, t2, ..., tn)，压缩数据块会在开头记录初始t-1时间,对t0记录其与t-1的差值，然后依次对t1等计算delta of deltas（）。在得到了delta of deltas后，就可以对该数值压缩，因为这一数值通常小于64（）或256()，只需要7/9位数据表示（变化值分为正负）。但数据被压缩后，其边界就不能够直接确定，为此，Gorilla使用了类似Huffmann编码的前缀表示数据位数，其编码方式如下以此类推，直至不可压缩：
| 数值范围 | 前缀编码二进制表示 | 数值存储位数 | 例子 |
|---|---|---|---|
| 0 | 0 | 1 | 0b00=(0,0b0)=0 |
| [-63, 64] | 10 | 7 | 0b101111=(10, 0b1111)=15 |
| [-255, 256] | 110 | 9 | 0b1101111111=(110,0b1111111)=127 |
在上述的表格中我们可以发现没有出现范围较低的5bit数，可能的原因这样反而增加了前缀编码的占用空间并使得整体压缩率降低。另外，每个范围的数据记录与正常的补码范围不同，可能的原因是排除了零后对正负数分别采用了不同的编码方式。因此，(0b0, 0)和(0b10, 0)解码后的实际数值应当是不同的。
例如，有三个时间点02:00:00、02:01:02、02:02:02，其delta为-、62、60，其delta of delta就只有-2。于是对于最后一个时间点，其记录就只需要包含两个数据：(delta of deltas: ('0b10',-2(7bit)), value: "0")。
# 数值压缩
在数值压缩上，Gorilla采用了类似浮点数压缩的算法。基本的假设是，相近数据点的数据变化不会太大，其符号、系数和分数的前几位基本相同（参考浮点数结构，1bit符号，数bit系数和数bit分数）。在这一假设下，使用异或操作能够获得发生变化的那一部分（位异或操作相同为0，相异为1），然后只存储非零的那些位数以及前导零和后缀零的位数（位数存储同样可以使用差分压缩）。
# InfluxDB
InfluxDB是另一种面向大量写操作的时间序列数据库服务，并面向聚合查询进行了优化。
# 数据建模
InfluxDB的数据模型与Gorilla类似是一个三元组，但其时间序列的序列键（Series Key）由两部分组成，Field和Tag，前者必须指定并表示实际的数值意义，后者可选并用于表示元数据。具有相同键的数据点属于一个时间序列，相关的时间序列则属于一个测量（measurement）。在此基础上，InfluxDB的组织方式为：1）一个数据库为一个bucket，包含多个测量；2）一个测量包含多个时间序列；3）一个时间序列包含多个tag和对应的值，另外包含一个field，tag在时间序列上组成tag集，field则在测量measurement中组成field集。例如，对于一组虚拟机cpu使用率和内存占用的监控：vm1.cpu、vm1.mem、vm2.cpu、vm2.mem，可使用一个measurement load、两个tag vm1和vm2以及两个field cpu和mem表示。这样做的好处是，在已有时间序列上细化记录时，相较于增加新的时间序列，InfluxDB只需要添加新的tag表示即可。
# 存储设计
由于LSM的设计思想非常适合处理具有时效性且写入量大的数据，InfluxDB采用了这一设计理念，早期的实现使用了基于LSM优化写的LevelDB，并使用了基于内存B+数索引优化读的BoltDB。
最终，InfluxDB使用了自行设计的面向时间序列的TSM Tree引擎，主要解决的是数据删除性能的问题。在LSM中，通过墓碑机制会标记大量过期数据，带来性能瓶颈。为此，InfluxDB采用了一种基于TSM文件（类似BigTable中SSTable的文件，管理属于一个series的数据）和墓碑文件的机制。在启动时，墓碑文件被用于丢弃完全过时的数据块；在进行打包时，根据墓碑文件删除数据项。由于删除操作只是很小的一部分，大多数删除是在丢弃过时数据块时完成的，这就避免了对过期数据的单独标记。除此之外，TSM Tree采用了与LSM类似的实现，包括写前追加日志（WAL）、缓存内存表以及与其相关的操作方法。
# 总结
这一章中我们了解了时间序列数据库的数据性质及其存储方法，以及一些相关的时间序列数据库的数据模型和设计。可以看到时间序列数据库与LSM有很强的关联，这与其读写特性有关。因此在设计一个系统时，要按照使用场景考虑如何优化最重要的那一部分服务。