Redis主要数据类型的底层实现

本文使用的Redis服务端和客户端版本如下：


shell复制代码
$ redis-server -v
Redis server v=7.0.0 sha=00000000:0 malloc=libc bits=64 build=9b921e455b2f5c37
$ redis-cli -v
redis-cli 7.0.0

Redis的几个主要的数据类型是string（字符串）、hash（哈希）、list（列表）、set（集合）、sorted set（排序集合）。string的底层数据结构主要是简单动态字符串（SDS），hash的底层数据结构是listpack或hashtable（数组+链表），list的底层数据结构是quicklist（双向链表+listpack的组合），set的底层数据结构是intset或者hashtable，sorted set的底层数据结构是listpack或者skiplist。

可以在《Redis入门》一文中了解Redis的安装和基础指令。

Redis源码地址：github.com/redis/redis…

这篇文章是对后面这个视频的学习笔记：www.bilibili.com/video/BV13R…

执行以下指令在后台启动Redis服务：


shell复制代码
$  redis-server --daemonize yes

执行以下指令进入和Redis的交互模式：


shell复制代码
$ redis-cli

string（字符串）

string的编码类型有int、embstr、raw三种类型，其中raw和embstr类型对应的底层数据结构都是简单动态字符串（SDS）。一个字符串最大为512M。Redis中的所有键都是由字符串实现的。

int

int保存的是long型的64位有符号整数。只有整数才会使用int，如果是浮点数，Redis内部先将浮点数转换为字符串值，然后再保存。

long型（长整型）的最小值是 $-2^{63}$ ，最大值是 $2^{63}-1$ 。
embstr

embedded string，表示嵌入式的string，底层数据结构是SDS（Simple Dynamic String，简单动态字符串），保存长度小于44字节的字符串。
raw

保存长度大于44字节的字符串。


redis复制代码
127.0.0.1:6379> set k1 100
OK
127.0.0.1:6379> type k1
string
127.0.0.1:6379> object encoding k1
"int"
127.0.0.1:6379> set k2 abc
OK
127.0.0.1:6379> object encoding k2
"embstr"
127.0.0.1:6379> set k3 1.12
OK
127.0.0.1:6379> object encoding k3
"embstr"
127.0.0.1:6379> set k4 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> object encoding k4
"raw"

SDS


c复制代码
/* sds.h */
struct __attribute__ ((__packed__)) sdshdr8 {
    uint8_t len; /* used，当前字符数组的长度 */
    uint8_t alloc; /* excluding the header and null terminator，当前字符数组总共分配的内存大小 */
    unsigned char flags; /* 3 lsb of type, 5 unused bits，当前字符串数组的属性，比如sdshdr5, sdshdr6等 */
    char buf[]; /*字符串真正的值*/
};

SDS有不同的结构，用于存储不同长度的字符串。比如sdshdr8， $2^8=256$ Byte，指数的值可以为5、8、16、32、64。

C语言中已经有一个字符串，重新设计SDS数据结构的原因如下：

字符串长度处理

C语言字符串用'\0'标记字符串的结尾，如果要知道字符串的长度，需要从头遍历，直到遇到'\0'为止，时间复杂度为 $O(n)$ 。

SDS记录了当前字符串的长度，直接读取即可，时间复杂度为 $O(1)$ 。
内存重新分配

C语言字符串分配内存空间超过后，会导致数组下标越界或内存分配溢出。

SDS使用空间预分配和惰性空间释放解决C语言字符串存在的问题：
- 空间预分配
  
  SDS修改后，len长度小于1M，那么将会额外分配与len相同长度的未使用空间。如果修改后长度大于1M，那么将会额外分配1M的使用空间。
- 惰性空间释放
  
  SDS缩短时，并不会回收多余的内存空间，而是将多出来的空间记录下来，如果后续有变更操作，直接使用记录好的空间，减少内存的分配。
二进制安全

C语言字符串中，可能会包含一些特殊的字符，比如'\0'等。C中字符串遇到了'\0'就会结束，'\0'之后的数据就读取不上了。

SDS根据len的长度来判断字符串结束，解决了二进制安全问题。

hash（哈希）

hash的底层数据结构为listpack（紧凑列表）或者hashtable（哈希表）。


redis复制代码
127.0.0.1:6379> config get hash*
1) "hash-max-listpack-value"
2) "64"
3) "hash-max-ziplist-value"
4) "64"
5) "hash-max-listpack-entries"
6) "512"
7) "hash-max-ziplist-entries"
8) "512"

hash-max-listpack-value：使用紧凑列表保存时哈希集合中单个元素的最大字节数。
hash-max-listpack-entries：使用紧凑列表保存时哈希集合中的最大元素个数。

hash类型的键的字段个数小于hash-max-listpack-entries，并且每个字段名和字段值的长度小于hash-max-listpack-value时，Redis使用listpack来存储hash值，否则会使用hashtable来存储值。


redis复制代码
127.0.0.1:6379> hmset user:1000 name momo grade 6 class 1
OK
127.0.0.1:6379> type user:1000
hash
127.0.0.1:6379> object encoding user:1000
"listpack"
127.0.0.1:6379> hmset user:1001 name aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
OK
127.0.0.1:6379> object encoding user:1001
"hashtable"

在说listpack之前，先了解一下ziplist（压缩列表），在Redis6的时候，hash类型在元素个数较少，以及值的字节长度较小的时候底层数据结构就是ziplist。ziplist是一个经过特殊编码的双向链表，它为了节省内存，不像一般的双向链表一样存储指向前一个链表节点的指针和指向后一个链表节点的指针，而是存储上一个节点的长度和当前节点的长度。ziplist是连续存储的，通过节点存储的长度来推算下一个节点在什么位置。

ziplist有一个很大的缺点，就是在新增元素或者更新元素的时候，可能会导致连锁更新。

prevlen有两种取值情况，1字节或者5字节，当上一个节点的长度小于254字节时，prevlen属性会占用1字节空间，否则会占用5字节空间。当前地址加上当前entry的长度，就能得到下一个节点的地址。

假设列表中所有节点都小于254字节，当节点长度变为大于254字节或者新增了一个大于254字节的节点时，后续所有节点的prevlen都要从1字节变为5字节，这就是连锁更新，需要重新进行内存分配。例如下图中新增了大于254字节的节点entryNew后，从entry2到entryN全部都要进行新的内存分配。

listpack

因为ziplist存在连锁更新的问题，所以Redis7中的hash使用listpack作为底层数据结构。

listpack的元素与ziplist不同的是，不再保存前一个列表项的长度，而是保存当前数据项的一个总长度，解决了连锁更新的问题。

list（列表）

list的底层数据结构是quicklist。


redis复制代码
127.0.0.1:6379> lpush alist a b c
(integer) 3
127.0.0.1:6379> type alist
list
127.0.0.1:6379> object encoding alist
"quicklist"

查看list相关配置项：


redis复制代码
127.0.0.1:6379> config get list*
1) "list-compress-depth"
2) "0"
3) "list-max-listpack-size"
4) "-2"
5) "list-max-ziplist-size"
6) "-2"

list-compress-depth，压缩配置

表示一个quicklist两端不被压缩的节点个数。
- 0：特殊值，表示都不压缩。这是Redis的默认值
- 1：表示quicklist两端各有1各节点不压缩，中间的节点压缩。
- 2：表示quicklist两端各有2各节点不压缩，中间的节点压缩。
- 依此类推。
list-max-listpack-size，是对每个quicklist上的listpack长度的限制。比如参数设置为5的时候，表示每个quicklist节点的listpack最多包含5个数据项。取负值的时候，表示按照占用字节数来限定每个quicklist的listpack长度，它只能取-1到-5这5个值。

-5对应64KB，-4对应32KB，-3对应16KB，-2对应8KB，-1对应4KB。

quicklist就是双向链表+listpack的组合，它结合了双端链表修改效率高和listpack查询效率高的优点：

Redis6中使用的是双向链表+ziplist。

set (集合)

set的底层数据结构是intset或者hashtable。


redis复制代码
127.0.0.1:6379> config get set*
1) "set-proc-title"
2) "yes"
3) "set-max-intset-entries"
4) "512"

如果元素都是整数，并且元素个数不超过set-max-intset-entries，就用intset（整数数组）类型存储，否则就用hashtable（数组+链表）存储。


redis复制代码
127.0.0.1:6379> sadd aset 1 2 3
(integer) 3
127.0.0.1:6379> type aset
set
127.0.0.1:6379> object encoding aset
"intset"
127.0.0.1:6379> sadd bset a b c
(integer) 3
127.0.0.1:6379> object encoding bset
"hashtable"

zset（排序集合）

zset的底层数据结构是listpack或skiplist。


redis复制代码
127.0.0.1:6379> config get zset*
1) "zset-max-ziplist-entries"
2) "128"
3) "zset-max-listpack-entries"
4) "128"
5) "zset-max-listpack-value"
6) "64"
7) "zset-max-ziplist-value"
8) "64"

当有序集合中包含的元素个数超过zset-max-listpack-entries，或者有序集合中新添加元素的长度大于zset-max-ziplist-value时，就使用跳跃表作为底层实现，否则使用listpack作为底层实现。


redis复制代码
127.0.0.1:6379> config set zset-max-listpack-entries 3
OK
127.0.0.1:6379> zadd azset 10 a 5 b
(integer) 2
127.0.0.1:6379> type azset
zset
127.0.0.1:6379> object encoding azset
"listpack"
127.0.0.1:6379> zadd azset 20 c
(integer) 1
127.0.0.1:6379> object encoding azset
"listpack"
127.0.0.1:6379> zadd azset 30 d
(integer) 1
127.0.0.1:6379>  object encoding azset
"skiplist"