背景
假设单个有状态实例支撑 1 W QPS，如果有 500 个实例，你可能会期望它们能够支撑 500 * 1W = 500W QPS 的流量。然而，实际情况可能会更为复杂。在实际系统中，添加多个实例并不总是线性地提高性能。
数据通常按照键进行分片。当你将数据分布在多个实例上时，不同的键可能被映射到不同的实例。如果你的访问模式导致某些键频繁被访问，而其他键很少被访问，那么可能会导致某些实例负载过高，而其他实例相对空闲。例如，如果某些热点键（hot keys）集中在同一实例，该实例可能会成为瓶颈。最终超过系统的承载能力，导致系统崩溃或性能下降。
处理热点数据是分布式系统中的常见挑战之一，如果预先知道某些键可能成为热点，可以将这些键手动分片到不同的实例。这样可以避免多个热点集中在同一个实例，实现负载均衡。
当然，也有一些通用的解决方案，包括：
- 缓存：将热点缓存到无状态服务中，减轻对热点集中的实例负载，提高系统性能。
- 动态分片：根据实时的负载情况，采用动态分片策略。如果某个键的访问频率增加，可以将其重新分片到其他实例，以实现负载均衡。
- 数据复制：特别重要的热点，可以将其复制到多个实例，将负载分散到多个实例。
此三者的第一步是一致的，首先要识别哪些数据是热点。
哈希表
如果你希望知道系统中哪些数据是频繁访问的，哈希表是一种有效的数据结构。你可以使用数据作为键，将访问次数作为值存储在哈希表中。每次访问数据项时，增加对应键的值。通过统计访问次数，你可以识别出热点数据。
当系统中的数据量很大时，哈希表的内存占用可能会成为一个问题。如果数据集非常庞大，可能需要考虑使用分布式存储或其他高效的数据结构来处理统计信息。
LRU
数据集庞大的场景，另外一个容易想到替代哈希表的选择是 LRU 缓存算法。
首先，LRU 算法因为是基于访问时间的顺序来进行缓存数据的淘汰，会相对较少淘汰热点数据，从而一定程度上减轻了 Hotkey 的影响。它没有识别出有效的热点数据，因此无法有效将热点数据均匀分散到多个实例。
其次，在缓存大小一定的前提下，LRU 算法的效果受数据集大小的影响。访问的数据集越大，效果越差。
最后，在极端要求的场景下，未优化的引入 LRU 会潜在带来延迟和性能方面的影响。
- 内存释放顺序导致的延迟增加
LRU 前：
请求到达——分配内存——返回结果——释放内存
LRU 后：
请求到达——分配内存——【缓存结果/淘汰内存】——返回结果
- 离散读写导致的锁冲突。
即使利用分片降低锁粒度，相比批量定时更新缓存，离线读写导致的锁冲突的概率仍然跟读写请求量正相关。当离散的将数据加入缓存，写入线程持有写锁时，其他线程无法获取读锁或者写锁，需要等待写锁释放，导致线程阻塞和上下文切换。
Heavy hitter
在大数据处理中，此类问题称之为：”Heavy hitter problem（Top K problem）”。类似的问题还有。在网络流量分析中，找出最常见的IP地址或协议可以帮助我们识别潜在的攻击或瓶颈。在广告领域，识别最热门的广告内容可以帮助优化广告投放和资源分配。
常见的解决 “heavy hitter” 问题的算法包括：
- Misra-Gries：实现较为简单，节省空间，但精度稍低。
- Count-Min Sketch(CMS)：团队同事力推的一个算法， CDN 识别热点，主动下推。但。采用类似 Bloom filter 的思想，牺牲了一定的准确度。见于缓存组件： Caffeine、ristretto。
- Space-saving(SS)：精度高，复杂度也更高一些。
三个算法的 Golang 版本实现 对比来看：CMS 算法使用哈希算法，如果数据不够离散，准确度下降的厉害（CDN 场景哈希文件名是由 MD5 生成，自然不成问题）；SS 算法相对来说更为稳定，虽然性能稍差，但可通过采样降低数据处理的量来降低性能的损耗。
本文作者 ： cyningsun
本文地址 ： https://www.cyningsun.com/06-13-2023/heavy-hitter.html
版权声明 ：本博客所有文章除特别声明外，均采用 CC BY-NC-ND 3.0 CN 许可协议。转载请注明出处！
