系统与基础设施danluu.com
缓存淘汰：随机算法何时优于 LRU？（2014）
Cache Eviction: When Are Randomized Algorithms Better Than LRU? (2014)
2014 — 2025，它一次次回到首页
黑点是上首页（≥ 50 分）的那次投稿，空心点是没冲上去的投稿，点越大分数越高。
导读
Dan Luu 的经典文章，探讨缓存淘汰策略：在什么情况下随机化算法（如 2-random）比 LRU 表现更好。文章分析了 LRU 在扫描式访问等模式下的失效场景，说明简单的随机策略反而能优雅降级。
为什么经久不衰：它用扎实的分析颠覆了“LRU 总是更好”的直觉，且结论在系统设计和日常优化中反复适用，因此多年反复登上 HN 首页。
HN 评论精选
随机策略的优势在于不依赖“局部性”假设、能抵御最坏情况
当访问模式是随机的——最近用过的项并不比其他项更可能被再次访问——随机算法就更好；甚至当访问模式“反近期”（刚访问的项更不可能再被访问）时更是如此。所有替换策略都是在模拟一个能预知未来的“魔法预言机”。随机化算法的价值在于防御最坏情况，避免触发算法的病态场景。
kazinator查看英文原文
> When Are Randomized Algorithms Better Than LRU? When the access pattern is random: recently used items are not more likely to be accessed than other items. Or worse: the access pattern is "anti-recent": items recently accessed are less likely to be accessed again than other items. This is undergraduate stuff I once had to know for exams in machine architectures and operating systems. The choice of LRU replacement is favorable when there exists "locality of reference"; that's what it's predicated upon. All of the replacement policy choices are only substitutes for a "magic oracle": a replacement strategy which can peer into the future and know which items will be accessed soonest. With a magic oracle, we can not only retain those items in the cache in preference to other items, to great advantage, but we can automatically prefetch the correct items that are not yet in the cache but are about to be accessed. In general, randomized algorithms provide a defense against situations in which things don't work out according to the best case assumptions. For instance, they help defend against tickling worst cases in algorithms (e.g. sorting) that have good average-case behavior.
LRU 在工作集略超缓存时性能断崖式下跌，随机策略则平滑退化
对于小缓存微控制器上的控制循环优化，这是关键经验：只要循环体放得进缓存，LRU 就很完美；一旦放不下，每次都会 miss，代码速度骤降到百分之一。而随机淘汰策略会随着循环变大而优雅地退化。
okl查看英文原文
> If you have a tight loop, LRU is going to be perfect as long as the loop fits in cache, but it's going to cause a miss every time if the loop doesn't fit. A random eviction policy degrades gracefully as the loop gets too big. That's the key take-away from my experience with optimizing control loops for microcontrollers with small caches. As soon as your loop is too bit, your code suddenly runs at a hundredth of the speed.
补充解释了 2-random 与 LRU 的具体机制差异
希望作者能更好地解释 2-random 和 LRU 的区别。简言之：LRU 记录每个缓存项最后访问时间，总是淘汰最旧的；2-random 也记录各项的年龄，但淘汰时随机挑两项、删掉其中较旧的那个。
vesinisa查看英文原文
Interesting read, but I wish he'd explain how 2-random and LRU differ better. In a nutshell, LRU tracks the time when a cache item was last accessed and always discards the oldest item. 2-random also tracks the age of all cache items, but when discarding picks two random items and discards the oldest of those two.
加权 LRU 能抵御一次性扫描流量冲掉热点数据
对不可预测的负载，加权 LRU 通常略好：当出现大量一次性访问的流量洪峰时，它不会把高频使用的缓存数据淘汰掉。做法大致是每次使用加二权重、每秒对所有项衰减一，压力下从权重最低的开始淘汰。这对数据库把热点行留在内存尤其相关。
falcolas查看英文原文
One thing I've seen is that a weighted LRU is usually slightly better for unpredictable workloads. i.e. it will never evict high use cache data when there's a flurry of one-off traffic that would normally start evicting a normal LRU cache, and even a 2 random LRU scheme. This is particularly relevant for databases and keeping rows in memory. The algorithm is something like "add two weight when an item is used, and decay one from every item every second, evict items under pressure from the lowest weight to the highest."
历次讨论
同类还值得读
TTY 揭秘（2008）
The TTY demystified (2008)
经典文章深入剖析了 Unix/Linux 中 TTY 子系统的工作原理，包括线路规程、终端驱动、信号与控制字符等机制。
系统与基础设施上首页 11 次 · 2009–2025linusakesson.net编辑精选为什么 GNU grep 这么快
Why GNU grep is Fast
FreeBSD 邮件列表上一篇广为流传的帖子，解释 GNU grep 为什么快：核心在于 Boyer-Moore 字符串搜索算法配合精心优化的内部循环和 I/O，让程序在搜索时“…
系统与基础设施上首页 9 次 · 2010–2022lists.freebsd.orgXplain：为普通人讲解 X11
Xplain – Explaining X11 for the rest of us
《Xplain》是作者（HN 用户 Jasper_）写的一系列 X11 长文，用他在浏览器中重建的 X11 绘图模型做交互演示，讲解 X11 的绘图模型与窗口系统设计。
系统与基础设施上首页 6 次 · 2013–2020magcius.github.io编辑精选旋风教程：为 Linux 创建极小 ELF 可执行文件（1999）
A Whirlwind Tutorial on Creating Really Teensy ELF Executables for Linux (1999)
breadbox 写于 1999 年的经典教程，主题是如何为 Linux 手工构造并裁剪出体积极小的 ELF 可执行文件。
系统与基础设施上首页 6 次 · 2007–2025muppetlabs.comPostgreSQL 内部原理
The internals of PostgreSQL
《The Internals of PostgreSQL》是一本免费在线书籍，系统讲解 PostgreSQL 的内部实现，包括查询处理、并发控制、WAL、缓冲区管理等核心机制。
系统与基础设施上首页 5 次 · 2017–2025interdb.jp编辑精选