前言

Github：https://github.com/HealerJean

博客：http://blog.healerjean.com

1、Redis使用场景

1、缓存，几乎在所有大型的网站都有使用，可以设置键值过期时间

2、计数器应用，这个我们公司就有用到，用来拦截访问次数的。

3、排行榜系统，Redis提供了list和Zset有序集合数据结构，合理使用这个就可以构建各种排行榜系统

4、消息队列，这个在netty和websocket的时候有使用过，通过coverAndSend进行队列的监听并发送

2、数据结构和编码

2.1、string

解释：这里的字符串千万不要以为真的是字符串，可以是字符串，也可以是数字（整数，浮点数，甚至可以是二进制)

字符串 string 是 Redis 最简单的数据结构。Redis 所有的数据结构都是以唯一的 key 字符串作为名称，然后通过这个唯一 key 值来获取相应的 value 数据。

不同类型的数据结 构的差异就在于 value 的结构不一样。

2.1.1、常用命令

2.1.2、使用场景：

计数，共享session，限速，用户信息

2.1.3、数据结构

String类型的数据结构存储方式有三种int、raw、embstr。那么这三种存储方式有什么区别呢？

2.1.3.1、int

数字类型：Redis中规定假如存储的是「数字」，比如set num 123这样的类型，就会使用 int的存储方式进行存储

最大值是(2^63)-1 （long的最小和最大值，超过这个范围会报错）

>set max 9223372036854775807
OK

>incr max
ERR increment or decrement would overflow


9223372036854775807 = (2^63)-1

2.1.3.2、raw

raw就是redisObject+sds，即redisObject的ptr指针指向一个sds对象。

SDS称为「简单动态字符串」，对于SDS中的定义在Redis的源码中有的三个属性int len、int capacity、char content[]。

SDS：是可以修改的字符串，内部结构实现上类似于 Java 的 ArrayList，采用预分配冗余空间的方式来减少内存的频繁分配，

如图中所示，内部为当前字符串实际分配的空间 capacity 一般要高于实际字符串长度 len。

struct SDS<T> {
  T capacity; // 数组容量
  T len; // 数组长度
  byte flags; // 特殊标识位，不理睬它
  byte[] content; // 数组内容
}

1、如代码所示，content 里面存储了真正的字符串内容，那 capacity 和 len 表示什么意思 呢?它有点类似于 Java 语言的 ArrayList 结构，需要比实际的内容长度多分配一些冗余空间。capacity 表示所分配数组的长度，len 表示字符串的实际长度。

前面我们提到字符串是可 以修改的字符串，它要支持 append 操作。如果数组没有冗余空间，那么追加操作必然涉及 到分配新数组，然后将旧内容复制过来，再 append 新内容。如果字符串的长度非常长，这 样的内存分配和复制开销就会非常大。

2、上面的 SDS 结构使用了范型 T，为什么不直接用 int 呢，这是因为当字符串比较短 时，len 和 capacity 可以使用 byte 和 short 来表示，Redis 为了对内存做极致的优化，不同长度的字符串使用不同的结构体来表示。

和c语言字符串比较

1、C语言中的字符串并不会记录自己的长度：

◯ C语言「每次获取字符串的长度都会遍历得到，时间的复杂度是O(n)

◯ SDS中获取字符串只要读取len的值就可，时间复杂度变为O(1)。

2、C语言不会动态扩容：

◯ C语言中两个字符串拼接，若是没有分配足够长度的内存空间就会出现缓冲区溢出的情况，n次增长字符串必然会带来n次的内存分配；

◯ SDS会先根据len属性判断空间是否满足要求，若是空间不够，就会进行相应的空间扩展，所以不会出现缓冲区溢出的情况。

3、SDS还提供「空间预分配」和「惰性空间释放」两种策略，在为字符串分配空间时

♡ 分配的空间比实际要多

1、当修改后字符串长度小于 1M时， 扩容都是加倍现有的空间

2、如果超过 1M，扩容时一次只会多扩 1M 的空间。需要注意的是 字符串最大长度为 512M。

♡ 当字符串被缩短的时候

1、SDS不会立即回收不使用用的空间，而是等后面使用的时候再释放。

4、 SDS存储多样性

◯ C语言中的字符串是以空字符串作为结束符，一些图片中含有结束符，因此不是二进制安全的。

◯ SDS是二进制安全的，除了可以储存字符串以外还可以储存二进制文件（如图片、音频，视频等文件的二进制数据）

2.1.3.2、embstr

⬤ embstr即embedded string：嵌入式的字符串，将SDS结构体嵌入RedisObject对象中，是专门用于保存短字符串的一种编码方式

⬤ 如果字符串对象保存的是一个字符串值，并且这个字符粗值的长度小于等于44字节（44这个值并不会一直保持不变，例如redis3.2版本之前是39），则使用embstr编码，

与raw的差别在于：raw 会调用两次内存分配函数来创建redisObject结构和sds结构，而embstr编码则通过调用一次内存分配函数来分配一块连续的空间，空间内一次包含了redisObject和sds两个结构。

**问题：在长度特别短时，使用 embs 形式存储 (embeded)，当 长度超过44 时，使用 raw 形式存储。 **

**1、这两种类型有什么区别呢? **

2、为什么分界线是 44 呢?

> set codehole abcdefghijklmnopqrstuvwxyz012345678912345678
OK
> debug object codehole
Value at:0x7fec2de00370 refcount:1 encoding:embstr serializedlength:45 lru:5958906 lru_seconds_idle:1  
  
  
> set codehole abcdefghijklmnopqrstuvwxyz0123456789123456789
OK
> debug object codehole
Value at:0x7fec2dd0b750 refcount:1 encoding:raw serializedlength:46 lru:5958911 lru_seconds_idle:1

  
  
26(a->z) + 10(0->1) + 8(1->8) = 44  

注意上面 debug object 输出中有个 encoding 字段，一个字符的差别，存储形式就发生 了变化。这是为什么呢?

为了解释这种现象，我们首先来了解一下 Redis 对象头结构体，所有的 Redis 对象都有 下面的这个结构头:

一个 RedisObject 对象头需要占据16 字节的存储空间

struct RedisObject {
 int4 type; // 4bits
 int4 encoding; // 4bits
 int24 lru; // 24bits
 int32 refcount; // 4bytes
 void *ptr; // 8bytes，64-bit system

} robj;

1、不同的对象具有不同的类型 type(4bit)，

2、同一个类型的 type 会有不同的存储形式 encoding(4bit)

3、为了记录对象的 LRU 信息，使用了 24 个 bit 来记录 LRU 信息。

4、每个对象都有个引用计数refcount，当引用计数为零时，对象就会被销毁，内存被回收。

**5、ptr 指针将指向对 象内容 (body) 的具体存储位置。 **

接着我们再看 SDS 结构体的大小，在字符串比较小时，SDS 对象头的大小是capacity+3，至少是 3。意味着分配一个字符串的最小空间占用为 19 字节 (16+3)。

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

1、embstr 存储形式是这样一种存储形式，它将 RedisObject 对象头和 SDS 对 象连续存在一起，使用 malloc 方法一次分配。而 raw 存储形式不一样，它需要两次 malloc，两个对象头在内存地址上一般是不连续的。

2、内存分配器 jemalloc/tcmalloc 等分配内存大小的单位都是 2、4、8、16、32、64 等等，为了能容纳一个完整的 embstr 对象，jemalloc 最少会分配 32 字节的空间，如果字符串再稍微长一点，那就是 64 字节的空间。如果总体超出了 64 字节，Redis 认为它是一个大字符串，不再使用 emdstr 形式存储，而该用 raw 形式。

3、当内存分配器分配了 64 空间时，那这个字符串的长度最大可以是多少呢?这个长度就 是 44。那为什么是 44 呢？

4、前面我们提到 SDS 结构体中的 content 中的字符串是以字节\0 结尾的字符串，之所以 多出这样一个字节，是为了便于直接使用 glibc 的字符串处理函数，以及为了便于字符串的调试打印输出。留给 content 的长度最多只有 45(64-19) 字节了。字符串又是以\0 结尾，所以 embstr 最大能容纳的字符串长度就是 44。

embstr有以下好处：

1、embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次，内存释放函数也是从两次降低为一次。

2、因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面，所以这些编码的字符串对象比起raw编码的对象字符串，能够更好地利用缓存（CPU缓存/缓存行）带来的优势。

embstr的缺点：

1、embstr编码的字符串对象实际上是只读的，当我们对embstr编码的字符串对象执行任何修改命令（例如append）时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。

2.2、list

Redis 的列表相当于 Java 语言里面的 LinkedList，注意它是链表而不是数组。

1、插入和删除操作非常快，时间复杂度为 O(1)

2、查找：时间复杂度为 O(n),让人比较意外

2.2.1、常用命令

2.2.2、使用场景

1、消息队列：， lpush （左侧放）和brpop （右侧拿）就可以实现消息队

2.2.3、数据结构

⬤ Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。

⬤ 在3.2之后的版本就是引入了quicklist，全面替代了ziplist和linklist。

2.2.3.1、慢操作

2.2.3.1.1、lindex

Lindex 命令用于通过索引获取列表中的元素。你也可以使用负数下标，以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

解释 ： lindex 相当于 Java 链表的 get(int index)方法，它需要对链表进行遍历，性能随着参数index 增大而变差

redis 127.0.0.1:6379> LPUSH mylist "World"
(integer) 1

redis 127.0.0.1:6379> LPUSH mylist "Hello"
(integer) 2

redis 127.0.0.1:6379> LINDEX mylist 0
"Hello"

redis 127.0.0.1:6379> LINDEX mylist -1
"World"

redis 127.0.0.1:6379> LINDEX mylist 3        # index不在 mylist 的区间范围内
(nil)

2.2.3.1.2、ltrim

Ltrim 对一个列表进行修剪(trim)，就是说，让列表只保留指定区间内的元素，不在指定区间之内的元素都将被删除。 我们可以通过 ltrim 来实现一个定长的链表，这一点非常有用。

1、下标 0 表示列表的第一个元素，以 1 表示列表的第二个元素，以此类推。

2、以 -1 表示列表的最后一个元素， -2 表示列表的倒数第二个元素，以此类推。

redis 127.0.0.1:6379> RPUSH mylist "hello"
(integer) 1
redis 127.0.0.1:6379> RPUSH mylist "hello"
(integer) 2
redis 127.0.0.1:6379> RPUSH mylist "foo"
(integer) 3
redis 127.0.0.1:6379> RPUSH mylist "bar"
(integer) 4
redis 127.0.0.1:6379> LTRIM mylist 1 -1
OK
redis 127.0.0.1:6379> LRANGE mylist 0 -1
1) "hello"
2) "foo"
3) "bar"

2.2.3.2、ziplist+linkedlsit=quicklist

如果再深入一点，你会发现 Redis 底层存储的还不是一个简单的 linkedlist，而是称之为 快速链表 quicklist 的一个结构。

1、首先在列表元素较少的情况下会使用一块连续的内存存储，这个结构是 ziplist，也即是 压缩列表。

2、它将所有的元素紧挨着一起存储，分配的是一块连续的内存。没有任何冗余空隙。当数据量比较多的时候才会改成 linkedlst。

3、因为普通的链表需要的附加指针空间太大，会比较浪费空间，而 会加重内存的碎片化。比如这个列表里存的只是 int 类型的数据，结构上还需要两个额外的指针 prev 和 next 。

4、所以 Redis 将 ziplist +链表linkedlist结合起来组成了 quicklist。也就是将多个 ziplist 使用双向指针串起来使用。这样既满足了快速的插入删除性能，又不会出现太大的空间冗余。

2.3、hash (字典)

Redis 的字典相当于 Java 语言里面的 HashMap，它是无序字典。内部实现结构上同 Java 的 HashMap 也是一致的，同样的数组 + 链表二维结构。 不同的是：

**1、Redis 的字典的值只能是字符串（数字也算 哈）， **

2、另外它们 rehash 的方式不一样，因为 Java 的 HashMap 在字典很大时，rehash 是个耗时的操作，需要一次性全部 rehash。Redis 为了高性能，不能堵塞服务，所以采用了渐进式 rehash 策略。

⬤ 渐进式 rehash 会在 rehash 的同时，保留新旧两个 hash 结构，查询时会同时查询两个 hash 结构，然后在后续的定时任务中以及 hash 的子指令中，循序渐进地将旧 hash 的内容 一点点迁移到新的 hash 结构中。

⬤ 当 hash 移除了最后一个元素之后，该数据结构自动被删除，内存被回收。

2.3.1、常用命令

2.3.2、使用场景

hash 结构也可以用来存储用户信息，不同于字符串一次性需要全部序列化整个对象， hash 可以对用户结构中的每个字段单独存储。这样当我们需要获取用户信息时可以进行部分获取。而以整个字符串的形式去保存用户信息的话就只能一次性全部读取，这样就会比较浪 费网络流量。

1、存储用户信息，更加直观，节省空间

2.3.2.1、缺点

hash 也有缺点，hash 结构的存储消耗要高于单个字符串，到底该使用 hash 还是字符 串，需要根据实际情况再三权衡。

2.3.3、数据结构

Hash 对象的实现方式有两种分别是ziplist、hashtable，其中hashtable的存储方式key是String类型的，value 也是以key value 的形式进行存储。

2.4、set

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值 NULL(java 是new Object())。

intset 和 dict 都是 set 命令的底层数据结构

⬤ intset 是一个紧凑的整数数组结构，它用于存放元素都是整数的并且元素个数 较少的 set 集合。Redis 支持 set 集合动态从 uint16 升级到 uint32， 再升级到 uint64。

⬤ 当遇到添加数据为字符串，即不能表示为整数时，Redis 会把数据结构转换为 dict，即把 intset 中的数据全部搬迁到 dict。

2.3.1、常用命令

2.3.1、使用场景

1、存储不重复的数据

2.3.3、数据结构

Set的底层实现是「ht 和intset」，ht（哈希表）前面已经详细了解过，下面我们来看看inset类型的存储结构。

inset 也叫做整数集合，用于保存整数值的数据结构类型，它可以保存int16_t、int32_t 或者int64_t 的整数值。

2.5、zset

zset 可能是 Redis 提供的最为特色的数据结构，它也是在面试中面试官最爱问的数据结构。它类似于 Java 的 SortedSet 和 HashMap 的结合体

1、一方面它是一个 set，保证了内部 value 的唯一性

2、另一方面需要提供按照 score 来排序的功能，还需要能够指定 score 的范围来获 取 value 列表的功能，这就需要另外一个结构「跳跃列表」。

3、还有一方面它需要一个 hash 结构来存储 value 和 score 的 对应关系

2.5.1、常用命令

2.5.2、使用场景

1、排行榜系统

2、 zset 可以用来存 粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间进行排序。

3、zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们 可以对成绩按分数进行排序就可以得到他的名次。

2.5.3、数据结构

2.5.3.1、skiplsit

看下文

3、数据结构解析

3.1、ziplist

压缩列表是一块连续的内存空间。它将所有的元素紧挨着一起存储，分配的是一块连续的内存。没有任何冗余空隙

struct ziplist<T> {
  int32 zlbytes; // 整个压缩列表占用字节数
  int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
  int16 zllength; // 元素个数
  T[] entries; // 元素内容列表，挨个挨个紧凑存储  
  int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}

entry 块随着容纳的元素类型不同，也会有不一样的结构。

struct entry {
  int<var> prevlen; // 前一个 entry 的字节长度 int<var> encoding; // 元素类型编码
  int<var> encoding; // 元素类型编码
  optional byte[] content; // 元素内容
}

1、压缩列表为什么支持双向遍历？

答：有 ztail_offset 这个字段，用来快速定位到最后一 个元素，然后倒着遍历，entry中它的 prevlen 字段表示前一个 entry 的字节长度，当压缩列表倒着遍历时，需要通过这 个字段来快速定位到下一个元素的位置。

3.1.1、prevlen

prevlen 表示前一个entry 的字节长度，使用如下方式进行编码：

1、当前一个entry的长度小于254(0xFE)(255是个特殊字符，被zlend使用)字节时，该字段会使用一个字节(即8 bit)表示长度；

2、当长度大于或等于254时，将会使用5个字节，此时第一个字节会被设置为254(0xFE)来表示一个较大的数值，后续4个字节表示前面一个entry的长度。

第一个字节是 0xFE(254)，剩余四个字节表示字符串长度。你可能会觉得用 5 个字节来 表示字符串长度，是不是太浪费了？

答案：我们可以算一下，当字符串长度比较长的时候，其实 5 个字节也只占用了到(5/(254+5))<2%的空间(这里的254表示的是字符串的的长度)。

因此，prevlen的编码为：

⬤ 如果前一个entry的长度小于254，编码为：

+-------+--------+-----+
|prevlen|encoding|entry| 
+-------+--------+-----+

⬤ 如果前一个entry的长度大于254，编码如下:

+----+---------------+--------+-----+
|0xFE|4 bytes prevlen|encoding|entry| 
+----+---------------+--------+-----+

3.1.2、encoding

entry的encoding字段取决于entry的内容。 encoding 中的第一个字节总是用于判定entry的类型，encoding 字段存储了元素内容的编码类型信息，ziplist 通过这个字段来决定后面的content 内容的形式。

​

1、当entry为字符串时，encoding的第一个字节的前2bit保存了编码类型（短、中、长字符串），剩余的bit位表示字符串的长度。

2、当entry为整数时，encoding仅占用1个字节，encoding的前2bit都设置为1，后续的2bit用于指定整数的类型，如int16_t，int32_t。举例如下：

Redis 为了节约存储空间，对 encoding 字段进行了相当复杂的设计。Redis 通过这个字 段的前缀位来识别具体存储的数据形式。下面我们来看看 Redis 是如何根据 encoding 的前缀 位来区分内容的:

1、00xxxxxx 最大长度位 63 的短字符串(x有6个， 2^6-1 = 63)，后面的 6 个位存储字符串的位数，剩余的字节就是字符串的内容。

2、01xxxxxx xxxxxxxx 中等长度的字符串(x有14个，2^14-1 = 16383)，后面 14 个位来表示字符串的长度，剩余的 字节就是字符串的内容。

3、10000000 aaaaaaaa bbbbbbbb cccccccc dddddddd 特大字符串，需要使用额外 4 个字节 来表示长度。第一个字节前缀是 10，剩余 6 位没有使用，统一置为零。后面跟着字符串内容。不过这样的大字符串是没有机会使用的，压缩列表通常只是用来存储小数据的。

4、11000000 表示 int16，后跟两个字节表示整数。

5、11010000 表示 int32，后跟四个字节表示整数。

6、11100000 表示 int64，后跟八个字节表示整数。

7、11110000 表示 int24，后跟三个字节表示整数。

8、11111110 表示 int8，后跟一个字节表示整数。

9、11111111 表示 ziplist 的结束，也就是 zlend 的值 0xFF。

10、1111xxxx 表示极小整数，xxxx 的范围只能是 (0001~1101), 也就是 1~13，因为0000、1110、1111 都被占用了。读取到的 value 需要将 xxxx 减 1，也就是整数 0~12 就是 最终的 value。

注意到 content 字段在结构体中定义为 optional 类型，表示这个字段是可选的，对于很小的整数而言，它的内容已经内联到 encoding 字段的尾部了。

3.1.3、增加元素

因为 ziplist 都是紧凑存储，没有冗余空间 (对比一下 Redis 的字符串结构)。 意味着插 入一个新的元素就需要调用 realloc 扩展内存。

取决于内存分配器算法和当前的 ziplist 内存 大小

1、realloc 可能会重新分配新的内存空间，并将之前的内容一次性拷贝到新的地址

2、也可能在原有的地址上进行扩展，这时就不需要进行旧内容的内存拷贝。

如果ziplist 占据内存太大，重新分配内存和拷贝内存就会有很大的消耗。所以 ziplist 不适合存储大型字符串，存储的元素也不宜过多。

3.1.4、级联更新/删除

前面提到每个 entry 都会有一个 prevlen 字段存储前一个 entry 的长度。如果内容小于 254 字节，prevlen 用 1 字节存储，否则就是 5 字节。

这意味着如果某个 entry 经过了修改 操作从 253 字节变成了 254 字节，那么它的下一个 entry 的prevlen 字段就要更新，从 1 个字节扩展到 5 个字节;如果这个 entry 的长度本来也是 253 字节，那么后面 entry 的 prevlen 字段还得继续更新。

如果ziplist 里面每个 entry 恰好都存储了 253 字节的内容，那么第一个 entry 内容的 修改就会导致后续所有 entry 的级联更新，这就是一个比较耗费计算资源的操作。

问题1：删除中间的某个节点也可能会导致级联更新，读者可以思考一下为什么?

答案：因为删除会导致被删除节点的上一个节点的entry连接被删除节点的下一个节点的entry

3.2、ht：字典

dict 是 Redis 服务器中出现最为频繁的复合型数据结构，除了 hash 结构的数据会用到字典外，

1、整个 Redis 数据库的所有 key 和 value 也组成了一个全局字典，

2、带过期时间的 key 集合也是一个字典。

3、zset 集合中存储 value 和 score 值的映射关系也是通过 dict 结构实现的。

struct RedisDb {
  dict* dict; // all keys key=>value
  dict* expires; // all expired keys key=>long(timestamp) ...
}


struct zset {
  dict *dict; // all values zskiplist *zsl;
}

3.2.1、字典内部结构

dict 结构内部包含两个 hashtable（新数组和旧数组），通常情况下只有一个 hashtable 是有值的。这意味着要操作处于 rehash 中的字典，需要同时访问新旧两个数组结构。如果在旧数组下面找不到元素，还需要去新数组下面去寻找

但是在dict 扩容缩容时，需要分配新的 hashtable，然后进行渐进式搬迁，这时候两个 hashtable 存储的分别是旧的 hashtable 和新的 hashtable。待搬迁结束后，旧的 hashtable 被删除，新的hashtable 取而代之。

struct dict { 
  dictht ht[2]; 
  ……
}

所以，字典数据结构的精华就落在了 hashtable 结构上了。hashtable 的结构和 ava 的HashMap 几乎是一样的，都是通过分桶的方式解决hash 冲突。第一维是数组，第二维是链表。数组中存储的是第二维链表的第一个元素的指针。

struct dictht {
  dictEntry** table; // 二维
  long size; // 第一维数组的长度 
  long used;  hash 表中的元素个数 ...
}



struct dictEntry {
  void* key;
  void* val;
  dictEntry* next; // 链接下一个 entry 

}

3.2.2、渐进式 rehash

大字典的扩容是比较耗时间的，需要重新申请新的数组，然后将旧字典所有链表中的元素重新挂接到新的数组下面，这是一个 O(n)级别的操作，作为单线程的 Redis 表示很难承受 这样耗时的过程。步子迈大了会扯着蛋，所以 Redis 使用渐进式 rehash 小步搬迁。虽然慢一 点，但是肯定可以搬完。

1、搬迁操作埋伏在当前字典的后续指令中(来自客户端的 hset/hdel 指令等)

2、但是有可能客户端闲下来了，没有了后续指令来触发这个搬迁，那么 Redis 就置之不理了么?当然不会，优雅的 Redis 怎么可能设计的这样潦草。Redis 还会在定时任务中对字典进行主动搬迁。

3.3.3、hash 函数

hashtable 的性能好不好完全取决于 hash 函数的质量。hash 函数如果可以将 key 打散 的比较均匀，那么这个 hash 函数就是个好函数。

Redis 的字典默认的 hash 函数是 siphash。siphash 算法即使在输入key 很小的情况下，也可以产生随机性特别好的输出，而 且它的性能也非常突出。对于 Redis 这样的单线程来说，字典数据结构如此普遍，字典操作 也会非常频繁，hash 函数自然也是越快越好。

3.3.4、hash 攻击

如果 hash 函数存在偏向性，黑客就可能利用这种偏向性对服务器进行攻击。

存在偏向 性的 hash 函数在特定模式下的输入会导致 hash 第二维链表长度极为不均匀，甚至所有的 元素都集中到个别链表中，直接导致查找效率急剧下降，从 O(1)退化到 O(n)。有限的服务器 计算能力将会被 hashtable 的查找效率彻底拖垮。这就是所谓 hash 攻击。

3.3.5、扩容条件

1、正常情况下，当 hash 表中元素的个数等于第一维数组的长度时，就会开始扩容，扩容 的新数组是原数组大小的 2 倍。

2、不过如果 Redis 正在做 bgsave，为了减少内存页的过多分离 (Copy On Write)，Redis 尽量不去扩容 (dict_can_resize)，但是如果 hash 表已经非常满 了，元素的个数已经达到了第一维数组长度的 5 倍 (dict_force_resize_ratio)，说明 hash 表 已经过于拥挤了，这个时候就会强制扩容

3.3.6、缩容条件

缩容不会考虑 Redis 是否正在做 bgsave。

当 hash 表因为元素的逐渐删除变得越来越稀疏时，Redis 会对 hash 表进行缩容来减少，hash 表的第一维数组空间占用。缩容的条件是元素个数低于数组长度的 10%。

3.3、skiplist：跳跃列表

Redis 的 zset 是一个复合结构

1、一方面它是一个 set，保证了内部 value 的唯一性

2、另一方面需要提供按照 score 来排序的功能，还需要能够指定 score 的范围来获 取 value 列表的功能，这就需要另外一个结构「跳跃列表」。

3、还有一方面它需要一个 hash 结构来存储 value 和 score 的 对应关系(我的理解k 是value,v是score)

3.3.1、skiplist：思想

Skip List主要思想是将链表与二分查找相结合,它维护了一个多层级的链表结构（用空间换取时间），可以把Skip List看作一个含有多个行的链表集合，每一行就是一条链表，这样的一行链表被称为一层，每一层都是下一层的”快速通道”，即如果x层和y层都含有元素a，那么x层的a会与y层的a相互连接（垂直）。

最底层的链表是含有所有节点的普通序列，而越接近顶层的链表，含有的节点则越少。

因为 zset 要支持随机的插入和删除，所以它不好使用数组来表示。我们先看一个普通的 链表结构。

问题：我们需要这个链表按照 score 值进行排序。这意味着当有新元素需要插入时，要定位到特定位置的插入点，这样才可以继续保证链表是有序的。通常我们会通过二分查找来找到插 入点，但是二分查找的对象必须是数组，只有数组才可以支持快速位置定位，链表做不到， 那该怎么办?

1、想想一个创业公司，刚开始只有几个人，团队成员之间人人平等，都是联合创始人。随 着公司的成长，人数渐渐变多，团队沟通成本随之增加。

2、这时候就会引入组长制，对团队进行划分。每个团队会有一个组长。开会的时候分团队进行，多个组长之间还会有自己的会议 安排。

3、公司规模进一步扩展，需要再增加一个层级 —— 部门，每个部门会从组长列表中推 选出一个代表来作为部长。部长们之间还会有自己的高层会议安排。

3.3.1.1、设计总结

跳跃列表就是类似于这种层级制（想想你老家在世界地图中的位置:亚洲- ->中国->安徽省->安庆市->枞阳县->汤沟镇->田间村->xxxx 号，也是这样一个类似的结构）

1、最下面一层所有的元素都会串起来。然后每隔几个元素挑选出一个代表来，再将这几个代表使用另外一级指针串起来。

2、然后在这些代表里再挑出 二级代表，再串起来。最终就形成了金字塔结构。

「跳跃列表」之所以「跳跃」，是因为内部的元素可能「身兼数职」，比如上图中间的 这个元素，同时处于 L0、L1 和 L2 层，可以快速在不同层次之间进行「跳跃」。

SkipList的设计初衷是作为替换平衡树的一种选择

1、我们都知道，AVL树有着严格的O(logN)的查询效率，但是由于插入过程中可能需要多次旋转，导致插入效率较低，因而才有了在工程界更加实用的红黑树

2、但是红黑树有一个问题就是在并发环境下使用不方便，比如需要更新数据时，而红黑树有个平衡的过程，在这个过程中会涉及到较多的节点，需要锁住更多的节点，从而降低了并发性能

3、Skip 需要更新的部分比较少，锁的东西也更少，结构也更加简单，这个定位的算法复杂度将会降到 O(lg(n))

4、redis 经常查有范围操作，这样利用跳表里面的双向链表，可以方便地操作。另外还有缓存区域化（cache locality）不会比*衡树差。

5、跳表的一个缺点是耗内存（我的理解：因为要重复分层存节点，分层的时候需要知道前面和后面的节点），但是作者也说了，可以调参数来降低内存消耗，和那些*衡树结构达到差不多。

3.3.2、skiplist 结构

zset 的内部实现是一个 hash 字典加一个跳跃列表 (skiplist)。`

下图就是跳跃列表的示意图，图中只画了四层，每一个 kv 块对应的结构如下面的代码中的 zslnode 结构

1、kv zskiplist的头结点不是一个有效的节点， header 也是这个结构，只不过 value 字段是 null 值——无效的，score 是Double.MIN_VALUE，用来垫底的，它ZSKIPLIST_MAXLEVEL(32)层，每层的forward指向该层跳跃表的第一个节点，若没有则为null

2、kv 之间使用指针串起来形成了双向链表结构，它们是有序排列的，从小到大。

3、不同的 kv 层高可能不一样，层数越高的 kv 越少。同一层的 kv会使用指针串起来。每一个层元素的遍历都是从 kv header 出发。

4、也正是因为层数一般不高，所以遍历的时候从顶层开始往下遍历会非常浪费。因此，跳跃列表会记录一下当前的最高层数 maxLevel，遍历时从这个 maxLevel 开始遍历性能就会提高很多。

​

struct zsl {
  zslnode* header;
  int maxLevel;
  map<string, zslnode*> ht; // hash 结构的所有键值对
}

struct zslforward {
  String value;
  double score;
  zslforward*[] forwards; // 多层连接指针
  zslnode* backward; // 回溯指针
}

3.3.3、查找过程

1、需要从 header 的最高层开始遍历找到第一个 节点 (最后一个比「我」小的元素)，

2、然后从这个节点开始降一层再遍历找到第二个节点 (最 后一个比「我」小的元素)，

3、然后一直降到最底层进行遍历就找到了期望的节点 (最底层的最 后一个比我「小」的元素)。

比如我们要查找key为19的结点，那么我们不需要逐个遍历，而是按照如下步骤:

1、从header出发，从高到低的level进行查找，先索引到9这个结点，发现9 < 19,继续查找(然后在level = 2这层)，查找到21这个节点，由于21 >19, 所以结点不往前走，而是level由2降低到1

2、然后索引到17这个节点，由于17 < 19, 所以继续往后，索引到21这个结点，发现 21 > 19, 所以level由1降低到0

3、在结点17上，level = 0 索引到 19 ,查找完毕。

4、如果在level = 0 这层没有查找到，那么说明不存在key为 19的节点，查找失败

3.3.4、随机层数

3.3.4.1、层数限制

Redis 跳跃表默认允许最大的层数是 32，被源码中 ZSKIPLIST_MAXLEVEL = 32 定义

1、看下面的源码，（Level[0]开始）直观上期望（实际是25%）的目标是 50% 的概率被分配到 Level，25% 的概率被分配到 Level2，12.5% 的概率被分配到 Level3。

Redis 标准源码中的晋升概率只有 25%，也就是代码中的 ZSKIPLIST_P 的值。所 以官方的跳跃列表更加的扁平化，层高相对较低，在单个层上需要遍历的节点数量会稍多一 点。

2、当 Level[0] (第一层)有 2^64 个元素时，才能达到 32 层，所以定义 32 完全够用了

//random() 返回一个0-1的随机数
// ZSKIPLIST_P = 1/4
// ZSKIPLIST_MAXLEVEL = 32
int zslRandomLevel(void) {
  int level = 1;
  while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
    level += 1;
  return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

3.3.4.1、如何确定层数？

1、首先，每个节点肯定都有第1层指针

2、如果一个节点有第i层(i >= 1)指针（即节点已经在第1层到第i层链表中），那么它有第( i + 1)层指针的概率为p，因为要求random() < p。

3、节点最大的层数不允许超过一个最大值，记为MaxLevel = 32。

//伪代码如下：
//random() 返回一个0-1的随机数
// p = 1/4
// MaxLevel = 32
randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。节点层数至少为1。而大于1的节点层数，满足一个概率分布定量的分析如下：

☼ 节点层数恰好等于1的概率为1-p：要求 random() < p 不成立，只有1-p的时候不成立，所以概率为1-p

☼ 节点层数大于等于2的概率为p：要求 random() < p成立，所以节点层数大于等于2的概率为p；

☼ 节点层数恰好等于2的概率为p(1-p)：

☼ 节点层数大于等于3的概率为p^2

☼ 节点层数恰好等于3的概率为p^2(1-p)。

☼ 节点层数大于等于4的概率为p^3，

☼ 节点层数恰好等于4的概率为p^3(1-p)。

☼ ……

☼ 节点层数恰好等于32的概率为p^32(1-p) -> 2^64-1/4 -> 2^64

3.3.4、插入过程：

1、首先我们在搜索合适插入点的过程中将「搜索路径」摸出来了，然后就可以开始创建新节点了

2、创建的时候需要给这个节点随机分配一个层数

3、再将搜索路径上的节点和这个新节点通过前向后向指针串起来（双向链表，很好串的）。如果分配的新节点的高度高于当前跳跃列表的最大高度，就需要更新一下跳跃列表的最大高度maxLevel

比如上图中要插入key为17的结点

1、一路查找到12,由于12 < 17,而12的下一个结点19 > 17,因而满足条件

2、创建新结点，并且产生一个在1 到 MAX_LEVEL 之间的随机level值作为该结点的level

3、调整指针指向，

3.3.5、删除过程

1、删除过程和插入过程类似，都需先把这个「搜索路径」找出来。

2、然后对于每个层的相关 节点都重排一下前向后向指针就可以了。

3、如果删除了最高的层数的节点，同时还要注意更新一下最高层数 maxLevel。

移除

3.3.6、更新过程

当我们调用 zadd 方法时

1、如果对应的 value 不存在，那就是插入过程。

2、如果这个value 已经存在了，只是调整一下 score 的值，那就需要走一个更新的流程。

⬤ 假设这个新的score 值不会带来排序位置上的改变，那么就不需要调整位置，直接修改元素的 score 值就可以了。

当我们使用zadd命令更新存在值的分数时，如果分数增量很小，元素等级将保持不变，我认为我们只需要更改分数，而无需删除和重新插入。 为了确保等级不变，我们可以使用当前节点的前向和后向指针访问同级节点，以测试新分数是否仍在上一个节点和下一个节点的分数之间

⬤ 但是如果排序位置改变了，那就要调整位置。Redis的策略就是先删除这个元素，再插入这个元素，需要经过两次路径搜索。

3.3.6、如果 score 值都一样呢

问题：在一个极端的情况下，zset 中所有的 score 值都是一样的，zset 的查找性能会退化为 O(n) 么?

答案：Redis 作者自然考虑到了这一点，所以 zset 的排序元素不只看 score 值，如果 score 值相同还需要再比较 value 值 (字符串比较后排序。

3.3.7、元素排名是怎么算出来的?

zset 可以获取元素的排名 rank。那这个 rank 是如何算出来的?

答案：如果仅仅使用上面的结构，rank 是不能算出来的。Redis 在 skiplist 的 forward 指针上进行了优化，给每一个 forward 指针都增加了 span 属性

span 是「跨度」的意思，表示从前一个节点沿着当前层的 forward 指针跳到当前这个节点中间会跳过多少个节点。Redis 在插入删除操作时会小心翼翼地更新 span 值的大小。

要计算一个元素的排名时，只需要将「搜索路径」上的经过的所有节点的跨 度 span 值进行叠加就可以算出元素的最终 rank 值。

struct zslforward {
  zslnode* item;
  long span;    // 跨度
}

struct zsl {
  String value;
  double score;
  zslforward*[] forwards; // 多层连接指针
  zslnode* backward; // 回溯指针
}

3.5、quicklist：快速列表

Redis 早期版本存储 list 列表数据结构使用的是压缩列表 ziplist 和普通的双向链表linkedlist，也就是元素少时用 ziplist，元素多时用 linkedlist。

// 链表
struct list {
  listNode *head;
  listNode *tail;
  long length; 
}

// 链表的节点
struct listNode<T> {
  listNode* prev; listNode* next; T value;
}

quicklist登场

**考虑到链表的附加空间相对太高，prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节)，另外每个节点的内存都是单独分配，会加剧内存的碎片化，影响内存管理效率。 **

后续版本对列表数据结构进行了改造，使用 quicklist 全面代替了 ziplist 和 linkedlist。

总结：为了解决 linkedlist 的双向指针占用内存过多，以及 ziplist 数据量太大性能就变差的问题，结合他们两个产出了新的数据结构，也就是 quicklist.

它将多个 ziplist 通过前后节点的指针连接起来，在一定程度上解决了上面的问题，提高了 Redis 的响应速度。

> rpush codehole go java python
  (integer) 3
  
> debug object codehole
  Value at:0x7fec2dc2bde0 refcount:1 encoding:quicklist serializedlength:31 lru:6101643 lru_seconds_idle:5 ql_nodes:1 ql_avg_node:3.00 ql_ziplist_max:-2 ql_compressed:0 ql_uncompressed_size:29

注意观察上面输出字段 encoding 的值。quicklist 是 ziplist 和 linkedlist 的混合体，它 将 linkedlist 按段切分，每一段使用ziplist 来紧凑存储，多个 ziplist 之间使用双向指针串 接起来。

3.5.1、每个 ziplist 存多少元素

quicklist 内部默认单个 ziplist 长度为 8k 字节，超出了这个字节数，就会新起一个 ziplist。

ziplist 的长度由配置参数 list-max-ziplist-size 决定

# 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

3.5.2、压缩深度

压缩的实际深度由配置参数 list- compress-depth决定。

⬤ quicklist 默认的压缩深度是 0，也就是不压缩。

⬤ 为了支持快速的 push/pop 操作，quicklist 的首尾两个 ziplist 不压 缩，此时深度就是 1。

⬤ 如果深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二 个 ziplist 都不压缩。

因为如果将一个 ziplist 压缩，那么要从它里面读取值，必然要先解压，会造成性能变差，因此可以将两端即将被操作的节点不压缩，其他的选择压缩。

3.6、intset

intset 和 dict 都是 set 命令的底层数据结构

intset 是一个紧凑的整数数组结构，它用于存放元素都是整数的并且元素个数 较少的 set 集合。Redis 支持 set 集合动态从 uint16 升级到 uint32， 再升级到 uint64。 当遇到添加数据为字符串，即不能表示为整数时，Redis 会把数据结构转换为 dict，即把 intset 中的数据全部搬迁到 dict。

◯ 元素类型只能为数字。

◯ 元素有三种类型：int16_t、int32_t、int64_t。

◯ 元素有序，不可重复，intset 和 sds 一样，内存连续，就像数组一样。

3.3.1、数据结构

⬤ encoding 用于保存当前集合的编码，有16位，32位和64位三种；（虽然contents部分指明的类型是int8_t，但是数据并不以这个类型存放)

⬤ length 保存了当前整数集合中保存的数据数量；

contents属性则保存了具体的数据，其每个数据占用的位数由encoding属性指定，contents 字段用于保存整数，数组中的元素要求不含有重复的整数且按照从小到大的顺序排列。在读取和写入的时候，均按照指定的 encoding 编码模式读取和写入。

typedef struct intset {
    /* 编码方式 */
    uint32_t encoding;

    /* 集合包含的元素数量 */
    uint32_t length;

    /* 保存元素的数组 */
    int8_t contents[];

} 

3.3.2、添加元素

当新元素编码 > 集合编码时，表明集合需要升级，同时根据新元素值来确定所添加的位置（头部或尾部）。

当新元素编码<=集合编码时，表明集合无需升级，系统会将集合大于value的元素往后移动一位，为新元素腾出空间。

3.3.3、查找元素

查找集合元素(二分查找)，判断value 是否已存在。若元素存在，则返回 1; 反之, 返回0。

intset是一种有序的集合。当元素存在时，pos 代表该元素所在的集合下标。当元素不存在时，pos 表示该元素添加的位置。

3.3.2、升级和降级

只会升级，不会降级

升级：指的是当向低编码的整数集合中添加位数较高的数值时，就会扩容并将整数集合中的所有元素都转换为高位数的编码格式，然后把新添加的元素插入到指定位置；

升级优点：节约内存，整数集合既可以让集合保存三种不同类型的值，又可以确保升级操作只在有需要的时候进行，这样就节省了内存。

降级：不支持，一旦对数组进行升级，编码就会一直保存升级后的状态。也就是说编码格式不会改变

3.3.2.1、升级过程

1、根据新元素的类型扩展数组的空间

2、将其他的数据类型转化为与新元素的数据类型相同

3、将新元素插入到数据的合适位置，并更新encoding属性的值

举例说明：

127.0.0.1:6381> SADD numbers 1 2 3
(integer) 3
127.0.0.1:6381> SADD numbers 65535
(integer) 1

1、SADD numbers 1 2 3操作后，其intset的结构如下

2、根据新元素的类型扩展数组的空间：新添加的元素的类型为32位的整型，故一共需要的空间为(length+1)*32=4*32=127

3、将其他的数据类型转化为与新元素的数据类型相同：按照从大到小的顺序，将numbers集合中元素的类型进行转换。

首先是元素3，在所有元素中是第三小的，故将其移动到contents[2]的位置上

接下来是元素2，在所有元素中是第二小的，故将其移动到contents[1]的位置上

最后是1，在所有元素中是第一小的，故将其移动到contents[0]的位置上

将新元素插入到数据的合适位置，并更新encoding属性的值

4、最后将encoding属性的值更新为INTSET_ENC_INT32，将length的值加一

3.3.2.2、降级（无）

以上面的例子继续举例：其他的三个元素（1，2，3）的数据类型仍然还是int32_t，并不会因此而降级为int16_t

127.0.0.1:6381> SREM numbers 65535
(integer) 1

5、容器型数据结构的通用规则

5.1、create if not exists

如果容器不存在，那就创建一个，再进行操作。比如 rpush 操作刚开始是没有列表的，Redis 就会自动创建一个，然后再 rpush 进去新元素。

5.2、drop if no elements

如果容器里元素没有了，那么立即删除元素，释放内存。这意味着 lpop 操作到最后一个元素，列表就消失了。

5.3、过期时间

Redis 所有的数据结构都可以设置过期时间，时间到了，Redis 会自动删除相应的对象。

⬤ 需要注意的是过期是以对象为单位，比如一个 hash 结构的过期是整个 hash 对象的过期， 而不是其中的某个子 key。

⬤ 还有一个需要特别注意的地方是如果一个字符串已经设置了过期时间，然后你调用了set 方法修改了它，它的过期时间会消失。