Redis设计与实现（一~五整合版）-阿里云开发者社区

http://www.tuicool.com/articles/YBNZZzI

一

前言

项目中用到了redis，但用到的都是最最基本的功能，比如简单的slave机制，数据结构只使用了字符串。但是一直听说redis是一个很牛的开源项目，很多公司都在用。于是我就比较奇怪，这玩意不就和 memcache 差不多吗？仅仅是因为memcache是内存级别的，没有持久化功能。而redis支持持久化？难道这就是它的必杀技？

带着这个疑问，我在网上搜了一圈。发现有个叫做huangz的程序员针对redis写了一本书叫做《redis设计与实现》，而且业界良心搞了一个reids2.6版本的注释版源码。这本书不到200页，估计2个星期能看完吧，之后打算再看下感兴趣部分的源码。当然，如果你不知道redis是干嘛的，请自行谷歌，简单说就是Key-Value数据库，而且 value 支持5种数据结构：

字符串
哈希表（map）
列表（list）
集合（set）
有序集

下面我们就从 redis 的内部结构开始说起吧：）

一、redis内部数据结构

首先需要知道，redis是用C写的。众所周知，任何系统对于字符串的操作都是最频繁的，而恰巧C语言的字符串备受诟病。然后作者就封装了一下 C 语言的字符串 char *。

总之，根据redis的业务场景，整个redis系统的底层数据支撑被设计为如下几种：

简单动态字符串sds(Simple Dynamic String)
双端链表
字典(Map)
跳跃表

下面我们就分别来说说这4种数据结构。

1. 简单动态字符串sds

redis的字符串表示为sds，而不是C字符串（以\0结尾的char*）
对比C字符串，sds有以下特性
- 可以高效执行长度计算O(1)
- 可以高效执行append操作(通过free提前分配）
- 二进制安全
sds会为追加操作进行优化，加快追加操作的速度，并降低内存分配的次数，代价是多占用内存，且不会主动释放

这个一看名字就能知道个大概了，因为字符串操作无非是增删查改，如果使用char[]数组，那是要死人的，任何操作都是O(N)复杂度。所以，要对某些频繁的操作实现O(1)级性能。但是我们还是得思考：

为什么要对字符串造轮子？

因为redis是一个key-value类型的数据库，而key全部都是字符串，value可以是集合、hash、list等等。同时，在redis的各种操作中，都会频繁使用字符串的长度和append操作，对于char[]来说，长度操作是O(N)的，append会引起N次realloc。而且因为redis分为client和server，传输的协议内容必须是二进制安全的，而C的字符串必须保证是\0结尾，所以在这两点的基础上开发sds

知道了上面几点就可以看下实现了，其实实现特别简单。它通过一个结构体来代表字符串对象，内部有个len属性记录长度，有个free用于以后的append操作，具体的值还是一个char[]。长度就不说了，只在插入的时候用一下，以后只需要维护len就可以O(1)拿到；对于free也很简单，vector不也是这么实现的嘛。就是按照某个阈值进行翻倍叠加。

2. 双端链表

redis自己实现了双端链表
双端链表主要两个作用：
1. 作为redis列表类型的底层实现之一
2. 作为通用数据结构被其他模块使用
双端链表及其节点的性能特征如下：
- 节点带有前驱和后继指针
- 链表是双向的，所以对表头和表尾操作都是O(1)
- 链表节点可以会被维护，LLEN复杂度为O(1)

这玩意当时刷数据结构与算法分析那本书看过，但是没怎么用到过。说白了双端链表就是有2个指针，一个指向链表头，一个指向链表尾。对每个节点而言，记录自己的父节点和子节点，这样双向移动速度会快很多。

还是老问题：

为什么要有双端链表？

在Java或者C++中，都有现成的容器供我们使用，但是C没有。于是作者自己造了一个双端链表数据结构。而这个也是redis列表数据结构的基础之一（另外一个还是压缩列表）。而且双端链表也是一个通用的数据结构被其他功能调用，比如事务。

至于实现也是比较简单，双端链表，肯定有2个指针指向链表头和链表尾，然后内部维护一个len保存节点的数目，这样当使用LLEN的时候就能达到O(1)复杂度了。其他的，额，对每个节点而言，都有双向的指针，另外还有针对双端链表的迭代器，也是两个方向。

3. 字典（其实说Map更通俗）

字典是由键值对构成的抽象数据结构
redis中的数据库和哈希键值对都基于字典实现
字典的底层实现为哈希表，每个字典含有2个哈希表，一般只是用0号哈希表，1号哈希表是在rehash过程中才使用的
哈希表使用链地址法来解决碰撞问题
rehash可以用于扩展或者收缩哈希表
对哈希表的rehash是分多次、渐进式进行的

这个虽然说经常用，但是对于redis来说确实是重中之重。毕竟redis就是一个key-value的数据库，而key被称为键空间(key space)，这个键空间就是由字典实现的。第二个用途就是用作hash类型的其中一种底层实现。下面分别来说明。

键空间：redis是一个键值对数据库，数据库中的键值对就由字典保存：每个数据库都有一个与之相对应的字典，这个字典被称为键空间。当用户添加一个键值对到数据库（不论键值对是什么类型），程序就讲该键值对添加到键空间，删除同理。
用作hash类型键的其中一种底层实现：hash底层实现是通过压缩列表和字典实现的，当建立一个hash结构的时候，会优先使用空间占用率小的压缩列表。当有需要的时候会将压缩列表转化为字典

对于字典的实现这里简单说明一下即可，因为很简单。

字典是通过hash表实现的。每个字典含有2个hash表，分别为ht[0]和ht[1]，一般情况下使用的是ht[0],ht[1]只有在rehash的时候才用到。为什么呢？因为性能，我们知道，当hash表出现太多碰撞的话，查找会由O(1)增加到O(MAXLEN),redis为了性能，会在碰撞过多的情况下发生rehash，rehash就是扩大hash表的大小，从而将碰撞率降低，当hash表大小和节点数量维持在1：1时候性能最优，就是O(1)。另外的rehashidx字段也比较有看头，redis支持渐进式hash，下面会讲到原理。

下面讲一下rehash的触发条件：

当新插入一个键值对的时候，根据used/size得到一个比例，如果这个比例超过阈值，就自动触发rehash过程。rehash分为两种：

自然rehash:满足used/size >= 1 && dict_can_resize条件触发的
强制rehash:满足used/size >= dict_force_resize_ratio(默认为5)条件触发的。

思考一下，为什么需要两种rehash呢？答案还是为了性能，不过这点考虑的是redis服务的整体性能。当redis使用后台子进程对字典进行rehash的时候，为了最大化利用系统的copy on write机制，子进程会暂时将自然rehash关闭，这就是dict_can_resize的作用。当持久化任务完成后，将dict_can_resize设为true，就可以继续进行自然rehash；但是考虑另外一种情况，当现有字典的碰撞率太高了，size是指针数组的大小，used是hash表节点数量，那么就必须马上进行rehash防止再插入的值继续碰撞，这将浪费很长时间。所以超过dict_force_resize_ratio后，无论在进行什么操作，都必须进行rehash。

rehash过程很简单，分为3步：

给ht[1]分配至少2倍于ht[0]的空间
将ht[0]数据迁移到ht[1]
清空ht[0], 将ht[0]指针指向ht[1],ht[1]指针指向ht[0]

同样是为了性能（当用户对一个很大的字典插入时候，你不能让系统阻塞来完成整个字典的rehash。所以redis采用了渐进式rehash。说白了就是分步进行rehash。具体由下面2个函数完成：

dictRehashStep:从名字可以看出，是按照step进行的。当字典处于rehash状态(dict的rehashidx不为-1)，用户进行增删查改的时候会触发dictRehashStep，这个函数就是将第一个索引不为空的全部节点迁移到ht[1]，因为一般情况下节点数目不会超过5(超过基本会触发强制rehash），所以成本很低，不会影响到响应时间。
dictRehashMilliseconds:这个相当于时间片轮转rehash，定时进行redis cron job来进行rehash。会在指定时间内对dict的rehashidx不为-1的字典进行rehash

上面讲完了rehash过程，但是以前在组内分享redis的时候遇到过一个问题：

当进行rehash时候，我进行了增删查改怎么办？是在ht[0]进行还是在ht[1]进行呢？

redis采用的策略是rehash过程中ht[0]只减不增，所以增加肯定是ht[1]，查找、修改、删除则会同时在ht[0]和ht[1]进行。

Tips: redis为了减少存储空间，rehash还有一个特性是缩减空间，当多次进行删除操作后，如果used/size的比例小于一个阈值（现在是10%),那么就会触发缩减空间rehash，过程和增加空间类似，不详述了。

3. 跳跃表

跳跃表是一种随机化数据结构（它的层是随机产生的），查找、添加、删除操作都是O(logN)级别的。
跳跃表目前在redis的唯一用处就是有序集类型的底层数据结构之一（另外一个还是字典）
当然，根据redis的特性，作者对跳跃表进行了修改
- socre可以重复
- 对比一个元素需要同时检查它的score和member
- 每个节点带有高度为1的后退指针，用于从表尾方向向表头方向迭代

redis使用了跳跃表，但是我发现。。。。我竟然不知道跳跃表是什么东东。亏我还觉得数据结构基础还凑合呢= =。于是赶紧去看了《数据结构与算法分析》，算是知道是啥玩意的。说白了，就是链表+二分查找的结合体。这里主要是研究redis的，所以就不细谈这个数据结构了。

和双端链表、字典不同的是，跳跃表在reids中不是广泛使用的，它在redis中的唯一作用就是实现有序集数据类型。所以等到集合的时候再深入了解。

二

上一章我们介绍了redis的内部结构：

但是，创建这些完整的数据结构是比较耗费内存的，如果对于一个特别简单的元素，使用这些数据结构无异于大材小用。为了解决这个问题，redis在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构，主要有：

整数集合 intset
压缩列表 ziplist

当然了，因为这些结构是和内存直接打交道的，就有节省内存的优点，而又因为对内存的操作比较复杂，所以也有操作复杂，占用的CPU时间更多的缺点。

这个要掌握一个平衡，才能使redis的总体效率更好。目前，redis使用两种内存映射数据结构。

1. 整数集合

整数集合用于有序、无重复的保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。比如，在一个int set中，最大的元素可以用int16_t保存，那么这个int set的所有元素都是int16_t，当插入一个元素是int32_t的时候，int set会先将所有元素升级为int32_t，再插入这个元素。总的来说，整数集合会自动升级。

看名字我们就知道它的用途：

只保存整数元素
元素的数量不多[因为它不费内存，费CPU。量多的话，肯定是CPU为第一考虑]

那么我们看一下 intset 的定义：

1 typedef struct intset {
 2 
 3     // 保存元素所使用的类型的长度
 4     uint32_t encoding;
 5 
 6     // 元素个数
 7     uint32_t length;    
 8 
 9     // 保存元素的数组
10     int8_t contents[];  
11 
12 } intset;

其中 encoding 保存的是 intset 中元素的编码类型，比如是 int16_t还是 int32_t等等。具体的定义在 intset.c 中：

1 #define INTSET_ENC_INT16 (sizeof(int16_t))
2 #define INTSET_ENC_INT32 (sizeof(int32_t))
3 #define INTSET_ENC_INT64 (sizeof(int64_t))

length 肯定就是元素的个数喽，然后是具体的元素，我们发现是 int8_t 类型的，实现上它只是一个象征意义上的类型，到实际分配时候，会根据具体元素的类型选择合适的类型。而且 contents 有两个特点：

没有重复元素
元素在数组中从小到大排序

所以，添加元素到intset有下面几个步骤：

判断插入元素是否存在于集合，如果存在，没有任何操作(无重复元素)
看元素的长度是否需要把intset升级，如果需要，先升级
插入元素，而且要保证在contents数组中，从小到大排序
维护length

简单总结一下整数集合的特点：

保存有序、无重复的整数元素
根据元素的值自动选择对应的类型，但是int set只升级、不降级
升级会引起整个int set中的contents数组重新内存分配，并移动所有的元素（因为内存不一样了），所以复杂度为O(N)
因为int set是有序的，所以查找使用的是binary search

2. 压缩列表

本质来说，压缩列表就是由一系列特殊编码的内存块构成的列表，一个压缩列表可以包含多个节点，每个节点可以保存一个长度受限的字符数组（不以为\0结尾的char数组）或者整数。说白了，它是以内存为中心的数据结构，一般列表是以元素类型的字节总数为大小，而压缩列表是以它最小内存块进行扩展组成的列表。下面我来说一下。

压缩列表分为3个部分：

header：10字节，保存整个压缩列表的信息，有尾节点到head的偏移量、节点个数、整个压缩列表的内存（字节）
节点：一个结构体、由前一个节点的大小（用于向前遍历）、元素类型and长度、具体值组成
哨兵：就是一个1字节的全为1的内存，表示一个压缩列表的结束

其中压缩列表的节点值得说一下，它可以存储两类数据：

那么，怎样实现呢？很简单，通过 encoding + length 就可以搞定。encoding 占2位，00，01，10，11表示不明的类型，只有11代表的是节点中存放的是整型，其他3个代表节点中存放的都是字符串。而根据这2位的不同，又对应着不同的长度。

所以，由 encoding 可以知道元素的类型和这个元素的范围（比如 encoding 为01，包括 encoding 在内的2byte 代表长度，所以最长是214 - 1；如果 encoding 为00，包括 encoding 在内的1byte 代表元素的长度，所以最大值为26 -1 ）

然后添加元素大概是下面酱紫滴（对于列表来说，添加元素默认是加在列表尾巴的）：

首先通过压缩列表的head信息，找到压缩列表的尾巴到head的偏移量（因为可能重新分配内存，所以指针的话会失效）
根据要插入的值，计算出编码类型和插入值的长度。然后还有前一个节点所用的空间、然后对压缩列表进行内存充分配
初始化entry节点的所有相关信息：pre_entry_length、encoding、length、content
更新head中的长度啦、尾偏移啦、压缩列表总字节啦

上面吐槽了压缩列表没有next指针，现在发现有了= =，但是不是指针，因为压缩列表会进行内存充分配，所以指针代表的内存地址需要一直维护，而当使用偏移量的话，就不需要更改一次维护一次。向后遍历是通过头指针+节点的大小（pre_entry_length+encoding+length的总大小）就可以跳到下一个节点了

不过，说实话，压缩列表这个设计的好处我还没有看到，可能还需要和后面的东西结合吧。

重读之后看到了，(^__^) 嘻嘻……

本质上面已经说的很清楚了——节省内存。所以它不像上一章讲到的那种分配固定的大小，而 intset 和 ziplist 完全是根据内存定做的，一个字节也不多（当然，有些操作还是会有浪费的）。

三

前言

这一章主要是讲redis内部的数据结构是如何实现的，可以说是redis的根基，前面2章介绍了redis的内部数据结构：

redis的内存映射数据结构：

而这一章，就是具体将这些数据结构是如何在redis中工作的。

1. 总观redis内部实现

一张图说明问题的本质：

Screen Shot 2014-09-02 at 23.11.30.png

之后，我们再根据这张图来说明redis中的数据架构为什么是酱紫滴。前面我们已经说过，redis中有5种数据结构，而它们的底层实现都不是唯一的，所以怎样选择对应的底层数据支撑呢？这就需要“多态”的思想，但是因为redis是C开发的。所以通过结构体来模仿对象的“多态”（当然，本质来说这是为了让自己能更好的理解）。

为了完成这个任务，redis是这样设计的：

redisObject对象
基于redisObject对象的类型检查
基于redisObject对象的显式多态函数
对redisObject进行分配、共享和销毁的机制

下面看下redisObject的定义：

/*
 * Redis 对象
 */
typedef struct redisObject {

  // 类型
  unsigned type:4;

  // 对齐位
  unsigned notused:2;

  // 编码方式
  unsigned encoding:4;

  // LRU 时间（相对于 server.lruclock）
  unsigned lru:22;

  // 引用计数
  int refcount;

  // 指向对象的值
  void *ptr;

} robj;

其中type、encoding、ptr是最重要的3个属性：

type：redisObject的类型，字符串、列表、集合、有序集、哈希表
encoding：底层实现结构，字符串、整数、跳跃表、压缩列表等
ptr：实际指向保存值的数据结构

举个例子就是：

如果一个 redisObject 的 type 属性为 REDIS_LIST ， encoding 属性为 REDIS_ENCODING_LINKEDLIST ，那么这个对象就是一个 Redis 列表，它的值保存在一个双端链表内，而 ptr 指针就指向这个双端链表；如果一个 redisObject 的 type 属性为 REDIS_HASH ， encoding 属性为 REDIS_ENCODING_ZIPMAP ，那么这个对象就是一个 Redis 哈希表，它的值保存在一个 zipmap 里，而 ptr 指针就指向这个 zipmap ；诸如此类。

所以，当执行一个操作时，redis是这么干的：

根据key，查看数据库中是否存在对应的redisObject，没有就返回null
查看redisObject的type是否和要执行的操作相符
根据redisObject的encoding属性选择对应的数据结构
返回处理结果

然后reids还搞了一个内存共享，这个挺赞的：

对于一些操作来说，返回值就那几个。对于整数来说，存入的数据也通常不会太大，所以redis通过预分配一些常见的值对象，并在多个数据结构之间（很不幸，你得时指针才能指到这里）共享这些对象，避免了重复分配，节约内存。同时也节省了CPU时间

如图所示：

Screen Shot 2014-09-02 at 23.11.39.png

三个列表的值分别为：

列表 A ： [20130101, 300, 10086]
列表 B ： [81, 12345678910, 999]
列表 C ： [100, 0, -25, 123]

最后一个：redis对对象的管理是通过最原始的引用计数方法。

2. 字符串

字符串是redis使用最多的数据结构，除了本身作为SET/GET的操作对象外，数据库中的所有key，以及执行命令时提供的参数，都是用字符串作为载体的。

在上面的图中，我们可以看见，字符串的底层可以有两种实现：

REDIS_ENCODING_INT使用long类型保存long的值
REDIS_ENCODING_ROW使用sdshdr保存sds、long long、double、long double等

说白了就是除了long是通过第一种存储以外，其他类型都是通过第二种存储滴。

然后新创建的字符串，都会默认使用第二种编码，在将字符串作为键或者值保存进数据库时，程序会尝试转为第一种（为了节省空间）

3. 哈希表

哈希表，嗯，它的底层实现也有两种：

REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_HT(字典)

当创建新的哈希表时，默认是使用压缩列表作为底层数据结构的，因为省内存呀。只有当触发了阈值才会转为字典：

哈希表中某个键或者值的长度大于server.hash_max_ziplist_value（默认为64）
压缩列表中的节点数量大于server.hash_max_ziplist_entries(默认为512)

4. 列表

列表嘛，其实就是队列。它的底层实现也有2种：

REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_LINKEDLIST

当创建新的列表时，默认是使用压缩列表作为底层数据结构的，还是因为省内存- -。同样有一个触发阈值：

试图往列表中插入一个字符串值，长度大于server..list_max_ziplist_value(默认是64)
ziplist包含的节点超过server.list_max_ziplist_entries(默认值为512)

阻塞命令

对于列表，基本的操作就不介绍了，因为列表本身的操作和底层实现基本一致，所以我们可以简单的认为它具有双端队列的操作即可。重点讨论一下列表的阻塞命令比较好玩。

当我们执行BLPOP/BRPOP/BRPOPLPUSH的时候，都可能造成客户端的阻塞，它们被称为列表的阻塞原语，当然阻塞原语并不是一定会造成客户端阻塞：

只有当这些命令作用于空列表，才会造成客户端阻塞
如果被处理的列表不为空，它们就执行无阻塞版本的LPOP/RPOP/RPOPLPUSH

上面两条的意思很简单，因为POP命令是删除一个节点，那么当没有节点的时候，客户端会阻塞直到一个元素添加进来，然后再执行POP命令，那么，对客户端的阻塞过程是这样的：

将客户端的连接状态更改为“正在阻塞”，并记录这个客户端是被那些键阻塞（可以有多个），以及阻塞的最长时间
将客户端的信息加入到字典server.db[i].blocking_keys中，i就是客户端使用的数据库编号
继续保持客户端和服务器端的连接，但是不发送任何信息，造成客户端阻塞

响应的，解铃须有系铃人：

被动脱离：有其他客户端为造成阻塞的键加入了元素
主动脱离：超过阻塞的最长时间
强制脱离：关闭客户端或者服务器

上面的过程说的很简单，但是在redis内部要执行的操作可以很多的，我们用一段伪代码来演示一下被动脱离的过程：

def handleClientsBlockedOnLists():

# 执行直到 ready_keys 为空
while server.ready_keys != NULL: 
  # 弹出链表中的第一个 readyList
  rl = server.ready_keys.pop_first_node() 
  # 遍历所有因为这个键而被阻塞的客户端
  for client in all_client_blocking_by_key(rl.key, rl.db):

    # 只要还有客户端被这个键阻塞,就一直从键中弹出元素
    # 如果被阻塞客户端执行的是 BLPOP ,那么对键执行 LPOP
    # 如果执行的是 BRPOP ,那么对键执行 RPOP
    element = rl.key.pop_element()
    if element == NULL:
      # 键为空,跳出 for 循环
      # 余下的未解除阻塞的客户端只能等待下次新元素的进入了 
      break
    else:
      # 清除客户端的阻塞信息
      server.blocking_keys.remove_blocking_info(client) 
      # 将元素返回给客户端,脱离阻塞状态
      client.reply_list_item(element)

至于主动脱离，更简单了，通过redis的cron job来检查时间，对于过期的blocking客户端，直接释放即可。伪代码如下：

def server_cron_job():

    # cron_job其他操作 ...

    # 遍历所有已连接客户端
    for client in server.all_connected_client:

  # 如果客户端状态为“正在阻塞”,并且最大阻塞时限已到达	
  if client.state == BLOCKING and \
  client.max_blocking_timestamp < current_timestamp(): 

  # 那么给客户端发送空回复, 脱离阻塞状态
  client.send_empty_reply()

  # 并清除客户端在服务器上的阻塞信息
  server.blocking_keys.remove_blocking_info(client)	 

    # cron_job其他操作 ...

5. 集合

这个就是set，底层实现有2种：

REDIS_ENCODING_INTSET
REDIS_ENCODING_HT(字典)

对于集合来说，和前面的2种不同点在于，集合的编码是决定于第一个添加进集合的元素：

如果第一个添加进集合的元素是long long类型的，那么编码就使用第一种
否则使用第二种

同样，切换也需要达到一个阈值：

intset保存的整数值个数超过server.set_max_intset_entries(默认值为512)
从第二个元素开始，如果插入的元素类型不是long long的，就要转化成第二种

然后对于集合，有3个操作的算法很好玩，但是因为没用到过，就暂时列一下：

6. 有序集

终于看到最后一个数据结构了，虽然只有5个- -。。。。首先从命令上就可以区分这几种了：

GET/SET是字符串
H开头的是哈希表
L开头的是列表
S开头的是集合
Z开头的是有序集

继续说有序集，这个东西我还真的没用过。。。其他最起码都了解过，这个算是第一次接触。现在看来，它也算一个sort过的map，sort的依据就是score，对score排序后得到的集合。

首先还是底层实现，有2种：

REDIS_ENCODING_ZIPLIST
REDIS_ENCODING_SKIPLIST

这个竟然用到了跳跃表，不用这个的话，跳跃表好像都快被我忘了呢。。对于编码的选择，和集合类似，也是决定于第一个添加进有序集的元素：

如果满足：1.服务器属性server.zset_max_ziplist_entries值大于0（默认为128）2.元素的member长度小于服务器属性server.zset_max_ziplist_value(默认为64)，就以第一种作为底层数据结构
否则使用第二种

对于编码的转换阈值是这样的：

ziplist保存的元素数量超过服务器属性server.zset_max_ziplist_entries的值（默认为128）
ziplist的元素长度大于服务器属性server.zset_max_ziplist_value(默认为64)

那我们知道，如果有序集是用ziplist实现的，而ziplist终对于member和score是按次序存储的，如member1,score1,member2,score2...这样的。那么，检索时候就蛋疼了，肯定是O(N)复杂度，既然这样，效率一下子就没有了。庆幸的是，转换成跳跃表之后，redis搞的很高明：

它用一个字典和一个跳跃表同时来存储有序集的元素，而且因为member和score是在内存区域其字典有指针，就可以共享一块内存，不用每个元素复制两份。

通过使用字典结构,并将 member 作为键,score 作为值,有序集可以在 O(1) 复杂度内:

检查给定member是否存在于有序集(被很多底层函数使用)
取出 member 对应的 score 值(实现 ZSCORE 命令)

通过使用跳跃表,可以让有序集支持以下两种操作:

在 O(logN) 期望时间、O(N) 最坏时间内根据 score 对 member 进行定位(被很多底层函数使用)
范围性查找和处理操作,这是(高效地)实现 ZRANGE 、ZRANK 和 ZINTERSTORE等命令的关键

通过同时使用字典和跳跃表,有序集可以高效地实现按成员查找和按顺序查找两种操作。所以，对于有序集来说，redis的思路确实是很流弊的。

7. 总结

上面几个小节讲述了redis的数据结构的底层实现，但是没有涉及到具体的命令，如果调研后发现redis的某种数据结构满足需求，就可以对症下药，去查看redis对应的API即可。

四

前言

这一章主要讲解redis内部的一些功能，主要分为以下4个：

那么，我们就来逐个击破！

1. 事务

事务对于刚接触计算机的人来说可能会比较抽象。因为事务是对计算机某些操作的称谓。通俗来说，事务就是一个命令、一组命令执行的最小单元。事务一般具有ACID属性（redis只支持两种，下文详细说明）：

原子性（atomicity）：一个事务是一个不可分割的最小工作单位，事务中包括的诸操作要么都做，要么都不做。
一致性（consistency）：事务必须是使数据库从一个一致性状态变到另一个一致性状态。一致性与原子性是密切相关的。
隔离性（isolation）：一个事务的执行不能被其他事务干扰。即一个事务内部的操作及使用的数据对并发的其他事务是隔离的，并发执行的各个事务之间不能互相干扰。
持久性（durability）：持续性也称永久性（permanence），指一个事务一旦提交，它对数据库中数据的改变就应该是永久性的。接下来的其他操作或故障不应该对其有任何影响。

那么，redis是通过MULTI/DISCARD/EXEC/WATCH这4个命令来实现事务功能。对事务，我们必须知道事务安全性是一个非常重要的。

事务提供了一种“将多个命令打包，然后一次性、按顺序执行”的机制，并且在事务执行期间不会中断——意思就是在事务完成之前，客户端的其他命令都是阻塞状态。

以下是一个事务的例子,它先以 MULTI 开始一个事务,然后将多个命令入队到事务中,最后由EXEC 命令触发事务,一并执行事务中的所有命令:

redis> MULTI
OK
redis> SET book-name "Mastering C++ in 21 days"
81
QUEUED
redis> GET book-name
QUEUED
redis> SADD tag "C++" "Programming" "Mastering Series"
QUEUED
redis> SMEMBERS tag
QUEUED
redis> EXEC
1) OK
2) "Mastering C++ in 21 days"
3) (integer) 3
4) 1) "Mastering Series"
   2) "C++"
   3) "Programming"

一个事务主要经历3个阶段：

开始事务
命令入队（看，上面都有QUEUED这个返回值）
执行事务

这几个过程都比较简单，开始事务就是切换到事务模式；命令入队就是把事务中的每条命令记录下来，包括是第几条命令，命令参数什么的（当然，事务中是不能再嵌套事务的，所以再有事务关键字（MULTI/DISCARD/WATCH）会立即执行的）；执行事务就是一下子把刚才那个事务的命令执行完。

DISCARD: 取消一个事务，它会清空客户端的整个事务队列，然后将客户端从事务状态调整回非事务状态，最终返回字符串OK给客户端，说明事务已经取消
MULTI：因为redis不允许事务嵌套，所以，当在事务中输入MULTI时，redis服务器会简单返回一个错误，然后继续等待该事务的其他操作，就好像没有输入过MULTI一样
WATCH：WATCH用于在事务开始之前监视任意数量的键，当调用EXEC执行事务时，如果任意一个监视的键被修改了，那么整个事务就不再执行，直接返回失败。【事务安全性检查】

对于上面的WATCH来说，我们可以看成一个锁。这个锁在执行期间是不可以修改（类比为打开锁）的，这样才能保证这次事务是隔离的，安全的。那么，WATCH是如何触发的呢？

在任何对数据库键空间进行修改的命令执行成功后，multi.c/touchWatchKey函数都会被调用——它会检查数据库的watch_keys字典，看是否有客户端在监视被修改的键，如果有的话，就把这个监视的是客户端的REDIS_DIRTY_CAS打开。之后，执行EXEC前，会对这个事务的客户端检查是否REDIS_DIRTY_CAS被打开，打开的话就说明事务的安全性被破坏，直接返回失败；反之则正常进行事务操作。

事务的ACID性质

前面说到，事务一般具有ACID属性，但是redis只保证两种机制：一致性和隔离性。对于原子性和持久性并没有支持，下面说明redis为什么这样做。

原子性：redis的单条命令是原子性的，但是redis没有对事务进行原子性保护。如果一个事务没有执行成功，是不会进行重试或者回滚的。
一致性【redis保证】：这个要分三个层次：
1. 入队错误：如果执行一个错误的命令（比如命令参数不对：set key），那么会被标记为REDIS_DIRTY_EXEC,执行会直接返回错误
2. 执行错误：对某个类型key执行其他类型的操作，不会影响结果，所以不会影响事务的一致性。事务会继续进行
3. redis进程被冻结：简单来说，redis有持久化功能。但是这个持久化是建立在执行成功的基础上，如果不成功是不会进行持久化的。所以，出问题时都会保证要么事务没有执行；要么事务执行成功。所以保证了数据的一致性。
隔离性【redis保证】：因为redis是单进程程序，并在执行事务时不会中断，一直执行到事务对列为空，所以隔离性是可以保证的。
持久性：不管是单纯的内存模式，还是开启了持久化文件的功能，事务的每条命令执行过程中都会有时间间隙，如果这时候出现问题，持久化还是无法保证。所以，redis使用的是事务没执行或者事务执行完成才会进行持久化工作（AOF模式除外，虽然现在还没有看到- -）

2. 订阅与发布

这个东西没有仔细看，但是大概知道是啥功能的。我想了一下，可以使用这个功能来完成跨平台之间消息的推送。比如我开发了一个app，分别有web版本、ios版本、Android版本、Symbian版本。那么，我可以结合模式+频道，将消息推送到所有安装此应用的平台上。

3. Lua脚本

这是redis2.6版本最大的亮点。但是我们好像木有用过- -所以，以后有需求的时候再好好研究一下吧。

4. 慢查询日志

慢查询日志是redis系统提供的一个查看系统性能的功能。它的每一条记录的是一条命令的执行时间。所以，你可以在redis.conf中设置当超过slowlog_log_slower_than的时候，将这个命令记录下来；因为慢查询日志是一个FIFO队列（用链表实现的），所以还有一个slowlog_max_than来限制队列长度，如果溢出，就从队头删除最旧的，将最新的添加到队尾。

五

前言

这一章是讲redis内部运作机制的，所以算是redis的核心。在这一章中，将会学习到redis是如何设计成为一个非常好用的nosql数据库的。下面我们将要讨论这些话题：

redis是如何表示一个数据库的？它的操作是如何进行的？
redis的持久化是怎样触发的？持久化有什么作用（memcache就没有）
redis如何处理用户的输入？又试如何将运行结果返回给用户呢？
redis启动的时候，都需要做什么初始化工作？传入服务器的命令又是以什么方法执行的？

带着这几个问题，我们就来学习一下redis的内部运作机制，当然，我们重点是学习它为什么要这样设计，这样设计为什么是最优的？有没有可以改进的地方呢？对细节不必太追究，先从整体上理解redis的框架是如何搭配的，然后对哪个模块感兴趣再去看看源码，好像2.6版本的代码量在5W行左右吧。

1. 数据库

嗯，好像一直用的都是默认的数据库。废话不说，直接上一个数据库结构：

typedef struct redisDb {
  //数据库编号
  int id;

  //保存数据库所有键值对数据，也成为键空间（key space）
  dict *dict;

  //保存着键的过期信息
  dict *expires;

  //实现列表阻塞原语，如BLPOP
  dict *blocking_keys;
  dict *ready_keys;

  //用于实现WATCH命令
  dict *watched_keys
}

主要来介绍3个属性：

id：数据库编号，但是不是select NUM这个里面的，id这个属性是为redis内部提供的，比如AOF程序需要知道当前在哪个数据库中操作的，如果没有id来标识，就只能通过指针来遍历地址相等，效率比较低
dict：因为redis本身就是一个键值对数据库，所以这个dict存放的就是整个数据库的键值对。键是一个string，值可以是redis五种数据结构的任意一种。因为数据库本身是一个字典，所以对数据库的操作，基本都是对字典的操作
键的过期时间：因为有些数据是临时的，或者不需要长期保存，就可以给它设置一个过期时间（当然，key不会同时存在在key space和expire的字典中，两者会公用一个内存块）

这其中比较好的一个是redis对于过期键的处理，我当时看到这里想，可以弄一个定时器，定期来检查expire字典中的key是否到了过期时间，但是这个定时器的时间间隔不好控制，长了的话已经过期的键还可以访问；短了的话，又注定会影像系统的性能。

定时删除：定时器方法，和我想法一致
懒惰删除：这个类似线段树的lazy操作，很巧妙（总算数据结构没白学啊。。。）
定期删除：上面2个都有短板，这个是结合两者的一个折中策略。它会定时删除过期key，但是会控制时间和频率，同时也会减少懒惰删除带来的内存膨胀

lazy机制：

当你不用这个键的时候，我才懒得删除。当你访问redis的某个key时，我就检查一下这个key是否存在在expire中，如果存在就看是否过期，过期则删除（优化是标记一下，直接返回空，然后定时任务再慢慢删除这个）；反之再去redis的dict中取值。但是缺点也有，如果用于不访问，内存就一直占用。加入我给100万个key设置了5s的过期时间，但是我很少访问，那么内存到最后就会爆掉。

所以，redis综合考虑后采用了懒惰删除和定期删除，这两个策略相互配合，可以很好的完成CPU和内存的平衡。

2. RDB

因为当前项目用到了这个，必须要好好看看啊。战略上藐视一下，就是redis数据库从内存持久化到文件的意思。redis一共有两种持久化操作：

逐个来说，先搞定RDB。

对于RDB机制来说，在保存RDB文件期间，主进程会被阻塞，直到保存成功为止。但是这也分两种实现：

SAVE：直接调用rdbSave，阻塞redis主进程，直到保存完成，这完成过程中，不接受客户端的请求
BGSAVE：fork一个子进程，子进程负责调用rdbSave，并在保存完成知乎向主进程发送信号，通知保存已经完成。因为是fork的子进程，所以主进程还是可以正常工作，接受客户端的请求

整个流程可以用伪代码表示：

def SAVE():

  rdbSave()


def BGSAVE():

  pid = fork()

  if pid == 0:

    # 子进程保存 RDB
    rdbSave()

  elif pid > 0:

    # 父进程继续处理请求，并等待子进程的完成信号
    handle_request()

  else:

    # pid == -1
    # 处理 fork 错误
    handle_fork_error()

当然，写入之后就是load了。当redis服务重启，就会将存在的dump.rdb文件重新载入到内存中，用于数据恢复，那么redis是怎么做的呢？

额，这一节重点是RDB文件的结构，如果有兴趣，可以自己去看下dump.rdb文件，然后对照一下很容易就明白了。

3. AOF

AOF是append only file的缩写，意思是追加到唯一的文件，从上面对RDB的介绍我们知道，RDB的写入是触发式的，等待多少秒或者多少次写入才会持久化到文件中，但是AOF是实时的，它会记录你的每一个命令。

同步到AOF文件的整个过程可以分为三个阶段：

命令传播：redis将执行的命令、参数、参数个数都发送给AOF程序
缓存追加：AOF程序将收到的数据整理成网络协议的格式，然后追加到AOF的内存缓存中
文件写入和保存：AOF缓存中的内容被写入到AOF文件的尾巴，如果设定的AOF保存条件被满足，fsync或者或者fdatasync函数会被调用，将写入的内容真正保存到磁盘中

对于第三点我们需要说明一下，在前面我们说到，RDB是触发式的，AOF是实时的。这里怎么又说也是满足条件了呢？原来redis对于这个条件，有以下的方式：

AOF_FSYNC_NO：不保存。这时候，调用flushAppendOnlyFile函数的时候WRITE都会执行（写入AOF程序的缓存），但SAVE会(写入磁盘)跳过，只有当满足：redis被关闭、AOF功能被关闭、系统要刷新缓存（空间不足等），才会进行SAVE操作。这种方式相当于迫不得已才会进行SAVE，但是很不幸，这三种操作都会引起redis主进程的阻塞
AOF_FSYNC_EVERYSEC：每一秒保存一次。因为SAVE是后台子线程调用的，所有主线程不会阻塞。
AOF_FSYNC_ALWAYS：每执行一个命令保存一次。这个很好理解，但是因为SAVE是redis主进程执行的，所以在SAVE时候主进程阻塞，不再接受客户端的请求

补充：对于第二种的流程可能比较麻烦，用一个图来说明：

Screen Shot 2014-09-02 at 23.12.05.png

如果仔细看上面的条件，会发现一会SAVE是子线程执行的，一会是主进程执行的，那么怎样从根本上区分呢？

我个人猜测是区分操作的频率，第一种情况是服务都关闭了，主进程肯定会做好善后工作，发现AOF开启了但是没有写入磁盘，于是自己麻溜就做了；第二种情况，因为每秒都需要做，主进程不可能用一个定时器去写入磁盘，这时候用一个子线程就可以圆满完成；第三种情况，因为一个命令基本都是特别小的，所以执行一次操作估计非常非常快，所以主进程再调用子线程造成的上下文切换都显得有点得不偿失了，于是主进程自己搞定。【待验证】

对于上面三种方式来说，最好的应该是第二种，因为阻塞操作会让 Redis 主进程无法持续处理请求，所以一般说来，阻塞操作执行得越少、完成得越快，Redis 的性能就越好。

模式 1 的保存操作只会在AOF 关闭或 Redis 关闭时执行，或者由操作系统触发，在一般情况下，这种模式只需要为写入阻塞，因此它的写入性能要比后面两种模式要高，当然，这种性能的提高是以降低安全性为代价的：在这种模式下，如果运行的中途发生停机，那么丢失数据的数量由操作系统的缓存冲洗策略决定。
模式 2 在性能方面要优于模式 3 ，并且在通常情况下，这种模式最多丢失不多于 2 秒的数据，所以它的安全性要高于模式 1 ，这是一种兼顾性能和安全性的保存方案。
模式 3 的安全性是最高的，但性能也是最差的，因为服务器必须阻塞直到命令信息被写入并保存到磁盘之后，才能继续处理请求。

AOF文件的还原

对于AOF文件的还原就特别简单了，因为AOF是按照AOF协议保存的redis操作命令，所以redis会伪造一个客户端，把AOF保存的命令重新执行一遍，执行之后就会得到一个完成的数据库，伪代码如下：

def READ_AND_LOAD_AOF():

    # 打开并读取 AOF 文件
    file = open(aof_file_name)
    while file.is_not_reach_eof():

  # 读入一条协议文本格式的 Redis 命令
  cmd_in_text = file.read_next_command_in_protocol_format()

  # 根据文本命令，查找命令函数，并创建参数和参数个数等对象
  cmd, argv, argc = text_to_command(cmd_in_text)

  # 执行命令
  execRedisCommand(cmd, argv, argc)

    # 关闭文件
    file.close()

AOF重写

上面提到，AOF可以对redis的每个操作都记录，但这带来一个问题，当redis的操作越来越多之后，AOF文件会变得很大。而且，里面很大一部分都是无用的操作，你如我对一个整型+1，然后-1，然后再加1，然后再-1（比如这是一个互斥锁的开关），那么，过一段时间后，可能+1、-1操作就执行了几万次，这时候，如果能对AOF重写，把无效的命令清除，AOF会明显瘦身，这样既可以减少AOF的体积，在恢复的时候，也能用最短的指令和最少的时间来恢复整个数据库，迫于这个构想，redis提供了对AOF的重写。

所谓的重写呢，其实说的不够明确。因为redis所针对的重写实际上指数据库中键的当前值。AOF 重写是一个有歧义的名字，实际的重写工作是针对数据库的当前值来进行的，程序既不读写、也不使用原有的 AOF 文件。比如现在有一个列表，push了1、2、3、4，然后删除4、删除1、加入1，这样列表最后的元素是1、2、3，如果不进行缩减，AOF会记录4次redis操作，但是AOF重写它看的是列表最后的值：1、2、3，于是它会用一条rpush 1 2 3来完成，这样由4条变为1条命令，恢复到最近的状态的代价就变为最小。

整个重写过程的伪代码如下：

def AOF_REWRITE(tmp_tile_name):

  f = create(tmp_tile_name)

  # 遍历所有数据库
  for db in redisServer.db:

    # 如果数据库为空，那么跳过这个数据库
    if db.is_empty(): continue

    # 写入 SELECT 命令，用于切换数据库
    f.write_command("SELECT " + db.number)

    # 遍历所有键
    for key in db:

      # 如果键带有过期时间，并且已经过期，那么跳过这个键
      if key.have_expire_time() and key.is_expired(): continue

      if key.type == String:

  # 用 SET key value 命令来保存字符串键

  value = get_value_from_string(key)

  f.write_command("SET " + key + value)

      elif key.type == List:

  # 用 RPUSH key item1 item2 ... itemN 命令来保存列表键

  item1, item2, ..., itemN = get_item_from_list(key)

  f.write_command("RPUSH " + key + item1 + item2 + ... + itemN)

      elif key.type == Set:

  # 用 SADD key member1 member2 ... memberN 命令来保存集合键

  member1, member2, ..., memberN = get_member_from_set(key)

  f.write_command("SADD " + key + member1 + member2 + ... + memberN)

      elif key.type == Hash:

  # 用 HMSET key field1 value1 field2 value2 ... fieldN valueN 命令来保存哈希键

  field1, value1, field2, value2, ..., fieldN, valueN =\
  get_field_and_value_from_hash(key)

  f.write_command("HMSET " + key + field1 + value1 + field2 + value2 +\
      ... + fieldN + valueN)

      elif key.type == SortedSet:

  # 用 ZADD key score1 member1 score2 member2 ... scoreN memberN
  # 命令来保存有序集键

  score1, member1, score2, member2, ..., scoreN, memberN = \
  get_score_and_member_from_sorted_set(key)

  f.write_command("ZADD " + key + score1 + member1 + score2 + member2 +\
      ... + scoreN + memberN)

      else:

  raise_type_error()

      # 如果键带有过期时间，那么用 EXPIREAT key time 命令来保存键的过期时间
      if key.have_expire_time():
  f.write_command("EXPIREAT " + key + key.expire_time_in_unix_timestamp())

    # 关闭文件
    f.close()

AOF重写的一个问题：如何实现重写？

是使用后台线程还是使用子进程（redis是单进程的），这个问题值得讨论下。额，对进程线程只是概念级的，等看完之后得拿redis的进程、线程机制开刀好好学一下。

redis肯定是以效率为先，所以不希望AOF重写造成客户端无法请求，所以redis采用了AOF重写子进程执行，这样的好处有：

子进程对AOF重写时，主进程可以继续执行客户端的请求
子进程带有主进程的数据副本，使用子进程而不是线程，可以在避免锁的情况下，保证数据的安全性

当然，有有点肯定有缺点：

因为子进程在进行AOF重写时，主进程没有阻塞，所以肯定继续处理命令，而这时候的命令会对现在的数据修改，这些修改也是需要写入AOF文件的。这样重写的AOF和实际AOF会出现数据不一致。

为了解决这个问题，redis增加了一个AOF重写缓存（在内存中），这个缓存在fort出子进程之后开始启用，redis主进程在接到新的写命令之后，除了会将这个写命令的协议内容追加到AOF文件之外，还会同时追加到这个缓存中。这样，当子进程完成AOF重写之后，它会给主进程发送一个信号，主进程接收信号后，会将AOF重写缓存中的内容全部写入新AOF文件中，然后对新AOF改名，覆盖老的AOF文件。

在整个AOF重写过程中，只有最后的写入缓存和改名操作会造成主进程的阻塞（要是不阻塞，客户端请求到达又会造成数据不一致），所以，整个过程将AOF重写对性能的消耗降到了最低。

AOF触发条件

最后说一下AOF是如何触发的，当然，如果手动触发，是通过BGREWRITEAOF执行的。如果要用redis的自动触发，就要涉及下面3个变量（AOF的功能要开启哦 appendonlyfile yes）：

记录当前AOF文件大小的变量aof_current_size
记录最后一次AOF重写之后，AOF文件大小的变量aof_rewrite_base_size
增长百分比变量aof_rewrite_perc

每当serverCron函数（redis的crontab）执行时，会检查以下条件是否全部满足，如果是的话，就会触发自动的AOF重写：

没有 BGSAVE 命令在执行
没有 BGREWRITEAOF 在执行
当前AOF文件大小 > server.aof_rewrite_min_size(默认为1MB)
当前AOF文件大小和最后一次AOF重写后的大小之间的比率大于等于指定的增长百分比(默认为1倍，100%)

默认情况下，增长百分比为100%。也就是说，如果前面三个条件已经满足，并且当前AOF文件大小比最后一次AOF重写的大小大一倍就会触发自动AOF重写。

Redis设计与实现（一~五整合版）