本文转载自微信公众号“月亮聊天技术”，作者月亮聊天技术。转载本文请联系moonchat科技公众号。简介我们知道redis是一个非常常用的内存数据库，从内存中读取数据是它效率很高的原因之一，但是如果有一天，“redis分配的内存满了怎么办”？遇到这个面试题不要慌，我们可以从两个角度来回答这种问题：“redis会做什么？”可用内存足够了。“通过配置文件配置”有两种方式//设置redis的最大内存大小为1000Mmaxmemory1000mb设置内存大小通过在redis安装目录下的redis.conf配置文件中添加如下配置“通过命令修改”//设置redis最大占用内存大小为1000M127.0.0.1:6379>configsetmaxmemory1000mbredis支持运行时通过命令动态修改内存大小。这个方法立竿见影。reids的内存总是受限于机器的内存，不能无限增长，那么没有办法增加redis的可用内存怎么办？内存淘汰策略其实Redis定义了“8种内存淘汰策略”来处理redis内存满的情况：1.noeviction：直接返回错误，不淘汰任何存在的rediskey2.allkeys-lru：all使用lru算法淘汰keys3.volatile-lru：使用lru算法淘汰有过期时间的keys4.allkeys-random：随机删除rediskey5.volatile-random：随机删除过期时间为6的rediskeys。volatile-ttl：删除即将过期的rediskey7.volatile-lfu：根据lfu算法从有过期时间的key中删除8.allkeys-lfu：根据lfu算法从所有key中删除这些内存淘汰策略很容易了解。下面重点讲解一下lru、lfu、ttl是如何实现的。lru的最佳实践？lru是LeastRecentlyUsed的缩写，即“最近很少使用”，也可以理解为最长时间未使用。最近刚用过的，后面用到的概率就越大。由于内存是非常宝贵的，我们可以存放在缓存中的数据是有限的。比如我们只能存储10000条数据。当内存已满时，每向缓存中插入一条新数据，就必须丢弃最长的一条未被使用的旧数据。我们把上面的内容梳理一下，可以得到一些需求：“1.保证它的读写效率，比如读写的复杂度是O(1)”“2.当读取一条数据时，就是最近使用的时间被更新”“3.当插入一条新的数据时，删除最长时间没有被使用的数据。”所以一定要尽量保证查询效率非常高，插入效率非常高。我们知道，如果只考虑查询效率，那么哈希表可能是最好的选择。如果只考虑插入效率，那么链表肯定有一席之地。然而，这两种数据结构在单独使用时都有其缺点。那么，有没有一种既能保证查询效率，又能保证插入效率的数据结构呢？于是哈希+链表的结构就出现了哈希表。查询数据在链表中的位置，链表负责数据的插入。链表头部插入新数据有两种情况；1、当链表满时，丢弃链表尾部的数据。这个比较简单，直接擦除链表尾部的指针，清除对应hash中的信息即可。2、每当缓存命中（即缓存数据被访问）时，将数据移至链表头部；在这种情况下，我们发现，如果它命中链表的中间节点，我们需要做的是1)。将节点移动到头节点2)。“设置本节点的前一个节点的下一个节点为本节点的下一个节点”，这里会出现问题，我们找不到本节点的前一个节点，因为是单向链表，所以生成了一个新模型。这个时候，双向链表的作用也被带出来了。可以直接定位父节点。这是非常有效的。又因为双向链表有尾指针，去掉最后一个尾节点非常方便快捷，所以最后的解决方案是使用“哈希表+双向链表”的结构lfu的最佳实践？LFU：LeastFrequentlyUsed，最少被使用的策略。在一段时间内，“使用频率最低”的数据将首先被淘汰。LeastUsed(LFU)是一种用于管理计算机内存的缓存算法。主要是记录和跟踪使用的内存块数。当缓存已满，需要更多空间时，系统会清除内存块使用频率最低的内存。使用LFU算法最简单的方法是为每个加载到缓存中的块分配一个计数器。每次引用该块时，计数器都会加一。当缓存达到容量并且有新的内存块等待插入时，系统会搜索计数器最低的块并将其从缓存中删除。在这里，我们提出了一个实现O(1)时间复杂度的LFU实现。它支持的操作包括插入、访问和删除。如图：由两个双向链表+哈希表组成，上层双向链表用于计数。下面的双向链表用于记录存储的数据。链表的头节点存储数字，哈希表的值对象记录下面双向链表的数据。这里我们走一下插入过程：将要存入的数据插入到哈希表中找到对应的下层双向链表，将该节点的前一个节点连接到该节点的下一个节点（这里可能只有你自己，去掉即可itdirectly），然后判断你上面的双向链表的计数是否比当前计数大1“如果是”，将自己移动到上层双向链表，“判断双向链表下是否有元素”，如果不存在，则删除节点“如果不存在或者上层双向链表没有”下一个节点“是增加一个新节点，将哈希表中的计数设置为当前计数+1”不存在“，存储hash表中的数据，像这样把数据连接到双向链表的头节点（这里链表可以不初始化）查找和插入的时候，效率都是O(1).redisTTL是怎么实现的?TTL存储的数据结构redis有一个专门用于TTL时间存储的dict，w这是redisDb中的dict*expires字段。顾名思义，dict是一个哈希表。key是对应的rediskey，value是对应的TTL时间。?dict的数据结构中包含2个dicttht对象，主要用于解决hash冲突过程中对数据进行re-hash。TTL设置过期时间TTL设置密钥过期时间主要有四种方式：expire使用相对时间，以秒为单位的过期策略expireat使用绝对时间，以秒为单位使用过期策略pexpire使用相对时间，以毫秒为单位以pexpireat为单位的过期策略是基于绝对时间和以毫秒为单位的过期策略{"expire",expireCommand,3,"w",0,NULL,1,1,1,0,0},{"expireat",expireatCommand,3,"w",0,NULL,1,1,1,0,0},{"pexpire",pexpireCommand,3,"w",0,NULL,1,1,1,0,0},{"pexpireat",pexpireatCommand,3,"w",0,NULL,1,1,1,0,0},expireexpireatpexpirepexpireat从实际设置过期时间的实现函数来看，相对时间策略会以当前时间为基准时间，而绝对时间策略会“以0为基准时间”。voidexpireCommand(redisClient*c){expireGenericCommand(c,mstime(),UNIT_SECONDS);}voidexpireatCommand(redisClient*c){expireGenericCommand(c,0,UNIT_SECONDS);}voidpexpireCommand(redisClient*c){expireGenericCommand(c,mstime(),UNIT_MILLISECONDS);}voidpexpireatCommand(redisClient*c){expireGenericCommand(c,0,UNIT_MILLISECONDS);}整个过期时间最后会转化为绝对时间存储，由基础时间+过期时间公式计算。?对于相对时间，参考时间为当前时间，对于绝对时间，相对时间为0。?中途考虑设置的过期时间是否已经过期。如果已经过期，master会删除数据，并将删除动作同步给slave。?正常设置过期时间通过setExpire方法保存到dict*expires对象中。/***该函数是EXPIRE、PEXPIRE、EXPIREAT、PEXPIREAT命令的底层实现函数。**命令的第二个参数可以是绝对值也可以是相对值。*执行*AT命令时，basetime为0，其他情况下保存当前绝对时间。**unit用于指定argv[2]（传入过期时间）的格式，*可以是UNIT_SECONDS或UNIT_MILLISECONDS，*basetime参数始终为毫秒格式。*/voidexpireGenericCommand(redisClient*c,longlongbasetime,intunit){robj*key=c->argv[1],*param=c->argv[2];longlongwhen;/*unixtimeinmillisecondswhenthekeywillexpire.*///取出when参数if(getLongLongFromObjectOrReply(c,param,&when,NULL)!=REDIS_OK)return;//如果传入的过期时间是秒，则转为毫秒if(unit==UNIT_SECONDS)when*=1000;when+=basetime;/*Nokey,returnzero.*///取出keyif(lookupKeyRead(c->db,key)==NULL){addReply(c,shared.czero);return;}/**in加载数据，或者当服务器是从节点时，*即使EXPIRE的TTL为负，或者EXPIREAT提供的时间戳已经过期，*服务器不会主动删除这个key，而是等待显式的DEL命令主节点。**程序会继续设置（一个可能已经过期的TTL）作为key的过期时间，*等待主节点发送DEL命令。*/if(when<=mstime()&&!server.loading&&!server.masterhost){//当提供的时间已过时，服务器为主节点，不加载数据robj*aux;redisAssertWithInfo(c,key,dbDelete(c->db,key));server.dirty++;/*Replicate/AOFthisasanexplicitDEL.*///传播DEL命令aux=createStringObject("DEL",3);rewriteClientCommandVector(c,2,aux,key);decrRefCount(aux);signalModifiedKey(c->db,key);notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"del",key,c->db->id);addReply(c,shared.cone);return;}else{//设置key的过期时间//如果服务器是附属节点，或者服务器正在加载，//那么这个when可能已经过期setExpire(c->db,key,when);addReply(c,shared.cone);signalModifiedKey(c->db,key);notifyKeyspaceEvent(REDIS_NOTIFY_GENERIC,"expire",key,c->db->id);server.dirty++;return;}}setExpire函数主要针对db中的key->expires对应的dictEntry设置过期时间。/**设置keykey的过期时间为when*/voidsetExpire(redisDb*db,robj*key,longlongwhen){dictEntry*kde,*de;/*Reusethesdsfromthemaindictintheexpiredict*///取出keykde=dictFind(db->dict,key->ptr);redisAssertWithInfo(NULL,key,kde!=NULL);//根据key获取key的过期时间de=dictReplaceRaw(db->e??xpires,dictGetKey(kde));//设置key的过期时间//这里是直接用整型值保存过期时间，不是用INT编码的String对象dictSetSignedIntegerVal(de,when);}redis什么时候执行淘汰策略？Redis中有三种删除操作。这个策略是定时删除的：for有一个有过期时间的key。当时间到了，定时任务会被立即删除。因为需要维护一个定时器，会占用cpu资源，尤其是有过期时间的rediskey越来越多，性能会直线上升。删除：只有再次访问key时，才会检查key的过期时间，如果已经过期则删除。这样的话，只有在访问的时候才会删除，所以有可能有些过期的rediskey永远也访问不到，会一直占用redis内存。定期删除：每隔一段时间，它会检查并删除过期的密钥。该方案相当于上述两种方案的折衷。通过最合理地控制删除时间间隔来删除key，减少CPU资源的消耗，使删除操作合理化。巨人的肩膀https://www.jianshu.com/p/53083f5f2ddchttps://zhuanlan.zhihu.com/p/265597517
