《Redis设计与实现》笔记

第二章：简单动态字符串

        1.Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组,以下简称C字符串),而是自己构建了一种名为简单动态字符串( simple dynamic string,SDS)的抽象类型,并将SDS用作 Redis的默认字符串表示。

        Redis里面,C字符串只会作为字符串字面量( string literal)用在一些无须对字符串值进行修改的地方,比如打印日志：

        redislog (REDIS_WARNING,"Redis is now ready to exit, bye bye..");

        2.空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改,并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未使用空间。 

        其中,额外分配的未使用空间数量由以下公式决定:

• 如果对SDS进行修改之后,SDS的长度(也即是1en属性的值)将小于1MB,那么程序分配和1en属性同样大小的未使用空间,这时SDS1en属性的值将和free属性的值相同。举个例子,如果进行修改之后,SDS的1en将变成13字节,那么程序也会分配13字节的未使用空间,SDS的buf数组的实际长度将变成13+13+1=27字节(额外的一字节用于保存空字符)。
• 如果对SDS进行修改之后,SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。举个例子,如果进行修改之后,SDS的len将变成30MB,那么程序会分配1MB的未使用空间,SDS的buf数组的实际长度将为30MB+1MB+1byte。

        通过空间预分配策略,可以减少连续执行字符串增长操作所需的内存重分配次数。

        3.惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

        通过惰性空间释放策略,SDS避免了缩短字符串时所需的内存重分配操作,并为将来可能有的增长操作提供了优化。

        与此同时,SDS也提供了相应的API,让我们可以在有需要时,真正地释放SDS的未使用空间,所以不用担心惰性空间释放策略会造成内存浪费。

        4.SDS的API都是二进制安全的。

第三章：链表

        1.integers列表键的底层实现就是一个链表,链表中的每个节点都保存了一个整数值。除了链表键之外,发布与订阅、慢查询、监视器等功能也用到了链表, Redis服务器本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区output buffer)。

 

        

        2.list结构为链表提供了表头指针head、表尾指针tail,以及链表长度计数器len,而dup、free和 match成员则是用于实现多态链表所需的类型特定函数:

• dup函数用于复制链表节点所保存的值;
• free函数用于释放链表节点所保存的值;
• match函数则用于对比链表节点所保存的值和另一个输入值是否相等。

        3.Redis的链表实现的特性可以总结如下：

• 双端:链表节点带有prev和next指针,获取某个节点的前置节点和后置节点的复杂度都是O(1)。
• 无环:表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。
• 带表头指针和表尾指针:通过1ist结构的head指针和tai1指针,程序获取链表的表头节点和表尾节点的复杂度为O(1)。
• 带链表长度计数器:程序使用1ist结构的len属性来对1ist持有的链表节点进行计数,程序获取链表中节点数量的复杂度为O(1)。
• 多态:链表节点使用void*指针来保存节点值,并且可以通过1ist结构的dup、free、 match三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

第四章：字典

        1.Redis字典所使用的哈希表由dict.h/dictht结构定义：

table属性是一个数组,数组中的每个元素都是一个指向dict.h/dicentra结构的指针,每个 dictentry结构保存着一个键值对。size属性记录了哈希表的大小,也即是tab1e数组的大小,而used属性则记录了哈希表目前已有节点(键值对)的数量。sizemask属性的值总是等于size-1,这个属性和哈希值一起决定一个键应该被放到table数组的哪个索引上面。

        2.哈希表节点使用 dictentry结构表示,每个 dictentry结构都保存着一个键值对：

key属性保存着键值对中的键,而ⅴ属性则保存着键值对中的值,其中键值对的值可以是一个指针,或者是一个uint64t整数,又或者是一个int64t整数。

next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的键值对连接在一次,以此来解决键冲突( collision)的问题。 

        3.Redis中的字典由dict.h/dict结构表示:

type属性和 privata属性是针对不同类型的键值对,为创建多态字典而设置的:

• type属性是一个指向 ditype结构的指针,每个 dicttype结构保存了一簇用于操作特定类型键值对的函数, Redis会为用途不同的字典设置不同的类型特定函数。
• 而 privata属性则保存了需要传给那些类型特定函数的可选参数。

ht属性是一个包含两个项的数组,数组中的每个项都是一个 dicth哈希表,一般情况下,字典只使用ht[0]哈希表,ht[1哈希表只会在对ht[0哈希表进行 rehash时使用。

除了ht[1]之外,另一个和 rehash有关的属性就是 rehashidx,它记录了hash目前的进度,如果目前没有在进行 rehash,那么它的值为-1。

Redis计算哈希值和索引值的方法如下：

        4.当字典被用作数据库的底层实现,或者哈希键的底层实现时, Redis使用 Murmurhash2算法来计算键的哈希值。

Murmurhash算法最初由 Austin Appleby于2008年发明,这种算法的优点在于,即使输入的键是有规律的,算法仍能给出一个很好的随机分布性,并且算法的计算速度也非常快。

Murmurhash算法目前的最新版本为 Murmurhash3,而 Redis使用的是 Murmurhashi2,关于Murmurhash算法的更多信息可以参考该算法的主页:http:/code.google.com/p/smasher/。

        5.当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时,我们称这些键发生了冲突( collision)。

Redis的哈希表使用链地址法( separate chaining)来解决键冲突,每个哈希表节点都有个next指针,多个哈希表节点可以用next指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

        6.随着操作的不断执行,哈希表保存的键值对会逐渐地增多或者减少,为了让哈希表的负载因子( load factor)维持在一个合理的范围之内,当哈希表保存的键值对数量太多或者太少时,程序需要对哈希表的大小进行相应的扩展或者收缩。

扩展和收缩哈希表的工作可以通过执行 rehash(重新散列)操作来完成, Redis对字典的哈希表执行 rehash的步骤如下：

        1).为字典的ht[1]哈希表分配空间,这个哈希表的空间大小取决于要执行的操作,以及h[O当前包含的键值对数量(也即是ht[0].used属性的值)：

• 如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2 的2的n次方幂
• 如果执行的是收缩操作,那么ht[1的大小为第一个大于等于ht[0].used 的2的n次方幂

        2).将保存在ht[0]中的所有键值对 rehash到ht[1]上面: rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht[1]哈希表的指定位置上。

        3).当ht[0]包含的所有键值对都迁移到了ht[1]之后(ht[0]变为空表),释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次 rehash做准备。

        6.哈希表的扩展与收缩 

当以下条件中的任意一个被满足时,程序会自动开始对哈希表执行扩展操作:

1).服务器目前没有在执行 BGSAVE命令或者 BGREWRITEAOF命令,并且哈希表的负载因子大于等于1。

2).服务器目前正在执行 BGSAVE命令或者 BGREWRITEAOF命令,并且哈希表的负载因子大于等于5。

其中哈希表的负载因子可以通过公式:

#负载因子=哈希表已保存节点数量/哈希表大小

load_factor =ht[0].used/ht[0].size计算得出。

例如,对于一个大小为4,包含4个键值对的哈希表来说,这个哈希表的负载因子为:

load_factor =4/4=1

又例如,对于一个大小为512,包含256个键值对的哈希表来说,这个哈希表的负载因子为:

load_factor =256/ 512=0.5

根据 BGSAVE命令或 BGREWRITEAOF命令是否正在执行,服务器执行扩展操作所需的负载因子并不相同,这是因为在执行 BGSAVE命令或 BGREWRITEAOF命令的过程中, Redis需要创建当前服务器进程的子进程,而大多数操作系统都采用写时复制(copy-onwrite)技术来优化子进程的使用效率,所以在子进程存在期间,服务器会提高执行扩展操作所需的负载因子,从而尽可能地避免在子进程存在期间进行哈希表扩展操作,这可以避免不必要的内存写入操作,最大限度地节约内存。

另一方面,当哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作。

        7.渐进式rehash

上一节说过,扩展或收缩哈希表需要将ht[0]里面的所有键值对 rehash到ht[1里面,但是,这个 rehash动作并不是一次性、集中式地完成的,而是分多次、渐进式地完成的。

这样做的原因在于,如果ht[0]里只保存着四个键值对,那么服务器可以在瞬间就将这些键值对全部 rehash到ht[1];但是,如果哈希表里保存的键值对数量不是四个,而是四百万、四千万甚至四亿个键值对,那么要一次性将这些键值对全部 rehash到ht[1]的话庞大的计算量可能会导致服务器在一段时间内停止服务。

因此,为了避免 rehash对服务器性能造成影响,服务器不是一次性将ht[0j里面的所有键值对全部 rehash到ht[1],而是分多次、渐进式地将ht[0]里面的键值对慢慢地 rehash到ht[1]。

以下是哈希表渐进式 rehash的详细步骤:

1)为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。

2)在字典中维持一个索引计数器变量 rehashidx,并将它的值设置为0,表示 rehash工作正式开始。

3)在 rehash进行期间,每次对字典执行添加、删除、查找或者更新操作时,程序除了执行指定的操作以外,还会顺带将ht[0]哈希表在 rehashidx索引上的所有键值对rehash到ht[1],当 rehash工作完成之后,程序将 rehashidx属性的值增一。

4)随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将 rehashidx属性的值设为-1,表示 rehash操作已完成。渐进式 rehash的好处在于它采取分而治之的方式,将 rehash键值对所需的计算工作均摊到对字典的每个添加、删除、查找和更新操作上,从而避免了集中式 rehash而带来的庞大计算量。

        8.渐进式 rehash执行期间的哈希表操作

因为在进行渐进式 rehash的过程中,字典会同时使用ht[0]和ht[1]两个哈希表,所以在渐进式 rehash进行期间,字典的删除( delete)、查找(fnd)、更新( update)等操作会在两个哈希表上进行。例如,要在字典里面查找一个键的话,程序会先在ht[0]里面进行查找,如果没找到的话,就会继续到ht[1]里面进行查找,诸如此类。

另外,在渐进式 rehash执行期间,新添加到字典的键值对一律会被保存到ht[1]里面,而ht[0]则不再进行任何添加操作,这一措施保证了ht[0]包含的键值对数量会只减不增,并随着 rehash操作的执行而最终变成空表。

第五章：跳跃表

        1.跳跃表( skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表支持平均O(logN、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。

在大部分情况下,跳跃表的效率可以和平衡树相媲美,并且因为跳跃表的实现比平衡树要来得更为简单,所以有不少程序都使用跳跃表来代替平衡树。

Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时, Redis就会使用跳跃表来作为有序集合键的底层实现。

图5-1展示了一个跳跃表示例,位于图片最左边的是 zskiplist结构,该结构包含以下属性:

• header:指向跳跃表的表头节点。 
• tail:指向跳跃表的表尾节点。
• level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)。
• length:记录跳跃表的长度,也即是,跳跃表目前包含节点的数量(表头节点不计算在内)。

位于skiplist结构右方的是四个zskiplistNode结构,该结构包含以下属性:

• 层( level):节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。每个层都带有两个属性:前进指针和跨度。前进指针用于访问位于表尾方向的其他节点,而跨度则记录了前进指针所指向节点和当前节点的距离。在上面的图片中,连线上带有数字的箭头就代表前进指针,而那个数字就是跨度。当程序从表头向表尾进行遍历时,访问会沿着层的前进指针进行。
• 后退( backward)指针:节点中用BW字样标记节点的后退指针,它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
• 分值( score):各个节点中的1.0、2.0和3.0是节点所保存的分值。在跳跃表中节点按各自所保存的分值从小到大排列。
• 成员对象(obj):各个节点中的o1、o2和o3是节点所保存的成员对象。

注意表头节点和其他节点的构造是一样的:表头节点也有后退指针、分值和成员对象,不过表头节点的这些属性都不会被用到,所以图中省略了这些部分,只显示了表头节点的各个层。

        2.跳跃表节点的实现由redis.h/zskiplistNode结构定义：

1.层

跳跃表节点的level数组可以包含多个元素,每个元素都包含一个指向其他节点的指针,程序可以通过这些层来加快访问其他节点的速度,一般来说,层的数量越多,访问其他节点的速度就越快。

每次创建一个新跳跃表节点的时候,程序都根据幂次定律(power law,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是层的“高度”。

2.前进指针

每个层都有一个指向表尾方向的前进指针(level[i]. forward属性),用于从表头向表尾方向访问节点。

3.跨度层的跨度

• (level[i].span属性)用于记录两个节点之间的距离口两个节点之间的跨度越大,它们相距得就越远。
• 指向NULL的所有前进指针的跨度都为0,因为它们没有连向任何节点。

4.后退指针

节点的后退指针( backward属性)用于从表尾向表头方向访问节点:跟可以一次跳过多个节点的前进指针不同,因为每个节点只有一个后退指针,所以每次只能后退至前一个节点。

5.分值和成员
节点的分值( score属性)是一个doub1e类型的浮点数,跳跃表中的所有节点都按分值从小到大来排序。

节点的成员对象(obj属性)是一个指针,它指向一个字符串对象,而字符串对象则保存着一个SDS值。

在同一个跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的:分值相同的节点将按照成员对象在字典序中的大小来进行排序,成员对象较小的节点会排在前面(靠近表头的方向),而成员对象较大的节点则会排在后面(靠近表尾的方向)。

        3.仅靠多个跳跃表节点就可以组成一个跳跃表，但通过使用一个 skip1ist结构来持有这些节点,程序可以更方便地对整个跳跃表进行处理,比如快速访问跳跃表的表头节点和表尾节点,或者快速地获取跳跃表节点的数量(也即是跳跃表的长度)等信息。

header和tail指针分别指向跳跃表的表头和表尾节点,通过这两个指针,程序定位表头节点和表尾节点的复杂度为O(1)。
通过使用1 ength属性来记录节点的数量,程序可以在O()复杂度内返回跳跃表的长度。
level属性则用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量,注意表头节点的层高并不计算在内。

第六章：整数集合

        1.整数集合(intset)是集合键的底层实现之一,当一个集合只包含整数值元素,并且这个集合的元素数量不多时, Redis就会使用整数集合作为集合键的底层实现。

整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素。
每个intset.h/intset结构表示一个整数集合:

contents数组是整数集合的底层实现:整数集合的每个元素都是 contents数组的个数组项(item),各个项在数组中按值的大小从小到大有序地排列,并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量,也即是 contents数组的长度。
虽然 intset结构将 contents属性声明为int8t类型的数组,但实际上 contents数组并不保存任何int8t类型的值, contents数组的真正类型取决于encoding属性的值：

        2.每当我们要将一个新元素添加到整数集合里面,并且新元素的类型比整数集合现有所有元素的类型都要长时,整数集合需要先进行升级( upgrade),然后才能将新元素添加到整数集合里面。

升级整数集合并添加新元素共分为三步进行：

• 1)根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间。
• 2)将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
• 3)将新元素添加到底层数组里面。

        3.因为每次向整数集合添加新元素都可能会引起升级,而每次升级都需要对底层数组中已有的所有元素进行类型转换,所以向整数集合添加新元素的时间复杂度为O(N)。

        4.升级之后新元素的摆放位置

因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大,所以这个新元素的值要么就大于所有现有元素,要么就小于所有现有元素:

• 在新元素小于所有现有元素的情况下,新元素会被放置在底层数组的最开头(索引0);
• 在新元素大于所有现有元素的情况下,新元素会被放置在底层数组的最末尾(索引length-1)。

        5.升级的好处
整数集合的升级策略有两个好处,一个是提升整数集合的灵活性,另一个是尽可能地节约内存。

        6.降级

整数集合不支持降级操作,一旦对数组进行了升级,编码就会一直保持升级后的状态。

第七章：压缩列表

        1.压缩列表( ziplist)是列表键和哈希键的底层实现之ー。当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么 Redis就会使用压缩列表来做列表键的底层实现。

        2.压缩列表是 Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块组成的顺序型( sequential)数据结构。一个压缩列表可以包含任意多个节点(enty),每个节点可以保存一个字节数组或者一个整数值。

        3.每个压缩列表节点可以保存一个字节数组或者一个整数值,其中,字节数组可以是以下三种长度的其中一种:

• 长度小于等于63(26-1)字节的字节数组;
• 长度小于等于16383(214-1)字节的字节数组;
• 长度小于等于4294967295(232-1)字节的字节数组

        而整数值则可以是以下六种长度的其中一种:

• 4位长,介于0至12之间的无符号整数;
• 1字节长的有符号整数;
• 3字节长的有符号整数;
• int16_t类型整数;
• int32_t类型整数;
• int64_t类型整数。

        4.每个压缩列表节点都由 previous_entry_length、 encoding、 content三个部分组成,如图7-4所示。

节点的 previous_entry_length属性以字节为单位,记录了压缩列表中前一个节点的长度。 previous_entry_length属性的长度可以是1字节或者5字节。

• 如果前一节点的长度小于254字节,那么 previous_entry_length属性的长度为1字节:前一节点的长度就保存在这一个字节里面。
• 如果前一节点的长度大于等于254字节,那么 previous_entry_length属性的长度为5字节:其中属性的第一字节会被设置为0xFE(十进制值254),而之后的四个字节则用于保存前一节点的长度。

节点的 encoding属性记录了节点的 content属性所保存数据的类型以及长度:

• 一字节、两字节或者五字节长,值的最高位为00、01或者10的是字节数组编码这种编码表示节点的 content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录;
• 一字节长,值的最高位以11开头的是整数编码:这种编码表示节点的 content属性保存着整数值,整数值的类型和长度由编码除去最高两位之后的其他位记录;

节点的 content属性负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的 encoding属性决定。

        5.因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作,而每次空间重分配的最坏复杂度为O(N)所以连锁更新的最坏复杂度为O(N*N)。
要注意的是,尽管连锁更新的复杂度较高,但它真正造成性能问题的几率是很低的:

• 首先,压缩列表里要恰好有多个连续的、长度介于250字节至253字节之间的节点,连锁更新才有可能被引发,在实际中,这种情况并不多见;
• 其次,即使出现连锁更新,但只要被更新的节点数量不多,就不会对性能造成任何影响:比如说,对三五个节点进行连锁更新是绝对不会影响性能的;

因为以上原因, ziplistpush等命令的平均复杂度仅为O(N),在实际中,我们可以放心地使用这些函数,而不必担心连锁更新会影响压缩列表的性能。

第八章：对象

        1.通过这五种不同类型的对象, Redis可以在执行命令之前,根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处是,我们可以针对不同的使用场景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。
        除此之外, Redis的对象系统还实现了基于引用计数技术的内存回收机制,当程序不再使用某个对象的时候,这个对象所占用的内存就会被自动释放;另外, Redis还通过引用计数技术实现了对象共享机制,这一机制可以在适当的条件下,通过让多个数据库键共享同个对象来节约内存。
        最后, Redis的对象带有访问时间记录信息,该信息可以用于计算数据库键的空转时长,在服务器启用了 maxmemory功能的情况下,空转时长较大的那些键可能会优先被服务器删除。

        2.Redis中的每个对象都由一个redisObject结构表示,该结构中和保存数据有关的个属性分别是type属性、encoding属性和ptr属性：

        3.TYPE命令的实现方式也与此类似,当我们对一个数据库键执行TYPE命令时,命令返回的结果为数据库键对应的值对象的类型,而不是键对象的类型:

        4.对象的ptr指针指向对象的底层实现数据结构,而这些数据结构由对象的 encoding属性决定。
encoding属性记录了对象所使用的编码,也即是说这个对象使用了什么数据结构作为对象的底层实现,这个属性的值可以是表8-3列出的常量的其中一个。

       

        5.通过encoding属性来设定对象所使用的编码,而不是为特定类型的对象关联一种固定的编码,极大地提升了 Redis的灵活性和效率,因为 Redis可以根据不同的使用场景来为一个对象设置不同的编码,从而优化对象在某一场景下的效率。

        6.如果字符串对象保存的是一个字符串值,并且这个字符串值的长度小于等于32字节那么字符串对象将使用 embstr编码的方式来保存这个字符串值。
embar编码是专门用于保存短字符串的一种优化编码方式,这种编码和raw编码一样,都使用 redisobject结构和 sasha结构来表示字符串对象,但raw编码会调用两次内存分配函数来分别创建 redisobject结构和 sdshdr结构,而 embstr编码则通过调用一次内存分配函数来分配一块连续的空间,空间中依次包含 redisobject和 sdshdr两个结构。

        7.可以用long double类型表示的浮点数在 Redis中也是作为字符串值来保存的。如果我们要保存一个浮点数到字符串对象里面,那么程序会先将这个浮点数转换成字符串值,然后再保存转换所得的字符串值。

在有需要的时候,程序会将保存在字符串对象里面的字符串值转换回浮点数值,执行某些操作,然后再将执行操作所得的浮点数值转换回字符串值,并继续保存在字符串对象里面。

        8.int编码的字符串对象和 embstr编码的字符串对象在条件满足的情况下,会被转换为raw编码的字符串对象。
对于int编码的字符串对象来说,如果我们向对象执行了一些命令,使得这个对象保存的不再是整数值,而是一个字符串值,那么字符串对象的编码将从int变为raw。

        9.另外,因为 Redis没有为 embar编码的字符串对象编写任何相应的修改程序(只有int编码的字符串对象和raw编码的字符串对象有这些程序),所以 embstr编码的字符串对象实际上是只读的。当我们对 embstr编码的字符串对象执行任何修改命令时,程序会先将对象的编码从 embstr转换成raw,然后再执行修改命令。因为这个原因, embstr编码的字符串对象在执行修改命令之后,总会变成一个raw编码的字符串对象。

        10.注意,linkedlist编码的列表对象在底层的双端链表结构中包含了多个字符串对象,这种嵌套字符串对象的行为在稍后介绍的哈希对象、集合对象和有序集合对象中都会出现,字符串对象是 Redis五种类型的对象中唯一一种会被其他四种类型对象嵌套的对象。

        11.当列表对象可以同时满足以下两个条件时,列表对象使用ziplist编码:

• 列表对象保存的所有字符串元素的长度都小于64字节;
• 列表对象保存的元素数量小于512个;不能满足这两个条件的列表对象需要使用linkedlist编码。

        12.哈希对象的编码可以是ziplist或者 hashtable。
ziplist编码的哈希对象使用压缩列表作为底层实现,每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推人到压缩列表表尾,因此:

• 保存了同一键值对的两个节点总是紧挨在一起,保存键的节点在前,保存值的节点在后;
• 先添加到哈希对象中的键值对会被放在压缩列表的表头方向,而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。

        13.hashtable编码的哈希对象使用字典作为底层实现,哈希对象中的每个键值对都使用一个字典键值对来保存:

• 字典的每个键都是一个字符串对象,对象中保存了键值对的键;
• 字典的每个值都是一个字符串对象,对象中保存了键值对的值。

        14.当哈希对象可以同时满足以下两个条件时,哈希对象使用 ziplist编码:

• 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节;
• 哈希对象保存的键值对数量小于512个;不能满足这两个条件的哈希对象需要使用hashtable编码。

        15.集合对象的编码可以是 intset或者 hashtable。
inset编码的集合对象使用整数集合作为底层实现,集合对象包含的所有元素都被保存在整数集合里面。

        16.另一方面, hashtable编码的集合对象使用字典作为底层实现,字典的每个键都是一个字符串对象,每个字符串对象包含了一个集合元素,而字典的值则全部被设置为NULL。

        17.当集合对象可以同时满足以下两个条件时,对象使用 intset编码:

• 集合对象保存的所有元素都是整数值;
• 集合对象保存的元素数量不超过512个。

不能满足这两个条件的集合对象需要使用 hashtable编码。

        18.有序集合的编码可以是ziplist或者skiplist。
ziplist编码的压缩列表对象使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员( member),而第二个元素则保存元素的分值( score)。
压缩列表内的集合元素按分值从小到大进行排序,分值较小的元素被放置在靠近表头的方向,而分值较大的元素则被放置在靠近表尾的方向。

        19.skiplist编码的有序集合对象使用zse结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表。

        20.Redis除了会根据值对象的类型来判断键是否能够执行指定命令之外,还会根据值对象的编码方式,选择正确的命令实现代码来执行命令。

        21.因为C语言并不具备自动内存回收功能,所以Reds在自己的对象系统中构建了一个引用计数( reference counting)技术实现的内存回收机制,通过这一机制,程序可以通过跟踪对象的引用计数信息,在适当的时候自动释放对象并进行内存回收。

        22.除了用于实现引用计数内存回收机制之外,对象的引用计数属性还带有对象共享的作用。

第九章：数据库

        1.Redis服务器将所有数据库都保存在服务器状态 redis.h/ redisServer结构的db数组中,db数组的每个项都是一个 redis.h/redisDb结构,每个redisDb结构代表一个数据库。

        2.在初始化服务器时,程序会根据服务器状态的 dbnum属性来决定应该创建多少个数据库:dbnum属性的值由服务器配置的 database选项决定,默认情况下,该选项的值为16,所以 Redis服务器默认会创建16个数据库。

        3.Redis是一个键值对(key- value pair)数据库服务器,服务器中的每个数据库都由一个 redis.h/ redisDb结构表示,其中, redis Db结构的dict字典保存了数据库中的所有键值对,我们将这个字典称为键空间( key space)键空间和用户所见的数据库是直接对应的:

• 键空间的键也就是数据库的键,每个键都是一个字符串对象。
• 键空间的值也就是数据库的值,每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种 Redis对象。

        4.虽然有多种不同单位和不同形式的设置命令,但实际上 EXPIRE、 PEXPIRE、 EXPIREAT三个命令都是使用 PEXPIREAT命令来实现的:无论客户端执行的是以上四个命令中的哪一个,经过转换之后,最终的执行效果都和执行 PEXPIREAT命令一样。

        5.redisDb结构的expires字典保存了数据库中所有键的过期时间,我们称这个字典为过期字典:

• 过期字典的键是一个指针,这个指针指向键空间中的某个键对象(也即是某个数据库键)。
• 过期字典的值是一个 long long类型的整数,这个整数保存了键所指向的数据库键的过期时间—一个毫秒精度的UNIX时间戳。

        6.PERSIST命令可以移除一个键的过期时间:PERSIST命令就是 PEXPIREAT命令的反操作: PERSIST命令在过期字典中查找给定的键,并解除键和值(过期时间)在过期字典中的关联。

        7.过期键删除策略:

• 定时删除:在设置键的过期时间的同时,创建一个定时器( timer),让定时器在键的过期时间来临时,立即执行对键的删除操作。
• 惰性删除:放任键过期不管,但是每次从键空间中获取键时,都检查取得的键是否过期,如果过期的话,就删除该键;如果没有过期,就返回该键。
• 定期删除:每隔一段时间,程序就对数据库进行一次检查,删除里面的过期键。至于要删除多少过期键,以及要检查多少个数据库,则由算法决定。

在这三种策略中,第一种和第三种为主动删除策略,而第二种则为被动删除策略。

        8.Redis的过期键删除策略:Redis服务器实际使用的是惰性删除和定期删除两种策略:通过配合使用这两种删除策略,服务器可以很好地在合理使用CPU时间和避免浪费内存空间之间取得平衡。

        惰性删除策略的实现:过期键的惰性删除策略由db.c/ expireIfNeeded函数实现,所有读写数据库的Redis命令在执行之前都会调用 expireIfNeeded函数对输入键进行检查

• 如果输入键已经过期,那么expireIfNeeded函数将输入键从数据库中删除。
• 如果输入键未过期,那么expireIfNeeded函数不做动作。

        定期删除策略的实现:过期键的定期删除策略由redis.c/activeExpireCycle函数实现,每当 Redis的服务器周期性操作redis.c/ serverCron函数执行时, activeExpireCycle函数就会被调用,它在规定的时间内,分多次遍历服务器中的各个数据库,从数据库的 expires字典中随机检查一部分键的过期时间,并删除其中的过期键。

        activeExpireCycle函数的工作模式可以总结如下:

• 函数每次运行时,都从一定数量的数据库中取出一定数量的随机键进行检查,并删除其中的过期键。
• 全局变量 current_db会记录当前activeExpireCycle函数检查的进度,并在下一次activeExpireCycle函数调用时,接着上一次的进度进行处理。
• 随着activeExpireCycle函数的不断执行,服务器中的所有数据库都会被检查一遍,这时函数将 current_db变量重置为0,然后再次开始新一轮的检査工作。

        9.在执行SAVE命令或者 BGSAVE命令创建一个新的RDB文件时,程序会对数据库中的键进行检查,已过期的键不会被保存到新创建的RDB文件中。

在启动 Redis服务器时,如果服务器开启了RDB功能,那么服务器将对RDB文件进行载入:

• 如果服务器以主服务器模式运行,过期键则会被忽略。
• 如果服务器以从服务器模式运行,不论是否过期,都会被载入到数据库中。

当过期键被惰性删除或者定期删除之后,程序会向AOF文件追加(append)一条DEL命令,来显式地记录该键已被删除。

和生成RDB文件时类似,在执行AOF重写的过程中,程序会对数据库中的键进行检查,已过期的键不会被保存到重写后的AOF文件中。

        10.当服务器运行在复制模式下时,从服务器的过期键删除动作由主服务器控制。

        11.数据库通知是 Redis28版本新增加的功能,这个功能可以让客户端通过订阅给定的频道或者模式,来获知数据库中键的变化,以及数据库中命令的执行情况。

 第十章：RDB持久化

        1.RDB持久化既可以手动执行,也可以根据服务器配置选项定期执行,该功能可以将某个时间点上的数据库状态保存到一个RDB文件中。
        RDB持久化功能所生成的RDB文件是一个经过压缩的二进制文件,通过该文件可以还原生成RDB文件时的数据库状态。

        2.有两个 Redis命令可以用于生成RDB文件,一个是SAVE,另一个是 BGSAVE。
SAVE命令会阻塞 Redis服务器进程,直到RDB文件创建完毕为止,在服务器进程阻塞期间,服务器不能处理任何命令请求。和SAVE命令直接阻塞服务器进程的做法不同, BGSAVE命令会派生出一个子进程,然后由子进程负责创建RDB文件,服务器进程(父进程)继续处理命令请求。

        3.和使用SAVE命令或者 BGSAVE命令创建RDB文件不同,RDB文件的载入工作是在服务器启动时自动执行的,所以 Redis并没有专门用于载入RDB文件的命令,只要 Redis服务器在启动时检测到RDB文件存在,它就会自动载入RDB文件。

        4.另外值得一提的是,因为AOF文件的更新频率通常比RDB文件的更新频率高,所以:

• 如果服务器开启了AOF持久化功能,那么服务器会优先使用AOF文件来还原数据库状态。
• 只有在AOF持久化功能处于关闭状态时,服务器才会使用RDB文件来还原数据库状态。

        5.在 BGSAVE命令执行期间服务器处理SAVE、 BGSAVE、 BGREWRITEAOF三个命令的方式会和平时有所不同。

        6.服务器在载入RDB文件期间,会一直处于阻塞状态,直到载入工作完成为止。

        7.当Reds服务器启动时,用户可以通过指定配置文件或者传入启动参数的方式设置save选项,如果用户没有主动设置save选项,那么服务器会为save选项设置默认条件:

        8.服务器程序会根据save选项所设置的保存条件,设置服务器状态redisServer结构的 saveparams属性:saveparams属性是一个数组,数组中的每个元素都是一个 saveparam结构,每个param结构都保存了一个save选项设置的保存条件。

 除了saveparams数组之外,服务器状态还维持着一个 dirty计数器,以及一个lastsave属性:

• dirty计数器记录距离上一次成功执行SAVE命令或者 BGSAVE命令之后,服务器对数据库状态(服务器中的所有数据库)进行了多少次修改(包括写入、删除、更新等操作)。
• lastsave属性是一个UNIX时间戳,记录了服务器上一次成功执行SAE命令或者 BGSAVE命令的时间。

        9.Redis的服务器周期性操作函数 servercron默认每隔100毫秒就会执行一次,该函数用于对正在运行的服务器进行维护,它的其中一项工作就是检查save选项所设置的保存条件是否已经满足,如果满足的话,就执行BGSAVE命令。

        10.RDB文件的最开头是REDIS部分,这个部分的长度为5字节,保存着"REDIS"五个字符。通过这五个字符,程序可以在载入文件时,快速检查所载入的文件是否RDB文件。

db_version长度为4字节,它的值是一个字符串表示的整数,这个整数记录了RDB文件的版本号。

databases部分包含着零个或任意多个数据库,以及各个数据库中的键值对数据:

• 如果服务器的数据库状态为空(所有数据库都是空的),那么这个部分也为空,长度为0字节。
• 如果服务器的数据库状态为非空(有至少一个数据库非空),那么这个部分也为非空根据数据库所保存键值对的数量、类型和内容不同,这个部分的长度也会有所不同。

EOF常量的长度为1字节,这个常量标志着RDB文件正文内容的结束,当读入程序遇到这个值的时候,它知道所有数据库的所有键值对都已经载人完毕了。

check_sum是一个8字节长的无符号整数,保存着一个校验和,这个校验和是程序通过对 REDIS、db_version、 databases、EOF四个部分的内容进行计算得出的。服务器在载入RDB文件时,会将载入数据所计算出的校验和与 check_sum所记录的校验和进行对比,以此来检査RDB文件是否有出错或者损坏的情况出现。

        11.每个非空数据库在RDB文件中都可以保存为 SELECTDB、 db_number、 key_value_pairs三个部分。

SELECTDB常量的长度为1字节,当读入程序遇到这个值的时候,它知道接下来要读入的将是一个数据库号码。

db_number保存着一个数据库号码,根据号码的大小不同,这个部分的长度可以是1字节、2字节或者5字节。

key_value_pairs部分保存了数据库中的所有键值对数据,如果键值对带有过期间,那么过期时间也会和键值对保存在一起。根据键值对的数量、类型、内容以及是否有过期时间等条件的不同, key_value_pairs部分的长度也会有所不同。 

不带过期时间的键值对在RDB文件中由TYPE、key、 value三部分组成,带有过期时间的键值对新增的EXPIRETIME_MS和ms。

第十一章：AOF持久化

        1.除了RDB持久化功能之外, Redis还提供了AOF(Append Only File)持久化功能。与RDB持久化通过保存数据库中的键值对来记录数据库状态不同,AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的。

        2.因为服务器在处理文件事件时可能会执行写命令,使得一些内容被追加到aof_buf缓冲区里面,所以在服务器每次结束一个事件循环之前,它都会调用flushappendOnlyFile函数,考虑是否需要将 aof_buf缓冲区中的内容写入和保存到AOF文件里面。

        3.flushAppendOnlyFile函数的行为由服务器配置的 appendfsync选项的值来决定,各个不同值产生的行为。如果用户没有主动为appendfsync选项设置值,那么 appendfsync选项的默认值为everysec。

         4.文件的写入和同步
为了提高文件的写入效率,在现代操作系统中,当用户调用 write函数,将一些数据写入到文件的时候,操作系统通常会将写入数据暂时保存在一个内存缓冲区里面,等到缓冲区的空间被填满、或者超过了指定的时限之后,才真正地将缓冲区中的数据写入到磁盘里面。
这种做法虽然提高了效率,但也为写入数据带来了安全问题,因为如果计算机发生停机,那么保存在内存缓冲区里面的写入数据将会丢失。
为此,系统提供了fsync和fdatasync两个同步函数,它们可以强制让操作系统立即将缓冲区中的数据写入到硬盘里面,从而确保写入数据的安全性。

        5.AOF持久化的效率和安全性
服务器配置appendfsync选项的值直接决定AOF持久化功能的效率和安全性。

• 当appendfsync的值为 always时,服务器在每个事件循环都要将 aof buf缓冲区中的所有内容写入到AOF文件,并且同步AOF文件,所以always的效率是appendfsync选项三个值当中最慢的一个,但从安全性来说,always也是最安全的,因为即使出现故障停机,AOF持久化也只会丢失一个事件循环中所产生的命令数据。
• 当appendfsync的值为everysec时,服务器在每个事件循环都要将 aof_buf缓冲区中的所有内容写入到AOF文件,并且每隔一秒就要在子线程中对AOF文件进行一次同步。从效率上来讲, everysec模式足够快,并且就算出现故障停机,数据库也只丢失一秒钟的命令数据。
• 当appendfsync的值为no时,服务器在毎个事件循环都要将 aof_buf缓冲区中的所有内容写入到AOF文件,至于何时对AOF文件进行同步,则由操作系统控制。因为处于no模式下的flushAppendOnlyFile调用无须执行同步操作,所以该模式下的AOF文件写入速度总是最快的,不过因为这种模式会在系统缓存中积累段时间的写入数据,所以该模式的单次同步时长通常是三种模式中时间最长的。从平摊操作的角度来看,no模式和everyse模式的效率类似,当出现故障停机时,使用no模式的服务器将丢失上次同步AOF文件之后的所有写命令数据。

        6.因为AOF持久化是通过保存被执行的写命令来记录数据库状态的,所以随着服务器运行时间的流逝,AOF文件中的内容会越来越多,文件的体积也会越来越大,如果不加以控制的话,体积过大的AOF文件很可能对 Redis服务器、甚至整个宿主计算机造成影响,并且AOF文件的体积越大,使用AOF文件来进行数据还原所需的时间就越多。为了解决AOF文件体积膨胀的问题, Redis提供了AOF文件重写( rewrite)功能。通过该功能, Redis服务器可以创建一个新的AOF文件来替代现有的AOF文件,新旧两个AOF文件所保存的数据库状态相同,但新AOF文件不会包含任何浪费空间的冗余命令,所以新AOF文件的体积通常会比旧AOF文件的体积要小得多。

        7.虽然 Redis将生成新AOF文件替换旧AOF文件的功能命名为“AOF文件重写”,但实际上,AOF文件重写并不需要对现有的AOF文件进行任何读取、分析或者写入操作,这个功能是通过读取服务器当前的数据库状态来实现的。

        8.在实际中,为了避免在执行命令时造成客户端输入缓冲区溢出,重写程序在处理列表哈希表、集合、有序集合这四种可能会带有多个元素的键时,会先检查键所包含的元素数量,如果元素的数量超过了redis.h/ REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值,那么重写程序将使用多条命令来记录键的值,而不单单使用一条命令。
        在目前版本中, REDIS_AOF_REWRITE_ITEMS_PER_CMD常量的值为64,这也就是说,如果一个集合键包含了超过64个元素,那么重写程序会用多条SADD命令来记录这个集合,并且每条命令设置的元素数量也为64个。

        9.很明显,作为一种辅佐性的维护手段, Redis不希望AOF重写造成服务器无法处理请求,所以 Redis决定将AOF重写程序放到子进程里执行,这样做可以同时达到两个目的：

• 子进程进行AOF重写期间,服务器进程(父进程)可以继续处理命令请求。
• 子进程带有服务器进程的数据副本,使用子进程而不是线程,可以在避免使用锁的情况下,保证数据的安全性。

        不过,使用子进程也有一个问题需要解决,因为子进程在进行AOF重写期间,服务器进程还需要继续处理命令请求,而新的命令可能会对现有的数据库状态进行修改,从而使得服务器当前的数据库状态和重写后的AOF文件所保存的数据库状态不一致。

        10.为了解决这种数据不一致问题, Redis服务器设置了一个AOF重写缓冲区,这个缓冲区在服务器创建子进程之后开始使用,当 Redis服务器执行完一个写命令之后,它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区。

这也就是说,在子进程执行AOF重写期间,服务器进程需要执行以下三个工作：

• 1)执行客户端发来的命令。
• 2)将执行后的写命令追加到AOF缓冲区。
• 3)将执行后的写命令追加到AOF重写缓冲区。

这样一来可以保证：

• AOF缓冲区的内容会定期被写入和同步到AOF文件,对现有AOF文件的处理工作会如常进行。
• 从创建子进程开始,服务器执行的所有写命令都会被记录到AOF重写缓冲区里面。

当子进程完成AOF重写工作之后,它会向父进程发送一个信号,父进程在接到该信号之后,会调用一个信号处理函数,并执行以下工作：

• 1)将AOF重写缓冲区中的所有内容写入到新AOF文件中,这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致。
• 2)对新的AOF文件进行改名,原子地(atomic)覆盖现有的AOF文件,完成新旧两个AOF文件的替换。

这个信号处理函数执行完毕之后,父进程就可以继续像往常一样接受命令请求了。 

在整个AOF后台重写过程中,只有信号处理函数执行时会对服务器进程(父进程)造成阻塞,在其他时候,AOF后台重写都不会阻塞父进程,这将AOF重写对服务器性能造成的影响降到了最低。

第十二章：事件

        1.Redis服务器是一个事件驱动程序,服务器需要处理以下两类事件：

• 文件事件( file event): Redis服务器通过套接字与客户端(或者其他 Redis服务器)进行连接,而文件事件就是服务器对套接字操作的抽象。服务器与客户端(或者其他服务器)的通信会产生相应的文件事件,而服务器则通过监听并处理这些事件来完成一系列网络通信操作。
• 时间事件( time event): Redis服务器中的一些操作(比如 serverCron函数)需要在给定的时间点执行,而时间事件就是服务器对这类定时操作的抽象。

        2.Redis基于 Reactor模式开发了自己的网络事件处理器:这个处理器被称为文件事件处理器( file event handler):

• 文件事件处理器使用I/O多路复用( multiplexing)程序来同时监听多个套接字,并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
• 当被监听的套接字准备好执行连接应答( accept)、读取(read)、写人( write)、关闭( close)等操作时,与操作相对应的文件事件就会产生,这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

虽然文件事件处理器以单线程方式运行,但通过使用I/O多路复用程序来监听多个套接字,文件事件处理器既实现了高性能的网络通信模型,又可以很好地与 Redis服务器中其他同样以单线程方式运行的模块进行对接,这保持了 Redis内部单线程设计的简单性。

         3.I/O多路复用程序负责监听多个套接字并向文件事件分派器传送那些产生了事件的套接字。
尽管多个文件事件可能会并发地出现,但IO多路复用程序总是会将所有产生事件的套接字都放到一个队列里面,然后通过这个队列,以有序(sequentially)、同步(synchronously)、每次一个套接字的方式向文件事件分派器传送套接字。当上一个套接字产生的事件被处理完毕之后(该套接字为事件所关联的事件处理器执行完毕),IO多路复用程序才会继续向文件事件分派器传送下一个套接字。

         4.Redis的I/O多路复用程序的所有功能都是通过包装常见的 select、epoll、 export和 kqueue这些I/O多路复用函数库来实现的。Redis在I/O多路复用程序的实现源码中用#include宏定义了相应的规则,程序会在编译时自动选择系统中性能最高的I/O多路复用函数库来作为Reds的IO多路复用程序的底层实现。

        5.如果一个套接字又可读又可写的话,那么服务器将先读套接字,后写套接字。

        6.Redis为文件事件编写了多个处理器,这些事件处理器分别用于实现不同的网络通信需求,比如说：

• 为了对连接服务器的各个客户端进行应答,服务器要为监听套接字关联连接应答处理器。
• 为了接收客户端传来的命令请求,服务器要为客户端套接字关联命令请求处理器。
• 为了向客户端返回命令的执行结果,服务器要为客户端套接字关联命令回复处理器。
• 当主服务器和从服务器进行复制操作时,主从服务器都需要关联特别为复制功能编写的复制处理器。

在这些事件处理器里面,服务器最常用的要数与客户端进行通信的连接应答处理器、命令请求处理器和命令回复处理器。

         7.Redis的时间事件分为以下两类:

• 定时事件:让一段程序在指定的时间之后执行一次。
• 周期性事件:让一段程序每隔指定时间就执行一次。

        8.一个时间事件主要由以下三个属性组成：

• id:服务器为时间事件创建的全局唯一ID(标识号)。ID号按从小到大的顺序递增,新事件的ID号比旧事件的ID号要大。
• when:毫秒精度的UNX时间戳,记录了时间事件的到达( arrive)时间。
• timeProc:时间事件处理器,一个函数。当时间事件到达时,服务器就会调用相应的处理器来处理事件。

        9.一个时间事件是定时事件还是周期性事件取决于时间事件处理器的返回值:

• 口如果事件处理器返回ae.h/AE_NOMORE,那么这个事件为定时事件:该事件在达到一次之后就会被删除,之后不再到达。
• 口如果事件处理器返回一个非AE_NOMORE的整数值,那么这个事件为周期性时间当一个时间事件到达之后,服务器会根据事件处理器返回的值,对时间事件的when属性进行更新,让这个事件在一段时间之后再次到达,并以这种方式一直更新并运行下去。

        10.目前版本的 Redis只使用周期性事件,而没有使用定时事件。

        11.服务器将所有时间事件都放在一个无序链表中,每当时间事件执行器运行时,它就遍历整个链表,查找所有已到达的时间事件,并调用相应的事件处理器。

         12.无序链表并不影响时间事件处理器的性能，在目前版本中,正常模式下的 Redis服务器只使用 servercron一个时间事件,而在 benchmark模式下,服务器也只使用两个时间事件。在这种情况下,服务器几乎是将无序链表退化成一个指针来使用,所以使用无序链表来保存时间事件,并不影响事件执行的性能。

        13.持续运行的 Redis服务器需要定期对自身的资源和状态进行检查和调整,从而确保服务器可以长期、稳定地运行,这些定期操作由redis.c/serverCron函数负责执行,它的主要工作包括口更新服务器的各类统计信息,比如时间、内存占用、数据库占用情况等。

• 清理数据库中的过期键值对。
• 关闭和清理连接失效的客户端。
• 尝试进行AOF或RDB持久化操作。
• 如果服务器是主服务器,那么对从服务器进行定期同步.
• 如果处于集群模式,对集群进行定期同步和连接测试。

Redis服务器以周期性事件的方式来运行 servercron函数,在服务器运行期间,每隔一段时间, servercron就会执行一次,直到服务器关闭为止。
在 Redis2.6版本,服务器默认规定 servercron每秒运行10次,平均每间隔100毫秒运行一次。
从 Redis28开始,用户可以通过修改hz选项来调整 servercron的每秒执行次数。

         14.对文件事件和时间事件的处理都是同步、有序、原子地执行的,服务器不会中途中断事件处理,也不会对事件进行抢占,因此,不管是文件事件的处理器,还是时间事件的处理器,它们都会尽可地减少程序的阻塞时间,并在有需要时主动让出执行权,从而降低造成事件饥饿的可能性。

因为时间事件在文件事件之后执行,并且事件之间不会出现抢占,所以时间事件的实际处理时间,通常会比时间事件设定的到达时间稍晚一些。

第十三章：客户端

        1.Redis服务器是典型的一对多服务器程序:一个服务器可以与多个客户端建立网络连接,每个客户端可以向服务器发送命令请求,而服务器则接收并处理客户端发送的命令请求,并向客户端返回命令回复。
通过使用由IO多路复用技术实现的文件事件处理器, Redis服务器使用单线程单进程的方式来处理命令请求,并与多个客户端进行网络通信。
对于每个与服务器进行连接的客户端,服务器都为这些客户端建立了相应的redis.h/redisClient结构(客户端状态),这个结构保存了客户端当前的状态信息,以及执行相关功能时需要用到的数据结构。

        2.Redis服务器状态结构的 clients属性是一个链表,这个链表保存了所有与服务器连接的客户端的状态结构,对客户端执行批量操作,或者查找某个指定的客户端,都可以通过遍历clients链表来完成。

        3.客户端状态包含的属性可以分为两类:

• 一类是比较通用的属性,这些属性很少与特定功能相关,无论客户端执行的是什么工作,它们都要用到这些属性。
• 另外一类是和特定功能相关的属性,比如操作数据库时需要用到的db属性和dictid属性,执行事务时需要用到的mstate属性,以及执行 WATCH命令时需要用到的 watched_keys属性等等。

        4.根据客户端类型的不同,fd属性的值可以是-1或者是大于-1的整数:

• 伪客户端( fake client)的fd属性的值为-1:伪客户端处理的命令请求来源于AOF文件或者Lua脚本,而不是网络,所以这种客户端不需要套接字连接,自然也不需要记录套接字描述符。目前 Redis服务器会在两个地方用到伪客户端,一个用于载入AOF文件并还原数据库状态,而另一个则用于执行Lua脚本中包含的 Redis命令。
• 普通客户端的fd属性的值为大于-1的整数:普通客户端使用套接字来与服务器进行通信,所以服务器会用fd属性来记录客户端套接字的描述符。因为合法的套接字描述符不能是-1,所以普通客户端的套接字描述符的值必然是大于-1的整数。

        5.在默认情况下,一个连接到服务器的客户端是没有名字的。使用 CLIENT setname命令可以为客户端设置一个名字,让客户端的身份变得更清晰。

        6.标志：客户端的标志属性flags记录了客户端的角色(role),以及客户端目前所处的状态。

        7.PUBSUB命令和SCRIPT LOAD命令的特殊性
通常情况下, Redis只会将那些对数据库进行了修改的命令写入到AOF文件,并复制到各个从服务器。如果一个命令没有对数据库进行任何修改,那么它就会被认为是只读命令,这个命令不会被写入到AOF文件,也不会被复制到从服务器。
以上规则适用于绝大部分 Redis命令,但 PUBSUB命令和 SCRIPT LOAD命令是其中的例外。 PUBSUB命令虽然没有修改数据库,但 PUBSUB命令向频道的所有订阅者发送消息这一行为带有副作用,接收到消息的所有客户端的状态都会因为这个命令而改变。

        8.客户端状态的输入缓冲区用于保存客户端发送的命令请求，输入缓冲区的大小会根据输入内容动态地缩小或者扩大,但它的最大大小不能超过lGB,否则服务器将关闭这个客户端。

        9.在服务器将客户端发送的命令请求保存到客户端状态的 querybuf属性之后,服务器将对命令请求的内容进行分析,并将得出的命令参数以及命令参数的个数分别保存到客户端状态的argv属性和argc属性。

argv属性是一个数组,数组中的每个项都是一个字符串对象,其中argv[0]是要执行的命令,而之后的其他项则是传给命令的参数。
argc属性则负责记录argv数组的长度。

针对命令表的查找操作不区分输入字母的大小写,所以无论argv[0]是"SET"、"set"或者"SeT"等等,查找的结果都是相同的。

        10.执行命令所得的命令回复会被保存在客户端状态的输出缓冲区里面,每个客户端都有两个输出缓冲区可用,一个缓冲区的大小是固定的,另一个缓冲区的大小是可变的:

• 固定大小的缓冲区用于保存那些长度比较小的回复,比如oK、简短的字符串值、整数值、错误回复等等。(16kb字节数组)
• 可变大小的缓冲区用于保存那些长度比较大的回复,比如一个非常长的字符串值一个由很多项组成的列表,一个包含了很多元素的集合等等。（链表）

        11.客户端状态的authenticated属性用于记录客户端是否通过了身份验证：

• 如果authenticated的值为0,那么表示客户端未通过身份验证;如果 authenticated的值为1,那么表示客户端已经通过了身份验证。
• 当客户端authenticated属性的值为0时,除了AUTH命令之外,客户端发送的所有其他命令都会被服务器拒绝执行。

        12.服务器使用两种模式来限制客户端输出缓冲区的大小:

• 硬性限制(hard limit):如果输出缓冲区的大小超过了硬性限制所设置的大小,那么服务器立即关闭客户端。
• 软性限制(soft limit):如果输出缓冲区的大小超过了软性限制所设置的大小,但还没超过硬性限制,那么服务器将使用客户端状态结构的obuf_soft_limit_reached_time属性记录下客户端到达软性限制的起始时间;之后服务器会继续监视客户端,如果输出缓冲区的大小一直超出软性限制,并且持续时间超过服务器设定的时长,那么服务器将关闭客户端;相反地,如果输出缓冲区的大小在指定时间之内,不再超出软性限制,那么客户端就不会被关闭,并且obuf_soft_limit_reached_time属性的值也会被清零。

第十四章：服务器

        1.Redis服务器的命令请求来自 Redis客户端,当用户在客户端中键入一个命令请求时,客户端会将这个命令请求转换成协议格式,然后通过连接到服务器的套接字,将协议格式的命令请求发送给服务器。

        2.当客户端与服务器之间的连接套接字因为客户端的写人而变得可读时,服务器将调用命令请求处理器来执行以下操作：

• 1)读取套接字中协议格式的命令请求,并将其保存到客户端状态的输入缓冲区里面。
• 2)对输入缓冲区中的命令请求进行分析,提取出命令请求中包含的命令参数,以及命令参数的个数,然后分别将参数和参数个数保存到客户端状态的argv属性和argc属性里面。
• 3)调用命令执行器,执行客户端指定的命令。

之后,分析程序将对输入缓冲区中的协议进行分析:并将得出的分析结果保存到客户端状态的argv属性和argc属性里面。之后,服务器将通过调用命令执行器来完成执行命令所需的余下步骤。

        3.命令执行器要做的第一件事就是根据客户端状态的argv[0]参数,在命令表(commandtable)中查找参数所指定的命令,并将找到的命令保存到客户端状态的cmd属性里面。

        4.Redis服务器中有不少功能需要获取系统的当前时间,而每次获取系统的当前时间都需要执行一次系统调用,为了减少系统调用的执行次数,服务器状态中的 unixtime属性和mtime属性被用作当前时间的缓存:

因为 serverCron函数默认会以每100毫秒一次的频率更新 unixtime属性和mtime属性,所以这两个属性记录的时间的精确度并不高:

• 服务器只会在打印日志、更新服务器的LRU时钟、决定是否执行持久化任务、计算服务器上线时间( uptime)这类对时间精确度要求不高的功能上。
• 对于为键设置过期时间、添加慢査询日志这种需要高精确度时间的功能来说,服务器还是会再次执行系统调用,从而获得最准确的系统当前时间。

        5.每个Redis对象都会有一个lru属性,这个lru属性保存了对象最后一次被命令访问的时间。

        6.serverCron函数默认会以每10秒一次的频率更新lruclock属性的值,因为这个时钟不是实时的,所以根据这个属性计算出来的LRU时间实际上只是一个模糊的估算值。

        7.serverCron函数中的trackOperationsPerSecond函数会以每100毫秒一次的频率执行,这个函数的功能是以抽样计算的方式,估算并记录服务器在最近一秒钟处理的命令请求数量。

         8.更新服务器内存峰值记录：每次 serverCron函数执行时,程序都会查看服务器当前使用的内存数量,并与stat_peak_memory保存的数值进行比较,如果当前使用的内存数量比stat_peak_memory属性记录的值要大,那么程序就将当前使用的内存数量记录到stat_peak_memory属性里面。

        9.在启动服务器时,Redis会为服务器进程的SIGTERM信号关联处理器sigtermHandler函数,这个信号处理器负责在服务器接到SIGTERM信号时,打开服务器状态的 shutdown_asap标识。每次serverCron函数运行时,程序都会对服务器状态的 shutdown_asap属性进行检查,并根据属性的值决定是否关闭服务器。

        10.从日志里面可以看到,服务器在关闭自身之前会进行RDB持久化操作,这也是服务器拦截SIGTERM信号的原因,如果服务器一接到SIGTERM信号就立即关闭,那么它就没办法执行持久化操作了。

        11.serverCron函数每次执行都会调用clientsCron函数, clientsCron函数会对一定数量的客户端进行以下两个检查:

• 如果客户端与服务器之间的连接已经超时(很长一段时间里客户端和服务器都没有互动),那么程序释放这个客户端。
• 如果客户端在上一次执行命令请求之后,输入缓冲区的大小超过了一定的长度,那么程序会释放客户端当前的输入缓冲区,并重新创建一个默认大小的输入缓冲区从而防止客户端的输入缓冲区耗费了过多的内存。

        12.serverCron函数每次执行都会调用databasesCron函数,这个函数会对服务器中的一部分数据库进行检查,删除其中的过期键,并在有需要时,对字典进行收缩操作。

        13.检查持久化操作的运行状态

         15.初始化服务器的第一步就是创建一个struct redisServer类型的实例变量server作为服务器的状态,并为结构中的各个属性设置默认值。

以下是 initServerConfig函数完成的主要工作:

• 设置服务器的运行ID。
• 设置服务器的默认运行频率。
• 设置服务器的默认配置文件路径。
• 设置服务器的运行架构。
• 设置服务器的默认端口号。
• 设置服务器的默认RDB持久化条件和AOF持久化条件。
• 初始化服务器的LRU时钟。
• 创建命令表。

当initServerConfig函数执行完毕之后,服务器就可以进入初始化的第二个阶段——载人配置选项。

服务器在载入用户指定的配置选项,并对server状态进行更新之后,服务器就可以进入初始化的第三个阶段一初始化服务器数据结构。

当初始化服务器进行到这一步,服务器将调用initServer函数,为以上提到的数据结构分配内存,并在有需要时,为这些数据结构设置或者关联初始化值。

服务器选择了将server状态的初始化分为两步进行, initServerConfig函数主要负责初始化一般属性,而 initServer函数主要负责初始化数据结构。

第十五章：复制

• 步骤1:设置主服务器的地址和端口
• 步骤2:建立套接字连接
• 步骤3:发送PING命令
• 步骤4:身份验证
• 步骤5:发送端口信息
• 步骤6:同步
• 步骤7:命令传播

        1.旧版复制功能的缺陷

在Redis中,从服务器对主服务器的复制可以分为以下两种情况：

• 初次复制:从服务器以前没有复制过任何主服务器,或者从服务器当前要复制的主服务器和上一次复制的主服务器不同。
• 断线后重复制:处于命令传播阶段的主从服务器因为网络原因而中断了复制,但从服务器通过自动重连接重新连上了主服务器,并继续复制主服务器。对于初次复制来说,旧版复制功能能够很好地完成任务,但对于断线后重复制来说,旧版复制功能虽然也能让主从服务器重新回到一致状态,但效率却非常低。

        2.SYNC命令是一个非常耗费资源的操作
每次执行SYMC命令,主从服务器需要执行以下动作：

• 主服务器需要执行 BGSAVE命令来生成RDB文件,这个生成操作会耗费主服务器大量的CPU、内存和磁盘IO资源。
• 主服务器需要将自己生成的RDB文件发送给从服务器,这个发送操作会耗费主从服务器大量的网络资源(带宽和流量),并对主服务器响应命令请求的时间产生影响。
• 接收到RDB文件的从服务器需要载入主服务器发来的RDB文件,并且在载入期间,从服务器会因为阻塞而没办法处理命令请求。

因为SYNC命令是一个如此耗费资源的操作,所以 Redis有必要保证在真正有需要时才执行SYNC命令。

        3.部分重同步的实现：部分重同步功能由以下三个部分构成：

• 主服务器的复制偏移量(replication offset)和从服务器的复制偏移量。
• 主服务器的复制积压缓冲区(replication backlog)。
• 服务器的运行ID(run ID)。

        4.复制积压缓冲区是由主服务器维护的一个固定长度(fxed-size)先进先出(FIFO)队列,默认大小为1MB。

        5.当主服务器进行命令传播时,它不仅会将写命令发送给所有从服务器,还会将写命令入队到复制积压缓冲区里面。

        6.当从服务器重新连上主服务器时,从服务器会通过PSYNC命令将自己的复制偏移量offset发送给主服务器,主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作:

• 如果offset偏移量之后的数据(也即是偏移量offset+1开始的数据)仍然存在于复制积压缓冲区里面,那么主服务器将对从服务器执行部分重同步操作。
• 相反,如果offset偏移量之后的数据已经不存在于复制积压缓冲区,那么主服务器将对从服务器执行完整重同步操作。

         7.当从服务器对主服务器进行初次复制时,主服务器会将自己的运行ID传送给从服务器,而从服务器则会将这个运行ID保存起来。
当从服务器断线并重新连上一个主服务器时,从服务器将向当前连接的主服务器发送之前保存的运行ID：

• 如果从服务器保存的运行ID和当前连接的主服务器的运行ID相同,那么说明从服务器断线之前复制的就是当前连接的这个主服务器,主服务器可以继续尝试执行部分重同步操作。
• 相反地,如果从服务器保存的运行ID和当前连接的主服务器的运行ID并不相同,那么说明从服务器断线之前复制的主服务器并不是当前连接的这个主服务器,主服务器将对从服务器执行完整重同步操作。

        8.在命令传播阶段,从服务器默认会以每秒一次的频率,向主服务器发送命令:REPLCONF ACK 其中replication_offset是从服务器当前的复制偏移量。发送 REPLCONF ACK命令对于主从服务器有三个作用:

• 检测主从服务器的网络连接状态。
• 辅助实现min-slaves选项。
• 检测命令丢失。

        9.REPLCONF ACK命令和复制积压缓冲区都是Redis 2.8版本新增的,在 Redis 2.8版本以前,即使命令在传播过程中丢失,主服务器和从服务器都不会注意到,主服务器更不会向从服务器补发丢失的数据,所以为了保证复制时主从服务器的数据一致性,最好使用2.8或以上版本的 Redis。

第十六章：Sentinel

        1.当server1的下线时长超过用户设定的下线时长上限时,Sentinel系统就会对server1执行故障转移操作:

• 首先,Sentinel系统会挑选server1属下的其中一个从服务器,并将这个被选中的从服务器升级为新的主服务器。
• 之后,Sentinel系统会向server1属下的所有从服务器发送新的复制指令,让它们成为新的主服务器的从服务器,当所有从服务器都开始复制新的主服务器时,故障转移操作执行完毕。
• 另外,Sentinel还会继续监视已下线的server1,并在它重新上线时,将它设置为新的主服务器的从服务器。

        2.当一个 Sentinel启动时,它需要执行以下步骤：

• 1)初始化服务器。
• 2)将普通 Redis服务器使用的代码替换成 Sentinel专用代码。
• 3)初始化 Sentinel状态。
• 4)根据给定的配置文件,初始化 Sentinel的监视主服务器列表。
• 5)创建连向主服务器的网络连接。

        3.Sentinel状态中的 masters字典记录了所有被 Sentinel监视的主服务器的相关信息,其中:

• 字典的键是被监视主服务器的名字。
• 而字典的值则是被监视主服务器对应的 sentinel.c/ sentinelRedisInstance结构。

每个sentinelRedisInstance结构(后面简称“实例结构”)代表一个被 Sentinel监视的 Redis服务器实例(Instance),这个实例可以是主服务器、从服务器,或者另外一个 Sentinel。

        4.对于每个被Sentinel监视的主服务器来说, Sentinel会创建两个连向主服务器的异步网络连接：

• 一个是命令连接,这个连接专门用于向主服务器发送命令,并接收命令回复。
• 另一个是订阅连接,这个连接专门用于订阅主服务器的 sentinel:hello频道。

        5.当Sentinel将一个主服务器判断为主观下线之后,为了确认这个主服务器是否真的下线了,它会向同样监视这一主服务器的其他 Sentinel进行询问,看它们是否也认为主服务器已经进入了下线状态(可以是主观下线或者客观下线)。当 Sentinel从其他 Sentinel那里接收到足够数量的已下线判断之后, Sentinel就会将从服务器判定为客观下线,并对主服务器执行故障转移操作。

        6.Redis选举领头Sentinel的规则和方法:

• 所有在线的Sentinel都有被选为领头Sentinel的资格,换句话说,监视同一个主服务器的多个在线Sentinel中的任意一个都有可能成为领头Sentinel
• 每次进行领头Sentinel选举之后,不论选举是否成功,所有Sentinel的配置纪元( configuration epoch)的值都会自增一次。配置纪元实际上就是一个计数器,并没有什么特别的。
• 在一个配置纪元里面,所有Sentinel都有一次将某个Sentinel设置为局部领头Sentinel的机会,并且局部领头一旦设置,在这个配置纪元里面就不能再更改。
• 每个发现主服务器进入客观下线的Sentinel都会要求其他Sentinel将自己设置为局部领头Sentinel。
• 当一个 Sentinel(源Sentinel)向另一个 Sentinel(目标 Sentinel)发送SENTINEL is-master-down-by-addr命令,并且命令中的runid参数不是*符号而是源Sentinel的运行ID时,这表示源Sentinel要求目标Sentinel将前者设置为后者的局部领头Sentinel。
• Sentinel设置局部领头 Sentinel的规则是先到先得:最先向目标 Sentinel发送设置要求的源 Sentinel将成为目标 Sentinel的局部领头 Sentinel,而之后接收到的所有设置要求都会被目标 Sentinel拒绝。
• 目标Sentinel在接收到 SENTINEL is-master-down-by-addr命令之后,将向源Sentinel返回一条命令回复,回复中的leader runid参数和leader_epoch参数分别记录了目标Sentinel的局部领头Sentinel的运行ID和配置纪元。
• 源Sentinel在接收到目标Sentinel返回的命令回复之后,会检查回复中leader_epoch参数的值和自己的配置纪元是否相同,如果相同的话,那么源Sentinel继续取出回复中的leader_runid参数,如果leader_runid参数的值和源Sentinel的运行ID一致,那么表示目标Sentinel将源Sentinel设置成了局部领头Sentinel。
• 如果有某个Sentinel被半数以上的 Sentinel设置成了局部领头 Dentine,那么这个Sentinel成为领头 Sentinel。举个例子,在一个由10个Sentinel组成的 Sentinel系统里面,只要有大于等于10/2+1=6个Sentinel将某个Sentinel设置为局部领头Sentinel,那么被设置的那个Sentine就会成为领头Sentinel。
• 因为领头Sentinel的产生需要半数以上Sentinel的支持,并且每个Sentinel在每个配置纪元里面只能设置一次局部领头Sentinel,所以在一个配置纪元里面,只会出现一个领头Sentinel。
• 如果在给定时限内,没有一个Sentinel被选举为领头Sentinel,那么各个Sentinel将在一段时间之后再次进行选举,直到选出领头Sentinel为止。

        7.故障转移

• 1)在已下线主服务器属下的所有从服务器里面,挑选出一个从服务器,并将其转换为主服务器。
• 2)让已下线主服务器属下的所有从服务器改为复制新的主服务器。
• 3)将已下线主服务器设置为新的主服务器的从服务器,当这个旧的主服务器重新上线时,它就会成为新的主服务器的从服务器。

       

第十七章：集群

        1.clusterNode结构保存了一个节点的当前状态,比如节点的创建时间、节点的名字节点当前的配置纪元、节点的IP地址和端口号等等。
每个节点都会使用一个clusterNode结构来记录自己的状态,并为集群中的所有其他节点(包括主节点和从节点)都创建一个相应的clusterNode结构,以此来记录其他节点的状态。

        2.clusterNode结构的link属性是一个clusterLink结构,该结构保存了连接节点所需的有关信息,比如套接字描述符,输人缓冲区和输出缓冲区。

        3.最后,每个节点都保存着一个clusterState结构,这个结构记录了在当前节点的视角下,集群目前所处的状态,例如集群是在线还是下线,集群包含多少个节点,集群当前的配置纪元,诸如此类:

 

        节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点,让其他节点也与节点B进行握手,最终,经过一段时间之后,节点B会被集群中的所有节点认识。

        4.Redis集群通过分片的方式来保存数据库中的键值对:集群的整个数据库被分为16384个槽(slot),数据库中的每个键都属于这16384个槽的其中一个,集群中的每个节点可以处理0个或最多16384个槽。
当数据库中的16384个槽都有节点在处理时,集群处于上线状态(ok);相反地,如果数据库中有任何一个槽没有得到处理,那么集群处于下线状态(fail)。

        5.Redis以0为起始索引,16383为终止索引,对slots数组中的16384个二进制位进行编号,并根据索引i上的二进制位的值来判断节点是否负责处理槽i：

• 如果slots数组在索引i上的二进制位的值为1,那么表示节点负责处理槽i。
• 如果slots数组在索引i上的二进制位的值为0,那么表示节点不负责处理槽i。

        6.一个节点除了会将自己负责处理的槽记录在clusterNode结构的slots属性和numslots属性之外,它还会将自己的slots数组通过消息发送给集群中的其他节点,以此来告知其他节点自己目前负责处理哪些槽。

当节点A通过消息从节点B那里接收到节点B的slots数组时,节点A会在自己的clusterState.nodes字典中查找节点B对应的clusterNode结构,并对结构中的slots数组进行保存或者更新。

因为集群中的每个节点都会将自己的slots数组通过消息发送给集群中的其他节点,并且每个接收到slots数组的节点都会将数组保存到相应节点的 clusternode结构里面,因此,集群中的每个节点都会知道数据库中的16384个槽分别被指派给了集群中的哪些节点。

        7.clusterstate结构中的slots数组记录了集群中所有16384个槽的指派信息：

slots数组包含16384个项,每个数组项都是一个指向clusterNode结构的指针:

• 如果slots[i]指针指向NULL,那么表示槽i尚未指派给任何节点。
• 如果slots[i]指针指向一个clusterNode结构,那么表示槽i已经指派给了clusterNode结构所代表的节点。 

        8.当客户端向节点发送与数据库键有关的命令时,接收命令的节点会计算出命令要处理的数据库键属于哪个槽,并检查这个槽是否指派给了自己:

• 如果键所在的槽正好就指派给了当前节点,那么节点直接执行这个命令。
• 如果键所在的槽并没有指派给当前节点,那么节点会向客户端返回一个 MOVED错误,指引客户端转向(redirect)至正确的节点,并再次发送之前想要执行的命令。

        9.节点使用以下算法来计算给定键key属于哪个槽：

 其中CRC16(key)语句用于计算键key的CRC-16校验和,而&16383语句则用于计算出一个介于0至16383之间的整数作为键key的槽号。

        10.一个集群客户端通常会与集群中的多个节点创建套接字连接,而所谓的节点转向实际上就是换一个套接字来发送命令。
如果客户端尚未与想要转向的节点创建套接字连接,那么客户端会先根据MOVED错误提供的IP地址和端口号来连接节点,然后再进行转向。

        11.节点和单机服务器在数据库方面的一个区别是,节点只能使用0号数据库,而单机Redis服务器则没有这一限制。

        12.另外,除了将键值对保存在数据库里面之外,节点还会用clusterState结构中的slots_to_keys跳跃表来保存槽和键之间的关系：

slots_to_keys跳跃表每个节点的分值(score)都是一个槽号,而每个节点的成员(member)都是一个数据库键：

• 每当节点往数据库中添加一个新的键值对时,节点就会将这个键以及键的槽号关联到 slots_to_keys跳跃表。
• 当节点删除数据库中的某个键值对时,节点就会在slots_to_keys跳跃表解除被删除键与槽号的关联。 

        13.Redis集群的重新分片操作可以将任意数量已经指派给某个节点(源节点)的槽改为指派给另一个节点(目标节点),并且相关槽所属的键值对也会从源节点被移动到目标节点。
重新分片操作可以在线(online)进行,在重新分片的过程中,集群不需要下线,并且源节点和目标节点都可以继续处理命令请求。

        14.Redis集群的重新分片操作是由Redis的集群管理软件 redis-trib负责执行的,Redis提供了进行重新分片所需的所有命令,而redis-trib则通过向源节点和目标节点发送命令来进行重新分片操作。

如果重新分片涉及多个槽,那么redis-trib将对每个给定的槽分别执行上面给出的步骤。

 
        15.在进行重新分片期间,源节点向目标节点迁移一个槽的过程中,可能会出现这样一种情况:属于被迁移槽的一部分键值对保存在源节点里面,而另部分键值对则保存在目标节点里面。当客户端向源节点发送一个与数据库键有关的命令,并且命令要处理的数据库键恰好就属于正在被迁移的槽时：

• 源节点会先在自己的数据库里面查找指定的键,如果找到的话,就直接执行客户端发送的命令。
• 相反地,如果源节点没能在自己的数据库里面找到指定的键,那么这个键有可能已经被迁移到了目标节点,源节点将向客户端返回一个ASK错误,指引客户端转向正在导入槽的目标节点,并再次发送之前想要执行的命令。

        16.clusterState结构的importing_slots_from数组记录了当前节点正在从其他节点导人的槽:

如果importing_slots_from[i]的值不为NULL,而是指向一个clusterNode结构,那么表示当前节点正在从clusterNode所代表的节点导人槽i。

        17.clusterState结构的migrating_slots_to数组记录了当前节点正在迁移至其他节点的槽。

        18.ASK错误：如果节点收到一个关于键key的命令请求,并且键key所属的槽立正好就指派给了这个节点,那么节点会尝试在自己的数据库里查找键key,如果找到了的话,节点就直接执行客户端发送的命令。
        与此相反,如果节点没有在自己的数据库里找到键key,那么节点会检査自己的clusterState.migrating_sLots_to[i],看键key所属的槽主是否正在进行迁移,如果槽的确在进行迁移的话,那么节点会向客户端发送一个ASK错误,引导客户端到正在导入槽i的节点去査找键key。

        19.ASKING命令唯一要做的就是打开发送该命令的客户端的 REDIS_ASKING标识。

客户端的REDIS_ASKING标识是一个一次性标识,当节点执行了一个带有REDIS_ASKING标识的客户端发送的命令之后,客户端的REDIS_ASKING标识就会被移除。

        20.ASK错误和MOVED错误的区别

• MOVED错误代表槽的负责权已经从一个节点转移到了另一个节点：在客户端收到关于槽i的 MOVED错误之后,客户端每次遇到关于槽i的命令请求时,都可以直接将命令请求发送至 MOVED错误所指向的节点,因为该节点就是目前负责槽i的节点。
• 与此相反,ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施:在客户端收到关于槽i的AsK错误之后,客户端只会在接下来的一次命令请求中将关于槽i的命令请求发送至ASK错误所指示的节点,但这种转向不会对客户端今后发送关于槽i的命令请求产生任何影响,客户端仍然会将关于槽i的命令请求发送至目前负责处理槽i的节点,除非ASK错误再次出现。

        20.向一个节点发送命令:
CLUSTER REPLICATE
可以让接收命令的节点成为node_id所指定节点的从节点,并开始对主节点进行复制。

        21.集群中的每个节点都会定期地向集群中的其他节点发送PING消息,以此来检测对方是否在线,如果接收PING消息的节点没有在规定的时间内,向发送PING消息的节点返回PONG消息,那么发送PING消息的节点就会将接收PING消息的节点标记为疑似下线(probable fail, PFAIL)。

        22.如果在一个集群里面,半数以上负责处理槽的主节点都将某个主节点x报告为疑似下线那么这个主节点x将被标记为已下线(FAIL),将主节点x标记为已下线的节点会向集群广播一条关于主节点x的FAIL消息,所有收到这条FAIL消息的节点都会立即将主节点x标记为已下线。

        23.故障转移
当一个从节点发现自己正在复制的主节点进入了已下线状态时,从节点将开始对下线主节点进行故障转移,以下是故障转移的执行步骤：

• 1)复制下线主节点的所有从节点里面,会有一个从节点被选中。
• 2)被选中的从节点会执行 SLAVEOF no one命令,成为新的主节点。
• 3)新的主节点会撤销所有对已下线主节点的槽指派,并将这些槽全部指派给自己。
• 4)新的主节点向集群广播一条PONG消息,这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点,并且这个主节点已经接管了原本由已下线节点负责处理的槽。
• 5)新的主节点开始接收和自己负责处理的槽有关的命令请求,故障转移完成。

        24.选举新的主节点
新的主节点是通过选举产生的。
以下是集群选举新的主节点的方法:

• 1)集群的配置纪元是一个自增计数器,它的初始值为0。
• 2)当集群里的某个节点开始一次故障转移操作时,集群配置纪元的值会被增一。
• 3)对于每个配置纪元,集群里每个负责处理槽的主节点都有一次投票的机会,而第一个向主节点要求投票的从节点将获得主节点的投票。
• 4)当从节点发现自己正在复制的主节点进入已下线状态时,从节点会向集群广播一条CLUSTERMSG_TYPE_FAILOVER_AUTH_REQUEST消息,要求所有收到这条消息、并且具有投票权的主节点向这个从节点投票。
• 5)如果一个主节点具有投票权(它正在负责处理槽),并且这个主节点尚未投票给其他从节点,那么主节点将向要求投票的从节点返回一条CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息,表示这个主节点支持从节点成为新的主节点。
• 6)每个参与选举的从节点都会接收CLUSTERMSG_TYPE_FAILOVER_AUTH_ACK消息,并根据自己收到了多少条这种消息来统计自己获得了多少主节点的支持。
• 7)如果集群里有N个具有投票权的主节点,那么当一个从节点收集到大于等于N/2+1张支持票时,这个从节点就会当选为新的主节点。
• 8)因为在每一个配置纪元里面,每个具有投票权的主节点只能投一次票,所以如果有N个主节点进行投票,那么具有大于等于N/2+1张支持票的从节点只会有一个,这确保了新的主节点只会有一个。
• 9)如果在一个配置纪元里面没有从节点能收集到足够多的支持票,那么集群进入一个新的配置纪元,并再次进行选举,直到选出新的主节点为止。

        25.集群中的各个节点通过发送和接收消息(message)来进行通信,我们称发送消息的节点为发送者(sender),接收消息的节点为接收者(receiver),节点发送的消息主要有五种。一条消息由消息头(header)和消息正文(data)组成。

        26.节点发送的所有消息都由一个消息头包裹,消息头除了包含消息正文之外,还记录了消息发送者自身的一些信息,因为这些信息也会被消息接收者用到,所以严格来讲,我们可以认为消息头本身也是消息的一部分。每个消息头都由一个cluster.h/clusterMsg结构表示。

clusterMsg.data属性指向联合 cluster.h/clusterMsgData,这个联合就是消息的正文。

clusterMsg结构的currentEpoch、sender、myslots等属性记录了发送者自身的节点信息,接收者会根据这些信息,在自己的clusterState.nodes字典里找到发送者对应的clusterNode结构,并对结构进行更新。

        27.因为MEET、PING、PONG三种消息都使用相同的消息正文,所以节点通过消息头的type属性来判断一条消息是MEET消息、PING消息还是PONG消息。
每次发送MEET、PING、PONG消息时,发送者都从自己的已知节点列表中随机选出两个节点(可以是主节点或者从节点),并将这两个被选中节点的信息分别保存到两个clustermsgDataGossip结构里面。

        28.当接收者收到MEET、PING、PONG消息时,接收者会访问消息正文中的两个clusterMsgDataGossip结构,并根据自己是否认识clusterMsgDataGossip结构中记录的被选中节点来选择进行哪种操作:

• 如果被选中节点不存在于接收者的已知节点列表,那么说明接收者是第一次接触到被选中节点,接收者将根据结构中记录的IP地址和端口号等信息,与被选中节点进行握手。
• 如果被选中节点已经存在于接收者的已知节点列表,那么说明接收者之前已经与被选中节点进行过接触,接收者将根据 clusterMsgDataGossip结构记录的信息,对被选中节点所对应的clusterNode结构进行更新。

        29.FAIL消息的正文由cluster.h/clusterMsgDataFail结构表示,这个结构只包含一个nodename属性,该属性记录了已下线节点的名字:

        30.当客户端向集群中的某个节点发送命令：
PUBLISH
的时候,接收到PUBLISH命令的节点不仅会向channel频道发送消息message,它还会向集群广播一条PUBLISH消息,所有接收到这条PUBLISH消息的节点都会向 channel频道发送message消息。

       31.PUBLISH消息的正文由cluster.h/clusterMsgDataPublish结构表示:

        32.clusterMsgDataPublish结构的bulk_data属性是一个字节数组,这个字节数组保存了客户端通过PUBLISH命令发送给节点的channel参数和message参数,而结构的channel_len和message_len则分别保存了channel参数的长度和message参数的长度：

• 其中bulk_data的0字节至channel_len-1字节保存的是 channel参数。
• 而bulk_data的channel_len字节至channel_len + messagelen-1字节保存的则是message参数。         

第十八章：发布与订阅

        1.除了订阅频道之外,客户端还可以通过执行 PSUBSCRIBE命令订阅一个或多个模式,从而成为这些模式的订阅者:每当有其他客户端向某个频道发送消息时,消息不仅会被发送给这个频道的所有订阅者,它还会被发送给所有与这个频道相匹配的模式的订阅者。

        2.Redis将所有频道的订阅关系都保存在服务器状态的 pubsub_channels字典里面,这个字典的键是某个被订阅的频道,而键的值则是一个链表,链表里面记录了所有订阅这个频道的客户端。

        3.如果删除退订客户端之后,频道的订阅者链表变成了空链表,那么说明这个频道已经没有任何订阅者了,程序将从 pubsub_channels字典中删除频道对应的键。

        4.与此类似,服务器也将所有模式的订阅关系都保存在服务器状态的pubsub_patterns属性里面:

         5.pubsub_patterns属性是一个链表,链表中的每个节点都包含着一个pubsub_Pattern结构,这个结构的pattern属性记录了被订阅的模式,而client属性则记录了订阅模式的客户端。

        6.当一个Redis客户端执行PUBLISH 命令将消息message发送给频道channel的时候,服务器需要执行以下两个动作

• 1)将消息message发送给channel频道的所有订阅者。
• 2)如果有一个或多个模式pattern与频道channel相匹配,那么将消息message发送给pattern模式的订阅者。

        7.PUBSUB CHANNELS [pattern]子命令用于返回服务器当前被订阅的频道,其中pattern参数是可选的:

• 如果不给定 pattern参数,那么命令返回服务器当前被订阅的所有频道。
• 如果给定 pattern参数,那么命令返回服务器当前被订阅的频道中那些与 pattern模式相匹配的频道。

        8.PUBSUB NUMSUB [channel-1 channel-2…. channel-n]子命令接受任意多个频道作为输入参数,并返回这些频道的订阅者数量。

        9.PUBSUB NUMPAT子命令用于返回服务器当前被订阅模式的数量。

第十九章：事务

        1.Redis通过MULTI、EXEC、WATCH等命令来实现事务(transaction)功能。事务提供了一种将多个命令请求打包,然后一次性、按顺序地执行多个命令的机制,并且在事务执行期间,服务器不会中断事务而改去执行其他客户端的命令请求,它会将事务中的所有命令都执行完毕,然后才去处理其他客户端的命令请求。

        2.MULTI命令的执行标志着事务的开始。MULTI命令可以将执行该命令的客户端从非事务状态切换至事务状态,这一切换是通过在客户端状态的flags属性中打开REDIS_MULTI标识来完成的。

        3.每个Redis客户端都有自己的事务状态,这个事务状态保存在客户端状态的mstate属性里面:

事务状态包含一个事务队列,以及一个已入队命令的计数器(也可以说是事务队列的长度)。

事务队列是一个multiCmd类型的数组,数组中的每个multiCmd结构都保存了一个已入队命令的相关信息,包括指向命令实现函数的指针、命令的参数,以及参数的数量。

        4.WATCH命令是一个乐观锁(optimistic locking),它可以在EXEC命令执行之前,监视任意数量的数据库键,并在EXEC命令执行时,检查被监视的键是否至少有一个已经被修改过了,如果是的话,服务器将拒绝执行事务,并向客户端返回代表事务执行失败的空回复。

        5.每个Redis数据库都保存着一个watched_keys字典,这个字典的键是某个被WATCH命令监视的数据库键,而字典的值则是一个链表,链表中记录了所有监视相应数据库键的客户端。

        6.所有对数据库进行修改的命令,比如SET、LPUSH、SADD、ZREM、DEL、FLUSHDB等等,在执行之后都会调用multi.c/ touchWatchKey函数对watched_keys字典进行检査,査看是否有客户端正在监视刚刚被命令修改过的数据库键,如果有的话,那么touchWatchKey函数会将监视被修改键的客户端的REDIS_DIRTY_CAS标识打开,表示该客户端的事务安全性已经被破坏。

        7.当服务器接收到一个客户端发来的EXEC命令时,服务器会根据这个客户端是否打开了REDIS_DIRTY_CAS标识来决定是否执行事务。

        8.Redis的事务和传统的关系型数据库事务的最大区别在于, Redis不支持事务回滚机制(rollback),即使事务队列中的某个命令在执行期间出现了错误,整个事务也会继续执行下去,直到将事务队列中的所有命令都执行完毕为止。

        9.如果Redis服务器在执行事务的过程中停机,那么根据服务器所使用的持久化模式,可能有以下情况出现:

• 如果服务器运行在无持久化的内存模式下,那么重启之后的数据库将是空白的,因此数据总是一致的。
• 如果服务器运行在RDB模式下,那么在事务中途停机不会导致不一致性,因为服务器可以根据现有的RDB文件来恢复数据,从而将数据库还原到一个一致的状态。如果找不到可供使用的RDB文件,那么重启之后的数据库将是空白的,而空白数据库总是一致的。
• 如果服务器运行在AOF模式下,那么在事务中途停机不会导致不一致性,因为服务器可以根据现有的AOF文件来恢复数据,从而将数据库还原到一个一致的状态。如果找不到可供使用的AOF文件,那么重启之后的数据库将是空白的,而空白数据库总是一致的。

第二十章：Lua脚本

        1.Redis服务器创建并修改Lua环境的整个过程由以下步骤组成:

• 1)创建一个基础的Lua环境,之后的所有修改都是针对这个环境进行的。
• 2)载入多个函数库到Lua环境里面,让Lua脚本可以使用这些函数库来进行数据操作。
• 3)创建全局表格 redis,这个表格包含了对 Redis进行操作的函数,比如用于在Lua脚本中执行 Redis命令的 redis.ca11函数。
• 4)使用 Redis自制的随机函数来替换Lua原有的带有副作用的随机函数,从而避免在脚本中引人副作用。
• 5)创建排序辅助函数,Lua环境使用这个辅佐函数来对一部分 Redis命令的结果进行排序,从而消除这些命令的不确定性。
• 6)创建 redis. pcall函数的错误报告辅助函数,这个函数可以提供更详细的出错信息
• 7)对Lua环境中的全局环境进行保护,防止用户在执行Lua脚本的过程中,将额外的全局变量添加到Lua环境中。
• 8)将完成修改的Lua环境保存到服务器状态的1ua属性中,等待执行服务器传来的Lua脚本。

        2.函数副作用是指函数在正常工作任务之外对外部环境所施加的影响。具体地说，函数副作用是指函数被调用，完成了函数既定的计算任务，但同时因为访问了外部数据，尤其是因为对外部数据进行了写操作，从而一定程度地改变了系统环境。函数的副作用也有可能是发生在函数运行期间，由于对外部数据的改变，导致了同步运行的外部函数受到影响。

        3.在之前载入Lua环境的math函数库中,用于生成随机数的math. random函数和math. randomseed函数都是带有副作用的,它们不符合Redis对Lua环境的无副作用要求。
因为这个原因, Redis使用自制的函数替换了math库中原有的math. random函数和math. randomseed函数。

        4.对于Lua脚本来说,另一个可能产生不一致数据的地方是那些带有不确定性质的命令。为了消除这些命令带来的不确定性,服务器会为Lua环境创建一个排序辅助函数redis_compare_helper,当Lua脚本执行完一个带有不确定性的命令之后,程序会使用 redis_compare_helper作为对比函数,自动调用 table,sort函数对命令的返回值做一次排序,以此来保证相同的数据集总是产生相同的输出。

        5.因为Redis使用串行化的方式来执行Redis命令,所以在任何特定时间里,最多都只会有一个脚本能够被放进Lua环境里面运行,因此,整个Redis服务器只需要创建一个Lua环境即可。

        6.当客户端向服务器发送EVAL命令,要求执行某个Lua脚本的时候,服务器首先要做的就是在Lua环境中,为传入的脚本定义一个与这个脚本相对应的Lua函数,其中,Lua函数的名字由f_前缀加上脚本的SHA1校验和(四十个字符长)组成,而函数的体(body)则是脚本本身。

        7.每个被EVAL命令成功执行过的Lua脚本,在Lua环境里面都有一个与这个脚本相对应的Lua函数,函数的名字由f_前缀加上40个字符长的SHA1校验和组成,例如f_5332031c6b470dc5a0dd9b4bf2030dea6d65de91。只要脚本对应的函数曾经在Lua环境里面定义过,那么即使不知道脚本的内容本身,客户端也可以根据脚本的SHA1校验和来调用脚本对应的函数,从而达到执行脚本的目的,这就是EVALSHA命令的实现原理。

        8.SCRIPT FLUSH命令用于清除服务器中所有和Lua脚本有关的信息,这个命令会释放并重建lua_scripts字典,关闭现有的Lua环境并重新创建一个新的Lua环境。

        9.SCRIPT EXISTS命令根据输入的SHA1校验和,检查校验和对应的脚本是否存在于服务器中。
SCRIPT EXISTS命令是通过检查给定的校验和是否存在于lua_scripts字典来实现的。

        10.SCRIPT LOAD命令所做的事情和EVAL命令执行脚本时所做的前两步完全一样:命令首先在Lua环境中为脚本创建相对应的函数,然后再将脚本保存到lua_scripts字典里面。

        11.如果服务器设置了lua-time-limit配置选项,那么在每次执行Lua脚本之前,服务器都会在Lua环境里面设置一个超时处理钩子(hook)超时处理钩子在脚本运行期间,会定期检查脚本已经运行了多长时间,旦钩子发现脚本的运行时间已经超过了lua-time-limit选项设置的时长,钩子将定期在脚本运行的间隙中,查看是否有SCRIPT KILL命令或者SHUTDOWN命令到达服务器。

如果超时运行的脚本未执行过任何写入操作,那么客户端可以通过 SCRIPT KILL命令来指示服务器停止执行这个脚本,并向执行该脚本的客户端发送一个错误回复。处理完 SCRIPT KILL命令之后,服务器可以继续运行。
另一方面,如果脚本已经执行过写入操作,那么客户端只能用 SHUTDOWN nosave命令来停止服务器,从而防止不合法的数据被写入数据库中。

        12.与其他普通 Redis命令一样,当服务器运行在复制模式之下时,具有写性质的脚本命令也会被复制到从服务器,这些命令包括EVAL命令、EVALSHA命令、SCRIPT FLUSH命令以及 SCRIPT LOAD命令。

        13.Redis复制EVAL、SCRIPT FLUSH、SCRIPT LOAD三个命令的方法和复制其他普通Redis命令的方法一样,当主服务器执行完以上三个命令的其中一个时,主服务器会直接将被执行的命令传播(propagate)给所有从服务器。

        14.EVALSHA命令是所有与Lua脚本有关的命令中,复制操作最复杂的一个,因为主服务器与从服务器载人Lua脚本的情况可能有所不同,所以主服务器不能像复制EVAL命令、SCRIPT LOAD命令或者SCRIPT FLUSH命令那样,直接将EVALSHA命令传播给从服务器。对于一个在主服务器被成功执行的EVALSHA命令来说,相同的EVALSHA命令在从服务器执行时却可能会出现脚本未找到(not found)错误。

为了防止以上假设的情况出现,Redis要求主服务器在传播EVALSHA命令的时候,必须确保EVALSHA命令要执行的脚本已经被所有从服务器载入过,如果不能确保这一点的话,主服务器会将EVALSHA命令转换成一个等价的EVL命令,然后通过传播EVAL命令来代替EVALSHA命令。
传播EVALSHA命令,或者将EVALSHA命令转换成EVAL命令,都需要用到服务器状态的lua_scripts字典和repl_scriptcache_dict字典,并最终说明Redis复制EVALSHA命令的方法。

        15.主服务器使用服务器状态的repl_scriptcache_dict字典记录自己已经将哪些脚本传播给了所有从服务器。

        16.每当主服务器添加一个新的从服务器时,主服务器都会清空自己的repl_scriptcache_dict字典。

        17.主服务器在传播完EVAL命令之后,会将被传播脚本的SHAI校验和(也即是原本EVALSHA命令指定的那个校验和)添加到repl_scriptcache_dict字典里面。

        

第二十一章：排序

        1.服务器执行 SORT numbers命令的详细步骤如下：

• 1)创建一个和 numbers列表长度相同的数组,该数组的每个项都是一个 redis.h/redisSortObject结构。
• 2)遍历数组,将各个数组项的obj指针分别指向numbers列表的各个项,构成obj指针和列表项之间的一对一关系。
• 3)遍历数组,将各个obj指针所指向的列表项转换成一个double类型的浮点数,并将这个浮点数保存在相应数组项的u.score属性里面。
• 4)根据数组项u.score属性的值,对数组进行数字值排序,排序后的数组项按u.score属性的值从小到大排列。
• 5)遍历数组,将各个数组项的bj指针所指向的列表项作为排序结果返回给客户端,程序首先访问数组的索引0,返回u.score值为1.0的列表项"1";然后访问数组的索引1,返回u.score值为2.0的列表项"2";最后访问数组的索引2,返回u.score值为3.0的列表项"3"。

        2.SORT命令为每个被排序的键都创建一个与键长度相同的数组,数组的每个项都是一个redisSortObject结构,根据SORT命令使用的选项不同,程序使用redisSortObject结构的方式也不同。

        3.通过使用 ALPHA选项,SORT命令可以对包含字符串值的键进行排序。

        4.升序排序和降序排序都由相同的快速排序算法执行,它们之间的不同之处在于：

• 在执行升序排序时,排序算法使用的对比函数产生升序对比结果。
• 而在执行降序排序时,排序算法所使用的对比函数产生降序对比结果。

        5.通过使用BY选项,SORT命令可以指定某些字符串键,或者某个哈希键所包含的某些域(field)来作为元素的权重,对一个键进行排序。

        6.BY选项默认假设权重键保存的值为数字值,如果权重键保存的是字符串值的话,那么就需要在使用BY选项的同时,配合使用ALPHA选项。

        7.通过LIMIT选项,我们可以让SORT命令只返回其中一部分已排序的元素。
        LIMIT选项的格式为LIMIT。

        8.在默认情况下,SORT命令在对键进行排序之后,总是返回被排序键本身所包含的元素。

但是,通过使用GET选项,我们可以让SORT命令在对键进行排序之后,根据被排序的元素,以及GET选项所指定的模式,查找并返回某些键的值。

        9.在默认情况下,SORT命令只向客户端返回排序结果,而不保存排序结果。但是,通过使用 STORE选项,我们可以将排序结果保存在指定的键里面,并在有需要时重用这个排序结果。

        10.如果按照选项来划分的话,一个SORT命令的执行过程可以分为以下四步：

• 1)排序:在这一步,命令会使用ALPHA、ASC或DESC、BY这几个选项,对输入键进行排序,并得到一个排序结果集。
• 2)限制排序结果集的长度:在这一步,命令会使用LIMIT选项,对排序结果集的长度进行限制,只有LIMIT选项指定的那部分元素会被保留在排序结果集中。
• 3)获取外部键:在这一步,命令会使用GET选项,根据排序结果集中的元素,以及GET选项指定的模式,查找并获取指定键的值,并用这些值来作为新的排序结果集。
• 4)保存排序结果集:在这一步,命令会使用STORE选项,将排序结果集保存到指定的键上面去。
• 5)向客户端返回排序结果集:在最后这一步,命令遍历排序结果集,并依次向客户端返回排序结果集中的元素。

在以上这些步骤中,后一个步骤必须在前一个步骤完成之后进行。

        11.另外要提醒的一点是,调用SORT命令时,除了GET选项之外,改变选项的摆放顺序并不会影响SORT命令执行这些选项的顺序。

不过,如果命令包含了多个GET选项,那么在调整选项的位置时,我们必须保证多个GET选项的摆放顺序不变,这才可以让排序结果集保持不变。

第二十二章：二进制位数组

        1.Redis提供了SETBIT、GETBIT、BITCOUNT、BITOP四个命令用于处理二进制位数组( bit array,又称“位数组”)。

• 其中, SETBIT命令用于为位数组指定偏移量上的二进制位设置值,位数组的偏移量从0开始计数,而二进制位的值则可以是0或者1。
• 而GETBIT命令则用于获取位数组指定偏移量上的二进制位的值。
• BITCOUNT命令用于统计位数组里面,值为1的二进制位的数量。
• 最后, BITOP命令既可以对多个位数组进行按位与(and)、按位或(or)、按位异或(xor)运算。

        2.Redis使用字符串对象来表示位数组,因为字符串对象使用的SDS数据结构是二进制安全的,所以程序可以直接使用SDS结构来保存位数组,并使用SDS结构的操作函数来处理位数组。

• redisObject.type的值为REDIS_STRING,表示这是一个字符串对象。
• sdshdr.len的值为1,表示这个SDS保存了一个一字节长的位数组。
• buf数组中的buf[0]字节保存了一字节长的位数组。
• buf数组中的buf[1]字节保存了SDS程序自动追加到值的末尾的空字符'\0'。

        3.现在,buf数组的每个字节都用一行来表示,每行的第一个格子buf[i]表示这是buf数组的哪个字节,而buf[i]之后的八个格子则分别代表这一字节中的八个位。
需要注意的是,buf数组保存位数组的顺序和我们平时书写位数组的顺序是完全相反的。使用逆序来保存位数组可以简化SETBIT命令的实现。（二进制的位是从左向右增加的，4->3->2->1->0）

        4.GETBIT命令用于返回位数组bitarray在 offset偏移量上的二进制位的值：
GETBIT

因为GETBIZ命令执行的所有操作都可以在常数时间内完成,所以该命令的算法复杂度为O(1)。

        5.SETBIT用于将位数组bitarray在offset偏移量上的二进制位的值设置为value并向客户端返回二进制位被设置之前的旧值:
SETBIT

        6.对位数组的长度进行检査,得知位数组现在的长度为1字节,这比执行命令所需的最小长度2字节要小,所以程序会要求将位数组的长度扩展为2字节。不过,尽管程序只要求2字节长的位数组,但SDS的空间预分配策略会为SDS额外多分配2字节的未使用空间,再加上为保存空字符而额外分配的1字节,扩展之后buf数组的实际长度为5字节。

        7.BITCOUNT命令用于统计给定位数组中,值为1的二进制位的数量。

        8.BITCOUNT命令要解决的问题一一统计一个位数组中非0二进制位的数量,在数学上被称为“计算汉明重量(Hamming Weight)”。

目前已知效率最好的通用算法为variable-precision SWAR算法。

        9.BITCOUNT命令的实现用到了查表和variable-precisions SWAR两种算法：

• 查表算法使用键长为8位的表,表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量。
• 至于variable-precision SWAR算法方面, BITCOUNT命令在每次循环中载入128个二进制位,然后调用四次32位variable-precision SWAR算法来计算这128个二进制位的汉明重量。

在执行 BITCOUNT命令时,程序会根据未处理的二进制位的数量来决定使用那种算法:

• 如果未处理的二进制位的数量大于等于128位,那么程序使用variable-precision SWAR算法来计算二进制位的汉明重量。
• 如果未处理的二进制位的数量小于128位,那么程序使用查表算法来计算二进制位的汉明重量。

        10.这个 BITCOUNT实现的算法复杂度为O(n),其中n为输入二进制位的数量。

        11.BITOP命令的AND、OR、XOR和NOT四个操作都是直接基于这些逻辑操作实现的：

• 在执行BITOP AND命令时,程序用&操作计算出所有输入二进制位的逻辑与结果然后保存在指定的键上面。
• 在执行BITOP OR命令时,程序用|操作计算出所有输入二进制位的逻辑或结果,然后保存在指定的键上面。
• 在执行BITOP XOR命令时,程序用^操作计算出所有输入二进制位的逻辑异或结果然后保存在指定的键上面。
• 在执行BITOP NOT命令时,程序用~操作计算出输入二进制位的逻辑非结果,然后保存在指定的键上面。

        12.因为BITOP AND、BITOP OR、BITOP XOR三个命令可以接受多个位数组作为输入程序需要遍历输入的每个位数组的每个字节来进行计算,所以这些命令的复杂度为O(n*n);与此相反,因为 BITOP NOT命令只接受一个位数组输入,所以它的复杂度为O(n)。

 第二十三章：慢查询日志

        1.服务器配置有两个和慢查询日志相关的选项:

• slowing-log-slower-than选项指定执行时间超过多少微秒(1秒等于1 000 000微秒)的命令请求会被记录到日志上。
• slowlog-max-len选项指定服务器最多保存多少条慢查询日志。

        2.服务器使用先进先出的方式保存多条慢查询日志,当服务器存储的慢査询日志数量等于slowlog-max-len选项的值时,服务器在添加一条新的慢查询日志之前,会先将最旧的条慢查询日志删除。

        3.首先用CONFIG SET命令将slowlog-log-slower-than选项的值设为0微秒,这样Redis服务器执行的任何命令都会被记录到慢查询日志中,接着将slowlog-max-len选项的值设为5,让服务器最多只保存5条慢査询日志。

        4.然后使用SLOWLOG GET命令查看服务器所保存的慢查询日志。

        5.服务器状态中包含了几个和慢查询日志功能有关的属性：

 slowlog_entry_id属性的初始值为0,每当创建一条新的慢查询日志时,这个属性的值就会用作新日志的id值,之后程序会对这个属性的值增一。

slowlog链表保存了服务器中的所有慢查询日志,链表中的每个节点都保存了一个slowlogEntry结构,每个slowlogEentry结构代表一条慢查询日志。

• slowlog_entry_id的值为6,表示服务器下条慢查询日志的id值将为6。
• slowlog链表包含了id为5至1的慢查询日志,最新的5号日志排在链表的表头,而最旧的1号日志排在链表的表尾,这表明slowlog链表是使用插入到表头的方式来添加新日志的。
• slowlog_log_slower_than记录了服务器配置slowlog-log-slower-than选项的值0,表示任何执行时间超过0微秒的命令都会被慢查询日志记录。
• slowlog-max-len属性记录了服务器配置slowlog-max-len选项的值5,表示服务器最多储存五条慢查询日志。 

        6.在每次执行命令的之前和之后,程序都会记录微秒格式的当前UNIX时间戳,这两个时间戳之间的差就是服务器执行命令所耗费的时长,服务器会将这个时长作为参数之一传给slowlogPushEntryIfNeeded函数,而slowlogPushEntryIfNeeded函数则负责检査是否需要为这次执行的命令创建慢查询日志。

第二十四章：监视器

        1.通过执行MONITOR命令,客户端可以将自己变为一个监视器,实时地接收并打印出服务器当前处理的命令请求的相关信息。每当一个客户端向服务器发送一条命令请求时,服务器除了会处理这条命令请求之外,还会将关于这条命令请求的信息发送给所有监视器。

        2.如果客户端c10086向服务器发送MONITOR命令,那么这个客户端的REDIS MONITOR标志会被打开,并且这个客户端本身会被添加到monitors链表的表尾。

        3.服务器在每次处理命令请求之前,都会调用 replicationFeedMonitors函数,由这个函数将被处理的命令请求的相关信息发送给各个监视器。