不同于nginx的精雕细琢,redis代码的风格趋向于简洁实用。简洁启事,下面所述不再列举任何源码,不拼凑任何外来资料。去除末枝,下面直入redis主题,尽可能简洁地描述redis的设计思想。
整体模型:单进程单线程事件驱动模式。
Redis在主处理流程中,采用了单进程接受各种client请求并返回结果,整体处理流程采用事件驱动的方式进行。通过其IO复用的方式监听aeEventLoop事件,在事件处理的过程中,这种模式对处理函数的要求:进行一次事件处理需要尽可能地快。因此会有以下几种处理方法:
1.对于非长时间处理事件,直接处理。如set命令;
2.对于需要长时间处理的事件,分步处理,直至完成。如rehash过程,在单次事件处理过程中,每次只移动一个桶。
3.对于阻塞函数,如从磁盘读取vm数据等,采用异步的模式。从磁盘load数据,是一个较为耗时的操作,如处理函数中直接读取数据,将会阻塞整体的单线程处理其他的client请求。
多线程开发的复杂性是我们所清楚的。采用单进程单线程的模式,可以避免很多复杂性,另外事务性操作,无须额外加锁,大大降低了开发难度。
IO复用
Redis的IO复用层,可以看作是一个tinylibevent,其实现只有四个文件,ae.c, ae_select.c, ae_kqueue.c,ae_epoll.c。一目了然,ae是事件监听总的interface,select、kqueque、epoll是三种可选的IO复用方式。小而够用,简洁高效,充分体现了redis的设计理念。RedisDefault:select,C10K max。
事件监听
在单线程事件驱动模型中,往往会遇到两种任务,定时处理任务及事件触发任务,于是会有如下问题:事件触发任务在无任务时,会处于阻塞状态;定时任务要求定时处理,于是往往会有如下两种处理方式:
1. 如果定时任务时间间隔为t,一般设IO复用层的超时时间为t/10,这样可以保证定时任务得到及时处理,在调用所有cron任务时,会做间隔时间判断。
2. 计算当前事件与最近的定时任务开始时间的间隔,设置IO复用超时时间为该事件。这样定时任务也能得到及时处理。
注意:以上定时任务的处理时间,都为估约时间,非精确时间。前一种方式每轮计算量少,当容易引起空转,后一种计算量大,但减少了空转次数。Redis采用的是后一种方式。
这里也许有人会问:为什么不采用sigaction、setitimer等设置精确时钟,以后再也不用为cron事件做额外处理。原因如下:
定时时钟,往往会让进程陷入内核态,内核软中断往往会打破用户态一个函数的完整性,因此会破坏相关的状态转移;另外加入软中断的程序,将可能为程序带来不可避免地复杂性。
以曾经做过一个项目的一段挫折经历为例:
一个电话多路呼转的项目,采用的是单线程异步事件驱动模型,每次定时任务有个让空闲通道“挂机”的任务。先前采用预制的驱动时钟,时钟信号为实时信号(信号宏值取32-64之间的一个数),信号在sigqueue中排队,这样如果任务阻塞返回后,会瞬间抛出大量时钟事件,造成空闲通道多次挂机失败。后改用setitimer设置系统时钟,软中断打断了用户态的一次mutex_lock和mutex_unlock,并且挂机时使用了该锁,造成整个进程时有时无的死锁现象。
数据结构
Intset,该set不同于hash set数据结构,该数据结构其实是一个有序数组,对于:
插入操作:二分查找该有序数组——>找到位置——>有则返回,无则插入该位置,memmove后续元素。
查找操作:二分查找。
相对于以hash table为基础的set而言,该模型简单且更省空间。时间复杂度,在作者的presentation中提及在size 20-50k的数据量下,基本与hashset无异。这里可以认为,hash set遍历链表的时间,与intset二分查找的时间基本差不多。但其实另一方面,作者没有提及的,intset的插入速度,实际降低了,因为需要memmove的数据量,是O(n)的;但较hash set更有优势的是,该array set,是有序的。
Ziplist,该数据结构是针对small size数据设计的数组list,好比常见的索引数组,不同于linkedlist,其保存在一个数组中,且用value-header保存链接项及其本身的偏移、长度,encoding等,用于遍历list。在需求上,encoding保证多种不同的数据,可以保存在同一个list中,如int16、int32、str等。
zset:hash dict + skip list。常见的有序set以rb tree为基础。而在整个redis中,我们很难发现任何复杂数据结构tree的踪影。Redis以hash dict保证散列查找的效率,以跳表结构保证有序及范围查找需求的快速满足,范围查找抛弃了rb tree,b+-* tree,也体现了其不想复杂的简洁美学。
......
整个redis中,没有任何专门的内存池结构。所有内存分配,不像stl,niginx,内存分配都有其内存池机构分配,redis没有!Redis全是size+malloc的zmalloc分配,其常见的小对象,在intset,ziplist等数据结构地以数组方式申请,并不断用realloc的方式resize,间接地体现了内存池的思想,但却没有实现一个内存池管理模块,作者简单暴力的美学,体现得淋漓尽致。
持久化模块
持久化是redis这种内存数据库的拓展功能,如memcachedb对memcached一样。其借鉴却大大削减了OS的vm处理机制(复杂程度较memecached远不在数量级),以够用的理念拿为己用,在某些地方按照需求定制。其思想为一个大的磁盘文件,作为vm文件,bitmap保存所有block的使用情况,redisObject与vmPointer为同型异构体,后者指明value在vm文件中的位置等信息,且对大的value进行lzf压缩解压以减少磁盘IO所带来的性能开销;而Key作为索引永远保存在内存中。
常见的LRU实现有如下几种:
如memcached,有专门的lru list数据结构,保存着数据的LRU信息(存入的时间戳,链表),每次使用会改变这个链表,最终淘汰置换该list末尾的数据。
如Linux内核,分为active和inactive两个list,根据相应的计算经验规则,将页放入相应的list,并对inactive中的page进行再激活或淘汰置换。
而redis没有相应的lru数据结构,其lru机制为:整个redis有一个时钟,每隔一段时间更新一次,每一个数据都会保存它们最近使用时当前的时钟,随机选出dict中几个数据,根据其value的大小和最后更新的系统时钟值,确定其swap的能力,超过某个阈值,则将其更换出去。
Vm的思想,对于redis这种崇尚简洁实效为美的设计来说,多少还是有些复杂,因此作者一直在考虑另外一种实现方式去替代vm的持久化机制,可见
主辅同步模块:redis的弱项,目前只能同到辅,而辅不能到主,有待继续开发,对此模块感兴趣的可以参考mysql的实现。
结语:redis崇尚简洁、实效、暴力的美学,让redis成为kv-db中效率的代表,而所有db的source code中,恐怕很难找到比redis更简单易读的代码了。这很多方面,值得我们设计开发借鉴。