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的编码来保存。

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),其次是不用担心缓冲区溢出,再来就是可以有效减少内存分配的次数,最后就是可以有效的存储二进制数据。

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

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

###哈希对象底层结构

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

ziplist

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

image-20200622213138371

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

image-20200622213212343

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

对于每一个entryX,都记录了它前一个节点的长度,所以我们可以很轻松的通过指针减,从zltail开始不断往前遍历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之前的——即使用的是头插法而不是尾插法。

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来指定的。

这个数据结构要弄清楚的就是升级和降级,升级就是原来存的每一个元素都是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数据库。现实中碰到的一个问题是复制可能需要的量太大了(毕竟从磁盘到内存的速度肯定是远远大于你在网络中传输的速度),这个需要额外使用一个缓存区,这样当一个服务器掉线的时候,服务器只需要把该服务器掉线之后的那些命令发送给它就能实现同步了。

sentinel

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

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

集群

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

独立功能的实现

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

事务

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

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

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