业务场景算法：限流、Top-K 与一致性哈希

真实世界的算法和面试题不一样——它们有明确的业务背景。本文以"业务场景 → 算法抽象 → 实现"的格式组织，覆盖限流、一致性哈希、Top-K、去重、分布式 ID、缓存淘汰等高频场景。

目录

章节	说明
限流算法	计数器/滑动窗口/漏桶/令牌桶对比
一致性哈希	虚拟节点代码实现
Top-K 与排名	堆/BFPRT/Redis ZSet
去重算法	布隆过滤器代码 + HyperLogLog 原理
缓存淘汰	LRU/LFU O(1) 实现
分布式 ID	雪花算法代码 + 时钟回拨处理

限流算法

为什么需要限流

服务的处理能力有上限。面对以下三类场景，需要主动控制流量：

场景	例子
突发流量	微博热搜、双十一秒杀
恶意流量	爬虫、DDoS 攻击
业务需要	云服务按等级限制 QPS

核心原则：宁可拒绝部分请求，也不让整个系统崩溃。

四种算法原理对比

算法	原理	优点	缺点	适用场景
计数器	固定窗口内计数	简单，无延迟	临界问题（窗口边界突刺）	粗粒度限流
滑动窗口	多个小区间滑动统计	解决临界问题	内存开销大	精度要求较高
漏桶	队列定速消费	流量绝对平滑	无法应对突发，有延迟	后台任务
令牌桶	定速放令牌，有令牌才处理	允许一定突发	实现略复杂	大多数 API 限流

计数器的临界问题：在窗口边界前后各发 100 个请求（共 200 个），两个窗口都认为自己未超限，但实际 1 秒内处理了 200 个请求，超出了限制。滑动窗口通过细粒度的时间格解决了这个问题。

令牌桶实现（Go 版本，可类比 Java）

type RateLimiter struct {
    rate   int64      // 每秒放入令牌数
    max    int64      // 令牌桶最大容量
    last   int64      // 上次请求时间（Unix 秒）
    amount int64      // 当前令牌数
    lock   sync.Mutex
}

func (rl *RateLimiter) Pass() bool {
    rl.lock.Lock()
    defer rl.lock.Unlock()

    now := time.Now().Unix()
    passed := now - rl.last                  // 距上次请求的秒数
    amount := rl.amount + passed*rl.rate     // 新增令牌
    if amount > rl.max {
        amount = rl.max                      // 不超过上限
    }
    if amount <= 0 {
        return false                         // 无令牌，拒绝
    }
    amount--
    rl.amount = amount
    rl.last = now
    return true
}

关键设计：不需要真的维护一个队列，通过时间差计算模拟令牌积累，约 50 行代码即可实现。令牌桶的"桶容量"决定了允许的最大突发量——桶满时一次性消费所有令牌，就是允许的最大突发。

滑动窗口实现（Java，基于 Redis ZSET）

// key: 用户/IP 标识，limit: 时间窗口内最大请求数，windowMs: 窗口大小（毫秒）
public boolean isAllowed(String key, int limit, long windowMs) {
    long now = System.currentTimeMillis();
    long windowStart = now - windowMs;

    try (Jedis jedis = pool.getResource()) {
        Pipeline pipe = jedis.pipelined();
        pipe.zremrangeByScore(key, 0, windowStart);  // 移除窗口外的请求
        pipe.zcard(key);                              // 统计窗口内请求数
        pipe.zadd(key, now, String.valueOf(now));     // 记录本次请求
        pipe.expire(key, (int)(windowMs / 1000) + 1);
        List<Object> results = pipe.syncAndReturnAll();

        long count = (Long) results.get(1);
        return count < limit;
    }
}

一致性哈希

为什么普通哈希不够用

分布式缓存集群扩缩容时，key % N 的方式会导致大量 key 重新映射（缓存雪崩）。

目标：节点增减时，只有少量 key 需要重新分配。

一致性哈希原理

1. 将整个哈希空间想象成一个 2³² 大小的环
2. 节点（bucket）通过哈希映射到环上某个位置
3. 请求（item）也映射到环上，顺时针找最近的节点
4. 为解决负载不均，引入虚拟节点：每个真实节点在环上放多个副本

真实节点 A → 虚拟节点 A-0, A-1, A-2, ... A-k

虚拟节点的作用：真实节点少时，哈希环上分布不均匀，某些节点承担的请求远多于其他节点。虚拟节点让每个真实节点在环上均匀分布，负载更均衡。

代码实现（Go，约 50 行）

import (
    "hash/crc32"
    "sort"
    "strconv"
)

type HashRing struct {
    nodes      map[uint32]string  // 哈希值 → 节点名
    replicates int                // 虚拟节点数量
    keys       []uint32           // 排序后的哈希值列表
}

func New(replicates int) *HashRing {
    return &HashRing{
        replicates: replicates,
        nodes:      make(map[uint32]string),
    }
}

// Add 向哈希环添加一个节点（及其虚拟节点）
func (h *HashRing) Add(node string) {
    for i := 0; i < h.replicates; i++ {
        hash := crc32.ChecksumIEEE([]byte(node + "-" + strconv.Itoa(i)))
        h.keys = append(h.keys, hash)
        h.nodes[hash] = node
    }
    // 保持有序，方便二分查找
    sort.Slice(h.keys, func(i, j int) bool { return h.keys[i] < h.keys[j] })
}

// Get 根据 key 找到负责的节点
func (h *HashRing) Get(key string) string {
    hash := crc32.ChecksumIEEE([]byte(key))
    // 二分查找第一个 >= hash 的位置（顺时针最近节点）
    idx := sort.Search(len(h.keys), func(i int) bool {
        return h.keys[i] >= hash
    })
    if idx == len(h.keys) {
        idx = 0  // 环形，超过最大值则回到起点
    }
    return h.nodes[h.keys[idx]]
}

效果：节点数量变化时，平均只有 1/N 的 key 需要重新分配（N 为节点数）。

Top-K 与排名

业务场景

• 热搜榜 Top-10
• 商品销量 Top-100
• 用户积分排名

三种方案对比

方案	时间复杂度	适用场景
全排序	O(nlogn)	数据量小，一次性查询
小顶堆	O(nlogk)	流式数据，k 较小
BFPRT（线性选择）	O(n)	精确第 k 大，一次性
Redis ZSet	O(logn) 插入	实时排行榜，动态更新

小顶堆求 Top-K（Java）

// 从 n 个数中找最大的 k 个数
// 为什么用小顶堆而不是大顶堆？
// 大顶堆需要全部入堆再弹出 k 次，O(n + klogn)
// 小顶堆维护 k 个最大值：堆顶是这 k 个数中最小的，遇到更大的就替换
public int[] topK(int[] nums, int k) {
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
    for (int num : nums) {
        if (minHeap.size() < k) {
            minHeap.offer(num);
        } else if (num > minHeap.peek()) {
            minHeap.poll();       // 踢出最小值
            minHeap.offer(num);   // 放入更大的值
        }
    }
    return minHeap.stream().mapToInt(i -> i).toArray();
}
// 时间 O(nlogk)，空间 O(k)
// 优势：不需要全部数据加载到内存，适合流式处理

Redis ZSet 实现实时排行榜

// 更新用户分数
jedis.zadd("leaderboard", score, userId);

// 获取 Top-K（降序）
Set<Tuple> top10 = jedis.zrevrangeWithScores("leaderboard", 0, 9);

// 获取某用户排名（0-indexed，从高到低）
Long rank = jedis.zrevrank("leaderboard", userId);

// 获取某用户分数
Double userScore = jedis.zscore("leaderboard", userId);

为什么 Redis ZSet 适合排行榜：底层用跳表（skiplist）实现，插入/删除/查询排名都是 O(logn)，支持范围查询。跳表相比红黑树的优势是实现简单、并发性更好（可以用 CAS 做无锁并发）。

去重算法

业务场景

• 海量 URL 去重（爬虫）
• 缓存穿透防护
• 用户访问计数（UV）

布隆过滤器

原理：用 k 个哈希函数将元素映射到 Bitmap 的 k 个位置，置为 1。

• 判断不存在：k 个位置中有任何一位为 0 → 一定不存在
• 判断可能存在：k 个位置全为 1 → 可能存在（有误判率）

为什么有误判但没有漏判？ 插入时置 1 是永久的，所以已插入的元素查询时 k 个位一定全为 1，不会漏判。但不同元素可能共享某些位，导致误判（把未插入的元素判断为已插入）。

误判率公式：

误判率 ≈ (1 - e^(-kn/m))^k

其中：m = Bitmap 位数，n = 已插入元素数，k = 哈希函数个数
经验值：100 万数据，5 次 Hash，700 万位 Bitmap（<1MB），误判率 < 5%

使用 Guava 布隆过滤器（Java）：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

// 创建：预期 100 万元素，误判率 1%
BloomFilter<String> filter = BloomFilter.create(
    Funnels.stringFunnel(Charset.forName("UTF-8")),
    1_000_000,   // 预期元素数量
    0.01         // 误判率
);

// 添加元素
filter.put("user:12345");

// 查询（注意：返回 true 不代表一定存在）
boolean mightExist = filter.mightContain("user:12345");

缓存穿透防护流程：

请求 key
  → 布隆过滤器判断
      → 不存在：直接返回 null（拦截穿透）
      → 可能存在：查 Redis
          → 命中：返回
          → 未命中：查数据库
              → 有数据：写入 Redis，返回
              → 无数据：返回 null（5% 误判穿透可接受）

局限性：

1. 有误判率（可接受）
2. 不支持删除：某位的 1 可能被多个元素共享，删除一个元素会影响其他元素的判断。解决方案：Counting Bloom Filter（每位改为计数器）

HyperLogLog（基数估计）

场景：统计网站 UV（独立访客数），允许约 0.81% 的误差。

为什么不用 HashSet？ HashSet 存储每个 userId，内存随数据量线性增长，百万用户需要数十 MB。HyperLogLog 只需固定的 12KB，误差仅 0.81%，是工程上的极佳权衡。

// Redis HyperLogLog 统计 UV
jedis.pfadd("uv:20240101", userId);    // 记录访问
long uv = jedis.pfcount("uv:20240101"); // 估算独立访客数

// 合并多天数据
jedis.pfmerge("uv:week", "uv:20240101", "uv:20240102");

三种方案对比：

方案	内存	精度	适用
HashSet	O(n)	精确	数据量小
布隆过滤器	O(m) 固定	有误判	判断存在性
HyperLogLog	约 12KB 固定	~0.81% 误差	大规模基数估计

缓存淘汰

LRU（最近最少使用）

核心思想：利用时间局部性，优先淘汰最久未访问的数据。

数据结构：哈希表 + 双向链表（LinkedHashMap）

• 哈希表：O(1) 查找节点
• 双向链表：O(1) 移动节点（需要双向才能 O(1) 删除任意节点）

为什么用双向链表而非单向链表？ 删除任意节点需要知道前驱节点，单向链表需要 O(n) 遍历，双向链表可以通过 node.prev 直接 O(1) 操作。

Java O(1) 实现：

class LRUCache {
    private final int capacity;
    private final Map<Integer, Node> map = new HashMap<>();
    private final Node head = new Node(0, 0);  // 虚拟头节点（最近使用端）
    private final Node tail = new Node(0, 0);  // 虚拟尾节点（最久未用端）

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        if (!map.containsKey(key)) return -1;
        Node node = map.get(key);
        moveToHead(node);    // 访问后移到头部（最近使用）
        return node.val;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.val = value;
            moveToHead(node);
        } else {
            Node node = new Node(key, value);
            map.put(key, node);
            addToHead(node);
            if (map.size() > capacity) {
                Node removed = removeTail();  // 淘汰最久未用的
                map.remove(removed.key);
            }
        }
    }

    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private Node removeTail() {
        Node node = tail.prev;
        removeNode(node);
        return node;
    }

    static class Node {
        int key, val;
        Node prev, next;
        Node(int key, int val) { this.key = key; this.val = val; }
    }
}
// get/put 均为 O(1)

LFU（最不经常使用）

核心思想：淘汰访问频次最低的数据；频次相同时淘汰最久未访问的。

数据结构：

• keyMap：key → (value, freq)
• freqMap：freq → LinkedHashSet（保持插入顺序，方便淘汰）
• minFreq：当前最小频次

为什么用 LinkedHashSet？ 同频次的 key 需要按插入顺序淘汰（即最久未访问的），LinkedHashSet 保持插入顺序且支持 O(1) 删除，恰好满足需求。

class LFUCache {
    private final int capacity;
    private int minFreq = 0;
    private final Map<Integer, int[]> keyMap = new HashMap<>(); // key -> [val, freq]
    private final Map<Integer, LinkedHashSet<Integer>> freqMap = new HashMap<>();

    public LFUCache(int capacity) { this.capacity = capacity; }

    public int get(int key) {
        if (!keyMap.containsKey(key)) return -1;
        increaseFreq(key);
        return keyMap.get(key)[0];
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (keyMap.containsKey(key)) {
            keyMap.get(key)[0] = value;
            increaseFreq(key);
        } else {
            if (keyMap.size() >= capacity) evict();
            keyMap.put(key, new int[]{value, 1});
            freqMap.computeIfAbsent(1, k -> new LinkedHashSet<>()).add(key);
            minFreq = 1;
        }
    }

    private void increaseFreq(int key) {
        int freq = keyMap.get(key)[1];
        keyMap.get(key)[1]++;
        freqMap.get(freq).remove(key);
        if (freqMap.get(freq).isEmpty()) {
            freqMap.remove(freq);
            if (minFreq == freq) minFreq++;
        }
        freqMap.computeIfAbsent(freq + 1, k -> new LinkedHashSet<>()).add(key);
    }

    private void evict() {
        LinkedHashSet<Integer> minSet = freqMap.get(minFreq);
        int evictKey = minSet.iterator().next();  // 最久未用的（LinkedHashSet 保持插入顺序）
        minSet.remove(evictKey);
        if (minSet.isEmpty()) freqMap.remove(minFreq);
        keyMap.remove(evictKey);
    }
}
// get/put 均为 O(1)

LRU vs LFU 对比

维度	LRU	LFU
淘汰策略	最久未访问	访问频次最低
适用场景	时间局部性强（最近访问的更可能再次访问）	频率局部性强（热点数据长期高频）
缺点	偶发的大批量扫描会污染缓存	新加入的热点数据频次低，容易被误淘汰
Redis 支持	allkeys-lru / volatile-lru	allkeys-lfu / volatile-lfu

分布式 ID

业务需求

• 全局唯一：多节点并发生成不重复
• 粗略有序：按时间递增，便于数据库索引
• 高性能：本地生成，无网络调用

主流方案对比

方案	唯一性	有序性	性能	缺点
数据库自增	全局唯一	严格有序	低（单点写）	性能瓶颈
UUID v4	极低冲突概率	无序	极高	无序，存储不友好
Snowflake	全局唯一	时间有序	极高（本地）	依赖时钟，有回拨问题
号段模式	全局唯一	有序	高（批量申请）	重启时 ID 不连续

雪花算法（Snowflake）

64 位结构：

为什么这样划分位数？

• 41 bit 时间戳：2⁴¹ 毫秒 ≈ 69 年，足够大多数业务生命周期
• 10 bit 机器 ID：1024 台机器，可以拆分为 5 bit 数据中心 + 5 bit 机器
• 12 bit 序列号：同一毫秒内 4096 个 ID，单机 400 万/秒，远超大多数业务需求

Java 实现（含时钟回拨处理）：

public class Snowflake {
    private static final long EPOCH = 1420070400000L;  // 自定义起始时间（2015-01-01）
    private static final int NODE_BITS = 10;
    private static final int SEQ_BITS = 12;
    private static final long MAX_NODE = (1L << NODE_BITS) - 1;    // 1023
    private static final long MAX_SEQ  = (1L << SEQ_BITS) - 1;     // 4095

    private final long nodeId;
    private long lastTimestamp = -1L;
    private long sequence = 0L;

    public Snowflake(long nodeId) {
        if (nodeId < 0 || nodeId > MAX_NODE)
            throw new IllegalArgumentException("nodeId must be in [0, " + MAX_NODE + "]");
        this.nodeId = nodeId;
    }

    public synchronized long nextId() {
        long now = currentMs();

        // 时钟回拨处理：等待时钟追上
        if (now < lastTimestamp) {
            long offset = lastTimestamp - now;
            if (offset <= 5) {
                // 回拨不超过 5ms，等待追上
                try { Thread.sleep(offset); } catch (InterruptedException e) { Thread.currentThread().interrupt(); }
                now = currentMs();
            }
            if (now < lastTimestamp) {
                throw new RuntimeException("Clock moved backwards. Refusing to generate id.");
            }
        }

        if (now == lastTimestamp) {
            sequence = (sequence + 1) & MAX_SEQ;
            if (sequence == 0) {
                now = waitNextMs(now);  // 序列号耗尽，等到下一毫秒
            }
        } else {
            sequence = 0;
        }
        lastTimestamp = now;

        return ((now - EPOCH) << (NODE_BITS + SEQ_BITS))
             | (nodeId << SEQ_BITS)
             | sequence;
    }

    private long currentMs() { return System.currentTimeMillis(); }

    private long waitNextMs(long current) {
        long ts = currentMs();
        while (ts <= current) ts = currentMs();
        return ts;
    }
}

时钟回拨的根本原因：NTP 时间同步可能导致系统时间向前调整。

处理策略：

回拨幅度	处理方式	原因
< 5ms	自旋等待时钟追上	短暂等待代价低，不影响可用性
> 5ms	抛异常，由调用方决策	长时间等待影响服务，应告警处理
美团 Leaf 方案	引入 ZK 记录时间戳，容忍一定回拨	更高可用性，适合大规模集群

推荐算法基础（补充）

协同过滤

基于用户的协同过滤：找到与目标用户行为相似的用户，推荐他们喜欢但目标用户未看过的内容。

相似度计算：

// 余弦相似度：cos(θ) = A·B / (|A| × |B|)
// 衡量两个向量的方向相似度，不受向量长度影响（适合用户评分数量不同的场景）
public double cosineSimilarity(Map<String, Double> userA, Map<String, Double> userB) {
    double dotProduct = 0, normA = 0, normB = 0;
    for (String key : userA.keySet()) {
        if (userB.containsKey(key)) {
            dotProduct += userA.get(key) * userB.get(key);
        }
        normA += userA.get(key) * userA.get(key);
    }
    for (double v : userB.values()) normB += v * v;
    return normA == 0 || normB == 0 ? 0 : dotProduct / (Math.sqrt(normA) * Math.sqrt(normB));
}

// Jaccard 相似度（适合集合）：|A∩B| / |A∪B|
// 衡量两个集合的重叠程度，适合"是否购买/是否点赞"这类二值数据
public double jaccardSimilarity(Set<String> setA, Set<String> setB) {
    Set<String> intersection = new HashSet<>(setA);
    intersection.retainAll(setB);
    Set<String> union = new HashSet<>(setA);
    union.addAll(setB);
    return union.isEmpty() ? 0 : (double) intersection.size() / union.size();
}

搜索排序（TF-IDF）

TF-IDF：衡量词语对文档的重要程度。

TF(t, d)   = 词 t 在文档 d 中出现的次数 / 文档 d 的总词数
IDF(t, D)  = log(文档总数 / 包含词 t 的文档数 + 1)
TF-IDF(t, d, D) = TF(t, d) × IDF(t, D)

直觉：TF 衡量词在文档中的频率（词越常见越重要），IDF 衡量词在整个语料库中的稀缺性（越稀有越有区分度）。"的"、"是"这类词 TF 高但 IDF 极低，最终权重接近 0。

BM25（TF-IDF 的改进版，Elasticsearch 默认使用）：

BM25(t, d) = IDF(t) × (TF(t,d) × (k₁+1)) / (TF(t,d) + k₁ × (1-b+b×|d|/avgdl))

其中：k₁ ≈ 1.2~2.0（词频饱和参数），b ≈ 0.75（文档长度归一化参数）

BM25 的改进：对高频词的贡献做了"饱和"处理，避免某个词出现 100 次比出现 10 次的文档得分高 10 倍。同时通过文档长度归一化，避免长文档因词频绝对值高而获得不公平的优势。

算法选型速查

业务需求	推荐算法	原因
API 限流（允许突发）	令牌桶	桶内积累的令牌可应对短时突发
API 限流（严格平滑）	漏桶	定速消费，彻底平滑流量
分布式缓存路由	一致性哈希	节点变化时只影响少量 key
实时排行榜	Redis ZSet	O(logn) 插入，支持范围查询
海量数据去重	布隆过滤器	极少内存，接受 5% 误判
大规模 UV 统计	HyperLogLog	12KB 固定内存，0.81% 误差
缓存淘汰（通用）	LRU	实现简单，命中率高
缓存淘汰（热点稳定）	LFU	频次低的冷数据更快被淘汰
分布式唯一 ID	Snowflake	本地生成，时间有序，高性能

参考资料

• 极客时间《业务开发算法 50 讲》— 微扰君
• Redis 官方文档 — LRU/LFU 缓存策略
• Twitter Snowflake 开源实现
• Google Guava BloomFilter 源码