一谈到redis,我们机会想到一个字‘快’,但是redis的快到底快在哪里呢?一方面,是因为它是内存数据库,所有操作都在内存上完成,内存的访问速度本来就很快;另一方面,要归功于它底层的数据结构,键值对是按一定的数据结构来组织的,操作键值对最终就是对数据结构进行增删改查操作。

1:redis底层有哪些数据结构?

注意:String(字符串)、List(列表)、Hash(哈希)、Set(集合)和 Sorted Set(有序集合)只是 Redis 键值对中值的数据类型,也就是数据的保存形式。

这里说的数据结构是,它的底层实现,简单来说,redis底层有6中数据结构,分别是 简单动态字符串,双向链表,压缩列表,跳表,整数数组,哈希表。它和数据类型的对应关系如下:

image.png

可以看到,String 类型的底层实现只有一种数据结构,也就是简单动态字符串。而 List、Hash、Set 和 Sorted Set 这四种数据类型,都有两种底层实现结构。通常情况下,我们会把这四种类型称为集合类型,它们的特点是一个键对应了一个集合的数据

2:redis中键和值用什么结构组织?

Redis为了实现键到值的快速访问,使用了一个哈希表来保存所有的键值对。
一个hash表也就是一个数组,数组的每一个元素成为哈希桶,也就是说一个哈希表是由多个哈希桶组成的,每个哈希桶中保存了键值对数据。

在这里需要注意的是。哈希桶中的元素存储的并不是值本身,而是指向具体值的指针,这也就是说,不管值是 String,还是集合类型,哈希桶中的元素都是指向它们的指针。

2.1:全局哈希表

从下面,可以看到,哈希桶中的 entry 元素中保存了key和value指针,分别指向了实际的键和值,这样一来,即使值是一个集合,也可以通过*value指针被查找到。

image.png
这个哈希表保存了所有的键值对,因此我们称之为全局哈希表

2.1.1:哈希表有哪些优势?

哈希表的优势十分明显;

  • 我们只需要计算键的哈希值,就可以知道它所对应的哈希桶位置,然后就可以访问相应的 entry 元素,时间复杂度为O(1)
  • 查找过程主要依赖于哈希计算,和数据量的多少并没有直接关系。也就是说,不管哈希表里有 10 万个键还是 100 万个键,我们只需要一次计算就能找到相应的键。

但是如果往redis中添加大量的数据后,就有很大可能性发生hash冲突。

2.2:哈希冲突

2.2.1:什么是hash冲突?

当我们向哈希表中添加很多的数据的时候,hash冲突是不可避免的问题。这里的哈希冲突,也就是指,两个 key 的哈希值和哈希桶计算对应关系时,正好落在了同一个哈希桶中。

2.2.2:Redis解决哈希冲突的方式?

Redis 解决哈希冲突的方式,就是链式哈希。链式哈希也很容易理解,就是指同一个哈希桶中的多个元素用一个链表来保存,它们之间依次用指针连接。

如下图所示:entry1、entry2 和 entry3 都需要保存在哈希桶 3 中,导致了哈希冲突。此时,entry1 元素会通过一个next指针指向 entry2,同样,entry2 也会通过next指针指向 entry3。这样一来,即使哈希桶 3 中的元素有 100 个,我们也可以通过 entry 元素中的指针,把它们连起来。这就形成了一个链表,也叫作哈希冲突链。

image.png

2.2.3:链式哈希存在的问题?

哈希冲突链上的元素只能通过指针逐一查找再操作。如果哈希表里写入的数据越来越多,哈希冲突可能也会越来越多,这就会导致某些哈希冲突链过长,进而导致这个链上的元素查找耗时长,效率降低。
为了解决这个问题,就需要了解rehash和渐进式rehash的过程和原理。

2.3:rehash VS 渐进式rehash

2.3.1:rehash

rehash,也就是增加现有的哈希桶的数量,让逐渐增多的entry元素能在更多的桶之间分散保存,减少单个桶中的元素数量。

为了使rehash操作更加高效,Redis默认使用了两个全局hash表,哈希表1和哈希表2。当刚插入数据的时候,默认使用哈希表1,此时哈希表2并没有分配空间,随着数据逐步增多,redis执行rehash。redis执行rehash的过程如下:

  • 1:给哈希表2分配更大的空间,比如是当前哈希表1的空间的2倍
  • 2:把哈希表1中的数据重新映射并拷贝到哈希表2中
  • 3:释放哈希表2的空间

此时哈希表1就切换到哈希表2,用大容量的哈希表2保存了更多的数据,而原来的哈希表1留作下一次rehash扩容准备。

但是这个过程,有个很大的问题,也就是上面的第二步大量的数据拷贝,会造成redis线程阻塞,无法服务其他请求。为了避免这个问题,Redis采用了渐进式的rehash.

2.3.1:渐进式rehash

redis渐进式rehash就是在第二步拷贝数据的时候,redis仍然正常处理客户端的请求,每处理一个请求时,从哈希表1中的第一个索引位置开始,顺带着将这个索引位置上的是有entries拷贝到哈希表2中;等处理下一个请求时,在顺带拷贝哈希表1中下一个索引位置的entries。

image.png

如上图,这样就巧妙的将一次性大量拷贝的开销,分摊到了多次请求的过程中,避免了耗时操作,保证了数据的快速访问。

3:redis常见类型的底层数据结构实现?

redis数据类型和底层数据结构的对应关系如下:
image.png

与String类型不同,一个集合类型的值,第一步是通过全局哈希表查找到对应的哈希桶位置,第二步是在集合中进行增删改查,这样,操作效率与底层的数据结构就有很大关系,其次和操作本身的执行特点也有关系(单个操作和批量操作)

3.1:List类型底层实现

Redis中的列表list,在版本3.2之前,列表底层的编码是ziplist(压缩列表)和linkedlist(双向链表)实现的,但是在版本3.2之后,重新引入 quicklist,列表的底层都由quicklist实现。quickList本质上也是一个双向链表。
redis中quicklist的源码

typedef struct quicklist { // src/quicklist.h
    quicklistNode *head;
    quicklistNode *tail;
    unsigned long count;        /* ziplist 的个数 */
    unsigned long len;          /* quicklist 的节点数 */
    unsigned int compress : 16; /* LZF 压缩算法深度 */
    //...
} quicklist;
typedef struct quicklistNode {
    struct quicklistNode *prev;
    struct quicklistNode *next;
    unsigned char *zl;           /* 对应的 ziplist */
    unsigned int sz;             /* ziplist 字节数 */
    unsigned int count : 16;     /* ziplist 个数 */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    unsigned int recompress : 1; /* 该节点先前是否被压缩 */
    unsigned int attempted_compress : 1; /* 节点太小无法压缩 */
    //...
} quicklistNode;
typedef struct quicklistLZF {
    unsigned int sz; 
    char compressed[];
} quicklistLZF;

从以上源码可以看出 quicklist 是一个双向链表,链表中的每个节点实际上是一个 ziplist。
image.png

ziplist 作为 quicklist 的实际存储结构,ziplist实际上类似于一个数组,数组的每一个元素都对应保存一个数据。但是和数组不同的是,压缩列表在表头有三个字段zlbytes,zltail,zllen,分别表示列表长度、列表尾的偏移量和列表中的entry个数;压缩列表尾部还有一个zlend,表示列表结束。

其中的字段含义如下:

  • zlbytes:压缩列表字节长度,占 4 字节;
  • zltail:压缩列表尾元素相对于起始元素地址的偏移量,占 4 字节;
  • zllen:压缩列表的元素个数;
  • entryX:压缩列表存储的所有元素,可以是字节数组或者是整数;
  • zlend:压缩列表的结尾,占 1 字节。

ziplist 数据结构如下图所示:
image.png

在压缩列表中,如果要查找定位第一个元素和最后一个元素,可以通过表头的三个字段直接定位,复杂度为O(1),而定位其他元素时,只能逐个查找,时间复杂度就变成O(N)了。

3.2:Set类型底层实现

Set集合类型由intset(整数数组/整数集合)或者hashtable(哈希表)组成。当集合类型以hashTable存储时,哈希表的key为要插入的元素值,而哈希表的value为Null,当集合中所有的值都是整数时,redis会采用intset结构来存储。

image.png

上面截图可以看出,当所有的元素都为整数的时候,集合会以intset结构进行存储,当发生以下两种情况时,会导致集合类型使用hashtable而非inset存储;

  • 1:当元素的个数超过512个(redis默认,该值可以通过set-max-intset-entries xxx来配制)
  • 2:当元素为非整数时,集合会以hashtable来存储

3.3:Sorted Set有序集合底层实现

有序集合类型 (Sorted Set) 相比于集合类型多了一个排序属性 score(分值),对于有序集合 ZSet 来说,每个存储元素相当于有两个值组成的,一个是有序结合的元素值,一个是排序值。有序集合的存储元素值也是不能重复的,但分值是可以重复的。

有序集合 sorted set是由ziplist(压缩列表)或者skiplist(跳表)存储的

有序集合采用ziplist存储数据必须满足一下两个条件

  • 有序集合元素个数要小于128个
  • 有序集合保存的所有元素的成员的长度都必须小于64字节

image.png

跳表skiplist的实现原理

跳表在链表的基础上,增加了多级索引,通过索引位置的几个跳转,实现数据的快速定位
跳表skipList的特点:

  • 1:由很多层结构组成
  • 2:每一层都是一个有序的链表
  • 3:最底层的链表包含所有元素
  • 4:如果一个元素出现在 Level i 的链表中,则它在 Level i 之下的链表也都会出现。
  • 5:每个节点包含两个指针,一个指向同一链表中的下一个元素,一个指向下面一层的元素。

image.png

根据以上图片展示,当我们在跳跃表中查询值 32 时,执行流程如下:

  • 从最上层开始找,1 比 32 小,在当前层移动到下一个节点进行比较;
  • 7 比 32 小,当前层移动下一个节点比较,由于下一个节点指向 Null,所以以 7 为目标,移动到下一层继续向后比较;
  • 18 小于 32,继续向后移动查找,对比 77 大于 32,以 18 为目标,移动到下一层继续向后比较;
  • 对比 32 等于 32,值被顺利找到。

跳跃表会从最上层开始找起,依次向后查找,如果本层的节点大于要找的值,或者本层的节点为 Null 时,以上一个节点为目标,往下移一层继续向后查找并循环此流程,直到找到该节点并返回,如果对比到最后一个元素仍未找到,则返回 Null

这个查找过程就是在多级索引上跳来跳去,最后定位到元素。这也正好符合“跳”表的叫法。当数据量很大时,跳表的查找复杂度就是 O(logN)。

3.3:Hash类型底层实现

字典类型 (Hash) 又被成为散列类型或者是哈希表类型。

字典类型本质上是由数组和链表结构组成的,来看字典类型的源码实现:

typedef struct dictEntry { // dict.h
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next; // 下一个 entry
} dictEntry;

字典数据结构如下图所示
image.png

哈希表,当我们在想哈希表中添加大量的数据时候,不可避免的会发生hash冲突,hash冲突的解决办法就是采用链地址法。但是hash冲突严重时,会造成链表的长度过长,效率就大大降低了,redis为了解决这个问题,采用了渐进式rehash的方式来解决。

3.5:String类型底层实现

字符串类型的全称是 Simple Dynamic Strings 简称 SDS,中文意思是:简单动态字符串。它是以键值对 key-value 的形式进行存储的,根据 key 来存储和获取 value 值。

SDS 对象包含了三种不同的数据类型:int、embstr 和 raw

① int 类型

127.0.0.1:6379> set key 66
OK
127.0.0.1:6379> object encoding key
"int"

② embstr 类型

127.0.0.1:6379> set key1 redis
OK
127.0.0.1:6379> object encoding key1
"embstr"

③ raw 类型

127.0.0.1:6379> set key2 erwerwerwetrqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqqq
OK
127.0.0.1:6379> object encoding key2
"raw"

整数类型对应的就是 int 类型,而字符串则对应是 embstr 类型,当字符串长度大于 44 字节时,会变为 raw 类型存储

关于字符串底层原理实现,后续会有专门的章节详解。

3.6:数据结构的时间复杂度

image.png

我们在使用redis的数据类型的时候,就需要权衡底层数据结构在不同的数据量级下的性能表现,综合对比,选择 最优的类型来进行业务操作。

Q.E.D.

知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议