一、Redis对象底层数据结构

Redis的八种编码类型，如下表所示：

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次方幂)。

扩容过程

收缩过程

渐进式rehash

上面说到，扩容或者收缩哈希表时需要将ht[0]中的所有键值对迁移到ht[1]中，如果ht[0]中的数据量不是很大，几十几百甚至几万个，对于redis来说都不是大问题；但是，如果hash表中存储的键值对数量是几百万、几千万甚至上亿的数据，那么要一次性将这些键值对迁移到ht[1]中，庞大的数据可能会使redis服务器在一段时间内停止服务。

因此为了避免rehash对服务器性能造成影响，服务器不会一次将ht[0]中的数据迁移到ht[1]中，而是分多次，渐进式的完成。

以下是哈希表渐进式rehash的详细步骤：

• 1）为ht[1]分配空间，让字段同事持有ht[0]和ht[1]两个hash表。
• 2）在字典中维持一个索引计数器变量rehashidx,并将他的值设置为0，表示rehash开始。
• 3）在rehash期间，每次对ht[0]字典执行添加、删除、查找或者更新操作时，程序除了执行指定操作外，还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对迁移到ht[1]上，完成后，rehashidx值+1。
• 4）随着字典操作不断进行，最总在某个时间点上，ht[0]上的所有键值对都将会被rehash到ht[1]，这是程序设置rehashidx为-1,表示rehash操作完成。

渐进式rehash的好处在于它采用分而治之的方式，将rehash键值对所需的计算工作量均摊到了对字典的每个添加、删除、查找和更新操作上，从而避免了集中式rehash带来的性能影响。

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

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

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

已扩容过程为例：

6、intset

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

7、skiplist（跳表）

skiplist是一种基于有序列表发展而来的数据数据结构，他可以支持平均O(logN)，最坏O(N)的时间复杂度。大部分情况下，skiplist的效率可以和平衡树相媲美，而且skiplist的实现更加简单，只要你能熟练操作链表，就能轻松实现一个 skiplist。

有序表的搜索

考虑一个有序表：

从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数为 2 + 4 + 6 = 12 次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉搜索树，我们把一些节点提取出来，作为索引。得到如下结构：

这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。

我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

元素越多skiplist的优势就越明显

skiplist

跳表具有如下性质：

• (1) 由很多层结构组成，支持平均O(logN)，最坏O(N)的时间复杂度
• (2) 每一层都是一个有序的链表
• (3) 最底层(Level 1)的链表包含所有元素
• (4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
• (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

插入操作

上图所示的skiplist有9个结点，一共4层，可以说是理想的跳跃表了，不过随着我们对跳跃表进行插入/删除结点的操作，那么跳跃表结点数就会改变，意味着跳跃表的层数也会动态改变。

这里我们面临一个问题，就是新插入的结点应该跨越多少层？

这个问题已经有大牛替我们解决好了，采取的策略是通过抛硬币来决定新插入结点跨越的层数：每次我们要插入一个结点的时候，就来抛硬币，如果抛出来的是正面，则继续抛，直到出现负面为止，统计这个过程中出现正面的次数，这个次数作为结点跨越的层数。

例如，我们要插入结点 3，4，通过抛硬币知道3，4跨越的层数分别为 0，2 (层数从0开始算)，则插入后skiplist如下：

删除操作

解决了插入之后，我们来看看删除，删除就比较简单了，例如我们要删除4，那我们直接把4及其所跨越的层数删除就行了

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. 排行榜：有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜，榜单维护可能是多方面：按照时间、按照播放量、按照获得的赞数等。

参考

• 【1】妖四灵.Shuen.Redis 5种数据结构(底层原理,性能分析,使用场景.CSDN)
• 【2】RyuGou.图解redis五种数据结构底层实现(动图版).今日头条
• 【3】唐宋缘明卿_cris.redis五种数据结构的实现及使用场景.CSDN
• 【4】Redis---String.码迷