e-works数字化企业网  »  文章频道  »  基础信息化  »  终端和服务器

内存缓存系统memcached与redis实现的对比

2018/1/3    来源:Java从入门到大神    作者:佚名      
关键字:内存缓存  memcached  
memcached和redis,作为近些年最常用的缓存服务器,相信大家对它们再熟悉不过了。前两年还在学校时,我曾经读过它们的主要源码,如今写篇笔记从个人角度简单对比一下它们的实现方式,权当做复习,有理解错误之处,欢迎指正。

    以上就是memcached如何实现一个key-value的数据库的介绍。
 
    2. redis数据库实现
 
    首先redis数据库的功能强大一些,因为不像memcached只支持保存字符串,redis支持string, list, set,sorted set,hash table 5种数据结构。例如存储一个人的信息就可以使用hash table,用人的名字做key,然后name super, age 24, 通过key 和 name,就可以取到名字super,或者通过key和age,就可以取到年龄24。这样,当只需要取得age的时候,不需要把人的整个信息取回来,然后从里面找age,直接获取age即可,高效方便。
 
    为了实现这些数据结构,redis定义了抽象的对象redis object,如下图。每一个对象有类型,一共5种:字符串,链表,集合,有序集合,哈希表。 同时,为了提高效率,redis为每种类型准备了多种实现方式,根据特定的场景来选择合适的实现方式,encoding就是表示对象的实现方式的。然后还有记录了对象的lru,即上次被访问的时间,同时在redis 服务器中会记录一个当前的时间(近似值,因为这个时间只是每隔一定时间,服务器进行自动维护的时候才更新),它们两个只差就可以计算出对象多久没有被访问了。 然后redis object中还有引用计数,这是为了共享对象,然后确定对象的删除时间用的。最后使用一个void*指针来指向对象的真正内容。正式由于使用了抽象redis object,使得数据库操作数据时方便很多,全部统一使用redis object对象即可,需要区分对象类型的时候,再根据type来判断。而且正式由于采用了这种面向对象的方法,让redis的代码看起来很像c++代码,其实全是用c写的。
 
内存缓存系统memcached与redis实现的对比
 
    说到底redis还是一个key-value的数据库,不管它支持多少种数据结构,最终存储的还是以key-value的方式,只不过value可以是链表,set,sorted set,hash table等。和memcached一样,所有的key都是string,而set,sorted set,hash table等具体存储的时候也用到了string。 而c没有现成的string,所以redis的首要任务就是实现一个string,取名叫sds(simple dynamic string),如下的代码, 非常简单的一个结构体,len存储改string的内存总长度,free表示还有多少字节没有使用,而buf存储具体的数据,显然len-free就是目前字符串的长度。
 
内存缓存系统memcached与redis实现的对比
 
    字符串解决了,所有的key都存成sds就行了,那么key和value怎么关联呢?key-value的格式在脚本语言中很好处理,直接使用字典即可,C没有字典,怎么办呢?自己写一个呗(redis十分热衷于造轮子)。看下面的代码,privdata存额外信息,用的很少,至少我们发现。 dictht是具体的哈希表,一个dict对应两张哈希表,这是为了扩容(包括rehashidx也是为了扩容)。dictType存储了哈希表的属性。redis还为dict实现了迭代器(所以说看起来像c++代码)。
  
    哈希表的具体实现是和mc类似的做法,也是使用开链法来解决冲突,不过里面用到了一些小技巧。比如使用dictType存储函数指针,可以动态配置桶里面元素的操作方法。又比如dictht中保存的sizemask取size(桶的数量)-1,用它与key做&操作来代替取余运算,加快速度等等。总的来看,dict里面有两个哈希表,每个哈希表的桶里面存储dictEntry链表,dictEntry存储具体的key和value。
 
    前面说过,一个dict对于两个dictht,是为了扩容(其实还有缩容)。正常的时候,dict只使用dictht[0],当dict[0]中已有entry的数量与桶的数量达到一定的比例后,就会触发扩容和缩容操作,我们统称为rehash,这时,为dictht[1]申请rehash后的大小的内存,然后把dictht[0]里的数据往dictht[1]里面移动,并用rehashidx记录当前已经移动万的桶的数量,当所有桶都移完后,rehash完成,这时将dictht[1]变成dictht[0], 将原来的dictht[0]变成dictht[1],并变为null即可。不同于memcached,这里不用开一个后台线程来做,而是就在event loop中完成,并且rehash不是一次性完成,而是分成多次,每次用户操作dict之前,redis移动一个桶的数据,直到rehash完成。这样就把移动分成多个小移动完成,把rehash的时间开销均分到用户每个操作上,这样避免了用户一个请求导致rehash的时候,需要等待很长时间,直到rehash完成才有返回的情况。不过在rehash期间,每个操作都变慢了点,而且用户还不知道redis在他的请求中间添加了移动数据的操作,感觉redis太贱了 ??
 
    typedef struct dict {
    dictType *type;  // 哈希表的相关属性
    void *privdata;  // 额外信息
    dictht ht[2];  // 两张哈希表,分主和副,用于扩容
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */ // 记录当前数据迁移的位置,在扩容的时候用的
    int iterators; /* number of iterators currently running */  // 目前存在的迭代器的数量
    } dict;
 
    typedef struct dictht {
    dictEntry **table;  // dictEntry是item,多个item组成hash桶里面的链表,table则是多个链表头指针组成的数组的指针
    unsigned long size;  // 这个就是桶的数量
    // sizemask取size - 1, 然后一个数据来的时候,通过计算出的hashkey, 让hashkey & sizemask来确定它要放的桶的位置
    // 当size取2^n的时候,sizemask就是1...111,这样就和hashkey % size有一样的效果,但是使用&会快很多。这就是原因
    unsigned long sizemask;
    unsigned long used;    // 已经数值的dictEntry数量
    } dictht;
 
    typedef struct dictType {
    unsigned int (*hashFunction)(const void *key);   // hash的方法
    void *(*keyDup)(void *privdata, const void *key);  // key的复制方法
    void *(*valDup)(void *privdata, const void *obj);  // value的复制方法
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);  // key之间的比较
    void (*keyDestructor)(void *privdata, void *key);  // key的析构
    void (*valDestructor)(void *privdata, void *obj);  // value的析构
    } dictType;
 
    typedef struct dictEntry {
    void *key;
    union {
       void *val;
       uint64_t u64;
       int64_t s64;
    } v;
    struct dictEntry *next;
    } dictEntry;
 
    有了dict,数据库就好实现了。所有数据读存储在dict中,key存储成dictEntry中的key(string),用void* 指向一个redis object,它可以是5种类型中的任何一种。如下图,结构构造是这样,不过这个图已经过时了,有一些与redis3.0不符合的地方。
 
内存缓存系统memcached与redis实现的对比
 
    5中type的对象,每一个都至少有两种底层实现方式。string有3种:REDIS_ENCODING_RAW, REDIS_ENCIDING_INT, REDIS_ENCODING_EMBSTR, list有:普通双向链表和压缩链表,压缩链表简单的说,就是讲数组改造成链表,连续的空间,然后通过存储字符串的大小信息来模拟链表,相对普通链表来说可以节省空间,不过有副作用,由于是连续的空间,所以改变内存大小的时候,需要重新分配,并且由于保存了字符串的字节大小,所有有可能引起连续更新(具体实现请详细看代码)。set有dict和intset(全是整数的时候使用它来存储), sorted set有:skiplist和ziplist, hashtable实现有压缩列表和dict和ziplist。skiplist就是跳表,它有接近于红黑树的效率,但是实现起来比红黑树简单很多,所以被采用(奇怪,这里又不造轮子了,难道因为这个轮子有点难?)。 hash table可以使用dict实现,则改dict中,每个dictentry中key保存了key(这是哈希表中的键值对的key),而value则保存了value,它们都是string。 而set中的dict,每个dictentry中key保存了set中具体的一个元素的值,value则为null。图中的zset(有序集合)有误,zset使用skiplist和ziplist实现,首先skiplist很好理解,就把它当做红黑树的替代品就行,和红黑树一样,它也可以排序。怎么用ziplist存储zset呢?首先在zset中,每个set中的元素都有一个分值score,用它来排序。所以在ziplist中,按照分值大小,先存元素,再存它的score,再存下一个元素,然后score。这样连续存储,所以插入或者删除的时候,都需要重新分配内存。所以当元素超过一定数量,或者某个元素的字符数超过一定数量,redis就会选择使用skiplist来实现zset(如果当前使用的是ziplist,会将这个ziplist中的数据取出,存入一个新的skiplist,然后删除改ziplist,这就是底层实现转换,其余类型的redis object也是可以转换的)。 另外,ziplist如何实现hashtable呢?其实也很简单,就是存储一个key,存储一个value,再存储一个key,再存储一个value。还是顺序存储,与zset实现类似,所以当元素超过一定数量,或者某个元素的字符数超过一定数量时,就会转换成hashtable来实现。各种底层实现方式是可以转换的,redis可以根据情况选择最合适的实现方式,这也是这样使用类似面向对象的实现方式的好处。
 
    需要指出的是,使用skiplist来实现zset的时候,其实还用了一个dict,这个dict存储一样的键值对。为什么呢?因为skiplist的查找只是lgn的(可能变成n),而dict可以到O(1), 所以使用一个dict来加速查找,由于skiplist和dict可以指向同一个redis object,所以不会浪费太多内存。另外使用ziplist实现zset的时候,为什么不用dict来加速查找呢?因为ziplist支持的元素个数很少(个数多时就转换成skiplist了),顺序遍历也很快,所以不用dict了。
 
    这样看来,上面的dict,dictType,dictHt,dictEntry,redis object都是很有考量的,它们配合实现了一个具有面向对象色彩的灵活、高效数据库。不得不说,redis数据库的设计还是很厉害的。
 
    与memcached不同的是,redis的数据库不止一个,默认就有16个,编号0-15。客户可以选择使用哪一个数据库,默认使用0号数据库。 不同的数据库数据不共享,即在不同的数据库中可以存在同样的key,但是在同一个数据库中,key必须是唯一的。
 
    redis也支持expire time的设置,我们看上面的redis object,里面没有保存expire的字段,那redis怎么记录数据的expire time呢? redis是为每个数据库又增加了一个dict,这个dict叫expire dict,它里面的dict entry里面的key就是数对的key,而value全是数据为64位int的redis object,这个int就是expire time。这样,判断一个key是否过期的时候,去expire dict里面找到它,取出expire time比对当前时间即可。为什么这样做呢? 因为并不是所有的key都会设置过期时间,所以,对于不设置expire time的key来说,保存一个expire time会浪费空间,而是用expire dict来单独保存的话,可以根据需要灵活使用内存(检测到key过期时,会把它从expire dict中删除)。
 
    redis的expire 机制是怎样的呢? 与memcahed类似,redis也是惰性删除,即要用到数据时,先检查key是否过期,过期则删除,然后返回错误。单纯的靠惰性删除,上面说过可能会导致内存浪费,所以redis也有补充方案,redis里面有个定时执行的函数,叫servercron,它是维护服务器的函数,在它里面,会对过期数据进行删除,注意不是全删,而是在一定的时间内,对每个数据库的expire dict里面的数据随机选取出来,如果过期,则删除,否则再选,直到规定的时间到。即随机选取过期的数据删除,这个操作的时间分两种,一种较长,一种较短,一般执行短时间的删除,每隔一定的时间,执行一次长时间的删除。这样可以有效的缓解光采用惰性删除而导致的内存浪费问题。
 
    以上就是redis的数据的实现,与memcached不同,redis还支持数据持久化,这个下面介绍。
 
    4.redis数据库持久化
 
    redis和memcached的最大不同,就是redis支持数据持久化,这也是很多人选择使用redis而不是memcached的最大原因。 redis的持久化,分为两种策略,用户可以配置使用不同的策略。
 
    4.1 RDB持久化
 
    用户执行save或者bgsave的时候,就会触发RDB持久化操作。RDB持久化操作的核心思想就是把数据库原封不动的保存在文件里。
 
    那如何存储呢?如下图, 首先存储一个REDIS字符串,起到验证的作用,表示是RDB文件,然后保存redis的版本信息,然后是具体的数据库,然后存储结束符EOF,最后用检验和。关键就是databases,看它的名字也知道,它存储了多个数据库,数据库按照编号顺序存储,0号数据库存储完了,才轮到1,然后是2, 一直到最后一个数据库。
 
内存缓存系统memcached与redis实现的对比
 
    每一个数据库存储方式如下,首先一个1字节的常量SELECTDB,表示切换db了,然后下一个接上数据库的编号,它的长度是可变的,然后接下来就是具体的key-value对的数据了。
 
内存缓存系统memcached与redis实现的对比
 
内存缓存系统memcached与redis实现的对比
 
    由上面的代码也可以看出,存储的时候,先检查expire time,如果已经过期,不存就行了,否则,则将expire time存下来,注意,及时是存储expire time,也是先存储它的类型为REDIS_RDB_OPCODE_EXPIRETIME_MS,然后再存储具体过期时间。接下来存储真正的key-value对,首先存储value的类型,然后存储key(它按照字符串存储),然后存储value,如下图。

责任编辑:李欢
本文为授权转载文章,任何人未经原授权方同意,不得复制、转载、摘编等任何方式进行使用,e-works不承担由此而产生的任何法律责任! 如有异议请及时告之,以便进行及时处理。联系方式:editor@e-works.net.cn tel:027-87592219/20/21。
兴趣阅读
相关资料
e-works
官方微信
掌上
信息化
编辑推荐
新闻推荐
博客推荐
视频推荐