热点检测治理

对于大部分互联网应用，数据访问频次分布通常满足二八定律，头部的20%数据往往占据超过80%的访问流量。在业务早期，由于流量较小，数据库就可以满足所有的访问流量，随着业务的发展，数据库无法抗住所有的流量，此时通常会引入高性能的缓存，用于缓解数据库的访问压力。得益于数据的二八分布，缓存的容量通常远远小于数据库的总容量，但是却能保证大部分的热点数据请求命中缓存。

这一套数据库+分布式缓存的架构在大部分场景中可以工作的很好。但是当出现热门活动以及突发热点时，缓存也极有可能被打崩。以S12为例，由于极度的流量访问倾斜，很容易导致部分缓存节点访问过热，对于过热节点，可以通过添加副本的方式来分担读流量，但是添加副本扩容的方式成本相对过高。此外当遇到突发热点时，这种突发热点很难进行提前预知扩容，突发流量很容易直接将缓存打崩。

对于变更不频繁的配置信息以及首页运营位推荐等数据量较小但访问频繁的的数据，使用小表广播的方式，每个应用实例在本地缓存全部信息，然后通过后台线程定期更新或者通过运营平台进行推送更新。该方案可以很好地解决一些更新不频繁的热点数据的访问，但是对于不同业务，每个业务都要单独实现一套本地的local cache，业务开发成本较为繁琐，且定期更新时效性较差。

对于高在线人数的直播间，通过准实时的访问流量统计，获取访问量topk的直播间，然后再主动推送给应用实例，应用实例收到推送以后，将该热点房间缓存到本地进行访问。通过准实时的统计以及推送可以拦截大部分的热门直播间以及热门视频的远程访问。然而该方案依然存在一些不足：统计时效性较差，对于突发热点检测不敏感，不同业务需要各自实现推送订阅以及本地缓存。

为了应对热门活动与突发热点，以及减少业务热点处理的开发量，我们开发了一套热点检测与治理框架。

该框架核心包含两个模块热点检测与本地缓存 。通过将该两个模块集成到缓存SDK 当中，实现了如下能力：

• 实时热点检测监控，便于业务发现访问热点

• 快速识别突发热点，并支持自动将热点数据加入本地缓存

• 高效的本地缓存策略，相同内存开销可以达到更高的本地缓存命中率

• 支持白名单，允许提前将活动id注册添加到本地缓存

• 透明接入，配置化开启热点检测与本地缓存

对于访问流量的热点检测，本质是如何从流式数据计算出topk。对于有限的数据项，可以简单地使用 Hashmap+Heap-Sort来对数据进行计数排序。但是对于海量数据以及有限的内存，该方法几乎是行不通的。因此我们需要使用更高效的数据结构和算法来实现。

lossy counting算法是在2002年提出的，算法的核心为将数据流切分成大小一样的许多窗口，窗口大小取决于期望的错误率。从第一个窗口开始，统计每个元素出现的频率。窗口结束时，将每个数的频率减1，同时将计数值为0的元素从内存中删除。通过减一和删除计数值为0的元素，可以大大地限制了内存的使用空间，同时也能近似地保证高频元素的准确性。

迭代处理每一个窗口，重复同样的流程在每一个窗口结束时将计数值减一同时删除计数为0的元素。直到所有窗口处理完毕或者到达数据检查点。此时将内存中剩余的元素进行排序，排序后的元素即为top k.

根据Zipf’s Law，元素在数据流中往往高度倾斜，少数高频元素往往占据数据流的大部分空间。通过减一剔除低频元素以后，虽然高频元素的频次也被减少了，但是依然能给出大致正确有意义的统计结果。

该算法的精髓在于通过剔除低频元素大大降低内存占用，同时以较小的错误率依然能得出较为精确的topk统计结果。

Count-Min Sketch算法于2004年提出，算法的原理与BloomFilter类似，不同之处在于，BloomFilter每一个位置存储的值是个bool值，通过bool值判断元素是否存在。Count-Min Sketch的每一个位置存储的则是一个计数，计数值表示元素的出现的频次。

算法的数据结构包含两个部分:

• 宽度为w，深度为d的二维整数数组。初始值为0

• d个独立的哈希函数(h1,h1..hd)

处理数据流时，对于每一个元素 n，首先将n分别用哈希函数h1..hd映射到二维数组中的每一个对应的位置。每一行的映射关系为idx = h(n)%w。找到每一行对应的idx以后，将相应位置的计数值+1。

处理完数据流以后，将得到一个包含计数的二维数组。此时如何得到一个元素的计数值呢？

要获取某个元素j的计数值的时候，只需将 j 通过哈希函数映射到对应的位置，然后读取对应的计数值。对于d个哈希函数的结果取最小值.

f[j] = mink CMS[k][hk(j)]

由于哈希冲突的存在，每一个位置的计数值肯定是偏大的，因此计数值越小说明哈希冲突概率越低，通过取最小值，可以更加接近真实的频率值。

但是该结构只是帮助我们获取对应元素的频率值，如果要获取topk，该如何做呢。答案很简单，我们只需通过最小堆额外维护一个topk即可。处理数据流的时候，再更新每一个位置计数值的同时，记录该元素的最小频率值，同时将该最小频率值与最小堆比较，如果该值大于堆顶元素，则将该元素加入最小堆。通过每次与最小堆堆顶对比决策更新最小堆元素。当数据流处理完以后，我们将得到频率最高的k个元素。再真实的数据流分布下，该最小堆可以得到及其近似的topk元素。具体误差和详细证明感兴趣可以参考论文原文。

HeavyKeeper于2018年提出，总体结构与Count-Min Sketch类似。与Count-Min Sketch不同的是，二维数组中每一个位置不在单纯保存计数值，而是同时保存了哈希指纹和计数值。同时对于哈希冲突的处理也存在差距。Count-Min Sketch对于哈希冲突，是直接对计数值加 1 ，然后对结果取最小值， 该方法会导致最终统计频次过大。HeaveyKeeper对于哈希冲突，则是进行计数值概率衰减。具体流程为:

对于数据流中的每一个元素，首先依然是通过d个哈希函数映射到二维数组对应的位置，找到对于位置以后。首先对比哈希指纹，如果哈希指纹相等，则对计数值进行加 1 ， 如果哈希指纹不相等，则说明存在哈希冲突，此时通过概率函数进行计数值衰减:

Pdecay = 1/ (b^C) (b < 1)

b表示衰减因子，C 为计数值，通过该概率函数，当计数值越大时，衰减概率越低，可以保证低频元素被快速剔除，同时保证高频元素较低的衰减概率从而保证频次的精确度。topk的实现则与Count-Min Sketch一样，通过最小堆来维护topk元素。

通过对比分析以上三个算法的topk精确度，频次准确率，以及内存开销， 在相同内存开销的基础上，HeavyKeeper可以提高更高的统计准确率，因此最终我们决定基于HeavyKeeper来实现我们的热点统计。

整个接口实现只包含三个函数， 具体的heavykeeper详细实现可以参考https://github.com/go-kratos/aegis/blob/main/topk/heavykeeper.go。

• Add 方法处理数据流中的每一个元素，并根据算法决定该元素是否能进入topk

• List 方法则返回当前topk中的元素列表

• Expelled会返回当前被驱逐出topk的元素。业务可以基于topk进行自定义的逻辑设计，比如下文要提到的热点本地缓存，当数据不在属于topk时，通过该方法可以将旧的热点数据驱逐出本地缓存从而保证本地缓存的热点新鲜度。

当出现哈希冲突的时候，原始的heavykeeper实现需要根据 计数值 C 进行计算指数概率然后进行衰减，当 C 的值比较大的时候，会存在较为严重的 指数计算 CPU 开销。为了降低 指数计算的cpu开销， 我们可以通过牺牲一定的指数精确值来降低运算次数。取衰减因子 b 取为0.925， 当C 等于256 的时候 ,取得的概率值已经是个极小的值，此时在计算精确的 指数值意义不大，因此当计数值大于256 的时候，我们可以都将概率近似为 b^256。

此外，当 C 小于256 的时候，我们还可以通过查表法的方式，进一步降低cpu的计算开销。通过维护 b的256次方数组，当实际计算的时候直接从数组取值从而减少cpu开销。

在大数据流中，原始的算法实现在统计topk的时候具有很高的准确率，但是对于在线实时热点统计，当出现突发热点数据的时候，由于历史数据流的频次统计堆积，原有算法很难快速识别突发热点。举个简单例子:

在实时数据流中统计出现频次最高的 top3，假设元素 a b c 是历史数据中访问频次最高的三个元素，且qps 都为10 ，在不考虑哈希冲突的情况下，假设数据流持续了1000s， 那么此时二维数组中这三个元素对应的频次则都为 1w, 从1001s开始，出现了一个突发热点元素d， 元素 d 的 qps 为100，按原始算法， 元素 d 得在频次超过1w以后才会被加入top3，当频次达到1w时，距离突发热点出现已经过去了100s，原始实现对于突发热点的检测是相当迟钝的。

为了提升对突发热点检测的敏感度， 我们需要对历史数据的频次统计进行额外的处理。在不影响总体请求占比的情况下， 我们可以对历史数据进行统一衰减。

具体实现为, 每隔 1s 所有元素的统计频次 Ci 衰减为 Ci = Ci / n, n为衰减因子，且n大于1，假设元素j平均每秒的新增频次记为 x ，则在第 k 秒，元素 j 的频次为

可得元素 j 在第 k 秒的一般表达式为

当 n 大于 1 时

取衰减因子 n = 2, 在上面的例子中，代入可得在1000s的时候元素a b c的频次近似为 2x 即 20， 此时当出现突发热点 d 的qps为100时，只需要 1s 元素d即可立刻被识别为top3 。

通过对历史统计频次进行衰减，我们可以快速灵敏地识别出突发热点流量。同时由于我们的衰减是针对所有元素及总数进行衰减的，在统计上依然可以保证元素请求占比的相对准确度。

在模拟突发热点压测的场景下，通过添加衰减因子可以极大地提升热点识别的检测速度。下图为添加衰减因子以后热点识别速度与本地缓存命中率。本地缓存部分会在下文进行展开。

在 1 时刻 未添加衰减因子的情况下，默认突发热点进行压测，大部分流量由于没法命中本地缓存会直接回源都远端 redis，导致redis qps快速上涨。在 2 时刻添加了衰减因子以后，由于热点可以快速被识别，因此当出现突发热点流量时，突发热点被快速识别并缓存在本地，本地缓存命中率快速上升，同时回源远端的redis请求也没出现明显上涨。

当出现超热数据时，即便是redis也可能无法抗住突发的海量请求，此时我们将请求截停在本地，通过本地缓存来降低对redis的压力。由于本地可用内存相对极少，因此我们需要将好钢用在刀刃上，用有限的内存，来响应尽可能多的请求。此时就需要我们提升本地缓存命中率。

本地缓存通常有两种实现方式， LRU 和 LFU，LFU 对于热点数据通常有较高的命中率，但是相应的实现复杂度也要比LRU 高。考虑到我们本身已经有热点识别模块，因此我们可以基于热点识别加上 LRU 来保证热点数据尽可能常驻缓存。

本地缓存模块的数据结构实现为经典的LRU ，此处不做赘述。不同点在于，我们对于LRU 的准入进行的前置判断。

topk的算法模块已在https://github.com/go-kratos/aegis 实现，自动热点本地缓存后续也会作为一个可用性中间件集成到Kratos (https://github.com/go-kratos/kratos) 中，应用可以基于该中间件对热点 url进行本地缓存。

在将元素添加进 LRU 之前，首先会判断该 key 是否为热点元素，如果是则加入 LRU ，否则不加入LRU， 通过前置检测，可以避免低频请求占据 LRU 内存空间。具体实现如下，其中topk为上文的热点检测模块

在热门活动时，热点是可以预知的，活动相关的 id 在活动开启的瞬间会立马成为热点数据。在该场景下，我们可以提前将活动相关id加入白名单。等到活动开启时，只要该id被访问到，立马会被加入本地缓存， 而无需等待热点检测模块进行检测。通过白名单可以避免突发热点流量瞬间将后端存储打死，虽然我们已经通过添加衰减因子来提升热点的检测敏感度，但是白名单可以进一步降低超级热点对后端的突发影响。最终本地缓存的实现为

热点检测与本地缓存为两个独立的模块，为了降低业务的使用成本，我们将这两个模块集成到框架的缓存SDK当中。业务无需改变sdk的使用习惯，只需添加配置即可开启热点检测与本地缓存。以redis sdk为例:

getFromLocalCache的实现非常简单，只需从本地LRU 中读取即可，updateLocalCache则包含了热点检测与缓存更新:

在b站的业务场景中，热门视频，热门话题往往占据着极高的流量，对于这些业务，如果能使用本地缓存来处理这些热门数据，那么就能极大低降低对后端的访问压力。以热门话题为例，在业务升级接入热点检测模块以后，在仅使用几M内存的情况下日常高峰期的本地缓存命中率达到35%。

出现超级热点时，本地缓存命中率甚至可以达到85%, 图一为本地缓存命中qps，图二则为业务访问的总qps

通过接入热点检测自动缓存以后，日常可以大幅降低redis缓存的资源开销，遇到突发热点时，又能进一步保障服务的可用性。

在互联网场景中，热点问题一直是个棘手的问题，但是如果我们使用合适的方法，对热点进行特殊处理，在一定程度上可以尽可能低降低热点对服务的影响。对于可以使用本地缓存的服务，该热点检测缓存模块可以让业务快速接入解决热点访问。对于数据一致性要求极高的场景，业务无法接入本地缓存带来的短暂不一致，那么则可以通过热点检测模块提前发现热点问题进行治理。通过 发现 + 治理 齐头并进，最终来达到服务的高可用。

参考文献

[1] LossyCounting: https://micvog.files.wordpress.com/2015/06/approximate_freq_count_over_data_streams_vldb_2002.pdf

[2] Count-Min Sketch: http://dimacs.rutgers.edu/~graham/pubs/papers/cmencyc.pdf

[3] HeavyKeeper: https://www.usenix.org/system/files/conference/atc18/atc18-gong.pdf

以上是今天的分享内容，如果你有什么想法或疑问，欢迎大家在留言区与我们互动，如果喜欢本期内容的话，欢迎点个“在看”吧！