本文总结：

1. 回收内存机制有哪些？主要包括包括两个：

• 清理达到过期时间时间的键
• maxmemory设置的内存上限，触发回收策略。

1 淘汰策略

回收内存机制主要包括包括两个：

• 清理达到过期时间时间的键
• maxmemory设置的内存上限，触发回收策略

1.1 清理过期时间的键

主要包括惰性删除和定期两种方式：

惰性删除：每次从键空间中获取键时，都检查取得的键是否过期，如果过期的话，就删除该键；如果没有过期，就返回该键。

定期删除：每隔一段时间（每秒运行10次），程序就对数据库进行一次检查，删除里面的过期键。

1.2 达到内存上限触发回收

内存使用达到maxmemory设置的内存上限时，触发内存溢出策略（maxmemory-policy参数）。默认策略是volatile-lru：

• noeviction:不删除任何键，只响应读操作，拒绝写入操作。如果有写入操作返回错误”OOM command not allowed when used memory”。
• allkeys-lru: 根据LRU算法删除键，不管数据有没有设置超时属性，直到腾出足够空间为止。
• allkeys-lfu: 根据LFU算法删除键，不管数据有没有设置超时属性，直到腾出足够空间为止。
• allkeys-random: 随机删除键，不管数据有没有设置超时属性，直到腾出足够空间为止。
• volatile-lru: 根据LRU算法删除设置了过期时间（expire）的键，直到腾出足够空间为止。
• volatile-random: 随机删除设置了过期时间（expire）的键，直到腾出足够空间为止。
• volatile-lfu: 根据LFU算法删除设置了过期时间（expire）的键，直到腾出足够空间为止。
• volatile-ttl: 删除最近将要过期数据，直到腾出足够空间为止。TTL, time to live，剩余存活时间。通过 “TTL key  xx”进行设置。

说明：

• volatile-xx策略，是针对设置过期时间的键。只会删除设置了过期时间的键，对于没有设置过期时间的键会一致保存。
• LRU和LFU。LRU（Least Recently Used）最近最少使用，是按照使用时间排序的，过滤很久之前访问的数据；LFU（Least Frequently Used）最近最不常用，是按照访问次数进行过滤的，顾虑频率最低的数据。

2.3 LRU改进

算法元素：

• Redis 默认会记录每个数据的最近一次访问的时间戳（RedisObject 中的 lru 字段）
• maxmemory_samples: 随机采样的精度，也就是随即取出key的数目。该数值配置越大, 越接近于真实的LRU算法，但是数值越大，相应消耗也变高，对性能有一定影响，样本值默认为5；这个配置为10时已经非常接近全量LRU的精准度了。

策略：

• 初始化：Redis 在决定淘汰的数据时，第一次会随机选出 N 个数据（ maxmemory-samples），把它们作为一个候选集合。
• 新增样本：将lru较大从lru池中剔除。
• 淘汰策略：把lru池中 lru 最小的数据从缓存中淘汰出去。

2 基于LinkedHashMap实现LRU

2.1 LinkedHashMap结构

LinkedHashMap是HashMap的子类，但是内部还有一个双向链表维护键值对的顺序，每个键值对既位于哈希表中，也位于双向链表中。LinkedHashMap支持插入和访问两种顺序。

• 插入顺序：先添加的在前面，后添加的在后面。修改操作不影响顺序
• 访问顺序：所谓访问指的是get/put操作，对一个键执行get/put操作后，其对应的键值对会移动到链表末尾，所以最末尾的是最近访问的，最开始的是最久没有被访问的，这就是访问顺序。

默认都采用插入顺序来维持取出键值对的次序，如果使用如下构造方法将accessOrder设置为true。

和Hashmap结构区别：LinkedHashMap 相比 HashMap 的拉链式存储结构，内部额外通过 Entry 维护了一个双向链表，Entry多了一个before和after指针。

2.2 实现LRU

源码中add操作会用到removeEldestEntry，

默认removeEldestEntry直接返回false，只需要复写removeEldestEntry方法即可。