Redis设计与实现

本博文是对《Redis设计与实现》的读书笔记,这书写的真的是挺好的,值得一看。本书基于Redis2.9,而我看的时候最新版本的Redis是6.0,所以代码部分我是直接用的6.0。

数据结构和对象

Redis一共有五种基本对象(Object),分别是:

  • 字符串对象 string object
  • 哈希对象 hash object
  • 列表对象 list object
  • 集合对象 set object
  • 有序集合对象 sorted set object

而每一种对象的背后,起码有两种数据结构来对其进行实现,这些对象都是一个个redisObject,下面是redisObject的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct redisObject {
// 具体是什么对象
unsigned type:4;
// 对象用的底层实现是什么
unsigned encoding:4;
// 下面的lru先忽略
unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or
* LFU data (least significant 8 bits frequency
* and most significant 16 bits access time). */
// 引用计数
int refcount;
// 指向底层具体的结构
void *ptr;
} robj;

字符串对象底层结构

字符串的底层可以有三种,分别是int、raw和embstr。

int自然不必多说,如果我需要保存字符串”12345”,那么我完全可以用int来保存它(当然不能超过阈值)。

如果要表示的字符串它不是数字,那么有两种情况:

  1. 该字符串的长度大于32字节,那么用SDS来保存,即为raw编码来实现。
  2. 该字符串长度小于32字节,那么使用embstr的编码来保存。

SDS

首先新增了两个属性分别是free和len,一个用来指明还有多少空间剩余,一个则是指明数组的长度(不包括最后一个\0)。

这个数据结构的空间分配也有点意思:如果len的值小于1MB,那么还会额外为SDS分配等量的free空间。总空间则是len+free+1。如果len大于了1MB,那么就只会分配给1MB的空间。也就是每次Redis都会浪费一半的空间。在释放空间的时候,并不是直接释放,而是惰性释放,只有调用相关api的时候才真正的释放。

同样因为使用了len这个数值作为判断依据,所以可以保存二进制的数据。

raw编码和embstr编码

raw编码和embstr编码使用的是一种叫SDS的结构,该结构就是为了在普通的char []数组上,封装了一个长度(len)和空余空间(free)这两个属性(在Redis6.0里面我看到是有5种SDS,其实就是len和free单位的变化)。 len的意思就是当前字符串占的长度,比如hello的长度就是5(当然第6位是\0,即空字符是不计算在len中的),而free则是还剩下多少空间没使用。

使用SDS的好处是,首先strlen()的时间复杂度变成了O(1),其次是不用担心缓冲区溢出,再来就是可以有效减少内存分配的次数,最后就是可以有效的存储二进制数据。SDS最底层用的还是char buf[],所以最后字符串最后一位还是\0,只不过这个最后一位不计算在len中。

那么它们的区别是什么呢?

raw编码会调用两次内存分配函数,分别分配redisObject和sds,而embstr则只会调用一次内存分配函数,将redisObject和sds紧紧挨着放在同一块内存中。同时embstr是只读的,也就是如果你要使用APPEND这类的函数来操作字符串,那么会先将其转换成raw编码的。

###哈希对象底层结构

哈希底层结构是ziplist或者hashtable。

ziplist

从名字上看这是一个压缩的列表,如果列表里的数字比较小,字符串又比较短,那么就可以使用ziplist来作为底层的数据结构。为什么能用来作为哈希对象的底层结构呢?其实只要是列表,那我完全可以list[0]作为key,list[1]作为value,以此类推即可。这个数据结构主要是从节约内存的角度来考虑的,它长这个样子:

image-20200622213138371

接下来是对每一部分的说明:

image-20200622213212343

可以看到,正是因为每一个列表的节点长度都是由节点保存的内存来决定,而不是固定大小,所以才可以节约内存。

对于每一个entryX,都记录了它前一个节点的长度,所以我们可以很轻松的通过指针减,从zltail开始不断往前遍历ziplist。

也就是ziplist其实在内存中是倒着存放你的数据的,但是因为读起来也是倒着读的,所以其实压根没有影响。

而压缩表最需要注意的就是有的时候可能会一个变化导致整个压缩表都需要更新,此时就非常消耗性能了。

hashtable

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 整个hashtable
typedef struct dictht {
dictEntry **table;
unsigned long size;

// sizemask = size-1,用来计算索引的
unsigned long sizemask;
unsigned long used;
} dictht;

// 其中的一条key-value
typedef struct dictEntry {
void *key;
union {
// 值可以从下面四选一
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;

所以hashtable的整体构造图如下图所示:

image-20200622214354354

上图中还发生了哈希碰撞,可以看到是后来的k1v1,在链表中的位置是在k0v0之前的——即使用的是头插法而不是尾插法。跟java中的hashmap如出一辙。扩容方法都是一致的,乘以二进行扩容。

dict

在hashtable基础之上,又封装了一层:

1
2
3
4
5
6
7
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx == -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;

其中最重要的就是ht[2]这个hashtable数组,ht[0]就是原先的hashtable,而当需要rehash的时候,就会把值慢慢移动到ht[1]中(注意是慢慢的,而不是一次性,否则要重新计算那么多hash,CPU受不了),一旦开始移动了,就不会再往ht[0]中存放数据了。

列表对象底层结构

列表对象可以由ziplist数据结构和linkedlist数据结构作为底层数据结构,ziplist上面已经讲过了,而linkedlist就是双向列表,最最基础的数据结构了,不可能不会。

集合对象底层结构

集合对象的底层结构可以由hashtable(只使用它的键值对中的键,所有的值一律为null即可)和intset(注意和insert的区别)来实现。

intset

1
2
3
4
5
6
typedef struct intset {
// 编码方式
uint32_t encoding;
uint32_t length;
int8_t contents[];
} intset;

contents里面存的是按照从小到大排列的整数,其类型不一定是int8_t,而是由encoding来指定的。

显然这个数据结构就是用来实现整数的集合的。而这个contents就是用来存放这些整数的,按照从小到大的顺序,且不会重复。

这个数据结构要弄清楚的就是升级和降级,升级就是原来存的每一个元素都是16位的,结果发现来了一个特别大或者特别小的数字,那么16位不够用,就需要对所有的元素进行一次升级,将它们升级到和这个数字一样的大小。降级也是同理。注意,由于是新来的数字导致了需要升级,所以这个数字必然是最大的或者最小的,所以其实效率还是可以接受的。

有序集合对象底层结构

有序集合,就是每一个元素都有一个值,按照该值的大小对集合进行排序。它的底层结构可以是ziplist或者skiplist(面试常考)。

跳表

跳表的实质跟二叉树非常像,基本思想都是一开始上来先减掉一半,然后接着砍一半。

image-20200622220415872

第一列是跳表的基本结构,第二列可以看到是L32~L1的结构,接下来就分别是三个元素o1o2和o3,以及它们的分数1.0,2.0和3.0

每一列(除了L32那列)的层数,都是随机生成的,为的就是防止插入和删除需要来维持数据结构而浪费过多时间。

具体的更加详细的数学证明可以参考 这篇博客,如果只是简单使用理解,相信是非常简单的。

单机数据库

数据库

在redis中,用redisServer这个数据结构来代表redis的服务器,里面最重要的就是redisDb *db;这个数组,每一个元素都对应了一个数据库,而这个数据库下面最重要的就是dict *dict这个结构,也就是数据库底层就是一个字典(还给这个字典取了个好听的名字叫key space,键空间),还有一个属性是dbnum,默认是16,这也就是为什么默认redis里面默认就有16个数据库。而在redisClient中则是用redisDb *db;来指向目前正在操作的数据库类型。

Redis中有4个指令可以用于操作数据库设置键的过期时间:

  1. EXPIRE key ttl:多少秒后过期
  2. PEXPIRE key ttl:多少毫秒后过期
  3. EXPIREAT key timestamp:在某个时间戳(秒为单位)后过期
  4. PEXPIREAT key timestamp:在某个时间戳(毫秒为单位)后过期

这四个可以很轻松进行转化,所以在Redis中会都转化成第四个进行操作。为了实现这个,Redis对每个数据库都有一个对应的叫expires的字典,该字典保存了键的过期时间(如果没有过期时间,则这个字典中就不会有相应的值)。实际中,这个字典的key保存的是声明了过期时间的对象(这个会和dict中共享,所以对象是不会重复的,也就是空间其实是很省的),然后value自然就是过期的unix timestamp(毫秒为单位)了。

对于键的过期操作,也有三种,分别是:

  • 定时删除:在给键设置过期时间的同时,创建一个定时器,只要过期时间一到,键就被删除。可以即时释放内存空间,但是对CPU不友好,并不推荐。
  • 惰性删除:键过期了不管,但是当获取键的时候,先去检查一下有没有过期,过期了就顺手删掉。对CPU友好,但是对内存不友好。
  • 定期删除:每隔一段时间对数据库进行检查。使用的是抽查模式,而不是遍历。

Redis在实际中用的是惰性删除和定期删除。

过期删除键对数据库的影响,只有一条比较违背常识:当主从服务器中都有一个key到了过期的时候,如果去从服务器访问这个key,这个key可以正常读写不被删除,只有当去主服务器进行读的时候,才会在所有的服务器上删除这个过期的key。这么做的目的是统一

总得来说就是一个server下面有一个db数组,对应了多个db,然后每个db下面有两个字典,一个存放真实的键值对,一个存放过期时间。

持久化

持久化有两种,一种是保存了从数据库开始到现在为止的所有操作(当然是需要优化过的),还有一种就是把内存里的数据给直接存到磁盘里,至于具体磁盘里的格式,我个人觉得是没必要掌握的。

事件

Redis服务器需要处理两类事件:

  • 文件事件:客户端和服务器之间,服务器相互之间都是通过套接字来进行连接的,文件事件就是对套接字操作的抽象(所以你可以直接理解为,如果客户端要向服务器发送消息,本质上就是在写一个文件,其余同理)
  • 时间事件:服务器中有一些操作需要每隔多久的时间来执行,这类操作就被抽象成了时间事件。

文件事件

我们都知道Redis是单进程单线程来进行处理套接字的,这就需要解决阻塞的问题,而一般的解决办法就是用多进程/多线程来进行处理,而Redis则是使用IO多路复用,相当于当某一个socket可读可写了,就由操作系统来通知Redis服务器,这样Redis服务器就去读写,整体的结构就如图所示:

image-20200624225951922

当客户端对套接字执行write操作,类似于你现在需要从客户端发送一条命令给服务器,对应的服务器的套接字就变得可读,于是就产生了AE_READABLE事件。

同理,当客户端对套接字执行read操作的时候,套接字产生AE_WRITEABLE事件。

产生事件的类型,其实就是根据服务器对于socket的读写来确定的。所以我们可以说Redis服务器是一个事件驱动的程序,发生了对应的事件,就调用不同的处理器进行处理。

时间事件

Redis服务器中就只有一个叫serverCron的函数作为时间事件的处理函数,基本理念就是每隔100ms进行一次检查操作。

多机数据库

复制

复制其实很简单,因为Redis是内存数据库,所以当我们从磁盘中恢复一个Redis的时候,就相当于在复制这个Redis数据库。现实中碰到的一个问题是复制可能需要的量太大了(毕竟从磁盘到内存的速度肯定是远远大于你在网络中传输的速度),这个需要额外使用一个缓存区,这样当一个服务器掉线的时候,服务器只需要把该服务器掉线之后的那些命令发送给它就能实现同步了。

同步

从服务器在复制主服务器的内容的时候,是通过SYNC这个命令来完成的。主服务器在收到这个命令之后,会使用BGSAVE命令来生成一个RDB文件,并且记录下从开始BGSAVE之后的所有命令。这样只需要把这个RDB文件发送给从服务器,并且把记录下来的命令也一并发给从服务器就可以了。

传播

在同步完成之后,主从两者的状态就一致了,接下来只要让任何命令都传播一下就好了。

部分重同步

每当主服务器向从服务器发送N个字节的数据之后,就把自己的offset+N。同理,从服务器收到之后也加上N。所以只需要比对一下offset就可以知道同步的状态了。而为了同步,主服务器还有一块缓冲区(缓冲区记录了偏移量以及对应的字节)用来保存最近的命令。这样从服务器如果断线之后,只需要把自己的offset发过来,主服务器根据缓冲区就可以知道到底是进行部分重同步呢,还是完整重同步。

除此之外,当从服务器第一次连接到主服务器的时候,主服务器会发送自己的id给从服务器,以便之后从服务器断线重连后判断。

心跳检测

从服务器每隔一秒发送一次offset。这个可以用来检测两者的网络连接是否正常,并且主服务器能够知晓从服务器目前的状态,并根据从服务器的状态来进行调整。

sentinel(高可用)

当sentinel检测到主服务器下线的时候,它会通知其中一个从服务器,将其作为主服务器,并通知其他所有的从服务器,让它们听命于新的主服务器。如果之前的主服务器上线了,那么也只有乖乖做从服务器的份。

基本步骤

sentinel本身是一个特殊的Redis服务器,只不过里面使用了不同的命令表,所以对于一般的服务器能用的指令对它是不生效的。

在配置文件里可以写好需要监视的主服务器的ip/port。在启动好sentinel之后,就需要向服务器创建两个链接。一个用来向主服务器发送命令并接收恢复,另外一个是用来订阅连接的。

sentinel会每隔10秒向被监视的主服务器发送INFO命令,来获取它们的信息(主服务器会自动向sentinel返回从服务器的信息),然后sentinel就可以知道从服务器的信息,并且会向从服务器同样建立命令连接和订阅连接。

接下来,sentinel也会向从服务器默认每隔10秒发送一次INFO命令,获取信息。

此时相当于sentinel已经知道了所有服务器的状态信息,接下来它会通过每隔2秒一次的频率,通过命令连接向服务器的频道发送一条信息。并且sentinel自身也会通过订阅连接向服务器发送订阅内容。这里有一点点绕,简单来说就是sentinel通过命令连接给每个(主从都要)服务器发送一条消息到频道中,并且还通过订阅链接从频道中接受信息。这个如果只有一台sentinel的话,看上去很蠢,因为这个其实是为了多台sentinel之间共享信息而设计的。然后sentinel就会跟别的sentinel建立命令连接。

总结:每隔10秒向所有主从服务器发送INFO命令来更新,每隔2秒向订阅连接发送消息并且接受消息,相当于每隔2秒更新其它sentinel的消息。

检测下线

sentinel会每隔一秒向所有的服务器(主、从、其余sentinel)发送一个PING,来判断它们是否在线。超过一定时间不回复,或者都是无效的回复的话,就主观认定下线了。

然后此时sentinel会向别的sentinel去询问它们关于这台服务器的下线与否的判断(因为不同sentinel配置的下线时间是不同的),根据得到的回复进行进一步判断。

如果一个服务器被认定为客观下线了,那么监视这个服务器的各个sentinel会协商出一个领头sentinel,这个算法就是raft算法。这里简单描述一下:每一轮选举都有一个计数器来指示这是第几轮,不论选举是不是成功,都会自增。所有的sentinel都会要求将自己作为领头的,而只有收到超过半数支持的sentinel才是真正的领头sentinel。你可能会担心这样冲突会不会导致最后没有一个sentinel能称为领头的?这个靠的是时间差,一般来说总有一个sentinel能够最先发起选票,这样大家都会投它。

接下来这个领头的sentinel会选取一个从服务器,令它成为主服务器,并且让所有其他的从服务器让它作为主服务器。

它的核心思想就是向被监视的主服务器发送INFO命令,来获取它们的信息(主服务器会自动向sentinel返回从服务器的信息),同时sentinel之间也会通过频道来接手别的sentinel的信息,彼此之间互相了解。当sentinel检测的服务器下线的时候,它就会向所有的监视这个服务器的sentinel发出询问,如果半数sentinel认为它下线了,那么就需要做一个故障转移(利用raft算法选举行的主服务器并进行一系列操作)

集群

集群的本质,你可以理解为一个大的数据库,然后每个redis都是它的一部分。集群一共有16384个槽,这些槽被所有节点分了,每个槽必定属于其中的一个redis。然后每个Redis都是知道任何一个槽都是由谁来负责的(通过互相之间信息沟通)。所以任何一个节点在接受到命令,并且计算出对应的数据在哪个槽的时候,都能够知道应该去哪个redis里面获取数据。

集群中的各个节点都是互相进行通信的,如果有个节点发现了超过半数的节点认为一个节点下线了,那么就会发送一条该节点下线了的消息广播给大家。此时就会从该下线的主服务器的从服务器中选举(raft算法)出一个来代替它作为新的主服务器并且负责指定的槽。

独立功能的实现

这部分其实涵盖了内容的发布和订阅、事务、lua脚本、排序(用的就是快排)、二进制位数组(本质上就是字节数组,没啥好说的)、慢查询日志(链表)和监视器。

事务

事务的四大特性,看看Redis是如何实现的:

  • 原子性:由于Redis中是通过一个事务列表来保存所有的命令,最后一次执行的,所以具有原子性。但是Redis本身是不支持事务回滚的,作者的观点是要简单高效。
  • 一致性:
    • 命令在进入事务队列的时候就出错了,那么就不会执行,所以数据肯定是一致的。
    • 命令在执行的时候搓了,服务器可以进行对应的错误处理(告知客户),出错的命令是不会对数据库进行任何修改的,所以不会对事务的一致性产生影响。我个人理解,书里这么写是有问题的,那我如果对一个客户加100元钱正确执行了,扣100元的执行错误了,你跟我说一致性没问题吗?
    • 服务器停机。如果是什么措施都没有的,那新的数据库是空的,所以数据是一致的(????我理解不能),如果是RDB模式,算了书里真的是完全颠覆了我的三观…..
  • 隔离性:这个最好理解,单线程,肯定没人干扰,绝对隔离。
  • 耐久性:这个主要是看你对Redis的设置。

作者认为,ACID中只有耐久性Redis是需要看配置来决定是否满足的,其它三个都满足。我个人认为,它仅仅满足了隔离性,耐久性看配置,原子性和一致性压根没满足,因为它允许其中的一条命令失败。