缓存算法
#算法
2024-02-04
内存是有限的，不可能无限制地添加数据。假定我们设置缓存能够使用的内存大小为 N，那么在某一个时间点，添加了某一条缓存记录之后，占用内存超过了 N，这个时候就需要从缓存中移除一条或多条数据了。
常用缓存算法
- 最不经常使用算法（Least Frequently Used,
LFU）：首先移除最低访问数的条目。
- 关键：使用一个计数器来记录条目被访问的频率。
- 缺点：不常用。若某个条目在历史上访问次数奇高，且在某个时间点之后长时间几乎不再被访问，则该条目迟迟不能被淘汰。
- 最近最少使用算法（Least Recently Used. LRU）：将最近使用的条目存放到靠近缓存顶部的位置。当一个新条目被访问时，LRU 将它放置到缓存的顶部。当缓存达到极限时，较早之前访问的条目将从缓存底部开始被移除。这里会使用到昂贵的算法，而且它需要记录“年龄位”来精确显示条目是何时被访问的。此外，当一个LRU缓存算法删除某个条目后，“年龄位”将随其他条目发生改变。
- 自适应缓存替换算法（ARC）：在 IBM Almaden 研究中心开发，这个缓存算法同时跟踪记录 LFU 和 LRU，以及驱逐缓存条目，来获得可用缓存的最佳使用。
- 最近最常使用算法（Most Recently Used,
MRU）：首先移除最近最常使用的条目。
- 优点：擅长处理一个条目越久，越容易被访问的情况。
- 先进先出算法（First In First Out, FIFO）：先进入缓存的先移除。
- 关键：栈式结构。
- 优点：实现简单。
- 缺点：只能顺序写入和移除，无法指定特定的地址。
