共计 19776 个字符，预计需要花费 50 分钟才能阅读完成。
| 导读 | memcached 和 redis，作为近些年最常用的缓存服务器，相信大家对它们再熟悉不过了。前两年还在学校时，我曾经读过它们的主要源码，如今写篇笔记从个人角度简单对比一下它们的实现方式，权当做复习，有理解错误之处，欢迎指正。 |
读一个软件的源码，首先要弄懂软件是用作干什么的，那 memcached 和 redis 是干啥的？众所周知，数据一般会放在数据库中，但是查询数据会相对比较慢，特别是用户很多时，频繁的查询，需要耗费大量的时间。怎么办呢？数据放在哪里查询快？那肯定是内存中。memcached 和 redis 就是将数据存储在内存中，按照 key-value 的方式查询，可以大幅度提高效率。所以一般它们都用做缓存服务器，缓存常用的数据，需要查询的时候，直接从它们那儿获取，减少查询数据库的次数，提高查询效率。
memcached 和 redis 怎么提供服务呢？它们是独立的进程，需要的话，还可以让他们变成 daemon 进程，所以我们的用户进程要使用 memcached 和 redis 的服务的话，就需要进程间通信了。考虑到用户进程和 memcached 和 redis 不一定在同一台机器上，所以还需要支持网络间通信。因此，memcached 和 redis 自己本身就是网络服务器，用户进程通过与他们通过网络来传输数据，显然最简单和最常用的就是使用 tcp 连接了。另外，memcached 和 redis 都支持 udp 协议。而且当用户进程和 memcached 和 redis 在同一机器时，还可以使用 unix 域套接字通信。
下面开始讲他们具体是怎么实现的了。首先来看一下它们的事件模型。
自从 epoll 出来以后，几乎所有的网络服务器全都抛弃 select 和 poll，换成了 epoll。redis 也一样，只不多它还提供对 select 和 poll 的支持，可以自己配置使用哪一个，但是一般都是用 epoll。另外针对 BSD，还支持使用 kqueue。而 memcached 是基于 libevent 的，不过 libevent 底层也是使用 epoll 的，所以可以认为它们都是使用 epoll。epoll 的特性这里就不介绍了，网上介绍文章很多。
它们都使用 epoll 来做事件循环，不过 redis 是单线程的服务器（redis 也是多线程的，只不过除了主线程以外，其他线程没有 event loop，只是会进行一些后台存储工作），而 memcached 是多线程的。redis 的事件模型很简单，只有一个 event loop，是简单的 reactor 实现。不过 redis 事件模型中有一个亮点，我们知道 epoll 是针对 fd 的，它返回的就绪事件也是只有 fd，redis 里面的 fd 就是服务器与客户端连接的 socket 的 fd，但是处理的时候，需要根据这个 fd 找到具体的客户端的信息，怎么找呢？通常的处理方式就是用红黑树将 fd 与客户端信息保存起来，通过 fd 查找，效率是 lgn。
不过 redis 比较特殊，redis 的客户端的数量上限可以设置，即可以知道同一时刻，redis 所打开的 fd 的上限，而我们知道，进程的 fd 在同一时刻是不会重复的（fd 只有关闭后才能复用），所以 redis 使用一个数组，将 fd 作为数组的下标，数组的元素就是客户端的信息，这样，直接通过 fd 就能定位客户端信息，查找效率是 O(1)，还省去了复杂的红黑树的实现（我曾经用 c 写一个网络服务器，就因为要保持 fd 和 connect 对应关系，不想自己写红黑树，然后用了 STL 里面的 set，导致项目变成了 c ++ 的，最后项目使用 g ++ 编译，这事我不说谁知道？）。显然这种方式只能针对 connection 数量上限已确定，并且不是太大的网络服务器，像 nginx 这种 http 服务器就不适用，nginx 就是自己写了红黑树。
而 memcached 是多线程的，使用 master-worker 的方式，主线程监听端口，建立连接，然后顺序分配给各个工作线程。每一个从线程都有一个 event loop，它们服务不同的客户端。master 线程和 worker 线程之间使用管道通信，每一个工作线程都会创建一个管道，然后保存写端和读端，并且将读端加入 event loop，监听可读事件。同时，每个从线程都有一个就绪连接队列，主线程连接连接后，将连接的 item 放入这个队列，然后往该线程的管道的写端写入一个 connect 命令，这样 event loop 中加入的管道读端就会就绪，从线程读取命令，解析命令发现是有连接，然后就会去自己的就绪队列中获取连接，并进行处理。多线程的优势就是可以充分发挥多核的优势，不过编写程序麻烦一点，memcached 里面就有各种锁和条件变量来进行线程同步。
memcached 和 redis 的核心任务都是在内存中操作数据，内存管理自然是核心的内容。
首先看看他们的内存分配方式。memcached 是有自己得内存池的，即预先分配一大块内存，然后接下来分配内存就从内存池中分配，这样可以减少内存分配的次数，提高效率，这也是大部分网络服务器的实现方式，只不过各个内存池的管理方式根据具体情况而不同。而 redis 没有自己得内存池，而是直接使用时分配，即什么时候需要什么时候分配，内存管理的事交给内核，自己只负责取和释放（redis 既是单线程，又没有自己的内存池，是不是感觉实现的太简单了？那是因为它的重点都放在数据库模块了）。不过 redis 支持使用 tcmalloc 来替换 glibc 的 malloc，前者是 google 的产品，比 glibc 的 malloc 快。
由于 redis 没有自己的内存池，所以内存申请和释放的管理就简单很多，直接 malloc 和 free 即可，十分方便。而 memcached 是支持内存池的，所以内存申请是从内存池中获取，而 free 也是还给内存池，所以需要很多额外的管理操作，实现起来麻烦很多，具体的会在后面 memcached 的 slab 机制讲解中分析。
接下来看看他们的最核心内容，各自数据库的实现。
memcached 只支持 key-value，即只能一个 key 对于一个 value。它的数据在内存中也是这样以 key-value 对的方式存储，它使用 slab 机制。
首先看 memcached 是如何存储数据的，即存储 key-value 对。如下图，每一个 key-value 对都存储在一个 item 结构中，包含了相关的属性和 key 和 value 的值。
item 是保存 key-value 对的，当 item 多的时候，怎么查找特定的 item 是个问题。所以 memcached 维护了一个 hash 表，它用于快速查找 item。hash 表适用开链法（与 redis 一样）解决键的冲突，每一个 hash 表的桶里面存储了一个链表，链表节点就是 item 的指针，如上图中的 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 的大小来比较确定它在哪个表里。
item 是从哪里分配的呢？从 slab 中。如下图，memcached 有很多 slabclass，它们管理 slab，每一个 slab 其实是 trunk 的集合，真正的 item 是在 trunk 中分配的，一个 trunk 分配一个 item。一个 slab 中的 trunk 的大小一样，不同的 slab，trunk 的大小按比例递增，需要新申请一个 item 的时候，根据它的大小来选择 trunk，规则是比它大的最小的那个 trunk。这样，不同大小的 item 就分配在不同的 slab 中，归不同的 slabclass 管理。这样的缺点是会有部分内存浪费，因为一个 trunk 可能比 item 大，如图 2，分配 100B 的 item 的时候，选择 112 的 trunk，但是会有 12B 的浪费，这部分内存资源没有使用。
如上图，整个构造就是这样，slabclass 管理 slab，一个 slabclass 有一个 slab_list，可以管理多个 slab，同一个 slabclass 中的 slab 的 trunk 大小都一样。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 的标准实现方法。
每次需要新分配 item 的时候，找到 slabclass 对于的链表，从尾部往前找，看 item 是否已经过期，过期的话，直接就用这个过期的 item 当做新的 item。没有过期的，则需要从 slab 中分配 trunk，如果 slab 用完了，则需要往 slabclass 中添加 slab 了。
memcached 支持设置过期时间，即 expire time，但是内部并不定期检查数据是否过期，而是客户进程使用该数据的时候，memcached 会检查 expire time，如果过期，直接返回错误。这样的优点是，不需要额外的 cpu 来进行 expire time 的检查，缺点是有可能过期数据很久不被使用，则一直没有被释放，占用内存。
memcached 是多线程的，而且只维护了一个数据库，所以可能有多个客户进程操作同一个数据，这就有可能产生问题。比如，A 已经把数据更改了，然后 B 也更改了改数据，那么 A 的操作就被覆盖了，而可能 A 不知道，A 任务数据现在的状态时他改完后的那个值，这样就可能产生问题。为了解决这个问题，memcached 使用了 CAS 协议，简单说就是 item 保存一个 64 位的 unsigned int 值，标记数据的版本，每更新一次（数据值有修改），版本号增加，然后每次对数据进行更改操作，需要比对客户进程传来的版本号和服务器这边 item 的版本号是否一致，一致则可进行更改操作，否则提示脏数据。
以上就是 memcached 如何实现一个 key-value 的数据库的介绍。
首先 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 写的。
//#define REDIS_STRING 0 // 字符串类型
//#define REDIS_LIST 1 // 链表类型
//#define REDIS_SET 2 // 集合类型 (无序的)，可以求差集，并集等
//#define REDIS_ZSET 3 // 有序的集合类型
//#define REDIS_HASH 4 // 哈希类型
//#define REDIS_ENCODING_RAW 0 /* Raw representation */ //raw 未加工
//#define REDIS_ENCODING_INT 1 /* Encoded as integer */
//#define REDIS_ENCODING_HT 2 /* Encoded as hash table */
//#define REDIS_ENCODING_ZIPMAP 3 /* Encoded as zipmap */
//#define REDIS_ENCODING_LINKEDLIST 4 /* Encoded as regular linked list */
//#define REDIS_ENCODING_ZIPLIST 5 /* Encoded as ziplist */
//#define REDIS_ENCODING_INTSET 6 /* Encoded as intset */
//#define REDIS_ENCODING_SKIPLIST 7 /* Encoded as skiplist */
//#define REDIS_ENCODING_EMBSTR 8 /* Embedded sds
string encoding */
typedef struct redisObject {unsigned type:4; // 对象的类型，包括 /* Object types */
unsigned encoding:4; // 底部为了节省空间，一种 type 的数据，
// 可 以采用不同的存储方式
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount; // 引用计数
void *ptr;
} robj;说到底 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 就是目前字符串的长度。
struct sdshdr {int len;
int free;
char buf[];};字符串解决了，所有的 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 太贱了 :-D
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 不符合的地方。
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 还支持数据持久化，这个下面介绍。
redis 和 memcached 的最大不同，就是 redis 支持数据持久化，这也是很多人选择使用 redis 而不是 memcached 的最大原因。redis 的持久化，分为两种策略，用户可以配置使用不同的策略。
3.1 RDB 持久化
用户执行 save 或者 bgsave 的时候，就会触发 RDB 持久化操作。RDB 持久化操作的核心思想就是把数据库原封不动的保存在文件里。
那如何存储呢？如下图，首先存储一个 REDIS 字符串，起到验证的作用，表示是 RDB 文件，然后保存 redis 的版本信息，然后是具体的数据库，然后存储结束符 EOF，最后用检验和。关键就是 databases，看它的名字也知道，它存储了多个数据库，数据库按照编号顺序存储，0 号数据库存储完了，才轮到 1，然后是 2, 一直到最后一个数据库。
每一个数据库存储方式如下，首先一个 1 字节的常量 SELECTDB，表示切换 db 了，然后下一个接上数据库的编号，它的长度是可变的，然后接下来就是具体的 key-value 对的数据了。
int rdbSaveKeyValuePair(rio *rdb, robj *key, robj *val,
long long expiretime, long long now)
{/* Save the expire time */
if (expiretime != -1) {/* If this key is already expired skip it */
if (expiretime < now) return 0;
if (rdbSaveType(rdb,REDIS_RDB_OPCODE_EXPIRETIME_MS) == -1) return -1;
if (rdbSaveMillisecondTime(rdb,expiretime) == -1) return -1;
}
/* Save type, key, value */
if (rdbSaveObjectType(rdb,val) == -1) return -1;
if (rdbSaveStringObject(rdb,key) == -1) return -1;
if (rdbSaveObject(rdb,val) == -1) return -1;
return 1;
} 由上面的代码也可以看出，存储的时候，先检查 expire time，如果已经过期，不存就行了，否则，则将 expire time 存下来，注意，及时是存储 expire time，也是先存储它的类型为 REDIS_RDB_OPCODE_EXPIRETIME_MS，然后再存储具体过期时间。接下来存储真正的 key-value 对，首先存储 value 的类型，然后存储 key（它按照字符串存储），然后存储 value，如下图。
在 rdbsaveobject 中，会根据 val 的不同类型，按照不同的方式存储，不过从根本上来看，最终都是转换成字符串存储，比如 val 是一个 linklist，那么先存储整个 list 的字节数，然后遍历这个 list，把数据取出来，依次按照 string 写入文件。对于 hash table，也是先计算字节数，然后依次取出 hash table 中的 dictEntry，按照 string 的方式存储它的 key 和 value，然后存储下一个 dictEntry。总之，RDB 的存储方式，对一个 key-value 对，会先存储 expire time（如果有的话），然后是 value 的类型，然后存储 key（字符串方式），然后根据 value 的类型和底层实现方式，将 value 转换成字符串存储。这里面为了实现数据压缩，以及能够根据文件恢复数据，redis 使用了很多编码的技巧，有些我也没太看懂，不过关键还是要理解思想，不要在意这些细节。
保存了 RDB 文件，当 redis 再启动的时候，就根据 RDB 文件来恢复数据库。由于以及在 RDB 文件中保存了数据库的号码，以及它包含的 key-value 对，以及每个 key-value 对中 value 的具体类型，实现方式，和数据，redis 只要顺序读取文件，然后恢复 object 即可。由于保存了 expire time，发现当前的时间已经比 expire time 大了，即数据已经超时了，则不恢复这个 key-value 对即可。
保存 RDB 文件是一个很巨大的工程，所以 redis 还提供后台保存的机制。即执行 bgsave 的时候，redis fork 出一个子进程，让子进程来执行保存的工作，而父进程继续提供 redis 正常的数据库服务。由于子进程复制了父进程的地址空间，即子进程拥有父进程 fork 时的数据库，子进程执行 save 的操作，把它从父进程那儿继承来的数据库写入一个 temp 文件即可。在子进程复制期间，redis 会记录数据库的修改次数（dirty）。当子进程完成时，发送给父进程 SIGUSR1 信号，父进程捕捉到这个信号，就知道子进程完成了复制，然后父进程将子进程保存的 temp 文件改名为真正的 rdb 文件（即真正保存成功了才改成目标文件，这才是保险的做法）。然后记录下这一次 save 的结束时间。
这里有一个问题，在子进程保存期间，父进程的数据库已经被修改了，而父进程只是记录了修改的次数（dirty），被没有进行修正操作。似乎使得 RDB 保存的不是实时的数据库，有点不太高大上的样子。不过后面要介绍的 AOF 持久化，就解决了这个问题。
除了客户执行 sava 或者 bgsave 命令，还可以配置 RDB 保存条件。即在配置文件中配置，在 t 时间内，数据库被修改了 dirty 次，则进行后台保存。redis 在 serve cron 的时候，会根据 dirty 数目和上次保存的时间，来判断是否符合条件，符合条件的话，就进行 bg save，注意，任意时刻只能有一个子进程来进行后台保存，因为保存是个很费 io 的操作，多个进程大量 io 效率不行，而且不好管理。
3.2 AOF 持久化
首先想一个问题，保存数据库一定需要像 RDB 那样把数据库里面的所有数据保存下来么？有没有别的方法？
RDB 保存的只是最终的数据库，它是一个结果。结果是怎么来的？是通过用户的各个命令建立起来的，所以可以不保存结果，而只保存建立这个结果的命令。redis 的 AOF 就是这个思想，它不同 RDB 保存 db 的数据，它保存的是一条一条建立数据库的命令。
我们首先来看 AOF 文件的格式，它里面保存的是一条一条的命令，首先存储命令长度，然后存储命令，具体的分隔符什么的可以自己深入研究，这都不是重点，反正知道 AOF 文件存储的是 redis 客户端执行的命令即可。
redis server 中有一个 sds aof_buf, 如果 aof 持久化打开的话，每个修改数据库的命令都会存入这个 aof_buf（保存的是 aof 文件中命令格式的字符串），然后 event loop 没循环一次，在 server cron 中调用 flushaofbuf，把 aof_buf 中的命令写入 aof 文件（其实是 write，真正写入的是内核缓冲区），再清空 aof_buf，进入下一次 loop。这样所有的数据库的变化，都可以通过 aof 文件中的命令来还原，达到了保存数据库的效果。
需要注意的是，flushaofbuf 中调用的 write，它只是把数据写入了内核缓冲区，真正写入文件时内核自己决定的，可能需要延后一段时间。不过 redis 支持配置，可以配置每次写入后 sync，则在 redis 里面调用 sync，将内核中的数据写入文件，这不过这要耗费一次系统调用，耗费时间而已。还可以配置策略为 1 秒钟 sync 一次，则 redis 会开启一个后台线程（所以说 redis 不是单线程，只是单 eventloop 而已），这个后台线程会每一秒调用一次 sync。这里要问了，RDB 的时候为什么没有考虑 sync 的事情呢？因为 RDB 是一次性存储的，不像 AOF 这样多次存储，RDB 的时候调用一次 sync 也没什么影响，而且使用 bg save 的时候，子进程会自己退出（exit），这时候 exit 函数内会冲刷缓冲区，自动就写入了文件中。
再来看，如果不想使用 aof_buf 保存每次的修改命令，也可以使用 aof 持久化。redis 提供 aof_rewrite，即根据现有的数据库生成命令，然后把命令写入 aof 文件中。很奇特吧？对，就是这么厉害。进行 aof_rewrite 的时候，redis 变量每个数据库，然后根据 key-value 对中 value 的具体类型，生成不同的命令，比如是 list，则它生成一个保存 list 的命令，这个命令里包含了保存该 list 所需要的的数据，如果这个 list 数据过长，还会分成多条命令，先创建这个 list，然后往 list 里面添加元素，总之，就是根据数据反向生成保存数据的命令。然后将这些命令存储 aof 文件，这样不就和 aof append 达到同样的效果了么？
再来看，aof 格式也支持后台模式。执行 aof_bgrewrite 的时候，也是 fork 一个子进程，然后让子进程进行 aof_rewrite，把它复制的数据库写入一个临时文件，然后写完后用新号通知父进程。父进程判断子进程的退出信息是否正确，然后将临时文件更名成最终的 aof 文件。好了，问题来了。在子进程持久化期间，可能父进程的数据库有更新，怎么把这个更新通知子进程呢？难道要用进程间通信么？是不是有点麻烦呢？你猜 redis 怎么做的？它根本不通知子进程。
什么，不通知？那更新怎么办？在子进程执行 aof_bgrewrite 期间，父进程会保存所有对数据库有更改的操作的命令（增，删除，改等），把他们保存在 aof_rewrite_buf_blocks 中，这是一个链表，每个 block 都可以保存命令，存不下时，新申请 block，然后放入链表后面即可，当子进程通知完成保存后，父进程将 aof_rewrite_buf_blocks 的命令 append 进 aof 文件就可以了。多么优美的设计，想一想自己当初还考虑用进程间通信，别人直接用最简单的方法就完美的解决了问题，有句话说得真对，越优秀的设计越趋于简单，而复杂的东西往往都是靠不住的。
至于 aof 文件的载入，也就是一条一条的执行 aof 文件里面的命令而已。不过考虑到这些命令就是客户端发送给 redis 的命令，所以 redis 干脆生成了一个假的客户端，它没有和 redis 建立网络连接，而是直接执行命令即可。首先搞清楚，这里的假的客户端，并不是真正的客户端，而是存储在 redis 里面的客户端的信息，里面有写和读的缓冲区，它是存在于 redis 服务器中的。所以，如下图，直接读入 aof 的命令，放入客户端的读缓冲区中，然后执行这个客户端的命令即可。这样就完成了 aof 文件的载入。
// 创建伪客户端
fakeClient = createFakeClient();
while(命令不为空) {// 获取一条命令的参数信息 argc，argv
...
// 执行
fakeClient->argc = argc;
fakeClient->argv = argv;
cmd->proc(fakeClient);
}整个 aof 持久化的设计，个人认为相当精彩。其中有很多地方，值得膜拜。
redis 另一个比 memcached 强大的地方，是它支持简单的事务。事务简单说就是把几个命令合并，一次性执行全部命令。对于关系型数据库来说，事务还有回滚机制，即事务命令要么全部执行成功，只要有一条失败就回滚，回到事务执行前的状态。redis 不支持回滚，它的事务只保证命令依次被执行，即使中间一条命令出错也会继续往下执行，所以说它只支持简单的事务。
首先看 redis 事务的执行过程。首先执行 multi 命令，表示开始事务，然后输入需要执行的命令，最后输入 exec 执行事务。redis 服务器收到 multi 命令后，会将对应的 client 的状态设置为 REDIS_MULTI，表示 client 处于事务阶段，并在 client 的 multiState 结构体里面保持事务的命令具体信息（当然首先也会检查命令是否能否识别，错误的命令不会保存），即命令的个数和具体的各个命令，当收到 exec 命令后，redis 会顺序执行 multiState 里面保存的命令，然后保存每个命令的返回值，当有命令发生错误的时候，redis 不会停止事务，而是保存错误信息，然后继续往下执行，当所有的命令都执行完后，将所有命令的返回值一起返回给客户。
redis 为什么不支持回滚呢？网上看到的解释出现问题是由于客户程序的问题，所以没必要服务器回滚，同时，不支持回滚，redis 服务器的运行高效很多。在我看来，redis 的事务不是传统关系型数据库的事务，要求 CIAD 那么非常严格，或者说 redis 的事务都不是事务，只是提供了一种方式，使得客户端可以一次性执行多条命令而已，就把事务当做普通命令就行了，支持回滚也就没必要了。
我们知道 redis 是单 event loop 的，在真正执行一个事物的时候（即 redis 收到 exec 命令后），事物的执行过程是不会被打断的，所有命令都会在一个 event loop 中执行完。但是在用户逐个输入事务的命令的时候，这期间，可能已经有别的客户修改了事务里面用到的数据，这就可能产生问题。
所以 redis 还提供了 watch 命令，用户可以在输入 multi 之前，执行 watch 命令，指定需要观察的数据，这样如果在 exec 之前，有其他的客户端修改了这些被 watch 的数据，则 exec 的时候，执行到处理被修改的数据的命令的时候，会执行失败，提示数据已经 dirty。这是如何是实现的呢？原来在每一个 redisDb 中还有一个 dict watched_keys，watched_kesy 中 dictentry 的 key 是被 watch 的数据库的 key，而 value 则是一个 list，里面存储的是 watch 它的 client。
同时，每个 client 也有一个 watched_keys，里面保存的是这个 client 当前 watch 的 key。在执行 watch 的时候，redis 在对应的数据库的 watched_keys 中找到这个 key（如果没有，则新建一个 dictentry），然后在它的客户列表中加入这个 client，同时，往这个 client 的 watched_keys 中加入这个 key。当有客户执行一个命令修改数据的时候，redis 首先在 watched_keys 中找这个 key，如果发现有它，证明有 client 在 watch 它，则遍历所有 watch 它的 client，将这些 client 设置为 REDIS_DIRTY_CAS，表面有 watch 的 key 被 dirty 了。
当客户执行的事务的时候，首先会检查是否被设置了 REDIS_DIRTY_CAS，如果是，则表明数据 dirty 了，事务无法执行，会立即返回错误，只有 client 没有被设置 REDIS_DIRTY_CAS 的时候才能够执行事务。需要指出的是，执行 exec 后，该 client 的所有 watch 的 key 都会被清除，同时 db 中该 key 的 client 列表也会清除该 client，即执行 exec 后，该 client 不再 watch 任何 key（即使 exec 没有执行成功也是一样）。所以说 redis 的事务是简单的事务，算不上真正的事务。
以上就是 redis 的事务，感觉实现很简单，实际用处也不是太大。
redis 支持频道，即加入一个频道的用户相当于加入了一个群，客户往频道里面发的信息，频道里的所有 client 都能收到。
实现也很简单，也 watch_keys 实现差不多，redis server 中保存了一个 pubsub_channels 的 dict，里面的 key 是频道的名称（显然要唯一了），value 则是一个链表，保存加入了该频道的 client。同时，每个 client 都有一个 pubsub_channels，保存了自己关注的频道。当用用户往频道发消息的时候，首先在 server 中的 pubsub_channels 找到改频道，然后遍历 client，给他们发消息。而订阅，取消订阅频道不够都是操作 pubsub_channels 而已，很好理解。
同时，redis 还支持模式频道。即通过正则匹配频道，如有模式频道 p , 1, 则向普通频道 p1 发送消息时，会匹配 p ，1，除了往普通频道发消息外，还会往 p ， 1 模式频道中的 client 发消息。注意，这里是用发布命令里面的普通频道来匹配已有的模式频道，而不是在发布命令里制定模式频道，然后匹配 redis 里面保存的频道。
实现方式也很简单，在 redis server 里面有个 pubsub_patterns 的 list（这里为什么不用 dict？因为 pubsub_patterns 的个数一般较少，不需要使用 dict，简单的 list 就好了），它里面存储的是 pubsubPattern 结构体，里面是模式和 client 信息，如下所示，一个模式，一个 client，所以如果有多个 clint 监听一个 pubsub_patterns 的话，在 list 面会有多个 pubsubPattern，保存 client 和 pubsub_patterns 的对应关系。同时，在 client 里面，也有一个 pubsub_patterns list，不过里面存储的就是它监听的 pubsub_patterns 的列表（就是 sds），而不是 pubsubPattern 结构体。
typedef struct pubsubPattern {redisClient *client; // 监听的 client
robj *pattern; // 模式
} pubsubPattern;当用户往一个频道发送消息的时候，首先会在 redis server 中的 pubsub_channels 里面查找该频道，然后往它的客户列表发送消息。然后在 redis server 里面的 pubsub_patterns 里面查找匹配的模式，然后往 client 里面发送消息。这里并没有去除重复的客户，在 pubsub_channels 可能已经给某一个 client 发过 message 了，然后在 pubsub_patterns 中可能还会给用户再发一次（甚至更多次）。估计 redis 认为这是客户程序自己的问题，所以不处理。
/* Publish a message */
int pubsubPublishMessage(robj *channel, robj *message) {int receivers = 0;
dictEntry *de;
listNode *ln;
listIter li;
/* Send to clients listening for that channel */
de = dictFind(server.pubsub_channels,channel);
if (de) {list *list = dictGetVal(de);
listNode *ln;
listIter li;
listRewind(list,&li);
while ((ln = listNext(&li)) != NULL) {
redisClient *c = ln->value;
addReply(c,shared.mbulkhdr[3]);
addReply(c,shared.messagebulk);
addReplyBulk(c,channel);
addReplyBulk(c,message);
receivers++;
}
}
/* Send to clients listening to matching channels */
if (listLength(server.pubsub_patterns)) {listRewind(server.pubsub_patterns,&li);
channel = getDecodedObject(channel);
while ((ln = listNext(&li)) != NULL) {
pubsubPattern *pat = ln->value;
if (stringmatchlen((char*)pat->pattern->ptr,
sdslen(pat->pattern->ptr),
(char*)channel->ptr,
sdslen(channel->ptr),0)) {addReply(pat->client,shared.mbulkhdr[4]);
addReply(pat->client,shared.pmessagebulk);
addReplyBulk(pat->client,pat->pattern);
addReplyBulk(pat->client,channel);
addReplyBulk(pat->client,message);
receivers++;
}
}
decrRefCount(channel);
}
return receivers;
}总的来看，redis 比 memcached 的功能多很多，实现也更复杂。不过 memcached 更专注于保存 key-value 数据（这已经能满足大多数使用场景了），而 redis 提供更丰富的数据结构及其他的一些功能。不能说 redis 比 memcached 好，不过从源码阅读的角度来看，redis 的价值或许更大一点。另外，redis3.0 里面支持了集群功能，这部分的代码还没有研究，后续再跟进。
