Redis设计与实现总结
2020-04-26 17:00:36 0 举报
AI智能生成
详细、生动地介绍Redis底层设计与实现,包含:五大类型的数据结构、主从复制的底层原理和实现、哨兵模式的底层原理和实现、集群模式的底层原理和实现、发布订阅模式、事务等等。
作者其他创作
大纲/内容
Redis
关于C语言整型的数据类型讲解
算法复杂度https://www.jianshu.com/p/769c21deb791
Gossip协议:https://www.jianshu.com/p/54eab117e6ae
数据结构与对象
数据结构
五种基本数据类型
Redis 数据库里面的每个键值对(key-value pair)都是由对象(object)组成的
数据库键总是一个字符串对象(string object)
而数据库键的值则可以是字符串对象、列表对象(listobject)、哈希对象(hash object)、集合对象(set object)、有序集合对象(sorted set object)这五种对象中的其中一种。
字符串 SDS(Simple Dynamic String)
结构
int len:记录 buf 数组中已使用字节的数量,等于 SDS 锁保存字符串的长度
int free:记录 buf 数组中未使用字节的数量
char buf[]:字节数组,用于保存字符串
常数复杂度获取字符串长度 O(1):因为 SDS 有 len 属性
杜绝缓冲区溢出:Redis 有一个 free 属性,扩展前,会先判断 free 属性是否满足扩展的字符长度,如果满足则直接扩展;如果不满足,则需要先执行内存重分配操作,来扩大字节数组的长度,然后再扩展字符串。
减少修改字符串长度时所需的内存重分配次数。:Redis 的两个优化策略,空间预分配和惰性空间释放。
空间预分配
惰性空间释放
二进制安全
C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
为了确保Redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的(binary-safe),所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读取时就是什么样。ps:所以为啥叫 SDS 的数组为字节数组。
兼容部分C字符串函数
由于 SDS 一样遵循C字符串以空字符结尾的惯例,所以 SDS 可以重用很多<string.h>库定义的函数。
列表 list
列表节点结构(listNode)
struct listNode * prev:前置节点
struct listNode * next:后置节点
void * value:节点的值
每个链表节点由一个listNode结构来表示,每个节点都有一个指向前置节点和后置节点的指针,所以Redis的链表实现是双端链表。
列表结构(list)
listNode * head:表头节点
listNode * tail:表尾节点
unsigned long len:链表所包含的节点数量
void *(*dup)(void *ptr):节点值复制函数
void (*free)(void *ptr):节点值释放函数
每个链表使用一个list结构来表示,这个结构带有表头节点指针、表尾节点指针,以及链表长度等信息。
因为链表表头节点的前置节点和表尾节点的后置节点都指向NULL,所以Redis的链表实现是无环链表。
通过为链表设置不同的类型特定函数,Redis的链表可以用于保存各种不同类型的值。
指针指向 void类型为 void * 的指针代表对象的地址,而不是类型。例如,内存分配函数 void *malloc( size_t size ); 返回指向 void 的指针,可以转换为任何数据类型。
链表被广泛用于实现Redis的各种功能,比如列表键、发布与订阅、慢查询、监视器等。
字典 dict
字典被广泛用于实现Redis的各种功能,其中包括数据库和哈希键。
Redis中的字典使用哈希表作为底层实现,每个字典带有两个哈希表,一个平时使用,另一个仅在进行rehash时使用。
字典(dict)
dictType *type:类型特定函数
包括 计算哈希值函数、复制键函数、复制值函数、对比键函数、销毁键函数、销毁值函数。
void *privdata:私有数据
dictht ht[2]:哈希表
一般只使用ht[0],rehash时才会使用到ht[1]
int rehashidx:rehash索引
它记录了rehash目前的进度,如果目前没有在进行rehash,那么它的值为-1
哈希表(dictht)
dictEntry **table:哈希表数组
unsigned long size:哈希表大小
unsigned long sizemask:哈希表大小掩码,用于计算索引值,总是等于 size-1
unsigned long used:该哈希表已有节点的数量
哈希表节点(dictEntry)
void *key:键
union{} v:值
void *val:值可以为一个指针
uint64_tu64:值可以为一个unit64_t整数
int64_ts64:值可以为一个int64_t整数
struct dictEntry *next:指向下个哈希节点,形成链表
当字典被用作数据库的底层实现,或者哈希键的底层实现时,Redis使用MurmurHash2算法来计算键的哈希值。
哈希算法就是 dictType *type 指针指向的类型特定的dictType里面的哈希值函数(hashFunction)
哈希表使用链地址法来解决键冲突,被分配到同一个索引上的多个键值对会连接成一个单向链表。
使用的是头插法,因为复杂度为o(1),而如果使用尾插法,复杂度将会是O(n)。
头插法在扩容的时候会存在并发问题,但是由于 Redis 是单线程的,所以不用考虑这个问题。
在对哈希表进行扩展或者收缩操作时,程序需要将现有哈希表包含的所有键值对rehash到新哈希表里面,并且这个rehash过程并不是一次性地完成的,而是渐进式地完成的。
rehash步骤
扩容或收缩操作
如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used*2的2 n(2的n次方幂);
如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2 n。
对ht[0]中所有键值对rehash到ht[1]中
在字典中维持一个索引计数器变量 rehashidx,将它设置为0,代表 rehash 工作正式开始。
每完成哈希表数组中一个索引上的所有节点的 rehash 工作,rehashidx属性的值增一。
在 rehash 执行期间,还是会允许对字典执行添加、删除、查找或者是更新操作。
添加:会直接添加到ht[1]中
查询:先从ht[0]里查询,如果没找到就继续到h[1]里查询。
随着字典操作的不断执行,最终在某个时间点上,ht[0]的所有键值对都会被rehash至ht[1],这时程序将rehashidx属性的值设为-1,表示rehash操作已完成。
释放ht[0],将ht[1]置为ht[0],并在ht[1]新创建一个空的哈希表
哈希表扩展与收缩的条件
负载因子公式:load_factor= ht[0].used / ht[0].size
扩展
服务器目前没有在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于1。
服务器目前正在执行BGSAVE命令或者BGREWRITEAOF命令,并且哈希表的负载因子大于等于5。
收缩
哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作。
关于 rehash 的思考。
联想到 JDK 的HashMap 中关于索引值的重新计算问题。
总结:得益于 HashMap 规定哈希桶的容量为 2的n次方,还有扩容时新数组的容量是旧数组容量的2倍,首先保证了可以使用位运算,然后,新数组的容量永远是旧数组的二进制左移一位,不管是n还是n-1。所以可以利用高位运算(hash & oldCap == 0 ?)来判断元素是否需要移动,省去每个元素都要重新计算数组索引。如果高位运算的结果是0,则表示扩展前后的索引值是一样的(newIndex = oldIndex)。如果高位运算的结果是1,则扩展后索引值等于扩展前索引值+旧哈希表容量(newIndex = oldIndex + oldCap)
跳跃列表 skiplist
跳跃表是有序集合的底层实现之一。
跳跃表(skiplist)是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找,还可以通过顺序性操作来批量处理节点。
Redis使用跳跃表作为有序集合键的底层实现之一,如果一个有序集合包含的元素数量比较多,又或者有序集合中元素的成员(member)是比较长的字符串时,Redis就会使用跳跃表来作为有序集合键的底层实现。
Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成,其中zskiplist用于保存跳跃表信息(比如表头节点、表尾节点、长度),而zskiplistNode则用于表示跳跃表节点。
zskiplist
header:指向跳跃表的表头节点
程序定位表头节点的复杂度为 O(1)
tail:指向跳跃表的表尾节点
程序定位表尾节点的复杂度为 O(1)
level:记录目前跳跃表内,层数最大的那个节点的层数(表头节点的层数不计算在内)
用于在O(1)复杂度内获取跳跃表中层高最大的那个节点的层数量,注意表头节点的层高并不计算在内。
length:记录跳跃表的长度,也就是,跳跃表目前包含节点的数量(表头节点不计算在内)
程序能在O(1)复杂度内获取跳跃表的长度
zskiplistNode
层(level):节点中用L1、L2、L3等字样标记节点的各个层,L1代表第一层,L2代表第二层,以此类推。每个层都带有两个属性:前进指针(struct zskiplistNode *forward)和跨度(unsigned int span)。
前进指针
前进指针用于访问位于表尾方向的其他节点
遍历操作只使用前进指针就可以完成了
跨度
跨度则记录了前进指针所指向节点和当前节点的距离。
跨度实际上是用来计算排位(rank)的;在查询某个节点的过程中,将沿途访问的所有层的跨度累计起来,得到的结果就是目标节点在跳跃表中的排位。
后退(backward)指针:它指向位于当前节点的前一个节点。后退指针在程序从表尾向表头遍历时使用。
分值(score):是一个 double 类型的浮点数,在跳跃表中,节点按各自所保存的分值从小到大排列。
成员对象(obj):是一个指针,它指向一个字符串对象,而字符串对象则保存着一个 SDS 值
同一跳跃表中,各个节点保存的成员对象必须是唯一的,但是多个节点保存的分值却可以是相同的。
分值相同的节点,将按照成员对象在字典顺序中的大小进行排序,成员对象较小的节点会排在前面,而成员对象较大的节点则会排在后面。
每个跳跃表节点的层高都是1至32之间的随机数。
整数集合 intset
整数集合是集合键的底层实现之一。
整数集合的底层实现为数组,这个数组以有序、无重复的方式保存集合元素。
整数集合(intset)是Redis用于保存整数值的集合抽象数据结构,它可以保存类型为int16_t、int32_t或者int64_t的整数值,并且保证集合中不会出现重复元素。
uint32_t encoding:编码方式
uint32_t length:集合包含的元素数量
int8_t contents:保存元素的数组
虽然intset结构将contents属性声明为int8_t类型的数组,但实际上contents数组并不保存任何int8_t类型的值,contents数组的真正类型取决于encoding属性的值
如果encoding属性的值为INTSET_ENC_INT16,那么contents就是一个int16_t类型的数组,数组里的每个项都是一个int16_t类型的整数值(最小值为-32768,最大值为32767)。
如果encoding属性的值为INTSET_ENC_INT32,那么contents就是一个int32_t类型的数组,数组里的每个项都是一个int32_t类型的整数值(最小值为-2147483648,最大值为2147483647)。
如果encoding属性的值为INTSET_ENC_INT64,那么contents就是一个int64_t类型的数组,数组里的每个项都是一个int64_t类型的整数值(最小值为-9223372036854775808,最大值为9223372036854775807)。
在有需要时,程序会根据新添加元素的类型,改变这个数组的类型(类型升级)
虽然 intset 能存放多种类型的整数值,但是却不会直接使用最大的类型来定义数组,而是利用升级操作,当元素的值达到一定长度时,会重新为数组分配内存空间,并将数组里的旧元素的类型进行升级。
升级步骤
根据新元素的类型,扩展整数集合底层数组的空间大小(空间重分配),并为新元素分配空间。
例如一开始数组里存放的元素的类型都是int16_t,一共有4个元素。如果此时要添加一个类型为int32_t的整数,那么需要分配大小为 32*5 = 160位的内存空间。
将底层数组现有的所有元素都转换成与新元素相同的类型,并将类型转换后的元素放置到正确的位上,而且在放置元素的过程中,需要继续维持底层数组的有序性质不变。
将新元素添加到底层数组里面。
将 intset 的 encoding 属性改成对应元素类型的值。例如从 INTSET_ENC_INT16 改成 INTSET_ENC_INT32。
修改 inset 的 length 属性。例如从 4 改成 5。
如果添加新元素时引起升级,那么向整数集合添加新元素的时间复杂度为O(N)。
升级后新元素的摆放位置
因为引发升级的新元素的长度总是比整数集合现有所有元素的长度都大,所以这个新元素的值要么就大于所有现有元素,要么就小于所有现有元素
在新元素小于所有现有元素的情况下,新元素会被放置在底层数组的最开头(索引0)
在新元素大于所有现有元素的情况下,新元素会被放置在底层数组的最末尾(索引length-1)
升级操作为整数集合带来了操作上的灵活性,并且尽可能地节约了内存。
提升灵活性:避免了类型错误,并且能自适应添加的新元素的长度。
节约内存:确保升级操作只会在需要的时候进行,尽量节省内存。
其实从另外一个角度看,是浪费内存的。因为数组里可以只存放一个长度为int64_t的元素,而其他元素都是int16_t或者是int32_t。
整数集合只支持升级操作,不支持降级操作。
假如我们将整数集合里唯一一个 int64_t 类型的元素删掉,整数集合的 encoding 仍然会维持 INTSET_ENC_INT64.
所以我们添加元素时,一定要考虑好整数变量定义的长度。
压缩列表 ziplist
压缩列表是一种为节约内存而开发的顺序型数据结构
压缩列表被用作列表键和哈希键的底层实现之一
当一个列表键只包含少量列表项,并且每个列表项要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做列表键的底层实现。
当一个哈希键只包含少量键值对,并且每个键值对的键和值要么就是小整数值,要么就是长度比较短的字符串,那么Redis就会使用压缩列表来做哈希键的底层实现。
ps:在 Redis 3.2 前,当列表对象的元素比较少的时候,底层数据结构使用 ziplist,当元素多的时候使用 linkedlist。在 Redis 3.2 后提供了快速列表(quicklist)来作为列表的底层实现,quicklist 等于 多个 ziplist 靠着前后指针相互连接起来。
ziplist 结构
uint32_t zlbytes:记录整个压缩列表占用的内存字节数;在对压缩列表进行内存重分配时,或者计算 zlend 的位置时使用
uint32_t zltail:记录压缩列表表尾节点距离压缩列表的起始地址有多少字节;通过这个偏移量,程序无须遍历真个压缩列表就可以确定表尾节点的地址
uint16_t zlen:记录了压缩列表包含的节点数量;当这个属性的值大于 UINT16_MAX(65535)时,节点的真实数量需要遍历整个压缩列表才能计算出来。
entryX:压缩列表的包含的各个节点,节点的长度由节点保存的内容决定。
uint8_t zlend:特殊值0XFF(十进制255),用于标记压缩列表的末端。
压缩列表可以包含多个节点,每个节点可以保存一个字节数组或者整数值
字节数组可以是以下三种长度的其中一种
长度小于等于63(2^6–1)字节的字节数组
长度小于等于16383(2^14–1)字节的字节数组
长度小于等于4294967295(2^32–1)字节的字节数组
整数值可以是以下六种长度的其中一种
4位长,介于0至12之间的无符号整数
1字节长的有符号整数
3字节长的有符号整数
int16_t类型整数
int32_t类型整数
int64_t类型整数
entry 的结构
int<var> prevlen:
节点的 previous_entry_length 属性以字节为单位,记录了压缩列表中前一个节点的长度。previous_entry_length属性的长度可以是1字节或者5字节
如果前一节点的长度小于254字节,那么 previous_entry_length 属性的长度为1字节:前一节点的长度就保存在这一个字节里面。
如果前一节点的长度大于等于254字节,那么 previous_entry_length 属性的长度为5字节:其中属性的第一字节会被设置为0xFE(十进制值254),而之后的四个字节则用于保存前一节点的长度。
因为节点的 previous_entry_length 属性记录了前一个节点的长度,所以程序可以通过指针运算,根据当前节点的起始地址来计算出前一个节点的起始地址。压缩列表的从表尾向表头遍历操作就是使用这个一原理实现的。
int<var> encoding:
记录了节点的 content 属性所保存数据的类型以及长度
一字节、两字节或者五字节长,值的最高位为00、01或者10的是字节数组编码:这种编码表示节点的content属性保存着字节数组,数组的长度由编码除去最高两位之后的其他位记录
一字节长,值的最高位以11开头的是整数编码:这种编码表示节点的content属性保存着整数值,整数值的类型和长度由编码除去最高两位之后的其他位记录
字节数组编码
00xxxxxx 最大长度位 63 的短字符串,后面的 6 个位存储字符串的位数,剩余的字节就是字符串的内容
01xxxxxx xxxxxxxx 中等长度的字符串,后面 14 个位来表示字符串的长度,剩余的字节就是字符串的内容
10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd 特大字符串,需要使用额外 4 个字节来表示长度。第一个字节前缀是10,剩余 6 位没有使用,统一置为零。后面跟着字符串内容。不过这样的大字符串是没有机会使用的,压缩列表通常只是用来存储小数据的。
整数编码
11000000 表示 int16,后跟两个字节表示整数(content)
11010000 表示 int32,后跟四个字节表示整数
11100000 表示 int64,后跟八个字节表示整数
11110000 表示 int24,后跟三个字节表示整数
11111110 表示 int8,后跟一个字节表示整数
encoding 没有 11111111 这个编码,因为这个编码是 zlend 使用的,表示 ziplist 的结束。
optional byte[] content:
负责保存节点的值,节点值可以是一个字节数组或者整数,值的类型和长度由节点的 coding 属性来决定。
添加新节点到压缩列表,或者从压缩列表中删除节点,可能会引发连锁更新操作,但这种操作出现的几率并不高
原因:
由于每个节点的 previous_entry_length 属性是记录前一个节点的长度的,而这个属性的所需要的空间是根据前一个节点的长度来判断的。
如果前一节点的长度小于254字节,那么 previous_entry_length 属性需要用1字节长的空间来保存这个长度值
新增节点导致连锁更新操作
假如压缩列表有连续多个长度介于 250 至 253字节的节点
此时,一个长度大于 254 的大节点插入到表头,那么后面的所有节点都需要更新自己的 previous_entry_length 属性了。
当然了,尽管新增节点可能导致连锁更新操作,但是这个几率还是比较低。而且,本来压缩列表就是用来存放节点数比较少的情况下的,所以少量节点的连锁更新还是不会太过于影响压缩列表的性能的。
删除节点导致的连锁更新原理其实是一致的~
思考:那当我们 push 节点进列表时,要保证是同一方向的,那么就不会出现连锁更新的现象了。pop 节点出列表同理。
类型
对象说明
Redis 并没有直接使用上面的数据结构来实现键值对数据库,而是基于上面的数据结构创建了一个对象系统
对象系统包含了字符串对象、列表对象、哈希对象、集合对象和有序集合对象这五种类型的对象,每种对象都用到了至少一种上面介绍的数据结构。
使用对象的好处
Redis 在执行命令之前,可以根据对象的类型判断这个对象是否可以执行给定的命令。
可以针对不用的使用场景,为对象设置多种不同的数据结构实现,从而优化对象在不同场景下的使用效率。
对象的类型与编码
Redis 使用对象来标识数据库中的键和值,在Redis 数据库中创建一个键值对时,最少会创建两个对象,一个对象用做键值对的键(键对象),另一个对象用做键值对的值(值对象)。
Redis 中每个对象都由一个 redisObject 结构表示,该结构中和保存数据有关的三个属性分别是 type 属性,encoding 属性和 ptr 属性。
对象的 type 属性记录了对象的类型,这个属性的值有以下五种
REDIS_STRUBG:字符串对象
type 命令输出:string
REDIS_LIST:列表对象
type 命令输出:list
REDIS_HASH:哈希对象
type 命令输出:hash
REDIS_SET:集合对象
type 命令输出:set
REDIS_ZSET:有序集合对象
type 命令输出:zset
对于 Redis 数据库保存的键值对来说,键总是一个字符串对象,而值可以是多种类型的对象。因此,如果我们称呼一个数据库键为“字符串键”,则指的是“这个数据库键所对应的值为字符串对象”,以此类推。
TYPE 命令的实现方式与上面类似,当我们对一个数据库键执行 type 命令,命令返回的是数据库键对应的值对象的类型。
编码
对象的 ptr 指针指向对象的底层实现数据结构,而这些数据结构由对象的 encoding 属性决定。
encoding属性记录了对象所使用的编码,也即是说这个对象使用了什么数据结构作为对象的底层实现,这个属性的值可以是以下几种
REDIS_ENCODING_INT:Long 类型的整数
REDIS_ENCODING_EMBSTR:embstr 编码的简单动态字符串
REDIS_ENCODING_RAW:简单动态字符串
REDIS_ENCODING_HT:字典
REDIS_ENCODING_LINKEDLIST:双端链表
REDIS_ENCODING_ZIPLIST:压缩列表
REDIS_ENCODING_INTSET:整数集合
REDIS_ENCODING_SKIPLIST:跳跃表和字典
每种类型的对象都至少使用了两种不同的编码。
使用 object encoding 命令可以查看一个数据库键的值对象的编码。
使用 encoding 属性来设定对象所使用的编码,而不是为特定类型的对象关联一种固定的编码,极大地提升了 Redis 的灵活性和效率,因为 Redis 可以根据不同的使用场景来为一个对象设置不同的编码,从而优化对象在某个场景下的效率。
详细介绍五大类型的对象
字符串对象
int、embstr或者raw
如果一个字符串对象保存的是整数值,并且这个整数值可以用 long 类型来表示,那么字符串对象会将整数值保存在字符串对象结构的 ptr 属性里面(将 void* 转换成 long),并将字符串对象的编码设置为 int(encoding = REDIS_ENCODING_INT)。
如果字符串对象保存的是一个字符串值,并且这个字符串值的长度小于等于32字节,那么字符串对象将使用embstr编码的方式来保存这个字符串值。
如果字符串对象保存的是一个字符串值,并且这个字符串值的长度大于32字节,那么字符串对象将使用一个简单动态字符串(SDS)来保存这个字符串值,并将对象的编码设置为raw。
embstr 编码 和 raw 编码的区别
embstr编码是专门用于保存短字符串的一种优化编码方式,这种编码和raw编码一样,都使用redisObject结构和sdshdr结构来表示字符串对象
embstr编码则通过调用一次内存分配函数来分配一块连续的空间,空间中依次包含redisObject和sdshdr两个结构
但raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构
embstr 编码的好处
创建 embstr 编码的字符串对象只需要调用一次内存分配函数
释放 embstr 编码的字符串只需要调用一次内存释放函数
因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面,所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势
最后要说的是,可以用long double类型表示的浮点数在Redis中也是作为字符串值来保存的。如果我们要保存一个浮点数到字符串对象里面,那么程序会先将这个浮点数转换成字符串值,然后再保存转换所得的字符串值。
字符串对象保存各类型值的编码方式
可以用 long 类型保存的整数,编码为 int
可以用 long double 类型保存的浮点数,编码为 embstr 或 raw
字符串值,或者因为长度太大而无法用 long 类型表示的整数,又或者因为长度太大而无法用 long double 类型表示的浮点数,编码为 embstr 或 raw
编码的转换
int 转 raw:当利用 append 命令往整数后面添加字符串,那么字符串对象的编码将从 int 变为 raw。
embstr 转 raw:embstr 编码的字符串对象实际上是只读的。当我们调用修改命令(如 append)时,会先将对象的编码从 embstr 转为 raw,然后再执行修改命令。
列表对象
可以是 ziplist 或者 linkedlist
ziplist编码的列表对象使用压缩列表作为底层实现,每个压缩列表节点(entry)保存了一个列表元素。压缩列表节点的组成部分包括:prevlength、encoding、content[]
linkedlist编码的列表对象使用双端链表作为底层实现,每个双端链表节点(node)都保存了一个字符串对象,而每个字符串对象都保存了一个列表元素
编码转换
使用 ziplist 编码的两个条件
列表对象保存的所有字符串元素的长度都小于64字节
列表对象保存的元素数量小于512个
以上两个条件的上限值是可以修改的,具体请看配置文件中关于list-max-ziplist-value选项和list-max-ziplist-entries选项的说明。
不能满足这两个条件的列表对象需要使用linkedlist编码
哈希对象
可以是ziplist或者hashtable
ziplist 编码
ziplist编码的哈希对象使用压缩列表作为底层实现,每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推入到压缩列表表尾
保存了同一键值对的两个节点总是紧挨在一起,保存键的节点在前,保存值的节点在后
先添加到哈希对象中的键值对会被放在压缩列表的表头方向,而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向
hashtable 编码
hashtable编码的哈希对象使用字典作为底层实现,哈希对象中的每个键值对都使用一个字典键值对来保存
字典的每个键都是一个字符串对象,对象中保存了键值对的键
字典的每个值都是一个字符串对象,对象中保存了键值对的值
哈希对象保存的所有键值对的键和值的字符串长度都小于64字节
哈希对象保存的键值对数量小于512个
这两个条件的上限值是可以修改的,具体请看配置文件中关于hash-max-ziplist-value选项和hash-max-ziplist-entries选项的说明
不能满足这两个条件的哈希对象需要使用hashtable编码
集合对象
可以是 intset 或者 hashtable
intset 编码
intset编码的集合对象使用整数集合作为底层实现,集合对象包含的所有元素都被保存在整数集合里面
intset 会根据传入的整数,修改 encoding 属性来做类型升级操作,但是没有降级操作。
hashtable编码的集合对象使用字典作为底层实现,字典的每个键都是一个字符串对象,每个字符串对象包含了一个集合元素,而字典的值则全部被设置为NULL。
使用 intset 编码的两个条件
集合对象保存的所有元素都是整数值
集合对象保存的元素数量不超过512个
第二个条件的上限值是可以修改的,具体请看配置文件中关于set-max-intset-entries选项的说明
不能满足这两个条件的集合对象需要使用hashtable编码
有序集合对象
可以是 ziplist 或者 skiplist
ziplist编码的压缩列表对象使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个元素则保存元素的分值(score)。
压缩列表内的集合元素按分值从小到大进行排序,分值较小的元素被放置在靠近表头的方向,而分值较大的元素则被放置在靠近表尾的方向。
skiplist 编码
skiplist编码的有序集合对象使用zset结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表
跳跃表:
zset结构中的zsl跳跃表按分值从小到大保存了所有集合元素,每个跳跃表节点都保存了一个集合元素:跳跃表节点的object属性保存了元素的成员,而跳跃表节点的score属性则保存了元素的分值。
通过这个跳跃表,程序可以对有序集合进行范围型操作,比如ZRANK、ZRANGE等命令就是基于跳跃表API来实现的。
字典:
zset结构中的dict字典为有序集合创建了一个从成员到分值的映射,字典中的每个键值对都保存了一个集合元素:字典的键保存了元素的成员,而字典的值则保存了元素的分值。
通过这个字典,程序可以用O(1)复杂度查找给定成员的分值,ZSCORE命令就是根据这一特性实现的,而很多其他有序集合命令都在实现的内部用到了这一特性。
有序集合每个元素的成员都是一个字符串对象,而每个元素的分值都是一个double类型的浮点数。
值得一提的是,虽然zset结构同时使用跳跃表和字典来保存有序集合元素,但这两种数据结构都会通过指针来共享相同元素的成员和分值,所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值,也不会因此而浪费额外的内存。
为什么同时使用跳跃表和字典?
首先,可以明确的一点是:在理论上,有序集合可以单独使用字典或者跳跃表的其中一种数据结构来实现,但无论单独使用字典还是跳跃表,在性能上对比起同时使用字典和跳跃表都会有所降低。
如果我们只使用字典来实现有序集合,那么虽然以O(1)复杂度查找成员的分值这一特性会被保留,但是,因为字典以无序的方式来保存集合元素,所以每次在执行范围型操作——比如ZRANK、ZRANGE等命令时,程序都需要对字典保存的所有元素进行排序,完成这种排序需要至少O(NlogN)时间复杂度,以及额外的O(N)内存空间(因为要创建一个数组来保存排序后的元素)。
如果我们只使用跳跃表来实现有序集合,那么跳跃表执行范围型操作的所有优点都会被保留,但因为没有了字典,所以根据成员查找分值这一操作的复杂度将从O(1)上升为O(logN)。
有序集合保存的元素数量小于128个
有序集合保存的所有元素成员的长度都小于64字节
以上两个条件的上限值是可以修改的,具体请看配置文件中关于zset-max-ziplist-entries选项和zset-max-ziplist-value选项的说明
不能满足以上两个条件的有序集合对象将使用skiplist编码
类型检查与命令多态
Redis 中用于操作键的命令基本可以分为两种类型
可以对任何类型的键执行的命令
DEL、EXPIRE、RENAME、TYPE、OBJECT等等
只能对特定类型的键执行的命令
SET、GET、APPEND、STRLEN等命令只能对字符串键执行
HDEL、HSET、HGET、HLEN等命令只能对哈希键执行
RPUSH、LPOP、LINSERT、LLEN等命令只能对列表键执行
SADD、SPOP、SINTER、SCARD等命令只能对集合键执行
ZADD、ZCARD、ZRANK、ZSCORE等命令只能对有序集合键执行
类型检查的实现
为了确保只有指定类型的键可以执行某些特定的命令,在执行一个类型特定的命令之前,Redis 会先检查输入键的类型是否正确,然后再决定是否执行给定的命令
类型特定命令所进行的类型检查是通过 redisObject 结构的 type 属性来实现的
多态命令的实现
Redis 除了会根据值对象的类型来判断键是否能够执行指定命令之外,还会根据值对象的编码方式,选择正确的命令实现代码来执行命令
例如:列表对象有ziplist和linkedlist两种编码可用,其中前者使用压缩列表API来实现列表命令,而后者则使用双端链表API来实现列表命令。LLEN 命令是查询列表的长度的,只要我们对列表键执行 LLEN 命令,Redis 底层程序会根据值对象所使用的编码来选择正确的命令实现;如果列表值对象的编码为 ziplist,程序则使用 ziplistLen 函数来返回列表长度;如果列表值对象的编码为 linkedlist,程序则使用 listLength 函数来返回双端链表的长度。
实际上,我们可以将DEL、EXPIRE、TYPE等命令也称为多态命令,因为无论输入的键是什么类型,这些命令都可以正确地执行。DEL、EXPIRE等命令和LLEN等命令的区别在于,前者是基于类型的多态——一个命令可以同时用于处理多种不同类型的键,而后者是基于编码的多态——一个命令可以同时用于处理多种不同编码。
内存回收
实现机制
因为C语言并不具备自动内存回收功能,所以Redis在自己的对象系统中构建了一个引用计数(reference counting)技术实现的内存回收机制,通过这一机制,程序可以通过跟踪对象的引用计数信息,在适当的时候自动释放对象并进行内存回收。
每个对象的引用计数信息由redisObject结构的refcount属性记录
引用计数信息的变化流程
在创建一个新对象时,引用计数的值会被初始化为1
当对象被一个新程序使用时,它的引用计数值会被增一
当对象不再被一个程序使用时,它的引用计数值会被减一
当对象的引用计数值变为0时,对象所占用的内存会被释放
对象共享
除了用于实现引用计数内存回收机制之外,对象的引用计数属性还带有对象共享的作用。
对象共享步骤
将数据库键的值指针指向一个现有的值对象
将被共享的值对象的引用计数增一
整数类型的字符串对象共享机制
目前来说,Redis会在初始化服务器时,创建一万个字符串对象,这些对象包含了从0到9999的所有整数值,当服务器需要用到值为0到9999的字符串对象时,服务器就会使用这些共享对象,而不是新创建对象。
创建共享字符串对象的数量可以通过修改redis.h/REDIS_SHARED_INTEGERS常量来修改。
上面的共享对象,不单单只有字符串键可以使用,那些在数据结构中嵌套了字符串对象的对象(linkedlist编码的列表对象、hashtable编码的哈希对象、hashtable编码的集合对象,以及zset编码的有序集合对象)都可以使用这些共享对象。
为什么Redis不共享包含字符串的对象?
当服务器考虑将一个共享对象设置为键的值对象时,程序需要先检查给定的共享对象和键想创建的目标对象是否完全相同,只有在共享对象和目标对象完全相同的情况下,程序才会将共享对象用作键的值对象,而一个共享对象保存的值越复杂,验证共享对象和目标对象是否相同所需的复杂度就会越高,消耗的CPU时间也会越多
校验复杂度比较
如果共享对象是保存整数值的字符串对象,那么验证操作的复杂度为O(1)
如果共享对象是保存字符串值的字符串对象,那么验证操作的复杂度为O(N)
如果共享对象是包含了多个值(或者对象的)对象,比如列表对象或者哈希对象,那么验证操作的复杂度将会是O(N 2)
因此,尽管共享更复杂的对象可以节约更多的内存,但受到CPU时间的限制,Redis只对包含整数值的字符串对象进行共享。
对象的空转时长
除了前面介绍过的 type、encoding、ptr 和 refcount 四个属性之外,redisObject 结构包含的最后一个属性为 lru 属性,该属性记录了对象最后一次被命令程序访问的时间
空转时长 = 当前时间 - lru 时间
OBJECT IDLETIME 命令
我们可以通过 OBJECT IDLETIME 命令来打印出给定键的空转时长。
OBJECT IDLETIME命令的实现是特殊的,这个命令在访问键的值对象时,不会修改值对象的lru属性。
如果服务器打开了maxmemory选项,并且服务器用于回收内存的算法为volatile-lru或者allkeys-lru,那么当服务器占用的内存数超过了maxmemory选项所设置的上限值时,空转时长较高的那部分键会优先被服务器释放,从而回收内存。
单机数据库的实现
数据库
服务器中的数据库
Redis服务器的所有数据库都保存在 redis.h/redisServer结构的 db 数组中
db 数组的每个项都是一个 redis.h/redisDb 结构。
而数据库的数量则由redisServer.dbnum 属性保存,dbnum 属性的值由服务器配置的 dtabase 选项决定,默认是 16.
切换数据库
实现:Redis 客户端默认目标数据库为 0号 数据库,但是可以通过执行 SELECT 命令来切换目标数据库。
原理
在服务器内部,客户端状态 redisClient 结构的 db 属性记录了客户端当前的目标数据库,这个属性是一个指向 redisDb 结构的指针。
客户端通过修改目标数据库指针,让 redisClient.db 指向 redisServer.db 数组中的不同元素来切换不同的数据库。
ps:在开发中,谨慎处理多数据库程序,多次数据库切换可能会让自己忘记当前正在使用的是哪个数据库。为了避免对数据库进行误操作,在执行 Redis 命令前,先执行以下 SELECT 命令。
数据库键空间
Redis 是一个键值对(key-value pair)数据库服务器,服务器中的每个数据库都由一个 redis.h/redisDb 结构表示,其中,redisDb 结构的 dict 字典保存了数据库中的所有键值对,我们将这个字典称为键空间(keyspace)
键空间和用户所见的数据库是直接对应的
键空间的键也就是数据库的键,每个键都是一个字符串对象
键空间的值也就是数据库的值,每个值可以是字符串对象、列表对象、哈希表对象、集合对象和有序集合对象中的任意一种Redis对象
所有对数据库的操作,实际上都是通过对键空间字典进行操作来实现的。
读写键空间时的维护操作
在读取一个键之后(读操作和写操作都要对键进行读取),服务器会根据键是否存在来更新服务器的键空间命中(hit)次数或键空间不命中(miss)次数,这两个值可以在INFO stats命令的keyspace_hits属性和keyspace_misses属性中查看。
在读取一个键之后,服务器会更新键的LRU(最后一次使用)时间,这个值可以用于计算键的闲置时间,使用OBJECT idletime命令可以查看键key的闲置时间。
如果服务器在读取一个键时发现该键已经过期,那么服务器会先删除这个过期键,然后才执行余下的其他操作。
如果有客户端使用WATCH命令监视了某个键,那么服务器在对被监视的键进行修改之后,会将这个键标记为脏(dirty),从而让事务程序注意到这个键已经被修改过。
服务器每次修改一个键之后,都会对脏(dirty)键计数器的值增1,这个计数器会触发服务器的持久化以及复制操作。
如果服务器开启了数据库通知功能,那么在对键进行修改之后,服务器将按配置发送相应的数据库通知。
设置键的生存时间或过期时间
设置生存时间
通过EXPIRE命令或者PEXPIRE命令,客户端可以以秒或者毫秒精度为数据库中的某个键设置生存时间(Time To Live,TTL),在经过指定的秒数或者毫秒数之后,服务器就会自动删除生存时间为0的键。
EXPIRE<key><ttl>命令用于将键key的生存时间设置为ttl秒。
PEXPIRE<key><ttl>命令用于将键key的生存时间设置为ttl毫秒。
设置过期时间
通过EXPIREAT命令或PEXPIREAT命令,以秒或者毫秒精度给数据库中的某个键设置过期时间(expire time);这个过期时间是一个 UNIX 时间戳,当键的过期时间来临时,服务器就会自动从数据库中删除这个键。
EXPIREAT<key><timestamp>命令用于将键key的过期时间设置为timestamp所指定的秒数时间戳。
PEXPIREAT<key><timestamp>命令用于将键key的过期时间设置为timestamp所指定的毫秒数时间戳。
查询键剩余的生存时间
TTL 命令和 PTTL 命令
TTL命令以秒为单位返回键的剩余生存时间,而PTTL命令则以毫秒为单位返回键的剩余生存时间。
TTL和PTTL两个命令都是通过计算键的过期时间和当前时间之间的差来实现的。
重点:实际上EXPIRE、PEXPIRE、EXPIREAT三个命令都是使用PEXPIREAT命令来实现的:无论客户端执行的是以上四个命令中的哪一个,经过转换之后,最终的执行效果都和执行PEXPIREAT命令一样。
过期字典 expires
实现
redisDb 结构的 expires 字典保存了数据库中所有键的过期时间,我们称这个字典为过期字典。
过期字典的键是一个指针,这个指针指向键空间中的某个键对象(也即是某个数据库键)。
过期字典的值是一个long long类型的整数,这个整数保存了键所指向的数据库键的过期时间——一个毫秒精度的UNIX时间戳。
移除过期时间
PERSIST命令可以移除一个键的过期时间
PERSIST命令就是PEXPIREAT命令的反操作:PERSIST命令在过期字典中查找给定的键,并解除键和值(过期时间)在过期字典中的关联。
过期键的判定
Redis 检查键是否过期,是通过函数从过期字典expires 中查询键对应的过期时间,然后和当前时间判断是否过期。
当然了,我们也可以利用 TTL 命令来判断是否过期,但是直接访问过期字典会比执行一个命令稍微快一些。
Redis使用惰性删除和定期删除两种策略来删除过期的键
惰性删除
过期键的惰性删除策略由 db.c/expireIfNeeded 函数实现,所有读写数据库的 Redis 命令在执行之前都会调用 expireIfNeeded 函数对输入键进行检查
expireIfNeeded 函数就像一个过滤器,它可以在命令真正执行之前,过滤掉过期的输入键,从而避免命令接触到过期键。
定期删除
过期键的定期删除策略由 redis.c/activeExpireCycle 函数实现,每当Redis的服务器周期性操作 redis.c/serverCron 函数执行时,activeExpireCycle 函数就会被调用,它在规定的时间内,分多次遍历服务器中的各个数据库,从数据库的 expires 字典中随机检查一部分键的过期时间,并删除其中的过期键。
activeExpireCycle 函数的工作模式
函数每次运行时,都从一定数量的数据库中取出一定数量的随机键进行检查,并删除其中的过期键。
全局变量current_db会记录当前activeExpireCycle函数检查的进度,并在下一次activeExpireCycle 函数调用时,接着上一次的进度进行处理。
随着 activeExpireCycle 函数的不断执行,服务器中的所有数据库都会被检查一遍,这时函数将current_db变量重置为0,然后再次开始新一轮的检查工作。
AOF、RDB和复制功能对过期键的处理
执行SAVE命令或者BGSAVE命令所产生的新RDB文件不会包含已经过期的键。
如果是主服务器模式,服务器载入 RDB 文件时,会过滤掉已过期的键;如果是从服务器模式,服务器不会过滤掉已过期的键。
当过期键被惰性删除或者定期删除后,程序会向 AOF 文件追加一条 DEL 命令。
AOF 重写会过滤掉已过期的键。
从服务器的删除策略
当主服务器删除一个过期键之后,它会向所有从服务器发送一条DEL命令,显式地删除过期键。
从服务器即使发现过期键也不会自作主张地删除它,而是等待主节点发来DEL命令,这种统一、中心化的过期键删除策略可以保证主从服务器数据的一致性。
数据库通知
数据库通知是Redis 2.8版本新增加的功能,这个功能可以让客户端通过订阅给定的频道或者模式,来获知数据库中键的变化,以及数据库中命令的执行情况。
键空间通知(key-space notification)
例子:客户端获取0号数据库中针对 message 键执行的所有命令:subscribe __keyspace@0__:message
键事件通知(key-event notification)
例子:客户端如何获取0号数据库中所有指定 DEL 命令的键:subscribe __keyevent@0__:del
服务器配置的notify-keyspace-events选项决定了服务器所发送通知的类型
想让服务器发送所有类型的键空间通知和键事件通知,可以将选项的值设置为AKE。
想让服务器发送所有类型的键空间通知,可以将选项的值设置为AK。
想让服务器发送所有类型的键事件通知,可以将选项的值设置为AE。
想让服务器只发送和字符串键有关的键空间通知,可以将选项的值设置为K$。
想让服务器只发送和列表键有关的键事件通知,可以将选项的值设置为El。
发送通知的实现
发送数据库通知的功能是由notify.c/notifyKeyspaceEvent函数实现的
函数的type参数是当前想要发送的通知的类型,程序会根据这个值来判断通知是否就是服务器配置notify-keyspace-events选项所选定的通知类型,从而决定是否发送通知。
event、keys和dbid分别是事件的名称、产生事件的键,以及产生事件的数据库号码,函数会根据type参数以及这三个参数来构建事件通知的内容,以及接收通知的频道名。
每当一个Redis命令需要发送数据库通知的时候,该命令的实现函数就会调用notify-KeyspaceEvent函数,并向函数传递传递该命令所引发的事件的相关信息。
伪代码
notifyKeyspaceEvent函数执行以下操作
先根据notify-keyspace-events 判断,看给定的通知类型 type 是否允许发送通知,如果不允许则直接返回,不做任何操作。
如果允许发送,则检测服务器是否允许发送键空间通知,如果允许,则构建频道名称并发送事件通知
最后,函数还会检测服务器是否允许发送键事件通知,如果允许的话,则构建频道名称并发送事件通知
RDB 持久化
概念
我们将 Redis 服务器中的非空的数据库以及它们的键值对统称为数据库状态。
因为 Redis 是内存数据库,所以它的数据库状态都是存储在内存里的,如果不将数据库状态保存到磁盘里,一旦服务进程退出,Redis 的数据库状态也会消失不见。
Redis 提供了 RDB 持久化功能,可以将内存中的数据库状态保存到磁盘里面,对应的是一个二进制文件。
RDB 持久化可以手动执行,也可以根据服务器配置选项定期执行。
RDB 文件的创建和载入
创建
SAVE 命令:阻塞 Redis 服务器进程,直到 RDB 文件创建完毕为止,在服务器进程阻塞期间,服务器不能处理任何命令请求。
BGSAVE 命令:派生出一个子进程,然后由子进程负责创建 RDB 文件,服务器进程(父进程)继续处理命令请求。
SAVE 命令 和 BGSAVE 命令底层都是由 rdb.c/rdbSave 函数完成,只不过俩命令会以不同的方式调用这个函数。
载入
RDB文件的载入工作是在服务器启动时自动执行的,所以Redis并没有专门用于载入RDB文件的命令,只要Redis服务器在启动时检测到RDB文件存在,它就会自动载入RDB文件。
ps:如果 Redis 开启了 AOF 持久化功能,那么服务器会优先使用 AOF 文件来还原数据库状态。
服务器在载入RDB文件期间,会一直处于阻塞状态,直到载入工作完成为止。
执行 RDB 持久化命令时服务器的状态
SAVE 命令:Redis 服务会被阻塞,客户端发送的所有命令请求都会被拒绝;等待 SAVE 命令执行完毕,才会接收客户端的命令请求并执行。
BGSAVE 命令:因为此命令会 fork 出一个子进程,所以完全不会影响 Redis 服务的运行,可以正常接收客户端的命令请求并执行。
命令之间的影响
BGSAVE 命令执行期间,服务器会拒绝客户端发送的 SAVE 命令;避免父进程和子进程同时执行两个 rdbSave,防止产生竞争条件。
BGSAVE 命令执行期间,服务器也会拒绝客户端发送的 BGSAVE 命令。
BGSAVE 命令执行,服务器会拒绝客户端发送的 BGREWRITEAOF 命令;同理,BGREWRITEAOF 命令执行,服务器会拒绝客户端发送的 BGSAVE 命令。这两个命令在操作方面并没有什么冲突的地方,考虑的只是性能问题,因为两个命令都会 fork 出一个子进程。
自动间隔性保存
Redis允许用户通过设置服务器配置的save选项,让服务器每隔一段时间自动执行一次BGSAVE命令。
默认的 save 配置
save 900 1:900秒内至少进行了1次修改,则会执行 BGSAVE 命令
save 300 10:300秒内至少进行了10次修改,则会执行 BGSAVE 命令
save 60 10000:60秒内至少进行了10000次修改,则会执行 BGSAVE 命令
Redis 启动时,会读取配置文件的 save 选项或传入启动参数的 save 选项,如果没有则使用默认值
使用服务器状态 redisServer 结构的 saveparams 属性来保存 save 配置
除了saveparams数组之外,服务器状态还维持着一个dirty计数器,以及一个lastsave属性
dirty计数器记录距离上一次成功执行SAVE命令或者BGSAVE命令之后,服务器对数据库状态(服务器中的所有数据库)进行了多少次修改(包括写入、删除、更新等操作)
lastsave属性是一个UNIX时间戳,记录了服务器上一次成功执行SAVE命令或者BGSAVE命令的时间。
ps:如果使用 sadd 往集合里面一次添加三个元素,dirty计数器的值会增加3。
Redis 的服务器周期性操作函数 serverCron 默认每隔100毫秒就会执行一次,该函数用于对正在运行的服务器进行维护,它的其中一项工作就是检查 save 选项所设置的保存条件是否已经满足,如果满足的话,就执行 BGSAVE 命令。
RDB 文件结构(大写表示常量,小写表示变量和数据)
完整 RDB 文件所包含的各个部分
REDIS:常量,\"R\" \"E\" \"D\" \"I\" \"S\" 五个字符
db_version:四个字节,记录 RDB 文件的版本号
databases
如果服务器的数据库状态为空(所有数据库都是空的),那么这个部分也为空,长度为0字节
如果服务器的数据库状态为非空(有至少一个数据库非空),那么这个部分也为非空,根据数据库所保存键值对的数量、类型和内容不同,这个部分的长度也会有所不同。
EOF:常量,一个字节,数字 337
check_sum
一个8字节长的无符号整数,保存着一个校验和
这个校验和是程序通过对REDIS、db_version、databases、EOF四个部分的内容进行计算得出的
服务器在载入RDB文件时,会将载入数据所计算出的校验和与check_sum所记录的校验和进行对比,以此来检查RDB文件是否有出错或者损坏的情况出现
databases 部分
每个非空数据库在 RDB 文件中都可以保存为 SELECTDB、db_number、key_value_pairs 三个部分
SELECTDB:是一个常量,长度为1个字节,当程序读到这个值,就知道接下来读入的是一个数据库号码。
db_number:保存着一个数据库号码,根据号码的大小不同,长度可以是1字节、2字节或者5字节。当程序读到这个值时,会执行 SELECT 命令来进行数据库切换。
key_value_pairs:保存了数据库中的所有键值对数据,如果键值对带有过期时间,那么过期时间也会和键值对保存在一起。根据键值对的数量、类型、内容以及是否有过期时间等条件的不同,key_value_pairs部分的长度也会有所不同。
key_value_pairs 部分
保存了一个或多个键值对,如果键值对带有过期时间,那么过期时间也会被保存在内。
不带过期时间的结构
TYPE key value
带过期时间的结构
EXPIRETIME_MS ms TYPE key value
TYPE:记录了 value 的类型,长度为1字节,值可以是以下常量的其中一个
REDIS_RDB_TYPE_STRING
REDIS_RDB_TYPE_LIST
REDIS_RDB_TYPE_SET
REDIS_RDB_TYPE_ZSET
REDIS_RDB_TYPE_HASH
REDIS_RDB_TYPE_LIST_ZIPLIST
REDIS_RDB_TYPE_SET_ZIPLIST
REDIS_RDB_TYPE_ZSET_ZIPLIST
REDIS_RDB_TYPE_HASH_ZIPLIST
key:总是一个字符串对象,它的编码方式和 REDIS_RDB_TYPE_STRING 类型的 value 一样。
value:根据 TYPE 类型的不同,以及保存内容长度的不同,value 的结构和长度也会有所不同。
EXPIRETIME_MS:常量,长度为1字节;当程序读到它,就知道接下来要读入的是以毫秒为单位的过期时间。
ms:一个8字节长的带符号整数,记录着一个以毫秒为单位的 UNIX 时间戳,它就是键值对的过期时间。
value 的编码
TYPE 的值为REDIS_RDB_TYPE_STRING,字符串对象的编码可以是REDIS_ENCODING_INT或者REDIS_ENCODING_RAW。
字符串对象编码是 REDIS_ENCODING_INT,那么字符串对象在 RDB 文件保存的结构为 \"ENCODING integer\"
ENCODING 的值可以是 REDIS_RDB_ENC_INT8、REDIS_RDB_ENC_INT16或者REDIS_RDB_ENC_INT32 三个常量的其中一个
integer 为整数值
字符串对象编码是 REDIS_ENCODING_RAW
RDB 文件压缩功能打开
如果字符串长度小于等于 20 字节,字符串对象在 RDB 文件保存结构为 \"len string\"
如果字符串长度大于 20 字节,保存的结构为 \"REDIS_RDB_ENC_LZF compressed_len origin_len compressed_string\"
ps:REDIS_RDB_ENC_LZF常量标志着字符串已经被LZF算法(http://liblzf.plan9.de)压缩过了,读入程序在碰到这个常量时,会根据之后的compressed_len、origin_len和compressed_string三部分,对字符串进行解压缩:其中compressed_len记录的是字符串被压缩之后的长度,而origin_len记录的是字符串原来的长度,compressed_string记录的则是被压缩之后的字符串
RDB 文件压缩功能关闭
不管字符串长度多少,字符串对象在 RDB 文件保存的结构为 \"len string\"
如果TYPE 的值为 REDIS_RDB_TYPE_LIST,那么 value 保存的就是一个 REDIS_ENCODING_LINKEDLIST 编码的列表对象
RDB 文件保存的结构为:\"list_length item1 item2 ... itemN\"
list_length:记录了列表的长度
item:代表列表项,每个列表项都是一个字符串对象,所以程序会以处理字符串对象的方式来保存和读入列表项。
例子:展示一个包含三个元素的列表
结构为: 3 5 \"hello\" 5 \"world\" 1 \"!\"
第一个列表项的长度为5,内容是字符串\"hello\"
第二个列表项的长度为5,内容是字符串\"world\"
第三个列表项的长度为1,内容是字符串\"!\"
如果TYPE 的值为 REDIS_RDB_TYPE_SET,那么 value 保存的就是一个 REDIS_ENCODING_HT 编码的集合对象
RDB 文件保存的结构为:\"set_size elem1 elem2 ... elemN\"
set_size:是集合的大小,记录了集合保存了多少个元素
elem:集合的元素,每个集合元素都是一个字符串对象,所以程序会以处理字符串对象的方式来保存和读入集合元素。
例子:展示一个包含三个元素的集合
结构为: 3 3 \"cat\" 3 \"dog\" 4 \"lion\"
第一个元素的长度为3,内容是字符串\"cat\"
第二个元素的长度为3,内容是字符串\"dog\"
第三个元素的长度为4,内容是字符串\"lion\"
哈希表对象
如果TYPE的值为REDIS_RDB_TYPE_HASH,那么value保存的就是一个REDIS_ENCODING_HT编码的集合对象
RDB 文件保存的结构为:\"hash_size key_value_pair1 key_value_pair2 ... key_value_pairN\"
hash_size:记录了哈希表的大小,哈希表有多少个键值对
key_value_pair:哈希表的键值对,键值对的键和值都是字符串对象,所以程序会以处理字符串对象的方式来保存和读入键和值。
结构中的每个键值对都以键紧挨着值的方式排列在一起:\"hash_size key1 value1 key2 value2 ... keyN valueN\"
例子:展示一个包含两个键值对的哈希表
结构为:2 1 \"a\" 5 \"apple\" 1 \"b\" 6 \"banana\"
第一个键值对,键是长度为1的字符串\"a\",值是长度为5的字符串\"apple\"
第二个键值对,键是长度为1的字符串\"b\",值是长度为6的字符串\"banana\"
如果TYPE的值为REDIS_RDB_TYPE_ZSET,那么value保存的就是一个REDIS_ENCODING_SKIPLIST编码的有序集合对象
RDB 文件保存的结构为:\"sorted_set_size element1 element2 ... elementN\"
sorted_set_size记录了有序集合的大小,也即是这个有序集合保存了多少元素
element:有序集合中的元素,每个元素分为成员(member)和分值(score),成员是一个字符串对象,分值则是一个 double 类型的浮点数,不过在 RDB 文件中,会将分值先转为字符串对象,然后再保存。
有序集合中的每个元素都以成员紧挨着分值的方式排列:\"sorted_set_size member1 score1 member2 score2 ... memberN scoreN\"
例子:展示一个包含两个元素的有序集合
结构:2 2 \"pi\" 4 \"3.14\" 1 \"e\" 3 \"2.7\"
第一个元素的成员是长度为2的字符串\"pi\",分值被转换成字符串之后变成了长度为4的字符串\"3.14\"
第二个元素的成员是长度为1的字符串\"e\",分值被转换成字符串之后变成了长度为3的字符串\"2.7\"
INTSET 编码的集合
如果TYPE的值为REDIS_RDB_TYPE_SET_INTSET,那么value保存的就是一个整数集合对象
RDB文件保存这种对象的方法是,先将整数集合转换为字符串对象,然后将这个字符串对象保存到RDB文件里面
如果程序在读入RDB文件的过程中,碰到由整数集合对象转换成的字符串对象,那么程序会根据TYPE值的指示,先读入字符串对象,再将这个字符串对象转换成原来的整数集合对象。
ZIPLIST编码的列表、哈希表或者有序集合
如果TYPE的值为REDIS_RDB_TYPE_LIST_ZIPLIST、REDIS_RDB_TYPE_HASH_ZIPLIST或者REDIS_RDB_TYPE_ZSET_ZIPLIST,那么value保存的就是一个压缩列表对象
RDB 文件保存这种对象的方法:
将压缩列表转换成一个字符串对象。
将转换所得的字符串对象保存到RDB文件。
如果程序在读入RDB文件的过程中,碰到由压缩列表对象转换成的字符串对象,那么程序会根据TYPE值的指示,执行以下操作:
读入字符串对象,并将它转换成原来的压缩列表对象
根据TYPE的值,设置压缩列表对象的类型:如果TYPE的值为REDIS_RDB_TYPE_LIST_ZIPLIST,那么压缩列表对象的类型为列表;如果TYPE的值为REDIS_RDB_TYPE_HASH_ZIPLIST,那么压缩列表对象的类型为哈希表;如果TYPE的值为REDIS_RDB_TYPE_ZSET_ZIPLIST,那么压缩列表对象的类型为有序集合
AOF 持久化
除了RDB持久化功能之外,Redis还提供了AOF(Append Only File)持久化功能。
与RDB持久化通过保存数据库中的键值对来记录数据库状态不同,AOF持久化是通过保存Redis服务器所执行的写命令来记录数据库状态的。
因为 Redis 的命令请求协议是纯文本格式的,所以写入 AOF 文件的所有命令也都是以 Redis 的命令请求协议格式保存的。
服务器在启动时,可以通过载入和执行AOF文件中保存的命令来还原服务器关闭之前的数据库状态
AOF 持久化功能的实现可分为命令追加(append)、文件写入、文件同步(sync)三个步骤
命令追加
Redis 的服务器状态 redisServer 结构里有一个属性叫 aof_buf。
当 AOF 持久化功能打开时,服务器在执行完一个写命令后,会以将写命令追加到 aof_buf 缓存区的末尾。
例子:
写命令:SET MSG HELLO
Redis 命令请求协议内容:*3\\$3\\SET\\$3\\MSG\\$5\\zHELLO\\
协议内容详解
*3:表示这个命令一共有三处地方
\\:每一个内容都用“\\”分隔
$3:表示接下来的内容长度为3个字符长度
文件写入与同步
Redis的服务器进程就是一个事件循环(loop),这个循环中的文件事件负责接收客户端的命令请求,以及向客户端发送命令回复,而时间事件则负责执行像serverCron函数这样需要定时运行的函数。
服务器在处理文件事件时并且执行的是写命令,会在命令实行后将写命令追加到 aof_buf 缓冲区里面,并且在结束一个事件循环之前,它都会调用 flushAppendOnlyFile 函数,根据服务器配置的 appendfsync 选项的值来判断是否将 aof_buf 缓冲区中的内容写入和保存到 AOF 文件里面。
appendfsync 选项
always:将 aof_buf 缓存区中的所有内容写入并同步到 AOF 文件
everysec:将 aof_buf 缓冲区中的所有内容写入到 AOF 文件,如果此时距离上次同步已经超过一秒,那么继续对 AOF 文件进行同步,并且这个同步操作是由一个线程专门负责执行的。
no:将 aof_buf 缓冲区中的所有内容写入 AOF 文件中,但并不对 AOF 文件进行同步,何时同步由操作系统来决定。
为什么分为文件写入和文件同步?
为了提高文件的写入效率,在现代操作系统中,当用户调用write函数,将一些数据写入到文件的时候,操作系统通常会将写入数据暂时保存在一个内存缓冲区里面,等到缓冲区的空间被填满、或者超过了指定的时限之后,才真正地将缓冲区中的数据写入到磁盘里面。
这种做法虽然提高了效率,但也为写入数据带来了安全问题,因为如果计算机发生停机,那么保存在内存缓冲区里面的写入数据将会丢失。
为此,系统提供了fsync和fdatasync两个同步函数,它们可以强制让操作系统立即将缓冲区中的数据写入到硬盘里面,从而确保写入数据的安全性。
AOF 文件的载入与数据还原
因为 AOF 文件包含了重建数据库状态的所有写命令,所以 Redis 服务器只需要读入并重新执行一遍 AOF 文件里面保存的写命令,即可恢复服务器关闭前的数据库状态。
详细步骤
创建一个不带网络连接的伪客户端(fake client)
从AOF文件中分析并读取出一条写命令
使用伪客户端执行被读出的写命令
一直执行步骤2和步骤3,直到AOF文件中的所有写命令都被处理完毕为止
AOF 重写
一个键,可能会有多个写命令,但是 AOF 文件其实可以只需要用一条写命令来记录当前最新的数据即可。
为了解决 AOF 文件体积膨胀的问题,Redis 提供了 AOF 文件重写功能。
虽然Redis将生成新AOF文件替换旧AOF文件的功能命名为“AOF文件重写”,但实际上,AOF文件重写并不需要对现有的AOF文件进行任何读取、分析或者写入操作,这个功能是通过读取服务器当前的数据库状态来实现的。
为了避免执行写命令时造成客户端输入缓冲区溢出,重写程序会通过 redis.h/REDIS_AOF_REWRITE_ITEMS_PER_CMD 这个常量的值来控制写命令的键的元素数量。元素数量超过了,会使用多条写命令来完成键的写入。
后台重写(BGWRITEAOF 命令的实现原理)
Redis 会将 AOF 重写程序放到子进程里面执行
由于子进程执行 AOF 重写,所以不影响 主进程继续接收客户端的写命令,如果之后的写命令对已经重写完的键进行操作,会导致数据不一致的现象
如何解决?
当Redis服务器执行完一个写命令之后,它会同时将这个写命令发送给AOF缓冲区和AOF重写缓冲区
当子进程完成 AOF 重写工作后,会向主进程发送一个信号,主进程在接到该信号后,会调用一个信号处理函数,并执行以下工作。
1)将AOF重写缓冲区中的所有内容写入到新AOF文件中,这时新AOF文件所保存的数据库状态将和服务器当前的数据库状态一致。
2)对新的AOF文件进行改名,原子地(atomic)覆盖现有的AOF文件,完成新旧两个AOF文件的替换。
ps:信号函数执行会对主进程造成阻塞,其他的不会。
事件
书本的重点回顾
Redis服务器是一个事件驱动程序,服务器处理的事件分为时间事件和文件事件两类。
文件事件处理器是基于Reactor模式实现的网络通信程序。
文件事件是对套接字操作的抽象:每次套接字变为可应答(acceptable)、可写(writable)或者可读(readable)时,相应的文件事件就会产生。
文件事件分为AE_READABLE事件(读事件)和AE_WRITABLE事件(写事件)两类。
时间事件分为定时事件和周期性事件:定时事件只在指定的时间到达一次,而周期性事件则每隔一段时间到达一次。
服务器在一般情况下只执行serverCron函数一个时间事件,并且这个事件是周期性事件。
文件事件和时间事件之间是合作关系,服务器会轮流处理这两种事件,并且处理事件的过程中也不会进行抢占。
时间事件的实际处理时间通常会比设定的到达时间晚一些。
文件事件处理器
使用 I/O 多路复用(multiplexing)程序来同时监听多个套接字,并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
当被监听的套接字准备好执行连接应答(accept)、读取(read)、写入(write)、关闭(close)等操作时,与操作相对应的文件事件就会产生,这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。
构成
套接字:一个客户端对应一个套接字
I/O多路复用程序:
负责监听多个套接字,并向文件事件分派器传送那些产生了事件的套接字。
I/O多路复用程序,利用队列来控制产生事件的套接字的并发;队列中的套接字以有序、同步、每次一个的方式分派给文件事件分派器。
当一个套接字的事件被处理完了,I/O多路复用程序才会接着给文件事件分派器传送下一个队列中的套接字。
文件事件分派器(dispatcher):接收 I/O多路复用程序传送过来的套接字,并根据套接字产生的事件的类型,调用相应的事件处理器。
事件处理器:是一个个函数,它们定义了某个事件发生时,服务器应该执行的动作。
I/O多路复用程序的实现
Redis的I/O多路复用程序的所有功能都是通过包装常见的select、epoll、evport和kqueue这些I/O多路复用函数库来实现的
每个I/O多路复用函数库在Redis源码中都对应一个单独的文件,比如ae_select.c、ae_epoll.c、ae_kqueue.c,诸如此类
程序会在编译时自动选择系统中性能最高的I/O多路复用函数库来作为Redis的I/O多路复用程序的底层实现
事件的类型
ae.h/AE_READABLE事件
当套接字变得可读时(客户端对套接字执行write操作【发送命令请求】,或者执行close操作),或者有新的可应答(acceptable)套接字出现时(客户端对服务器的监听套接字执行connect操作),套接字产生AE_READABLE事件。
ae.h/AE_WRITABLE事件
当套接字变得可写时(客户端对套接字执行read操作【等待服务器对命名请求的响应】),套接字产生AE_WRITABLE事件。
I/O 多路复用程序允许同时监听套接字的 AE_READABLE事件和 AE_WRITABLE事件,但是如果同时产生两种事件,优先处理 AE_READABLE事件。
文件事件重点API
ae.c/aeCreateFileEvent函数接受一个套接字描述符、一个事件类型,以及一个事件处理器作为参数,将给定套接字的给定事件加入到I/O多路复用程序的监听范围之内,并对事件和事件处理器进行关联。
ae.c/aeDeleteFileEvent函数接受一个套接字描述符和一个监听事件类型作为参数,让I/O多路复用程序取消对给定套接字的给定事件的监听,并取消事件和事件处理器之间的关联。
ae.c/aeGetFileEvents函数接受一个套接字描述符,返回该套接字正在被监听的事件类型
ae.c/aeWait函数接受一个套接字描述符、一个事件类型和一个毫秒数为参数,在给定的时间内阻塞并等待套接字的给定类型事件产生,当事件成功产生,或者等待超时之后,函数返回。
ae.c/aeApiPoll函数接受一个sys/time.h/struct timeval结构为参数,并在指定的时间內,阻塞并等待所有被aeCreateFileEvent函数设置为监听状态的套接字产生文件事件,当有至少一个事件产生,或者等待超时后,函数返回。
ae.c/aeProcessEvents函数是文件事件分派器,它先调用aeApiPoll函数来等待事件产生,然后遍历所有已产生的事件,并调用相应的事件处理器来处理这些事件。
ae.c/aeGetApiName函数返回I/O多路复用程序底层所使用的I/O多路复用函数库的名称:返回\"epoll\"表示底层为epoll函数库,返回\"select\"表示底层为select函数库,诸如此类。
文件事件的处理器
为了对连接服务器的各个客户端进行应答,服务器要为监听套接字关联连接应答处理器。
为了接收客户端传来的命令请求,服务器要为客户端套接字关联命令请求处理器。
为了向客户端返回命令的执行结果,服务器要为客户端套接字关联命令回复处理器。
当主服务器和从服务器进行复制操作时,主从服务器都需要关联特别为复制功能编写的复制处理器。
一次完整的客户端与服务器连接事件示例
假设一个Redis服务器正在运作,那么这个服务器的监听套接字的AE_READABLE事件应该正处于监听状态之下,而该事件所对应的处理器为连接应答处理器。
如果这时有一个Redis客户端向服务器发起连接,那么监听套接字将产生AE_READABLE事件,触发连接应答处理器执行。处理器会对客户端的连接请求进行应答,然后创建客户端套接字,以及客户端状态,并将客户端套接字的AE_READABLE事件与命令请求处理器进行关联,使得客户端可以向主服务器发送命令请求。
之后,假设客户端向主服务器发送一个命令请求,那么客户端套接字将产生AE_READABLE事件,引发命令请求处理器执行,处理器读取客户端的命令内容,然后传给相关程序去执行。
执行命令将产生相应的命令回复,为了将这些命令回复传送回客户端,服务器会将客户端套接字的AE_WRITABLE事件与命令回复处理器进行关联。当客户端尝试读取命令回复的时候,客户端套接字将产生AE_WRITABLE事件,触发命令回复处理器执行,当命令回复处理器将命令回复全部写入到套接字之后,服务器就会解除客户端套接字的AE_WRITABLE事件与命令回复处理器之间的关联。
子主题
时间事件
分类
定时事件
周期性事件(目前版本的Redis只使用周期性事件,而没有使用定时事件。)
id:服务器为时间事件创建的全局唯一ID(标识号)。ID号按从小到大的顺序递增,新事件的ID号比旧事件的ID号要大。
when:毫秒精度的UNIX时间戳,记录了时间事件的到达(arrive)时间。
timeProc:时间事件处理器,一个函数。当时间事件到达时,服务器就会调用相应的处理器来处理事件。
服务器将所有时间事件都放在一个无序链表中,每当时间事件执行器运行时,它就遍历整个链表,查找所有已到达的时间事件,并调用相应的事件处理器。ps:所谓无序,是不按照过期时间来排序
将时间事件添加到无序链表是使用头插法ps:和尾插法相比下性能较高
无序链表并不影响时间事件处理器的性能:因为正常模式下的 Redis 服务器只有一个时间事件:serverCron;而即使在 benchmark 模式下也只有两个时间事件。
serverCron函数
主要工作
更新服务器的各类统计信息,比如时间、内存占用、数据库占用情况等。
清理数据库中的过期键值对。
关闭和清理连接失效的客户端。
尝试进行AOF或RDB持久化操作。
如果服务器是主服务器,那么对从服务器进行定期同步。
如果处于集群模式,对集群进行定期同步和连接测试。
运行方式:周期性事件的方式,定期执行直到 Redis 服务关闭。
从 Redis 2.8开始,可以利用 hz 选项来指定执行周期。
事件的调度和执行
事件的调度和执行由ae.c/aeProcessEvents函数负责
aeApiPoll函数的最大阻塞时间由到达时间最接近当前时间的时间事件决定,这个方法既可以避免服务器对时间事件进行频繁的轮询(忙等待),也可以确保aeApiPoll函数不会阻塞过长时间。
因为文件事件是随机出现的,如果等待并处理完一次文件事件之后,仍未有任何时间事件到达,那么服务器将再次等待并处理文件事件。随着文件事件的不断执行,时间会逐渐向时间事件所设置的到达时间逼近,并最终来到到达时间,这时服务器就可以开始处理到达的时间事件了。
对文件事件和时间事件的处理都是同步、有序、原子地执行的,服务器不会中途中断事件处理,也不会对事件进行抢占,因此,不管是文件事件的处理器,还是时间事件的处理器,它们都会尽可地减少程序的阻塞时间,并在有需要时主动让出执行权,从而降低造成事件饥饿的可能性。比如说,在命令回复处理器将一个命令回复写入到客户端套接字时,如果写入字节数超过了一个预设常量的话,命令回复处理器就会主动用break跳出写入循环,将余下的数据留到下次再写;另外,时间事件也会将非常耗时的持久化操作放到子线程或者子进程执行。
因为时间事件在文件事件之后执行,并且事件之间不会出现抢占,所以时间事件的实际处理时间,通常会比时间事件设定的到达时间稍晚一些。
客户端
书本重点回顾
服务器状态结构使用clients链表连接起多个客户端状态,新添加的客户端状态会被放到链表的末尾。
客户端状态的flags属性使用不同标志来表示客户端的角色,以及客户端当前所处的状态。
输入缓冲区记录了客户端发送的命令请求,这个缓冲区的大小不能超过1GB。
命令的参数和参数个数会被记录在客户端状态的argv和argc属性里面,而cmd属性则记录了客户端要执行命令的实现函数。
客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用,其中固定大小缓冲区的最大大小为16KB,而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值。
输出缓冲区限制值有两种,如果输出缓冲区的大小超过了服务器设置的硬性限制,那么客户端会被立即关闭;除此之外,如果客户端在一定时间内,一直超过服务器设置的软性限制,那么客户端也会被关闭。
当一个客户端通过网络连接连上服务器时,服务器会为这个客户端创建相应的客户端状态。网络连接关闭、发送了不合协议格式的命令请求、成为CLIENT KILL命令的目标、空转时间超时、输出缓冲区的大小超出限制,以上这些原因都会造成客户端被关闭。
处理Lua脚本的伪客户端在服务器初始化时创建,这个客户端会一直存在,直到服务器关闭。
载入AOF文件时使用的伪客户端在载入工作开始时动态创建,载入工作完毕之后关闭。
Redis 服务器使用 redis.h/redisClient 结构来保存客户端当前的状态信息,以及执行相关功能时需要用到的数据结构
redisClient 属性
客户端状态的fd属性记录了客户端正在使用的套接字描述符
伪客户端的 fd 属性值为 -1;伪客户端处理的命令请求来源于 AOF 文件或者 Lua 脚本。
普通客户端的 fd 属性值为大于 -1 的整数。
客户端的名字:可以使用 CLIENT setname 命令为客户端设置一个名字
客户端的标志属性flags记录了客户端的角色(role),以及客户端目前所处的状态
flags属性的值可以是单个标志
也可以是多个标志的二进制或
指向客户端正在使用的数据库的指针,以及该数据库的号码
客户端的输入缓冲区和输出缓冲区
输入缓冲区
客户端状态的输入缓冲区用于保存客户端发送的命令请求ps:保存的格式就是 Redis 的命令请求协议
输入缓冲区的大小会根据输入内容动态地缩小或者扩大,但它的最大大小不能超过1GB,否则服务器将关闭这个客户端。
输出缓冲区
每个客户端都有两个输出缓冲区可用,一个缓冲区的大小是固定的,另一个缓冲区的大小是可变的
客户端的固定大小缓冲区由buf和bufpos两个属性组成.buf是一个大小为REDIS_REPLY_CHUNK_BYTES字节的字节数组,而bufpos属性则记录了buf数组目前已使用的字节数量。
可变大小缓冲区由reply链表和一个或多个字符串对象组成。通过使用链表来连接多个字符串对象,服务器可以为客户端保存一个非常长的命令回复,而不必受到固定大小缓冲区16KB大小的限制。
客户端命令与命令参数与函数指针
argv 属性是一个数组,数组中的每个项都是一个字符串对象,其中argv[0]是要执行的命令,而之后的其他项则是传给命令的参数。
argc 属性则负责记录argv数组的长度。
cmd 属性是指向 argv[0] 对应的 RedisCommand 结构的指针
ps:redis 是不区分命令的大小写的
客户端状态的authenticated属性用于记录客户端是否通过了身份验证
0:代表未通过身份验证,除了 AUTH 命令,其他命令都会被服务器拒绝
1:代表通过身份验证
时间
ctime 属性记录了创建客户端的时间,这个时间可以用来计算客户端与服务器已经连接了多少秒,CLIENT list命令的age域记录了这个秒数
lastinteraction 属性记录了客户端与服务器最后一次进行互动(interaction)的时间,这里的互动可以是客户端向服务器发送命令请求,也可以是服务器向客户端发送命令回复。
obuf_soft_limit_reached_time 属性记录了输出缓冲区第一次到达软性限制(soft limit)的时间
客户端的复制状态信息,以及进行复制所需的数据结构
客户端执行BRPOP、BLPOP等列表阻塞命令时使用的数据结构
客户端的事务状态,以及执行WATCH命令时用到的数据结构
客户端执行发布与订阅功能时用到的数据结构
创建与关闭
创建普通客户端
如果客户端是通过网络连接与服务器进行连接的普通客户端,那么在客户端使用connect函数连接到服务器时,服务器就会调用连接事件处理器(在第12章有介绍),为客户端创建相应的客户端状态,并将这个新的客户端状态添加到服务器状态结构clients链表的末尾。
关闭普通客户端
客户端可以因多种原因而被关闭。
伪客户端
Lua 脚本的伪客户端
服务器会在初始化时创建负责执行Lua脚本中包含的Redis命令的伪客户端,并将这个伪客户端关联在服务器状态结构的lua_client属性中
lua_client伪客户端在服务器运行的整个生命期中会一直存在,只有服务器被关闭时,这个客户端才会被关闭。
AOF 文件的伪客户端
服务器在载入AOF文件时,会创建用于执行AOF文件包含的Redis命令的伪客户端,并在载入完成之后,关闭这个伪客户端。
服务器
一个命令请求从发送到完成主要包括以下步骤:1)客户端将命令请求发送给服务器;2)服务器读取命令请求,并分析出命令参数;3)命令执行器根据参数查找命令的实现函数,然后执行实现函数并得出命令回复;4)服务器将命令回复返回给客户端。
serverCron函数默认每隔100毫秒执行一次,它的工作主要包括更新服务器状态信息,处理服务器接收的SIGTERM信号,管理客户端资源和数据库状态,检查并执行持久化操作等等。
服务器从启动到能够处理客户端的命令请求需要执行以下步骤:1)初始化服务器状态;2)载入服务器配置;3)初始化服务器数据结构;4)还原数据库状态;5)执行事件循环。
命令请求的执行过程
发送命令请求:
协议格式转换:客户端读取用户写入的命令请求,将请求转为 Redis 规定的协议格式
套接字发送命令:然后连接服务器的套接字,将协议格式的命令请求发送给服务器。
读取命令请求:
命令请求保存到输入缓冲区:读取套接字中协议格式的命令请求,并将其保存到客户端的输入缓冲区里面
分析命令请求:对输入缓冲区中的命令请求进行分析,提取出命令请求中包含的命令参数、以及命令参数的个数,然后分别将参数和参数个数保存到客户端状态的argv属性和argc属性里面。
执行命令:服务器通过调用命令执行器来完成执行命令的操作
查找命令实现:根据客户端状态的 argv[0] 参数,在命令表查找参数所指定的命令(redisCommand结构),然后保存到客户端状态的 cmd 属性里面。
命令表是一个字典,字典的键是一个个命令名字,例如\"set\
执行预备操作:在真正执行命令之前,程序还需要进行一些预报操作,从而保证命令可以正确、顺利地被执行。
检查客户端状态(RedisClient)的 cmd 指针是否为null
根据 cmd 属性指向的 redisCommand结构的 arity 属性,检查命令请求的参数个数是否正确
检查客户端是否通过了身份验证
如果服务器打开了 maxmemory 功能,命令执行前判断内存是否足够
如果服务器上一次执行 BGSAVE 命令失败,并且开启了 stop-writes-on-bgsave-error 功能,则拒绝执行命令
判断客户端此时是否正在用 subscribe 命令订阅频道,如果是,只能执行 subscribe 、 psubscribe 、 unsubscribe、punsubscribe 这四个命令。
如果服务器正在进行数据载入,那么客户端发送的命令必须带有l标识(比如INFO、SHUTDOWN、PUBLISH等等)才会被服务器执行,其他命令都会被服务器拒绝。
如果服务器因为执行Lua脚本而超时并进入阻塞状态,那么服务器只会执行客户端发来的SHUTDOWN nosave命令和SCRIPT KILL命令,其他命令都会被服务器拒绝。
如果客户端正在执行事务,那么服务器只会执行客户端发来的EXEC、DISCARD、MULTI、WATCH四个命令,其他命令都会被放进事务队列中。
如果服务器打开了监视器功能,那么服务器会将要执行的命令和参数等信息发送给监视器。当完成了以上预备操作之后,服务器就可以开始真正执行命令了。
上面只是单机情况下的检查操作,集群会更多。。。
调用命令的实现函数:client -> cmd -> proc(client); 然后当命令执行完毕后,会将对应的回复保存在客户端的输出缓冲区中,之后会为客户端的套接字关联命令回复处理器(处理器会将回复返回给客户端)。
执行后续工作:
慢查询日志功能:如果服务器开启了慢查询日志功能,那么慢查询日志模块会检查是否需要为刚刚执行完的命令请求添加一条新的慢查询日志。
命令耗时记录:根据刚刚执行命令所耗费的时长,更新被执行命令的redisCommand结构的milliseconds属性,并将命令的redisCommand结构的calls计数器的值增一。
AOF持久化:如果服务器开启了AOF持久化功能,那么AOF持久化模块会将刚刚执行的命令请求写入到AOF缓冲区里面。
主从复制:如果有其他从服务器正在复制当前这个服务器,那么服务器会将刚刚执行的命令传播给所有从服务器。
命令回复发送给客户端
命令回复处理器发送回复:当客户端套接字变为可写状态,服务器会执行命令回复处理器,将客户端(redisClient)中输出缓冲区中的命令回复发送给客户端
清空输出缓冲区:命令回复发送完毕后,会清空输出缓冲区,为处理下一个命令请求做好准备。
客户端接收并打印命令回复
转为人类可读的格式:由于命令回复也是 Redis 协议格式的,所以客户端需要将回复转为人类可读的格式,然后打印出来。
serverCron 函数
意义:Redis服务器中的serverCron函数默认每隔100毫秒执行一次,这个函数负责管理服务器的资源,并保持服务器自身的良好运转。
操作
更新服务器的时间缓存
Redis 服务器中不少功能是要使用系统的当前时间的,而获取系统当前时间需要执行一次系统调用。
为了减少系统调用,提升性能,服务器状态(redisServer)中的 unixtime 属性和 mstime 属性分别保存了秒级精度的系统当前 UNIX 时间戳和毫秒级精度的系统当前 UNIX 时间戳。
serverCron 函数会每隔 100 毫秒更新一次这两个属性。
ps:这两个时间只会用在对时间精确度要求不高的功能上,例如打印日志、计算服务器上线时间等等。像设置键过期时间、添加慢查询日志这种需要时间精确度高的功能上,服务器还是会每次都调用系统来获取。
更新 LRU 时钟
服务器状态中的lruclock属性保存了服务器的LRU时钟;而每个 Redis 对象都会有一个 lru 属性,这个属性记录了对象最后一次被命令访问的时间。
当服务器要计算一个数据库键的空转时间(也即是数据库键对应的值对象的空转时间),程序会用服务器的lruclock属性记录的时间减去对象的lru属性记录的时间,得出的计算结果就是这个对象的空转时间
serverCron函数默认会以每10秒一次的频率更新lruclock属性的值
因为这个时钟不是实时的,所以根据这个属性计算出来的LRU时间实际上只是一个模糊的估算值。
更新服务器每秒执行命令次数
更新服务器内存峰值记录
处理 SIGTERM 信号
在启动服务器时,Redis会为服务器进程的SIGTERM信号关联处理器sigtermHandler函数,这个信号处理器负责在服务器接到SIGTERM信号时,打开服务器状态的shutdown_asap标识
每次serverCron函数运行时,程序都会对服务器状态的shutdown_asap属性进行检查,并根据属性的值决定是否关闭服务器
1:关闭服务器;0:不做动作
管理客户端资源
释放长时间与服务器没有互动的客户端
控制客户端的输入缓冲区大小
管理数据库资源
例如删除过期键
执行被延迟的 BGREWRITEAOF
当执行 BGSAVE 时,BGREWRITEAOF 操作会被延迟执行
检查持久化操作的运行状态
服务器状态使用rdb_child_pid属性和aof_child_pid属性记录执行BGSAVE命令和BGREWRITEAOF命令的子进程的ID,这两个属性也可以用于检查BGSAVE命令或者BGREWRITEAOF命令是否正在执行
如果其中一个值不为 -1,则检查子进程是否有信号发到服务器进程中
如果有信号到达,那么表示新的RDB文件已经生成完毕(对于BGSAVE命令来说),或者AOF文件已经重写完毕(对于BGREWRITEAOF命令来说),服务器需要进行相应命令的后续操作,比如用新的RDB文件替换现有的RDB文件,或者用重写后的AOF文件替换现有的AOF文件。
如果没有信号到达,那么表示持久化操作未完成,程序不做动作。
两个值都为 -1
检查是否有被延迟的 BGREWRITEAOF
检查是否可以做 BGSAVE 操作
检查是否可以做 AOF 重写操作
将 AOF 缓冲区中的内容写入 AOF 文件
关闭异步客户端
增加cronloops计数器的值:服务器状态的cronloops属性记录了serverCron函数执行的次数
初始化服务器
初始化服务器状态结构
创建一个struct redisServer类型的实例变量server作为服务器的状态,并为结构中的各个属性设置默认值。
初始化server变量的工作由redis.c/initServerConfig函数完成
设置服务器的运行ID。
设置服务器的默认运行频率。
设置服务器的默认配置文件路径。
设置服务器的运行架构。
设置服务器的默认端口号。
设置服务器的默认RDB持久化条件和AOF持久化条件。
初始化服务器的LRU时钟。
创建命令表。
initServerConfig函数设置的服务器状态属性基本都是一些整数、浮点数、或者字符串属性,除了命令表之外,initServerConfig函数没有创建服务器状态的其他数据结构,数据库、慢查询日志、Lua环境、共享对象这些数据结构在之后的步骤才会被创建出来。
载入服务器配置
在启动服务器时,用户可以通过给定配置参数或者指定配置文件来修改服务器的默认配置。
用户配置:redis-server --port 10086,那么 Redis 服务的端口号将被修改
指定配置文件:redis-server redis.conf,那么将读取配置文件中的配置,然后修改对应的服务器配置
初始化服务器数据结构(initServer 函数)
server.clients链表,这个链表记录了所有与服务器相连的客户端的状态结构,链表的每个节点都包含了一个redisClient结构实例。
server.db数组,数组中包含了服务器的所有数据库。
用于保存频道订阅信息的server.pubsub_channels字典,以及用于保存模式订阅信息的server.pubsub_patterns链表。
用于执行Lua脚本的Lua环境server.lua。
用于保存慢查询日志的server.slowlog属性。
思考:为啥此时才初始化这些数据结构?这是因为服务器必须先载入用户指定的配置选项,才能正确地对数据结构进行初始化。
除了上面的数据结构初始化,还会做下面一下非常重要的设置操作
为服务器设置进程信号处理器。
创建共享对象:这些对象包含Redis服务器经常用到的一些值,比如包含\"OK\"回复的字符串对象,包含\"ERR\"回复的字符串对象,包含整数1到10000的字符串对象等等,服务器通过重用这些共享对象来避免反复创建相同的对象。
打开服务器的监听端口,并为监听套接字关联连接应答事件处理器,等待服务器正式运行时接受客户端的连接。
为serverCron函数创建时间事件,等待服务器正式运行时执行serverCron函数。
如果AOF持久化功能已经打开,那么打开现有的AOF文件,如果AOF文件不存在,那么创建并打开一个新的AOF文件,为AOF写入做好准备。
初始化服务器的后台I/O模块(bio),为将来的I/O操作做好准备。
还原数据库状态
在完成了对服务器状态server变量的初始化之后,服务器需要载入RDB文件或者AOF文件,并根据文件记录的内容来还原服务器的数据库状态。
执行事件循环
多机数据库的实现
复制
Redis 2.8以前的复制功能不能高效地处理断线后重复制情况,但Redis 2.8新添加的部分重同步功能可以解决这个问题。
部分重同步通过复制偏移量、复制积压缓冲区、服务器运行ID三个部分来实现。
在复制操作刚开始的时候,从服务器会成为主服务器的客户端,并通过向主服务器发送命令请求来执行复制步骤,而在复制操作的后期,主从服务器会互相成为对方的客户端。
主服务器通过向从服务器传播命令来更新从服务器的状态,保持主从服务器一致,而从服务器则通过向主服务器发送命令来进行心跳检测,以及命令丢失检测。
旧版复制功能的实现
同步(sync)
同步操作用于将从服务器的数据库状态更新至主服务器当前所处的数据库状态。
步骤
从服务器向主服务器发送 SYNC 命令
主服务器收到 SYNC 命令后,后台生成一个 RDB 文件(BGSAVE),并使用一个缓冲区记录从现在开始执行的所有写命令。
当主服务器的 BGSAVE 命令执行完毕,将生成的 RDB 文件发送给从服务器;从服务器接收并载入这个 RDB 文件。
主服务器将缓冲区里的所有写命令发送给从服务器;从服务器执行这些写命令。
至此,主从服务器两者的数据库将达到一致状态。
命令传播(command propagate)
命令传播操作则用于在主服务器的数据库状态被修改,导致主从服务器的数据库状态出现不一致时,让主从服务器的数据库重新回到一致状态。
缺陷
假设主从服务去断开连接,当从服务器重新连接上后,又要重新执行一遍同步(sync)操作。
但是其实,从服务器重新连接时,数据库状态和主服务器大致是一样的,缺少的只是断开连接过程中,主服务器接收到的写命令。
新版复制功能的实现(Redis2.8)
PSYNC
使用 PSYNC 命令代替 SYNC 命令来执行复制时的同步操作。
PSYNC命令具有完整重同步(full resynchronization)和部分重同步(partial resynchronization)两种模式
完整重同步:其中完整重同步用于处理初次复制情况:完整重同步的执行步骤和SYNC命令的执行步骤基本一样,它们都是通过让主服务器创建并发送RDB文件,以及向从服务器发送保存在缓冲区里面的写命令来进行同步。
部分重同步:而部分重同步则用于处理断线后重复制情况:当从服务器在断线后重新连接主服务器时,如果条件允许,主服务器可以将主从服务器连接断开期间执行的写命令发送给从服务器,从服务器只要接收并执行这些写命令,就可以将数据库更新至主服务器当前所处的状态。
PSYNC 的部分重同步的实现
构成部分
主服务器的复制偏移量(replication offset)和从服务器的复制偏移量。
主服务器的复制积压缓冲区(replication backlog)。
服务器的运行ID(run ID)。
复制偏移量:
主服务器和从服务器会分别维护自己的复制偏移量
主服务器每次向从服务器传播N个字节的数据时,就将自己的复制偏移量的值加上N。
从服务器每次收到主服务器传播来的N个字节的数据时,就将自己的复制偏移量的值加上N。
ps:只要我们对比主从服务器的复制偏移量,就知道主从服务器的数据库状态是否一致。
复制积压缓冲区:
复制积压缓冲区是由主服务器维护的一个固定长度(fixed-size)先进先出(FIFO)队列,默认大小为1MB。固定长度先进先出队列的长度是固定的,当入队元素的数量大于队列长度时,最先入队的元素会被弹出,而新元素会被放入队列。
主服务器的复制积压缓冲区里面会保存着一部分最近传播的写命令,并且复制积压缓冲区会为队列中的每个字节记录相应的复制偏移量。
当从服务器重新连上主服务器时,从服务器会通过PSYNC命令将自己的复制偏移量offset发送给主服务器,主服务器会根据这个复制偏移量来决定对从服务器执行何种同步操作。如果偏移量 offset+1 开始的数据仍然存在在复制积压缓冲区,则执行部分重同步操作,否则执行完整重同步操作。
ps:复制积压缓冲区的大小应该根据业务来设置。为了安全起见,可以将复制积压缓冲区的大小设为2*second(从服务器从断线到脸上的平均时间,单位为秒)*write_size_per_second(主服务器平均每秒产生的写命令数据量,协议格式的写命令的长度总和),这样可以保证绝大部分断线情况都能用部分重同步来处理。
服务运行ID
每个 Redis 服务器,不管是主还是从,都会有自己的运行ID;运行ID在服务器启动时自动生成,由40个随机的十六进制字符组成。
当从服务器对主服务器进行初次复制时,主服务器会将自己的运行ID传送给从服务器,而从服务器则会将这个运行ID保存起来。
当从服务器断线并重新连上一个主服务器时,从服务器将向当前连接的主服务器发送之前保存的运行ID。如果从服务器保存的运行ID和当前主服务器的运行ID相同,主服务器尝试执行部分重同步操作;否则,执行完整重同步操作。
PSYNC 调用细节
从服务器 PSYNC命令的调用方法有两种
如果从服务器以前没有复制过任何主服务器,或者之前执行过SLAVEOF no one命令,那么从服务器在开始一次新的复制时将向主服务器发送PSYNC ? -1命令,主动请求主服务器进行完整重同步(因为这时不可能执行部分重同步)。
相反地,如果从服务器已经复制过某个主服务器,那么从服务器在开始一次新的复制时将向主服务器发送PSYNC <runid> <offset>命令:其中runid是上一次复制的主服务器的运行ID,而offset则是从服务器当前的复制偏移量,接收到这个命令的主服务器会通过这两个参数来判断应该对从服务器执行哪种同步操作。
主服务器收到 PSYNC 命令的回复有三种
如果主服务器返回+FULLRESYNC <runid> <offset>回复,那么表示主服务器将与从服务器执行完整重同步操作:其中runid是这个主服务器的运行ID,从服务器会将这个ID保存起来,在下一次发送PSYNC命令时使用;而offset则是主服务器当前的复制偏移量,从服务器会将这个值作为自己的初始化偏移量。
如果主服务器返回+CONTINUE回复,那么表示主服务器将与从服务器执行部分重同步操作,从服务器只要等着主服务器将自己缺少的那部分数据发送过来就可以了。
如果主服务器返回-ERR回复,那么表示主服务器的版本低于Redis 2.8,它识别不了PSYNC命令,从服务器将向主服务器发送SYNC命令,并与主服务器执行完整同步操作。
复制的底层实现
步骤1:设置主服务器的地址和端口
客户端向从服务器发送命令:SLAVEOF <master_ip> <master_port>。
从服务器将命令中的主服务器信息(ip地址和端口号)保存在服务器状态中的 masterhost 属性和 masterport 属性。
ps:SLAVEOF命令是一个异步命令,在完成masterhost属性和masterport属性的设置工作之后,从服务器将向发送SLAVEOF命令的客户端返回OK,表示复制指令已经被接收,而实际的复制工作将在OK返回之后才真正开始执行。
步骤2:建立套接字连接
从服务器创建的套接字能成功连接(connect)主服务器后,为套接字关联一个专门用于处理复制工作的文件事件处理器,负责执行后续的负责工作。
主服务器在接受(accept)从服务器的套接字连接后,为该套接字创建对应的客户端状态(redisClient)。从服务器可以发送命令请求,主服务区也可以返回命令回复。
步骤3:发送 PING 命令
虽然主从服务器成功建立起了套接字连接,但双方并未使用该套接字进行过任何通信,通过发送PING命令可以检查套接字的读写状态是否正常。
因为复制工作接下来的几个步骤都必须在主服务器可以正常处理命令请求的状态下才能进行,通过发送PING命令可以检查主服务器能否正常处理命令请求。
发送 PING 命令后的三种情况
主服务器响应了,但是从服务器超时未接收到:如果主服务器向从服务器返回了一个命令回复,但从服务器却不能在规定的时限(timeout)内读取出命令回复的内容,那么表示主从服务器之间的网络连接状态不佳,不能继续执行复制工作的后续步骤。当出现这种情况时,从服务器断开并重新创建连向主服务器的套接字。
主服务器暂时无法处理从服务器的命令请求:如果主服务器向从服务器返回一个错误,那么表示主服务器暂时没办法处理从服务器的命令请求,不能继续执行复制工作的后续步骤。当出现这种情况时,从服务器断开并重新创建连向主服务器的套接字。比如说,如果主服务器正在处理一个超时运行的脚本,那么当从服务器向主服务器发送PING命令时,从服务器将收到主服务器返回的BUSY Redisis busy running a script.You can onlycall SCRIPT KILL or SHUTDOWN NOSAVE.错误。
主服务器响应成功,从服务器也接收成功:如果从服务器读取到\"PONG\"回复,那么表示主从服务器之间的网络连接状态正常,并且主服务器可以正常处理从服务器(客户端)发送的命令请求,在这种情况下,从服务器可以继续执行复制工作的下个步骤。
步骤4:身份验证
接收 PONG 响应后
如果从服务器设置了masterauth选项,那么进行身份验证。
如果从服务器没有设置masterauth选项,那么不进行身份验证。
从服务器在身份验证阶段可能遇到的情况有以下几种
如果主服务器没有设置requirepass选项,并且从服务器也没有设置masterauth选项,那么主服务器将继续执行从服务器发送的命令,复制工作可以继续进行。
如果从服务器通过AUTH命令发送的密码和主服务器requirepass选项所设置的密码相同,那么主服务器将继续执行从服务器发送的命令,复制工作可以继续进行。与此相反,如果主从服务器设置的密码不相同,那么主服务器将返回一个invalid password错误。
如果主服务器设置了requirepass选项,但从服务器却没有设置masterauth选项,那么主服务器将返回一个NOAUTH错误。另一方面,如果主服务器没有设置requirepass选项,但从服务器却设置了masterauth选项,那么主服务器将返回一个no password isset错误。
步骤5:发送端口信息
在身份验证步骤之后,从服务器将执行命令REPLCONF listening-port <port-number>,向主服务器发送从服务器的监听端口号。
主服务器在接收到这个命令之后,会将端口号记录在从服务器所对应的客户端状态的slave_listening_port属性中
步骤6:同步
完整重同步还是部分重同步
步骤7:命令传播
通过主服务器将自己执行的写命令发送给从服务器,保证主从服务器的数据库状态是一致的。
心跳检测
在命令传播阶段,从服务器默认会以每秒一次的频率,向主服务器发送命令:REPLCONF ACK <replication_offset>,其中 replication_offet 是从服务器当前的复制偏移量。
作用
检测主从服务器的网络连接状态
如果主服务器超过一秒钟没有收到从服务器发来的 REPLCONF ACK 命令,那么主服务器就知道主从服务器之间的连接出现问题了。
通过向主服务器发送 INFO replication 命令,在列出的从服务器列表的 lag 一栏中,我们可以看到相应从服务器最后一次向主服务器发送 REPLCONFACK 命令距离现在过了多少秒。ps:在一般情况下,lag的值应该在0秒或者1秒之间跳动,如果超过1秒的话,那么说明主从服务器之间的连接出现了故障。
辅助实现min-slaves选项
Redis的 min-slaves-to-write 和 min-slaves-max-lag 两个选项可以防止主服务器在不安全的情况下执行写命令。
min-slaves-to-write 3min-slaves-max-lag 10
在从服务器的数量少于3个,或者三个从服务器的延迟(lag)值都大于或等于10秒时,主服务器将拒绝执行写命令,这里的延迟值就是上面提到的INFO replication命令的lag值。
检测命令丢失
主服务器根据从服务器的 REPLCONF ACK 中的 replication_offset 来判断从服务器的命令是否丢失,如果丢失了,则从复制积压缓冲区中找到从服务区缺少的数据,并将数据重新发送给从服务器。
ps:这里的补发缺失数据的原理和部分重同步操作的原理非常相似。这两个操作的区别在于,补发缺失数据操作在主从服务器没有断线的情况下执行,而部分重同步操作则在主从服务器断线并重连之后执行。
REPLCONF ACK 命令和复制积压缓冲区都是 Redis 2.8版本新增的;Redis 2.8版本以前,主服务器不会理会从服务器是否出现命令丢失。
Sentinel
Sentinel只是一个运行在特殊模式下的Redis服务器,它使用了和普通模式不同的命令表,所以Sentinel模式能够使用的命令和普通Redis服务器能够使用的命令不同。
Sentinel会读入用户指定的配置文件,为每个要被监视的主服务器创建相应的实例结构,并创建连向主服务器的命令连接和订阅连接,其中命令连接用于向主服务器发送命令请求,而订阅连接则用于接收指定频道的消息。
Sentinel通过向主服务器发送INFO命令来获得主服务器属下所有从服务器的地址信息,并为这些从服务器创建相应的实例结构,以及连向这些从服务器的命令连接和订阅连接。
在一般情况下,Sentinel以每十秒一次的频率向被监视的主服务器和从服务器发送INFO命令,当主服务器处于下线状态,或者Sentinel正在对主服务器进行故障转移操作时,Sentinel向从服务器发送INFO命令的频率会改为每秒一次。
对于监视同一个主服务器和从服务器的多个Sentinel来说,它们会以每两秒一次的频率,通过向被监视服务器的__sentinel__:hello频道发送消息来向其他Sentinel宣告自己的存在。
每个Sentinel也会从__sentinel__:hello频道中接收其他Sentinel发来的信息,并根据这些信息为其他Sentinel创建相应的实例结构,以及命令连接。
Sentinel只会与主服务器和从服务器创建命令连接和订阅连接,Sentinel与Sentinel之间则只创建命令连接。
Sentinel以每秒一次的频率向实例(包括主服务器、从服务器、其他Sentinel)发送PING命令,并根据实例对PING命令的回复来判断实例是否在线,当一个实例在指定的时长中连续向Sentinel发送无效回复时,Sentinel会将这个实例判断为主观下线。
当Sentinel将一个主服务器判断为主观下线时,它会向同样监视这个主服务器的其他Sentinel进行询问,看它们是否同意这个主服务器已经进入主观下线状态。
当Sentinel收集到足够多的主观下线投票之后,它会将主服务器判断为客观下线,并发起一次针对主服务器的故障转移操作。
启动并初始化 Sentinel
命令
redis-sentinel /path/to/your/sentinel.conf
redis-server /path/to/your/sentinel.conf --sentinel
初始化服务器:和初始化一个普通的 Redis 服务器类似,不过不完全相同,例如 Sentinel 不需要使用数据库,所以就不会载入 RDB 文件或者 AOF 文件。不使用数据库命令、不使用事务命令、不使用脚本命令等等。
使用 Sentinel 专用代码:例如使用 sentinel.c/REDIS_SENTINEL_PORT作为服务端口,使用 sentinel.c/sentinelcmds 作为服务器的命令表。ps:PING、SENTINEL、INFO、SUBSCRIBE、UNSUBSCRIBE、PSUBSCRIBE和PUNSUBSCRIBE这七个命令就是客户端可以对Sentinel执行的全部命令了
初始化 Sentinel 状态:初始化 sentinel.c/sentinelState 结构,成为 Sentinel 状态;这个结构保存了 Sentinel 服务器中所有和 Sentinel 功能有关的状态。
初始化 Sentinel 状态的 masters 属性:该属性的结构是字典,字典的键是被监视主服务器的名字,值是被监视主服务器对应的 sentinel.c/sentinelRedisInstance 结构。ps:每个sentinelRedisInstance结构(后面简称“实例结构”)代表一个被Sentinel监视的Redis服务器实例(instance),这个实例可以是主服务器、从服务器,或者另外一个Sentinel。ps:sentinelRedisInstance.addr属性是一个指向sentinel.c/sentinelAddr结构的指针,这个结构保存着实例的IP地址和端口号。
创建连向主服务器的网络连接:创建两个异步网络连接,一个是命令连接,这个连接专门用于向主服务器发送命令,并接收命令回复;另一个是订阅连接,这个连接专门用于订阅主服务器的__sentinel__:hello频道。
获取主服务器信息
Sentinel默认会以每十秒一次的频率,通过命令连接向被监视的主服务器发送INFO命令,并通过分析INFO命令的回复来获取主服务器的当前信息。
通过 INFO 命令,Sentinel 可以获取两方面的信息
主服务本身的信息,包括运行ID(run_id)和服务器角色(role)
所有从服务器的基本信息,然后更新主服务器实例结构的 slaves 字典。
字典的键是由 Sentinel 自动设置的从服务器名字,格式为ip:port:如对于IP地址为127.0.0.1,端口号为11111的从服务器来说,Sentinel为它设置的名字就是127.0.0.1:11111。
字典的值则是从服务器对应的实例结构(也是 sentinelRedisInstance 结构):比如说,如果键是127.0.0.1:11111,那么这个键的值就是IP地址为127.0.0.1,端口号为11111,名称为\"127.0.0.1:11111\" 的从服务器的实例结构。
此时主服务器的实例结构
获取从服务器信息
通过上面获取到从服务器的基本信息后,Sentinel 会创建连接到从服务器的命令连接和订阅连接。
之后也是默认以每十秒一次的频率,通过命令连接向从服务器发送 INFO 命令。
通过 INFO 命令,Sentinel 获取从服务器的详细信息
从服务器的运行ID run_id
从服务器的角色role
主服务器的IP地址master_host,以及主服务器的端口号master_port
主从服务器的连接状态master_link_status
从服务器的优先级slave_priority
从服务器的复制偏移量slave_repl_offset
根据上面的信息,Sentinel 会对从服务器的实例结构进行更新。
向主服务器和从服务器发送信息
在默认情况下,Sentinel会以每两秒一次的频率,通过命令连接向所有被监视的主服务器和从服务器发送以下格式的命令PUBLISH __sentinel__:hello \
接收来自主服务器和从服务器的频道消息
当Sentinel与一个主服务器或者从服务器建立起订阅连接之后,Sentinel就会通过订阅连接,向服务器发送以下命令:SUBSCRIBE __sentinel__:hello
Sentinel对__sentinel__:hello频道的订阅会一直持续到Sentinel与服务器的连接断开为止。
这也就是说,对于每个与Sentinel连接的服务器,Sentinel既通过命令连接向服务器的__sentinel__:hello频道发送信息(PUBLISH),又通过订阅连接从服务器的__sentinel__:hello频道接收信息(SUBSCRIBE)。
对于监视同一个服务器的多个Sentinel来说,一个Sentinel发送的信息会被其他Sentinel接收到,这些信息会被用于更新其他Sentinel对发送信息Sentinel的认知,也会被用于更新其他Sentinel对被监视服务器的认知。ps:对于一个 Sentinel 发送消息会被其他 Sentinel 接收到,是因为 主服务器会重新将这个消息发到 __sentinel__:hello 频道中。
当 Sentinel 接收到 __sentinel__:hello 频道中的消息,会提取其中的参数,然后进行下面的检查
如果信息中记录的Sentinel运行ID和接收信息的Sentinel的运行ID相同,那么说明这条信息是Sentinel自己发送的,Sentinel将丢弃这条信息,不做进一步处理。
相反地,如果信息中记录的Sentinel运行ID和接收信息的Sentinel的运行ID不相同,那么说明这条信息是监视同一个服务器的其他Sentinel发来的,接收信息的Sentinel将根据信息中的各个参数,对相应主服务器的实例结构进行更新(更新 sentinels 字典)。
更新 sentinels 字典
字典的结构
键是格式为“ip:port”格式的 Sentinel 名字
键是对应的 Sentinel 实例结构(包括IP属性和PORT属性)
__sentinel__:hello 频道的消息主要分为两个,一个是源Sentinel(发送信息的 Sentinel)信息,一个是源Sentinel正在监听的主服务器的信息。
目标 Sentinel (接收信息的 sentinel 们)接收到信息后,会提取上面的两个信息,然后做下面的操作。
目标Sentinel会在自己的Sentinel状态的masters字典中查找相应的主服务器实例结构,然后根据提取出的Sentinel参数(sentinels 字典),检查主服务器实例结构的sentinels字典中,源Sentinel的实例结构是否存在
如果源Sentinel的实例结构已经存在,那么对源Sentinel的实例结构进行更新。
如果源Sentinel的实例结构不存在,那么说明源Sentinel是刚刚开始监视主服务器的新Sentinel,目标Sentinel会为源Sentinel创建一个新的实例结构,并将这个结构添加到sentinels字典里面。
因为一个Sentinel可以通过分析接收到的频道信息来获知其他Sentinel的存在,并通过发送频道信息来让其他Sentinel知道自己的存在,所以用户在使用Sentinel的时候并不需要提供各个Sentinel的地址信息,监视同一个主服务器的多个Sentinel可以自动发现对方。
创建连向其他 Sentinel 的命令连接
当 Sentinel 通过 __sentinel__:hello 频道接收到消息时,不但会做上面的操作(更新 sentinels 字典),还会创建一个连向新 Sentinel 的命令连接。最后监视同一主服务器的多个 Sentinel 会形成互相连接的网络。
Sentinel 之间的命令连接主要用来实现主服务器的主观下线检测和客观下线检测。
为什么 Sentinel 之间需要建立订阅连接?
Sentinel 与主从服务器建立订阅连接是因为 Sentinel 需要接收主服务器或者从服务器发来的频道信息来发现未知的新 Sentinel。
而 Sentinel 只需要命令连接来进行通信就足够了。
检测主观下线状态
在默认情况下,Sentinel会以每秒一次的频率向所有与它创建了命令连接的实例(包括主服务器、从服务器、其他Sentinel在内)发送PING命令,并通过实例返回的PING命令回复来判断实例是否在线。
实例对 PING 命令回复的两种情况
有效回复:实例返回+PONG、-LOADING、-MASTERDOWN三种回复的其中一种。
无效回复:实例返回除+PONG、-LOADING、-MASTERDOWN三种回复之外的其他回复,或者在指定时限内没有返回任何回复。
Sentinel 配置文件中的 down-after-milliseconds 判断实例是否进入主观下线。如果实例在 down-after-milliseconds 毫秒内连续向 Sentinel 返回无效回复,Sentinel 会修改该实例对应的实例结构,在结构的 flags 属性中打开 SRI_S_DOWN 标识。
用户设置的down-after-milliseconds选项的值,不仅会被Sentinel用来判断主服务器的主观下线状态,还会被用于判断主服务器属下的所有从服务器,以及所有同样监视这个主服务器的其他 Sentinel 的主观下线状态。
ps:对于监视同一个主服务器的多个 Sentinel 来说,所设置的 down-after-milliseconds 选项的值也可能不同。因此,当一个 Sentinel 将主服务器判断为主观下线时,其他 Sentinel 可能仍然会认为主服务器处于在线状态。
检查客观下线状态
当 Sentinel 从其他 Sentinel 接收到足够数量的主服务器主观下线判断后,Sentinel 就会将主服务器判定为客观下线,然后执行故障转移操作。
发送 is-master-down-by-add 命令
Sentinel 会发送此命令询问其他 Sentinel 是否同意主服务器已下线。
SENTINEL is-master-down-by-add <ip> <port> <current_epoch> <runid>
ip:被 Sentinel 判断为主观下线的主服务器的 IP 地址
port:被 Sentinel 判断为主观下线的主服务器的端口号
current_epoch:Sentinel 当前的配置纪元,用于选举领头 Sentinel
runid:可以是 * 符号或者是 Sentinel 的运行ID。* 符号代表命令仅仅用于检测主服务器的客观下线状态,而 Sentinel 的运行 ID 用于选举领头 Sentinel。
接收 is-master-down-by-add 命令
当目标 Sentinel 接收到 源 Sentinel发来的 SENTINEL is-master-down-by-add 命令时,会分析并取出命令请求中的参数,然后根据其中主服务器的 IP 和端口号,检查主服务器是否已下线。
然后返回一条包含三个参数的 MultiBulk 回复
1) <down_state>:返回目标 Sentinel 对主服务器的下线检查结果,1 代表已下线,0 代表未下线。
2) <leader_runid>:可以是 * 符号或者目标 Sentinel 的局部领头 Sentinel 的运行 ID。* 符号代表命令仅仅用于检测主服务器的下线状态,而局部领头 Sentinel 的运行 ID 用于选举领头 Sentinel。
3) <leader_epoch>:目标 Sentinel 的局部领头 Sentinel 的配置纪元。用于选举领头 Sentinel。仅在 leader_runid 不为 * 时有效,如果 leader_runid 为 *,那么 leader_epoch 总为0。
接收 SENTINEL is-master-down-by-add 命令的回复
源 Sentinel 会接收目标 Sentinel 同意主服务器已下线的数量,当数量达到配置指定的判断客观下线所需要的数量时,Sentinel 会将主服务器实例结构 flags 属性的 SRI_O_DOWN 标识打开,表示主服务器已进入客观下线状态。
当认为主服务器已经进入下线状态的 Sentinel 的数量,超过 Sentinel 配置中设置的 quorum 参数的值,那么该 Sentinel 就会认为主服务器已经进入客观下线状态。quarum 在启动时就载入了:sentinel monitor master 127.0.0.1 6379 2(2就是 quorum 值)
ps:对于监视同一个主服务器的多个Sentinel来说,它们将主服务器标判断为客观下线的条件可能也不同。
选举领头 Sentinel
当一个主服务器被判断为客观下线时,监视这个下线主服务器的各个Sentinel会进行协商,选举出一个领头Sentinel,并由领头Sentinel对下线主服务器执行故障转移操作。
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设置成了局部领头Sentinel,那么这个Sentinel成为领头Sentinel。举个例子,在一个由10个Sentinel组成的Sentinel系统里面,只要有大于等于10/2+1=6个Sentinel将某个Sentinel设置为局部领头Sentinel,那么被设置的那个Sentinel就会成为领头Sentinel。
因为领头Sentinel的产生需要半数以上Sentinel的支持,并且每个Sentinel在每个配置纪元里面只能设置一次局部领头Sentinel,所以在一个配置纪元里面,只会出现一个领头Sentinel。
如果在给定时限内,没有一个Sentinel被选举为领头Sentinel,那么各个Sentinel将在一段时间之后再次进行选举,直到选出领头Sentinel为止。
故障转移
选出新的主服务器
在已下线主服务器属下的所有从服务器中,挑选出一个状态良好、数据完整的从服务器,然后向这个从服务器发送 SLAVEOF no one 命令,将这个从服务器转换为主服务器。
如何挑选
领头Sentinel会将已下线主服务器的所有从服务器保存到一个列表里面,然后按照以下规则,一项一项地对列表进行过滤
删除列表中所有处于下线或者断线状态的从服务器,这可以保证列表中剩余的从服务器都是正常在线的。
删除列表中所有最近五秒内没有回复过领头Sentinel的INFO命令的从服务器,这可以保证列表中剩余的从服务器都是最近成功进行过通信的。
删除所有与已下线主服务器连接断开超过down-after-milliseconds*10毫秒的从服务器:down-after-milliseconds选项指定了判断主服务器下线所需的时间,而删除断开时长超过down-after-milliseconds*10毫秒的从服务器,则可以保证列表中剩余的从服务器都没有过早地与主服务器断开连接,换句话说,列表中剩余的从服务器保存的数据都是比较新的。
之后,领头Sentinel将根据从服务器的优先级,对列表中剩余的从服务器进行排序,并选出其中优先级最高的从服务器。
如果有多个具有相同最高优先级的从服务器,那么领头Sentinel将按照从服务器的复制偏移量,对具有相同最高优先级的所有从服务器进行排序,并选出其中偏移量最大的从服务器(复制偏移量最大的从服务器就是保存着最新数据的从服务器)。
最后,如果有多个优先级最高、复制偏移量最大的从服务器,那么领头Sentinel将按照运行ID对这些从服务器进行排序,并选出其中运行ID最小的从服务器。
自己总结:
1、去掉处于下线或断线状态的从服务器
2、去掉最近五秒内没回复过领头 Sentinel 的 INFO 命令的从服务器
3、删除于已下线主服务器连接断开超过 down-after-milliseconds * 10 毫秒的从服务器
4、选择优先级最高的从服务器
5、优先级相等,则选择复制偏移量最大的从服务器
6、优先级和复制偏移量都相等,则选择运行 ID 最小的从服务器
在发送SLAVEOF no one命令之后,领头Sentinel会以每秒一次的频率(平时是每十秒一次),向被升级的从服务器发送INFO命令,并观察命令回复中的角色(role)信息,当被升级服务器的role从原来的slave变为master时,领头Sentinel就知道被选中的从服务器已经顺利升级为主服务器了。
选举领头 Sentinel 是算法是 Raft 算法:https://www.cnblogs.com/xybaby/p/10124083.html
修改从服务器的复制目标
当新的主服务器出现之后,领头Sentinel下一步要做的就是,让已下线主服务器属下的所有从服务器去复制新的主服务器,这一动作可以通过向从服务器发送SLAVEOF命令来实现。
将旧的主服务器变为从服务器
将已下线的主服务器设置为新的主服务器的从服务器;这种设置是保存在已下线主服务器对应的实例结构中,当已下线主服务器重新上线时,Sentinel 就会向它发送 SLAVEOF 命令,让它成功新的主服务器的从服务器。
集群
节点通过握手来将其他节点添加到自己所处的集群当中。
集群中的16384个槽可以分别指派给集群中的各个节点,每个节点都会记录哪些槽指派给了自己,而哪些槽又被指派给了其他节点。
节点在接到一个命令请求时,会先检查这个命令请求要处理的键所在的槽是否由自己负责,如果不是的话,节点将向客户端返回一个MOVED错误,MOVED错误携带的信息可以指引客户端转向至正在负责相关槽的节点。
对Redis集群的重新分片工作是由redis-trib负责执行的,重新分片的关键是将属于某个槽的所有键值对从一个节点转移至另一个节点。
如果节点A正在迁移槽i至节点B,那么当节点A没能在自己的数据库中找到命令指定的数据库键时,节点A会向客户端返回一个ASK错误,指引客户端到节点B继续查找指定的数据库键。
MOVED错误表示槽的负责权已经从一个节点转移到了另一个节点,而ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施。
集群里的从节点用于复制主节点,并在主节点下线时,代替主节点继续处理命令请求。
集群中的节点通过发送和接收消息来进行通信,常见的消息包括MEET、PING、PONG、PUBLISH、FAIL五种。
节点
刚开始的时候,每个节点(Redis 服务器)都是互相独立的,它们都处于一个只包含自己的集群当中(开启了集群模式)。
连接各个节点的工作可以使用 CLUSTER MEET 命令来完成。命令格式:CLUSTER MEET <ip> <port>。
例子
客户端连接 7000 节点:redis-cli -c -p 7000。-c 表示集群模式
向 7000 节点发送 CLUSTER MEET 命令:CLUSTER MEET 127.0.0.1 7001。将 7001 节点加入到节点 7000 的集群中。
向一个节点 node 发送 CLUSTER MEET 命令,可以让 node 节点与 ip 和 port 所指定的节点进行握手(handshake),当握手成功时,node 节点就会将 ip 和 port 所指定的节点添加到 node 节点当前所在的集群中。
可以使用 CLUSTER NODE 命令 查看当前节点的集群状态。
启动节点
Redis 服务器在启动时,会根据 cluster-enabled 配置选项来决定是否开启服务器的集群模式
Redis 服务器在集群模式下,还是会使用单机模式中使用的服务器组件
使用文件事件处理器处理命令请求和返回回复。
使用时间处理器执行 serverCron 函数,serverCron 函数会调用集群模式下特有的 clusterCron 函数。clusterCron 函数主要负责发送 Gossip 消息,检查节点是否断线等等。
使用数据库保存键值对数据。
使用 RDB 和 AOF 持久化。
使用发布订阅模块执行 PUBLISH 和 SUBSCRIBE。
使用复制模块进行节点的复制工作。
使用 Lua 脚本环境来执行 Lua 脚本。
集群数据结构
clusterNode:保存了一个节点的当前状态每个节点里面,还会为集群中其他节点(包括主节点和从节点)的创建对应的 clusterNode 结构。
clusterLink:对应 clusterNode 的 link 属性,保存了连接节点所需要的信息比如套接字描述符,输入缓冲区和输出缓冲区。
clusterState:在当前节点的视角下,保存了集群目前所处的状态当然了,集群中每个节点都会有 clusterState 结构。
CLUSTER MEET 命令的实现
客户端向节点A发送 CLUSTER MEET 命令,节点A将会与命令中参数对应的节点B进行握手。
1)节点A会为节点B创建一个clusterNode结构,并将该结构添加到自己的clusterState.nodes字典里面。
2)之后,节点A将根据CLUSTER MEET命令给定的IP地址和端口号,向节点B发送一条MEET消息(message)。
3)如果一切顺利,节点B将接收到节点A发送的MEET消息,节点B会为节点A创建一个clusterNode结构,并将该结构添加到自己的clusterState.nodes字典里面。
4)之后,节点B将向节点A返回一条PONG消息。
5)如果一切顺利,节点A将接收到节点B返回的PONG消息,通过这条PONG消息节点A可以知道节点B已经成功地接收到了自己发送的MEET消息。
6)之后,节点A将向节点B返回一条PING消息。
7)如果一切顺利,节点B将接收到节点A返回的PING消息,通过这条PING消息节点B可以知道节点A已经成功地接收到了自己返回的PONG消息,握手完成。
重点:之后,节点A会将节点B的信息通过Gossip协议传播给集群中的其他节点,让其他节点也与节点B进行握手,最终,经过一段时间之后,节点B会被集群中的所有节点认识。
槽指派
Redis集群通过分片的方式来保存数据库中的键值对
集群的整个数据库被分为16384个槽(slot),数据库中的每个键都属于这16384个槽的其中一个,集群中的每个节点可以处理0个或最多16384个槽。
当数据库中的16384个槽都有节点在处理时,集群处于上线状态(ok);相反地,如果数据库中有任何一个槽没有得到处理,那么集群处于下线状态(fail)。
通过 CLUSTER MEET 命令将多节点连接到同一个集群里,此时集群是处于下线状态的,因为集群中的节点都没有在处理任何槽。
我们可以通过向节点发送 CLUSTER ADDSLOTS 命令,将一个或多个槽指派(assign)给某个节点负责。命令格式:CLUSTER ADDSLOTS <slot>[slot1 slot2 ...]
记录节点的槽指派信息
clusterNode 结构的 slots 属性和 numslot 属性分别记录了节点负责处理哪些槽和槽的数量。
unsigned char slots[16384/8]
一个二进制位数组(bit array),这个数组的长度为16384/8=2048个字节,共包含16384个二进制位。
Redis 以0位起始索引,以18363位终止索引,对应 slots 数组中的 16384 个二进制位进行编号。
如果slots数组在索引 i 上的二进制位的值为1,那么表示节点负责处理槽 i。如果slots数组在索引 i 上的二进制位的值为0,那么表示节点不负责处理槽 i。
int numslots
记录节点负责处理的槽的数量,也即是slots数组中值为1的二进制位的数量。
传播节点的槽指派信息
节点处理利用 clusterNode 结构记录自己处理的槽外,还会将clusterNode 的 slots 数组通过消息发送给集群中的其他节点,让大家都知道~
当节点收到其他节点发送过来的 slots 数组时,会在 clusterState.nodes 字典中查找其他节点对应的 clusterNode 结构,然后对结构中的 slots 数组进行保存或更新。
重点:每当节点更新了自己负责处理的槽,就会给集群中的其他所有节点发送 UPDATE 消息(clusterMsgDataUpdate结构),里面包含节点的节点的槽布局 (unsigned char slots[REDIS_CLUSTER_SLOTS/8];),所以最后集群中每个节点都保存着集群16384个槽的指派信息。
记录集群中所有槽的指派信息
clusterState 结构中的 slots 数组记录了集群中所有 16384 个槽的指派信息
clusterNode *slots[16384]
每个数组项都是一个指向clusterNode结构的指针
如果 slots[i] 指针指向 NULL,那么表示槽i尚未指派给任何节点。
如果 slots[i] 指针指向一个clusterNode结构,那么表示槽i已经指派给了 clusterNode 结构所代表的节点。
重点
clusterState.slots 数组记录了集群中所有槽的指派信息,而 clusterNode.slots 数组只记录了 clusterNode 结构所代表的节点的槽指派信息,这是两个 slots 数组的关键区别所在。
为何要这两个 slots 数组?
使用 clusterState.slots 是为了方便判断槽是否被指派了,或者判断键所对应的槽被哪个节点负责,此时的复杂度是 0(1);而如果使用 clusterNode.slots 来判断,那么我们需要遍历整个 clusterState.nodes 字典,此时复杂度是 O(N),N为 nodes 字典中 clusterNode 的数量。
使用 clusterNode.slots 是为了方便将某个节点的槽指派信息发送给集群中的其他节点,此时只需要将 clusterNode.slots 整个发送出去就可以了;而如果使用 clusterState.slots,则需要遍历整个 clusterState.slots 数组。
CLUSTER ADDSLOTS 命令的实现
CLUSTER ADDSLOTS命令接受一个或多个槽作为参数,并将所有输入的槽指派给接收该命令的节点负责
伪代码:我们可以看到他是遍历了两次输入槽,一次是判断输入槽是否有已经被指派的,只要有一个就直接向客户端返回错误;第二次遍历输入槽是给这些槽指派给当前节点。
在集群中执行命令
当数据库中 16384 个槽全部进行了指派之后,集群就会进入上线状态,此时客户端就可以向集群中的节点发送数据命令了。
下面将介绍执行命令的两个步骤。
1、计算键属于哪个槽
节点接收命令后,会先计算出命令要处理的数据库键属于哪个槽
计算算法:CRC16(key) & 16383
CRC16(key)语句用于计算键key的CRC-16校验和
&16383语句则用于计算出一个介于0至16383之间的整数作为键key的槽号
我们可以利用 CLUSTER KEYSLOT <key> 命令来查看一个给定键属于哪个槽。当然了,这个命令也是利用上面的算法实现的。
2、判断槽是否由当前节点负责处理
如果 clusterState.slots[i] 等于 clusterState.myself ,那么说明槽i由当前节点负责,节点可以执行客户端发送的命令
如果 clusterState.slots[i] 不等于 clusterState.myself ,那么说明槽 i 并非由当前节点负责,节点会根据 clusterState.slots[i] 指向的 clusterNode 结构所记录的节点 IP 和端口号,向客户端返回 MOVED 错误,指引客户端转向至正在处理槽 i 的节点。
MOVED 错误
当节点发现键所在的槽不是自己负责处理时,节点就会向客户端返回一个 MOVED 错误,指引客户端转向负责此槽的节点。
MOVED 错误的格式:MOVED <slot> <ip>:<port>
其中 slot 为键所在的槽,而 ip 和 port 则是负责处理槽 slot 的节点的 IP 地址和端口号。
ps:被隐藏的 MOVED 错误:集群模式下的 redis-cli 客户端收到 MOVED 错误时,会根据 MOVED 错误自动转向正确的节点,然后打印转向信息。而如果是单机模式的 redis-cli 客户端,接收到 MOVED 错误时会直接打印出来,而不会帮忙转向。
节点数据库的实现
首先,集群节点保存键值对以及键值对过期时间的方式和单机模式的 Redis 服务器方式完全相同。
但是,集群节点只能使用 0 号数据库,而单机 Redis 服务器没有这一限制,用户可自定义有多少个数据库。
还有的就是,集群节点处理将键值对保存在 0 号数据库,还会在 clusterState 结构中的 slots_to_keys 跳跃表来保存槽和键之间的关系。
clusterState.slots_to_keys 的作用:由于这里记录了所有数据库键所属的槽,所以节点可以很方便地对某个或者某些槽的所有数据库键进行批量操作。
重新分片
Redis集群的重新分片操作可以将任意数量已经指派给某个节点(源节点)的槽改为指派给另一个节点(目标节点),并且相关槽所属的键值对也会从源节点被移动到目标节点。
重新分片操作可以在线(online)进行,在重新分片的过程中,集群不需要下线,并且源节点和目标节点都可以继续处理命令请求。
实现原理
Redis 集群的重新分片操作是由Redis的集群管理软件 redis-trib 负责执行的,Redis 提供了进行重新分片所需的所有命令,而 redis-trib 则通过向源节点和目标节点发送命令来进行重新分片操作。
单个槽重分片步骤
1)redis-trib 对目标节点发送 CLUSTER SETSLOT<slot>IMPORTING<source_id>命令,让目标节点准备好从源节点导入(import)属于槽slot的键值对。
2)redis-trib 对源节点发送 CLUSTER SETSLOT<slot>MIGRATING<target_id> 命令,让源节点准备好将属于槽slot的键值对迁移(migrate)至目标节点。
3)redis-trib 向源节点发送 CLUSTER GETKEYSINSLOT<slot><count> 命令,获得最多count个属于槽slot的键值对的键名(key name)。
4)对于步骤3获得的每个键名,redis-trib 都向源节点发送一个 MIGRATE<target_ip><target_port><key_name>0<timeout> 命令,将被选中的键原子地从源节点迁移至目标节点。
5)重复执行步骤3和步骤4,直到源节点保存的所有属于槽slot的键值对都被迁移至目标节点为止。
6)redis-trib 向集群中的任意一个节点发送 CLUSTER SETSLOT<slot>NODE<target_id> 命令(Gossip 协议),将槽 slot 指派给目标节点,这一指派信息会通过消息发送至整个集群,最终集群中的所有节点都会知道槽 slot 已经指派给了目标节点。
ps:如果重新分片涉及多个槽,那么redis-trib将对每个给定的槽分别执行上面给出的步骤。
相关命令的实现
CLUSTER SETSLOT IMPORTING
clusterState 结构的 importing_slots_from 数组记录了当前节点正在从其他节点导入的槽。
如果 importing_slots_from[i] 的值不为NULL,而是指向一个 clusterNode 结构,那么表示当前节点正在从 clusterNode 所代表的节点导入槽 i。
在对集群进行重分片时,向目标节点发送命令:CLUSTER SETSLOT <i> IMPORTING <source_id>,可以将目标节点 clusterState.importing_slots_from[i] 的值设置为 source_id 所代表节点的 clusterNode 结构。
CLUSTER SETSLOT MIGRATING
clusterState结构的migrating_slots_to数组记录了当前节点正在迁移至其他节点的槽
如果 migrating_slots_to[i] 的值不为NULL,而是指向一个 clusterNode 结构,那么表示当前节点正在将槽i迁移至 clusterNode 所代表的节点。
在对集群进行重分片时,向源节点发送命令:CLUSTER SETSLOT <i> MIGRATING <target_id>,可以将目标节点 clusterState.migrating_slots_to[i] 的值设置为 target_id 所代表节点的 clusterNode 结构。
ASK 错误
如果重新分片期间,命令请求操作的键在正在迁移的槽中,节点会怎么处理?
1、源节点会先在自己的数据库里面查找指定的键 key,如果找到的话,就直接执行客户端发送的命令。
2、相反地,如果源节点没有在自己的数据库里找到键 key,那么节点会检查自己的 clusterState.migrating_slots_to[i],看键 key 所属的槽 i 是否正在进行迁移,如果槽 i 的确在进行迁移的话,那么节点会向客户端发送一个 ASK 错误,引导客户端到正在导入槽i的节点去查找键 key。
3、接收到 ASK 错误的客户端会根据错误提示的 IP 地址和端口号,转向至正在导入槽的目标节点,然后先向目标节点发送一个 ASKING 命令,之后再重新发送原本想要执行的命令。
ASKING 命令
ASKING命令唯一要做的就是打开发送该命令的客户端(redisClient 结构)的REDIS_ASKING标识。
在一般情况下,如果客户端向节点发送一个关于槽i的命令,而槽i又没有指派给这个节点的话,那么节点将向客户端返回一个 MOVED 错误;
但是,如果节点的 clusterState.importing_slots_from[i] 显示节点正在导入槽 i,并且发送命令的客户端带有 REDIS_ASKING 标识,那么节点将破例执行这个关于槽i的命令一次。
当客户端接收到ASK错误并转向至正在导入槽的节点时,客户端会先向节点发送一个 ASKING 命令,然后才重新发送想要执行的命令,这是因为如果客户端不发送 ASKING 命令,而直接发送想要执行的命令的话,那么客户端发送的命令将被节点拒绝执行,并返回 MOVED 错误。
注意:客户端的 REDIS_ASKING 标识是一个一次性标识,当节点执行了一个带有 REDIS_ASKING 标识的客户端发送的命令之后,客户端的 REDIS_ASKING 标识就会被移除。
ASK 错误和 MOVED 错误的区别
MOVED 错误代表槽的负责权已经从一个节点转移到了另一个节点:在客户端收到关于槽 i 的 MOVED 错误之后,客户端每次遇到关于槽 i 的命令请求时,都可以直接将命令请求发送至 MOVED 错误所指向的节点,因为该节点就是目前负责槽 i 的节点。
与此相反,ASK错误只是两个节点在迁移槽的过程中使用的一种临时措施:在客户端收到关于槽 i 的 ASK 错误之后,客户端只会在接下来的一次命令请求中将关于槽 i 的命令请求发送至 ASK 错误所指示的节点,但这种转向不会对客户端今后发送关于槽 i 的命令请求产生任何影响,客户端仍然会将关于槽 i 的命令请求发送至目前负责处理槽 i 的节点,除非 ASK 错误再次出现。
复制与故障转移
复制(新增&设置从节点)
集群中的主节点和从节点
Redis集群中的节点分为主节点(master)和从节点(slave),其中主节点用于处理槽,而从节点则用于复制某个主节点,并在被复制的主节点下线时,代替下线主节点继续处理命令请求。
设置从节点
首先利用命令 CLUSTER MEET <ip> <port> 将一个新节点加入到集群中,此时节点的状态是 REDIS_NODE_MASTER,即此时节点是主节点来的。
然后向新节点发送 CLUSTER REPLICATE <node_id> 命令,将新节点成为 node_id 所指定节点的从节点,并开始对主节点进行复制。此时新节点的状态为 REDIS_NODE_REDIS,即此节点是从节点。
接收到 CLUSTER REPLICATE 命令的节点首先会在自己的 clusterSate.nodes 字典中找到 node_id 所对应节点的 clusterNode 结构,并将自己的 clusterState.myself.slaveof 指针指向这个结构,以此来记录这个节点正在负责哪个主节点。
然后节点会修改自己在 clusterState.myself.flags 中的属性,关闭原本的 REDIS_NODE_MASTER 标识,打开 REDIS_NODE_SLAVE 标识。
最后,节点会调用复制代码,并根据 clusterState.myself.slaveof 指向的 clusterNode 结构所保存的 IP 地址和端口号,对主节点进行复制。因为节点的复制功能和单机 Redis 服务器的复制功能使用了相同的代码,所以让从节点复制主节点相当于向从节点发送命令 SLAVEOF。
一个节点成为从节点,并开始复制某个主节点这一信息会通过消息发送给集群中的其他节点,最终集群中的所有节点都会知道某个从节点正在复制某个主节点。集群中的所有节点都会在代表主节点的 clusterNode 结构的 slaves 属性和 numslaves 属性中记录正在复制这个主节点的从节点名单~
故障检测
集群中的每个节点都会定期地向集群中的其他节点发送 PING 消息,以此来检测对方是否在线,如果接收 PING 消息的节点没有在规定的时间内,向发送 PING 消息的节点返回 PONG 消息,那么发送 PING 消息的节点就会将接收 PING 消息的节点标记为疑似下线(probable fail,PFAIL)。
b style=\
当节点 B 规定时间内没有收到节点 C 对于 PING 消息的 PONG 消息回复,那么节点 B 会找到节点 C 对应的 clusterNode 结构,并在结构里的 flags 属性打开 REDIS_NODE_PFAIL 标识,表示节点 C 进入了疑似下线状态。
接着节点 B 会向集群里的其他节点发送消息来交换节点 C 的状态信息。
当一个主节点A通过消息得知主节点B认为主节点C进入了疑似下线状态时,主节点A会在自己的 clusterState.nodes 字典中找到主节点C所对应的 clusterNode 结构,并将主节点B的下线报告(failure report)添加到 clusterNode 结构的 fail_reports 链表里面:
每个下线报告由一个 clusterNodeFailReport 结构表示:
在一个集群中,半数以上负责处理槽的主节点都将某个主节点 x 报告为疑似下线,那么这个主节点 x 将被标记为已下线(FAIL)。接着将主节点 x 标记为已下线的节点会向集群广播一条关于主节点 x 的 FAIL 消息,所有接收到这条 FAIL 消息的节点都会立即将主节点 x 标记为已下线。
故障转移步骤
1)复制下线主节点的所有从节点里面,会有一个从节点被选中。
2)被选中的从节点会执行SLAVEOF no one命令,成为新的主节点。
3)新的主节点会撤销所有对已下线主节点的槽指派,并将这些槽全部指派给自己。
4)新的主节点向集群广播一条PONG消息,这条PONG消息可以让集群中的其他节点立即知道这个节点已经由从节点变成了主节点,并且这个主节点已经接管了原本由已下线节点负责处理的槽。
5)新的主节点开始接收和自己负责处理的槽有关的命令请求,故障转移完成。
选举新的主节点
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)如果在一个配置纪元里面没有从节点能收集到足够多的支持票,那么集群进入一个新的配置纪元,并再次进行选举,直到选出新的主节点为止。
这个选举新主节点的方法和选举领头Sentinel的方法非常相似,因为两者都是基于Raft算法的领头选举(leader election)方法来实现的。
消息
角色
集群中的各个节点通过发送和接收消息(message)来进行通信,我们称发送消息的节点为发送者(sender),接收消息的节点为接收者(receiver)
五种消息
❑MEET 消息:当发送者接到客户端发送的 CLUSTER MEET 命令时,发送者会向接收者发送 MEET 消息,请求接收者加入到发送者当前所处的集群里面。
❑PING 消息:集群里的每个节点默认每隔一秒钟就会从已知节点列表中随机选出五个节点,然后对这五个节点中最长时间没有发送过 PING 消息的节点发送 PING 消息,以此来检测被选中的节点是否在线。除此之外,如果节点A最后一次收到节点B发送的 PONG 消息的时间,距离当前时间已经超过了节点A的 cluster-node-timeout 选项设置时长的一半,那么节点A也会向节点B发送 PING 消息,这可以防止节点A因为长时间没有随机选中节点B作为 PING 消息的发送对象而导致对节点B的信息更新滞后。
❑PONG 消息:当接收者收到发送者发来的 MEET 消息或者 PING 消息时,为了向发送者确认这条 MEET 消息或者 PING 消息已到达,接收者会向发送者返回一条 PONG 消息。另外,一个节点也可以通过向集群广播自己的 PONG 消息来让集群中的其他节点立即刷新关于这个节点的认识,例如当一次故障转移操作成功执行之后,新的主节点会向集群广播一条 PONG 消息,以此来让集群中的其他节点立即知道这个节点已经变成了主节点,并且接管了已下线节点负责的槽。
❑FAIL消息:当一个主节点A判断另一个主节点B已经进入FAIL状态时,节点A会向集群广播一条关于节点B的FAIL消息,所有收到这条消息的节点都会立即将节点B标记为已下线。
❑PUBLISH消息:当节点接收到一个PUBLISH命令时,节点会执行这个命令,并向集群广播一条PUBLISH消息,所有接收到这条PUBLISH消息的节点都会执行相同的PUBLISH命令。
消息组成
消息头(header)
节点发送的所有消息都由一个消息头包裹,消息头除了包含消息正文之外,还记录了消息发送者自身的一些信息,因为这些信息也会被消息接收者用到,所以严格来讲,我们可以认为消息头本身也是消息的一部分。
结构:cluster.h/clusterMsg clusterMsg.data 属性就是消息正文,指向 cluster.h/clusterMsgData
clusterMsg结构的currentEpoch、sender、myslots、flags等属性记录了发送者自身的节点信息,接收者会根据这些信息,在自己的clusterState.nodes字典里找到发送者对应的clusterNode结构,并对结构进行更新。
消息正文(data)
结构:cluster.h/clusterMsgData
MEET、PING、PONG 消息的实现
Redis集群中的各个节点通过Gossip协议来交换各自关于不同节点的状态信息,其中 Gossip 协议由MEET、PING、PONG三种消息实现,这三种消息的正文都由两个cluster.h/clusterMsgDataGossip 结构组成。正式因为这三种消息的正文都是使用 clusterMsgDataGossip 结构,所以节点要通过 clusterMsg.type 属性来判断是这三种消息的其中哪一种。
每次发送MEET、PING、PONG消息时,发送者都从自己的已知节点列表中随机选出两个节点(可以是主节点或者从节点),并将这两个被选中节点的信息分别保存到两个 clusterMsgDataGossip 结构里面。
当接收者收到MEET、PING、PONG消息时,接收者会访问消息正文中的两个clusterMsgDataGossip结构,并根据自己是否认识clusterMsgDataGossip结构中记录的被选中节点来选择进行哪种操作:
❑如果被选中节点不存在于接收者的已知节点列表,那么说明接收者是第一次接触到被选中节点,接收者将根据结构中记录的IP地址和端口号等信息,与被选中节点进行握手。
❑如果被选中节点已经存在于接收者的已知节点列表,那么说明接收者之前已经与被选中节点进行过接触,接收者将根据clusterMsgDataGossip结构记录的信息,对被选中节点所对应的clusterNode结构进行更新。
FAIL 消息的实现
当集群里的主节点A将主节点B标记为已下线(FAIL)时,主节点A将向集群广播一条关于主节点B的FAIL消息,所有接收到这条FAIL消息的节点都会将主节点B标记为已下线。
由于在集群的节点数量比较大的情况下,单纯使用 Gossip 协议来传播节点的已下线信息会给节点的信息更新带来一定的延迟,因为 Gossip 协议消息通常需要一段时间才能传播至整个集群。
所以节点已下线消息通知不会采用 Gossip 协议消息,而是使用 FAIL 消息。
FAIL 消息可以让集群里的所有节点立刻知道某个主节点已下线,从而尽快判断是否需要将集群标记为下线,又或者对下线主节点进行故障转移。
FAIL消息的正文由cluster.h/clusterMsgDataFail结构表示,这个结构只包含一个nodename属性,该属性记录了已下线节点的名字
因为集群里的所有节点都有一个独一无二的名字,所以FAIL消息里面只需要保存下线节点的名字,接收到消息的节点就可以根据这个名字来判断是哪个节点下线了。
PUBLISH 消息的实现
当客户端向集群中的某个节点发送命令 PUBLISH <channel> <message>。接收到 PUBLISH 命令的节点不仅会向 channel 频道发送消息 message,它还会向集群广播一条 PUBLISH 消息,所有接收到这条 PUBLISH 消息的节点都会向 channel 频道发送 message 消息。
PUBLISH 消息正文的结构:cluster.h/clusterMsgDataPublish
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+message_len-1字节保存的则是message参数。
为什么不直接向节点广播 PUBLISH 命令?
实际上,要让集群的所有节点都执行相同的PUBLISH命令,最简单的方法就是向所有节点广播相同的PUBLISH命令,这也是Redis在复制PUBLISH命令时所使用的方法,不过因为这种做法并不符合Redis集群的“各个节点通过发送和接收消息来进行通信”这一规则,所以节点没有采取广播PUBLISH命令的做法。
独立功能的实现
发布与订阅
❑服务器状态在 pubsub_channels 字典保存了所有频道的订阅关系:SUBSCRIBE 命令负责将客户端和被订阅的频道关联到这个字典里面,而 UNSUBSCRIBE 命令则负责解除客户端和被退订频道之间的关联。
❑服务器状态在 pubsub_patterns 链表保存了所有模式的订阅关系:PSUBSCRIBE 命令负责将客户端和被订阅的模式记录到这个链表中,而 PUNSUBSCRIBE 命令则负责移除客户端和被退订模式在链表中的记录。
❑PUBLISH 命令通过访问 pubsub_channels 字典来向频道的所有订阅者发送消息,通过访问 pubsub_patterns 链表来向所有匹配频道的模式的订阅者发送消息。
❑PUBSUB 命令的三个子命令都是通过读取 pubsub_channels 字典和 pubsub_patterns 链表中的信息来实现的。
Redis的发布与订阅功能由PUBLISH、SUBSCRIBE、PSUBSCRIBE等命令组成。
通过 SUBSCRIBE 命令,客户端可以订阅一个或多个频道。
通过 PSUBSCRIBE 命令,客户端可以订阅一个或多个模式。
通过 PUBLISH 命令,客户端可以往指定频道发送消息。
频道的订阅与退订
Redis 将频道的订阅关系保存在服务器状态(redisServer)的 pubsub_channels 字典里面;字典的键是被订阅的频道,值是一个链表,链表记录的是订阅这个频道的所有客户端。
订阅频道
当客户端执行 SUBSCRIBE channel 命令订阅频道时,服务器会将客户端与被订阅的频道在 pubsub_channels 字典中进行关联
1、首先,先判断频道在 pubsub_channels 字典是否存在,如果存在则将客户端添加到订阅者链表的末尾。
2、如果频道在字典中不存在,则在字典中为频道创建一个新的键,并将键的值设置为空链,然后将客户端添加到链表中。
退订频道
客户端执行 UNSUBSCRIBE channel 命令退订频道时,服务器会在 pubsub_channels 字典中将对应的关联关系删掉
1、根据频道的名字,在 pubsub_channels 字典中找到对应的键,然后将客户端从订阅者链表中删掉。
2、如果删掉客户端后,订阅者链表为空,则将频道对应的键也删掉。
模式的订阅与退订
Redis 将模式的订阅关系保存在服务器状态(redisServer)的 pubsub_patterns 链表里面。链表元素的结构为 pubsubPattern。
订阅模式
当客户端执行 PSUBSCRIBE pattern 命令订阅模式时,服务器会将客户端与被订阅模式在 pubsub_patterns 链表中记录起来。
1、新建一个 pubsubPattern 结构,将 pattern 属性设置为被订阅的模式,将 client 属性设置为订阅模式的客户端。
2、将 pubsubPattern 结构添加到 pubsub_patterns 链表的表尾。
退订模式
客户端执行 PUNSUBSCRIBE pattern 命令退订模式时,服务器会将客户端与被订阅模式的记录从 pubsub_patterns 链表中删掉。
1、遍历 pubsub_patterns 链表,找到 pattern 属性为被退订的模式并且 client 属性为执行退订模式的客户端的 pubsubPattern 结构
2、然后将匹配的 pubsubPattern 结构从 pubsub_patterns 链表中删除。
发送消息
Redis 客户端可以使用 PUBLISH <channel> <message> 命令将 message 消息发送 channel 频道中。
将消息发送给频道订阅者
1、遍历 pubsub_channels 字典,找到键和 channel 对应的键值对。
2、遍历值对应的订阅者链表,将消息 message 发送给所有订阅者。
将消息发送给模式订阅者
1、遍历 pubsub_patterns 链表,找到和 channel 匹配的模式。
2、将消息 message 发送给订阅了这些模式的客户端。
最后 PUBLISH 命令的伪代码就是上面两个的结合
查看订阅信息
下面是 PUBLISH 命令的三个子命令,可以利用这三个子命令查看服务器的订阅信息
PUBSUB CHANNELS [pattern]
PUBSUB CHANNELS[pattern] 子命令用于返回服务器当前被订阅的频道,其中 pattern 参数是可选的。
❑如果不给定 pattern 参数,那么命令返回服务器当前被订阅的所有频道。 例如:PUBLISH CHANNEL
❑如果给定 pattern 参数,那么命令返回服务器当前被订阅的频道中那些与 pattern 模式相匹配的频道。例如
1、程序遍历服务器状态(redisServer)的 pubsub_channels 属性(字典)。
2、然后返回那些符合下面判断条件的 channel。判断条件:(命令中的 pattern 为空) or(pattern 不为空并且 channel 与 pattern 匹配)。
PUBSUB NUMSUB [channel1 channel2 .... channelN]
PUBSUB NUMSUB [channel1 channel2 .... channelN] 子命令可以接受多个频道作为输入参数,然后返回这些频道的订阅者数量。
1、遍历 pubsub_channels 字典,找到所有匹配命令参数的键。
2、然后计算键对应的值的长度(链表长度),来作为频道的订阅者数量。
PUBSUB NUMPAT
返回服务器当前被订阅模式的数量
直接返回 pubsub_patterns 的长度即可
事务
❑事务提供了一种将多个命令打包,然后一次性、有序地执行的机制。
❑多个命令会被入队到事务队列中,然后按先进先出(FIFO)的顺序执行。
❑事务在执行过程中不会被中断,当事务队列中的所有命令都被执行完毕之后,事务才会结束。
❑带有WATCH命令的事务会将客户端和被监视的键在数据库的 watched_keys 字典中进行关联,当键被修改时,程序会将所有监视被修改键的客户端的REDIS_DIRTY_CAS标志打开。
❑只有在客户端的REDIS_DIRTY_CAS 标志未被打开时,服务器才会执行客户端提交的事务,否则的话,服务器将拒绝执行客户端提交的事务。
❑Redis的事务总是具有ACID中的原子性、一致性和隔离性,当服务器运行在AOF持久化模式下,并且appendfsync选项的值为always时,事务也具有耐久性。
事务的实现
一个事务从开始到结束通常会经历以下三个阶段:
1、事务开始
客户端发送 MULTI 命令,服务器执行 MULTI 命令逻辑。
服务器会在客户端状态(redisClient)的 flags 属性打开 REDIS_MULTI 标识,将客户端从非事务状态切换到事务状态。
2、命令入队
当客户端切换到事务状态时,服务器会根据客户端发来的命令来执行不同的操作。
❑如果客户端发送的命令为EXEC、DISCARD、WATCH、MULTI四个命令的其中一个,那么服务器立即执行这个命令。
❑与此相反,如果客户端发送的命令是EXEC、DISCARD、WATCH、MULTI四个命令以外的其他命令,那么服务器并不立即执行这个命令。首先检查此命令的格式是否正确,如果不正确就返回错误信息,如果正确将这个命令放入一个事务队列里面,然后向客户端返回QUEUED回复。
事务队列的实现
每个 Redis 客户端都有自己的事务状态,对应的是客户端状态(redisClient)的 mstate 属性。
事务状态(mstate)包含一个事务队列(FIFO 队列),以及一个已入队命令的计数器。
事务队列是一个 multiCmd 类型数组,数组中每个 multiCmd 结构都保存了一个如入队命令的相关信息。例如指向命令实现函数的指针,命令的参数,以及参数的数量。
3、事务执行
客户端发送 EXEC 命令,服务器执行 EXEC 命令逻辑。
由于客户端处于事务状态(flags 有 REDIS_MULTI 标识),服务器会遍历客户端的事务队列,然后执行事务队列中的所有命令,最后将返回结果全部返回给客户端。
WATCH 命令
WATCH 命令是一个乐观锁,它可以在 EXEC 命令执行之前,监视任意数量的数据库键。
在 EXEC 命令执行时,检查被监视的键是否至少有一个已经被修改过了,如果是的话,服务器拒绝执行事务并返回空回复(nil);否则正常执行事务。
每个 Redis 数据库(redisDb)都保存着一个 watched_keys 字典。字典的键是被监视的数据库键,而值则是一个链表,记录了所有监视这个数据库键的客户端。
当一个客户端发送 WATCH 命令时,服务器会将客户端与 watched_keys 字典中对应的数据库键关联起来。
1、判断字典中是否存在对应的数据库键,如果不存在则新建一个。
2、将客户端添加到值对应的链表的表尾。
监视机制的触发原理
1、当服务器执行对数据库进行修改的命令时,比如 SET、LPUSH、SADD、ZREM等等,在执行完修改命令后,都会调用 multi.c/touchWatchKey 函数对 watched_keys 字典进行检查。
2、如果 watched_keys 字典中找到命令中对应的数据库键并且监视客户端链表不为空,则将监视此数据库键的客户端的 REDIS_DIRTY_CAS 标识打开,表示该客户端的事务安全性已经被破坏了。
3、当服务器接收到一个客户端发送的 EXEC 命令时,先判断客户端状态(redisClient)的 flags 属性是否打开了 REDIS_DIRTY_CAS 标识,如果打开了,则拒绝执行客户端提交的事务,否则正常执行。
事务的 ACID 性质
原子性(Atomicity)
事务具有原子性指的是,数据库将事务中的多个操作当作一个整体来执行,服务器要么就执行事务中的所有操作,要么就一个操作也不执行。
Redis 事务的原子性
Redis 事务执行过程中,如果一个命令执行出错,那么就返回错误,接着继续执行下面的命令。那为什么还说 Redis 事务原子性?请看看下面红色框框的讨论!
Redis的事务和传统的关系型数据库事务的最大区别在于,Redis不支持事务回滚机制(rollback),即使事务队列中的某个命令在执行期间出现了错误,整个事务也会继续执行下去,直到将事务队列中的所有命令都执行完毕为止。ps:不支持事务回滚是因为这种复杂的功能和Redis追求简单高效的设计主旨不相符。
为什么很多人说 Redis 事务不是原子性?正是因为 Redis 事务不支持事务回滚机制,如果事务执行中出现了命令执行错误(例如对 String 类型的数据库键执行 LPUSH 操作),只会返回当前命令执行的错误给客户端,并不会影响下面的命令的执行。所以很多人觉得和关系型数据库(MySQL) 不一样,所以认为 Redis 事务不支持原子性。其实应该这么分析:首先,他们俩的定位不一样,一个是关系型数据库,一个是 NoSQL。MySQL 的查询 SQL 是可以相当复杂的,而且MySQL没有事务队列这种说法,SQL 真正开始执行才会进行分析和检查,MySQL 不可能提前知道下一条 SQL 是否正确。所以支持事务回滚是非常有必要的~但是~ Redis 使用了事务队列来预先将执行命令存储起来,并且会对其进行格式检查的,提前就知道命令是否可执行了。所以 Redis 作者认为基本只会出现在开发环境的编程错误其实在生产环境基本是不可能出现的(例如对 String 类型的数据库键执行 LPUSH 操作),所以他觉得没必要为了这事务回滚机制而改变 Redis 追求简单高效的设计主旨。所以最后,其实 Redis 事务真正支持原子性的前提:开发者不要傻不拉几的写有逻辑问题的代码!
一致性(Consistency)
事务具有一致性指的是,如果数据库在执行事务之前是一致的,那么在事务执行之后,无论事务是否执行成功,数据库也应该仍然是一致的。
“一致”指的是数据符合数据库本身的定义和要求,没有包含非法或者无效的错误数据。
Redis 事务的一致性
Redis通过谨慎的错误检测和简单的设计来保证事务的一致性
1、入队错误
如果一个事务在命令入队的过程中,发现命令不存在或者命令不正确等情况,Redis 会直接拒绝执行这个事务。
因为服务器会拒绝执行入队过程中出现错误的事务,所以Redis事务的一致性不会被带有入队错误的事务影响。
ps:Redis 2.6.5前,即使事务队列中的命令是错误的,Redis 还是会执行这个事务,不过会将错误命令全部忽略掉,所以最后还是不会因为入队错误而影响事务的一致性。
2、执行错误
执行过程中发生的错误都是一些不能在入队时被服务器发现的错误,这些错误只会在命令实际执行时被触发。
即使在事务的执行过程中发生了错误,服务器也不会中断事务的执行,它会继续执行事务中余下的其他命令,并且已执行的命令(包括执行命令所产生的结果)不会被出错的命令影响。
对数据库键执行了错误类型的操作是事务执行期间最常见的错误之一。
因为在事务执行的过程中,出错的命令会被服务器识别出来,并进行相应的错误处理,所以这些出错命令不会对数据库做任何修改,也不会对事务的一致性产生任何影响。
3、服务器停机
无论Redis 服务器运行在哪种持久化模式下,事务执行中途发生的停机都不会影响数据库的一致性。要不就是根据 RDB 文件或者 AOF 文件恢复数据库状态,要不直接空白状态。
隔离性(Isolation)
事务的隔离性指的是,即使数据库中有多个事务并发地执行,各个事务之间也不会互相影响,并且在并发状态下执行的事务和串行执行的事务产生的结果完全相同。
Redis 事务的隔离性
因为 Redis 使用单线程的方式来执行事务(以及事务队列中的命令),并且服务器保证,在执行事务期间不会对事务进行中断,因此,Redis 的事务总是以串行的方式运行的,并且事务也总是具有隔离性的。
耐久性(Durability)
事务的耐久性指的是,当一个事务执行完毕时,执行这个事务所得的结果已经被保存到永久性存储介质(比如硬盘)里面了,即使服务器在事务执行完毕之后停机,执行事务所得的结果也不会丢失。
Redis 事务的耐久性
当服务器在无持久化的内存模式下运作时,事务不具有耐久性:一旦服务器停机,包括事务数据在内的所有服务器数据都将丢失。
当服务器在 RDB 持久化模式下运作时,服务器只会在特定的保存条件被满足时,才会执行 BGSAVE 命令,对数据库进行保存操作,并且异步执行的 BGSAVE 不能保证事务数据被第一时间保存到硬盘里面,因此 RDB 持久化模式下的事务也不具有耐久性。
当服务器运行在 AOF 持久化模式下,并且 appendfsync 选项的值为 always 时,程序总会在执行命令之后调用同步(sync)函数,将命令数据真正地保存到硬盘里面,因此这种配置下的事务是具有耐久性的。
当服务器运行在 AOF 持久化模式下,并且 appendfsync 选项的值为 everysec 时,程序会每秒同步一次命令数据到硬盘。因为停机可能会恰好发生在等待同步的那一秒钟之内,这可能会造成事务数据丢失,所以这种配置下的事务不具有耐久性。
当服务器运行在 AOF 持久化模式下,并且 appendfsync 选项的值为 no 时,程序会交由操作系统来决定何时将命令数据同步到硬盘。因为事务数据可能在等待同步的过程中丢失,所以这种配置下的事务不具有耐久性。
no-appendfsync-on-rewrite配置选项对耐久性的影响
当这个选项打开时,如果 Redis 在执行 BGSAVE 命令或者是 BGREWRITE 命令,会暂时停止对 AOF 文件进行同步。
所以说,如果打开了这个选项,always 模式的 AOF 持久化不再可以保证事务的耐久性了!当然了,这个配置默认是关闭的。
Lua 脚本
排序
SORT命令通过将被排序键包含的元素载入到数组里面,然后对数组进行排序来完成对键进行排序的工作。
在默认情况下,SORT命令假设被排序键包含的都是数字值,并且以数字值的方式来进行排序。
如果SORT命令使用了ALPHA选项,那么SORT命令假设被排序键包含的都是字符串值,并且以字符串的方式来进行排序。
SORT命令的排序操作由快速排序算法实现。
SORT命令会根据用户是否使用了DESC选项来决定是使用升序对比还是降序对比来比较被排序的元素,升序对比会产生升序排序结果,被排序的元素按值的大小从小到大排列,降序对比会产生降序排序结果,被排序的元素按值的大小从大到小排列。
当SORT命令使用了BY选项时,命令使用其他键的值作为权重来进行排序操作。
当SORT命令使用了LIMIT选项时,命令只保留排序结果集中LIMIT选项指定的元素。
当SORT命令使用了STORE选项时,命令会将排序结果集保存在指定的键里面。
当SORT命令同时使用多个选项时,命令先执行排序操作(可用的选项为ALPHA、ASC或DESC、BY),然后执行LIMIT选项,之后执行GET选项,再之后执行STORE选项,最后才将排序结果集返回给客户端。
除了GET选项之外,调整选项的摆放位置不会影响SORT命令的排序结果。
SORT <key> 命令的实现
SORT 命令最简单执行方式为:SORT <key>;这个命令可以对一个包含数字值的键 key 进行排序(默认升序)。
RPUSH numbers 3 1 2SORT numbers
1、创建一个和 numbers 列表长度相同的数组,数组的每个项都是一个 redis.h/redisSortObject 结构。
2、遍历数组,将各个数组项的 obj 指针分别指向 numbers 列表的各个项,构成 obj 指针和列表项之间的一对一关系。
3、遍历数组,将各个 obj 指针所指向的列表项转换成一个 double 类型的浮点数,并将这个浮点数保存在相应数组项的 u.score 属性里面。
4、根据数组项 u.socre 属性的值,对数组进行数字值排序,排序后的数组项按 u.score 属性的值从小到大排列。
5、遍历数组,将数组项的 obj 指针所指向的列表项作为排序结果返沪给客户端。
ALPHA 选项的实现
通过使用 ALPHA 选项,SORT 命令可以对包含字符串值的键进行排序:SORT <key> ALPHA
SADD fruits apple banana cherrySORT fruits ALPHA
1、创建一个 redisSortObject 结构数组,数组的长度等于 fruits 集合的大小。
2、遍历数组,将各个数组项的 obj 指针分别指向 fruits 集合的各个元素。
3、根据 obj 指针所指向的集合元素,对数组进行字符串排序,排序后的数组项按集合元素的字符串值从小到大排列。
4、遍历数组,依次将数组项的 obj 指针所指向的元素返回给客户端。
ASC 选项和 DESC 选项的实现
在默认情况下,SORT 命令执行升序排序,排序后的结果按值的大小从小到大排列
相反地,在执行 SORT 命令时使用 DESC 选项,可以让命令执行降序排序,让排序后的结果按值的大小从大到小排列
升序排序和降序排序都由相同的快速排序算法执行。
BY 选项的实现
在默认情况下,SORT命令使用被排序键包含的元素作为排序的权重,元素本身决定了元素在排序之后所处的位置。
另一方面,通过使用BY选项,SORT命令可以指定某些字符串键,或者某个哈希键所包含的某些域(field)来作为元素的权重,对一个键进行排序。命令格式:SORT<key>BY<pattern>
命令执行步骤
SADD fruits apple banana cherry
MSET apple-price 8 banana-price 5.5 cherry-price 7利用 mset 命令创建对个字符串类型的键值对。
SORT fruits BY *-price
实现步骤
3、遍历数组,根据各个数组项的 obj 指针所指向的集合元素,以及 BY 选项所给定的模式 *-price ,查找相应的权重键。例如 apple 就会找到数据库键 apple-price
4、将各个权重键的值转换成一个 double 类型的浮点数,然后保存在相应数组项的 u.score 属性里面。
5、以项目组 u.score 属性的值为权重,对数组进行排序,得到一个按 u.score 属性的值从小到大排序的数组。
6、遍历数组,依次将数组项的 obj 指针所指向的集合元素返回给客户端。
带有 ALPHA 选项和 BY 选项的实现
BY选项默认假设权重键保存的值为数字值,如果权重键保存的是字符串值的话,那么就需要在使用BY选项的同时,配合使用ALPHA选项。命令格式:SORT <key> BY <pattern>ALPHA
MSET app-id \"FRUIT-25\" banana-id \"FRUIT-79\" cherry-id \"FRUIT-13\"
SORT fruits BY *-id ALPHA
3、遍历数组,根据各个数组项的 obj 指针所指向的集合元素,以及 BY 选项所给定的模式 *-id ,查找相应的权重键。例如 apple 就会找到数据库键 apple-id
4、将各个数组项的 u.cmpobj 指针分别指向相应的权重键(一个字符串对象)。
5、以各个数组项的权重键的值为权重,对数组执行字符串排序。
LIMIT 选项的实现
在默认情况下,SORT命令总会将排序后的所有元素都返回给客户端;通过 LIMIT 选项,我们可以让 SORT 命令只返回其中一部分已排序的元素。
LIMIT 选项的格式为 LIMIT<offset><count>:
offset参数表示要跳过的已排序元素数量。
count参数表示跳过给定数量的已排序元素之后,要返回的已排序元素数量。
SADD alphabet a b c d e f
SORT alphabet ALPHA LIMIT 0 4
SORT alphabet ALPHA LIMIT 2 3
1、创建一个 redisSortObject 结构数组,数组的长度等于 alphabet 集合的大小。
2、遍历数组,将各个数组项的 obj 指针分别指向 alphabet 集合的各个元素。
3、根据 obj 指针所指向的集合元素,对数组进行字符串排序。
4、根据选项 LIMIT 0 4,将指针移动到数组的索引0上面,然后依次访问array[0]、array[1]、array[2]、array[3]这4个数组项,并将数组项的 obj 指针所指向的元素\"a\"、\"b\"、\"c\"、\"d\"返回给客户端。
服务器执行 SORT alphabet ALPHA LIMIT 2 3 命令时的第一至第三步都和执行 SORT alphabetALPHA LIMIT 0 4 命令时的步骤一样,只是第四步有所不同
4、根据选项 LIMIT 2 3,将指针移动到数组的索引2上面,然后依次访问array[2]、array[3]、array[4]这3个数组项,并将数组项的 obj 指针所指向的元素\"c\"、\"d\"、\"e\"返回给客户端。
GET 选项的实现
在默认情况下,SORT命令在对键进行排序之后,总是返回被排序键本身所包含的元素;通过使用GET选项,我们可以让SORT命令在对键进行排序之后,根据被排序的元素,以及GET选项所指定的模式,查找并返回某些键的值。
命令执行
SADD students peter jack tom
MSET peter-name \"Peter White\" jack-name \"Jack Snow\" tom-name \"Tom Smith\"
SORT students ALPSHA GET *-name
1、创建一个 redisSortObject 结构数组,数组的长度等于 students 集合的大小。
2、遍历数组,将各个数组项的 obj 指针分别指向 students 集合的各个元素。
4、遍历数组,根据数组项 obj 指针所指向的集合元素,以及 GET 选项所给定的 “*-name”模式,查找到对应的键。例如 jack 就会找到 jack-name
5、遍历查找程序返回的三个键,并向客户端返回他们的值。
一个 SORT 命令可以带有多个 GET 选项。
例如,我们可以同时返回学生的全名和出生日期
MSET peter-birth \"1995-5-5\" jack-birth \"1996-6-6\" tom-birth \"1997-7-7\"
SORT students ALPSHA GET *-name GET *-birth
1、2、3、前三个步骤和上面一个 GET 选项是一样的
4、遍历数组,根据数组项 obj 指针所指向的集合元素,以及两个 GET 选项所给定的 *-name 模式和 *-birth 模式,查找相应的键。例如 jack 就会找到 jack-name 和 jack-birth
5、遍历查找程序返回的六个键,并向客户端返回他们的值。
STORE 选项的实现
在默认情况下,SORT命令只向客户端返回排序结果,而不保存排序结果;通过使用STORE选项,我们可以将排序结果保存在指定的键里面,并在有需要时重用这个排序结果
SORT students ALPSHA STORE sorted_students
4、检查 sorted_students 键是否存在,如果存在就删除该键。
5、设置 sorted_students 为空白的列表键。
6、遍历数组,将排序后的三个元素依次推入 sorted_students 列表的末尾(相当于执行命令 RPUSH sorted_students xx1 xx2 xxx3)。
7、遍历数组,向客户端返回三个元素。
多个选项的执行顺序
选项的执行顺序
1)排序:在这一步,命令会使用ALPHA、ASC或DESC、BY这几个选项,对输入键进行排序,并得到一个排序结果集。
2)限制排序结果集的长度:在这一步,命令会使用LIMIT选项,对排序结果集的长度进行限制,只有LIMIT选项指定的那部分元素会被保留在排序结果集中。
3)获取外部键:在这一步,命令会使用GET选项,根据排序结果集中的元素,以及GET选项指定的模式,查找并获取指定键的值,并用这些值来作为新的排序结果集。
4)保存排序结果集:在这一步,命令会使用STORE选项,将排序结果集保存到指定的键上面去。
5)向客户端返回排序结果集:在最后这一步,命令遍历排序结果集,并依次向客户端返回排序结果集中的元素。
选项的摆放顺序
调用 SORT 命令时,除了 GET 选项之外,改变选项的摆放顺序并不会影响 SORT 命令执行这些选项的顺序。因为程序会按照多个 GET 选项的顺序返回结果给客户端。
二进制位数组
Redis使用SDS来保存位数组。
SDS使用逆序来保存位数组,这种保存顺序简化了SETBIT命令的实现,使得SETBIT命令可以在不移动现有二进制位的情况下,对位数组进行空间扩展。
BITCOUNT命令使用了查表算法和variable-precision SWAR算法来优化命令的执行效率。
BITOP命令的所有操作都使用C语言内置的位操作来实现。
位数组的表示
Redis使用字符串对象来表示位数组,因为字符串对象使用的SDS数据结构是二进制安全的,所以程序可以直接使用SDS结构来保存位数组,并使用SDS结构的操作函数来处理位数组。
例子:使用 SDS 表示一字节长的位数组
redisObject.type的值为REDIS_STRING,表示这是一个字符串对象。
sdshdr.len的值为1,表示这个SDS保存了一个一字节长的位数组。
buf数组中的buf[0]字节保存了一字节长的位数组。
buf数组中的buf[1]字节保存了SDS程序自动追加到值的末尾的空字符'\\0'。
Redis 使用逆序来保存位数组。
例如 buf 数组中的 buf[0] 字节中各个位的值分别是 1、0、1、1、0、0、1、0,这表示 buf[0] 字节保存的位数组为 01001101.
GETBIT 命令的实现
GETBIT命令用于返回位数组bitarray在offset偏移量上的二进制位的值:GETBIT <bitarry> <offset>
GETBIT 命令的执行过程
1、计算 byte = offset ÷ 8,byte 值记录了 offset 偏移量指定的二进制保存在位数组的哪个字节。
2、计算 bit = (offset mod 8) + 1,bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第几个二进制位。
3、根据 byte 值和 bit 值,在位数组 bitarray 中定位 offset 偏移量指定的二进制位,并返回这个位的旧值。
例子:GETBIT <bitarry> 3
1、byte = 3 ÷ 8 = 0,表明 offset 在 buf[0] 字节上。
2、bit = (3 mod 8) + 1 = 4,表明 offset 在 buf[0] 字节的第四个二进制位上。
3、根据上面的 byte 和 bit 值,定位到 buf[0] 字节的第四个二进制位上,取值。
4、向客户端返回步骤3取到的值。
代码
SETBIT 命令的实现
SETBIT 用于将位数组 bitarray 在 offset 偏移量上的二进制位的值设置为 value ,并向客户端返回二进制位被设置之前的旧值:SETBIT <bitarray> <offset> <value>
SETBIT 命令的执行过程
1、计算 len = offset ÷ 8 + 1,len 值记录了保存 offset 偏移量指定的二进制至少需要多少字节。
2、检查 bitarray 键保存的位数组(也就是 SDS)的长度是否小于 len,如果是的话,将 SDS 的长度扩展为 len 字节,并将所有新扩展空间的二进制位的值设置为0。
3、计算 byte = offset ÷ 8,byte 值记录了 offset 偏移量指定的二进制位保存在位数组的哪个字节上。
4、计算 bit = (offset mod 8) + 1,bit 值记录了 offset 偏移量指定的二进制位是 byte 字节的第几个二进制位。
5、根据 byte 值和 bit 值,在位数组 bitarray 中定位 offset 偏移量指定的二进制位,首先将指定二进制位现在的值保存在 oldvalue 变量中,然后将新值 value 设置为这个二进制的值。
6、向客户端返回 oldvalue 变量的值。
SDS 扩展的知识点
假设 buf 数组一开始只有1个字节来保存位数组(结束符号一个字节不算在内),然后现在位数组一共需要 2个字节来保存,那么会对 buf 数组进行扩展,len 属性扩展为 2;并且程序还会为 buf 数组预分配2个字节的未使用空间,即 free 属性也为2,此时 buf 数组就是 4个字节了(结束符号一个字节不算在内);最后还要加上结尾标识符一个字节(空字符),SDS 一共就有 5个字节了。
由于 buf 数组使用逆序来保存位数组,所以即使程序对 buf 数组进行扩展后,写入操作直接在新扩展的二进制位中完成即可,而不需要改动位数组原来已有的二进制位。而如果 Redis 设计是使用顺序来保存位数组的话,那么每次扩展都需要对已有的二进制位进行移动,然后才能执行写入操作,这样的话命令的执行速度大大下降!
BITCOUNT 命令的实现
遍历算法:实现BITCOUNT命令最简单直接的方法,就是遍历位数组中的每个二进制位,并在遇到值为1的二进制位时,将计数器的值增一。
查表算法:我们可以创建一个表,表的键为某种排列的位数组,而表的值则是相应位数组中,值为1的二进制位的数量。例如对 8位长的位数组创建一个表。
variable-precision SWAR算法:该算法通过一系列位移和位运算操作,可以在常数时间内计算多个字节的汉明重量,并且不需要使用任何额外的内存。
Redis 的实现
BITCOUNT命令的实现用到了查表和variable-precisionSWAR两种算法
❑查表算法使用键长为8位的表,表中记录了从0000 0000到1111 1111在内的所有二进制位的汉明重量。
慢查询日志
监视器
0 条评论
回复 删除
下一页