怎样缓存时序数据更合理? 解密 DBMind 在时序数据缓存上的代码实践 openGauss

业务背景

DBMind 是 openGauss 开源的数据库自治运维底座，在设计和实现上，融合了大量的工程技巧和优化。其中，DBMind 的一个功能需求是“通过从时序数据库中获取监控数据，然后基于该监控数据进行分析”，上述提到的时序数据，可以用于异常检测、时序预测以及多指标关联分析等。同时，上述 DBMind 功能总体上可以认为是一个近似使用滑动窗口进行离线分析的功能。

注

时序数据至少由两部分组成，即时间标志（可以是时间戳）和该时间标志上的值。为了方便表示，下文中所有时序数据均只表示其时间戳，省略具体值。表示形式可以是 (T1, T2, T3, T4)，也可以缩略为 (1, 2, 3, 4) 二者是等价的。用于表示时间标志为 1、2、3、4 以及其对应值组成的时间序列。

提出问题

问题 1：重复区间数据的缓存

例如，某时刻我们需要使用时间序列 (T0, T1, T2, ..., T99) 这 100 个样本点组成的数据进行分析；一段时间后，我们可能需要使用的时间序列为 (T50, T51, T52, ..., T149). 这个时间序列的长度仍然是 100, 但是，这两段时间序列之间明显是有重叠数据的。那么，我们不禁可以思考，如何实现一个缓存结构缓存从 (T50, T51, ..., T99) 这一段数据呢？

问题 2：区间合并与组织

思考这样一个问题，DBMind 内部的某个功能需要检索时间序列取值从 0 到 49 的数据，即(T0, T1, T2, ..., T49). 另一个功能检索了数据段从 40 到 100，那么，这两个时间段如果缓存到 Buffer 中，是可以进行区间合并的，也就是合并为 (T0, T1, T2, ..., T99, T100). 下次，某个功能如果检索的时间区间落在 (0, 100) 区间，则可以直接返回数据，避免从 TSDB（时序数据库）中获取数据的网络 IO.

问题 3：时序数据的下采样与上采样

面前两个问题，只引出了时序数据的起始和终止位置两个要素，起始时序数据还有间隔这个要素。例如，某时间序列 A = (T0, T1, T2, ..., T49) 可以作为时间序列 B = (T0, T2, T4, ..., T48) 的父序列，即可以从时间序列 A 上抽取出时间序列 B，这个过程称之为下采样（或降采样）。反之，如果从间隔更稀疏的数据则不可以恢复间隔更稠密的时序数据，否则可能会失真。根据上述描述，当我们已经缓存了时序数据 A，则可以从该时序数据中直接提取出时序序列 B，从而避免从 TSDB（时序数据库）中获取数据的网络 IO.

问题 4：缓存数据的淘汰机制如何设计？

我们前面只提到了可以将时序数据缓存到内存中，从而避免从 TSDB（时序数据库）中获取数据的网络 IO，那么，如果只是存储在内存中，不进行淘汰，数据迟早会导致系统 OOM. 如何组织数据的淘汰机制？

问题 5：如何进行数据对齐？

来自 TSDB（时序数据库）中的时序数据，可能不是干净的，也就是可能存在间隔不一致，起止时间不一致的情况，这样的话，不能直接把数据进行合并。例如时序数据 (100, 200, 300, ..., 1000) 和 (101, 201, 301, ..., 1001) 就没有对齐，这两个数据涉及到合并的话，还需要有一个 shift 的过程

解决问题

解决问题 1：构建一个树形结构

我们抛出了上面的问题 2，可以帮助我们分析我们可以使用的数据结构。例如某个时间序列 (1,2,3,4,5) 可以是 (1,2) 以及 (4,5) 的父序列。那么，我们可以构造某个树结构，来表示这层关系，例如：

      (1,2,3,4,5)  (1,2)       (3,4,5)                   (4,5)

当然，也可以是其他的形式，例如：

      (1,2,3,4,5)  (1,2,3)       (4,5)

如果是多叉树的话，则可以表示的形式就更多了。通过分析上述数据结构，我们发现，父节点其实只需要存储一个序列的起始值就可以了，具体的数据值由叶子节点来存储，父节点只需要存储指向叶子节点的引用即可，这样可以避免数据冗余。那么，这颗树就可以是：

        (1, 5)(1, 2)          (3, 5)          (3, 3)   (4, 5)  <--- 叶子节点，存具体序列值

或者是：

           (1, 5)        (1, 4)   (5, 5)    <--- 父节点，只存区间    (1, 3)   (4, 4)      (1,2,3)    <--- 叶子节点，存具体序列值

这样设计的一个好处是，可以容忍缺失值，当下次需要取出完整时序序列区间的时候，只需要从 TSDB（时序数据库）中获取缺失的数据即可，例如：

           (1, 5)        (1, 4)   (5, 5)     (1, 2)   (4, 4)  <--- 缺少序号为3的值

上面的例子，如果 caller 需要获取 (1, 5) 间隔为 1 的数据，则只需要从 TSDB（时序数据库）中获取序号为 3 的值，然后放到树种进行合并（merge），即可生成指定序列。这样，就减少了网络 IO.

通过上面的例子，我们可以看到，这个数的设计上，有点类似于区间树（segment tree）

细心的读者可能会发现，这里面我们只是使用了二叉树，那么为什么用二叉树，不用多叉树呢？因为，我们可以把父节点的左子树设置为值更小的序列范围，右子树设置为值更大的序列范围，这样的话，我们就可以通过二分搜索，快速地检索到我们需要定位的叶子节点了。同时，这个 Buffer 是存储在内存中的，如果树的高度比较高的话，开销也可控。因此，也不必像 B-tree 那样，做成一个多叉树。

但是，还有一个问题，我们前面提到的，如果一个树很高的话，我们实现的优化机制二分搜索的复杂度 O(logN) 就会退化为 O(N), 没有办法来优化数据了。例如：

               (1, 5)            (1, 4) (5, 5)        (1, 3) (4, 4)     (1, 2) (3, 3)   (1, 1) (2, 2)

例如检索时间编号为 1 的值，就会遍历 5 次，即 O(N)的复杂度。所以，老手艺就得用上了，也就是这个树的旋转和合并。这块太过于复杂，但总体思路与 B-tree, 红黑树的策略类似。只不过，这块我们用不到实现这么复杂，我们说过，叶子节点存储具体的值，那么我们就可以将叶节点向父节点进行合并，从而减小树高，提高算法效率。

解决问题 2：上、下采样问题

有了上面的数据结构，下采样就很简单了，我们只需要首先判断时序序列的时间间隔是不是更大，如果比现有树形结构的间隔更大，那么直接定位到指定区间，然后使用下采样算法进行数据点的抽取即可。下采样的方法可以取模，也可以使用滑动窗口（计算平均值、中位数或分位数）。如果是上采样，那么就麻烦了，例如当前缓存的树结构是的时间序列间隔是 10，某个 caller 调用时，希望使用的时间序列间隔是 1, 那显然不能满足 caller 的需求。需要从 TSDB（时序数据库）中获取数据，这样，从 TSDB（时序数据库）中获取到的数据，比当前缓存的 Tree 结构其实更好，这里面会涉及到一个权衡，即是不是可以把当前已经缓存的这个 Tree 结构淘汰，换用更密集的序列呢？这块实现也很复杂，此处不赘述。

淘汰机制

我们前面从背景上提到过，DBMind 的根本业务相当于一个滑动窗口，这样的话，滑动窗口的长度其实是固定的，我们就可以在内存中划定一个序列的缓存长度，超过这个长度直接淘汰掉就行了。只不过，该如何淘汰呢？应该由谁来驱动呢? DBMind 里面的实现机制是，通过实现一个 EvictThread 来完成的，只不过，线程在数据淘汰时候，需要加锁，否则容易会出现数据不一致的情况。而且，锁的粒度，最好也可以优化一下。即某个区间上的共享锁。不过，这个机制虽然更好，但是更复杂，实际实现上，只需要控制 EvictThread 的淘汰触发事件即可。

结语

即便是一个看似很简单的功能，如果想把它实现得比较优雅，那么需要考虑的方面也是足以让这个问题变得很复杂。对代码实现逻辑的复杂性、多角度思考，是代码实现过程中一个非常重要且有乐趣的一环，也是体现某款软件的软件工程能力好坏的重要因素。DBMind 是立足于 openGauss 自治数据库能力的载体，力争将软件工程能力做得更好，以便用户获得更优的软件体验。