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

作者: vearne
文章标题: 玩转Arduino(2)-按钮控制小灯
发表时间: 2024年10月20日
文章链接: https://vearne.cc/archives/40174
版权说明: CC BY-NC-ND 4.0 DEED

微信公众号

vearne@ut

262