---
tags: [redis, heavykeeper, hot-key-detection, top-k, count-min-sketch]
create time: 2026-08-08 18:43
update time: 2026-08-08 18:43
---

# HeavyKeeper 热点探测算法

## 概述

在分布式缓存系统中，热点 Key（Hot Key）问题是一种特殊的缓存击穿现象：单个或少数几个 key 的访问频率远高于平均水平，超过底层 Redis 实例的处理能力。HeavyKeeper 是美团开源的一种在线 Top-K 热点检测算法，能够在 O(K) 空间复杂度的前提下，以极低的计算开销实时维护访问量最高的 K 个 key，同时具备抗误报、自适应衰减的能力。

## 核心原理

### Top-K 维护问题的背景

在海量流量中找出出现频率最高的 K 个元素，这是一个经典的流式计数问题。传统方案如排序法需要 O(N) 空间存储所有数据，不适合高并发场景。HeavyKeeper 的核心创新在于概率衰减加双计数器机制。

### Fading Count（概率衰减因子 alpha）

HeavyKeeper 的核心思想是每个计数器的值都会随着时间自然衰减。具体来说，每次增加计数时，实际增加值不是固定值 1，而是以概率 alpha（0 < alpha < 1）进行增加：

```
new_count = old_count * (1 - alpha) + alpha
```

这个设计的精妙之处在于：
- 自动淘汰旧热点：长期不更新的 key 其计数器会逐渐衰减到接近 0
- 无需显式 TTL：不像传统方案需要手动设置过期时间
- 响应速度快：alpha 越大衰减越快，对突发热点更敏感

### 双计数器结构（Error Counter + Main Counter）

HeavyKeeper 采用类似 Count-Min Sketch 的多哈希结构，但加入了关键改进每个 entry 使用两个计数器协同工作。

```mermaid
graph TB
    subgraph Input["输入流"]
        STREAM["key 访问序列 k1, k3, k1, k5"]
    end

    subgraph HK["HeavyKeeper 内部结构"]
        subgraph MT["主计数表 m 行"]
            T1["Table[0]: h0 -> MainC"]
            T2["Table[1]: h1 -> MainC"]
            Tm["Table[m-1]: hm -> MainC"]
        end
        
        subgraph ET["误差计数表 m 行"]
            E1["Table[0]: h0 -> ErrC"]
            E2["Table[1]: h1 -> ErrC"]
            Em["Table[m-1]: hm -> ErrC"]
        end
    end

    subgraph Output["Top-K 输出"]
        HEAP["最小堆保留最大值"]
    end

    STREAM --> T1
    STREAM --> T2
    STREAM --> Tm
    T1 -.-> E1
    T2 -.-> E2
    Tm -.-> Em
    T1 --> HEAP
    T2 --> HEAP
    Tm --> HEAP
```

**Main Counter（主计数器）**：记录 key 的实际访问次数（经过衰减）。当查询某个 key 的频率时取 m 个 hash 表中该 key 对应位置的最小值（与 Count-Min Sketch 一致）。

**Error Counter（误差计数器）**：专门用来估计其他冲突 key 可能造成的虚假抬高值。用同样的哈希方法但只在不冲突时递增。查询时，true_count 约等于 Main Counter 减去 Error Counter。

这一设计比 Count-Min Sketch 的关键优势是 CMS 没有误差补偿机制所有的 collision 都被计入；HeavyKeeper 通过 Error Counter 减去估计的碰撞干扰，大幅降低误报率。

### 最小堆淘汰机制

为了维护 Top-K，HeavyKeeper 内部维护一个大小为 K 的最小堆（min-heap）：

| 操作 | 行为 |
|------|------|
| Insert(key) | 更新所有 m 个表的 main/error counter，将当前估算频率插入堆 |
| Heap Full and New greater than Min | 弹出堆顶（最小的），插入新元素 |
| Heap Full and New less than or equal Min | 忽略新元素（已不在 Top-K 范围内） |

由于是最小堆，堆顶始终是当前 Top-K 中的最小值。只有新元素的估计频率大于堆顶时才有机会进入 Top-K。

### 空间复杂度分析

HeavyKeeper 的空间复杂度为 O(m x K)，其中：
- m 是计数表的行数（hash 函数数），通常取 4~8
- K 是要维护的 Top-K 大小
- 每个计数器为 uint32（4 bytes）

对比典型值：K = 1000, m = 4 -> 4000 个计数器 x 4 bytes = 16KB，极其紧凑。

### 与其他方案的对比

| 维度 | HeavyKeeper | Count-Min Sketch | Misra-Gries | Lossy Counting |
|------|-------------|------------------|-------------|---------------|
| 空间复杂度 | O(m x K) | O(m / epsilon) | O(1/epsilon x log N) | O(log(1/delta) / epsilon) |
| 支持 Top-K | 原生支持（最小堆） | 需外部维护 | 不支持直接 Top-K | 需额外数据结构 |
| 时间复杂度 | O(m) 每次 | O(m) 每次 | O(1) 每次 | O(1) 每次 |
| 误差控制 | Main 减 Error 双重抵消 | 仅有上界无下界 | bounded by epsi*N | bounded by delta*N |
| 自适应衰减 | 有（alpha 参数） | 无（需手动重置） | 有（阈值 cutoff） | 有（threshold decay） |
| 适用场景 | 实时热点检测加 Top-K | 频率近似估计 | 频繁项发现 | 概念漂移场景 |
| 工程落地难度 | 中 | 低 | 高 | 高 |

## 代码示例

Go 简化版 HeavyKeeper 核心逻辑：

```go
type HeavyKeeper struct {
    tables     [][]uint32
    errTables  [][]uint32
    hashFns    []hash.Hash64
    m          int
    k          int
    alpha      float64
    minHeap    *MinHeap
}

func (h *HeavyKeeper) Update(key string) {
    for i := 0; i < h.m; i++ {
        idx := h.hashFns[i].Hash([]byte(key)) % uint64(len(h.tables[i]))
        
        // Main Counter: 带衰减的增加
        val := uint32(float64(h.tables[i][idx])*(1-h.alpha) + h.alpha)
        h.tables[i][idx] = val
        
        // Error Counter: 只在非冲突时增长
        if h.errTables[i][idx] < h.tables[i][idx] {
            h.errTables[i][idx]++
        }
    }
    
    estFreq := h.estimateFrequency(key)
    h.minHeap.Insert(estFreq, key)
}

func (h *HeavyKeeper) estimateFrequency(key string) uint32 {
    minMain := ^uint32(0)
    maxErr := uint32(0)
    for i := 0; i < h.m; i++ {
        idx := h.hashFns[i].Hash([]byte(key)) % uint64(len(h.tables[i]))
        if h.tables[i][idx] < minMain {
            minMain = h.tables[i][idx]
        }
        if h.errTables[i][idx] > maxErr {
            maxErr = h.errTables[i][idx]
        }
    }
    if minMain > maxErr {
        return minMain - maxErr
    }
    return 0
}
```

## 实践场景

1. **Redis 热点探测**：在应用服务端部署 HeavyKeeper 实例，统计各 key 的 QPS，超过阈值的自动触发本地缓存预热或多实例分片隔离。这也是 ThumbUP 项目的核心技术之一。

2. **CDN 热点调度**：视频网站统计各资源的访问热度，动态调整 CDN 边缘节点的内容分发策略，把 Top-K 内容提前推送到最近节点。

3. **数据库慢查询告警**：不仅监测慢 SQL 的数量，用 HeavyKeeper 找出执行最频繁的 SQL 模式（通过 SQL fingerprint 作为 key），配合索引优化方案治理。

4. **反爬虫策略**：识别异常高频的请求来源 IP 和 URL 组合（将 ip 加 path 拼接作为 key），一旦进入 Top-K 立即触发验证码或限流。

> [!TIP]
> 面试加分点：可以讨论 alpha 参数的调优经验——alpha 大则衰减快、响应突发热点但不稳定；alpha 小则衰减慢、能记住长期热点但对突发反应迟钝。生产环境中 alpha 一般取 0.01 ~ 0.05，根据业务流量特征实验确定。

## 关联笔记

- [[03.Redis/strategies/多级缓存架构设计]]
- [[03.Redis/strategies/缓存穿透击穿雪崩解决方案]]
- [[03.Redis/core/集群与哨兵机制]]