LRU算法
- 最近最少使用算法，一般使用一个链表，最新访问的数据会移动至首部，当链表到达容量时淘汰尾部的节点
LRU-K
- 相对于LRU，多了一个记录访问次数的链表，这个链表里记录的是每个key对应的访问次数，当访问次数达到k时，才会到达LRU链表中
- 这个设计保证了偶然的数据访问造成命中率降低，如果某个数据到达尾部即将被淘汰，此时有一个请求，使之到达首部，但是后续可能再没有访问
- 实施流程
- 当有访问来时，左边链表会记录每个key被访问的次数，并且按照FIFO淘汰
- 当某个值访问次数达到了K，会将该key移动到右边的LRU队列
- 当右边的某个key被访问后，移动至队列首部
- 当队列满后，淘汰对尾的key
LFU
- 最近最长使用，使用的频率越高，越排在队列前面，当队列满了之后淘汰对尾元素
- 步骤
- 新数据进入队列，引用计数为1，重新排列队列
- 如果相同的引用计数，则按照时间排序
- 整体按照引用计数排序