之前看到一道面试题：Redis的过期策略有哪些？记忆消除机制是什么？手写LRU代码？图片来自PexelsStudy作者，分析工作中遇到的问题。希望看完这篇文章，对大家有所帮助。来自一个莫名其妙的故障，问题的描述：一个接口列表数据，依赖定时器任务的生成，有时有，有时没有。怀疑redis过期删除策略的排查过程比较长，因为手动执行了timer，setdata没有报错，但是setdata之后并没有生效。set没有报错，但是set完成后再次查看没有数据，开始怀疑redis的过期删除策略（准确的说应该是redis的内存回收机制中的数据淘汰策略触发了内存限制剔除数据），导致新加入的Redis数据被丢弃。最后发现失败的原因是配置错误，导致数据写错了地方，并不是Redis的内存回收机制导致的。想了想这次失败，如果下次再遇到类似的问题，怀疑后如何有效证明Redis内存回收的正确性呢？如何快速证明猜测的正确性？而在什么情况下怀疑内存回收是否合理？下次再遇到类似的问题，就能更快更准确的定位问题的原因。另外，Redis的内存回收机制的原理也需要掌握，才能明白它是什么，为什么。花了点时间查资料研究Redis的内存回收机制，看了内存回收的实现代码。通过代码和理论的结合，给大家分享一下Redis的内存回收机制。为什么需要内存回收？原因有二：在Redis中，Set命令可以指定Key的过期时间。当达到过期时间时，Key将失效。Redis是基于内存操作的，所有的数据都存储在内存中，一台机器的内存是有限的，非常宝贵。基于以上两点，为了保证Redis能够持续提供可靠的服务，Redis需要一种机制来清理不常用的、无效的、冗余的数据。无效数据需要及时清理，这就需要内存回收。Redis的内存回收机制Redis的内存回收主要分为两部分：过期删除策略和内存淘汰策略。过期删除策略删除已达到过期时间的密钥。①定时删除每个Key都会创建一个定时器，设置了过期时间，一旦到了过期时间就立即删除。这种策略可以立即清除过期数据，对内存比较友好，但缺点是处理过期数据会占用大量CPU资源，会影响Redis的吞吐量和响应时间。②懒删除当访问一个Key时，判断Key是否过期，过期则删除。这种策略可以最大程度的节省CPU资源，但是对内存很不友好。极端情况下，大量过期的key可能不会被再次访问，所以不会被清除，导致大量内存占用。在计算机科学中，惰性删除（英语：lazydeletion）是指从哈希表（也称为哈希表）中删除元素的方法。在这个方法中，删除只是标记一个要删除的元素，而不是完全清除它。删除的位置在插入时被视为空元素，在搜索时被占用。③每隔一段时间定时删除，扫描Redis中过期的Key字典，清除一些过期的Key。该策略是前两者的折衷方案。它还可以通过调整计划扫描的时间间隔和每次扫描的限制时间消耗来实现不同情况下CPU和内存资源的最佳平衡。在Redis中，周期删除和惰性删除都有使用。过期删除策略的原理为了不让大家听起来一头雾水，在正式介绍过期删除策略的原理之前，先介绍一下可能会用到的Redis的一些基础知识。①RedisDB结构定义我们知道Redis是一个键值对数据库。对于每个Redis数据库，Redis使用一个RedisDB结构来保存。其结构如下：typedefstructredisDb{dict*dict;/*数据库的键空间，保存数据库中所有的键值对*/dict*expires;/*保存所有过期的键*/dict*blocking_keys;/*Keyswithclientswaitingfordata(BLPOP)*/dict*ready_keys;/*BlockedkeysthatreceivedaPUSH*/dict*watched_keys;/*WATCHEDkeysforMULTI/EXECCAS*/intid;/*数据库ID字段代表不同的数据库*/longlongavg_ttl;/*AverageTTL,justforstats*/}redisDb;从结构定义我们可以发现，对于每一个Redis数据库，都会使用一个数据字典结构来保存每一个键值对，dict的结构图如下：以上是实现中使用的核心数据结构到期策略。程序=数据结构+算法。介绍完数据结构，我们继续看处理算法。②expires属性RedisDB定义的第二个属性是expires，它的类型也是字典。Redis会将所有过期的键值对添加到expires中，然后通过周期性的删除来清除expires中的值。添加expires的场景有：Set指定过期时间expire。如果在设置Key时指定了过期时间，Redis会直接将Key添加到expires字典中，并将超时时间设置到字典元素中。调用expire命令显式指定Key的过期时间。恢复或修改数据，从Redis持久化文件中恢复文件或修改Key，如果数据中的Key设置了过期时间，将这个Key添加到expires字典中。以上所有操作都会将过期的Key保存到expires中。Redis会定期从expires字典中清理过期的键。③Redis清理过期key的时候Redis启动的时候，会注册两种事件，一种是时间事件，一种是文件事件。时间事件主要是Redis处理后台操作的一类事件，比如客户端超时，删除过期的Key；文件事件正在处理请求。在时间事件中，Redis注册的回调函数是serverCron。在定时任务回调函数中，通过调用databasesCron清理一些过期的key。（这是定时删除的实现）intserverCron(structaeEventLoop*eventLoop,longlongid,void*clientData){.../*HandlebackgroundoperationssonRedisdatabases.*/databasesCron();...}每次访问Key时，expireIfNeeded函数会调用判断Key是否过期，如果过期则清除Key。（这是懒删除的实现）robj*lookupKeyRead(redisDb*db,robj*key){robj*val;expireIfNeeded(db,key);val=lookupKey(db,key);...returnval;}每次事件在循环执行过程中，主动清理一些过期键。（这也是懒删除的实现）;aeProcessEvents(eventLoop,AE_ALL_EVENTS);}}voidbeforeSleep(structaeEventLoop*eventLoop){.../*Runafastexpirecycle(调用的函数会返回-不需要ASAPIfastcycle).*/if(server.active_expire_enabled&&server.masterhost==NULL)activeExpireCycle(ACTIVE_EXPIREF_C④）过期策略的实现我们知道Redis是单线程运行的，在清理Key的时候不能占用过多的时间和CPU。需要在不影响正常服务的情况下，尽可能清理过期的Key。过期清理的算法如下：server.hz配置serverCron任务的执行周期，默认为10，即CPU空闲时每秒执行十次。每次清除过期键的时间不能超过CPU时间的25%：timelimit=1000000*ACTIVE_EXPIRE_CYCLE_SLOW_TIME_PERC/server.hz/100。例如hz=1，一次cleanup的最长时间为250ms，hz=10，一次cleanup的最长时间为25ms。如果是快速清理模式（在beforeSleep函数中调用），一次清理的最大时间为1ms。依次遍历所有DB。从DB过期列表中随机取20个Key判断是否过期，如果过期则清理。如果超过5个key过期，重复第5步，否则继续处理下一个DB。在清洗过程中，如果达到25%的CPU时间，则退出清洗过程。从实现的算法可以看出，这只是一个简单的基于概率的算法，而且是随机选择的，所以不可能删除所有过期的key。通过增加hz参数，可以增加清理的频率，及时清除过期的key。删除，但是hz太高会增加CPU时间的消耗。⑤删除在KeyRedis4.0之前，删除命令是del，del会直接释放对象的内存。在大多数情况下，这个命令非常快，没有任何延迟的感觉。但是，如果删除的Key是一个非常大的对象，比如包含千万级元素的Hash，那么删除操作会造成单线程卡顿，Redis的响应会变慢。为了解决这个问题，在Redis4.0版本中引入了unlink命令，可以对删除操作进行“惰性”处理，将删除操作抛给后台线程，后台线程会异步回收内存。其实判断Key需要过期后，删除Key的真正过程是先将expire事件广播给从库和AOF文件，然后根据Redis的配置决定是立即删除还是异步删除.如果立即删除，Redis会立即释放Key和Value占用的内存空间，否则，Redis会在另一个BIO线程中释放需要删除的空间。总结：一般来说，Redis的过期删除策略是在启动时注册serverCron函数，每一个时钟周期，会提取expires字典中的一些Key进行清理，从而实现定时删除。另外Redis在访问Key的时候会判断Key是否已经过期。过期则删除，每次Redis访问事件到来，beforeSleep会在1ms内调用activeExpireCycle函数主动清理部分Key。这就是懒删除的实现。.Redis结合了定时删除和惰性删除，基本上把过期数据的清理处理的很好，但实际上还是存在一些问题。如果过期键很多，有一部分被定时删除漏掉了，没有及时检查，也就是不惰性删除，那么就会在内存中堆积大量过期键，导致Redis内存不足。当内存耗尽时，新密钥到来时会发生什么？是直接丢弃还是其他措施？有没有办法接受更多的钥匙？内存淘汰策略Redis的内存淘汰策略是指当内存达到maxmemorylimit时，使用某种算法来决定清理哪些数据，从而保证新数据的存储。Redis的内存淘汰机制如下：noeviction：当内存不足以容纳新写入的数据时，新的写入操作会报错。allkeys-lru：当内存不足以容纳新写入的数据时，在key空间（server.db[i].dict）中，移除最近最少使用的Key（这个是最常用的）。allkeys-random：当内存不足以容纳新写入的数据时，在key空间（server.db[i].dict）中，随机移除一个Key。volatile-lru：当内存不足以容纳新写入的数据时，移除key空间（server.db[i].expires）中设置过期时间的最近最少使用的Key。volatile-random：当内存不足以容纳新写入的数据时，从key空间（server.db[i].expires）中随机移除一个key，并设置过期时间。volatile-ttl：当内存不足以容纳新写入的数据时，在设置了过期时间的key空间（server.db[i].expires）中，先删除过期时间较早的Key。可以通过配置文件中的maxmemory-policy配置使用哪种驱逐机制。①什么时候淘汰？Redis每处理一条命令（processCommand函数调用freeMemoryIfNeeded）都会判断当前Redis是否达到内存的最大限制。如果达到限制，它会使用相应的算法来处理需要删除的Key。伪代码如下：intprocessCommand(client*c){...if(server.maxmemory){intretval=freeMemoryIfNeeded();}...}②LRU实现原理Redis在剔除Key时默认采用最常用的LRU算法（最近使用过）。Redis通过在每个redisObject中保存lRU属性来保存Key的最近访问时间，实现LRU算法时直接读取Key的lRU属性。具体实现中，Redis遍历每个DB，从每个DB中随机抽取一批样本key，默认为3个key，然后从这3个key中删除最近最少使用的key。伪代码如下：keys=getSomeKeys(dict,sample)key=findSmallestIdle(keys)remove(key)3这个数字就是配置文件中的maxmeory-samples字段，也可以设置采样大小。如果设置为10，效果会更好，但也会消耗更多的CPU资源。以上就是Redis内存回收机制原理的介绍。理解了上面的原理介绍，回到最初的问题。在对Redis内存回收机制存疑时，能否及时判断故障是否由Redis内存回收机制引起？回到问题的本源，如何证明故障是不是内存回收机制引起的呢？根据前面的分析，如果Set不报错但不生效，只有两种情况：设置的过期时间太短，比如1s。内存超出最大限制，设置了noeviction或allkeys-random。所以，遇到这种情况，首先检查Set中是否添加了过期时间，过期时间是否合理。如果过期时间短，应检查设计是否合理。如果过期时间没有问题，需要查看Redis的内存使用情况，查看Redis的配置文件或者使用Redis中的Info命令查看Redis的状态，maxmemory属性查看最大内存值.如果为0，则没有限制。这时候受限于total_system_memory。将used_memory与Redis的最大内存进行比较，查看内存使用情况。如果当前内存使用率高，需要检查是否配置了最大内存。如果有，并且超出内存，则可以初步判断是内存回收机制导致按键设置失败。还需要检查内存淘汰算法是noeviction还是allkeys-random。如果是，则可以确认是Redis的内存回收机制导致的。如果没有超出内存，或者内存淘汰算法不是以上两种，还需要检查Key是否过期，通过TTL检查Key的存活时间。如果程序运行起来Set没有报错，TTL应该立即更新，否则说明Set失败了。如果设置失败，则应检查操作程序代码是否正确。总结一下，Redis有两种回收内存的方式，一种是回收过期的Key，另一种是超过Redis的最大内存后释放内存。对于第一种情况，Redis在每次访问Key时都会判断是否到了Key的过期时间，如果到了则删除Key。Redis启动时会创建一个定时事件，定时清理一些过期的key。默认是每秒执行十次检查，每个过期key被清理的时间不超过CPU时间的25%。即hz=1时，最大清洗时间为250ms，hz=10时，最大清洗时间为25ms。对于第二种情况，Redis每处理一个Redis命令都会判断当前Redis是否达到内存的最大限制。如果达到限制，它会使用相应的算法来处理需要删除的Key。看完这篇文章，你能回答文章开头的面试题吗？
