redis存储结构及常用类型底层结构

redis底层结构及常用命令数据结构分析

33A11

5040人浏览 · 2022-04-04 20:09:19

33A11 · 2022-04-04 20:09:19 发布

Redis 数据类型底层结构

1 前言

本文将在熟悉使用redis的基本数据结构的基础上，对redis的五种数据类型底层结构进行分析。本次基于redis-3.2.1版本。后续所有讲解如不做特殊说明，都是基于此版本。

2 redis数据库的存储结构

2.1 引言

在了解redis的数据结构原理时，有必要先了解Redis的数据存储结构。redis是一种使用K-V形式做数据存储的数据库。正如Mysql底层使用B+来维护索引和数据的对应关系。redis则使用hash表存储K-V数据(C源码中也叫字典dict)。

我们知道，hash表是一种O(1)时间复杂度的数据结构。其底层是基于数组结构; redis中将hash表中的每一个元素都封装成了entry对象，其对象中保存了实际的key-Value数据。其结构如下所示：

![(E:\java_study\redis\底层数据结构\hashtable结构.png)
说到这里，我们已经明白redis数据库是使用hash表来存储的，那么redis底层又是如何对redisDB和hashtable进行封装的呢？

2.2 redis数据库的底层结构分析

redisDb

/* Redis database representation. There are multiple databases identified
 * by integers from 0 (the default database) up to the max configured
 * database. The database number is the 'id' field in the structure. */
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */  //字典对象
    dict *expires;              /* Timeout of keys with a timeout set */  //过期时间
    //用于list类型的阻塞操作
    dict *blocking_keys;        /* Keys with clients waiting for data (BLPOP) */ 
    //用于list类型的阻塞操作
    dict *ready_keys;           /* Blocked keys that received a PUSH */ 
    dict *watched_keys;         /* WATCHED keys for MULTI/EXEC CAS */
    struct evictionPoolEntry *eviction_pool;    /* Eviction pool of keys */
    int id;                     /* Database ID */
    PORT_LONGLONG avg_ttl;          /* Average TTL, just for stats */
} redisDb;

上图为redis源码中对其DB库中定义数据类型和字段。可以看出在dictEntry结构体中有一个字典类型字段dictEntry，该字段就是redis存放K-V数据的hashtable。我们进入到dict类型中查看。

dict

typedef struct dict {
    dictType *type;  //存储了一下hashtable的函数操作，包括对key的hash以及比较key的函数等
    void *privdata;
    dictht ht[2];    //两个字典对象，其中ht[1]的内存是ht[0]的两倍，用于渐进式rehash使用
    //记录rehash 进度的标志，值为-1表示rehash未进行
    PORT_LONG rehashidx; /* rehashing not in progress if rehashidx == -1 */ 
    int iterators; /* number of iterators currently running */
} dict;

上图为redis中hashtable具体的数据结构。各个字段都已标注注释。其中最为重要的两个字段分别是dictht ht[2]和rehashidx。其中字段ht便是redis的hashtable。至于为什么是两个ht以及rehashidx字段，都是为了渐进式rehash做准备。该部分将在下面详细讲解

dictht

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table;   //hash表
    PORT_ULONG size;  //hash表大小
    PORT_ULONG sizemask;  // 等于size - 1;会用于后续与hash一起确定该数据存放的索引位
    PORT_ULONG used;  //hash表中已使用的大小
} dictht;

经过上面的分析，我们已经明白了字段ht就是redis中的hastable.我们进一步跟进到dictht 这个结构体中。结构如上图。可以明显的看到。redis的hashtable对象中定义了一个 dictEntry对象，到这里我们就豁然开朗了，和我们认知的hashtable结构一致。因此，我们可以大胆猜测，dictEntry字段一定定义了我们的key和value字段。我们进入到dictEntry字段查看。

dictEntry

typedef struct dictEntry {
    void *key;   //redis的key 封装为SDS
    union {
        void *val;     //value, 指向底层数据结构
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;  //hash冲突时指向下一个数据节点
} dictEntry;

从图中可以看出，dictEntry字段定了我们存入的key字段和value字段。

redisObject

typedef struct redisObject {
    unsigned type:4;  //记录了该对象的类型
    unsigned encoding:4;  //表示ptr指针指向的具体使用到的数据结构
    unsigned lru:LRU_BITS; /* lru time (relative to server.lruclock) */ //对象最后一次被访问的时间
    int refcount; // 引用计数
    void *ptr;  //指向实际值的指针
} robj;

redisObject是redis中封装value的对象，其每个存入到redis中的value都会被封装成redisObject对象保存；其内存也包含了五个字段：

1、type：用于表示该对象的类型，其包含了string、list、hash、set、zset等；

2、encoding：表示ptr指针指向的具体使用到的数据结构，也就是value用什么底层数据类型存储的；

3、lru：对象最后一次被访问的时间，用户后续的过期策略；

4、refcount：引用计数器；表明了redis中的垃圾回收算法是使用了引用计数法完成的；因C语言中不存在

5、ptr指针：指向实际保存数据的底层结构对象；

那么问题来了：我们在学习JVM的时候已经知道了，引用计数法这种垃圾回收机制虽然效率很高，但是不能解决循环依赖的问题，因此可能会导致内存泄漏，那么为什么redis还要使用这种gc算法呢？

从上面的对redis的结构分析可知，redis中每个key-value都对应这一个底层数据结构来维护，所以就不会出现循环引用的情况了；

2.3 总结

通过上面层层递进的结构体类型，我们对redis的底层数据库的结构已经有了深刻的认识。下面对着四种结构体进行总结归纳。

redisDb ：redis的顶层数据库结构，内部定义了数据存储结构字典dict，过期时间、用于阻塞key以及事务相关的监听。
dict ：用于存储redis中的k-v数据的字段结构。其中定义了两个hashtable和rehash下标值。
dictht ： redis中真正的hash表，二维数组结构，内部定义了存储k-v的entry、数组长度、确定数据存放位置的模、数组内的数据量。
dictEntry ：用于存储k-v数据的entry对象，内部封装了key、value字段，以及用于处理hash冲突的指针。
redisObject：用于封装value数字的对象；其内部包含了value的命令类型、底层存储结构、回收策略、lru信息等；

我们可以用下图清晰的描述各个结构体的包含关系
在这里插入图片描述

3 redis中的hash冲突

到此为止，redis底层的数据库结构我们已经了解了。于此同时也存在了一些困惑，只要使用hash，就一定会存在hash冲突，因此又引入了另一个话题：redis是如何解决hash冲突的呢。他和java中的hashMap的处理方式是否一样呢？下面我们一起来探讨。

通过上面对redis护具库结构的分析，我们可以发现在dictEntry结构体中定义了next字段并且还是一个dictEntry类型的指针。以此可以得出redis是采用了拉链法来解决hash冲突。

但是读过hashMap源码的同学应该知道，hashMap解决hash冲突的方式也是拉链法，但是当同一分支hash冲突过多，就会导致生成的链表数据过长，从而使查询效率下降，hashMap中当链表长度超过8时就会装换为红黑树来增加查询效率。那么redis作为高效的查存数据库，是如何解决拉链法导致的查询效率下降的呢？

3.1 incremental rehashing——渐进式rehash

在经过对redis底层的数据库结构梳理后，可以发现在dict结构体中定义了两个hashtable。所以redis是通过渐进式rehash来解决解决链表过长带来的问题。

当第一个hashtable中的元素数量达到了其容量时，redis会生成比当前hashtab容量大1倍的新hashtable，然后把旧的hashtable中的数据转移到新的hashtable里，当旧数据全部迁移完毕后，旧hashtable内存将会释放，使用新的hashtable。在数据未全部迁移到新hashtable前，每次查询查询都会优先从旧的hashtable中获取。

但是由于redis在增删改查时时单线程处理，如果一次性全部rehash到新的hashtable中，但是数据量很大时，可能会阻塞主线程。因此redis采用了渐进式的rehash迁移。也即在每次读命令操作时，就会对当前的hash桶进行rehash迁移，直到旧的hashtable中无数据。这次会将dictht[0]内存释放。
在这里插入图片描述
值得注意的是，当redis进行rehash时由于会重新申请一块内存区域，所以在这段时间内，redis内存占比可能会明显增加。但是当rehash结束后，内存则会恢复到平均水位。

4 redis底层数据结构

下面汇总了redis底层现有在使用的底层数据结构

SDS	简单动态字段串
hashtable	基于hash桶结构
intlist	整形数组
ziplist	压缩列表；对双向链表的改造，减少内存开销
quicklist	快速列表；基于zipList的改造，减少zipList插入带来的性能问题
skiplist	跳表；基于双向链表二分查找思想，建立多索引来增加检索效率

4.1 SDS

SDS是redis设计的一种保存字符串的数据结构，其内部结构定义如下图所示：
在这里插入图片描述

可以很明显的看到，sds已经记录了所存储的字符串长度大小，并且使用可扩容字符数组存储字符串；SDS相对于原有C中的字符串有哪些优势呢？

1、效率高

C中要获取字符串的长度需要遍历整个字符串,时间复杂度是O(n)，而sds内部的len已经记录了字符串的长度，因此查询的时间复杂度是O(1)；

2、安全的动态扩容

C中如果想对一个字符串进行修改(增加字符串长度),那么如果不事先指定好内存大小，有可能出现内存溢出，进而可能覆盖其他的字符串数据，对数据不安全；而sds可以在修改字符串之前先进行内存预估，如果该字符串内存大小不足以保存修改后的大小，就会进行自动扩容来避免出现内存溢出的问题；同时在每次扩容是会额外预留一下内存最为预留内存，以防止频繁的修改操作

3、二进制安全

由于C中字符串都是以’\0’结尾，因此如果保存的字符串中包含字符’\0’，那么C就会自动停止检索，直接返回该字符之前的数据，造成了数据截断；但是sds中的len字段由于保存了字符串的长度，因此sds判断字符串是否结束是按照len的大小判断的；所以对二进制数据是安全的；

4.2 hashtable

hashtable的底层实现我们已经较为熟悉，正如2.2节所示；并且关于使用hashtable可能会出现的hash冲突以及redis中的解决方案也已经详细说明；

4.3 intlist(整形数组)

整形数组在redis中使用的场景较少，只有set的数据类型中可能会使用到；该数据类型特点就是只能存储整形数据，同时redis中使用的整形数组会自动进行递增排序处理。

4.4 ziplist

ziplist数据结构是redis在linklist的基础上进行了改进，将双端指针改为使用数组存储，大大节省了内存开销；下面这段话为redis源码中对ziplist的介绍：

/* The ziplist is a specially encoded dually linked list that is designed
 * to be very memory efficient. It stores both strings and integer values,
 * where integers are encoded as actual integers instead of a series of
 * characters. It allows push and pop operations on either side of the list
 * in O(1) time. However, because every operation requires a reallocation of
 * the memory used by the ziplist, the actual complexity is related to the
 * amount of memory used by the ziplist.
 *
 * ----------------------------------------------------------------------------
 *
 * ZIPLIST OVERALL LAYOUT:
 * The general layout of the ziplist is as follows:
 * <zlbytes><zltail><zllen><entry><entry><zlend>
 *
 * <zlbytes> is an unsigned integer to hold the number of bytes that the
 * ziplist occupies. This value needs to be stored to be able to resize the
 * entire structure without the need to traverse it first.
 *
 * <zltail> is the offset to the last entry in the list. This allows a pop
 * operation on the far side of the list without the need for full traversal.
 *
 * <zllen> is the number of entries.When this value is larger than 2**16-2,
 * we need to traverse the entire list to know how many items it holds.
 *
 * <zlend> is a single byte special value, equal to 255, which indicates the
 * end of the list.

从上面我们可以看出，ziplist是一种经过特殊编码的双链表，其非常节省内存。同时他可以存储字符串和整形数据；可以以O(1)的时间复杂度完成任一侧的push和pop操作；

注释中给出了ziplist的完整的数据结构，因此我们就可以很清楚的了解ziplist的结构构成。
在这里插入图片描述

虽然ziplist可以很大程度上减少内存开销，但是每次对ziplist的操作都会使其重新分配内存，因此ziplist的时间复杂度和实际使用的内存大小有关。

4.5 quicklist

上一小节我们已经知道当使用list命令插入一个元素时，会在ziplist中分配该元素的内存空间，而ziplist的内存空间又是连续的，如果待插入的元素的内存较大或者ziplist的元素个数过多时，会导致ziplist内存不足，从而触发扩容并进行内存重分配，导致效率严重下降。因此redis提出了quicklist来解决ziplist的内存重分配问题。

在redis的配置文件中，可以设置ziplist的存储节点的大小，当达到存储ziplist内存大小时，就会触发quicklist的节点分裂；其配置如下：

# Lists are also encoded in a special way to save a lot of space.
# The number of entries allowed per internal list node can be specified
# as a fixed maximum size or a maximum number of elements.
# For a fixed maximum size, use -5 through -1, meaning:
# -5: max size: 64 Kb  <-- not recommended for normal workloads
# -4: max size: 32 Kb  <-- not recommended
# -3: max size: 16 Kb  <-- probably not recommended
# -2: max size: 8 Kb   <-- good
# -1: max size: 4 Kb   <-- good
# Positive numbers mean store up to _exactly_ that number of elements
# per list node.
# The highest performing option is usually -2 (8 Kb size) or -1 (4 Kb size),
# but if your use case is unique, adjust the settings as necessary.
list-max-ziplist-size -2

qiucklist数据结构就是双端链表，不同的是，其每个节点都是由ziplist组成，当ziplist的元素个数达到预设的上线时，就会分裂出一个新的ziplist，并使用双端列表关联。其结构图如下所示：
在这里插入图片描述

同时，为了更好的节省quicklist的内存消耗，redis还可以配置化的设置quicklist是否进行压缩(默认不进行压缩)，其配置如下：

# Lists may also be compressed.
# Compress depth is the number of quicklist ziplist nodes from *each* side of
# the list to *exclude* from compression.  The head and tail of the list
# are always uncompressed for fast push/pop operations.  Settings are:
# 0: disable all list compression
# 1: depth 1 means "don't start compressing until after 1 node into the list,
#    going from either the head or tail"
#    So: [head]->node->node->...->node->[tail]
#    [head], [tail] will always be uncompressed; inner nodes will compress.
# 2: [head]->[next]->node->node->...->node->[prev]->[tail]
#    2 here means: don't compress head or head->next or tail->prev or tail,
#    but compress all nodes between them.
# 3: [head]->[next]->[next]->node->node->...->node->[prev]->[prev]->[tail]
# etc.
list-compress-depth 0

值的注意的是，由于quicklist的两端都是进行会被访问到的，如果进行压缩的话会影响查询效率，所以其头尾两端是不参与压缩的；

1：表示从插入第一个节点开始进行压缩，也即压缩第一个节点；

2：不压缩头尾结点和头的下一个节点以及尾的上一个节点；也即从第2个节点和倒数第2个节点开始压缩;

3：表示从第3个节点和倒数第3个节点开始压缩;

…

n：表示从第n节点和倒数第n个节点开始压缩;

4.6 skiplist

跳表是特殊的双向链表，是redis用来解决ziplist低查询效率而设计的。其主要特点就是可以向上分裂出多级索引，从而达到快速检索的目的(其原理类似于二分查找思想)。

/* ZSETs use a specialized version of Skiplists */
//跳表节点组成
typedef struct zskiplistNode {
    robj *obj;  //元素成员 封装成redisObject对象
    double score;  //该元素成员对应的分数
    struct zskiplistNode *backward;  //后置指针
    struct zskiplistLevel {     //数组类型
        struct zskiplistNode *forward;  //指向下一个元素
        unsigned int span;   //与下一个元素的间隔
    } level[];
} zskiplistNode;

//跳表结构组成
typedef struct zskiplist {
    struct zskiplistNode *header, *tail; //头尾指针
    PORT_ULONG length;  //跳表最底层列表的节点数
    int level; //记录当前跳表最高索引层
} zskiplist;

//zset结构组成
typedef struct zset {
    dict *dict;    //字典对象  用于保存value-> score的映射关系，方便通过O(1)复杂度根据元素获取对应的分数
    zskiplist *zsl;  //跳表对象
} zset;

从redis中可以看到zset的对象结构包含了字典对象和skiplist对象。其中这个字典对象dict是为了存储value和score的映射关系的，便于以O(1)的速度根据value获取对于的score值，其对应的命令为：ZSCORE 。

再进入skiplist对象查看，发现其一共包含四个字段：

1、header、tail： ziplist的头尾指针；

2、length：记录着跳表最底层列表的节点数；

3、level：记录了当前的最高索引层；

最后我们进入到保存节点数据的zskiplistNode对象中，其结构体中包含了四个字段：

1、obj：redisObject对象类型，其保存了value值；

2、score：value对应的分数；

3、backward：后置指针，用于前一个节点；连接上一个节点的指针；

4、level数组：用于建立索引位，其内部包含了一个签字节点forward：指向后置节点；一个span字段：用于保存与后一个节点的间隔不包括当前节点），主要用于进行排名使用，eg；ZRANK 、ZREVRANK 命令
在这里插入图片描述

在redis中，跳表升级一层索引时(每次插入数据的时候)采用随机的方式，并且随着索引的层数越高进行索引升级的概率就会越小。

第一次升级索引：P1 = 0.25

第二次升级索引：P2 = （1- 0.25）* P1

第三次升级索引：P3 = （1- 0.25）* P2

第N次升级索引：P = （1- 0.25）* P(n-1)

5 redis数据类型对应的底层数据结构关系

由于本文重在讲解redis的五种数据类型的底层结构，因此对redis的相关命令还不清楚的同学可以移步该网站熟悉即可： http://redisdoc.com/

下图展示了五种常用的数据类型和Redis底层的数据结构对于关系。从图中可以看出，除了string类型外，其他的数据类型至少有两种不同的底层结构。
在这里插入图片描述
上图为redis的五种常用数据类型使用到的底层数据结构；下面将分别讲解这五种数据类型；

5.1 string

string类型是redis中最为基础的数据类型，因此其底层使用的数据结构也是最简单的一个——动态字符串(SDS);
在这里插入图片描述

1、int编码：用于存储整形数据，是以Long类型存储，未使用SDS类型；

2、embstr：用于存储小于等于32字节的字符串值，其结构使用的是SDS结构；

3、raw：用于存储大于32字节的字符串值，其结构使用的是SDS结构；

5.2 hash

hash结构底层使用到了ziplist和hashtable两种数据结构；那么满足什么条件会使用哪种数据结构呢？满足一下任意条件时都会从ziplist转为hashtable。

1、ziplist元素个数超过512个；

2、单个元素大小超过64byte；

这两个阈值在redis的配置文件中都可以设置：

# Hashes are encoded using a memory efficient data structure when they have a
# small number of entries, and the biggest entry does not exceed a given
# threshold. These thresholds can be configured using the following directives.
hash-max-ziplist-entries 512
hash-max-ziplist-value 64

在这里插入图片描述

ziplist存储特点:当使用ziplist作为存储结构时，redis将field和value当做成两个元素分别放置在ziplist数组的前后节点处。
为什么使用ziplist：由于hashtable在内存方面比ziplist要高一些(多了指针),并且内存对redis来说至关重要，所以在数据量不大的前提下，使用了内存利用率更高的ziplist结构。

5.3 list

在redis3.2之后，redis使用qiucklist代替了原来的ziplist+linkedlist结构。因此3.22版本级以后，list命令的存储结构变为了单一的qiucklist结构；

因此为了这里补充分析一下3.2版本之前的list底层结构。本次使用2.8.9版本，在其配置文件中存在对应ziplist转linkedlist的阈值配置：

# Similarly to hashes, small lists are also encoded in a special way in order
# to save a lot of space. The special representation is only used when
# you are under the following limits:
list-max-ziplist-entries 512
list-max-ziplist-value 64

1、ziplist的节点数超过512个时；

2、ziplist中存储的单个节点内存大于64字节时；

当满足上述两个条件之一，就会将ziplist结构转为linkedlist;
在这里插入图片描述

5.4 set

redis对应set命令也进行了两层数据结构存储，分别是整形数组(intlist)和hashtable。其中前者只能存储整形数据，当数据为非整形时，就会转为hashtable结构存储。

当使用intlist进行存储时，redis会自动的进行递增排序。因此，对于只存储整形的set命令，其是一个有顺序的结构。
在这里插入图片描述

如果这个时候在test_set中插入一个非整形数据，那么该结构就会转变为hashtable,并且value的顺序也是随机的。同时hashtable的存储方式和java的hashset类似，用key存储数据，而value为null
![在这里插入图片描述](https://img-blog.csdnimg.cn/3df63e082b6640198e667545b7f50d12.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBAMzNBMTE=,size_20,color_FFFFFF,t_70,g_se,x_16#pic_center

但是，并不是我们一直使用整形存储时就会始终是intlist类型，因为这种结构是数组结构，所以当元素个数过多时会影响查询效率，因此redis在配置文件中对intlist的元素个数做了限制，当达到设定的元素个数时就会自动转为hashtable存储方式。默认是512个元素个数。

# Sets have a special encoding in just one case: when a set is composed
# of just strings that happen to be integers in radix 10 in the range
# of 64 bit signed integers.
# The following configuration setting sets the limit in the size of the
# set in order to use this special memory saving encoding.
set-max-intset-entries 512

5.5 zset

zset是工作中较为常用的结构类型，其底层存储结构也使用了两种，ziplist和skiplist。同时也存在切换关系：

# Similarly to hashes and lists, sorted sets are also specially encoded in
# order to save a lot of space. This encoding is only used when the length and
# elements of a sorted set are below the following limits:
zset-max-ziplist-entries 128
zset-max-ziplist-value 64

满足一下条件任意一种，就会将ziplist结构转为skiplist：

1、ziplist存储的元素个数大于128个；

2、ziplist存储的单个节点数据内存超过64字节；
在这里插入图片描述