151 lines
7.5 KiB
Markdown
151 lines
7.5 KiB
Markdown
---
|
||
tags: [test/review, redis, heavykeeper, hot-key-detection, top-k, count-min-sketch]
|
||
create time: 2026-08-09 12:00
|
||
---
|
||
|
||
# HeavyKeeper热点探测算法_测试题
|
||
|
||
## 概述
|
||
本测试覆盖 HeavyKeeper 作为在线 Top-K 热点检测算法的核心原理，包括 Fading Count 概率衰减、双计数器结构、最小堆淘汰机制及与其他方案的对比。共 10 道题：6 道选择题、3 道填空题、1 道简答题。
|
||
|
||
---
|
||
|
||
## 一、选择题（6道，由浅入深）
|
||
|
||
> **难度阶梯**: Q1-Q2 基础概念 → Q3-Q4 核心原理 → Q5-Q6 深入应用/边界场景
|
||
|
||
### Q1（基础）— 考察定义层面
|
||
|
||
HeavyKeeper 是一个什么样的算法？
|
||
|
||
A. 离线批量排序算法，需要对全量数据排序后取 Top-K
|
||
B. 在线流式计数算法，以 O(K) 空间复杂度实时维护访问量最高的 K 个 key
|
||
C. 基于规则的热点阈值告警系统
|
||
D. 用于 Redis 集群分片的负载均衡算法
|
||
|
||
### Q2（基础）— 考察行为判断
|
||
|
||
HeavyKeeper 的 Fading Count 衰减公式为：`new_count = old_count * (1 - alpha) + alpha`。当 alpha 取值较大（接近 1）时，会发生什么？
|
||
|
||
A. 计数器衰减极慢，能长期记住热点
|
||
B. 计数器衰减快，对突发热点更敏感但不稳定
|
||
C. 计数器不再衰减，变成固定计数
|
||
D. 计数器变成负数
|
||
|
||
### Q3（进阶）— 考察核心原理
|
||
|
||
HeavyKeeper 采用双计数器结构（Main Counter + Error Counter），与 Count-Min Sketch 相比的关键优势是什么？
|
||
|
||
A. HeavyKeeper 使用了更多的 hash 函数
|
||
B. Error Counter 可以估计碰撞干扰并从 Main Counter 中减去，大幅降低误报率
|
||
C. HeavyKeeper 不需要最小堆来维护 Top-K
|
||
D. Error Counter 比 Main Counter 有更高的精度
|
||
|
||
### Q4（进阶）— 考察对比辨析
|
||
|
||
在空间复杂度方面，HeavyKeeper 的典型配置是 m=4, K=1000（每个计数器 uint32，4 bytes），总空间约为：
|
||
|
||
A. 4KB
|
||
B. 16KB
|
||
C. 64KB
|
||
D. 256KB
|
||
|
||
### Q5（深入）— 考察场景推理
|
||
|
||
在一个高并发的电商秒杀场景中，HeavyKeeper 部署在每个应用服务端实例上监控各 SKU 的访问热度。当发现某个 SKU 进入 Top-K 时，自动触发的优化措施是：
|
||
|
||
A. 将该 SKU 的所有请求转发到单一的 Redis 节点处理
|
||
B. 触发本地缓存预热或多实例分片隔离
|
||
C. 暂停对该 SKU 的所有写操作
|
||
D. 将所有请求排队等待统一处理
|
||
|
||
### Q6（深入）— 考察源码级别细节
|
||
|
||
HeavyKeeper 的 estimateFrequency 方法在查询某个 key 的真实频率时，是如何利用两个计数器表的？
|
||
|
||
A. 取 m 个表中 Main Counter 的最大值加上 Error Counter 的最小值
|
||
B. 取 m 个表中 Main Counter 的最小值减去 Error Counter 的最大值
|
||
C. 取 m 个表中 Error Counter 的最小值减去 Main Counter 的最大值
|
||
D. 对所有 m 个表的两个计数器求和取平均
|
||
|
||
---
|
||
|
||
## 二、填空题（3道）
|
||
|
||
### F1 — 填空
|
||
|
||
HeavyKeeper 内部维护一个大小为 K 的 ______ 来保留当前访问量最高的 K 个 key。只有新元素的估计频率大于堆顶时才有机会进入 Top-K。
|
||
|
||
> **提示**: 堆的顶部是最小还是最大的元素？
|
||
|
||
### F2 — 填空
|
||
|
||
HeavyKeeper 的空间复杂度为 O(m × K)，其中 m 是计数表的行数（hash 函数数，通常取 ______ ~ 8），K 是要维护的 Top-K 大小。
|
||
|
||
> **提示**: m 的典型下限值是多少？
|
||
|
||
### F3 — 填空
|
||
|
||
生产环境中 HeavyKeeper 的 alpha 参数一般取 ______ ~ 0.05，alpha 越大衰减越快、响应突发热点但不稳定；alpha 小则衰减慢、能记住长期热点但对突发反应迟钝。
|
||
|
||
> **提示**: 回顾文档中的调优经验。
|
||
|
||
---
|
||
|
||
## 三、简答题（1道）
|
||
|
||
### S1
|
||
|
||
一个视频网站的 CDN 调度系统需要实时监控全球边缘节点的资源访问热度。需求如下：
|
||
- 每秒约有 1 亿次访问请求
|
||
- 需要找出 Top-1000 的热度内容
|
||
- 需要能快速感知新冒出的热点（应对突发事件如热门视频发布）
|
||
- 不能承受过高的内存开销
|
||
|
||
请设计一个基于 HeavyKeeper 的热点检测方案，说明：
|
||
1. 部署架构（在哪里部署 HeavyKeeper 实例？）
|
||
2. Alpha 参数的选择依据
|
||
3. 为什么选择 HeavyKeeper 而非 Count-Min Sketch？
|
||
|
||
> **答题框架提示**:
|
||
1. 部署位置和聚合策略
|
||
2. Alpha 参数对突发敏感度的影响
|
||
3. HeavyKeeper vs CMS 的核心差异
|
||
|
||
---
|
||
|
||
## 参考答案与解析
|
||
|
||
### 选择题答案
|
||
|
||
| 题号 | 正确答案 | 解析 |
|
||
|------|---------|------|
|
||
| Q1 | B | HeavyKeeper 是美团开源的在线 Top-K 热点检测算法，能够在 O(K) 空间复杂度的前提下以极低计算开销实时维护访问量最高的 K 个 key。它具有抗误报、自适应衰减的能力。A 错误——它是流式在线算法而非离线批处理。 |
|
||
| Q2 | B | alpha 越大衰减越快，对突发热点更敏感但也更不稳定。alpha 小则衰减慢能记住长期热点但对突发反应迟钝。这是一个需要权衡的参数。 |
|
||
| Q3 | B | HeavyKeeper 的双计数器结构中，Error Counter 专门用来估计其他冲突 key 可能造成的虚假抬高值。真实频率 ≈ Main Counter 最小值 - Error Counter 最大值。这是相比 CMS 的关键改进——CMS 没有误差补偿，所有 collision 都被计入。 |
|
||
| Q4 | B | m=4, K=1000 → 4 × 1000 = 4000 个计数器 × 4 bytes = 16KB。极其紧凑！这也是 HeavyKeeper 工程落地的最大优势之一。 |
|
||
| Q5 | B | 发现热点 SKU 后自动触发本地缓存预热（L1）或多实例分片隔离，让不同用户的请求打散到多个 Redis 实例，避免单个实例被打垮。 |
|
||
| Q6 | B | estimateFrequency 的核心：取 m 个表中 Main Counter 的最小值（与 CMS 一致），减去 Error Counter 的最大值（HeavyKeeper 的独有贡献），得到估计的真实频率。如果结果小于 0 则返回 0。 |
|
||
|
||
### 填空题答案
|
||
|
||
| 题号 | 答案 | 解析 |
|
||
|------|------|------|
|
||
| F1 | 最小堆（min-heap） | 最小堆的堆顶是当前 Top-K 中最小的元素。新元素只有大于堆顶时才可能进入 Top-K，否则忽略。弹出堆顶插入新元素维持堆大小不变。 |
|
||
| F2 | 4 | m 是计数表行数（hash 函数数），通常取 4~8。更多行能提高精度但增加内存和计算开销。典型配置 K=1000, m=4 仅需 16KB。 |
|
||
| F3 | 0.01 | 生产环境中 alpha 一般取 0.01~0.05，根据业务流量特征实验确定。大 alpha 对突发敏感但容易抖动，小 alpha 稳定但对突发反应迟钝。 |
|
||
|
||
### 简答题参考答案
|
||
|
||
S1：**参考答案要点**：
|
||
1. 部署架构：在每个应用服务端实例上部署 HeavyKeeper 实例统计 local key 的 QPS，然后定期（如每秒）将所有实例的局部 Top-K 合并到全局 Top-K。或者在网关层统一部署一个 HeavyKeeper 收集所有流量的完整视图（更精确但单点压力大）。
|
||
2. Alpha 参数选择：取 0.03~0.05 偏大值。原因：视频网站热点可能突然爆发（如新剧上线），需要快速感知突发热点。较小的 alpha 虽然稳定但响应延迟偏高。
|
||
3. HeavyKeeper vs CMS 的核心差异：CMS 只有上界没有下界，所有 collision 都被计入 Main Counter 导致误报率高；HeavyKeeper 通过 Error Counter 减去估计的碰撞干扰，大幅降低误报率。此外 HeavyKeeper 原生支持 Top-K（通过最小堆），而 CMS 需要外部维护。
|
||
|
||
**评分标准**：答出任意 2 个要点即可得满分；完全正确需覆盖部署架构、alpha 选择依据和算法对比三个维度。
|
||
|
||
## 关联笔记
|
||
- [[03.Redis/strategies/多级缓存架构设计]]
|
||
- [[03.Redis/strategies/缓存穿透击穿雪崩解决方案]]
|
||
- [[03.Redis/core/集群与哨兵机制]]
|