Redis原理（中）

1-4-3.ZipList的连锁更新问题

ZipList的每个Entry都包含previous_entry_length来记录上一个节点的大小，长度是1个或5个字节：

如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值

如果前一节点的长度大于等于254字节，则采用5个字节来保存这个长度值，

第一个字节为0xfe，后四个字节才是真实长度数据

假设我们有N个连续的、长度为250~253字节之间的entry，

因此entry的previous_entry_length属性用1个字节即可表示，如图所示：

ZipList这种特殊情况下产生的连续多次空间扩展操作称之为连锁更新（Cascade Update）。

新增、删除都可能导致连锁更新的发生。

ZipList数据结构优点

• 压缩列表的可以看做一种连续内存空间的"双向链表"
• 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
• 如果列表数据过多，导致链表过长，可能影响查询性能
• 增或删较大数据时有可能发生连续更新问题

1-5.QuickList

QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

为了避免QuickList中的每个ZipList中entry过多，Redis提供了一个配置项：list-max-ziplist-size来限制

如果值为正，则代表ZipList的允许的entry个数的最大值

如果值为负，则代表ZipList的最大内存大小（常用）分5种情况：

• -1：每个ZipList的内存占用不能超过4kb
• -2：每个ZipList的内存占用不能超过8kb（默认值）
• -3：每个ZipList的内存占用不能超过16kb
• -4：每个ZipList的内存占用不能超过32kb
• -5：每个ZipList的内存占用不能超过64kb

QuickList数据结构优点

• 是一个节点为ZipList的双端链表
• 节点采用ZipList，解决了传统链表的内存占用问题
• 控制了ZipList大小，解决连续内存空间申请效率问题
• 中间节点可以压缩，进一步节省了内存

1-6.SkipList

SkipList（跳表）首先是链表，但与传统链表相比有几点差异：

• 元素按照升序排列存储
• 节点可能包含多个指针，指针跨度不同。

SkipList数据结构优点：

• 跳跃表是一个双向链表，每个节点都包含score和ele值
• 节点按照score值排序，score值一样则按照ele字典排序
• 每个节点都可以包含多层指针，层数是1到32之间的随机数
• 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
• 增删改查效率与红黑树基本一致，实现却更简单

1-7.RedisObject

Redis中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象

从Redis的使用者的角度来看，⼀个Redis节点包含多个database

（非cluster模式下默认是16个，cluster模式下只能是1个），

而一个database维护了从key space到object space的映射关系。

这个映射关系的key是string类型，⽽value可以是多种数据类型，

比如：string, list, hash、set、sorted set等。可以看到，key的类型固定是string，而value可能的类型是多个。

从Redis内部实现的⾓度来看，database内的这个映射关系是用⼀个dict来维护的。

dict的key固定用⼀种数据结构来表达就够了，这就是动态字符串sds。

而value则比较复杂，为了在同⼀个dict内能够存储不同类型的value，

这就需要⼀个通⽤的数据结构，这个通用的数据结构就是robj，全名是redisObject。

1-7-1.Redis的编码方式

Redis中会根据存储的数据类型不同，选择不同的编码方式，共包含11种不同类型：

1-7-2.Redis的五种数据结构

Redis中会根据存储的数据类型不同，选择不同的编码方式。每种数据类型的使用的编码方式如下：

2-Redis数据类型

2-1.String

String是Redis中最常见的数据存储类型：

其基本编码方式是RAW，基于简单动态字符串（SDS） 实现，存储上限为512mb。

如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。

申请内存时只需要调用一次内存分配函数，效率更高。

如果存储的字符串是整数值，并且大小在LONG_MAX范围内，

则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

2-2.List

Redis的List类型可以从首、尾操作列表中的元素：

在3.2版本之后，Redis统一采用QuickList来实现List：

2-3.Set

Set是Redis中的单列集合，满足下列特点：

• 不保证有序性
• 保证元素唯一
• 求交集、并集、差集

HashTable，也就是Redis中的Dict，确保元素有序，不过Dict是双列集合（可以存键、值对），不满足查询效率

Set，也就是Redis底层数据结构中的IntSet，确保元素有序，可以满足元素唯一、查询效率极高要求。

为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。

当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存

2-4.ZSet

ZSet也就是SortedSet，其中每一个元素都需要指定一个score值和member值：

• 可以根据score值排序后
• member必须唯一
• 可以根据member查询分数

zset底层数据结构必须满足键值存储、键必须唯一、可排序这几个需求

• SkipList：可以排序，并且可以同时存储score和ele值（member）
• HT（Dict）：可以键值存储，并且可以根据key找value

当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：

• 元素数量小于zset_max_ziplist_entries，默认值128
• 每个元素都小于zset_max_ziplist_value字节，默认值64

ziplist本身没有排序功能，而且没有键值对的概念，因此需要有zset通过编码实现：

• ZipList是连续内存，因此score和element是紧挨在一起的两个entry， element在前，score在后
• score越小越接近队首，score越大越接近队尾，按照score值升序排列

2-5.Hash

Hash结构与Redis中的Zset非常类似：

• 都是键值存储
• 都需求根据键获取值
• 键必须唯一

区别如下：

• zset的键是member，值是score；hash的键和值都是任意值
• zset要根据score排序；hash则无需排序

Hash底层采用的编码与Zset也基本一致，只需要把排序有关的SkipList去掉即可：

Hash结构默认采用ZipList编码，用以节省内存。 ZipList中相邻的两个entry 分别保存field和value

当数据量较大时，Hash结构会转为HT编码，也就是Dict，触发条件有两个：

• ZipList中的元素数量超过了hash-max-ziplist-entries（默认512）
• ZipList中的任意entry大小超过了hash-max-ziplist-value（默认64字节）

3-Redis网络模型

3-1.用户空间和内核态空间

任何Linux发行版，其系统内核都是Linux。我们的应用都需要通过Linux内核与硬件交互

用户的应用，比如redis，mysql等其实是没有办法去执行访问我们操作系统的硬件的，

所以可以通过发行版的这个壳子去访问内核，再通过内核去访问计算机硬件

计算机硬件包括，如cpu，内存，网卡等等，内核（通过寻址空间）可以操作硬件的，

但是内核需要不同设备的驱动，有了这些驱动之后，内核就可以去对计算机硬件去进行 内存管理，文件系统的管理，进程的管理等等

内核本身上来说也是一个应用，所以他本身也需要一些内存，cpu等设备资源，

用户应用本身也在消耗这些资源，如果不加任何限制，用户去操作随意的去操作我们的资源，就有可能导致一些冲突，

甚至有可能导致我们的系统出现无法运行的问题，因此需要把用户和内核隔离开

应用程序也好，还是内核空间也好，都是没有办法直接去物理内存的，

而是通过分配一些虚拟内存映射到物理内存中，内核和应用程序去访问虚拟内存的时候，就需要一个虚拟地址，

这个地址是一个无符号的整数，比如一个32位的操作系统，他的带宽就是32，他的虚拟地址就是2的32次方，也就是说他寻址的范围就是0~2的32次方， 这片寻址空间对应的就是2的32个字节，就是4GB，

这个4GB，会有3个GB分给用户空间，会有1GB给内核系统

在linux中，他们权限分成两个等级，0和3，

用户空间只能执行受限的命令（Ring3），而且不能直接调用系统资源，

必须通过内核提供的接口来访问内核空间可以执行特权命令（Ring0）

比如：

Linux系统为了提高IO效率，会在用户空间和内核空间都加入缓冲区：

写数据时，要把用户缓冲数据拷贝到内核缓冲区，然后写入设备

读数据时，要从设备读取数据到内核缓冲区，然后拷贝到用户缓冲区

3-2.阻塞IO

应用程序想要去读取数据，是无法直接去读取磁盘数据的，

需要先到内核里边去等待内核操作硬件拿到数据，需要等待的

等到内核从磁盘上把数据加载出来之后，再把这个数据写给用户的缓存区，

如果是阻塞IO，那么整个过程中，用户从发起读请求开始，一直到读取到数据，都是一个阻塞状态。

阶段一：

• 用户进程尝试读取数据（比如网卡数据）
• 此时数据尚未到达，内核需要等待数据
• 此时用户进程也处于阻塞状态

阶段二：

• 数据到达并拷贝到内核缓冲区，代表已就绪
• 将内核数据拷贝到用户缓冲区
• 拷贝过程中，用户进程依然阻塞等待
• 拷贝完成，用户进程解除阻塞，处理数据

可以看到，阻塞IO模型中，用户进程在两个阶段都是阻塞状态。

3-3.非阻塞IO

非阻塞IO的recvfrom操作会立即返回结果而不是阻塞用户进程。

阶段一：

• 用户进程尝试读取数据（比如网卡数据）
• 此时数据尚未到达，内核需要等待数据
• 返回异常给用户进程
• 用户进程拿到error后，再次尝试读取
• 循环往复，直到数据就绪

阶段二：

• 将内核数据拷贝到用户缓冲区
• 拷贝过程中，用户进程依然阻塞等待
• 拷贝完成，用户进程解除阻塞，处理数据
• 可以看到，非阻塞IO模型中，用户进程在第一个阶段是非阻塞，第二个阶段是阻塞状态。虽然是非阻塞，但性能并没有得到提高。而且盲等机制会导致CPU空转，CPU使用率暴增。