heavykeeper算法的一些设计思想
版权声明 本站原创文章 由 萌叔 发表 转载请注明 萌叔 | http://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题 ...