数据结构原理

Redis所有的数据结构都是基于以下这些底层数据结构支持的：

• 动态字符串SDS
• IntSet
• Dict
• ZipList
• QuickList
• SkipList
• RedisObject
• 五种数据结构

动态字符串SDS

我们都知道Redis中保存的Key是字符串，value往往是字符串或者字符串的集合。可见字符串是Redis中最常用的一种数据结构。
Redis虽然是C语言写的，不过Redis没有直接使用C语言中的字符串，因为C语言字符串存在很多问题：

1. 获取字符串长度的需要通过运算
2. 非二进制安全（不得存在特殊字符如'\0'）
3. 不可修改

Redis构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称SDS。
例如，我们执行命令：

那么Redis将在底层创建两个SDS，其中一个是包含“name”的SDS，另一个是包含“虎哥”的SDS。
Redis是C语言实现的，其中SDS是一个结构体，源码如下：

C语言的结构体可以理解成Java中的class，可以这样理解，但本质不是一个东西

并且默认提供了五种结构体来存放不同大小的字符串，例如：
uint8_t = 无符号的8个bit位的整型 = 2的8次方 - 1 - 1 = 256个字节 - 符号位 - 结束标识 = 254个字节

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

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

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

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

优点

1. 获取字符串长度的时间复杂度未O(1)
2. 支持动态扩容
3. 减少内存分配次数
4. 二进制安全

Intset

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

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

其中contents里面存放的并不是元素本身，而是一个指针，指向元素的内存空间，encoding编码方式的限制也是为了方便C语言根据角标进行寻址。

例如起始地址为0x001，存放的是5，因为数组的内存空间是连续的，找下一个元素相当于是根据编码大小16bit，也就+2个字节找到0x003，从而做到快速寻址。
现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为：

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

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

1. 升级编码为INTSET_ENC_INT32, 每个整数占4字节，并按照新的编码方式及元素个数扩容数组
2. 倒序依次将数组中的元素拷贝到扩容后的正确位置
3. 将待添加的元素放入数组末尾
4. 最后，将inset的encoding属性改为INTSET_ENC_INT32，将length属性改为4

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

• Redis会确保Intset中的元素唯一、有序
• 具备类型升级机制，可以节省内存空间
• 底层采用二分查找方式来查询
• Intset适用于数据量不大的场景

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的扩容
Dict中的HashTable就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。
Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：

• 哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；
• 哈希表的 LoadFactor > 5；

Dict除了扩容以外，每次删除元素时，也会对负载因子做检查，当LoadFactor < 0.1 时，会做哈希表收缩。
Dict的rehash
不管是扩容还是收缩，必定会创建新的哈希表，导致哈希表的size和sizemask变化，而key的查询与sizemask有关。因此必须对哈希表中的每一个key重新计算索引，插入新的哈希表，这个过程称为rehash。但是rehash过程不是一次性完成的，试想一下，试想一下，如果Dict中包含数百万的entry，要在一次rehash完成，极有可能导致主线程阻塞。因此Dict的rehash是分多次、渐进式的完成，因此称为渐进式rehash。流程如下：

1. 计算新hash表的realeSize，值取决于当前要做的是扩容还是收缩：
   1. 如果是扩容，则新size为第一个大于等于dict.ht[0].used + 1的2^n
   2. 如果是收缩，则新size为第一个大于等于dict.ht[0].used的2^n （不得小于4）
2. 按照新的realeSize申请内存空间，创建dictht，并赋值给dict.ht[1]
3. 设置dict.rehashidx = 0，标示开始rehash
4. ~~将dict.ht[0]中的每一个dictEntry都rehash到dict.ht[1] ~~
5. 每次执行新增、查询、修改、删除操作时，都检查一下dict.rehashidx是否大于-1，如果是则将dict.ht[0].table[rehashidx]的entry链表rehash到dict.ht[1]，并且将rehashidx++。直至dict.ht[0]的所有数据都rehash到dict.ht[1]
6. 将dict.ht[1]赋值给dict.ht[0]，给dict.ht[1]初始化为空哈希表，释放原来的dict.ht[0]的内存
7. 将rehashidx赋值为-1，代表rehash结束
8. 在rehash过程中，新增操作，则直接写入ht[1]，查询、修改和删除则会在dict.ht[0]和dict.ht[1]依次查找并执行。这样可以确保ht[0]的数据只减不增，随着rehash最终为空

整个过程可以描述成：
小总结
Dict的结构：

• 类似java的HashTable，底层是数组加链表来解决哈希冲突
• Dict包含两个哈希表，ht[0]平常用，ht[1]用来rehash

Dict的伸缩：

• 当LoadFactor大于5或者LoadFactor大于1并且没有子进程任务时，Dict扩容
• 当LoadFactor小于0.1时，Dict收缩
• 扩容大小为第一个大于等于used + 1的2^n
• 收缩大小为第一个大于等于used 的2^n
• Dict采用渐进式rehash，每次访问Dict时执行一次rehash
• rehash时ht[0]只减不增，新增操作只在ht[1]执行，其它操作在两个哈希表

ZipList

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

属性	类型	长度	用途
zlbytes	uint32_t	4 字节	记录整个压缩列表占用的内存字节数
zltail	uint32_t	4 字节	记录压缩列表表尾节点距离压缩列表的起始地址有多少字节，通过这个偏移量，可以确定表尾节点的地址。
zllen	uint16_t	2 字节	记录了压缩列表包含的节点数量。 最大值为UINT16_MAX （65534），如果超过这个值，此处会记录为65535，但节点的真实数量需要遍历整个压缩列表才能计算得出。
entry	列表节点	不定	压缩列表包含的各个节点，节点的长度由节点保存的内容决定。
zlend	uint8_t	1 字节	特殊值 0xFF （十进制 255 ），用于标记压缩列表的末端。

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

• previous_entry_length：前一节点的长度，占1个或5个字节。
  • 如果前一节点的长度小于254字节，则采用1个字节来保存这个长度值
  • 如果前一节点的长度大于254字节，则采用5个字节来保存这个长度值，第一个字节为0xfe，后四个字节才是真实长度数据
• encoding：编码属性，记录content的数据类型（字符串还是整数）以及长度，占用1个、2个或5个字节
• contents：负责保存节点的数据，可以是字符串或整数

ZipList中所有存储长度的数值均采用小端字节序，即低位字节在前，高位字节在后。例如：数值0x1234，采用小端字节序后实际存储值为：0x3412。
基于这个结构，ZipList可以在不影响寻址效率的前提下，不像intSet，动态的保存不同大小的节点数据，从而达到节省内存的效果。
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特性：

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

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个数的最大值
如果值为负，则代表ZipList的最大内存大小，分5种情况：

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

其默认值为 -2：

除了控制ZipList的大小，QuickList还可以对节点的ZipList做压缩。通过配置项list-compress-depth来控制。因为链表一般都是从首尾访问较多，所以首尾是不压缩的。这个参数是控制首尾不压缩的节点个数：

• 0：特殊值，代表不压缩
• 1：标示QuickList的首尾各有1个节点不压缩，中间节点压缩
• 2：标示QuickList的首尾各有2个节点不压缩，中间节点压缩
• 以此类推

其默认值为 0：

QuickList的特点：

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

SkipList

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

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

最多允许32级指针，理想情况下最大的元素存储个数可以达到232次方个，还是相当可观的。

结构：

多级指针：

SkipList的特点：

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

RedisObject

什么是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中的任意数据类型的键和值都会被封装为一个RedisObject，也叫做Redis对象，源码如下：

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

编号	编码方式	说明
0	OBJ_ENCODING_RAW	raw编码动态字符串
1	OBJ_ENCODING_INT	long类型的整数的字符串
2	OBJ_ENCODING_HT	hash表（字典dict）
3	OBJ_ENCODING_ZIPMAP	已废弃
4	OBJ_ENCODING_LINKEDLIST	双端链表
5	OBJ_ENCODING_ZIPLIST	压缩列表
6	OBJ_ENCODING_INTSET	整数集合
7	OBJ_ENCODING_SKIPLIST	跳表
8	OBJ_ENCODING_EMBSTR	embstr的动态字符串
9	OBJ_ENCODING_QUICKLIST	快速列表
10	OBJ_ENCODING_STREAM	Stream流

每种数据类型对应的编码：

数据类型	编码方式
OBJ_STRING	int、embstr、raw
OBJ_LIST	LinkedList和ZipList(3.2以前)、QuickList（3.2以后）
OBJ_SET	intset、HT
OBJ_ZSET	ZipList、HT、SkipList
OBJ_HASH	ZipList、HT

可以通过object encoding [KEY]命令来查看key的编码

五种数据类型

String

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

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

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

• 如果存储的字符串是整数值，并且大小在LONG_MAX范围内，则会采用INT编码：直接将数据保存在RedisObject的ptr指针位置（刚好8字节），不再需要SDS了。

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：

Set

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

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

无论是什么操作，都需要先判断元素是否存在，对查询效率要求极高。
所以就有了以下结构：

• 为了查询效率和唯一性，set采用HT编码（Dict）。Dict中的key用来存储元素，value统一为null。
• 当存储的所有数据都是整数，并且元素数量不超过set-max-intset-entries时，Set会采用IntSet编码，以节省内存。

Zset

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

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

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

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

于是Redis就结合了SkipList和Dict，用两个结构来实现了Zset：

由上图可看出虽然Zset功能强大，但当元素数量不多时，HT和SkipList的优势不明显，而且更耗内存。因此zset还会采用ZipList结构来节省内存，不过需要同时满足两个条件：

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

如果zset_max_ziplist_entries设置为了0，则相当于禁用了ZipList编码

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

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

Hash

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

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

区别如下：
hash

set

• 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字节）

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

• 每次插⼊或修改引发的realloc操作会有更⼤的概率造成内存拷贝，从而降低性能。
• ⼀旦发生内存拷贝，内存拷贝的成本也相应增加，因为要拷贝更⼤的⼀块数据。
• 当ziplist数据项过多的时候，在它上⾯查找指定的数据项就会性能变得很低，因为ziplist上的查找需要进行遍历。

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

Redis网络模型

Redis到底是单线程还是多线程？

• 如果仅仅聊Redis的核心业务部分（命令处理），答案是单线程
• 如果是聊整个Redis，那么答案就是多线程

在Redis版本迭代过程中，在两个重要的时间节点上引入了多线程的支持：

• Redis v4.0：引入多线程异步处理一些耗时较旧的任务，例如异步删除命令unlink
• Redis v6.0：在核心网络模型中引入多线程，进一步提高对于多核CPU的利用率

因此，对于Redis的核心网络模型，在Redis 6.0之前确实都是单线程。是利用epoll（Linux系统）这样的IO多路复用技术在事件循环中不断处理客户端情况。
为什么Redis要选择单线程？

• 抛开持久化不谈，Redis是纯内存操作，执行速度非常快，它的性能瓶颈是网络延迟而不是执行速度，因此多线程并不会带来巨大的性能提升。
• 多线程会导致过多的上下文切换，带来不必要的开销。
• 引入多线程会面临线程安全问题，必然要引入线程锁这样的安全手段，实现复杂度增高，而且性能也会大打折扣。

epoll模式

FD：文件描述符（File Descriptor）是一个从0 开始的无符号整数，用来关联Linux中的一个文件。在Linux中，一切皆文件，例如常规文件、视频、硬件设备等，当然也包括网络套接字（Socket）。

Redis IO多路复用API

Redis通过IO多路复用来提高网络性能，并且支持各种不同的多路复用实现，并且将这些实现进行封装， 提供了统一的高性能事件库API库 AE：

对外暴露了统一的接口，根据平台支持的IO多路复用形式提供了多个实现。

Redis epoll源码

1. 初始化服务，epoll_create，创建eventLoop，在内核空间创建fd监听红黑树和可读fd链表
2. 监听TCP端口获取serverSocket对应的fd
3. 将serverSocket的fd注册到红黑树中，也就是eventLoop中
4. 注册连接处理器，用于接收客户端socket
5. 注册前置处理器，用于遍历响应队列中的client，监听并绑定到响应处理器
6. 开始监听事件循环
7. 调用前置处理器
8. 执行epoll_wait等待可读的fd
9. fd就绪可读后，执行对应的事件处理器

当发生客户端连接时，会调用下面这个函数：

1. 获取客户端socket连接对应的fd
2. 注册到eventLoop
3. 监听可读时间并绑定读处理器

Redis单线程网络模型完整流程

客户端首次连接时：

1. eventLoop监听到server socket readable事件
2. 连接应答处理器tcpAcceptHandler获取client socket
3. 注册client到IO多路复用模型eventLoop中
4. 绑定命令请求处理器readQueryFromClient

客户端发送请求时：

1. eventLoop监听到client socket readable事件
2. 命令请求处理器readQueryFromClient给client socket封装对象client
3. 读取请求数据写入client对象的查询缓冲区queryBuf
4. 解析缓冲区的字符串转为sds结构的Redis命令参数存入argv数组
5. 根据argv[0]匹配Command命令并执行
6. 将执行结果写入client对象的写缓冲区（有数组buf和链表reply，数组写不下则会写链表）
7. 然后将执行结果准备就绪的client对象放入响应队列server.clients_pending_write

客户端等待响应时：

1. eventLoop监听到client socket writeable事件
2. 命令回复处理器从响应队列中获取对应的client对象
3. 将写缓冲区的数据写出给client socket

简单来讲：
当我们的客户端想要去连接我们服务器，会去先到IO多路复用模型去进行排队，会有一个连接应答处理器，他会去接受读请求，然后又把读请求注册到具体模型中去，此时这些建立起来的连接，如果是客户端请求处理器去进行执行命令时，他会去把数据读取出来，然后把数据放入到client中， clinet去解析当前的命令转化为redis认识的命令，接下来就开始处理这些命令，从redis中的command中找到这些命令，然后就真正的去操作对应的数据了，当数据操作完成后，会去找到命令回复处理器，再由他将数据写出。

Redis多线程部分

Redis 6.0版本中引入了多线程，目的是为了提高IO读写效率。因此在解析客户端命令、写响应结果时采用了多线程。核心的命令执行、IO多路复用模块依然是由主线程执行。

Redis主要的IO操作在哪？就是用户态的命令读取到内核态中，也就是从请求中获取数据写入queryBuf的过程以及内核态的结果写出到用户态，也就是命令回复处理器将写缓冲区数据写出给客户端socket的时候。

Redis RESP协议

Redis是一个CS架构的软件，通信一般分两步（不包括pipeline和PubSub）：

1. 客户端（client）向服务端（server）发送一条命令
2. 服务端解析并执行命令，返回响应结果给客户端

因此客户端发送命令的格式、服务端响应结果的格式必须有一个规范，这个规范就是通信协议。

而在Redis中采用的是RESP（Redis Serialization Protocol）协议：

• Redis 1.2版本引入了RESP协议
• Redis 2.0版本中成为与Redis服务端通信的标准，称为RESP2
• Redis 6.0版本中，从RESP2升级到了RESP3协议，增加了更多数据类型并且支持6.0的新特性--客户端缓存

但目前，默认使用的依然是RESP2协议，以下简称RESP。

在RESP中，通过首字节的字符来区分不同数据类型，常用的数据类型包括5种：

1. 单行字符串：首字节是+ ，后面跟上单行字符串，以CRLF（ "\r\n" ）结尾。例如返回"OK"： "+OK\r\n"
2. 错误（Errors）：首字节是 - ，与单行字符串格式一样，只是字符串是异常信息，例如："-Error message\r\n"
3. 数值：首字节是 : ，后面跟上数字格式的字符串，以CRLF结尾。例如：":10\r\n"
4. 多行字符串：首字节是 $ ，表示二进制安全的字符串，最大支持512MB：
   1. 如果大小为0，则代表空字符串："$0\r\n\r\n"
   2. 如果大小为-1，则代表不存在："$-1\r\n"
5. 数组：首字节是 *，后面跟上数组元素个数，再跟上元素，元素数据类型不限
   

手写Redis客户端

效果

代码

import java.io.*;
import java.net.Socket;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * @author kinoko
 */
public class RedisClient {

    static Scanner sc = new Scanner(System.in);
    static String host = "192.168.66.128";
    static int port = 6379;
    static Socket socket;
    static PrintWriter writer;
    static BufferedInputStream reader;
    static StringBuilder replyBuf = new StringBuilder();

    public static void main(String[] args) throws IOException {
        try {
            // 建立连接
            connectToRedis();
            // 通信
            communicateToRedis();
        } catch (IOException e) {
            throw new RuntimeException(e);
        } finally {
            if (writer != null) {
                writer.close();
            }
            if (reader != null) {
                reader.close();
            }
            if (socket != null) {
                socket.close();
            }
        }
    }

    private static void communicateToRedis() throws IOException {
        String command;
        while (true) {
            command = sc.nextLine();
            if ("exit".equals(command)) {
                break;
            }
            // 发出请求
            sendRequest(command);
            // 解析响应
            System.out.println(handleResponse());
        }
    }

    private static Object handleResponse() throws IOException {
        // 获取响应首字符判断响应类型
        int prefix = reader.read();
        switch (prefix) {
            case RESP_DATA_TYPE.STR: // 字符类型
                return readLine();
            case RESP_DATA_TYPE.ERR: // 异常类型
                return "ERR: " + readLine();
            case RESP_DATA_TYPE.INT: // 数字类型
                return readInt();
            case RESP_DATA_TYPE.BULK_STR: // 多行字符类型
                return readBulkString();
            case RESP_DATA_TYPE.ARRAY: // 数组类型
                return readArray();
            default:
                throw new RuntimeException("Invalid RESP data");
        }
    }

    private static Object readArray() throws IOException {
        // 获取数组大小
        int len = Integer.parseInt(readLine());
        if (len <= 0) {
            return null;
        }
        // 定义集合，接收多个元素
        List<Object> list = new ArrayList<>(len);
        // 遍历，依次读取每个元素
        for (int i = 0; i < len; i++) {
            list.add(handleResponse());
        }
        return list;
    }

    private static Object readBulkString() throws IOException {
        // 因为已经把表示数据类型的首字符读了，所以这里读的是字符长度
        // $5\r\nhello\r\n -> hello\r\n
        int len = Integer.parseInt(readLine());
        if (len == -1) {
            return null;
        }
        if (len == 0) {
            return "";
        }
        // 读取数据
        // hello\r\n -> \r\n
        byte[] buffer = new byte[len];
        reader.read(buffer);

        // 跳过\r\n
        reader.read();
        reader.read();
        return new String(buffer, StandardCharsets.UTF_8);
    }

    private static Long readInt() throws IOException {
        return Long.parseLong(readLine());
    }

    private static String readLine() throws IOException {
        // 清空响应缓冲区
        replyBuf.setLength(0);
        int c;
        while ((c = reader.read()) != '\r') {
            replyBuf.append(((char) c));
        }
        // 跳过\n
        reader.read();
        return replyBuf.toString();
    }


    /**
     * 发出请求
     * 统一使用多行字符数组的格式发送：
     * set key value -> *3\r\n
     * $3\r\nset\r\n
     * $3\r\nkey\r\n
     * $5\r\nvalue\r\n
     *
     * @param command 命令
     */
    private static void sendRequest(String command) {
        // 根据空格切割命令
        List<String> args = Arrays.stream(command.split("\\u0020"))
                // 过滤空格
                .filter(s -> !s.isEmpty()).collect(Collectors.toList());
        // 写入指令，先拼接字符串，防止char转int导致命令拼接错误
        writer.println("" + RESP_DATA_TYPE.ARRAY + args.size());
        for (String arg : args) {
            writer.println("" + RESP_DATA_TYPE.BULK_STR + arg.getBytes(StandardCharsets.UTF_8).length);
            writer.println(arg);
        }
        writer.flush();
    }


    private static void connectToRedis() throws IOException {
        System.out.println("connect to redis");
        System.out.print("host:");
        if (host == null) {
            host = sc.nextLine();
        } else {
            System.out.println(host);
        }
        System.out.print("port:");
        if (port == 0) {
            port = Integer.parseInt(sc.nextLine());
        } else {
            System.out.println(port);
        }
        // 创建socket
        socket = new Socket(host, port);
        // 获取输出流输入流
        writer = new PrintWriter(new OutputStreamWriter(socket.getOutputStream(), StandardCharsets.UTF_8));
        reader = new BufferedInputStream(socket.getInputStream());
        System.out.println("connect success");
    }

    interface RESP_DATA_TYPE {
        char STR = '+';
        char ERR = '-';
        char INT = ':';
        char BULK_STR = '$';
        char ARRAY = '*';
    }

}

Redis内存回收

Redis之所以性能强，最主要的原因就是基于内存存储。然而单节点的Redis其内存大小不宜过大，会影响持久化或主从同步性能。
我们可以通过修改配置文件来设置Redis的最大内存：

当内存使用达到上限时，就无法存储更多数据了。为了解决这个问题，Redis提供了一些策略实现内存回收，那么是如何实现的呢？
Redis本身是一个典型的key-value内存存储数据库，因此所有的key、value都保存在之前学习过的Dict结构中。redisDb结构如下：

不过在其database结构体中，有两个Dict：

• 一个用来记录key-value。
• 另一个用来记录key-TTL。

其他的Dict结构都是用来存储一些功能性key的，例如blocking_keys，存的是阻塞key，用于阻塞其行为来获取结果的，watched_keys，用来做一些事务相关操作的key。

过期策略

惰性删除：顾明思议并不是在TTL到期后就立刻删除，而是在访问一个key的时候，检查该key的存活时间，如果已经过期才执行删除。

周期删除：顾明思议是通过一个定时任务，周期性的抽样部分过期的key，然后执行删除。
执行周期有两种：

• Redis服务初始化函数initServer()中设置定时任务，按照server.hz的频率来执行过期key清理，模式为SLOW。
• Redis的每个事件循环前会调用beforeSleep()函数，执行过期key清理，模式为FAST。

SLOW模式规则：

• 执行频率受server.hz影响，默认为10，即每秒执行10次，每个执行周期100ms。
• 执行清理耗时不超过一次执行周期的25%.默认slow模式耗时不超过25ms
• 逐个遍历db，逐个遍历db中的bucket，抽取20个key判断是否过期
• 如果没达到时间上限（25ms）并且过期key比例大于10%，再进行一次抽样，否则结束

FAST模式规则（过期key比例小于10%不执行 ）：

• 执行频率受beforeSleep()调用频率影响，但两次FAST模式间隔不低于2ms
• 执行清理耗时不超过1ms
• 逐个遍历db，逐个遍历db中的bucket，抽取20个key判断是否过期如果没达到时间上限（1ms）并且过期key比例大于10%，再进行一次抽样，否则结束

淘汰策略

内存淘汰：就是当Redis内存使用达到设置的上限时，主动挑选部分key删除以释放更多内存的流程。Redis会在处理客户端命令的方法processCommand()中尝试做内存淘汰：

Redis支持8种不同策略来选择要删除的key：

• noeviction： 不淘汰任何key，但是内存满时不允许写入新数据，默认就是这种策略。
• volatile-ttl： 对设置了TTL的key，比较key的剩余TTL值，TTL越小越先被淘汰
• allkeys-random：对全体key ，随机进行淘汰。也就是直接从db->dict中随机挑选
• volatile-random：对设置了TTL的key ，随机进行淘汰。也就是从db->expires中随机挑选。
• allkeys-lru： 对全体key，基于LRU算法进行淘汰
• volatile-lru： 对设置了TTL的key，基于LRU算法进行淘汰
• allkeys-lfu： 对全体key，基于LFU算法进行淘汰
• volatile-lfu： 对设置了TTL的key，基于LFI算法进行淘汰

两个淘汰算法：

• LRU（Least Recently Used），最少最近使用（最久没使用）。用当前时间减去最后一次访问时间，这个值越大则淘汰优先级越高。
• LFU（Least Frequently Used），最少频率使用。会统计每个key的访问频率，值越小淘汰优先级越高。

可以通过修改配置文件中的maxmemory-policy属性来修改策略

Redis的数据都会被封装为RedisObject结构：

LFU的访问次数之所以叫做逻辑访问次数，是因为并不是每次key被访问都计数，而是通过运算：

• 生成0~1之间的随机数R
• 计算 (旧次数 * lfu_log_factor + 1)，记录为P
• 如果 R < P ，则计数器 + 1，且最大不超过255
• 访问次数会随时间衰减，距离上一次访问时间每隔 lfu_decay_time 分钟，计数器 -1

淘汰流程