heavykeeper算法的一些设计思想
版权声明 本站原创文章 由 萌叔 发表
转载请注明 萌叔 | https://vearne.cc
1.引言
topk问题是十分经典的算法问题，它的核心是从大量数据中找出前k个最大或者最小的元素。
它对于提高缓存的命中率，以及发现新增热点的发现有很大的帮助。
对于topk问题而言， 如果庞大的数据集本身是固定的，萌叔觉得topk问题本身还不算复杂， 顶多算是一个大数据计算的问题。
但如果这个庞大的数据集本身就处于变化中，不断在新增元素， topk问题就会变得非常复杂。
2023年萌叔看到一篇B站的文章，介绍了B站使用的heavykeeper算法来计算topk问题，取得了比较好的效果。
本文不是纯粹意义上的介绍heavykeeper算法的，萌叔想探讨一下里面的设计理念。
heavykeeper 对应的参考实现见参考资料4
B站给出的试验结果数据
2.数据结构
heavykeeper的设计目标是解决高流速情况下的topk问题且topk的元素出现的频率必须显著高于其它元素。
互联网数据大体满足二八定律，是符合要求的。
- 1）heavykeeper使用的d行w列的二维数组，
- 2）流体中的每个元素在 每一行上都有一个对应的位置，由哈希函数决定，哈希函数从h1()、h2() 到 hd()
这个数据结构与Count-Min Sketch算法是非常像的，唯一的区别是heavykeeper中二维数组的bucket，是一个结构体
type bucket struct {
fingerprint uint64 // 比Count-Min Sketch算法多出来的字段
count uint64
}
3.处理逻辑
对应代码 heavy_keeper.go
func (topk *TopK) jobAdder() {
for item := range topk.items {
itemFingerprint := xxhash.Checksum64S(item, uint64(topk.seed))
var maxCount uint64
itemHeapIdx, itemHeapExist := topk.minHeap.Find(item)
heapMin := topk.minHeap.Min()
// compute d hashes
for i := uint32(0); i < topk.depth; i++ {
bI := make([]byte, 4)
binary.LittleEndian.PutUint32(bI, uint32(i))
bucketNumber := xxhash.Checksum64S(append([]byte(item), bI...), uint64(topk.seed)) % uint64(topk.width)
topk.buckets[i][bucketNumber].mu.Lock()
fingerprint := topk.buckets[i][bucketNumber].fingerprint
count := topk.buckets[i][bucketNumber].count
if count == 0 { // Case 1
topk.buckets[i][bucketNumber].fingerprint = itemFingerprint
topk.buckets[i][bucketNumber].count = 1
maxCount = max(maxCount, 1)
} else if fingerprint == itemFingerprint { // Case 2
if itemHeapExist || count <= heapMin {
topk.buckets[i][bucketNumber].count++
maxCount = max(maxCount, topk.buckets[i][bucketNumber].count)
}
} else { // Case 3
decay := math.Pow(topk.decay, float64(count))
if rand.Float64() < decay {
topk.buckets[i][bucketNumber].count--
if topk.buckets[i][bucketNumber].count == 0 {
topk.buckets[i][bucketNumber].fingerprint = itemFingerprint
topk.buckets[i][bucketNumber].count = 1
maxCount = max(maxCount, 1)
}
}
}
topk.buckets[i][bucketNumber].mu.Unlock()
}
// update heap
if itemHeapExist {
topk.minHeap.Fix(itemHeapIdx, maxCount)
} else {
topk.minHeap.Add(minheap.Node{
Count: maxCount,
Item: item,
})
}
}
}
3.1 众数问题
看到上面的处理逻辑，很多读者可能会感到懵，为什么这样做就可以找出topk的元素？
为了解释heavykeeper的设计理念，我们先来看一个求众数问题
LeetCode 第169题
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
解答
此问题有一种特殊的解法: Boyer-Moore 投票算法。这种算法的时间复杂度为O(n)，空间复杂度为O(1)。
官方解释
如果我们把众数记为 +1，把其他数记为 −1，将它们全部加起来，显然和大于 0，从结果本身我们可以看出众数比其他数多。
萌叔的理解
- 从集合中任意取2个元素
- 如果它们不相同，就认为他们相互抵消掉了;如果相同，还放回集合
- 由于众数的数量超过集合中元素总数量的一半，重复步骤1和2，一段时间后，只有众数会被剩下来
C++代码示例
class Solution {
public:
int majorityElement(vector<int>& nums) {
int candidate = -1;
int count = 0;
for (int num : nums) {
if (num == candidate)
++count;
else if (--count < 0) {
candidate = num;
count = 1;
}
}
return candidate;
}
};
3.2 延伸
我们能容易发现，
* heavykeeper的处理逻辑就是Boyer-Moore投票算法的变种，
* Boyer-Moore投票算法寻找的是唯一的1个众数，heavykeeper寻找的k个”众数”
Q: d * w 二维数组的作用？
A:
对于Boyer-Moore投票算法， 不同的元素如果落在同一个bucket中，它们就会相互抵消。为了保证k个”众数”,
都能被发现，就要求他们尽可能落到不同的bucket中。它们可以与其他元素发生碰撞，但最好是不要互相碰撞。
如果相互碰撞，可能导致某些topk中的元素无法露出。
d个哈希函数，以及每行w列个元素都是确保元素在二维数组中的分布尽可能的散开。
这里还有个2个隐含的要求:
* w的取值必须远大于k
* topk的元素的数量要显著的大于其它元素的数量
Q: 为什么在Count-Min Sketch算法中，estimate()取多个bucket中的最小值当做元素的出现次数，而在heavykeeper算法用最大值作为元素的出现次数？
A:
在Count-Min Sketch算法中，如果元素发生碰撞，bucket中的count+1，这样会导致count偏大，因此取最小值;
而在heavykeeper算法中，元素如果发生碰撞，bucket中的count-1, 这样会导致count偏小，因此取最大值
总结
heavykeeper算法其实结合了Count-Min Sketch算法和Boyer-Moore投票算法，非常的巧妙，值得看一看。
参考资料3 热点检测治理，B站在heavykeeper算法的基础上，又做了一些优化也非常推荐看一下。
参考资料
1.Count-Min Sketch
2.HeavyKeeper
3.热点检测治理
4.migotom/heavykeeper
5.Boyer–Moore majority vote algorithm
