缓存算法主要从以下方面考虑
- 成本,如果缓存对象有不同的成本,应该把那些难以获得的对象缓存起来
- 容量,如果缓存对象有不同的大小,应该把那些大的缓存对象清除,这样可以缓存更多的数据对象
- 时间,缓存对象可以持有一个过期时间,方便系统判定缓存对象是否可用
Least Frequently Used（LFU）
为每个缓存对象计算它们被使用的频率,把使用频率最低的数据换出
Least Recently User (LRU)
换出最近最少使用的缓存对象
将最近被访问的缓存对象放置在缓存池的顶部,每次直接淘汰缓存池底部的缓存数据
Least Recently Used 2（LRU2）
相对于LRU,解决了批量访问非热点数据对热点数据缓存的影响
把被两次访问过的对象放入缓存池，当缓存池满了之后,换出最少使用的缓存对象.因为需要跟踪所有访问对象,并统计访问次数,访问负载会随访问数据量线性增长,在大容量数据下会有容量问题
Two Queues（2Q）
将访问数据放到LRU中,如果这个对象再次被访问,将被转移至另一个更大的LRU缓存中.
Adaptive Replacement Cache（ARC）
由两个LRU L1 L2组成,L1包含最近仅被使用过一次的数据,L2包含最近被使用过两次的数据.
Most Recently Used（MRU）
换出最近最多被使用的数据
缓存系统中找出最近最少使用数据对象是时间复杂度非常高的运算,该算法的目的是减少换出数据的时间复杂度
每次缓存数据被使用,会将被使用的数据放到栈的顶端,栈满后,将栈顶元素替换为新的数据对象
First in First out（FIFO）
直接通过队列维护缓存对象,先进先出
Second Chance
与FIFO的立即换出数据不同,该算法会检查准备换出数据的访问标志位,没有使用过会被立即换出,否则清除该标记位然后将该缓存对象当做新的缓存数据加入队列,形成类似环队列的数据访问形式,
CLock
使用环形列表存储缓存对象,不需要像second chance对有标记的缓存对象进行移位操作
持有一个装有缓存对象的环形列表,头指针指向列表中最老的缓存对象.当缓存mess发生并没有新的缓存空间时,如果标志是0,直接用新的缓存对象替代这个缓存对象;如果标志位为1,将当前标记位清空为0,并将指针递增后,重复该过程,直到新的缓存对象被放入.
Simple time-based
通过绝对的时间周期去失效缓存对象,新增的对象会被保存特定的时间周期,统一的失效时间会导致所有缓存会在同一时间失效,可能导致大量数据请求的激增
Extended time-based expiration
通过相对时间去失效缓存对象,对新增的缓存对象,会保存特定的时间
Sliding time-based expiration
通过最后访问时间更新缓存对象的生命周期