缓存放满了，先清掉什么？

常见的规则有两条：

• 最久没用的先清出去：按每道菜上一次被用到的先后排队，命中一次就排到队尾；要腾地方时，清掉排在最前、最久没被用到的那一道。它叫最久未用优先淘汰（LRU）。
• 先放进来的先清出去：按放进来的先后排队，命中时不调整；要腾地方时，清掉最早放进来的那一道，不管它后来被用过多少次。它叫先进先出（FIFO）。

下图的缓存放得下 4 道菜，读者一道一道点开菜谱。

在上图里，用两条规则各走一遍「番茄炒蛋常回头」：番茄炒蛋隔一道就被点开一次。按最久没用的先清出去，它总是刚用过，一直留在缓存里；按先放进来的先清出去，第 7 下点开葱油拌面时，番茄炒蛋因为放得最早被清了出去，虽然第 6 下刚用过它，第 8 下再点开，只好再查一遍。再换成「回头再看前几道」：看完四道、回头看一眼番茄炒蛋、点开葱油拌面以后，读者又依次回头看罗宋汤、红烧茄子和番茄炒蛋。这一回结果反过来：最久没用的先清出去，恰好把接下来要看的那两道清了出去，一连两下没命中。

所以两条规则谁好，要看读者怎样访问。Twitter 用真实的访问记录模拟过：缓存不太小时，两条规则的命中率常常差不多（2020）。真实的缓存软件放满以后怎样处理，默认做法也各不相同。