技术库 > 存储系统

redis设计思想

技术库:tec.5lulu.com

from:tec.5lulu.com

整体模型:单进程单线程事件驱动模式。

Redis在主处理流程中,采用了单进程接受各种client请求并返回结果,整体处理流程采用事件驱动的方式进行。通过其IO复用的方式监听aeEventLoop事件,在事件处理的过程中,这种模式对处理函数的要求:进行一次事件处理需要尽可能地快。因此会有以下几种处理方法:

1.对于非长时间处理事件,直接处理。如set命令;

2.对于需要长时间处理的事件,分步处理,直至完成。如rehash过程,在单次事件处理过程中,每次只移动一个桶。

3.对于阻塞函数,如从磁盘读取vm数据等,采用异步的模式。从磁盘load数据,是一个较为耗时的操作,如处理函数中直接读取数据,将会阻塞整体的单线程处理其他的client请求。

多线程开发的复杂性是我们所清楚的。采用单进程单线程的模式,可以避免很多复杂性,另外事务性操作,无须额外加锁,大大降低了开发难度。

IO复用

RedisIO复用层,可以看作是一个tiny libevent,其实现只有四个文件,ae.c ae_select.c ae_kqueue.cae_epoll.c。一目了然,ae是事件监听总的interfaceselectkquequeepoll是三种可选的IO复用方式。小而够用,简洁高效,充分体现了redis的设计理念。Redis DefaultselectC10K max

事件监听

单线程事件驱动模型中,往往会遇到两种任务,定时处理任务及事件触发任务,于是会有如下问题:事件触发任务在无任务时,会处于阻塞状态;定时任务要求定时处理,于是往往会有如下两种处理方式:

1. 如果定时任务时间间隔为t,一般设IO复用层的超时时间为t/10,这样可以保证定时任务得到及时处理,在调用所有cron任务时,会做间隔时间判断。

2. 计算当前事件与最近的定时任务开始时间的间隔,设置IO复用超时时间为该事件。这样定时任务也能得到及时处理。

注意:以上定时任务的处理时间,都为估约时间,非精确时间。前一种方式每轮计算量少,当容易引起空转,后一种计算量大,但减少了空转次数。Redis采用的是后一种方式。

这里也许有人会问:为什么不采用sigactionsetitimer等设置精确时钟,以后再也不用为cron事件做额外处理。原因如下:

定时时钟,往往会让进程陷入内核态,内核软中断往往会打破用户态一个函数的完整性,因此会破坏相关的状态转移;另外加入软中断的程序,将可能为程序带来不可避免地复杂性。

以曾经做过一个项目的一段挫折经历为例:

一个电话多路呼转的项目,采用的是单线程异步事件驱动模型,每次定时任务有个让空闲通道“挂机”的任务。先前采用预制的驱动时钟,时钟信号为实时信号(信号宏值取32-64之间的一个数),信号在sigqueue中排队,这样如果任务阻塞返回后,会瞬间抛出大量时钟事件,造成空闲通道多次挂机失败。后改用setitimer设置系统时钟,软中断打断了用户态的一次mutex_lockmutex_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,好比常见的索引数组,不同于linked list,其保存在一个数组中,且用value-header保存链接项及其本身的偏移、长度,encoding等,用于遍历list。在需求上,encoding保证多种不同的数据,可以保存在同一个list中,如int16int32str等。

zsethash dict + skip list。常见的有序setrb tree为基础。而在整个redis中,我们很难发现任何复杂数据结构tree的踪影。Redishash dict保证散列查找的效率,以跳表结构保证有序及范围查找需求的快速满足,范围查找抛弃了rb treeb+-* tree,也体现了其不想复杂的简洁美学。

......

整个redis中,没有任何专门的内存池结构。所有内存分配,不像stlniginx内存分配都有其内存池机构分配,redis没有!Redis全是size+malloczmalloc分配,其常见的小对象,在intsetziplist数据结构地以数组方式申请,并不断用realloc的方式resize,间接地体现了内存池的思想,但却没有实现一个内存池管理模块,作者简单暴力的美学,体现得淋漓尽致。

持久化模块

持久化redis这种内存数据库的拓展功能,如memcachedbmemcached一样。其借鉴却大大削减了OSvm处理机制(复杂程度较memecached远不在数量级),以够用的理念拿为己用,在某些地方按照需求定制。其思想为一个大的磁盘文件,作为vm文件,bitmap保存所有block的使用情况,redisObjectvmPointer为同型异构体,后者指明valuevm文件中的位置等信息,且对大的value进行lzf压缩解压以减少磁盘IO所带来的性能开销;而Key作为索引永远保存在内存中。

常见的LRU实现有如下几种:

memcached,有专门的lru list数据结构,保存着数据的LRU信息(存入的时间戳,链表),每次使用会改变这个链表,最终淘汰置换该list末尾的数据。

Linux内核,分为activeinactive两个list,根据相应的计算经验规则,将页放入相应的list,并对inactive中的page进行再激活或淘汰置换。

redis没有相应的lru数据结构,其lru机制为:整个redis有一个时钟,每隔一段时间更新一次,每一个数据都会保存它们最近使用时当前的时钟,随机选出dict中几个数据,根据其value的大小和最后更新的系统时钟值,确定其swap的能力,超过某个阈值,则将其更换出去。

Vm的思想,对于redis这种崇尚简洁实效为美的设计来说,多少还是有些复杂,因此作者一直在考虑另外一种实现方式去替代vm持久化机制,可见

http://groups.google.com/group/redis-db/browse_thread/thread/d444bc786689bde9/1565b7570ffbb268?show_docid=1565b7570ffbb268#

主辅同步模块:redis的弱项,目前只能同到辅,而辅不能到主,有待继续开发。

结语:redis崇尚简洁、实效、暴力的美学,让redis成为kv-db中效率的代表,而所有dbsource code中,恐怕很难找到比redis更简单易读的代码了。

redis设计思想


标签: 时间 事件本文链接 http://tec.5lulu.com/detail/109ktn1h941aw8yfd.html

我来评分 :6.5
1

转载注明:转自5lulu技术库

本站遵循:署名-非商业性使用-禁止演绎 3.0 共享协议

www.5lulu.com