Redis五种常见数据结构的实现及使用场景

一、Redis对象底层数据结构

Redis底层数据结构共有八种,如下表所示:

编码类型 编码所对应的底层数据结构
REDIS_ENCODING_INT 8字节的long长整型
REDIS_ENCODING_EMBSTR embstr 编码的简单动态字符串
REDIS_ENCODING_RAW 简单动态字符串
REDIS_ENCODING_HT 字典
REDIS_ENCODING_LINKEDLIST 双端链表
REDIS_ENCODING_ZIPLIST 压缩列表
REDIS_ENCODING_INTSET 整数集合
REDIS_ENCODING_SKIPLIST 跳跃表和字典
1、SDS(简单动态字符串)

字符串对象的编码可以是int、raw或者embstr(专门保存段字符串的优化编码方式)

1.1、raw

重点说一下SDS,当字符串长度大于OBJ_ENCODING_EMBSTR_SIZE_LIMIT(39)(39字节)的时候,底层实现为SDS,encoding 编码设置为raw

Redis没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示.

在Redis 里面,C字符串只会作为字面量(string literal)用在一些无须对字符串值进行修改的地方。

一个可以被修改的字符串值里面,Redis就会使用SDS来表示字符串值,比如:Redis数据库里面,包含字符串值得健值对在底层得实现都是由SDS实现的


注意:更正一下,buf在Redis中实质是一个字节数组,它里面保存的是二进制数据。

SDS与C字符串的区别

(1)常数O(1)复杂度获取字符串长度

C字符串不记录自身的长度信息, 获取字符串长度时会遍历字节数组, 直到遇到空字符为止. 复杂度为 O(N)
SDS直接通过 len 属性获取字符串长度. 复杂度为O(1)

(2)杜绝缓冲区溢出

C字符串不记录自身长度, 修改字符串时不会判断本身是否拥有足够的内存空间, 当内存空间不足时, 则会造成缓冲区的溢出.

SDS对字符串进行修改时,先检查内存空间是否满足修改的需要, 若不满足, 则自动扩展SDS的内存空间. 所以使用SDS既不需要手动修改内存空间的大小, 也不会出现缓冲区溢出的情况.

(3)空间预分配

第一次创建字符串对象时, SDS不会分配冗余空间, 即 len = 0,当SDS的API修改SDS时, 则会为其分配冗余空间.

  • 当修改后的SDS的 len 属性小于1MB时, 则为其分配和 len 同样大小的冗余空间, 即 free = len, 此时 buf [ ] 的实际长度 = len(实际长度) + free(冗余空间) + 1(空字符)
  • 当修改后的SDS的 len 属性大于等于1MB时, 则为其分配1MB的冗余空间. buf [ ] 的实际长度 = len(实际长度) + free(1MB) + 1(空字符)

(4)惰性空间释放

SDS的API缩短SDS的字符串时, 不会立即使用内存分配回收缩短后多出来的字节, 而是记录在 free 属性中, 并等待将来使用.

(5)二进制安全
C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

SDS的API都是二进制安全的。所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读 取时就是什么样

这也是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符,而是用它来保存一系列二进制数据。

1.2、embstr
从Redis 3.0版本开始字符串引入了EMBSTR编码方式,长度小于OBJ_ENCODING_EMBSTR_SIZE_LIMIT(3.2 以前是39字节、3.2以后是44字节)的字符串将以EMBSTR方式存储。

EMBSTR方式的意思是 embedded string ,字符串的空间将会和redisObject对象的空间一起分配,两者在同一个内存块中。

Redis中内存分配使用的是jemalloc(内存分配器),jemalloc分配内存的时候是按照 8,16,32,64 作为chunk的单位进行分配的。

为了保证采用这种编码方式的字符串能被jemalloc分配在同一个chunk中,该字符串长度不能超过64,

故字符串长度限制OBJ_ENCODING_EMBSTR_SIZE_LIMIT我们就可以来计算一下

在redis 3.2版本以前

struct SDS {
    unsigned int capacity; // 4byte
    unsigned int len; // 4byte
    byte[] content; // 内联数组,长度为 capacity
}

这里的unsigned int 一个4字节,加起来是8字节.

内存分配器jemalloc分配的内存如果超出了64个字节就认为是一个大字符串,就会用到raw编码。

前面提到 SDS 结构体中的 content 的字符串是以字节\0结尾的字符串,之所以多出这样一个字节,是为了便于直接使用 glibc 的字符串处理函数,以及为了便于字符串的调试打印输出。所以我们还要减去1字节
64byte - 16byte - 8byte - 1byte = 39byte

在redis 3.2版本之后

struct SDS {
    int8 capacity; // 1byte
    int8 len; // 1byte
    int8 flags; // 1byte
    byte[] content; // 内联数组,长度为 capacity
}

这里unsigned int 变成了uint8_t、uint16_t的形式,还加了一个int8 flags标识,总共只用了3个字节的大小。相当于优化了sds的内存使用,相应的用于存储字符串的内存就会变大

然后进行计算:

64byte - 16byte -3byte -1byte = 44byte。

所以,redis 3.2版本之后embstr最大能容纳的字符串长度是44,之前是39。长度变化的原因是SDS中内存的优化

2、int

int编码以整数的方式保存字符串数据,即使在写的时候加上了引号,Redis也会把这些数字当作整数类型来保存。0-10000之间的OBJ_ENCODING_INT编码的字符串对象将进行共享。注意:当整数的范围超过long了,还是会使用embstr或raw来保存。

3、双向链表

Redis中的双链表是这样式的:

每个节点都是一个listNode,拥有前驱节点,后继节点和值。这就是C语言中的双向链表

typedef struct listNode{
	struct listNode *prev;    //前驱节点
	struct listNode *next;    //后继节点
	void* value;   //万能指针,可以存放任何类型的值  
}listNode;

只要有多个节点就可以组成一个链表了,但是redis再在外面封装了一层,也就是使用adlist.h/list来实现,这样操作起来更加方便。

typedef struct list { 
	listNode *head; //链表头结点指针 
	listNode *tail; //链表尾结点指针
	unsigned long len; //链表长度计数器
 
	//下面的三个函数指针就像类中的成员函数一样
	void *(*dup)(void *ptr); //复制链表节点保存的值 
	void (*free)(void *ptr); //释放链表节点保存的值
	int (*match)(void *ptr, void *key); //比较链表节点所保存的节点值和另一个输入的值是否相等 
}list;

链表结构比较简单,这里不多说了。

4、ziplist(压缩列表)

压缩列表。redis的列表键和哈希键的底层实现之一。此数据结构是为了节约内存而开发的。和各种语言的数组类似,它是由连续的内存块组成的,这样一来,由于内存是连续的,就减少了很多内存碎片和指针的内存占用,进而节约了内存。

Emtry结点的内部结构是这样的:

元素的遍历

先找到列表尾部元素:

然后再根据ziplist节点元素中的 previous_entry_length属性,来逐个遍历:

连锁更新

再次看看 entry元素的结构,有一个 previous_entry_length字段,他的长度要么都是1个字节,要么都是5个字节:

  • 前一节点的长度小于254字节,则 previous_entry_length长度为1字节
  • 前一节点的长度大于254字节,则 previous_entry_length长度为5字节
5、哈希表

哈希表的结构是这样的:

蓝色部分很好理解,数组就是bucket,一般不同的key首先会定位到不同的bucket,若key重复,就用链表把冲突的key串起来。熟悉HashMap的同学应该不陌生,这个结构和HashMap的结构几乎一样,就连处理冲突的的方式都是采用一样的方式:拉链法。

rehash

再来看看哈希表总体图中左边橘黄色的部分,其中有两个关键的属性:ht和 rehashidx。ht是一个数组,有且只有俩元素ht[0]和ht[1];其中,ht[0]存放的是redis中使用的哈希表,而ht[1]和rehashidx与哈希表的扩容有关,具体来说,ht[1]自相的是扩容后的hash表

rehash指的是重新计算键的哈希值和索引值,然后将键值对重排的过程

加载因子(load factor)=ht[0].used/ht[0].size

扩容和收缩标准

扩容:

  • 没有执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的 加载因子大于等于1。
  • 正在执行BGSAVE和BGREWRITEAOF指令的情况下,哈希表的 加载因子大于等于5。

收缩:

  • 加载因子小于0.1时,程序自动开始对哈希表进行收缩操作。

扩容和收缩的数量

扩容:第一个大于等于 ht[0].used*2的 2^n(2的n次方幂)。

收缩:第一个大于等于 ht[0].used的 2^n(2的n次方幂)。

扩容过程
收缩过程

渐进式refresh

在"扩容步骤"和"收缩步骤" 两幅动图中每幅图的第四步骤“将ht[0]中的数据利用哈希函数重新计算,rehash到ht[1]”,并不是一步完成的,而是分成N多步,循序渐进的完成的。因为hash中有可能存放几千万甚至上亿个key,毕竟Redis中每个hash中可以存 2^32-1 键值对(40多亿),假如一次性将这些键值rehash的话,可能会导致服务器在一段时间内停止服务

哈希表的refresh是分多次、渐进式进行的。

渐进式refresh和下图中左边黄色的部分中的 rehashidx密切相关:

  • rehashidx 的数值就是现在rehash的元素位置
  • rehashidx 等于 -1 的时候说明没有在进行refresh

甚至在进行期间,每次对哈希表的增删改查操作,除了正常执行之外,还会顺带将ht[0]哈希表相关键值对rehash到ht[1]。

已扩容过程为例:

6、intset

整数集合是集合键的底层实现方式之一。

7、skiplist(跳表)

跳表的原始模样是这个样式的:

跳表,是基于链表实现的一种类似“二分”的算法。它可以快速的实现增,删,改,查操作。

当我们要在一个链表中查找某个数据的时候需要的时间复杂度为O(n)。怎么提高查询效率呢?如果我们给该单链表加两级索引,将会改善查询效率。

比如我们要查询元素6,如果是单链表,我们需要重链表的头结点一个个遍历,需要比较6次才可以找到到元素6节点,时间复杂度是O(n),而我们给原链表加上两级索引之后查询元素6。当数据量增大到一定程度的时候,效率将会有显著的提升。

如果我们再加多几级索引的话,效率将会进一步提升。这种链表加多级索引的结构,就叫做跳表。跳表的查询时间复杂度可以达到O(logn)

redis中把跳表抽象成如下所示:

看这个图,左边黄色部分:

  • header: 跳表表头
  • tail:跳表表尾
  • level:层数最大的那个节点的层数
  • length:跳表的长度

右边蓝色部分:

  • 表头:是链表的哨兵节点,不记录主体数据。
  • 是个双向链表
  • 分值是有顺序的
  • o1、o2、o3是节点所保存的成员,是一个指针,可以指向一个SDS值。
  • 层级高度最高是32。每次创建一个新的节点的时候,程序都会随机生成一个介于1和32之间的值作为level数组的大小,这个大小就是“高度”

二、Redis五种数据结构的实现

Redis对象头结构体

redis中并没有直接使用以上所说的各种数据结构来实现键值数据库,这里我们首先来了解一下 Redis 对象头结构体,所有的 Redis 对象都有下面的这个结构头:

不同的对象具有不同的类型** type(4bit)**,同一个类型的 type 会有不同的存储形式 encoding(4bit),为了记录对象的 LRU 信息,使用了 24 个 bit 来记录 LRU 信息

每个对象都有个引用计数refcount(4字节),当引用计数为零时,对象就会被销毁,内存被回收。*ptr 指针将指向对象内容 (body) 的具体存储位置

这样一个RedisObject对象头就占用16字节的空间

1、字符串(string)

字符串对象的编码可以是int、raw或者embstr

如果一个字符串的内容可以转换为int,那么该字符串就会被转换成为int类型,对象的ptr就会指向该int,并且对象类型也用int类型表示

普通的字符串有两种,embstr和raw。embstr应该是Redis 3.0新增的数据结构,在2.8中是没有的。如果字符串对象的长度小于39字节,就用embstr对象

使用场景:

  1. 缓存功能:字符串最经典的使用场景,redis做为缓存层,Mysql作为储存层,绝大部分请求数据都是redis中获取,由于redis具有支撑高并发特性,所以缓存通常能起到加速读写和降低 后端压力的作用。
  2. 计数器:许多运用都会使用redis作为计数的基础工具,他可以实现快速计数、查询缓存的功能,同时数据可以一步落地到其他的数据源。如:视频播放数系统就是使用redis作为视频播放数计数的基础组件。
  3. 共享session:出于负载均衡的考虑,分布式服务会将用户信息的访问均衡到不同服务器上,用户刷新一次访问可能会需要重新登录,为避免这个问题可以用redis将用户session集中管理,在这种模式下只要保证redis的高可用和扩展性的,每次获取用户更新或查询登录信息都直接从redis中集中获取。
  4. 限速:处于安全考虑,每次进行登录时让用户输入手机验证码,为了短信接口不被频繁访问,会限制用户每分钟获取验证码的频率。

2、list

list对象的编码可以是ziplist或者linkedlist

ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大,每个元素也不大的时候,就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性,插入的复杂度是O(N),即每次插入都会重新进行realloc。

当list对象同时满足以下两个条件时,列表对象使用ziplist编码:

(1)列表对象保存的所有字符串元素的长度都小于64字节

(2)列表对象保存的元素数量小于512个

当有任一条件 不满足时将会进行一次转码,使用linkedlist。

使用场景:

  1. 消息队列: redis的lpush+brpop命令组合即可实现阻塞队列,生产者客户端是用lupsh从列表左侧插入元素,多个消费者客户端使用brpop命令阻塞时的“抢”列表尾部的元素,多个客户端保证了消费的负载均衡和高可用性

3、hash

哈希对象的底层实现可以是ziplist或者hashtable。

zipList编码的哈希对象使用压缩列表作为底层实现,每当有新的健值对要加入到哈希对象时,程序会先将保存了key的压缩列表节点推入到压缩列表尾,然后再将保存了value的压缩节点推入到压缩列表尾,因此:保存了同一key:vlaue对的两个节点总是紧挨在一起,保存key的节点在前,保存value的节点在后,如下图所示:

当对象数目不多且内容不大时,这种方式效率是很高的。此时redis会使用哈希表(hashtable)作为底层数据结构

hashtable编码的哈希独享使用字典作为底层实现,哈希对象中的每个键值对都使用一个字典健值对来保存。字典的每个键(key)和每个值(value)都是一个字符串对象,对象中保存了键或值。这种结构的时间复杂度为O(1),但是会消耗比较多的内存空间

当哈希对象可以同时满足以下两个条件时,哈希对象使用ziplist编码:

  • 当键的个数小于hash-max-ziplist-entries(默认512)
  • 当所有值都小于hash-max-ziplist-value(默认64)

使用场景:

  1. 哈希结构相对于字符串序列化缓存信息更加直观,并且在更新操作上更加便捷。所以常常用于用户信息等管理,但是哈希类型和关系型数据库有所不同,哈希类型是稀疏的,而关系型数据库是完全结构化的,关系型数据库可以做复杂的关系查询,而redis去模拟关系型复杂查询,开发困难,维护成本高。

4、set

set对象的编码可以是intset或者hashtable。

intset是一个整数集合,里面存的为某种同一类型的整数,支持如下三种长度的整数:

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

intset编码使用的条件:

(1)集合对象保存的元素全部都是整数

(2)集合对象保存的元素不超过512个

不满足以上条件,集合对象需要使用hashtable

注:第二个条件的上限可以修改,set-max-intset-entries默认值为512。表示如果entry的个数小于此值,则可以编码成REDIS_ENCODING_INTSET类型存储,节约内存。否则采用dict的形式存储。

使用场景:

  1. 标签(tag):集合类型比较典型的使用场景,如一个用户对娱乐、体育比较感兴趣,另一个可能对新闻感兴趣,这些兴趣就是标签,有了这些数据就可以得到同一标签的人,以及用户的共同爱好的标签,这些数据对于用户体验以及曾强用户粘度比较重要。(用户和标签的关系维护应该放在一个事物内执行,防止部分命令失败造成数据不一致)
  2. sadd=tagging(标签)
  3. 生成随机数,比如抽奖:spop/srandmember=random item
  4. sadd+sinter=social Graph(社交需求)

5、zset

zset的编码有两种,一种是ziplist,另一种是skiplist与dict的结合

ziplist编码的压缩对象使用压缩列表作为底层实现,每个集合元素使用两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员(member),而第二个原属则保存元素的分值(score)

压缩列表内的集合原属按分值从小到大进行排序,分值较小的元素放置在靠近表头的方向,而分值较大的元素则放置在靠近表位的方向

ziplist编码的使用条件:

(1)有序集合保存的元素数量小于128个

(2)有序集合保存的所有元素成员长度小于64字节

上限值可以根据配置文件中的配置进行调整

skiplist是一种跳跃表,它实现了有序集合中的快速查找,在大多数情况下它的速度都可以和平衡树差不多。但它的实现比较简单,可以作为平衡树的替代品。它的结构比较特殊。

使用场景:

  1. 排行榜:有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜,榜单维护可能是多方面:按照时间、按照播放量、按照获得的赞数等。

参考

留言区

还能输入500个字符