浅谈Redis五种数据结构的底层原理

淡淡的烟草味﹌ 2021-12-09 04:37 307阅读 0赞

**概念**

Redis作为一个开源的用C编写的非关系型数据库，基于优秀的CRUD效率，常用于软件系统的缓存，其本身提供了以下五种数据格式：

> 1、string：字符串
> 
> 2、list：列表
> 
> 3、hash：散列表
> 
> 4、set：无序集合
> 
> 5、zset：有序集合

接下来我们就要针对这五种数据结构，来分析其底层的结构

这里选用的版本是redis-5.0.4，所以可能有很多地方和如今网络上的其他博文不太一致，不同的地方我会在文中指出

**string**

因为redis使用c语言开发，所以自然没有java和c++的那些字符串类库，在redis中，其自己定义了一种字符串格式，叫做SDS（Simple Dynamic String），即简单动态字符串

这个结构定义在sds.h中：

> typedefchar\*sds;

但是这个sds类型仅作为参数和返回值使用，并不是真正用于操作的类型，真正核心的部分是下面的这些类：

> struct\_\_attribute\_\_((\_\_packed\_\_))sdshdr5\{
> 
> unsignedcharflags;
> 
> charbuf\[\];
> 
> \};
> 
> struct\_\_attribute\_\_((\_\_packed\_\_))sdshdr8\{
> 
> uint8\_tlen;uint8\_talloc;
> 
> unsignedcharflags;
> 
> charbuf\[\];
> 
> \};
> 
> struct\_\_attribute\_\_((\_\_packed\_\_))sdshdr16\{
> 
> uint16\_tlen;
> 
> uint16\_talloc;
> 
> unsignedcharflags;
> 
> charbuf\[\];
> 
> \};
> 
> struct\_\_attribute\_\_((\_\_packed\_\_))sdshdr32\{
> 
> uint32\_tlen;uint32\_talloc;
> 
> unsignedcharflags;
> 
> charbuf\[\];
> 
> \};
> 
> struct\_\_attribute\_\_((\_\_packed\_\_))sdshdr64\{
> 
> uint64\_tlen;
> 
> uint64\_talloc;
> 
> unsignedcharflags;
> 
> charbuf\[\];
> 
> \};

除掉第一个结构体（已经弃用），sds具体类型的结构可以分为以下部分：

> 1、len：已使用的长度，即字符串的真实长度
> 
> 2、alloc：除去标头和终止符('\\0')后的长度
> 
> 3、flags：低3位表示字符串类型，其余5位未使用（我暂时没发现redis在哪里使用过这个属性）
> 
> 4、buf\[\]：存储字符数据

这里和老版本做一下对比，因为我手头只有4.x和5.x的版本，它们sds的实现是一致的，但是据其他人说sds之前的版本实现方式不同，有时间我会去下载下来看一下，其将字符串分为以下部分：

> 1、len：buf中已经占有的长度（表示此字符串的实际长度）
> 
> 2、free：buf中未使用的缓冲区长度
> 
> 3、buf\[\]：实际保存字符串数据的地方

redis同时写重写了大量的与sds类型相关的方法，那redis为什么要这么下功夫呢，有以下4个优点：

> 1、降低获取字符串长度的时间复杂度到O(1)
> 
> 2、减少了修改字符串时的内存重分配次数
> 
> 3、兼容c字符串的同时，提高了一些字符串工具方法的效率
> 
> 4、二进制安全（数据写入的格式和读取的格式一致）

**list**

我们查看源文件可以看到有两个list，一个是ziplist，字面意是压缩列表，另一个是quicklist，字面意是快速列表，在redis中直接使用的是quicklist，但是我们先来看ziplist

**ziplist**

ziplist并不是一个类名，其结构是下面这样的： <zlbytes><zltail><entries><entry>...<entry><zlend>

其中各部分代表的含义如下：

> 1、zlbytes：4个字节（32bits），表示ziplist占用的总字节数
> 
> 2、zltail：4个字节（32bits），表示ziplist中最后一个节点在ziplist中的偏移字节数
> 
> 3、entries：2个字节（16bits），表示ziplist中的元素数
> 
> 4、entry：长度不定，表示ziplist中的数据
> 
> 5、zlend：1个字节（8bits），表示结束标记，这个值固定为ff（255）

这些数据均为小端存储，所以可能有些人查看数据的二进制流与其含义对应不上，其实是因为读数据的方式错了

ziplist内部采取数据压缩的方式进行存储，压缩方式就不是重点了，我们仅从宏观来看，ziplist类似一个封装的数组，通过zltail可以方便地进行追加和删除尾部数据、使用entries可以方便地计算长度

但是其依然有数组的缺点，就是当插入和删除数据时会频繁地引起数据移动，所以就引出了quicklist数据类型

**quicklist**

其核心数据结构如下：

> typedef struct quicklist\{
> 
> quicklistNode \*head;
> 
> quicklistNode \*tail;unsignedlongcount;
> 
> /\* ziplist所有节点的个数 \*/unsignedlonglen;
> 
> /\* quicklistNode节点的个数 \*/intfill :16;
> 
> /\* 单个节点的填充因子 \*/unsignedintcompress :16;
> 
> /\* 压缩端结点的深度 \*/
> 
> \}
> 
> quicklist;

我们可以明显地看出，quicklist是一个双向链表的结构，但是内部又涉及了ziplist，我们可以这么说，在宏观上，quicklist是一个双向链表，在微观上，每一个quicklist的节点都是一个ziplist

在redis.conf中，可以使用下面两个参数来进行优化：

> list-max-ziplist-size：表示每个quicklistNode的字节大小。默认为2，表示8KB
> 
> list-compress-depth：表示quicklistNode节点是否要压缩。默认为0，表示不压缩

这种存储方式的优点和链表的优点一致，就是插入和删除的效率很高，而链表查询的效率又由ziplist来进行弥补，所以quicklist就成为了list数据结构的首选

**hash**

hash这种结构在redis的使用时最为常见，在redis中，hash这种结构有两种表示：zipmap和dict

**zipmap**

zipmap其格式形如下面这样： <zmlen><len>"foo"<len><free>"bar"<len>"hello"<len><free>"world"

各部分的含义如下：

> 1、zmlen：1个字节，表示zipmap的总字节数
> 
> 2、len：1~5个字节，表示接下来存储的字符串长度
> 
> f3、ree：1个字节，是一个无符号的8位数，表示字符串后面的空闲未使用字节数，由于修改与键对应的值而产生

这其中相邻的两个字符串就分别是键和值，比如在上面的例子中，就表示"foo" => "bar", "hello" => "world"这样的对应关系

这种方式的缺点也很明显，就是查找的时间复杂度为O(n)，所以只能当作一个轻量级的hashmap来使用

**dict**

这种方式就适于存储大规模的数据，其格式如下：

> typedef struct dict\{
> 
> dictType \*type;
> 
> /\* 指向自定义类型的指针，可以存储各类型数据 \*/void\*privdata;
> 
> /\* 私有数据的指针 \*/dictht ht\[2\];
> 
> /\* 两个hash表，一般只有h\[0\]有效，h1\[1\]只在rehash的时候才有值 \*/longrehashidx;
> 
> /\* -1：没有在rehash的过程中，大于等于0：表示执行rehash到第几步 \*/unsignedlongiterators;
> 
> /\* 正在遍历的迭代器个数 \*/
> 
> \}
> 
> dict;

如果我们不想更深入的话了解到这种程度就可以了，其中真正存储数据的是dictEntry结构，如下：

> typedef struct dictEntry\{
> 
> void\*key;
> 
> union\{
> 
> void\*val;
> 
> uint64\_tu64;
> 
> int64\_ts64;
> 
> doubled;
> 
> \}
> 
> v;
> 
> structdictEntry\*next;
> 
> \}
> 
> dictEntry;

很明显是一个链表，我们知道这是采用链式结构存储就足够了

这种方式会消耗较多的内存，所以一般数据较少时会采用轻量级的zipmap

**set**

在redis中，我们可以查看intset.h文件，这是一个存储整数的集合，其结构如下：

typedefstructintset\{uint32\_tencoding;uint32\_tlength;int8\_tcontents\[\];\} intset;

其中各字段含义如下：

> 1、encoding：数据编码格式，表示每个数据元素用几个字节存储（可取的值有2、4，和8）
> 
> 2、length：元素个数
> 
> 3、contents：柔性数组，这部分内存单独分配，不包含在intset中

具体的操作我们就不详细展开了，了解集合这种数据结构的应该都很清楚，我们这里说一下，intset有一个数据升级的概念，比方说我们有一个16位整数的set，这时候插入了一个32位整数，所以就导致整个集合都升级为32位整数，但是反过来却不行，这也就是柔性数组的由来

如果集合过大，会采用dict的方式来进行存储

**zset**

zset，有很多地方也叫做sorted set，是一个键值对的结构，其键被称为member，也就是集合元素（zset依然是set，所以member不能相同），其对应的值被称为score，是一个浮点数，可以理解为优先级，用于排列zset的顺序

其也有两种存储方式，一种是ziplist/zipmap的格式，这种方式我们就不过多介绍了，只需要了解这种格式将数据按照score的顺序排列即可