Redis的LRU缓存淘汰算法实现

LRU， 最近最少使用 （Least Recently Used，LRU），经典缓存算法。

LRU会使用一个链表维护缓存中每个数据的访问情况，并根据数据的实时访问，调整数据在链表中的位置，然后通过数据在链表中的位置，表示数据是最近刚访问的，还是已有段时间未访问。

LRU会把链头、尾分别设为MRU端和LRU端：

LRU可分成如下情况：

case2图解：链表长度为5，从链表头部到尾部保存的数据分别是5，33，9，10，8。假设数据9被访问一次，则9就会被移动到链表头部，同时，数据5和33都要向链表尾部移动一位。

所以若严格按LRU实现，假设Redis保存的数据较多，还要在代码中实现：

最终导致降低Redis访问性能。

所以，无论是为节省内存 or 保持Redis高性能，Redis并未严格按LRU基本原理实现，而是 提供了一个近似LRU算法实现 。

Redis的内存淘汰机制是如何启用近似LRU算法的？redisconf中的如下配置参数：

所以，一旦设定maxmemory选项，且将maxmemory-policy配为allkeys-lru或volatile-lru，近似LRU就被启用。allkeys-lru和volatile-lru都会使用近似LRU淘汰数据，区别在于：

Redis如何实现近似LRU算法的呢？

近似LRU算法仍需区分不同数据的访问时效性，即Redis需知道数据的最近一次访问时间。因此，有了LRU时钟：记录数据每次访问的时间戳。

Redis对每个KV对中的V，会使用个redisObject结构体保存指向V的指针。那redisObject除记录值的指针，还会使用24 bits保存LRU时钟信息，对应的是lru成员变量。这样，每个KV对都会把它最近一次被访问的时间戳，记录在lru变量。

redisObject定义包含lru成员变量的定义：

每个KV对的LRU时钟值是如何计算的？Redis Server使用一个实例级别的全局LRU时钟，每个KV对的LRU time会根据全局LRU时钟进行设置。

这全局LRU时钟保存在Redis全局变量server的成员变量 lruclock

当Redis Server启动后，调用initServerConfig初始化各项参数时，会调用getLRUClock设置lruclock的值：

于是，就得注意， 若一个数据前后两次访问的时间间隔 1s，那这两次访问的时间戳就是一样的！ 因为LRU时钟精度就是1s，它无法区分间隔小于1秒的不同时间戳！

getLRUClock函数将获得的UNIX时间戳，除以LRU_CLOCK_RESOLUTION后，就得到了以LRU时钟精度来计算的UNIX时间戳，也就是当前的LRU时钟值。

getLRUClock会把LRU时钟值和宏定义LRU_CLOCK_MAX（LRU时钟能表示的最大值）做与运算。

所以默认情况下，全局LRU时钟值是以1s为精度计算得UNIX时间戳，且是在initServerConfig中进行的初始化。

那Redis Server运行过程中，全局LRU时钟值是如何更新的？和Redis Server在事件驱动框架中，定期运行的时间事件所对应的serverCron有关。

serverCron作为时间事件的回调函数，本身会周期性执行，其频率值由redisconf的 hz配置项 决定，默认值10，即serverCron函数会每100ms（1s/10 = 100ms）运行一次。serverCron中，全局LRU时钟值就会按该函数执行频率，定期调用getLRUClock进行更新：

这样，每个KV对就能从全局LRU时钟获取最新访问时间戳。

对于每个KV对，它对应的redisObjectlru在哪些函数进行初始化和更新的呢？

对于一个KV对，其LRU时钟值最初是在这KV对被创建时，进行初始化设置的，这初始化 *** 作在 createObject函数 中调用，当Redis要创建一个KV对，就会调用该函数。

createObject除了会给redisObject分配内存空间，还会根据maxmemory_policy配置，初始化设置redisObjectlru。

LRU_CLOCK返回当前全局LRU时钟值。因为一个KV对一旦被创建，就相当于有了次访问，其对应LRU时钟值就表示了它的访问时间戳：

那一个KV对的LRU时钟值又是何时再被更新？

只要一个KV对被访问，其LRU时钟值就会被更新！而当一个KV对被访问时，访问 *** 作最终都会调用 lookupKey 。

lookupKey会从全局哈希表中查找要访问的KV对。若该KV对存在，则lookupKey会根据maxmemory_policy的配置值，来更新键值对的LRU时钟值，也就是它的访问时间戳。

而当maxmemory_policy没有配置为LFU策略时，lookupKey函数就会调用LRU_CLOCK函数，来获取当前的全局LRU时钟值，并将其赋值给键值对的redisObject结构体中的lru变量

这样，每个KV对一旦被访问，就能获得最新的访问时间戳。但你可能好奇：这些访问时间戳最终是如何被用于近似LRU算法进行数据淘汰的？

Redis之所以实现近似LRU，是为减少内存资源和 *** 作时间上的开销。

近似LRU主要逻辑在performEvictions。

performEvictions被evictionTimeProc调用，而evictionTimeProc函数又是被processCommand调用。

processCommand，Redis处理每个命令时都会调用：

然后，isSafeToPerformEvictions还会再次根据如下条件判断是否继续执行performEvictions：

一旦performEvictions被调用，且maxmemory-policy被设置为allkeys-lru或volatile-lru，近似LRU就被触发执行了。

执行可分成如下步骤：

调用getMaxmemoryState评估当前内存使用情况，判断当前Redis Server使用内存容量是否超过maxmemory配置值。

若未超过maxmemory ，则返回C_OK，performEvictions也会直接返回。

getMaxmemoryState评估当前内存使用情况的时候，若发现已用内存超出maxmemory，会计算需释放的内存量。这个释放内存大小=已使用内存量-maxmemory。

但已使用内存量并不包括用于主从复制的复制缓冲区大小，这是getMaxmemoryState通过调用freeMemoryGetNotCountedMemory计算的。

而若当前Server使用的内存量超出maxmemory上限 ，则performEvictions会执行while循环淘汰数据释放内存。

为淘汰数据，Redis定义数组EvictionPoolLRU，保存待淘汰的候选KV对，元素类型是evictionPoolEntry结构体，保存了待淘汰KV对的空闲时间idle、对应K等信息：

这样，Redis Server在执行initSever进行初始化时，会调用evictionPoolAlloc为EvictionPoolLRU数组分配内存空间，该数组大小由EVPOOL_SIZE决定，默认可保存16个待淘汰的候选KV对。

performEvictions在淘汰数据的循环流程中，就会更新这个待淘汰的候选KV对集合，即EvictionPoolLRU数组。

performEvictions调用evictionPoolPopulate，其会先调用dictGetSomeKeys，从待采样哈希表随机获取一定数量K：

于是，dictGetSomeKeys返回采样的KV对集合。evictionPoolPopulate根据实际采样到的KV对数量count，执行循环：调用estimateObjectIdleTime计算在采样集合中的每一个KV对的空闲时间：

接着，evictionPoolPopulate遍历待淘汰的候选KV对集合，即EvictionPoolLRU数组，尝试把采样的每个KV对插入EvictionPoolLRU数组，取决于如下条件之一：

有一成立，evictionPoolPopulate就能把采样KV对插入EvictionPoolLRU数组。等所有采样键值对都处理完后，evictionPoolPopulate函数就完成对待淘汰候选键值对集合的更新了。

接下来，performEvictions开始选择最终被淘汰的KV对。

因evictionPoolPopulate已更新EvictionPoolLRU数组，且该数组里的K，是按空闲时间从小到大排好序了。所以，performEvictions遍历一次EvictionPoolLRU数组，从数组的最后一个K开始选择，若选到的K非空，就把它作为最终淘汰的K。

该过程执行逻辑：

一旦选到被淘汰的K，performEvictions就会根据Redis server的惰性删除配置，执行同步删除或异步删除：

至此，performEvictions就淘汰了一个K。若此时释放的内存空间还不够，即没有达到待释放空间，则performEvictions还会 重复执行 前面所说的更新待淘汰候选KV对集合、选择最终淘汰K的过程，直到满足待释放空间的大小要求。

performEvictions流程：

近似LRU算法并未使用耗时且耗空间的链表，而使用 固定大小的待淘汰数据集合 ，每次随机选择一些K加入待淘汰数据集合。

最后，按待淘汰集合中K的空闲时间长度，删除空闲时间最长的K。

根据LRU算法的基本原理，发现若严格按基本原理实现LRU算法，则开发的系统就需要额外内存空间保存LRU链表，系统运行时也会受到LRU链表 *** 作的开销影响。

而Redis的内存资源和性能都很重要，所以Redis实现近似LRU算法：

一个算法的基本原理和算法的实际执行，在系统开发中会有一定折中，需综合考虑所开发的系统，在资源和性能方面的要求，以避免严格按照算法实现带来的资源和性能开销。

redis-cli --scan  ，306版本，不知道低版本的有没有这个参数。

如果想要 所有键值对

redis-cli --scan |while read a;do echo -n $a: ;redis-cli get $a ;done

-r（repeat）选项代表将命令执行多次，例如下面 *** 作将会执行三次ping

命令：

redis-cli -r 3 ping 

PONG

PONG 

PONG

-i（interval）选项代表每隔几秒执行一次命令，但是-i选项必须和-r选 项一起使用，下面的 *** 作会每隔1秒执行一次ping命令，一共执行5次：

注意-i的单位是秒，不支持毫秒为单位，但是如果想以每隔10毫秒执行 一次，可以用-i001

redis-cli -r 5 -i 001 ping

例如下面的 *** 作利用-r和-i选项，每隔1秒输出内存的使用量，一共输出 100次

redis-cli -r 100 -i 1 info | grep used_memory_human 

used_memory_human:295G 

used_memory_human:295G

-x选项代表从标准输入（stdin）读取数据作为redis-cli的最后一个参 数，例如下面的 *** 作会将字符串world作为set hello的值

$ echo "world" | redis-cli -x set hello 

OK

-c（cluster）选项是连接Redis Cluster节点时需要使用的，-c选项可以防 止moved和ask异常

如果Redis配置了密码，可以用-a（auth）选项，有了这个选项就不需要 手动输入auth命令

--scan选项和--pattern选项用于扫描指定模式的键，相当于使用scan命令

--slave选项是把当前客户端模拟成当前Redis节点的从节点，可以用来 获取当前Redis节点的更新 *** 作

下面开启第一个客户端，使用--slave选项，看到同步已完成：

$ redis-cli --slave 

SYNC with master, discarding 72 bytes of bulk transfer 

SYNC done Logging commands from master

--rdb选项会请求Redis实例生成并发送RDB持久化文件，保存在本地。 可使用它做持久化文件的定期备份

--pipe选项用于将命令封装成Redis通信协议定义的数据格式，批量发送 给Redis执行

例如下面 *** 作 同时执行了set hello world和incr counter两条命令：

echo -en '3\r\n$3\r\nSET\r\n$5\r\nhello\r\n$5\r\nworld\r\n2\r\n$4\r\nincr\r\ n$7\r\ncounter\r\n' | redis-cli --pipe

--bigkeys选项使用scan命令对Redis的键进行采样，从中找到内存占用比

较大的键值，这些键可能是系统的瓶颈

--eval选项用于执行指定Lua脚本，有关Lua脚本的使用将在34节介绍。

latency有三个选项，分别是--latency、--latency-history、--latency-dist。 它们都可以检测网络延迟，对于Redis的开发和运维非常有帮助。

该选项可以测试客户端到目标Redis的网络延迟，例如当前拓扑结构如 图3-4所示。客户端B和Redis在机房B，客户端A在机房A，机房A和机房B是

跨地区的

客户端B：

redis-cli -h {machineB} --latency 

min: 0, max: 1, avg: 007 (4211 samples)

客户端A：

redis-cli -h {machineB} --latency 

min: 0, max: 2, avg: 104 (2096 samples)

可以看到客户端A由于距离Redis比较远，平均网络延迟会稍微高一些

--latency的执行结果只有一条，如果想以分时段的形式了解延迟信息， 可以使用--latency-history选项：

redis-cli -h 1010xxxx --latency-history 

min: 0, max: 1, avg: 028 (1330 samples) -- 1501 seconds range… 

min: 0, max: 1, avg: 005 (1364 samples) -- 1501 seconds range

可以看到延时信息每15秒输出一次，可以通过-i参数控制间隔时间。

（3）--latency-dist

该选项会使用统计图表的形式从控制台输出延迟统计信息。

--stat选项可以实时获取Redis的重要统计信息，虽然info命令中的统计信 息更全，但是能实时看到一些增量的数据（例如requests）对于Redis的运维还是有一定帮助的

--no-raw选项是要求命令的返回结果必须是原始的格式，--raw恰恰相反，返回格式化后的结果。

在Redis中设置一个中文的value：

$redis-cli set hello "你好" 

OK

如果正常执行get或者使用--no-raw选项，那么返回的结果是二进制格式：

如果使用了--raw选项，将会返回中文：

$redis-cli --raw get hello

你好

redis不重复取出思路如下：（1）、后台有一个单独获取token接口 A，token是一个随机唯一字符串，可以是uuid，每次调用获取（token也可以前端生成，减少一次前后台交互）；

还有一个提交业务数据的接口B（就是为了防止这个接口B，重复 *** 作提交）;

（2）、在进入需要提交页面时，调用后台接口A，例如获取token = 123，并且返回给前端token

（3）、前端点击提交按钮时，只调用提交接口B，此处不能再次调用获取token接口A，提交业务数据，并且把之前接口A获取的token = 123 带到后台过去，

需要保证在当前页面重复点击过来传递的token是同一个值；

Redis（Remote Dictionary Server )，即远程字典服务，是一个开源的使用ANSI C语言编写、支持网络、可基于内存亦可持久化的日志型、Key-Value数据库，并提供多种语言的API。

集合的数据是唯一的，插入之后再次插入时不会执行

(1)查询集合里面元素的数量

(2)从集合中获取数据

--如果count省略则随机获取一条数据

--如果count为其他大于1的整数，则获取对应条数据

--如果count对应的证书大于集合总数据的条数，则获取集合所有数据

(3)获取集合中的所有数据

(4)判断集合中是否存在某个元素

--如果数据存在，则返回1，如果数据不存在，则返回0

既属于A集合又属于B/其他集合，集合数量可以是多个，多个代表对应所有集合的交集

A集合与B/其他集合所包含的所有数据，如果数据一样则去重，集合数量可以是多个，多个代表对应所有集合的并集

只属于A（key1）集合，不属于其他集合的数据

锁要实现的三个目标：

该命令仅在密钥尚不存在时才设置key（NX选项），到期时间为30000毫秒（PX选项）。键设置为值 “myrandomvalue” 。此值必须在所有客户端和所有锁定请求中都是唯一的。

使用随机值是为了以安全的方式释放锁，实现上使用了Redis的脚本：只有当key存在且其值恰好是我期望的随机值时才删除key。这是通过以下Lua脚本完成的：

这一点很重要，这可以避免删除由另一个客户端创建的锁。例如：

ok，这样我们完成redis分布式锁的实现。你以为这样就安全了吗，接下来我们设想这样一个情况：

首先，假设我们的Redis是主从的：

这时就会同时有两把锁存在的情况。对于这种情况（非常特殊），Redis官方提供了一个叫RedLock的解决方案。

我们假设我们有N个Redis主机。这些节点完全独立，因此我们不使用复制或任何其他隐式协调系统。我们假设N = 5，这是一个合理的值，因此我们需要在不同的计算机或虚拟机上运行5个Redis主服务器，以确保它们以大多数独立的方式失败。

为了获取锁，客户端执行以下 *** 作：

我个人觉得对于小公司这还是相当昂贵的。

其他的细节请参考 redis官方文档 。

以上就是关于Redis的LRU缓存淘汰算法实现全部的内容，包括:Redis的LRU缓存淘汰算法实现、有没有好的方法遍历redis里面的所有key、Redis-cli详解等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！