缓存

副标题 / 摘要 这题不是“背答案题”，而是缓存系统的基本功：如何在常数时间内同时满足“快速访问”和“按最近最少使用淘汰”。本文从朴素方案推到最优结构，并给出可运行的多语言实现。 预计阅读时长：14~18 分钟 标签：LRU、哈希表、双向链表、系统设计 SEO 关键词：LRU Cache, LeetCode 146, 哈希表, 双向链表, O(1) 元描述：通过哈希表 + 双向链表实现 LRU 缓存，get/put 平均 O(1)，附工程场景、常见坑与六语言实现。 目标读者 正在刷 LeetCode 中等题、想吃透“数据结构组合技”的同学 做后端/中间件，需要实现或优化本地缓存的工程师 面试中经常被问到 LRU，但只记住结论、没掌握细节的人 背景 / 动机 缓存是“空间换时间”，但空间是有限的。 当缓存满了，必须淘汰一些键。LRU（Least Recently Used，最近最少使用）假设： 最近被访问的数据，将来更可能再次访问 很久没访问的数据，优先淘汰更合理 工程里常见于： 接口响应缓存 数据库热点记录缓存 页面/会话本地状态缓存 核心概念 LRU 策略：淘汰“最久未使用”的键 访问即更新新鲜度：get 成功后要把该 key 标为“最近使用” 容量约束：put 新 key 造成超容时，需要立即驱逐一个最旧键 O(1) 平均复杂度：get 和 put 都不能线性扫描 A — Algorithm（题目与算法） 题目重述 设计并实现一个满足 LRU 约束的数据结构 LRUCache： LRUCache(int capacity)：用正整数容量初始化 int get(int key)：若 key 存在返回 value，否则返回 -1 void put(int key, int value)： key 已存在：更新 value，并视作最近使用 key 不存在：插入新键值对 若超出容量：淘汰最久未使用的 key 并要求 get 和 put 平均时间复杂度为 O(1)。 ...

副标题 / 摘要 缓存不是万能的，有时甚至危险。本文解释缓存带来的风险场景，并给出规避策略。 目标读者 负责架构选型的工程师 需要平衡一致性与性能的团队 经常做缓存优化的开发者 背景 / 动机 “加缓存”几乎是所有性能问题的第一反应，但在强一致性场景中，缓存可能带来严重业务风险。 理解何时不该缓存，和如何安全缓存一样重要。 核心概念 一致性风险：缓存与源数据不一致 失效策略：主动失效 / TTL / 事件驱动 读写比例：决定缓存收益 错误放大：错误缓存比错误计算更危险 实践指南 / 步骤 判断一致性要求（金融、库存、权限等） 识别可容忍的延迟 选择失效策略（TTL/主动清理） 对关键字段禁用缓存 建立缓存监控与熔断 可运行示例 cache = {} def get_price(product_id): if product_id in cache: return cache[product_id] price = 100 # 假设从数据库读取 cache[product_id] = price return price 解释与原理 缓存只在“读多写少、可容忍延迟”的场景下安全。 如果业务对一致性敏感，缓存会放大错误并导致不可控后果。 常见问题与注意事项 缓存一定提升性能吗？ 不一定，缓存失效或穿透时成本更高。 TTL 足够吗？ 不一定，某些场景需要事件驱动失效。 缓存和幂等有什么关系？ 幂等能降低缓存错误带来的二次风险。 最佳实践与建议 对“强一致性”业务谨慎缓存 缓存前先定义失效策略 监控命中率与错误率 小结 / 结论 缓存是性能工具，不是默认选项。 在强一致性与高风险业务中，缓存反而可能危险。 参考与延伸阅读 Cache Invalidation 技术讨论 Redis 缓存最佳实践 分布式一致性案例 元信息 阅读时长：7~9 分钟 标签：缓存、架构、一致性 SEO 关键词：缓存, Cache Invalidation, 一致性 元描述：说明缓存何时危险并给出规避策略。 行动号召（CTA） 列出你系统中最不能容忍错误的字段，明确哪些绝对不能缓存。

副标题 / 摘要 缓存大小不是拍脑袋，而是命中率、成本与稳定性之间的平衡。本文给出确定缓存大小的工程方法。 目标读者 负责缓存系统和性能优化的工程师 做容量规划与成本控制的团队 需要提升命中率与稳定性的开发者 背景 / 动机 缓存太小会导致频繁穿透，太大则成本高且失效风险增加。 正确做法是用数据驱动的方式确定缓存大小。 核心概念 命中率（Hit Rate）：缓存命中 / 总请求 工作集（Working Set）：短期内频繁访问的数据集合 淘汰策略：LRU/LFU 等 成本曲线：边际命中率收益逐渐降低 实践指南 / 步骤 采集访问分布（热度、访问频率） 估算工作集大小 用不同容量做离线回放 评估命中率与成本曲线 预留安全余量（波峰期、突发流量） 可运行示例 下面模拟不同缓存容量的命中率： from collections import OrderedDict def lru_hit_rate(requests, capacity): cache = OrderedDict() hits = 0 for key in requests: if key in cache: hits += 1 cache.move_to_end(key) else: if len(cache) >= capacity: cache.popitem(last=False) cache[key] = True return hits / len(requests) if __name__ == "__main__": reqs = [1,2,3,1,2,4,1,2,3,5,1,2,3,4] for cap in [1, 2, 3, 4]: print(cap, lru_hit_rate(reqs, cap)) 解释与原理 缓存大小的收益是递减的：容量越大，新增命中率提升越小。 因此需要找到“边际收益开始下降”的拐点，而不是盲目扩容。 ...