Redis - 原理篇-1

Redis(原理篇)

一、数据结构

1.1 动态字符串SDS

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。

不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题

获取字符串的长度需要通过计算（因为c语言中其实没有字符串而是字符数组，通过最后的 ‘\0’ 来表示结束，所以在计算数组长度的时候需要减去这个’\0’）

非二进制安全(因为是通过使用 ‘\0’ 来表示结束那么在这个字符串的中间都不能有特殊符号)

不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。

例如，我们执行命令：

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“虎哥”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“虎哥”的SDS。

Redis是C语言实现的，其中SDS是一个结构体，源码如下：

例如，一个包含字符串“name”的sds结构如下：

SDS之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为“hi”的SDS：

假如我们要给SDS追加一段字符串“,Amy”，这里首先会申请新内存空间：

• 如果新字符串小于1M，则新空间为扩展后字符串长度的两倍+1；
  
• 如果新字符串大于1M，则新空间为扩展后字符串长度+1M+1。称为内存预分配。
  

动态字符串优点：

1. 获取字符串长度的时间复杂度为0(1)[因为长度已经存在于结构体中]
2. 支持动态扩容
3. 减少内存分配次数
4. 二进制安全（可以存储特殊字符，无需考虑结束符的问题）

.2 Redis数据结构-IntSet

IntSet是Redis中set集合的一种实现方式，基于整数数组来实现，并且具备长度可变、有序等特征。

结构如下：

其中的encoding包含三种模式，表示存储的整数大小不同：

为了方便查找，Redis会将intset中所有的整数按照升序依次保存在contents数组中，结构如图：

寻址公式：startPtr【开始的起始地址为0】+（sizeof(int16) 【数据类型的字节大小】* index【它对应的下标】）就可以快速找到对应的数据

现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：

• encoding：4字节
• length：4字节
• contents：2字节 * 3 = 6字节

1.2.1 IntSet 升级

现在，假设有一个intset,元素为{5,10,20}，采用的编码是INTSET_ENC_INT16，则每个整数占2字节：

我们向该其中添加一个数字：50000，这个数字超出了int16_t的范围，intset会自动升级编码方式到合适的大小。以当前案例来说流程如下：

升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组

倒序依次将数组中的元素拷贝到扩容后的正确位置（倒叙放是为了防止，正序放的时候，字节扩大的时候会将后面的数据给覆盖掉）

将待添加的元素放入数组末尾

最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

在length+prepend中如果我们之前判断的prepend如果是正数那么就是0即在倒序插入的时候原来元素的角标不会改变，只在扩容后的数组或者原数组最后加上新的数据就行，如果为负数那么prepend的值就是为1，那么所有元素就要向前移动一位

小总结：

Intset可以看做是特殊的整数数组，具备一些特点：

Redis会确保Intset中的元素唯一、有序

具备类型升级机制，可以节省内存空间

• 底层采用二分查找方式来查询
  
  

1.3 Redis数据结构-Dict

我们知道Redis是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过Dict来实现的。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

当我们向Dict添加键值对时，

Redis首先根据key计算出hash值（h），然后利用 h & sizemask来计算元素应该存储到数组中的哪个索引位置。我们存储k1=v1，假设k1的哈希值h =1，则1&3 =1，因此k1=v1要存储到数组角标1位置。

Dict由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict）

1.3.1 Dict 扩容 / 收缩

Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。

Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程（因为这种操作对性能要求高，如果我在在进行rehash的操作就可能导致阻塞）；

哈希表的 LoadFactor > 5 ；

dict_force_resize_ratio是5

HASHTABLE_MIN_FILL是10

Dict的rehash

不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。过程是这样的：

计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：

如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n

如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）

按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]

设置dict.rehashidx = 0，标示开始rehash

每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]

将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

将rehashidx赋值为-1，代表rehash结束

在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

整个过程可以描述成：

当ht[0]大小只有4的时候这个时候，新添加了一个dictEntry，这个时候就ht[1]就会申请一个大小 >=userd+1大小的2^n的dictht1，将原来在ht[0]的数据渐进的转移到ht[1]中，最后ht[0]指针指向ht[1],将dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存

1.4 Redis数据结构-ZipList

ZipList 是一种特殊的“双端链表” ，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入/弹出操作, 并且该操作的时间复杂度为 O(1)。

这里的尾偏移量的作用就是为了可以直接定位到最后一个entry节点，当我们知道了起始地址在加上尾偏移量就可以找到最后一个节点

ZipListEntry

ZipList 中的Entry并不像普通链表那样记录前后节点的指针，因为记录两个指针要占用16个字节，浪费内存。而是采用了下面的结构：

previous_entry_length：前一节点的长度，占1个或5个字节。

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

如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据

encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节

contents：负责保存节点的数据，可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412E

Encoding编码

ZipListEntry中的encoding编码分为字符串和整数两种：

字符串：如果encoding是以“00”、“01”或者“10”开头，则证明content是字符串

例如，我们要保存字符串：“ab”和 “bc”

ZipListEntry中的encoding编码分为字符串和整数两种：

• 整数：如果encoding是以“11”开始，则证明content是整数，且encoding固定只占用1个字节

1.4.1 Redis数据结构-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 Redis数据结构-QuickList

问题1：ZipList虽然节省内存，但申请内存必须是连续空间，如果内存占用较多，申请内存效率很低。怎么办？

答：为了缓解这个问题，我们必须限制ZipList的长度和entry大小。

问题2：但是我们要存储大量数据，超出了ZipList最佳的上限该怎么办？

答：我们可以创建多个ZipList来分片存储数据。

问题3：数据拆分后比较分散，不方便管理和查找，这多个ZipList如何建立联系？

答：Redis在3.2版本引入了新的数据结构QuickList，它是一个双端链表，只不过链表中的每个节点都是一个ZipList。

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

如果值为正，则代表ZipList的允许的entry个数的最大值(但是这样的话，如果我每一个entry都很大的话，对内存还是有负担)

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

-1：每个ZipList的内存占用不能超过4kb

-2：每个ZipList的内存占用不能超过8kb

-3：每个ZipList的内存占用不能超过16kb

-4：每个ZipList的内存占用不能超过32kb

-5：每个ZipList的内存占用不能超过64kb其默认值为 -2：

以下是QuickList的和QuickListNode的结构源码：

我们接下来用一段流程图来描述当前的这个结构

总结：

QuickList的特点：

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

1. 6 Redis数据结构-SkipList

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

元素按照升序排列存储

节点可能包含多个指针，指针跨度不同。

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

元素按照升序排列存储

节点可能包含多个指针，指针跨度不同。

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

元素按照升序排列存储

节点可能包含多个指针，指针跨度不同。

总结

SkipList的特点：

跳跃表是一个双向链表，每一个节点都包含score和ele值

节点按照score值排序，score值一样则按照ele字典排序

每个节点都可以包含多层指针，层数是1到32之间的随机数

不同层指针到下一个节点的跨度不同，层级越高，跨度越大

增删改查效率与红黑树基本一致，实现却更简单

1.7 Redis数据结构-RedisObject

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

1、什么是redisObject：

从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。

Redis的编码方式

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

五种数据结构

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

数

1.8 Redis数据结构-String

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

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

如果存储的SDS长度小于44字节，则会采用EMBSTR编码，此时object head与SDS是一段连续空间。申请内存时只需要调用一次内存分配函数，效率更高。

（1）底层实现⽅式：动态字符串sds 或者 long String的内部存储结构⼀般是sds（Simple Dynamic String，可以动态扩展内存），但是如果⼀个String类型的value的值是数字，那么Redis内部会把它转成long类型来存储，从⽽减少内存的使用。

如果存储的字符串内存大小是小于44个字节的那么，就会采用的是EMBSTR编码

确切地说，String在Redis中是⽤⼀个robj来表示的。

用来表示String的robj可能编码成3种内部表⽰：OBJ_ENCODING_RAW，OBJ_ENCODING_EMBSTR，OBJ_ENCODING_INT。

其中前两种编码使⽤的是sds来存储，最后⼀种OBJ_ENCODING_INT编码直接把string存成了long型。

在对string进行incr, decr等操作的时候，如果它内部是OBJ_ENCODING_INT编码，那么可以直接行加减操作；如果它内部是OBJ_ENCODING_RAW或OBJ_ENCODING_EMBSTR编码，那么Redis会先试图把sds存储的字符串转成long型，如果能转成功，再进行加减操作。对⼀个内部表示成long型的string执行append, setbit, getrange这些命令，针对的仍然是string的值（即⼗进制表示的字符串），而不是针对内部表⽰的long型进⾏操作。比如字符串”32”，如果按照字符数组来解释，它包含两个字符，它们的ASCII码分别是0x33和0x32。当我们执行命令setbit key 7 0的时候，相当于把字符0x33变成了0x32，这样字符串的值就变成了”22”。⽽如果将字符串”32”按照内部的64位long型来解释，那么它是0x0000000000000020，在这个基础上执⾏setbit位操作，结果就完全不对了。因此，在这些命令的实现中，会把long型先转成字符串再进行相应的操作。

1.9 Redis数据结构-List

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

哪一个数据结构能满足上述特征？

LinkedList ：普通链表，可以从双端访问，内存占用较高，内存碎片较多

ZipList ：压缩列表，可以从双端访问，内存占用低，存储上限低

QuickList：LinkedList + ZipList，可以从双端访问，内存占用较低，包含多个ZipList，存储上限高

Redis的List结构类似一个双端链表，可以从首、尾操作列表中的元素：

在3.2版本之前，Redis采用ZipList和LinkedList来实现List，当元素数量小于512并且元素大小小于64字节时采用ZipList编码，超过则采用LinkedList编码。在3.2版本之后，Redis统一采用QuickList来实现List：

1.10 Redis数据结构-Set结构

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

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

以看出，Set对查询元素的效率要求非常高，思考一下，什么样的数据结构可以满足？

HashTable，也就是Redis中的Dict，不过Dict是双列集合（可以存键、值对）

Set是Redis中的集合，不一定确保元素有序，可以满足元素唯一、查询效率要求极高。

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

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

1.11 Redis数据结构-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在后(当我们查询的时候就可以直接遍历即可，当我们要找m1的score，只需要找到m1在找下一个即可)

• score越小越接近队首，score越大越接近队尾，按照score值升序排列

1.12 Redis数据结构-Hash

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

都是键值存储

都需求根据键获取值

键必须唯一

区别如下：

zset的键是member，值是score；hash的键和值都是任意值

zset要根据score排序；hash则无需排序

底层实现方式：压缩列表ziplist 或者 字典dict

当Hash中数据项比较少的情况下，Hash底层才⽤压缩列表ziplist进⾏存储数据，随着数据的增加，底层的ziplist就可能会转成dict，具体配置如下：

hash-max-ziplist-entries 512

hash-max-ziplist-value 64

当满足上面两个条件其中之⼀的时候，Redis就使⽤dict字典来实现hash。

Redis的hash之所以这样设计，是因为当ziplist变得很⼤的时候，它有如下几个缺点：

每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。

⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。

当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。

总之，ziplist本来就设计为各个数据项挨在⼀起组成连续的内存空间，这种结构并不擅长做修改操作。⼀旦数据发⽣改动，就会引发内存realloc，可能导致内存拷贝。

hash结构如下：

zset集合如下：

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

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

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

是否需要转换成HT

这里就是在判断插入的时候key是否重复

1.13 数据结构总结

IntSet（整数集合）：IntSet 是一种优化的数据结构，用于存储只包含整数值的集合。它在内存占用和性能方面都具有优势，适用于需要存储大量整数值的场景，比如计数器、唯一ID生成器等。

Dict（字典）：Dict 是 Redis 中的哈希表实现，用于存储键值对。它是 Redis 中很多数据结构的底层实现，适用于存储任意类型的键值对数据，常用于缓存数据、用户会话管理等。

ZipList（压缩列表）：ZipList 是一种紧凑的、压缩的列表实现。它在元素较少且每个元素较小的情况下可以节省内存，并且支持快速的插入和删除操作。ZipList 适用于存储较小规模的列表数据。

QuickList（快速列表）：QuickList 是一种特殊的列表实现，它将多个 ZipList 组合在一起形成一个链表结构。它可以在列表元素较多时节省内存，并且支持在列表两端进行插入和删除操作。QuickList 适用于存储较大规模的列表数据。

SkipList（跳跃表）：SkipList 是一种有序的链表数据结构，可以快速进行元素的插入、删除和查找操作。SkipList 在有序集合 ZSet 的实现中被使用，适用于需要快速的有序集合操作的场景，比如排行榜、范围查询等。

RedisObject（Redis 对象）：RedisObject 是 Redis 中所有数据结构的基础对象，它封装了不同数据结构的值和类型信息。RedisObject 在 Redis 内部使用，作为数据结构的统一表示方式。

String（字符串）：String 是最基本的数据结构，可以存储字符串、整数或者浮点数。它的使用场景非常广泛，例如缓存数据、计数器、分布式锁等。

List（列表）：List 是一个有序的字符串列表，可以在两端进行元素的插入和删除操作。它常用于实现队列、栈、消息发布与订阅等场景。

Set（集合）：Set 是一个无序的、不重复的字符串集合，支持对集合进行交集、并集、差集等操作。它适用于存储唯一值的场景，比如社交网络中的关注列表、标签系统等。

Hash（哈希）：Hash 是一个键值对的无序散列表，可以存储多个字段和对应的值。Hash 适用于存储对象，例如用户信息、商品信息等，每个字段对应对象的一个属性。

ZSet（有序集合）：ZSet 是一个有序的字符串集合，每个成员都关联一个分数，根据分数进行排序。它常用于实现排行榜、优先级队列等场景。

二、Redis网络模型

2.1 用户空间和内核态空间

服务器大多都采用Linux系统，这里我们以Linux为例来讲解:

ubuntu和Centos 都是Linux的发行版，发行版可以看成对linux包了一层壳，任何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效率，会在用户空间和内核空间都加入缓冲区：

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

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

针对这个操作：我们的用户在写读数据时，会去向内核态申请，想要读取内核的数据，而内核数据要去等待驱动程序从硬件上读取数据，当从磁盘上加载到数据之后，内核会将数据写入到内核的缓冲区中，然后再将数据拷贝到用户态的buffer中，然后再返回给应用程序，整体而言，速度慢，就是这个原因，为了加速，我们希望read也好，还是wait for data也最好都不要等待，或者时间尽量的短。