摘要缓存是提升系统性能的第一道防线也是面试中系统设计环节的核心话题。本文系统讲解缓存的四大置换策略、LRU 和 LFU 的实现原理并结合 Python 代码展示完整的缓存系统。AI 开发者还将学到 KV Cache 在 LLM 推理中的关键作用。一、为什么需要缓存1.1 缓存的时空权衡是否请求缓存命中?直接返回~1ms查数据库~100ms写入缓存图 1缓存读取流程1.2 缓存的三大问题问题描述解决方案缓存穿透查询不存在的数据绕过缓存直达 DB布隆过滤器、空值缓存缓存击穿热点 key 过期大量请求涌入 DB互斥锁、逻辑过期缓存雪崩大量 key 同时过期随机过期时间、多级缓存二、缓存置换策略2.1 四大经典策略 缓存策略对比 fromtypingimportDict,OptionalfromcollectionsimportOrderedDictimportrandomclassCacheStrategy:缓存策略基类def__init__(self,capacity:int):self.capacitycapacity self.cache{}defget(self,key):raiseNotImplementedErrordefput(self,key,value):raiseNotImplementedErrorclassLRUCacheImpl(CacheStrategy): LRU (Least Recently Used) 缓存 使用 OrderedDict 实现 O(1) 操作 def__init__(self,capacity:int):super().__init__(capacity)self.cacheOrderedDict()defget(self,key):ifkeynotinself.cache:return-1# 移动到末尾最近使用self.cache.move_to_end(key)returnself.cache[key]defput(self,key,value):ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]valueiflen(self.cache)self.capacity:# 移除最旧的self.cache.popitem(lastFalse)classLFUCacheImpl(CacheStrategy): LFU (Least Frequently Used) 缓存 记录每个 key 的访问频率淘汰使用最少的 def__init__(self,capacity:int):super().__init__(capacity)self.key_to_val{}self.key_to_freq{}self.freq_to_keys{}# 频率 - key 集合self.min_freq0defget(self,key):ifkeynotinself.key_to_val:return-1self._increase_freq(key)returnself.key_to_val[key]defput(self,key,value):ifself.capacity0:returnifkeyinself.key_to_val:self.key_to_val[key]value self._increase_freq(key)returniflen(self.key_to_val)self.capacity:self._evict()self.key_to_val[key]value self.key_to_freq[key]1self.freq_to_keys.setdefault(1,set()).add(key)self.min_freq1def_increase_freq(self,key):freqself.key_to_freq[key]self.key_to_freq[key]freq1self.freq_to_keys[freq].remove(key)ifnotself.freq_to_keys[freq]:delself.freq_to_keys[freq]iffreqself.min_freq:self.min_freq1self.freq_to_keys.setdefault(freq1,set()).add(key)def_evict(self):keysself.freq_to_keys[self.min_freq]key_to_removenext(iter(keys))keys.remove(key_to_remove)ifnotkeys:delself.freq_to_keys[self.min_freq]delself.key_to_val[key_to_remove]delself.key_to_freq[key_to_remove]deftest_caches():print(*60)print(缓存策略测试)print(*60)print(\n【LRU 测试】)lruLRUCacheImpl(2)lru.put(1,10)lru.put(2,20)lru.get(1)lru.put(3,30)# 淘汰 key 2print(f get(1){lru.get(1)}, get(2){lru.get(2)}, get(3){lru.get(3)})print(\n【LFU 测试】)lfuLFUCacheImpl(2)lfu.put(1,10)lfu.put(2,20)lfu.get(1)lfu.get(1)lfu.put(3,30)# 淘汰 key 2使用频率低print(f get(1){lfu.get(1)}, get(2){lfu.get(2)}, get(3){lfu.get(3)})print(\n*60)if__name____main__:test_caches()代码 1LRU 与 LFU 实现三、AI 场景LLM 的 KV Cache3.1 KV Cache 原理在 Transformer 解码过程中每个 token 的注意力计算需要用到之前所有 token 的 Key 和 Value。为了避免重复计算将它们缓存起来输入 Token注意力计算KV Cache输出更新 KV Cache图 2KV Cache 在 Transformer 推理中的作用3.2 KV Cache 管理挑战挑战解决方案内存随序列长度线性增长PagedAttention 分页管理不同请求序列长度不一Continuous Batching长上下文内存爆炸滑动窗口注意力、H2O 重计算四、总结核心要点缓存是性能优化的第一手段用空间换时间LRU 适合时间局部性好的场景大多数 Web 应用LFU 适合频率差异明显的场景热点内容分发AI 推理中 KV Cache 是核心优化点直接决定可服务的并发量。本文基于 Coding Interview University 项目整理专注缓存设计专题。
