hotKey检测
对于访问流量的热点检测，本质是如何从流式数据计算出topk。对于有限的数据项，可以简单地使用 Hashmap+Heap-Sort来对数据进行计数排序。但是对于海量数据以及有限的内存，该方法几乎是行不通的。因此我们需要使用更高效的数据结构和算法来实现。
Majority问题
数组中有一个数字出现的次数超过数组长度的一半 m / 2，请找出这个数字。
解决：维护一个候选元素以及数量，如果下一个元素相同，则++， 否者–；计数为0时更换候选元素
- 最多扣减 m / 2 - 1次，因此majority元素不会被扣成0
Misra-Gries算法
推广
数据流中一共有m个元素，请找出出现频率超过m / k的k - 1个元素。
维护k - 1个候选值与计数器的集合：
如果元素在集合中，将其对应的计数器自增；
如果元素不在集合中且集合未满，就将元素加入集合，计数器设为1；
如果元素不在集合中且集合已满，将集合内所有计数器自减，计数器减为0的元素被移
每次减少计数k次（k-1 + 触发元素1），最多减少m/k 次，所以最终大于m/k的一定能留下来
最终结果能够保证没有假阴性（false negative），即不会漏掉实际频率高于m / k的元素。但可能会出现假阳性（false positive），即混入实际频率低于m / k的元素。
Lossy Counting
- 将数据切分成k个窗口，每次添加窗口内元素的频率并且最后 所有元素频率–，删除等于零的元素
- 窗口越大误差越小
Count-Min Sketch
一个二维数组，宽w（桶的个数），深度d（hash函数个数）
d个hash函数
每一个元素x，通过d个hash映射到d个位置上++
计数时，为d个hash函数的结果最小值；
结果偏大，hash冲突越低约接近真实值
获得topk：额外维护一个最小堆topk
HeavyKeeper
2018年提出，对CM sketch算法在hash冲突时进行了优化，使用指纹结合指数衰减，剔除低频袁术
初始化d个w桶的哈希表,所有指纹和计数器置零
对于数据流中的每个元素x:
- 计算d个哈希值: h1(x), h2(x), …, hd(x)
- 对每个哈希表i (1 ≤ i ≤ d):
- if 第hi(x)个桶的指纹为空或等于x的指纹:
- 增加计数器
- else:
- 以一定概率减少计数器
P = b^(-C)，C越小衰减概率越低，可用保证低频元素快速被剔除，而高频可以保留- b 是一个大于1的参数，通常设置为1.08
- C 是当前的计数器值
- 如果计数器变为0,则用x的指纹替换当前指纹
- 以一定概率减少计数器
- if 第hi(x)个桶的指纹为空或等于x的指纹:
查询时,返回d个表中x对应位置的最大计数值作为频率估计
突发流量：
原始的算法实现在统计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
假如qps为x，k秒后的值为等比数列求和，当k区域无穷大时，C(j,k) = n/(n-1) * x
京东
1、etcd集群
etcd作为一个高性能的配置中心，可以以极小的资源占用，提供高效的监听订阅服务。主要用于存放规则配置，各worker的ip地址，以及探测出的热key、手工添加的热key等。
2、client端jar包
就是在服务中添加的引用jar，引入后，就可以以便捷的方式去判断某key是否热key。同时，该jar完成了key上报、监听etcd里的rule变化、worker信息变化、热key变化，对热key进行本地caffeine缓存等。
3、worker端集群
worker端是一个独立部署的Java程序，启动后会连接etcd，并定期上报自己的ip信息，供client端获取地址并进行长连接。之后，主要就是对各个client发来的待测key进行累加计算，当达到etcd里设定的rule阈值后，将热key推送到各个client。
4、dashboard控制台
控制台是一个带可视化界面的Java程序，也是连接到etcd，之后在控制台设置各个APP的key规则，譬如2秒出现20次算热key。然后当worker探测出来热key后，会将key发往etcd，dashboard也会监听热key信息，进行入库保存记录。同时，dashboard也可以手工添加、删除热key，供各个client端监听。
得物
Burning的架构设计遵循了以上热点探测的技术原理，同时借鉴了jd-hotKey的设计思路，主要分为Burning-Admin、Burning-Worker、Burning-Config、Burning-Client四个模块：
- Burning-Admin （热点探测管理台）：与Worker节点Netty长链接通信，提供不同维度的应用管理和热点规则配置，提供查询热点数据统计，规则和热点数据监控大盘，提供工作集群信息查询及客户端节点信息查询，提供本地缓存动态配置及热点信息实时通知
- Burning-Worker（热点集中计算单元）：无状态server端，与管理台和客户端进行Netty长链接通信，获取规则，滑动窗口计算热点，将热点记录推送到管理台展示和客户端处理
- Burning-Config（热点配置中心）：作为热点、规则配置中心和注册中心，将规则配置下发到Worker节点和客户端，通过Raft算法进行系统高可用一致性保证
- Burning-Client（热点客户端SDK）：与Worker节点建立Netty长链接通信，监听配置中心配置变化定时推送热Key数据，获取热Key推送本地内缓存设置，与Redis-client无缝集成及其他ORM框架无缝集成
