# 前言

### 为什么我要尝试写作技术书籍

- 一个人年轻时经历的艰难会在未来成为他的财富

# 第一篇 基础和应用篇

## 1.1 授人以鱼不如授人以渔

Redis：Remote Dictionary Service，远程字典服务

### 1.1.1 由Redis面试想到的

架构师的技能水平很高，对提升团队研发效率很有帮助，我们非常钦佩和羡慕，但是普通开发者如果习惯于在架构师封装好的东西上，只专注于做业务开发，那么久而久之，在技术理解和成长上就会变得迟钝甚至麻木。从这个角度上看，架构师可能成为普通开发者的”敌人“，他的强大能力会让大家变成”温室的花朵“，一旦遇到环境变化就会不知所措

## 1.2 万丈高楼平地起 — Redis基础数据结构

### 1.2.2 5种基础数据结构

Redis有5种基础数据结构，分别为：string（字符串）、list（列表）、hash（字典）、set（集合）、zset（有序集合）

#### string（字符串）

- Redis所有的数据结构以唯一的key字符串作为名称，然后通过这个唯一key值来获取相应的value数据，不同类型的数据结构的差异就在于value的结构不一样

- Redis的字符串是动态字符串，是可以修改的字符串，内部结构的实现类似于Java的ArrayList，实际空间capacity一般高于实际字符串长度len，1M空间动态扩容

- 键值对：set name codehole; get name; exits name; del name; get name;

- 批量键值对：set name1 codehole; set name2 holycoder; mget name1 name2 name3; mset name1 boy name2 girl name3 unkown; mget name1 name2 name3;

- 过期和set命令扩展：set name codehole; get name; expire name 5; get name; setex name 5 codehole; get name; setnx name codehole; get name; set nax name holycoder; get name;

- 计数：set age 30; incr age; incrby age 5; incrby age -5; set codehole 9223372036854775807; incr codehole;

#### list（列表）

- Redis的列表相当于Java语言里面的LinkedList，注意它是链表不是数组，意味着插入和删除操作非常快，但索引定位很慢

- Redis的列表结构常用来做异步队列使用，将需要延后处理的任务结构体序列化成字符串，塞进Redis的列表，另一个线程从这个列表中轮训数据进行处理

- 右边进左边出：队列 rpush books python java golang; llen books; lpop books;

- 右边进右边出：栈 rpush books python java golang; rpop books;

- ##### 慢操作

- index相当于Java链表中的get(int index)方法

- ltrim两个参数start_index和end_index定义了一个区间，其他的都删掉

- index可以为负数，-1位倒数第一个元素

- rpush books python java golang; lindex books 1; lrange books 0 -1; ltrim books 1 -1; lrange books 0 -1; ltrim books 1 0; llen books;

- ##### 快速列表

- Redis底层不是简单的linkedlist，而是quicklist的一个结构

- 元素较少的时候，使用一块连续内存存储，结构是ziplist，数据比较多的时候改为quicklist，多个ziplist使用双向指针串起来使用

#### hash（字典）

- Redis的字典相当于Java语言里面的HashMap，数组+联表二维结构，渐进式rehash

- hset books java "think in java"; hset books golang "concurrency in go"; hset books python "python cookbook"; hgetall books; hlen books; hget books java; hset books golang "learning go programming"; hget books golang; hmset books java "effective java" ptyhon "learning python";

- hash可对单个key进行计数：hset user-laoqian age 29; hincrby user-laoqian age 1

#### set（集合）

- Redis的集合相当于Java语言里面的HashSet，键值对无序的

- sadd books python; sadd books python; sadd books java golang; smembers books; sismember books java; sismember books rust; scard books; spop books;

#### zset（有序列表）

- 类似于Java的SortedSet和HashMap的结合体，跳跃列表数据结构

- zadd books 9.0 "think in java"; zadd books 8.9 "java concurreency"; zadd books 8.6 "java cookbook"; zrange books 0 -1; zrevrange books 0 -1; zcard books; zscore books "java concurrency"; zrank books "java concurrency"; zrangebyscore books 0 8.91; zrangebyscore books -inf 8.91 withscores; zrem books "java concurrency"; zrange books 0 -1;

- 跳跃列表，最下面一层所有的元素都会串起来。然后每隔几个元素挑选出一个代表，再将这几个代表使用另外一级指针串起来。然后在这些代表里面再挑出二级代表，再串起来。最终就形成了金字塔结构。跳跃列表采取一个随机策略来决定新元素可以兼职到第几层。L0层100%，L1层50%，L2层25%...

### 1.2.3 容器型数据结构的通用规则

list set hash zset都是容器型数据结构，共享两条规则

1. create if not exists，如果容器不存在，那就创建一个，再进行操作

2. drop if no elements，如果容器的元素没有了，那么立即删除容器，释放内存

### 1.2.4 过期时间

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

## 1.3 千帆竞发 — 分布式锁

原子操作是指不会被线程调度机制打断的操作。这种操作一旦开始，就会一直运行到结束，中间不会有任何线程切换

### 1.3.1 分布式锁的奥义

- 分布式锁本质上要实现的目标就是在Redis里面占一个”坑“，当别的进程也要占坑时，发现那里已经有一根”大萝卜“了，就只好放弃或者稍后再试

- 占坑一般使用setnx(set if not exists)指令，先来先占，用完了，再调用del指令释放”坑“

- setnx lock:codehole true; del lock:codehole;

- 一般拿到锁之后，再给锁加一个过期时间，避免占坑后逻辑出现异常，没有释放锁，导致死锁

- setnx lock:codehole true; expire lock:codehole 5; del lock:codehole;

- 如果setnx和expire之间服务器进程突然挂掉，还是会造成死锁。也不能加事务，事务的特点是一口气执行，要么全执行，要么一个不执行，setnx有可能没抢到锁，expire是不应该执行的。

- Redis 2.8版本，引入了setnx和expire指令可以一起执行

- set lock:codehole true ex 5 nx; del lock:codehole;

### 1.3.2 超时问题

- Redis分布式锁不要用于较长时间的任务

- 稍微安全的办法：将set的value参数设置为一个随机数，释放锁的时候先匹配随机数是否一致，然后再删除key。确保当前线程占的锁不会被其他线程释放，除非这个锁是因为过期而被服务器释放，但匹配和删除不是一个院子操作，需要使用Lua脚本处理，保证连续多个指令的原子性执行。这个方案只是相对安全一些，如果真的超时了，当前线程逻辑没有处理完，其他线程也会趁虚而入

### 1.3.3 可重入性

- 如果一个锁支持同一个线程的多次加锁，那么这个锁是可重用的。Redis如果要支持可重入，需要客户端对set封装，使用线程的Threadlocal变量存储当前持有锁的计数

## 1.4 缓兵之计 — 延时队列

### 1.4.1 异步消息队列

- Redis的list（列表）数据结构常用来作为异步消息队列使用，用rpush和lpush操作入队列，用lpop和rpop操作出队列

### 1.4.2 队列空了怎么办

- 如果队列空了，客户端就会陷入pop的死循环，通常我么使用sleep来解决这个问题

### 1.4.3 阻塞读

- 睡眠会导致延迟增大，blpop/brpop，阻塞读在队列没有数据的时候，会立即进入休眠状态，一旦数据到来，则立刻醒过来。消息的延迟几乎为0

### 1.4.4 空闲连接自动断开

- 如果线程一直阻塞在那里，Redis的客户端就成了空闲连接，闲置过久，服务器一般会主动断开连接，减少闲置资源占用。这个时候blpop/brpop会抛出异常，所以客户端需要捕获异常后重试

### 1.4.5 锁冲突处理

客户端加锁没成功处理策略

1. 直接抛出异常，通知用户稍后重试

2. sleep一会儿，然后重试

3. 将请求转移至延时队列，过一会再试

### 1.4.6 延时队列的实现

- 延时队列可以通过Redis的zset（有序列表）来实现，我们将消息序列化成一个字符串作为set的value，这个消息的到期处理时间做为score，然后多个线程轮训zset获取到期的任务进行处理。

- Redis的zerm方法可以返回多线程中是否抢到任务

### 1.4.7 进一步优化

- 同一个任务可能会被多个进程取到之后再使用zrem进行争抢，没抢到的进程白取了一次任务，可使用lua scripting来优化，将zrangebyscore和zrem一同挪到服务器端进行原子操作

## 1.5 节衣缩食 — 位图

位图不是特殊的数据结构，它的内容其实就是普通的字符串，也就是byte数组，我们可以使用普通的get/set直接获取和设置整个位图的内容，也可以使用位图操作getbit/setbit等将byte数组看成”位数组“来处理

### 1.5.1 基本用法

零存零取，整存零取

### 1.5.2 统计和查找

Redis提供了位图统计指令bitcount和位图查找指令bitpos

### 1.5.3 魔术指令bitfield

- bitfield有三个子指令，get、set、incrby

- bitfield提供了溢出策略子指令overflow，饱和截断，失败不执行

## 1.6 四两拨千斤 — HyperLogLog

用来解决非精确统计问题，UV

### 1.6.1 使用方法

pfadd和set集合的sadd的用法是一样的，来一个用户ID，就将用户ID塞进去就是。pfcount和scard的用法一样，直接获取计数值

### 1.6.2 pfadd中的pf是什么意思

HyperLogLog数据结构的发明人Philippe Flajolet，pf是缩写

### 1.6.3 pfmerge适合的场景

pfmerge，用于将多个pf计数值累加在一起形成一个新的pf值

### 1.6.4 注意事项

需要占据12KB的存储空间，数据少的时候采用稀疏矩阵存储，超过阈值后，才会一次性转变为稠密矩阵

### 1.6.5 HyperLogLog实现原理

给定一系列随机数，记录下低位连续零位的最大长度K，可通过K估算出随机数的数量N。K和N的对数之间存在显著的线性相关性

### 1.6.6 pf的内存占用为什么是12KB

实现的时候使用的是2的14次方桶，每个桶的maxbits需要6个bit存储

## 1.7 层峦叠嶂 — 布隆过滤器

布隆过滤器，专门解决去重问题

### 1.7.1 布隆过滤器是什么

是一个不怎么精确的set结构，当使用contains方法判断对象是否存在，可能产生误判。它说某个值存在时，可能不存在。它说某个值不存在时，那他肯定不存在

### 1.7.2 Redis中的布隆过滤器

docker run -p6379:6379 redislabs/rebloom

### 1.7.3 布隆过滤器的基本用法

- bf.add添加元素，bf.exists查询元素是否存在，添加多个元素要用bf.madd，查询多个元素是否存在bf.mexists

- bf.reserve指令显示创建，key，error_rate，initial_size

### 1.7.4 注意事项

initial_size设置过大，会浪费存储空间。error_rate越小，需要存储空间越大

### 1.7.5 布隆过滤器的原理

- 数据结构里面就是一个大型的位数组和几个不一样的无偏hash函数，无偏hash就是hash值比较平均

- add的时候进行hash，然后对长度取模，相应位置1，查询的时候，全是1代表极有可能存在，只要有一位是0，那么肯定不存在

- 实际元素大于初始化数量，应该对布隆过滤器进行重建，重新分配size更大的过滤器，并且把历史元素add进去

### 1.7.6 空间占用估计

- 预计元素数量n，错误率f=>数组的长度l，hash的最佳数量k

- set中存储的是每隔元素的内容，而布隆过滤器仅仅存储元素的指纹

### 1.7.7 实际元素超出时，误判率会怎样变化

- 错误率10%，倍数比为2，错误率会到40%

- 错误率1%，倍数为2，错误率会升到15%

- 错误率为0.1%，倍数为2，错误率会升到5%

### 1.7.8 用不上Redis 4.0怎么办

- Redis布隆过滤器Python库，pyreBloom

- Redis布隆过滤器Java库，orestes-bloomfilter

### 1.7.9 布隆过滤器的其他应用

- 爬虫过滤爬过的网站

- NoSQL，查询某个row，先通过内存中过滤器过滤大量不存在的row

- 垃圾邮件过滤

## 1.8 短尾求生 — 简单限流

除了控制流量，限流还有一个应用目的是控制用户行为，避免垃圾请求

### 1.8.1 如何使用Redis来实现简单限流策略

系统要限制用户的某个行为在指定的时间里智能发生N次

### 1.8.2 解决方案

zset数据结构的score值，通过score来保留时间窗口。每一个行为都会作为zset中的一个key保存下来，同一个用户的同一种行为用一个zset记录

## 1.9 一毛不拔 — 漏斗限流

- 漏斗的剩余空间代表着当前行为可以持续进行的数量，漏嘴的流水率代表着系统允许该行为的最大频率

- Funnel使用hash，无法保证原子性，从hash结构中取值，然后内存运算，再回填到hash。而一旦加锁，就意味着加锁失败可能，选择重试会导致性能下降，选择放弃，影响用户体验，需要Redis-Cell救星

### 1.9.1 Redis-Cell

- Redis 4.0模块提供Redis-Cell模块，命令为cl.throttle

- cl.throtttle laoqian:reply 15 30 60 1，laoqian:reply：key laoqian，15：capacity是漏斗容量，30：operations，60 seconds，30/60为漏斗速率，1：need 1 quota，可选，默认是1

- 返回值0，15，14，-1，2；0代表允许，1表示拒绝；15：漏斗容量capacity，14：漏斗剩余空间left_quota；-1：如果被拒绝了，需要多长时间后再试，单位s；2：多长时间后，漏斗完全空出来

## 1.10 近水楼台 — GeoHash

### 1.10.1 用数据库来算附近的人

一般方法都是通过指定举行区域来限定元素的数量，然后对区域内的元素进行全量距离计算再排序。数据库表需要把经纬度坐标加上双向复合索引（x, y）

### 1.10.2 GeoHash算法

- GeoHash可以将二维的经纬度坐标映射到一维的整数

- 地球看为平面，二分法划分方格，00，01，10，11，Redis里面经纬度用52位整数进行编码，放进zset中，zset的value元素的key，score是GeoHash的52位整数

### 1.10.3 Geo指令的基本用法

- 增加，geoadd，集合名称，多个经纬度名称三元组

- 距离，geodist，集合名称、两个名称和距离单位

- 获取元素位置，geopos，集合，元素名称，获取的坐标是有损的

- 获取元素的 hash值，base32编码

- 附近的公司，georadiusbymember，查询指定元素附近的其他元素；georadius，查询附近的的元素指令

- 数据量过大，需要对Geo数据进行拆分，按照国家拆分、省、市、区

## 1.11 大海捞针 — scan

- 如何从海量的key中找出满足特定前缀的key列表

- keys命令用来列出所有满足特定正则字符串规则的key

- 指令缺点：1. 没有offset、limit 参数 2. keys算法是遍历，复杂度O(n)，这个指令卡顿，所有读写Redis其他指令都会延后甚至报错，因为Redis单线程，引入了scan命令解决

- scan优点：1. 复杂度虽然是O(n)，但是通过游标分布进行的，不会阻塞线程。2. 提供limit参数 3. 同keys一样，也提供模式匹配 4. 服务器你不需要为游标保存状态，游标唯一状态就是为客户端返回游标整数 5. 返回的结果可能会有重复，需要客户端去重 6. 遍历定的过程中如果有数据修改，改动后的数据能不能遍历到是不确定的 7. 单次返回的结果是空的并不意味着遍历结束，而是要看游标值是否为0

### 1.11.1 scan基本用法

- scan提供三个参数，第一个是cursor整数值，第二个是key的正则模式，第三个是遍历的limit hint。

- limit不是返回的数量结果，是单词遍历的字典槽位数量（约等于）

### 1.11.2 字典的结构

- 在Redis里所有的key都存储在一个很大的字典中，类似HashMap，是一维数组，二维联表结构

- scan返回的游标就是第一维数组的位置索引，我们称之为槽

### 1.11.3 scan遍历顺序

高位进位加法来遍历，避免扩容或缩容时槽位的遍历重复和遗漏

### 1.11.4 字典扩容

Java的HashMap扩容，重新分配2倍大小数组，所有元素rehash新的数组下面，rehash相当于元素的hash值对数组长度进行取模运算，因为数组的长度是2的n次方，所以等价于位与操作。7，15，31成为字典的mask值，mask的作用就是保留hash值的低位，高位被置为0

### 1.11.5 对比扩容、缩容前后的遍历顺序

高位进位加法的遍历顺序，rehash后的槽位在遍历顺序上是相邻的。扩容可以避免重复遍历，缩容会有重复遍历

### 1.11.6 渐进式rehash

Java的扩容，会将HashMap一次性rehash，Redis需要使用渐进式rehash，先同时保留旧数组和新数组，定时任务中以及后续对hash指令操作中渐渐地将就数组中挂接的元素迁移到新数组

### 1.11.7 更多的scan指令

zscan遍历zset集合元素，hscan遍历hash字典的元素，sscan遍历set集合的元素

### 1.11.8 大key扫描

- 平时业务逻辑，要尽量避免大key产生。会引起卡顿

- redis-cli -h 127.0.0.1 -p 7001 --bigkeys扫描大key，可以加个休眠参数 -i 0.1

# 第2篇 原理篇

## 2.1 鞭辟入里 — 线程IO模型

Redis是个单线程程序

对于那些O(n)级别的指令，一定要谨慎使用

### 2.1.1 非阻塞IO

非阻塞IO在套接字对象上提供了一个选项Non_Blocking，当这个选项打开时，读写方法不会阻塞，而是能读多少读多少，能写多少写多少。

### 2.1.2 事件轮询（多路复用）

最简单的事件轮询API是select函数，它是操作系统他提供给用户程序的API。输入是读写描述符列表read_fds & writ_fds，输出是与之对应的可读可写时间。同时还提供了一个timeout参数，如果没有任何事件到来，那么就最多等待timeout的值的时间，线程处于阻塞状态。一旦期间有任何事件到来，就可以立即返回。时间过了之后还是没有任何事件到来，也会立即返回。

### 2.1.3 指令队列

Redis会将每个客户端套接字都关联一个指令队列。客户端的指令通过队列来排队进行顺序处理，先到先服务。

### 2.1.4 响应队列

Redis同样也会为每个客户端套接字关联一个响应队列。Redis服务器通过响应队列来将指令的返回结果回复给客户端。

### 2.1.5 定时任务

Redis的定时任务会记录在一个被称为“最小堆”的数据结构中，在这个堆中，最快要执行的任务排在堆的最上方。

## 2.2 交头接耳 — 通信协议

Redis将所有数据都放入内存中，用一个单线程对外提供服务，单个节点在跑满一个CPU核心的情况下可以达到了10W/s的超高QPS

### 2.2.1 RESP

RESP是Redis序列化协议（Redis Serialization Protocol）的缩写，它是一种直观的文本协议，优势在于实现过程异常简单，解析性能极好。

Redis协议将传输分为5种最小单元类型，单元结束时统一加上回车换行符号\r\n

1. 单行字符串以”+”符号开头

2. 多行字符串以“$”符号开头，后跟字符串长度

3. 整数值以“:”符号开头，后跟整数的字符串形式

4. 错误消息以“-”符号开头

5. 数组以”*”号开头，后跟数组的长度

### 2.2.2 客户端 -> 服务器

客户端向服务器发送的指令只有一种格式，多行字符串数组。

### 2.2.3 服务器 -> 客户端

服务器向客户端回复的响应要支持多种数据结构，但再复杂的消息也不会超过以上5种数据结构

### 2.2.4 小结

Redis协议里虽然有大量冗余的回车换行符，但不影响它成为互联网技术领域非常受欢迎的文本协议。在技术领域里，性能并不总是一切，还有简单性、易理解性和易实现性，这些都需要进行适当权衡。

## 2.3 未雨绸缪 — 持久化

- Redis持久化机制有两种，第一种是快照，第二种是AOF日志。快照是一次全量备份，AOF日志是连续的增量备份。

- 快照是内存数据的二进制序列化形式，在存储上非常紧凑，而AOF日志记录的是内存数据修改的指令记录文本

- AOF日志在长期的运行过程中会变得无比庞大，数据库重启时需要加载AOF日志进行指令重放，这个时间就会无比漫长，所以需要定期进行AOF重写，给AOF日志进行瘦身

### 2.3.1 快照原理

- 为了不阻塞线上的业务，Redis就需要一边持久化，一边响应客户端请求。持久化的同事，内存数据结构还在改变

- Redis使用操作系统的多进程COW（Copy On Write）机制来实现快照持久化。

### 2.3.2 fork（多进程）

- Redis在持久化时会调用glibc的函数fork产生一个子进程，快照持久化完全交给子进程来处理，父进程继续处理客户端请求。子进程刚产生的时，它和父进程共享内存里面的代码段和数据段。

- 子进程做数据持久化，不会修改现在的内存数据结构，它只是对数据结构进行遍历读取，然后序列化写道磁盘中。但是父进程不一样，它必须持续服务客户端请求，然后对内存数据结构进行不间断的修改。

- 这个时候就会使用操作系统的COW机制进行数据段页面的分离。数据段是由操作系统的页面组合而成，当父进程对其中一个页面的数据进行修改时，会被共享的页面复制一份分离出来，然后对这个复制的页面进行修改。这时子进程相应的页面是没有变化的，还是进程产生时那一瞬间的数据。

### 2.3.3 AOF原理

Redis会在收到客户端修改指令后，进行参数校验、逻辑处理，如果没问题，就立即将该指令文本存储到AOF日志中，也就说，先执行指令才将日志存盘。不同于leveldb、hbase等存储引擎

### 2.3.4 AOF重写

Redis提供了bgrewriteaof指令用于对AOF日志进行瘦身，其原理就是开辟一个子进程对内存进行遍历，转化成一系列Redis的操作指令，序列化到一个新的AOF日志中。序列化完毕后再将操作期间发生的增量AOF日志追加到这个新的AOF日志文件中，追加完毕后就立即替换旧的AOF日志文件了。

### 2.3.5 fsync

- Linux的glibc提供了fsync(int fd)函数可以将指定文件的内容强制从内核缓存刷到磁盘。只要Redis进程实时调用fsync函数就可以保证AOF日志不丢失。但是fsync是一个磁盘IO操作，它很慢！如果Redis执行一条指令就fsync一次，那么Redis高性能的低位就不保了。

- 所以在生产环境的服务器中，Redis通常是每隔1s左右执行一次fsync操作，这个1s是可以配置的。这是在数据安全性和性能之间做的一个折中，在保持高性能的同时，尽可能使数据少丢失。

### 2.3.6 运维

Redis的主节点不会进行持久化操作，持久化操作主要在从节点进行。从节点是备份节点，没有来自客户端请求的压力，它的操作系统资源往往比较充沛

### 2.3.7 Redis 4.0混合持久化

- 重启Redis时，我们很少使用rdb来回复内存状态，因为会丢失大量数据。我们通常使用AOF日志重放，但是重放AOF日志相对于使用rdb要慢的多。

- 于是在Redis重启的时候，可以先加载rdb的内容，然后再重放增量AOF日志，就可以完全替代之前的AOF全量文件重放，重启效率因此得到大幅提升。

## 2.4 雷厉风行 — 管道

- Redis管道（Pipeline）本身并不是Redis服务器直接提供的技术，这个技术本质上是由客户端提供的，跟服务器没有什么直接关系。

### 2.4.1 Redis的消息交互

客户端经理写-读-写-读四个操作才能完整的执行两条指令，如果我们调整读写顺序，改为写-写-读-读，这两个指令同样可以完成。客户端对管道中的指令列表改变读写顺序就可以大幅节省IO时间。管道中指令越多，效果越好

### 2.4.2 管道压力测试

redis-benchmark，P参数

### 2.4.5 深入理解管道本质

对于管道来说，连续的write操作根本就没有耗时，之后第一个read操作会等待一个网络的来回开销，然后所有的响应消息都已经送回到内核的读缓冲了，后续的read操作直接就可以从缓冲中拿到结果，瞬间就返回了

## 2.5 同舟共济 — 事务

### 2.5.1 Redis事务的基本用法

指令分别是multi、exec、discard。multi表示事务的开始，exec指示事务的执行，discard指示事务的丢弃

### 2.5.2 原子性

Redis的事务根本不具备”原子性“，而仅仅是满足了事务的”隔离性“中的串行化 — 当前执行的事务有着不被其他事务打断的权利

### 2.5.3 discard（丢弃）

在discard之后，队列中的所有制令都没执行

### 2.5.4 优化

通常Redis的客户端在执行事务的都会结合pipeline一起使用，这样可以将多次IO操作压缩为单次IO操作

### 2.5.5 watch

- 两个并发的客户端对账户余额进行修改操作，需要取出余额在内存乘以倍数，将结果写回Redis

- 分布式锁是一种悲观锁

- Redis提供的watch机制，它是一种乐观锁

- watch会再事务开始之前盯住一个或者多个关键变量，当事务执行时，也就是服务器收到了exec指令要顺序执行缓存的事务的队列时，Redis会检查关键变量自watch之后是否被修改了（包括当前事务所在的客户端）。如果关键变量被人东莞过了，exec指令就会返回NULL回复告知客户端事务执行失败，这个时候客户端一般会选择重试

### 2.5.6 注意事项

Redis禁止在multi和exec之间执行watch指令，必须在multi之前盯住关键变量

## 2.6 小道消息 — PubSub

Redis消息队列不足之处，那就是它不支持消息的多播机制

### 2.6.1 消息多播

消息多播允许生产者只生产一次消息，由中间件负责将消息复制到多个消息队列，每个消息队列由相应的消费组进行消费。

### 2.6.2 PubSub

- 为了支持消息多播，它单独使用了一个模块来支持消息多播，PubSub(PublisherSubscriber)(发布者/订阅者模式)

- PubSub的消费者如果使用休眠的方式来轮询消息，也会遭遇消息处理不及时的问题。不过我们可以使用Lisen阻塞监听来进行处理，这点同blpop原理是一样的。

### 2.6.3 模式订阅

一次订阅多个主题，即使生产者新增加了同模式的主题，消费者也可以立即收到消息。psubscribe codehole.*

### 2.6.4 消息结构

- data: 消息的内容

- channel：当前订阅的主体名称

- type：消息类型，普通：message，订阅指令的反馈：subscribe，模式订阅反馈：psubscribe，还有unsubscribe和punsubscribe

- pattern：当前消息使用哪种模式订阅到的，如果通过subscribe则为空

### 2.6.5 PubSub的缺点

Redis消费者端断连，则消息丢失

### 2.6.6 补充

Reids 5.0新增了Steam数据结构，这个功能给Redis带来了持久化消息队列。

## 2.7 开源节流 — 小对象压缩

### 2.7.1 32bit VS 64bit

如果Redis使用内存不超过4GB，可以考虑使用32bit进行编译，能够节约大量内存

### 2.7.2 小对象压缩存储(ziplist)

- 如果Redis内部管理的集合数据结构很小，它会使用紧凑存储形式压缩存储

- Redis的ziplist是一个紧凑的字节数组结构。如果它存储的是hash结构，那么key和value会作为两个entry被相邻存储。如果它存储的是zset结构，那么value和score会作为两个entry被相邻存储。intset是一个紧凑的证书数据结构。如果set里存储的是字符串，那么sadd立即会升级为hashtable机构。

- 当集合对象不断增加，或者某个value值过大，这种小对象存储也会被升级为标准结构。

### 2.7.3 内存回收机制

- 删除1GB的key，内存并没有太大变化。原因操作系统是以页回收内存，但key分散到了很多页

- 如果执行了flushdb，内存就回收了

- Redis会重新利用删除key的内存

### 2.7.4 内存分配算法

Redis默认使用jemalloc(facebook)库来管理内存

# 第3篇 集群篇

## 3.1 有备无患 — 主从同步

### 3.1.1 CAP原理

- CAP原理就好比分布式领域的牛顿定律，它是分布式存储的理论基石。

- C：Consistent，一致性

- A：Availability，可用性

- P：Partition tolerance，分区容忍性

- 分布在不同机器上进行网络隔离开的节点，网络断开的时候成为网络分区

- 当网络分区发生的时候，一致性和可用性两难全

### 3.1.2 最终一致

Redis保证最终的一致性，从节点会努力追赶主节点，最终从节点的状态会和主节点的状态保持一致。

### 3.1.3 主从同步与从从同步

从从同步为了减轻主节点的同步负担后续版本加的，为了描述简单，统一为主从同步

### 3.1.4 增量同步

Redis同步的是指令流，主节点会将那些对自己的状态产生修改性影响的指令记录在本地的内存buffer中，然后异步将buffer中的指令同步到从节点，从节点一遍执行同步来的指令流来达到和主节点一样的状态，一遍向主节点反馈自己同步到哪里了（偏移量）

### 3.1.5 快照同步

需要在主节点上进行一次bgsave，将当前内存的数据全部快照到磁盘文件中，然后再将快照文件的内容全部传送到从节点。从节点将快照文件接收完毕后，立即执行一次全量加载。如果快照加载的时间过长或者复制buffer太小，就会导致快照同步的死循环。务必要设置一个合适的复制buffer大小

### 3.1.6 增加从节点

节点刚加入到集群中，必须先进行一次快照同步，同步完成后再继续进行增量同步

### 3.1.7 无盘复制

2.8.18版本后，Redis支持无盘复制，主服务器通过套接字将快照内容发送到从节点，生成快照是一个遍历的过程，主节点会一边遍历内存，一边序列化的内容发送到从节点，从节点还是跟以前一样，先接收到的内容写入磁盘，然后进行一次性加载

### 3.1.8 wait指令

Redis的复制是异步的，wait指令可以让异步复制变身同步复制，确保系统的强一致性。

### 3.1.9 小结

复制功能也不是必须的，如果只是用Redis做缓存，也就不需要从节点做备份，挂掉了重启一下就行。

## 3.2 李代桃僵 — Sentinel

Redis Sentinel集群看成一个zookeeper集群，它是集群高可用的心脏，一般由3~5个节点组成，这样即使个别节点挂了，集群还可以正常运转

### 3.2.1 消息丢失

Sentinel不能保证消息完全不丢失，min-slaves-to-write标识主节点必须至少有这些个从节点在进行正常复制，否则就停止对外写服务；min-slaves-max-lag表示如果再这些秒内没有收到从节点的反馈，就意味着从节点同步不正常

### 3.2.2 Sentinel基本用法

- 连接池建立新连接时，会去查询主节点地址，然后跟内存中的比对，如果变更了，就断开所有连接，重新使用新地址连接，重连的时候就会用到新地址

- 处理命令的时候如果捕获ReadOnlyError也会把旧连接关掉，后续指令会重新连接

## 3.3 分而治之 — Codis

- Redis集群方案将众多小内存的Redis实例整合起来，将分布在多台机器上的众多CPU核心的计算能力聚集在一起，完成海量数据存取和高并发读写操作

- Codis是集群方案之一，Codis上挂的所有Redis实例构成一个Redis集群，集群空间不足的时候，可以通过动态增加Redis实例来实现扩容需求

- Codis只是一个转发代理中间件，可以起多个实例，显著增加整体QPS需求，还能起容灾功能

### 3.3.1 Codis分片原理

- Codis默认将所有的key划分为1024个槽位，对客户端传来的key进行crc32运算计算hash值，再将hash后的整数值对1024整数取模得到一个余数，这个余数就是对应的槽位

- Codis会在内存维护槽位和Redis实例的映射关系

### 3.3.2 不同的Codis实例之间槽位关系如何同步

Codis开始使用zookeeper，后来也支持了etcd，分布式配置存储数据库专门用来持久化槽位关系

### 3.3.3 扩容

- Codis增加SLOTSSCAN指令，可以遍历指定slot下所有的key。扩容的时候挨个迁移每个key到新的Redis节点

- 当Codis接收到位于正在迁移槽位的key后，会立即强制对当前的单个key进行迁移，迁移完成后，再将请求转发到新的Redis实例

### 3.3.4 自动均衡

Codis会在系统比较闲的时候，观察每个Redis实例对应的slot数量，如果不平衡，就会自动进行迁移

### 3.3.5 Codis的代价

- 因为所有的key分散在不同的Redis，就不能再支持事务了

- 同样rename操作也很危险，它的参数是两个key，如果这两个key在不同的Redis实例中，rename操作是无法正确完成的

- 单个的key对应的value不宜过大

- Codis因为作为Proxy作为中转层，网络开销要比单个Redis大

- Codis的集群配置中心使用zookeeper来实现，意味着带来运维代价

### 3.3.6 Codis的优点

相比官方的Redis Cluster集群方案简单，分布式的问题交给了第三方(zookeeper/etcd)去负责

### 3.3.7 mget指令的操作过程

mget指令获取多个key，Codis策略将key按照所分配的实例打散分组，依次调用每个实例mget，然后结果汇总给客户端

### 3.3.8 架构变迁

Redis升级，Codis也需要实时跟进

### 3.3.9 Codis的尴尬

Redis Cluster在业界逐渐流行，官方升级不会考虑第三方

### 3.3.10 Codis的后台管理

支持服务器集群管理功能，可以添加分组、添加节点、执行自动均衡命令，可以直接查看slot的状态，被分配到哪个实例

## 3.4 众志成城 — Cluster

- Redis Cluster是去中心化的，比如三个节点的Redis集群，他们是互相连接总成一个对等集群对外服务

- 将所有数据划分16384个槽，槽位的信息存储在每个节点中

- 客户端连接后，也会得到一份集群的槽位配置信息，客户端查询key可以直接定位到节点

### 3.4.1 槽位定位算法

Redis Cluster对key使用crc16算法进行hash，得到的整数值对16384进行取模来获取槽位

### 3.4.2 跳转

客户端向错误的节点发出指令后，节点发现key所在的槽位不归自己管理，会向客户端发送一个特殊的跳转指令携带目标操作的点的地址

### 3.4.3 迁移

- redis-trib可以让运维人员手动调整槽位的分配情况

- redis迁移的单位是槽，迁移的时候，槽处于中间过渡状态

- 从源节点获取内容->存到目标节点->从源节点删除内容

- 目标节点执行restore指令到源节点删除key之间，源节点的主线程会处于阻塞状态，知道key被删除成功

- 集群环境下，业务逻辑要尽量避免产生很大的key

- 访问源节点的时候，会返回客户端一个-ASK目标节点的指令，没迁移完成的时候，按理来说不归新节点管理，ASKING指令是告诉目标节点下一个指令不能不理

### 3.4.4 容错

Redis Cluster可以为每个主节点设置从节点，主节点发生故障，会将从节点提升为主节点。如果没有从节点，也可以设置require-full-coverage允许部分节点发生故障还可对外访问

### 3.4.5 网络抖动

- cluster-node-timeout标识当某个节点持续timeout的时间失联，才可以认定该节点出现故障

- cluster-slave-validity-factor作为系数放大这个超时时间来宽松容错紧急程度

### 3.4.6 可能下线（PFail）与确定下线（Fail）

只有当大多数节点都认定某个节点失联了，集群才认为该节点需要进行主从切换来容错

### 3.4.7 Cluster基本用法

- 构造实例时候，最好提供多个节点去初始化

- Cluster不支持事务，mget币Redis要慢很多，rename不再是原子的

### 3.4.8 槽位迁移感知

- MOVED是用来矫正槽位的，客户端需要更新槽位关系表

- ASKING是用来临时纠正槽位的，先发旧槽位，旧槽位有就返回了，客户端不应刷新槽位关系表

- 重试2次，指令发送到错误节点，先MOVED，然后再去另外节点，另外节点正好迁移操作，ASKING到新的节点，客户端重试了2次

- 重复多次，一般客户端会设置一个重复次数

### 3.4.9 集群变更感知

- 目标节点挂掉，客户端抛ConnectionError，重试的节点通过MOVED告知分配的新的节点

- 运维手动修改了集群信息，主节点切换到其他节点，或者移除了集群，打到旧节点的会报ClusterDown，客户端会关闭所有的连接，清空槽位映射关系表，重新尝试初始化

# 第4篇 拓展篇

## 4.1 耳听八方 — Stream

- Redis 5.0发布的，它是一个强大的支持多播的可持久化消息队列。消息链表将所有加入的消息都串起来，每个消息都有一个唯一的ID和对应的内容。消息是持久化的，重启后，内容还在

- 每个Steam都可挂多个消费组，每个消费组有个游标last_delivered_id在Stream数组之上往前移动，表示当前消费组已经消费到哪条消息

- 每个消费组的状态都是独立的，相互不受影响

- 消费者内部会有一个状态变量pending_ids，记录当前已被客户端取走，但还没有ack的消息，用来确保客户端至少消费了消息一次

### 4.1.1 消息ID

消息ID格式“整数-整数”，后面加入的消息的ID必须要大于前面的消息ID

### 4.1.2 消息内容

消息内容就是键值对，形如hash结构的键值对，这没什么特别之处

### 4.1.3 增删改查

xadd: 向Stream追加消息。xdel：向Stream上次删除消息，只是置位，不影响消息总长度。xrange：获取Stream中的消息列表，会自动过滤已删除的消息。xlen：获取Stream消息长度。del：删除整个Stream消息列表中的所有消息。

### 4.1.4 独立消费

不定义消费组的情况下对Stream消息独立消费，xread，完全忽略额消费组的存在，就好像Stream是一个普通的列表一样

### 4.1.5 创建消费组

通过xgroup create指令创建消费组，需要制定其实消息ID来初始化last_delivered_id

### 4.1.6 消费

xreadgroup指令可进行消费组的组内消费，需要提供消费组名称，消费者起始消息ID。它同xread一样，也可以阻塞等待新消息。读到新消息后，对应的消息ID就会进入消费者的PEL（正在处理的消息）结构里，客户端处理完毕后使用xack指令通知服务器，本条消息已经处理完毕，该消息ID就会从PEL中移除。

### 4.1.7 Steam消息太多怎么办

Redis提供了一个定长Stream功能，在xadd的指令中提供一个定长长度参数maxlen，就可以将老的消息干掉，确保链表不超过指定长度。

### 4.1.8 消息如果忘记ack会怎样

如果消费者处理完消息没有ack，就会导致PEL不断增大，内存就会放大

### 4.1.9 PEL如何避免消息丢失

如果客户端断开了连接，待客户端重新连接之后，可以再次收到PEL中的消息ID列表，此时xreadgroup的起始消息ID必须是人以有效的消息ID，一般将参数设为0-0

### 4.1.10 Stream的高可用

Stream的高可用是建立在主从复制基础上的，不过鉴于Redis的指令复制是异步的，在failover发生时，Redis可能丢失极小部分数据

### 4.1.11 分区Partition

Redis的服务器没有原生支持分区能力，如果想要使用分区，那就需要分配多个Stream，然后在客户端使用一定的策略来生产消息到不通的Stream。

### 4.1.12 小结

Stream的消费模型借鉴了Kafka的消费分组的概念，弥补了Redis PubSub不能持久化消息的缺陷。

## 4.2 无所不知 — Info指令

Info指令繁多，分为9大块：

1. Server：服务器运行的环境参数

2. Clients：客户端相关信息

3. Memory：服务器运行内存统计数据

4. Persistence：持久化信息

5. Stats：通用统计数据

6. Replication：主从复制相关信息

7. CPU：CPU使用情况

8. Cluster：集群信息

9. KeySpace：键值对统计数量信息

### 4.2.1 Redis每秒执行多少指令

info stats | grep ops  代表客户端每秒发送多少指令到服务器执行，redis-cli monitor可以观察哪些key被频繁访问

### 4.2.2 Redis连接了多少客户端

info clients，通过观察数量可以确定是否存在意料之外的连接。如果不对，则可以用过client list指令列出所有的客户端连接地址来确定源头。客户端的数量有个重要的参数rejected_connections，表示因为超出最大连接而被拒绝的客户端连接次数，如果过多，则需要调整maxclients参数

### 4.2.3 Redis内存占用多大

info memory，如果单个Redis内存占用过大，并且在业务上没有太多压缩的空间的话，可以考虑集群化了。

### 4.2.4 复制积压缓冲区多大

info replication，它严重影响主从复制的效率。通过sync_partial_err半同步失败的次数，来决定是否需要扩大积压缓冲区。

## 4.3 拾遗补漏 — 再谈分布式锁

在Sentinel集群中，当主节点挂掉时，原先客户端在主节点申请的一把锁，还没即使同步到从节点，从节点变成主节点后，另外一个客户端请求加锁，被批准，就导致系统同样一把锁被两个客户端同时持有。

### 4.3.1 Redlock算法

加锁时，它会向半数节点发送set(key, value, nx=True, ex=xxx)指令，只要过半节点set成功，就认为加锁成功，释放锁时，需要向所有节点发送del指令。不过Redlock算法还需要考虑出错重试、时钟漂移等很多细节问题

### 4.3.2 Redlock使用场景

如果你很在乎高可用性，希望即使挂掉一台Redis也完全不受影响，就应该考虑Redlock，不过性能也会下降

### 4.4 朝生暮死 — 过期策略

Redis内部有个死神，他时刻盯着所有设置了过期时间的key，寿命一到就立即收割。

### 4.4.1 过期的key集合

Redis会将每个设置了过期时间的key放入到一个独立的字典中，以后会定时遍历这个字典来删除到期的key。除了遍历外，还会使用惰性策略来删除过期key，惰性删除是客户端访问这个key的时候，对key进行过期检查，如果过期了就立即删除。

### 4.4.2 定时扫描策略

Redis每秒进行10次过期扫描，采用简单的贪心策略：

1. 从过期字典随机选出20个key

2. 删除这20个key中已经过期的key

3. 如果过期的key的比例超过1/4，那么就重复步骤1

为了扫描不会出现循环过度，算法加了扫描的上限，默认不超过25ms

如果客户端请求到来时，服务器正好进入过期扫描状态，客户端的请求将会等待25ms后才会进行处理，如果客户端将超时时间设置的比较短，10ms，就会因为超时而关闭。而且无法从slowlog中看到慢查询记录，因为慢查询是逻辑处理时间，不包含等待时间。所以开发人员一定要注意过期时间，如果大批量的key过期，要给过期时间设置随机范围，而不能同一时间过期。

### 4.4.3 从节点的过期策略

从节点不会进行过期扫描，主节点在key到期的时候，会在AOF文件里增加一条del指令，同步到所有从节点。

## 4.5 优胜劣汰 — LRU

实际内存超出maxmemory时，Redis提供的策略：

1. noeviction：不会继续服务写请求（del请求可继续服务），读请求可以继续进行，默认淘汰策略

2. volatile-lru：尝试淘汰设置了过期时间的key，最少使用的key优先被淘汰

3. volatile-ttl：淘汰策略是key的剩余寿命ttl的值，值越小优先被淘汰

4. volatile-random：淘汰key是从过期key集合中随机的key

5. allkeys-lru：全体的key集合进行lru

6. allkeys-random：淘汰的key是全体集合进行随机

### 4.5.1 LRU算法

位于链表尾部的元素就是不被重用的元素，所以会被踢掉。位于表头的元素就是最近刚刚被人用过的元素，所以暂时不会被踢。

### 4.5.2 近似LRU算法

- Redis使用的是一个近似LRU算法，它跟LRU算法还不太一样，之所以不使用LRU算法，是因为其需要消耗大量的额外内存，需要对现有的数据结构进行较大的改造。

- Redis为实现近似LRU算法，给每个key增加了一个额外的小字段，这个字段长度是24个bit，也就是最后一次被访问的时间戳。

- LRU只有惰性删除，Redis执行写操作的时候，发现内存超出maxmemory，就会执行一次LRU淘汰算法，随机采样5（可设置）个key，然后淘汰掉最旧的key，如果内存还超过maxmemory，就继续随机采样淘汰

## 4.6 平波缓进 — 懒惰删除

Redis是单线程的，Redis内部实际上并不是只有一个主线程，还有几个异步线程专门处理一些耗时的操作

### 4.6.1 Redis为什么使用懒惰删除

如果被删除的key是一个非常大的对象，删除操作就会导致单线程卡顿，4.0后引入了unlink指令，能对删除操作进行懒处理，丢给后台线程来异步回收内存。unlink相当于减掉树枝焚烧

### 4.6.2 flush

flushdb和flushall指令很慢，4.0后提供了后面增加async将整颗树根连根拔起，扔给后台进程焚烧

### 4.6.3 异步队列

主线程将对象的引用从“大树”中摘除后，会将这个key的内存回收操作包装成一个任务，塞进异步任务队列，后台线程会从这个异步队列中取任务

### 4.6.4 AOF Sync也很慢

Redis每秒（可设置）次同步AOF日志到磁盘，执行AOF sync操作的线程是一个独立的异步线程，同样它也有一个属于自己的任务队列。

### 4.6.5 更多异步删除点

还有一种flush操作，发生正在全量同步的从节点中，在接收完整的rdb文件后，也需要将当前内存一次性清空。

## 4.7 妙手仁心 — 优雅地使用Jedis

Java程序一般都是多线程的应用程序，意味着我们很少直接使用Jedis，而是要Jedis的连接池 — JedisPool，因为Jedis对象不是线程安全的，当我们使用Jedis对象时，需要从连接池中拿出一个Jedis对象独占，使用完毕后再归还给线程池

### 4.7.1 重试

遇到错误连接的时候需要发送重试指令，也不能无限次的重试

## 4.8 居安思危 — 保护Redis

### 4.8.1 指令安全

比如一些指令keys会导致Redis卡顿，flushdb和flushall会清空所有数据，rename-command指令用于将某些危险的指令修改成特别的名字，用来避免人为误操作。

### 4.8.2 端口安全

运维人员务必在Redis的配置文件中指定监听的IP地址，增加Redis的密码访问限制，客户端必须使用auth指令

### 4.8.3 Lua脚本安全

必须禁止Lua脚本由用户输入的内容生成，同时我们应该让Redis以普通用户的身份启动。

### 4.8.4 SSL代理

Redis并不支持SSL链接，如果要用到公网上，可以考虑SSL代理，常见的有ssh，官方推荐spiped工具，同时SSL代理也可用于主从复制上

## 4.9 隔墙有耳 — Redis安全通信

### 4.9.1 spiped原理

spiped接收Redis Client发送过来的请求，然后传到server对应的spiped，然后解密给Redis Server，Server再走一个反向流程给Client

### 4.9.2 spiped使用入门

Spiped可同时支持多个client，但不支持多个server

# 第5篇 源码篇

## 5.1 丝分缕析 — 探索“字符串”内部

C语言里面的字符串标准以NULL结束，但获取长度的时候是O（n)，Redis承受不起。Redis的字符串叫SDS，它是一个带着长度信息的字节数组。capacity表示所分配数组的长度，len代表字符串实际长度。

### 5.1.1 embstr VS raw

- 长度特别短的时候使用embstr，长度超过44字节使用raw形式存储。

- RedisObject包含类型type(4bit)，同一类型的type会有不同的存储形式encoding(4bit)，为了记录LRU信息（24bit)，每个对象有个引用计数refcount(4 bytes)，ptr指向真实对象的具体存储位置

### 5.1.2 扩容策略

在字符串小于1MB，扩容采用加倍策略。超过1MB以后，只扩容1MB

## 5.2 循序渐进 — 探索”字典”内部

### 5.2.1 字典内部结构

- 字典内部结构包含两个hashtable，通常情况下只有一个有值，当扩容的时候，需要渐进式移出，移出完成后会删除旧的hashtable

- hashtable的结构和Java的HashMap几乎是一样的，都是通过分桶的方式解决hash冲突。第一维是数组，第二维是链表

### 5.2.2 渐进式rehash

大字典扩容比较耗时，Redis使用渐进式rehash小步搬迁。搬迁操作埋伏在当前字典的后续指令中（客户端的hset、hdel等）Redis还会再定时任务中对字典主动搬迁

### 5.2.3 查找过程

hash_func可以将key映射到一个整数，不通的key会被映射成分布比较均匀散乱的整数。

### 5.2.4 hash函数

hashtable的性能好不好完全取决于hash函数的质量，如果hash函数能够将key打散的比较均匀，那么hash函数就是个好函数。Redis字典默认hash函数是siphash

### 5.2.5 hash攻击

有的hash函数存在偏向性，会将查找从O(1)退化到O(n)

### 5.2.6 扩容条件

正常情况下，hash元素的个数等于第一维数组长度，就开始扩容。扩容原数组的2倍，如果Redis正在做bgsave，Redis尽量不扩容减少内存页过多分离。但到达5倍就会强制扩容

### 5.2.7 缩容条件

缩容条件是元素个数低于数组长度的10%，缩容不考虑是否在bgsave

### 5.2.8 set的结构

set的结构底层也是字典，只不过value是NULL，其他特征和字典一致

## 5.3 挨肩迭背 — 探索“压缩列表”内部

- 在元素比较少的时候zset和hash采用压缩列表进行存储，压缩列表是一块连续的内存空间，元素之间紧挨着存储，没有任何冗余空隙。

- 压缩列表支持双向遍历，所以才会有ztail_offset字段

### 5.3.1 增加元素

因为紧凑存储，意味着每插入一个新元素就需要调用realloc扩展内存。所以不宜存储大型字符串

### 5.3.2 级联更新

如果ziplist里面的每个entry恰好存储了253字节内容，那么第一个entry内容的修改就会导致后续所有entry的级联更新

### 5.3.3 intset小整数集合

当set集合容纳的元素都是整数并且元素个数较小时，Redis会使用intset来存储集合元素。

### 5.4 风驰电掣 — 探索”快速列表”内部

quicklist是ziplist和linkedlist的混合体，它将linkedlist按段切分，每一段使用ziplist让存储紧凑，多个ziplist之间使用双向指针串联起来。

### 5.4.1 每个ziplist存多少元素

默认ziplist长度为8KB，超过这个字节数就会灵气一个ziplist，这个长度可由list-max-ziplist-size决定

### 5.4.2 压缩深度

默认不压缩，由list-comporess-depth决定。为了支持快速的push/pop操作，首尾的ziplist不压缩

## 5.5 凌波微步 — 探索“跳跃列表”内部

zset是一个复合结构，一方面他需要一个hash存储value和score的对应关系，另一方面需要提供按照score排序的功能，还需要能够指定score范围来获取value列表的功能，就需要“跳跃列表”，内部实现是一个hash字典加一个跳跃列表skiplist

### 5.5.1 基本结构

跳跃列表共有64层，每一个key/value对应的结构是zslnode结构，kv之间使用指针串起来形成双向链表结构，他们是有序排列的，从小到大，不同的kv层高可能不一样，层数越高kv越少，每一层元素的遍历都是从kv header出发。

### 5.5.2 查找过程

从header的最高层开始遍历找到第一个节点（最后一个比我小的元素），然后从这个节点开始降一层再遍历找到第二个节点（最后一个表我小的元素），最后降到最底层进行遍历就找到了期望的节点。

### 5.5.3 随机层数

对于每一个新插入的节点，都需要随机算法给它分配一个合理的层数。概率逐级递减2倍

### 5.5.4 插入过程

先搜索插入点合适的搜索路径，创建新节点，分配随机层数，再将搜索路径上的节点和这个新节点通过前后指针串起来。同时需要更新maxLevel

### 5.5.5 删除过程

搜索路径找出来，然后对于每个层的相关节点进行重排前后后向指针，同事需要更新maxLevel

### 5.5.6 更新过程

zadd如果value不存在，那么插入过程，如果存在就是更新score的值，不会带来排序的改变，就不需要调整位置，如果排序位置变了，需要调整位置。一个简单的策略就是先删除这个元素，在插入这个元素。

### 5.5.7 如果score值都一样呢

zset不仅只看score，score相同还会比较value

### 5.5.8 元素排名怎么算出来的

zset可以获取元素排名rank，Redis在skiplist的forward指针上进行了优化，给forward指针增加span跨度属性，表示从前一个节点沿着当前层的forward指针跳到当前这个节点中间会跳过多少节点。

## 5.6 破旧立新 — 探索“紧凑列表”内部

listpack跟ziplist的结构几乎一模一样，只是少了一个zltail_offset字段。ziplist通过这个字段来定位出最后一个元素的位置，用于逆序遍历。listpack长度字段放在了元素定的尾部，而且存储的不是上一个元素的长度，是当前元素的长度。所以就可以省去了zltail_offset，最后一个元素位置可以通过total_bytes字段和最后一个元素的长度字段计算出来。

### 5.6.1 级联更新

消灭了ziplist存在的级联更新，元素与元素之间完全独立，不会因为一个元素的长度变长就导致后续的元素内容收到影响。

### 5.6.2 取代ziplist尚待时日

ziplist在Redis的数据结构中使用太广泛了，替换起来复杂度会非常高。listpack目前只使用在新增加的Stream数据结构中

## 5.7 金枝玉叶 — 探索”基数树”内部

rax是一个有序字典树（基数树Radix Tree），按照key的字典排列，支持快速地定位、插入和删除操作。hash不具备排序功能，zset则是按照score进行排序的。rax跟zset不同的是它是按照key排序的。

### 5.7.1 应用

一本英文字典看成一颗Radix Tree，有了这棵树，就可以快速地检索字典，还可以查询以某个前缀开头的单词有哪些。可利用在公安局的居民档案、时间序列应用、Web服务器的Router、Stream的消息队列（消息ID是时间戳+序号），Cluster中用来记录槽位和key的对应关系

### 5.7.2 结构

rax是一颗比较特殊的Radix Tree，结构不是标准的Radix Tree，如果一个中间节点有多个叶节点，那么路由键就只是一个字符；如果只有一个叶子节点，那么路由键就是一个字符串。

## 5.8 精益求精 — LFU VS LRU

LFU是Least Frequently Used，表示按最近的访问频率进行淘汰，它比LRU更加精确地表示了一个key被访问的热度。

### 5.8.1 Redis对象的热度

所有的对象头结构中都有一个24bit的字段，这个字段用来记录对象的热度

### 5.8.2 LRU模式

在LRU模式下，lru字段存储的是Redis始终server.lruclock，默认是对2的24次方取模的结果。

### 5.8.3 LFU模式

在LFU模式下，lru字段24bit用来存储两个值，分别是ldt（last decrement time）和logc（logistic counter)。logc是8bit，存储访问频次的对数值，并且值还会随着时间衰减，新建的对象默认为5.ldt是16bit，用来存储上一次logc的更新时间。它取的分钟时间戳对2的16进行取模，每45天会折返。

### 5.8.4 为什么Redis要缓存系统时间戳

每一次获取系统时间戳都是一次系统调用，系统调用相对来说比较费时间，它需要对时间进行缓存，获取时间都是从缓冲直接拿。

### 5.8.5 Redis为什么在获取lruclock时使用原子操作

Redis实际上不是单线程，背后还有几个异步线程也在默默工作，llruclock字段是需要支持多线程读写的。使用attomic读写能保证多线程lruclock数据的一致性

### 5.8.6 如何打开LFU模式

淘汰策略参数maxmemory-policy增加了2个选项，volatile-lfu和allkeys-lfu

## 5.9 如履薄冰 — 懒惰删除的巨大牺牲

一步线程在Redis内部有一个特别的名字：BIO。

### 5.9.1 懒惰删除的最初实现不是异步线程

异步线程不用为每种数据结构适配一套渐进式释放策略，也不用搞个自适应算法来仔细控制回收频率，只是将对象从全局字典中摘掉，然后往队列一扔，主线程就干别的去了。异步线程从队列中取出对象，直接走正常的同步释放逻辑就可以了。

### 5.9.2 异步线程方案其实也相当复杂

Redis内部对象有共享机制阻碍了异步线程的改造，比如集合的并集操作sunionstore用来将多个集合合并成一个新集合。懒惰删除相当于彻底砍掉某个树枝，将它扔到异步删除队列中，如果底层是共享的，就做不到彻底删除。为了支持懒惰删除，Antirez将对象的共享机制彻底抛弃。

### 5.9.3 异步删除的实现

执行懒惰删除时，Redis将删除操作的相关参数封装成一个bio_job结构，然后追加到链表尾部，异步线程通过遍历链表摘取job元素来挨个执行异步任务。

### 5.9.4 队列安全

当主线程将任务追加到队列之前需要给它加锁，追加完毕后，再释放锁，还需要唤醒异步线程 — 如果其在休眠的话。异步线程摘取也需要加锁，摘出来后解锁。

### 5.10 跋山涉水 — 深入字典遍历

### 5.10.1 一边遍历一边修改

Redis对象树的主干是一个字典，keys命令搜索指定模式key时，会遍历整个主干字典。如果key被找到了，但对象已经过期，就会从主干字典中将该key删除。

### 5.10.2 重复遍历的难题

字典在扩容的时候要进行渐进式迁移，会存在新旧两个hashtable，遍历完旧的时候进行了rehashStep，遍历新的就会重复遍历

### 5.10.3 迭代器的结构

Redis为字典提供安全迭代器和不安全迭代器，安全指遍历过程可以对字典进行查找和修改，为了保证不重复就会禁止rehashStep。不安全是指在遍历过程中字典是只读的，不可以修改，正能调用dictNext对字典进行持续遍历，部的调用任何可能触发过期判断的函数。好处是不影响rehash，代价就是遍历的元素可能会出现重复。安全迭代器在开始遍历时候，会给字典打上一个标记，有了这个标记rehashStep就不会执行，遍历元素就不会重复出现。

### 5.10.4 迭代过程

值得注意的是，在字典扩容时进行rehash，将旧数组中的链表迁移到新的数组中，某个具体槽位下的链表只可能会迁移到新数组的两个槽位中

### 5.10.5 迭代器的选择

- 如果遍历不允许出现重复，就得使用安全迭代器。比如bgaofrewrite需要遍历所有对象，转换成操作指令进行持久化，绝对不允许出现重复。bgsave也需要遍历所有对象持久化，不允许重复。

- 如果遍历需要处理元素过期，需要对字典进行修改，那也不许使用安全迭代器。

- 如果允许遍历过程出现元素重复，不进行字典结构修改，非安全迭代器