/首页
/开源
/关于
再聊一道xue微简单点儿的面试题
发表@2020-04-02 12:04:51
更新@2023-04-27 16:00:10
大家好，我是我心永恒的老李。 今天下午的时候，我看到来自于大洋彼岸的短视频：一些擦腚纸贩子都在囤积居奇，高价兜售擦腚纸，看到这些消息真的是雏菊一紧。沙雕肺炎病毒全球肆虐的时候，难道不应该是买口罩保护上面的口么，怎么抢着买擦腚纸招呼下边那个眼了？算了，管不了那么多了，我也囤点儿擦腚纸得了。 买擦腚纸这件小事儿，在这个物欲横流而又穷人穷横的年代，必须要货比三家：「匋玉」和「并夕夕」横向比了下还是「并夕夕」以绝对的优势胜出了！看着「匋玉」上昂贵的擦腚纸价格，我心如刀绞，这公司啥时候堕落成这样了？你看人家「并夕夕」，包邮到家还仅售一块三...  大概三年多以前吧好像是，我曾经有缘去「匋玉」所属的母公司「四十大盗」集团望京总部面试过，大概夭折在了第三轮：主要不是我差劲，而是竞争对手们太厉害，还因为后文马上要提到的那条狗子。 那天我白嫖了一辆锁已经被暴力开拔的免费ofo到了「四十大盗」望京中心后，刚把ofo横着放倒藏到草丛里，就看到一条狗子疯狂地冲我跑了过来，旁边还有个惊慌失措的小姐姐。当时我心里一横就一个想法：这沙雕狗子竟然敢咬小姐姐，我必须得冲上去挡在前面狠狠地咬这条沙雕狗子。于是我「嗷」地一声冲着狗子猛扑过去，把狗子吓得猛一哆嗦，夹起来的尾巴这一明显的特征已然透露出这狗子已经被我征服了，就在这关键时刻，这姐们儿突然抱起那狗子慌里慌张地跑了，中间还撇了我几眼，从她的眼神中我可以读取到信息：这tm哪儿来的神经病... 实际上人家问了我很多问题，但我今天就想说其中一个：Redis中Key的过期删除原理大概是怎样的？ 题外话：之所以能记起这个问题，完全是因为有个泥腿子说MongoDB支持定时删除数据。  当时这问题可给我整懵了，我那会儿可没怎么深入研究过Redis，所以当时我就开启了胡诌模式，而且一定程度上说我应该是胡诌对了一部分：先胡诌Redis对于过期Key处理的三种策略，再胡诌定时器，但是胡诌定时器的时候实际上心里已经很虚了，和三种策略连贯性上串联地并不好。 现在想想，这个问题真挺简单的，当时只要我再狠狠地吃口屎冷静一下，没准能全部胡诌对了。回到正题上来，Redis到底是如何结合Key的过期策略实现对过期Key删除的？ 首先说下业界通用的关于过期Key处置的三种策略： - 定时删除：这种策略最狠的，假如你搞了个key叫做「lurenjia」，五分钟后删除，那么五分钟后这个key就一定会被及时地删除掉。因为在这种策略下，当你给一个key搞了一个过期时间的同时，会创建一个定时器，这个定时器会在按时启动，然后不干别的，只干删除。但是这种策略实在太TM狠了，如果你有10万个带过期时间的key，就要搞10万个定时器，而Redis作为主业务流程为单进程单线程的典范，到底是忙着响应正规业务需求，还是忙着启动这10万个定时器删除过期key呢？男人，请善待CPU。友情提示：Redis里没有实现这种策略，如我说错了纠正我。 - 惰性删除：这种策略也是最狠的，只不过是狠在了另外一个极端。就算给一个路人甲key指定了过期时间，这个key到期也不会被删除。你深爱着这个key以至于你每次获取这个key的时候，都会计算一下这个key距离过期时间还有多长时间，终于到最后一次用这个key的时候你发现这个key过期了，你就再也不爱这个key了；如果很不幸你给一个key设定了过期时间后再也没用过这个key，那这个key可能将永远躺在内存里，那这也太TM狠了，提起裤子不认人？男人，请善待内存。 - 定期删除：比较温和折衷的策略。大概就是每隔一段固定的时间，就去扫描一波儿，按照算法删除一些过期的key，这个删除操作的执行时长也是有限制的。所以这个策略需要注意的就是两点：执行间隔和执行时长，这个需要根据自己的业务场景在定了，总之，TA一定程度既解决了CPU被浪费的问题又解决内存被浪费的问题。 以上内容，我默认大家都应该是100%知道的。而且请务必注意：以上三种策略是通用策略，而不是Redis的三种策略。Redis里，实现了惰性删除和定期删除两种策略。 这就完了？并没有，我们需要聊下定时器！定时器一般说来是分两种的： - 一种是定时发生的事件，比如今天晚上9点执行打卡一次，但只执行这一次，执行过了就算OK了 - 另一种是周期性发生的事件，比如每隔30分钟写一次日报给你的老板原上草同志 在Redis里应该大多数定时器都是周期性的（我没怎么太详细读过Redis源码，按场景说的话，Redis里应该大量都是周期性定时器，至于定时发生的定时器我不确定是否一定有），那么问题来了： 定时器是怎么实现的呢？ - 利用IO复用的超时时间。《PHP网络编程》里在讲select系统调用时候，还记得有个timeout参数吗？因为服务器会陷入到select循环中，每次都是阻塞在select调用处，你可以指定一个超时时间，表示过了这个超时时间依然没有文件描述符变成「可读」「可写」那么将重新开始下一次；同样，epoll中可以在epoll_wait()中指定超时时间。这是一种解决方案。你可以通过PHP调用下select系统调用来试试看。 - Linux下有个叫做settimer()的系统调用（你就粗暴当函数理解就行了），你们可以去感受一下。settimer会在满足时间的时候发出信号，所以你需要在相关进程/线程上安装好信号处理。PHP是没指望了，老老实实在Linux下用C去写一写试试吧。 - Linux下的timerfd，提供了了一系列timerfd_*函数来创建、销毁定时器，比如timerfd_create()、timerfd_settime()。不过有意思的timerfd创建出来的定时器都是以文件描述符形式体现的，你可以很方便地监听读写事件。虽然我这么说，不过可能还有会有一部分小老弟感受不到这意味着啥。PHP依然没戏，老老实实在Linux下用C去写一写试试吧。 - Libevent全家桶系列。嗯，这个之前在《PHP网络编程》里我做过演示的，只要你安装了event扩展，直接复制粘贴代码就能飞起，这个PHP写一写没问题的。但是Libevent底层可能也是通过epoll/select来实现的，我没看过Libevent源码实现，此处我主动保留意见。 好了上面就是就是一些常见的定时器实现的方法，讲这个就是就是为了铺垫Redis里过期key处理的实现，还是回到面试题本身来。不要妖魔化定时器，实际上TA就是个串串儿。 在Redis里，有一个叫做struct叫做redisDb，这个struct里有一个指针叫做expires的指针，这个指针指向了一个dict（你就粗暴理解为hashtable），然后这个dict（就是个hashtable）里存了所有的被设置了过期时间的key，TA大概是这样样子的： ```C // 仅仅为演示，具体redis里具体数据结构请参考redis源码 struct redisDb { dict * expires; // 指向一个dict（就是hashtable，就k=>v） } // 就key=>value，key就是键值，value就是过期时间 dict hashtable { key1 => 1234567 // 过期时间的unix时间戳 key2 => 1234567 // 过期时间的unix时间戳 key3 => 1234567 // 过期时间的unix时间戳 . .. ... } ``` 所以对于惰性删除这种策略，本质上就是每当你从Redis里获取一个key的时候，系统都会对比当前时间戳与key的过期时间戳，对比一下，这个逻辑我们在常规CURD业务里都经常用，Redis竟然与我们雷同，一定是Redis抄我们的。具体在Redis里，这个业务逻辑流程的函数叫做expireIfNeeded()，有兴趣同学可以仔细关注下。 所以对于定期删除这种策略，就是Redis本身的定期启动扫描，但是每次都是扫描一定数量的key，等扫描一段时间后系统记录下当前扫描位置然后强制结束，等下次再次扫描时候接着从上次终止的地方继续扫描。具体体现在Redis里就是activeExpireCycle()函数，这个函数会定期启动，每次挑选出一定数量的库，然后从每个库中挑选出一定数量的key，进行主动的删除处理，而且每次都是在有限时间内，避免Redis响应主业务出现问题。 那么我们接着唠下「定时删除」这种策略，敞开了唠，放飞自我！如果在Redis里要实现「定时删除」这种策略，方案上应该是要为「每个设置了过期时间的key同时创建一个定时器」，这种定时器会在到达的时候定时器启动主动删除掉key。而目前的Redis里，定时器事件大概是这样的（请注意定时器与定时器事件的区别）： ```C // 仅仅为演示的伪结构 time_event { int id // 定时器的id，反正是一个数字 long expire_time // 何时执行... callback process // 到期执行时候要执行哪个函数，就是回调 } ``` 然后所有的定时器事件以「链表」这种数据结构形式串在一起成了一个串串儿，新的定时器事件一定会被添加到「链表」的最前边，成为最强插队者。这个串串儿是无序的，这个无序是说expire_time是无序的，并不是说id无序。 假如说我们为每个设置了过期时间的key都要添加一个定时器事件，那么这个「无序的链表」将会承载很多东西了。因为串串儿是「expire_time」无序的，所以一个key的过期时间到了后定时器会执行后需要遍历整个串串儿找出满足「expire_time」条件的时间事件，这个时间复杂度是O(N)。Redis是一个主流程业务为单进程单线程的服务器，这种定时器以及定时器事件毫无疑问将会要了TA的小命。 所以我们继续放飞自我，还记得前面那张图里一个泥腿子说「Mongodb可以设置数据过期」这个事儿么？如果说下次你面试有面试官问你Mongodb这个大概是如何实现的，虽然你没有接触过Mongodb，但是你总是能根据目前已有的底层原理去大胆猜测一下吧？连推论都不敢推，你还敢对HR说你热爱这家公司？其实这里是个面试的小技巧，虽然面试官问的东西你没有接触过，但是你一定要尝试根据已有的基础知识去推测一下，面试是双向的，面试官对你循循善诱，你也要引导对面试官。 面试官：你能说下Mongodb删除过期数据的怎么实现的吗？ 老李想象中的泥：虽然我没接触过，但是我想推测一下，你看我设计的合不合理。 真实的泥：...呃，那个，没怎么用过Mongodb... 然后我们接着放飞自我，你们一定遇到过这种业务场景：当Redis某个key过期后，能不能通知一下我？...宝贝儿们，深入思考下，如果要实现一个稳定靠谱的通知功能，你觉得以目前Redis的现状，能实现么？友情提示：Redis有个关键字叫做keyspace，了解一下？ 最后说明一下什么叫「Redis是一个主流程业务为单进程单线程的服务器」，大家虽然都说Redis单进程单线程，这个意思是说Redis的主要逻辑是单进程单线程的，而不是所有流程。众所周知（我假装你知道）Redis在开启了rdb备份后，每次从内存向硬盘dump rdb文件的时候，都是fork出一个子进程执行的dump任务。如果不fork子进程执行这个dump任务，那Redis在dump期间一定是停止响应客户端请求的。所以说，你能说TA单进程单线程吗？所以一般说某某软件为单进程单线程，都是指其主业务流程为单进程单线程。 最后说明一下什么叫「Redis是一个主流程业务为单进程单线程的服务器」，大家虽然都说Redis单进程单线程，这个意思是说Redis的主要逻辑是单进程单线程的，而不是所有流程。众所周知（我假装你知道）Redis在开启了rdb备份后，每次从内存向硬盘dump rdb文件的时候，都是fork出一个子进程执行的dump任务。如果不fork子进程执行这个dump任务，那Redis在dump期间一定是停止响应客户端请求的。所以说，你能说TA单进程单线程吗？所以一般说某某软件为单进程单线程，都是指其主业务流程为单进程单线程。
