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

terry 2年前 (2023-09-26) 阅读数 83 #数据库

Redis 是一个用 C 语言编写的开源非关系型数据库，基于优异的 CRUD 效率，常用于软件系统中的缓存。它本身给出了以下五种数据格式：

string：字符串
list：列表
hash：哈希表
set：无序集合
list：我们设置order order：这五种数据结构。分析一下它的底层结构
这里选择的版本是redis-5.0.4，所以可能有很多地方和今天网上其他博文不符。我会在文章中指出不同之处
string
因为redis是使用c语言开发的，所以显然没有java和c++的字符串库。在redis中，它定义了自己的字符串格式，称为SDS（Simple Dynamic String），即简单动态字符串
这个结构体在sds.h中定义：
```
typedef char *sds;
```
但是，这个sds类型只是作为参数使用，返回value，并不是真正用于操作的类型。实际的核心部分是以下几个类：
```
struct __attribute__ ((__packed__)) sdshdr5 {
   unsigned char flags; 
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
   uint8_t len; 
   uint8_t alloc; 
   unsigned char flags; 
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
   uint16_t len;
   uint16_t alloc; 
   unsigned char flags;
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
   uint32_t len;
   uint32_t alloc; 
   unsigned char flags; 
   char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
   uint64_t len; 
   uint64_t alloc;
   unsigned char flags; 
   char buf[];
};
```
除了第一个结构（已经过时）之外，具体 sds 类型的结构可以分为以下几个部分：
- len：使用的长度，即字符串的实际长度
- alloc：去掉头部和终止符（'\0'之后的长度）
- flag：低 3 位代表字符串类型，其余 5 位未使用（我没有'还没找到redis哪里用过这个属性）
- buf[]：保存字符数据
这里是和旧版本的对比，因为我只有4版本，下载下来看看。它将字符串拆分为以下部分：
- len：buf 中已经占用的长度（表示该字符串的实际长度）
- free：buf 中未使用的缓冲区 Length
- buf[]：字符串所在的位置数据实际上是保存的
redis同时写入和重写大量与sds类型相关的方法。那么萝卜为什么要花这么大的功夫呢？它有以下 4 个优点：
- 将获取字符串长度的时间复杂度降低到 O(1)
- 减少更改字符串时重新分配内存的次数
- 在兼容 C 字符串的同时，还提高了一些字符串实用方法的效率
- 二进制安全性（数据写入格式符合读取格式）
list
查看源文件，我们可以看到有两个列表。一个是ziplist，字面意思是压缩列表，另一个是quicklist，字面意思是快速列表。 Quicklist在redis中直接使用，不过首先我们看一下ziplist
ziplist
ziplist不是类名。其结构如下： ...
各部分代表的含义如下：
- zlbytes: 4 个字节 ( 32bits ）表示ziplist占用的总字节数
- zltail：4个字节（32bits）表示ziplist中最后一个节点在ziplist中的偏移量字节数
- post：2个字节（16bits）表示ziplist 中的项目数
- entry：可变长度，表示 ziplist 中的数据
- zlend：1 个字节（8bits）表示结束标记，该值固定为 ff（255）
此数据为全部小端存储，因此有些人可能无法将二进制数据流与其含义相匹配。其实是因为读取数据的方式不对
内部ziplist采用了数据压缩来存储。压缩方法不是重点。从宏观角度来看，ziplist 看起来就像一个嵌套数组。通过zltail可以方便的添加和删除尾部数据，并且使用input可以方便的计算长度
但是它还是有数组的缺点，就是在插入和删除数据的时候，往往会造成数据的移动，所以引入了快速列表数据类型
quicklist
它的核心数据结构如下：
```
typedef struct quicklist {
   quicklistNode *head;
   quicklistNode *tail;
   unsigned long count;        /* ziplist所有节点的个数 */
   unsigned long len;          /* quicklistNode节点的个数 */
   int fill : 16;              /* 单个节点的填充因子 */
   unsigned int compress : 16; /* 压缩端结点的深度 */
} quicklist;
```
我们可以清楚地看到quicklist是一个双向链表结构，但内部也涉及到ziplist。可以说，宏观层面上quicklist是一个双向链表，微观层面上每个quicklist节点是一个ziplist
在redis.conf中可以使用以下两个参数进行优化：
- list-max-ziplist -size：指定每个quicklistNode的字节大小。默认为2，即8KB
- list-compress-深度：指定是否压缩quicklistNode节点。默认为0，表示不压缩
这种存储方式的优点和链表一样，即。插入和删除的效率非常高，而链表查询的效率是通过ziplist构建的，所以quicklist就变成了列表数据。所选择的结构
hash
hash是使用redis时最常见的结构。在redis中，哈希结构有两种表示：zipmap和dictzipmap
zipmap。它的格式如下： "foo""bar""hello""world"
The各部分含义如下：
- zmlen：1 个字节，表示 zipmap 的总字节数
- len：1~5 个字节，表示接下来存储的字符串长度
- free：1 个字节无符号8位，表示字符串后面空闲未使用的字节数，通过改变key对应的值生成
相邻的两个字符串分别是key和value，如上例，表示“foo”=>“bar”，“hello”=>“world”这样的对应关系
这种方法的缺点也很明显，就是搜索的时间复杂度为O(n) ，所以只能作为轻量级的hashmap
dict
该方法适合大规模存储数据。其格式如下：
```
typedef struct dict {
   dictType *type;/* 指向自定义类型的指针，可以存储各类型数据 */
   void *privdata; /* 私有数据的指针 */
   dictht ht[2];/* 两个hash表，一般只有h[0]有效，h1[1]只在rehash的时候才有值 */
   long rehashidx; /* -1：没有在rehash的过程中，大于等于0：表示执行rehash到第几步 */
   unsigned long iterators; /* 正在遍历的迭代器个数 */
} dict;
```
如果不想深入的话，了解这一层就够了。真正存储数据的是dictEntry结构体，如下：
```
typedef struct dictEntry {
   void *key;
   union {
       void *val;
       uint64_t u64;
       int64_t s64;
       double d;
  } v;
   struct dictEntry *next;
} dictEntry;
```
很明显，它是一个链表。我们知道用链式结构存储就够了
这种方式会消耗较多的内存，所以一般数据较少的时候会使用轻量级的zipmap
set
在redis中我们可以看到intset.h 文件，它是存储整数的集合。其结构如下：
```
typedef struct intset {
   uint32_t encoding;
   uint32_t length;
   int8_t contents[];
} intset;
```
各个字段的含义如下：
- encoding：表示每个数据元素的数据编码格式，以多个字节存储（可用值有2、4和8）
- length：元素数量
- content：灵活数组，这部分内存是单独分配的，不包含在intset中
具体操作我们就不细说了。了解集合数据结构的人应该很清楚。我们来谈谈这个吧。 Intset有一个数据升级的概念。例如，我们有一组 16 位整数。此时，我们插入一个32位整数，以便整个集合升级为32位整数，但反之则不然。这就是灵活数组的由来
如果集合太大，就会存储在dict中。