时序数据库系列（三）时序数据库相关技术点、LSM-Tree数据架构、Delta压缩算法

系列文章链接
时序数据库系列（一）初识时序数据
时序数据库系列（二）时序数据库详解
时序数据库系列（三）时序数据库相关技术点、LSM-Tree数据架构、Delta压缩算法
时序数据库系列（四）Timelyre应对时序数据游刃有余
时序数据库系列（五）时序数据案例集

1. LSM-Tree数据结构

对于时序数据库来说，大部分场景都是写入，几乎不需要对已经写入的数据做修改，读取数据时也是在特定时间段进行分段读取。LSM-Tree数据结构与时序数据库的需求非常匹配，因此被广泛应用以实现更好的存储和查询性能。

LSM-Tree 全称是 Log Structured Merge Tree，是一种分层、有序、面向磁盘的数据结构，其核心思想是充分利用磁盘的顺序写性能要远高于随机写性能这一特性，将批量的随机写转化为一次性的顺序写。目前主流的NoSQL数据库是采用LSM tree替换B tree，比如Timelyre、Hyperbase等。LSM-Tree解决

了写多读少的应用场景，适用于亿级的海量数据存储和查询场景。

LSM tree操作流程如下：

1. 数据写入和更新时首先写入位于内存里的数据结构。为了避免数据丢失也会先写到WAL文件中。

2. 内存里的数据结构会定时或者达到固定大小会刷到磁盘。这些磁盘上的文件不会被修改。

3. 随着磁盘上积累的文件越来越多，会定时的进行合并操作，消除冗余数据，减少文件数量。

LSM Tree核心思想就是通过内存写和后续磁盘的顺序写入获得更高的写入性能，避免了随机写入。假定内存足够，每次数据写入时将不会直接写入磁盘，而可以将最新的数据驻留在内存当中，当数据积累到一定数值以后，再使用归并排序的方式将内存中的数据合并并追加到磁盘队尾。

LSM具有批量特性，存储延迟。当写读比例很大的时候（写比读多），LSM树相比于B树有更好的性能。因为随着insert操作，为了维护B树结构，节点分裂。 读磁盘的随机读写概率会变大，性能会逐渐减弱。 多次单页随机写，变成一次多页随机写,复用了磁盘寻道时间，极大提升效率。

2. 数据压缩差分编码Delta

时序数据采用列式格式存储，数据之间的相关性较高，例如同一设备相邻的时间戳Timestamp有较明显的规律，因此可以采用数据编码和压缩算法的方式对原始数据进行压缩，在需要使用数据分析时进行数据还原的操作，减少数据在传输及存储时的大小，提高传输效率并降低存储成本。时序数据库使用内置数据压缩功能可以将数据压缩至十倍甚至二十倍以上，下面将介绍时序数据压缩常见的Delt差分编码和Delta-of-Delta二阶差分编码对时间戳的压缩。

Delta

差分编码又称增量编码，编码时第一个数据不变，其他数据转换为上一个数据的 delta。其原理与 XOR 类似，都是计算相邻两个数据的差异。该算法应用广泛，如需要查看文件的历史更改记录（版本控制、Git 等）。但在时序数据库中这种算法很少单独使用，一般会搭配 RLE、Simple8b 或者 Zig-zag 一起使用，压缩效果更好。下面对delta时间戳压缩举例说明：

时间戳一般采用 long 类型进行存储，需要占用 8byte 存储空间。最直接的优化就是存储时间戳的差值，这里需要起始时间戳和 delta 的最大范围阈值。有两种常用的实现思路：

• 存储相邻两个时间戳差值 Delta(n) = T(n) - T(n-1)

•       存储与起始时间戳的差值 Delta(n) = T(n) - T(0)

假设起始时间戳为 1571889600000，delta 的最大范围阈值为 3600s，每个 delta 的数值需要 13bit 可以存储。因此以上时间戳数据共占用空间为 64 + 13 * 4 = 116bit。思路 2 的优势是不需要对块内数据依次遍历，但是相比思路 1 可能需要更为频繁地更换起始时间，根据实际需求选择合适的压缩方案。

Delta-of-Delta

又名二阶差分编码，是在 Delta 编码的基础上再一次使用 Delta 编码，比较适合编码单调递增或者递减的序列数据。Delta-of-delta算法可以极大程度地降低数据存储的成本和提高数据写入、查询的性能。delta-of-delta 压缩时间戳是 Facebook Gorilla 论文中所提到的，论文地址：http://www.vldb.org/pvldb/vol8/p1816-teller.pdf。针对不同时间跨度的数据，Facebook Gorilla 给出了一种较为通用的处理方案。

依然通过一组时间戳数据来直观感受下 delta-of-delta 编码的压缩效果：

依然假设起始时间戳为 1571889600000，delta 的最大范围阈值为 3600s，占用存储空间对比如下：

delta 算法： 64 + 13 * 7 = 155bit 。

delta-of-delta 算法： 64 + 9 * 4 + 1 * 3 = 103bit 。

可以看出 delta-of-delta 算法相比 delta 算法进一步获得了更高的压缩率。在实际应用场景中，海量时序数据的时间戳都是密集且连续的，绝大部分都满足 delta-of-delta=0 的条件，这样可以大幅度降低时间戳的存储空间。

3. 存算分离架构（Disaggregated Storage and Compute Architecture）

时序数据库要实现对海量时序数据的存储、计算、分析等业务操作，就必须实现大规模低成本的数据存储以及高效的数据分析能力。时序数据库可以通过优化存算架构，获得更高细粒度的的资源控制，以保证在大规模存储下的计算能力，这就需要讲计算层与存储层进行解耦。

单机架构

单机架构是最简单的存储架构，单台机器节点上包含了存储服务和磁盘，所有的读写请求都会发送到一台机器上。当机器出现故障时，整个存储服务将变为不可用的状态，这无法满足不了时序数据存储的可用性需求。因为，分布式的存储架构凭借其高可用的特性开始被人们广泛应用。

分布式架构

通过分布式架构，解决了服务器的可用性问题，做到在主节点出现故障时，备用节点可以快速接入，实现数据库的高可用。在基于分布式一致性Raft协议讲数据全量同步到其他节点，保障数据库的可靠性。但是当数据平台面对多种数据类型的分析服务时，需要对接不同的数据分析引擎，此时数据会在不同业务中重复存储。与此同时，在对节点扩容时不能很好的单独增加计算资源或存储资源。当存储与计算服务资源未做隔离处理时，对业务稳定性影响较大。因此，存算分离架构逐渐成为热点。

存算分离架构是一种新的数据架构的设计范式，自上而下分为数据分析层、计算层和存储层，其中计算层和存储层解耦合，都是独立的分布式服务。其设计的目标是要解决三个需求：数据可以灵活开放给不同业务做数据分析、计算和存储独立扩展以及计算与存储的资源隔离，同时也提供与存算一体架构等同的存算性能。

存算分离架构参考示意图如下所示：

•  计算层。计算层是一组无状态节点组成的集群，具有更好的可扩展性。计算层分离还有一个好处是，由于时序数据的读写是相对不均衡的，写入流量是取决于设备数和上报周期，基本是稳定的；而读取流量取决于业务，存在一定的波动性。这就可以将计算层按照读和写进一步分离，可以做到为读取和写入分别预留适当的计算资源。

•  存储层。存储层选择分布式存储，例如 HDFS、对象存储等。同时可以按照时序数据的访问特性进行分层存储，将不同时间段的数据分别存储到单价不同的存储介质中，做到精细化存储。不同存储节点之间通过Raft一致性协议实现数据全量同步至其他节点。同时，在存储层对时序数据分层存储。结合不同时间范围的时序数据访问频率的差异，存储层可以采用多种存储介质和存储方式来分别负责热数据和冷数据的存储，从而在保证性能的同时最大化地降低存储成本。

 
下一篇：时序数据库系列（四）Timelyre应对时序数据游刃有余