高频增量告警查询中的轻量级区间LRU缓存方案

一、需求背景：高性能告警查询

在告警监控场景中，值守人员经常需要按时间段查询告警列表或其它相关信息。尤其在需要进行实时分析的自动化告警评估和推荐业务中，由于需要对时间段内全部告警进行评估，如果每次都要从数据库中加载完整数据，会产生很高的I/O负载，响应速度也不尽如人意。

安全事件应急响应分秒必争，系统能否及时处理用户的高频查询请求，不仅影响用户操作体验，更是决定应急处置速度的关键因素，不容疏失。

二、现有技术瓶颈

既然问题出在高频查询的I/O性能上，我们可能需要某种数据缓存机制来应对它。

但经初步调研，现有的常规缓存算法大多针对Key-Value键值对型结构，但在安全运营场景中的告警查询通常是以时间段为条件的，难以直接应用。

讲到这里，可能有的读者会问，如果只是为了解决时间段查询需求与键值缓存算法不匹配的问题，可以简单地将告警数据按一定时间周期进行切片并缓存，然后在每次查询时对查询目标范围所涉及的所有切片进行查询，再去掉两端可能多余的部分即可。

但这样一来，就会面临一个两难问题：

1、如果选择较大的切片长度，那么当实际查询片段较小或较为分散时，就会浪费很多资源。例如切片长度为1小时，若要查询某5分钟内的告警而未命中缓存，就不得不为此加载1小时的数据（甚至2小时，如果查询目标时间段刚好跨过分片边界的话），这极有可能导致添加缓存机制后的整体性能不升反降；

图1：长分片键值缓存响应区间查询

2、如果选择较小的切片长度，那么当实际查询片段较长时，就需要多次查询索引并加载缓存。例如切片长度为1分钟，若要查询某一天内的告警而未命中缓存，就需要执行多达1440次索引查询和加载。尤其对于使用哈希索引的缓存来说，这同样会导致查询性能低下。

图2：短分片键值缓存响应区间查询

此外，由于在很多实际场景中，现场未必能够提前部署高性能设备，导致告警评估系统经常需要安装在现场人员的笔记本电脑上，这就要求系统需要尽可能降低部署成本，避免依赖过于大型的外部组件。

综上，针对键值对结构的缓存系统确实不适合安全防守中需要高性能响应区间查询的场合。

三、实现思路

其实从上面的案例可以看到，缓存机制本身并没有问题，普通的基于链表的LRU缓存方案等都是可以的，只是常规缓存的索引结构（哈希表或二叉树等）不适配区间查询的场景。

那么重点就在于如何构建适合区间查询的索引了。一般想来，最适合这个场景的应该是区间树了，但初步实验中又遇到了问题：

由于告警查询最常见的场景就是“不断查询最新一定时间的告警”，导致区间树总是沿右子树方向生长，深度急剧增加。下图为模拟从1:00起每10分钟一次查询最近1小时告警的情况，可见区间树很快就变成了一个效率低下的形状：

图3：其中橙色节点是包含实际数据的叶节点

但是，区间树不同于常规二叉树，只有叶节点包含数据，实现旋转操作时需要修改枝节点的区间边界（而非简单交换节点父子关系），与常规的平衡二叉树略有不同：

图4：平衡区间树的旋转过程

至此，区间缓存结构最关键的部分就已经实现完毕了。关于LRU缓存算法的其余部分，以及数据合并切分的具体实现，由于与现有常规方法没有什么区别，本文不再赘述。

四、效果测试

我们接下来尝试查询1个小时的告警，可见此时缓存为空，实际耗时与没有缓存机制时基本相同，包含评估过程共耗时约36秒，其中数据加载消耗约28秒：

图5：初次查询的时间开销

然后再次提交完全相同的查询，可见总耗时迅速缩短到了约7秒，其中数据加载耗时基本可以忽略：

图6：再次查询的时间开销

但普通缓存结构显然也能做到这一点。接下来我们将查询时间段向后移动10分钟，可见实际需要加载的数据只有多出来的10分钟部分，数据加载仅耗时8秒：

图7：增量查询的时间开销

可见缓存结构确实能够极大提高告警数据区间查询的时间效率。

五、后记

系统性能优化的道路仍然漫长，点滴积累，贵在坚持。

如果您发现文中描述有不当之处，还请留言指出。在此致以真诚的感谢~