结合源码分析Memcached与Redis实现

怼烎@ 2022-05-22 08:07 122阅读 0赞

[Memcached 与 Redis 实现的对比。][Memcached _ Redis]  
[Redis和Memcached的区别][Redis_Memcached]  
[选redis还是memcache，源码怎么说？][redis_memcache]

# 综述 #

memcache和redis是互联网分层架构中，最常用的kv键值缓存。将常用数据缓存在内存中，加快查询速度，检索数据库服务器的压力非常重要。在选型的时候到底是选择memcache还是redis必须根据实际的应用场景选择。

# 事件网络模型 #

Memcached和Redis都可以通过后台daemon进程的方式运行。都支持TCP、UDP、Unix套接字（仅支持在同一台机器）协议通信。

*  二者不论是谁都使用epoll复用机制。不同的是Redis自己简答封装了事件管理模块，而Memcached使用了Libevent事件驱动库。
 *  Redis通常是单进程单线程模型（RDB后台备份会fork子进程处理备份相关，AOF重写的时候会fork子进程重写；注意AOF直接在主进程中进行，可能会阻塞服务器命令处理）Redis只有一个event loop，是简单的reactor实现。redis中epoll返回的fd就是服务器与客户端连接的socket的fd，但是处理的时候，需要根据这个fd找到具体的客户端的信息，怎么找呢？通常的处理方式就是用红黑树将fd与客户端信息保存起来，通过fd查找，效率是lgn。不过redis比较特殊，redis的客户端的数量上限可以设置，即可以知道同一时刻，redis所打开的fd的上限，而我们知道，进程的fd在同一时刻是不会重复的（fd只有关闭后才能复用），所以redis使用一个数组，将fd作为数组的下标，数组的元素就是客户端的信息，这样，直接通过fd就能定位客户端信息，查找效率是O(1)，还省去了复杂的红黑树的实现。[参考][Link 1]
 *  Memcached是多线程模型，使用master-worker的方式，主线程监听端口，建立连接，然后采用轮询的方式分配给各个工作线程。**分配的方式是将其加入对应线程的连接队列(存储已连接的套接字fd)中，然后往线程管道写命令字`'c'`表明这个已经连接，需要子进程从其连接队列中弹出然后处理。此时子线程epoll中监听到管道可读，并读取出对应的命令，弹出fd。然后加入对应的epoll监听可读事件，至此这个连接交给了当前子线程处理，后续命令到来，会调用其回调函数，并将连接信息的内存指针一并传入回调函数，处理连接。**每个子线程都会是上述的处理方式执行，通过轮询达到负载均衡的效果，对于每个线程可连接的数量是有限的。多线程的优势就是可以充分发挥多核的优势，不过编写程序麻烦一点，memcached里面就有各种锁和条件变量来进行线程同步。[参考][Link 2]

# 内存分配 #

memcached和redis的核心任务都是在内存中操作数据，内存管理自然是核心的内容。

*  memcached使用slab内存池，即预先分配一大块内存，然后接下来分配内存就从内存池中分配，这样可以减少内存分配的次数，提高效率，这也是大部分网络服务器的实现方式，只不过各个内存池的管理方式根据具体情况而不同。
 *  redis没有自己得内存池，而是直接使用时分配，即什么时候需要什么时候分配，内存管理的事交给内核，自己只负责取和释放（redis既是单线程，又没有自己的内存池，是不是感觉实现的太简单了？那是因为它的重点都放在数据库模块了）。不过redis支持使用tcmalloc来替换glibc的malloc，前者是google的产品，比glibc的malloc快。
 *  由于redis没有自己的内存池，所以内存申请和释放的管理就简单很多，直接malloc和free即可，十分方便。而memcached是支持内存池的，所以内存申请是从内存池中获取，而free也是还给内存池，所以需要很多额外的管理操作，实现起来麻烦很多。

# 数据库实现 #

## **1、memcached数据库实现** ##

![这里写图片描述][70]  
item中保存key-value对，value通过柔性数组保存，memcached维护了一个hash表用于快速查找item。hash表使用开链法（与redis一样）解决键的冲突，上图中的`h_next`就是指桶里面的链表的下一个节点。hash表支持扩容（item的数量是桶的数量的1.5以上时扩容），有一个`primary_hashtable`，还有一个`old_hashtable`，其中正常使用`primary_hashtable`，但是扩容的时候，最后将是`old_hashtable = primary_hashtable`。首先`primary_hashtable`设置为新申请的hash表（桶的数量乘以2），然后依次将`old_hashtable`里面的数据往新的hash表里面移动，并用一个变量`expand_bucket`记录以及移动了多少个桶，移动完成后，再free原来的`old_hashtable`即可（redis也是有两个hash表，也是移动，不过不是后台线程完成，而是每次移动一个桶，使用均摊的思想，在同一个线程中完成）。扩容的操作，专门有一个后台扩容的线程来完成，需要扩容的时候，使用条件变量通知它，完成扩容后，它又阻塞等待扩容的条件变量。这样在扩容的时候，查找一个item可能会在`primary_hashtable`和`old_hashtable`的任意一个中，需要根据比较它的桶的位置和`expand_bucket`的大小来比较确定它在哪个表里。

![这里写图片描述][70 1]  
memcached有很多slabclass，**它们管理不同的slab，每一个slab其实是管理chunk的集合，真正的item是在chunk中分配的，一个chunk分配一个item**。一个slab中的chunk的大小一样，不同的slab，chunk的大小按比例递增，需要新申请一个item的时候，根据它的大小来选择chunk，规则是比它大的最小的那个chunk。这样，不同大小的item就分配在不同的slab中，归不同的slabclass管理。 这样的缺点是会有部分内存浪费，因为一个trunk可能比item大，假如分配100B的item的时候，选择112的trunk，但是会有12B的浪费，这部分内存资源没有使用。

slabclass管理slab，一个slabclass有一个slab\_list，可以管理多个slab页，同一个slabclass中的slab的chunk大小都一样。slabclass有一个指针slot，保存了未分配的item已经被free掉的item（不是真的free内存，只是不用了而已），有item不用的时候，就放入slot的头部，这样每次需要在当前slab中分配item的时候，直接取slot取即可，不用管item是未分配过的还是被释放掉的。

**然后，每一个slabclass对应一个链表，有head数组和tail数组，它们分别保存了已分配节点链表的头节点和尾节点**。链表中的节点就是从slabclass所分配出的item内存，新分配的放在头部，链表越往后的item，表示它已经很久没有被使用了。当slabclass的内存不足，需要删除一些过期item的时候，就可以从链表的尾部开始删除，没错，这个链表就是为了实现LRU。光靠它还不行，因为链表的查询是O(n)的，所以定位item的时候，使用hash表所有分配的item已经在hash表中了所以，hash用于查找item，然后使用链表存储同样大小item的最近使用顺序，这也是LRU（(Least recently used）的标准实现方法。

每次需要新分配item的时候，首先找到LRU链表，从尾部往前找，看是否有item已经过期，过期的话，直接就用这个过期的item当做新的item。没有过期的，则需要从slab中分配chunk，如果slab用完了，则需要往slabclass中添加新的slab页了。

## **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 *ptr`指针来指向对象的真正内容。正是由于使用了抽象redis object，使得数据库操作数据时方便很多，全部统一使用redis object对象即可，需要区分对象类型的时候，再根据type来判断。而且正式由于采用了这种面向对象的方法，让redis的代码看起来很像c++代码，其实全是用c写的。

//代表实现值类型的数据结构，因为某个值可以通过多种数据结构实现
    #define OBJ_ENCODING_RAW 0 /* Raw representation 原始表示方式，sds */
    #define OBJ_ENCODING_INT 1 /* Encoded as integer 整型*/
    #define OBJ_ENCODING_HT 2 /* Encoded as hash table 字典*/
    #define OBJ_ENCODING_ZIPMAP 3 /* Encoded as zipmap 不再使用了*/
    #define OBJ_ENCODING_LINKEDLIST 4 /* No longer used: old list encoding. 双端链表，不在使用了 */
    #define OBJ_ENCODING_ZIPLIST 5 /* Encoded as ziplist 压缩表*/
    #define OBJ_ENCODING_INTSET 6 /* Encoded as intset 整数集*/
    #define OBJ_ENCODING_SKIPLIST 7 /* Encoded as skiplist 跳跃表*/
    #define OBJ_ENCODING_EMBSTR 8 /* Embedded sds string encoding embstr编码的sds*/
    #define OBJ_ENCODING_QUICKLIST 9 /* Encoded as linked list of ziplists 由压缩列表组成的双向列表-->快速列表*/
    
    //实际的值类型
    #define OBJ_STRING 0 //字符串对象
    #define OBJ_LIST 1 //列表对象
    #define OBJ_SET 2 //集合对象
    #define OBJ_ZSET 3 //有序集合对象
    #define OBJ_HASH 4 //hash对象
    
    
    //对象结构定义
    typedef struct redisObject {
        unsigned type:4;//何种对象，占4bits，共5种类型
        unsigned encoding:4;//对象通过哪种的编码实现，占4bits，共10种类型
        //实用LRU算法计算相对server.lruclock的LRU时间
        unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or * LFU data (least significant 8 bits frequency * and most significant 16 bits access time). */
        int refcount;//引用计数
        void *ptr;//指向底层数据实现的指针
    } robj;

说到底redis还是一个key-value的数据库，不管它支持多少种数据结构，最终存储的还是以key-value的方式，只不过value可以是string、list、set、zset、hash table等。和memcached一样，所有的key都是string，redis的首要任务就是实现一个string，取名叫sds（simple dynamic string）。key和value的关联通过字典实现（hash表）。

哈希表的具体实现是和mc类似的做法，也是使用开链法来解决冲突，不过里面用到了一些小技巧。比如使用dictType存储函数指针，可以动态配置桶里面元素的操作方法。又比如dictht中保存的sizemask取size（桶的数量）-1，用它与key的hash值做&操作来代替取余运算，加快速度等等。总的来看，dict里面有两个哈希表，每个哈希表的桶里面存储dictEntry链表，dictEntry存储具体的key和value。

一个dict对于两个dictht，是为了扩容（其实还有缩容）。正常的时候，dict只使用`dictht[0]`，当`dictht[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在他的请求中间添加了移动数据的操作。  
有了dict，数据库就好实现了。所有数据读存储在dict中，key存储成dictEntry中的key（string），用void\* 指向一个redis object，它可以是5种类型中的任何一种。如下图，结构构造是这样，不过这个图已经过时了，有一些与redis3.0不符合的地方。  
![这里写图片描述][70 2]  
5中type的对象，每一个都至少有两种底层实现方式。  
**string支持** `REDIS_ENCODING_RAW,REDIS_ENCIDING_INT,REDIS_ENCODING_EMBSTR`。

**list实现** 普通双向链表和压缩链表，压缩链表简单的说，就是将数组改造成链表，连续的空间，然后通过存储字符串的大小信息来模拟链表，相对普通链表来说可以节省空间，不过有副作用，由于是连续的空间，所以改变内存大小的时候，需要重新分配，并且由于保存了字符串的字节大小，所有有可能引起连续更新（具体实现请详细看代码），作者真是有强迫症，为了节约一点内存，何必这么麻烦哦。

**set实现有** dict和intset（全是整数的时候使用它来存储）。set中的dict，每个dictentry中key保存了set中具体的一个元素的值，value则为NULL。

**zset实现有** skiplist和ziplist。skiplist就是跳表，它有接近于红黑树的效率，但是实现起来比红黑树简单很多，所以被采用。在zset中，每个set中的元素都有一个分值score，用它来排序。所以在ziplist中，按照分值大小，先存元素，再存它的score，再存下一个元素，然后score。这样连续存储，所以插入或者删除的时候，都需要重新分配内存。所以当元素超过一定数量，或者某个元素的字符数超过一定数量，redis就会选择使用skiplist来实现zset（如果当前使用的是ziplist，会将这个ziplist中的数据取出，存入一个新的skiplist，然后删除改ziplist，这就是底层实现转换，其余类型的redis object也是可以转换的）。

**hashtable实现** 有dict、ziplist。dict本身就是hashtable的实现，则将dict中，每个dictentry中key保存了key（这是哈希表中的键值对的key），而value则保存了value指向sds，它们都是string。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了。

这样看来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还支持数据持久化，这个下面介绍。

## **3、redis的RDB持久化** ##

## **4、redis的AOF持久化** ##

RDB保存的只是最终的数据库而保存的是一条一条建立数据库的命令。

我们首先来看AOF文件的格式，它里面保存的是一条一条的命令，首先存储命令长度，然后存储命令，具体的分隔符什么的可以自己深入研究，这都不是重点，反正知道AOF文件存储的是redis客户端执行的命令即可。

redis server中有一个`sds aof_buf`，如果AOF持久化打开的话，每个修改数据库的命令都会存入这个`aof_buf`缓冲区，然后每次event loop循环，在server cron中调用`flushaofbuf`，把`aof_buf`中的命令写入aof文件（**其实是write，真正写入的是内核缓冲区**），再清空`aof_buf`，进入下一次loop。这样所有的数据库的变化，都可以通过aof文件中的命令来还原，达到了保存数据库的效果。

需要注意的是，`flushaofbuf`中调用的`write`，它只是把数据写入了内核缓冲区，真正写入文件时内核自己决定的，可能需要延后一段时间。不过redis支持配置，**可以配置每次写入后fsync，则在redis里面调用fsync**，将内核中的数据同步写入文件，这不过这要耗费一次系统调用，耗费时间而已。还可以配置策略为1秒钟`fsync`一次，则redis会开启一个后台线程（所以说redis不是单线程，只是单eventloop而已），这个后台线程会每一秒调用一次`fsync`。RDB的时候为什么没有考虑fsync的事情呢？因为RDB是一次性存储的，不像AOF这样多次存储，RDB的时候调用一次`fsync`也没什么影响，而且使用bg save的时候，子进程会自己退出（exit），这时候exit函数内会冲刷缓冲区，自动就写入了文件中。当AOF文件过大的时候，AOF还支持重写操作。

## **5、redis的事务** ##

Redis支持简单的事务就是把几个命令合并，一次性执行全部命令。对于关系型数据库来说，事务还有回滚机制，即事务命令要么全部执行成功，只要有一条失败就回滚，回到事务执行前的状态。redis不支持回滚，**它的事务只保证命令依次被执行，即使中间一条命令出错也会继续往下执行，所以说它只支持简单的事务**。

事务首先执行multi命令，表示开始事务，然后输入需要执行的命令，最后输入exec执行事务。 redis服务器收到multi命令后，会将对应的client的状态设置为`REDIS_MULTI`，表示client处于事务阶段，并在client的multiState结构体里面保持事务的命令具体信息（当然首先也会检查命令是否能识别，错误的命令不会保存，并立即返回给客户端错误），即命令的个数和具体的各个命令，当收到exec命令后，redis会顺序执行multiState里面保存的命令，然后保存每个命令的返回值，当有命令发生错误的时候，redis不会停止事务，而是保存错误信息，然后继续往下执行，当所有的命令都执行完后，将所有命令的返回值一起返回给客户。redis为什么不支持回滚呢？网上看到的解释出现问题是由于客户程序的问题，所以没必要服务器回滚，同时，不支持回滚，redis服务器的运行高效很多。在我看来，redis的事务不是传统关系型数据库的事务，要求CIAD那么非常严格，或者说redis的事务都不是事务，只是提供了一种方式，**使得客户端可以一次性执行多条命令而已**，就把事务当做普通命令就行了，支持回滚也就没必要了。

## **6、redis的发布和订阅** ##

redis支持频道，即加入一个频道的用户相当于加入了一个群，客户往频道里面发的信息，频道里的所有client都能收到。

## **7、redis的集群** ##

## **8、redis的哨兵** ##

[Memcached _ Redis]: https://cloud.tencent.com/developer/article/1004377
[Redis_Memcached]: https://www.biaodianfu.com/redis-vs-memcached.html
[redis_memcache]: https://mp.weixin.qq.com/s/hOdwK2-7_S7_fi-KVu9_OQ
[Link 1]: https://blog.csdn.net/u010710458/article/details/80644926
[Link 2]: https://blog.csdn.net/u010710458/article/details/80246630
[70]: /images/20220522/53a89741841d4f0896bee3aefba0e252.png
[70 1]: /images/20220522/cb9f4c517269425cb484c3f4cceabff5.png
[70 2]: /images/20220522/33d1ca3c31f74f349e8f1d5658f657cc.png