本来是想看guide哥的，但确实一些高频考点讲的不是很细。所以就直接all in 小林了。后续会持续更新，把一些低频考点也补上。~期待的话请多多为我点赞收藏吧QAQ~

Redis

基础

Redis

定义：基于 C 语言开发的开源 NoSQL 数据库。数据存储在内存中，支持持久化。数据是KV键值对数据。

好处：

• 高性能：访问速度快
• 高并发
• 功能全面

• • 分布式锁
  • 限流
  • 消息队列

为什么Redis这么快

• redis基于内存，内存的访问速度要比磁盘快
• redis内置多种优化后的数据类型，其底层编码会随状态而变化
• redis基于reactor模式设计开发了一套高效事件处理模型，主要是单线程事件循环和IO多路复用
• redis通信协议实现简单且解析高效

分布式缓存常见的技术选型方案有哪些？

以前有Memcached。腾讯开源的Tendis，但几乎不维护更新了。

目前，比较业界认可的 Redis 替代品还是下面这两个开源分布式缓存（都是通过碰瓷 Redis 火的）：

• Dragonfly：一种针对现代应用程序负荷需求而构建的内存数据库，完全兼容 Redis 和 Memcached 的 API，迁移时无需修改任何代码，号称全世界最快的内存数据库。
• KeyDB： Redis 的一个高性能分支，专注于多线程、内存效率和高吞吐量。

首选还是redis。

什么是Redis Module？

在redis4.0之后，支持使用module来扩展功能。这些module以动态链接库（so文件）的形式被加载到redis。

我们可以基于redis来定制开发module，比如实现搜索引擎功能，自定义分布式锁和分布式限流。

目前，被 Redis 官方推荐的 Module 有：

• RediSearch：用于实现搜索引擎的模块。
• RedisJSON：用于处理 JSON 数据的模块。
• RedisGraph：用于实现图形数据库的模块。
• RedisTimeSeries：用于处理时间序列数据的模块。
• RedisBloom：用于实现布隆过滤器的模块。
• RedisAI：用于执行深度学习/机器学习模型并管理其数据的模块。
• RedisCell：用于实现分布式限流的模块。
• ……

关于 Redis 模块的详细介绍，可以查看官方文档：https://redis.io/modules

应用

Redis 除了做缓存，还能做什么？

• 分布式锁：基于Redisson实现。
• 限流：使用redis+lua来实现。也可以直接使用Redisson的RRateLimiter来实现分布式限流，底层就是基于lua+令牌桶算法
• 消息队列：自带的list数据类型可以作为简单的消息队列使用。redis5.0新增的 Stream类型 更适合做消息队列，它类似kafka，有主题和消费组的概念，支持消息持久化和ack机制。
• 复杂业务场景：使用redis或者redis扩展提供的数据结构实现。比如bitmap统计活跃用户，sortedset维护排行榜。

基于redis实现分布式锁

数据类型

常见数据类型

5种基本数据类型：

• String
• List
• Hash
• Set
• Zset

3种特殊数据类型：

• HyperLogLog
• Bitmap
• Geospatial

String

定义：redis中最常用的数据类型，是二进制安全的，可以用来存储任何类型数据，如字符串，整数，浮点数、序列化后的对象。

场景：

• 缓存对象：JSON数据，或者通过key来分离 user：id：属性
• 常规的计数：redis处理命令是单线程的，所以适用于计数场景，如文章阅读量，订单个数。
• 分布式锁：为锁加上过期时间防止锁无人解锁一直存在，解锁时需要用lua脚本里判断（保证原子性）是否是持锁的客户端，是才能解锁。
• 共享session：在分布式系统中，session保存在各自的服务器中，如果用户访问不同的服务器，session就不再通用，所以需要用redis来作一个分布式服务器的session统一。

底层数据结构

string类型的底层数据结构实现主要是 int 和 简单动态字符串（SDS），SDS相比c语言的字符串：

• 不仅能保存文本数据，还能保存二进制数据（比如图片）：因为它使用len属性来判断字符串是否结束，而不是空字符来判断，并且SDS的api也都是以二进制的方式处理数据的。
• 获取字符串长度的时间复杂度是O（1）：因为sds结构里len属性记录了字符串长度。
• SDS API是安全的，拼接字符串不会造成缓冲区溢出：因为SDS在拼接字符串前会先检查SDS空间是否足够，不够就扩容。

内部编码

• int
• embstr
• raw

int

如果字符串对象保存的是整数，并且在long类型的范围内，那么字符串对象结构里的ptr将直接转为long类型并存储该值，并将字符串对象的编码设置为int（没错虽然是long类型的值，但是字符串编码是int）

embstr

如果字符串对象保存的是字符串，并且字符串大小在44字节内，那么它将以简单动态字符串（SDS）来保存该字符串，并把字符串对象编码设为embstr

raw

如果字符串对象保存的是字符串，并且字符串大小大于44字节，那么它将以简单动态字符串（SDS）来保存该字符串，并把字符串对象编码设为raw

不同rredis版本embstr和raw的边界值是不一样的

在redis5.0以后是44字节

embstr和raw编码都使用SDS来存值，但embstr编码只需要一次内存分配，因为它的SDS和redisobject是连在一起的（连续内存），而raw编码需要两次内存分配，一次redisobject，一次SDS。

好处：

• embstr编码的字符串对象内存分配次数更少，包括内存释放也只需要一次，减少内存碎片
• embstr编码的字符串对象所有数据保存在一块连续内存可以更好利用cpu缓存提升性能

坏处：

• 如果字符串长度增加需要重新分配内存时，就要同时重新分配redisobject和sds的内存空间，所以embstr编码的字符串对象直接设计成了只读，当我们对该编码下的字符串对象进行修改时，实际会把该字符串对象的编码改为raw，然后再执行命令。

List

定义：字符串列表，按插入顺序排序，可以在头尾两端操作元素。列表最大长度为2^32 - 1

场景：

• 消息队列：有普通的和阻塞式读取。
  处理重复消息：可以通过给消息生成一个全局唯一id，然后在收到消息时拿消息id和记录中已处理的消息id比对。如LPUSH mq "111000102:stock:99"
  保证消息可靠性：使用BRPOPLPUSH命令，在读取消息的同时，把该消息插入到另一个list中备份。如果消息没能正常处理，就可以通过从备份list中重新读取消息处理了。
  坏处：

• • 不支持多个消费者消费同一条消息：因为一个消费者消费完就删除了。（解决方法：Stream类型支持消费组形式读取）

底层数据结构

QuickList

Hash

定义：键值对集合。它的value形式是field对应value。

场景：

• 缓存对象：String类型也可以，但相比它，对于对象中的属性修改要方便很多。
• 购物车：用户id为key，商品id为field，商品数量为value

底层数据结构

• ZipList：如果哈希类型元素个数小于512个，所有值小于64字节，就使用压缩列表。
• Dict：不满足ZipList条件就使用哈希表。

Set

定义：无序、唯一的键值集合。集合的最大容量为2^32 -1

场景：

• 点赞：key为文章id，value为用户id
• 共同关注：SINTER取交集
• 抽奖活动：key为抽奖活动名，value为员工名，如果运行重复中奖，使用SRANDMEMBER命令；如果不允许重复中奖，使用SPOP命令

底层数据结构

• Intset：如果集合内元素全为整数并且个数小于512个，就会使用整数集合作为Set的底层数据结构。
• Dict：不满足Intset的使用条件，就使用哈希表。

Zset

定义：有序集合，相比set多了一个score用于排序。所以每个存储元素有score和value两个值。

场景：

• 最新列表：先插入的score小，后插入的score大
• 排行榜：key为用户，score为点赞数，value为文章id
• 电话、姓名排序：score统一设为同一个值，这样就会仅靠value进行排序，并且能达到去重效果。

底层数据结构

• ZipList：如果有序集合内元素小于128个，并且每个元素的值小于64字节，就使用压缩列表
• SkipList：如果不满足ZipList，就使用跳表 ps：其实是跳表+哈希表，只不过哈希表只用于获取元素的权重，大部分操作还是跳表实现的。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

BitMap

定义：位图。是一串连续的二进制数组（只含0和1）。可以通过偏移量来定位元素。元素使用bit作为单位，能节省内存空间。

场景：

• 签到统计：key为年月，offset为 当天-1，value为1，BITCOUNT来统计签到次数
• 判断用户登录态：key为用户登录状态集合，offset为用户id
• 连续签到用户总数：key为日期，offset为用户id，要连续几天的签到，就设置几个BitMap，对这些BitMap做与运算，就能得到满足连续签到n天条件的用户。

底层数据结构

使用String类型，Redis把String类型的字节数组的每个bit位利用起来，作为元素的二值判断。所以可以把bitmap看做bit数组。

常用命令

bitmap 基本操作：

# 设置值，其中value只能是 0 和 1
SETBIT key offset value

# 获取值
GETBIT key offset

# 获取指定范围内值为 1 的个数
# start 和 end 以字节为单位
BITCOUNT key start end

bitmap 运算操作：

# BitMap间的运算
# operations 位移操作符，枚举值
  AND 与运算 &
  OR 或运算 |
  XOR 异或 ^
  NOT 取反 ~
# result 计算的结果，会存储在该key中
# key1 … keyn 参与运算的key，可以有多个，空格分割，not运算只能一个key
# 当 BITOP 处理不同长度的字符串时，较短的那个字符串所缺少的部分会被看作 0。返回值是保存到 destkey 的字符串的长度（以字节byte为单位），和输入 key 中最长的字符串长度相等。
BITOP [operations] [result] [key1] [keyn…]

# 返回指定key中第一次出现指定value(0/1)的位置
BITPOS [key] [value]

HyperLogLog

定义：一个用于统计基数的集合，基数统计就是统计一个集合中不重复元素的个数。它是基于概率完成的，结果并非非常精确。标准误算率是 0.81%

好处：在输入元素数量或体积很大时，计算基数所需的内存总是固定的，并且很小。每个HyperLogLog键只需要12kb内存就能算出近2^64个不同元素的基数。

场景：

• 统计大用户量的网页UV，key为网页，element为用户id。（如果要精确统计，还是使用Set或Hash类型）

常见命令

# 添加指定元素到 HyperLogLog 中
PFADD key element [element ...]

# 返回给定 HyperLogLog 的基数估算值。
PFCOUNT key [key ...]

# 将多个 HyperLogLog 合并为一个 HyperLogLog
PFMERGE destkey sourcekey [sourcekey ...]

底层数据结构

太难，不会。

GEO

定义：存储地理位置。

场景：

• 打车：key为所有车辆的集合，经纬度，然后member为车辆id

底层数据结构

使用的SortedSet类型，对经纬度进行编码，然后转换为对应元素的权重分数。

常用命令

# 存储指定的地理空间位置，可以将一个或多个经度(longitude)、纬度(latitude)、位置名称(member)添加到指定的 key 中。
GEOADD key longitude latitude member [longitude latitude member ...]

# 从给定的 key 里返回所有指定名称(member)的位置（经度和纬度），不存在的返回 nil。
GEOPOS key member [member ...]

# 返回两个给定位置之间的距离。
GEODIST key member1 member2 [m|km|ft|mi]

# 根据用户给定的经纬度坐标来获取指定范围内的地理位置集合。
GEORADIUS key longitude latitude radius m|km|ft|mi [WITHCOORD] [WITHDIST] [WITHHASH] [COUNT count] [ASC|DESC] [STORE key] [STOREDIST key]

Stream

定义：专为消息队列设置的数据类型

原来用List实现的消息队列，有着 无法重复消费消息，消息无法持久化 的缺陷。而Stream可以解决。

好处：

• 支持消息的持久化
• 支持自动生成全局唯一 ID，解决消息重复消费问题
• 支持 ack 确认消息的模式，解决消息未处理完丢失的问题
• 支持消费组模式，解决消息不能被多个消费者消费的问题

场景：

• 消息队列

全局id在插入消息后自动返回，由两部分组成，一部分是服务器当前计算的时间，另一部分是消息序号，从0开始计数。

# * 表示让 Redis 为插入的数据自动生成一个全局唯一的 ID
# 往名称为 mymq 的消息队列中插入一条消息，消息的键是 name，值是 xiaolin
> XADD mymq * name xiaolin
"1654254953808-0"

XREAD读取消息可以从指定消息id的下一个消息开始读取

# 从 ID 号为 1654254953807-0 的消息开始，读取后续的所有消息（示例中一共 1 条）。
> XREAD STREAMS mymq 1654254953807-0
1) 1) "mymq"
   2) 1) 1) "1654254953808-0"
         2) 1) "name"
            2) "xiaolin"

阻塞读可以在XREAD后面加上BLOCK配置项,单位为毫秒

# 命令最后的“$”符号表示读取最新的消息
> XREAD BLOCK 10000 STREAMS mymq $
(nil)
(10.00s)

XGROUP可以创建消费组，XREADGROUP可以让消费组内的消费者读取消息。

# 创建一个名为 group1 的消费组，0-0 表示从第一条消息开始读取。
> XGROUP CREATE mymq group1 0-0
OK
# 创建一个名为 group2 的消费组，0-0 表示从第一条消息开始读取。
> XGROUP CREATE mymq group2 0-0
OK

# 消费组 group1 内的消费者 consumer1 从 mymq 消息队列中读取所有消息的命令如下
# 命令最后的参数“>”，表示从第一条尚未被消费的消息开始读取。
> XREADGROUP GROUP group1 consumer1 STREAMS mymq >
1) 1) "mymq"
   2) 1) 1) "1654254953808-0"
         2) 1) "name"
            2) "xiaolin"

同一个消费组不能消费同一条消息，不同的消费组可以，前提是创建消费组的时候消费消息开始位置相同。

使用消费组的目的是为了让不同的消费者共同承担消费消息。

常见命令

• XADD：插入消息，保证有序，可以自动生成全局唯一 ID；
• XLEN ：查询消息长度；
• XREAD：用于读取消息，可以按 ID 读取数据；
• XDEL ： 根据消息 ID 删除消息；
• DEL ：删除整个 Stream；
• XRANGE ：读取区间消息
• XREADGROUP：按消费组形式读取消息；
• XPENDING 和 XACK：

• • XPENDING 命令可以用来查询每个消费组内所有消费者「已读取、但尚未确认」的消息；
  • XACK 命令用于向消息队列确认消息处理已完成；

基于 Stream 实现的消息队列，如何保证消费者在发生故障或宕机再次重启后，仍然可以读取未处理完的消息？

Stream会使用内部队列（pending list）来存储消费者中读取但未处理的消息。

消费者在处理完消息后，需要执行XACK命令来确认消息已经处理完。如果没有发送该命令，消息就会留存在内部队列。我们可以使用XPENDING命令来读取这些未被处理的消息。

127.0.0.1:6379> XPENDING mymq group2
1) (integer) 3
2) "1654254953808-0"  # 表示 group2 中所有消费者读取的消息最小 ID
3) "1654256271337-0"  # 表示 group2 中所有消费者读取的消息最大 ID
4) 1) 1) "consumer1"
      2) "1"
   2) 1) "consumer2"
      2) "1"
   3) 1) "consumer3"
      2) "1"

如果想查看某个消费者具体读取了哪些数据，可以执行下面的命令：

# 查看 group2 里 consumer2 已从 mymq 消息队列中读取了哪些消息
> XPENDING mymq group2 - + 10 consumer2
1) 1) "1654256265584-0"
   2) "consumer2"
   3) (integer) 410700
   4) (integer) 1

此时，一旦消息"1654256265584-0"被消费者2处理了，消费者2就可以使用XACK来通知Stream确认处理完该消息，随后该消息就会被移出内部队列。

> XACK mymq group2 1654256265584-0
(integer) 1

> XPENDING mymq group2 - + 10 consumer2
(empty array)

基于 Stream 消息队列与专业的消息队列有哪些差距？

• 消息不丢失
• 消息可堆积

Stream在三个环节对于消息丢失情况讨论：

• 生产者：只要能正常收到mq的ack确认就代表消息发送成功，如果返回异常就重发就行，所以这个阶段不会丢消息。
• 消费者：Stream提供了内部队列（PENDING List）来保存消费者读取了但未处理的消息，就算消费端出问题，也能在恢复后通过该队列继续处理消息，并最终向Stream发送XACK确认命令。所以也不会丢消息。
• Redis中间件：可能会丢消息。

• • AOF持久化为每秒写盘，写盘操作是异步的，可能会数据丢失
  • 主从复制也是异步的，也可能会数据丢失

Stream 消息可堆积吗？

可以堆积但不多，但如果消息堆积过多，会导致内存占用过高，有Out Of Memory的风险。所以Stream有指定队列的最大长度，当队列消息超过上限后，旧消息会被删除，也就是会丢失数据。

而专业的消息队列数据都存储在磁盘上，就算出现消息堆积也就多占点磁盘空间。

Redis 发布/订阅机制为什么不可以作为消息队列？

• 它不具备数据持久化能力，消息容易丢失。
• 消息不能暂存。发布者发布消息后，如果订阅者离线就没法接收到消息了。

数据结构

键值对数据库

使用 哈希表 来保存键值对。

• redisDB：表示redis的结构，里面存放了指向dict结构的指针
• dict结构：存放了两个hash表，一个是存储数据，一个是rehash时使用。
• dictht 结构：哈希表的结构，里面存放了哈希表数组，数组里每个元素都是一个指向hash节点的指针
• dictEntry 结构：hash节点的结构，里面分别有key的指针和value的指针，key指针指向String对象，value指针可以指向各种数据类型的对象。

key和value指针指向的都是redis对象，由redisobject表示。

• type：表示对象是哪种数据类型（String，List，Hash...）
• encoding：表示对象的底层数据结构。
• ptr：指向底层数据结构的指针

SDS

定义：Redis是用c语言实现的，但字符串并没有使用c语言的char*数组，而是使用了简单动态字符串作为数据结构来表示字符串。

不使用c语言的字符串的原因

• 获取字符串长度时间为O（n）——需要遍历到'\0'字符为止
• 字符串不能保存二进制数据——遇到“\0”字符就会认为读到了末尾。
• 字符串操作函数效率不高（遍历到"\0"），并且不安全，如strcat拼接函数有缓冲区溢出风险。——c语言字符串不会记录自身缓冲区大小，所以在原字符串内存不足时增加过多的字符，可能会出现缓冲区溢出，造成程序终止。

结构设计

• len：记录字符串长度，所以获取时只需要O（1）时间复杂度（虽然sds不再需要 \0 来标记结尾了，但为了兼容c语言的字符串函数，仍然会加上）
• alloc：分配的空间长度，所以alloc-len就可以获得剩余内存空间，可用于判断剩余空间是否满足字符串操作需求，不满足就可以自动扩容，能避免缓冲区溢出问题
  扩容函数：先计算出新的需要的容量，然后判断是否小于1MB，如果是，就扩容为所需容量的2倍；如果不是，就扩容到所需容量+1MB。
• flags：用于表示不同类型的sds，一共有五种，sdshdr5，sdshdr8，sdshdr16，sdshdr32，sdshdr64
• buf[] ：字符数组，存放实际数据，可以存储二进制数据。

flags成员变量设计

五种类型的区别在于，len和alloc的数据类型不同

struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len;
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};


struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};

• sdshdr16 类型的 len 和 alloc 的数据类型都是 uint16_t，表示字符数组长度和分配空间大小不能超过 2 的 16 次方。
• sdshdr32 则都是 uint32_t，表示表示字符数组长度和分配空间大小不能超过 2 的 32 次方。

设计不同数据类型的len和alloc，可以灵活地保存各种大小的字符串，来节约空间。

除此之外，编译中还添加了__attribute__ ((packed))来优化，取消了字节优化对齐，改为按实际占用字节对齐。

不添加__attribute__ ((packed))，如

struct test1 {
    char a;
    int b;
 } test1;

链表

定义：C语言没有设计链表数据结构，所以redis自己设计了一个。是一个双向链表。

好处：

• 获取表头和表尾节点的复杂度为O（1），获取某个节点的上个或下个节点也是。
• 获取链表节点数量时间复杂度为O（1）——链表结构提供了len属性。
• 链表节点的值可以是不同数据类型——链表节点的value属性的数据类型是void指针，并且有dup，free，match函数指针来对节点设置个性的实现。

缺点：

• 无法很好利用cpu缓存——链表节点内存是不连续的，而只有像数组那样连续内存空间才能更充分地利用cpu缓存来加速访问。
• 链表节点的结构内存开销比较大。

因此，redis的list对象在数据较少时，底层使用压缩列表来节约内存空间。

不过压缩列表存在性能问题，所以redis在后续版本设计了新的数据结构QuickList，并让它作为list的底层实现

后续redis又设计了新的数据结构listpack，它也使用了压缩列表的紧凑型内存布局，并把它作为压缩列表的替代，作为hash对象和zset对象的底层实现。

结构设计

链表节点结构

typedef struct listNode {
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
} listNode;

链表结构

typedef struct list {
    //链表头节点
    listNode *head;
    //链表尾节点
    listNode *tail;
    //节点值复制函数
    void *(*dup)(void *ptr);
    //节点值释放函数
    void (*free)(void *ptr);
    //节点值比较函数
    int (*match)(void *ptr, void *key);
    //链表节点数量
    unsigned long len;
} list;

dup，free，match函数可自定义实现。

压缩列表

定义：一种内存紧凑型数据结构，它占用一段连续的内存空间，可以利用cpu缓存优化，而且可以针对不同长度的数据进行相应的编码来节约内存占用。

缺点：

• 不能存储过多数据，否则查询效率会降低
• 新增或修改元素时，内存会重新分配，可能会导致连锁更新问题。

所以，一般在redis对象（LIst，Hash，Zset）包含元素较少时，才会使用压缩列表作为底层数据结构。

结构设计

压缩列表结构

• zlbytes：记录整个压缩列表占用对内存字节数；
• zltail：记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
• zllen：记录压缩列表包含的节点数量；
• zlend：标记压缩列表的结束点，固定值 0xFF（十进制255）。

如果只是查找首尾元素，那么可以直接通过zltail和三字段的内存占用作偏移量直接得到，而其他元素就只能通过遍历了，所以并不适合存储过多元素。

压缩列表节点结构

• prevlen：记录前一个节点的长度，用于从后往前的节点遍历
• encoding：记录当前节点数据的类型和长度，类型分为 字符串 和 整数
• data：记录当前节点的数据，类型和长度由encoding决定

当往压缩列表插入数据，压缩列表会自动判断数据类型是字符串还是整数，并且使用对应的prevlen和encoding来封装数据，这样作更能节省内存。

prevlen

• 如果前一个节点的长度小于254字节，就只用1字节空间来保存这个值
• 如果前一个节点的长度大于等于254字节，就要用5字节空间来保存这个值

encoding

• 如果节点数据是整数，那么encoding字段长度为1字节。而不同的encoding编码也确认了数据的不同类型和长度。
• 如果节点数据是字符串，那么encoding字段长度是1/2/5节点，不同的encoding编码也确认了数据的不同长度。

连锁更新

当压缩列表新增或修改一个元素时，如果原有空间不够，该压缩列表节点的内存就要重新分配。而如果此时其他后续的节点的长度都在250-253字节范围内，当一个节点的prevlen字段长度增加，整个节点的长度也超出了254节点，那么它又会导致下一个节点的prevlen字段长度增加，由此形成连续多个节点内存的连锁更新。反过来prevlen字段长度减小也会。

哈希表

定义：保存键值对的数据结构。key是唯一的，value不唯一。

好处：

• 快速查询数据——通过对key进行哈希计算，计算出在哈希数组里的索引值

缺点：

• 数据过多时哈希冲突概率会变大
  解决方法：使用拉链法来解决哈希冲突。

结构设计

typedef struct dictht {
    //哈希表数组
    dictEntry **table;
    //哈希表大小
    unsigned long size;  
    //哈希表大小掩码，用于计算索引值
    unsigned long sizemask;
    //该哈希表已有的节点数量
    unsigned long used;
} dictht;

可以看到，哈希表里定义了一个指向数组指针的指针，也就是哈希数组。而哈希数组里的每一个指针都指向一个哈希表节点。

哈希表节点

typedef struct dictEntry {
    //键值对中的键
    void *key;
  
    //键值对中的值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    //指向下一个哈希表节点，形成链表
    struct dictEntry *next;
} dictEntry;

哈希表节点不仅包含了指向键和值的指针，还包含了指向下一个哈希表节点的指针。这就是拉链法的实现原理。

值： 哈希表节点里定义的值是一个联合体，它可以是一个void指针，也可以是无符号或有符号的64位整数，也可以是double类的值，这样如果是整数或者浮点数时，就可以直接把值嵌入数据结构里，而不是单独再去开辟一块内存。

哈希冲突

一个键值对的键经过hash函数计算后得到的哈希值，并对其进行%哈希数组大小，得到的结果就是对应的哈希数组的下标。当两个不同的key经过运算后得到了相同的下标，就是哈希冲突。

链式哈希（拉链法）

哈希表节点上有一个next指针，用于指向下一个哈希表节点，被分配在同一个哈希数组的节点之间就可以通过这种方法连接起来，解决哈希冲突。

坏处：如果链表长度过长，查询时间会变为O（n）

解决这个问题，需要rehash对哈希表进行扩容。

rehash

在实际使用哈希表时，redis定义了一个结构体，结构体里定义了两个哈希表。

typedef struct dict {
    …
    //两个Hash表，交替使用，用于rehash操作
    dictht ht[2]; 
    …
} dict;

其中第二个哈希表就是用来rehash扩容的。

正常情况，插入的数据只会写入哈希表1，而哈希表2没有被分配空间。当数据慢慢增多到负载因子超出阈值，会进行三步操作

1. 给哈希表2分配空间，空间为第一个大于等于哈希表1已有节点数量+1的2的幂（收缩时是第一个大于等于哈希表1已有节点数量的2的幂）
2. 把哈希表1已有的数据迁移到哈希表2
3. 释放原哈希表1的空间，把哈希表2设为哈希表1，然后再在把哈希表2设为空的哈希表，用于下一次的rehash

如果哈希表1数据非常大，在迁移时会拷贝大量数据，可能会造成redis的阻塞。所以redis采用了渐进式rehash扩容

渐进式rehash

在数据迁移时不再是一次性迁移完，而是在每次对哈希表进行crud的同时，顺便做一次数据迁移。（dict有一个rehashidx字段，可以维护每次迁移原哈希数组的下标）。当然，如果长期不操作哈希表，redis也会通过后台定期进行rehash操作。

在此期间，对key的新增操作是直接写入哈希表2的，而查询、修改和删除操作都是从哈希表1到哈希表2依次查找。这样可以保证哈希表1的数据只减不增。

rehash触发条件

和负载因子有关

• 当负载因子大于等于 1 ，并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令，也就是没有执行 RDB 快照或没有进行 AOF 重写的时候，就会进行 rehash 操作。
• 当负载因子大于等于 5 时，此时说明哈希冲突非常严重了，不管有没有有在执行 RDB 快照或 AOF 重写，都会强制进行 rehash 操作
• 收缩时，负载因子要小于0.1

整数集合

定义：只存储整数的集合。当Set对象内只包含整数，并且数量不多时，使用该数据结构作为底层实现

结构设计

typedef struct intset {
    //编码方式
    uint32_t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8_t contents[];
} intset;

保存元素的容器是一个数组，所以说它占用的是一段连续内存空间。虽然它的数据类型被声明为int8_t,但它其实是一个柔性数组（c语言的一种特性），它在实际使用时，真正的数据类型取决于encoding属性。

• 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
• 如果 encoding 属性值为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
• 如果 encoding 属性值为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

柔性数组在分配内存空间时，按encoding对应的实际数据类型进行分配；在插入数据时，也是通过指针强转，以实际数据类型插入数据；在读取时，也是依靠指针强转成实际数据类型的指针来读取。

升级操作

当新元素加入到集合里时，新元素的数据类型比原有元素的数据类型要更大时，整数集合会先升级，按新元素的数据类型进行扩容，然后把旧元素的数据类型改为新元素的数据类型，并保持有序性地添加回去，最后添加新元素。

整数集合升级不会重新分配一个新数组，而是在原有的数组上进行扩展空间。

整数集合不支持降级操作，也就是一旦对数组升级就不会再降级。

好处：可以节约内存资源——一开始不用设置为大数据类型，而是在需要时再扩容。

跳表

定义：多层的有序链表。当数据量很大时，它能够解决链表的查询效率低问题，从O（n）变为O（logn）

结构设计

跳表结构

typedef struct zskiplist {
    struct zskiplistNode *header, *tail;
    unsigned long length;
    int level;
} zskiplist;

• 跳表的头尾节点，可以O（1）获得
• 跳表的长度，可以O（1）获得
• 跳表的最大层级，可以O（1）获得

跳表节点结构

typedef struct zskiplistNode {
    //Zset 对象的元素值
    sds ele;
    //元素权重值
    double score;
    //后向指针
    struct zskiplistNode *backward;
  
    //节点的level数组，保存每层上的前向指针和跨度
    struct zskiplistLevel {
        struct zskiplistNode *forward;
        unsigned long span;
    } level[];
} zskiplistNode;

Zset对象要同时保存元素和元素权重，就是靠sds类型的ele属性和double类的score。每个跳表节点还有一个向后指针用来从后往前遍历节点。

跳表是带有层级关系的链表。跳表节点中的level数组，每一个元素就代表一层，结构体中包含下一个跳表节点的指针和跨度（用来记录两节点之间的距离）

跨度不是用来遍历操作的，遍历只需要向前指针就行了。跨区是用来计算节点在跳表中的排位的，如图中的跳表节点序号，该节点前的某层路径上的跨度累加起来就是该节点的排位。

头节点也是跳表节点，只是没有向后指针，权重和元素值。

跳表节点查询过程

查询一个跳表节点，会先从跳表头结点的最高层开始找，一层一层地遍历，通过元素权重和sds类元素来进行大小判断。

• 如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
• 如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。

如果上面两条件都不满足，或者下一个节点为null，就会在当前节点的level数组里找下一层的指针继续查找，如此循环。

举个例子，下图有个 3 层级的跳表。

如果要查找「元素：abcd，权重：4」的节点，查找的过程是这样的：

• 先从头节点的最高层开始，L2 指向了「元素：abc，权重：3」节点，这个节点的权重比要查找节点的小，所以要访问该层上的下一个节点；
• 但是该层的下一个节点是空节点（ leve[2]指向的是空节点），于是就会跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[1];
• 「元素：abc，权重：3」节点的 leve[1] 的下一个指针指向了「元素：abcde，权重：4」的节点，然后将其和要查找的节点比较。虽然「元素：abcde，权重：4」的节点的权重和要查找的权重相同，但是当前节点的 SDS 类型数据「大于」要查找的数据，所以会继续跳到「元素：abc，权重：3」节点的下一层去找，也就是 leve[0]；
• 「元素：abc，权重：3」节点的 leve[0] 的下一个指针指向了「元素：abcd，权重：4」的节点，该节点正是要查找的节点，查询结束。

跳表节点层级设置

跳表的相邻两层的节点数量比例会影响查询性能。

理想的相邻两层跳表节点比例是2:1 ，查询复杂度就是O（logn）

但是redis并没有在新增或删除节点时来调整跳表节点比例，因为这样会需要额外开销。redis选择在创建节点时，生成随机数来确定节点的层数。——随机值在0到1的范围内，如果小于0.25，则层数加一，然后继续生成随机数，直到随机数大于0.25，最后确定了跳表节点的层数。

选择0.25是平衡了时间复杂度和空间复杂度。

跳表的层数最高为64（redis7.0定义为32），并且在创造头结点时，会直接创建64层高的头节点。

为什么Zset用跳表而不是平衡树？（todo）

• 它们不是非常内存密集型的。基本上由你决定。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
• Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。
• 它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。
• 从内存占用上来比较，跳表比平衡树更灵活一些。平衡树每个节点包含 2 个指针（分别指向左右子树），而跳表每个节点包含的指针数目平均为 1/(1-p)，具体取决于参数 p 的大小。如果像 Redis里的实现一样，取 p=1/4，那么平均每个节点包含 1.33 个指针，比平衡树更有优势。
• 在做范围查找的时候，跳表比平衡树操作要简单。在平衡树上，我们找到指定范围的小值之后，还需要以中序遍历的顺序继续寻找其它不超过大值的节点。如果不对平衡树进行一定的改造，这里的中序遍历并不容易实现。而在跳表上进行范围查找就非常简单，只需要在找到小值之后，对第 1 层链表进行若干步的遍历就可以实现。
• 从算法实现难度上来比较，跳表比平衡树要简单得多。平衡树的插入和删除操作可能引发子树的调整，逻辑复杂，而跳表的插入和删除只需要修改相邻节点的指针，操作简单又快速。

QuickList

定义：就是双向链表+压缩列表，因为一个QuickList就是一个双向链表，而链表的每个节点内保存的是压缩列表。

它解决（规避）了压缩列表“连锁更新”的问题——通过控制每个链表节点中压缩列表的大小，如果压缩列表大小大了我就直接再加个节点创一个新的压缩列表，这样保持压缩列表元素不多，可以提供更高效的查询。

使用：List

结构设计

链表结构

typedef struct quicklist {
    //quicklist的链表头
    quicklistNode *head;      //quicklist的链表头
    //quicklist的链表尾
    quicklistNode *tail; 
    //所有压缩列表中的总元素个数
    unsigned long count;
    //quicklistNodes的个数
    unsigned long len;       
    ...
} quicklist;

链表节点结构

quicklistNode

typedef struct quicklistNode {
    //前一个quicklistNode
    struct quicklistNode *prev;     //前一个quicklistNode
    //下一个quicklistNode
    struct quicklistNode *next;     //后一个quicklistNode
    //quicklistNode指向的压缩列表
    unsigned char *zl;              
    //压缩列表的的字节大小
    unsigned int sz;                
    //压缩列表的元素个数
    unsigned int count : 16;        //ziplist中的元素个数 
    ....
} quicklistNode;

里面有前后节点指针，来构成双向链表。链表节点中有一个指向压缩列表的指针。

在添加元素时，会检查插入位置的压缩列表能否容纳该元素，如果能，那就直接插入；如果不能，但是插入位置是列表头或尾，可以看相邻的节点的压缩列表头或尾能否容纳该元素，如果还是不能，那就会涉及到对压缩列表的分裂，以及新链表节点的插入。包括在中间插入等情况。

listpack

定义：redis5.0后，用于代替压缩列表的数据结构。它在节点中不在使用像压缩节点的prevlen字段了，因此也就没有了“连锁更新”的问题。

结构设计

listpack结构

listpack节点结构

• encoding：和压缩列表的encoding一样，定义数据的类型，字符串或整数
• data：存放数据
• len：encoding+data的总长度。

listpack节点没了prevlen也可以实现从后往前遍历：通过lpDecodeBacklen函数，可以从当前的节点的起始位置向左逐字节解析，直到得到上个节点的len值，从而实现向前遍历。

线程模型

redis是单线程吗？

redis的基本操作（接收客户端请求->解析请求->数据读写->发送数据给客户端）是单线程（主线程）的。

但是redis程序并不是单线程的，redis是会启动后台线程（BIO）的：

• 用后台线程处理关闭文件，AOF刷盘
• 通过lazyfree线程异步释放redis内存，所以删除大key的时候别用del，会导致主线程阻塞，而是使用unlink来调用后台线程。

关闭文件、AOF刷盘、释放内存三个任务都有各自的任务队列。

后台线程可以处理耗时任务，可以避免主线程阻塞。

redis单线程模式

redis初始化时：

1. 先创建一个epoll对象和一个服务端socket
2. 然后绑定端口并监听这个socket
3. 然后再把这个监听的socket加入到epoll，并注册连接事件来处理函数

初始化完后，主线程就来到事件循环函数：

1. 先调用处理发送队列函数，寻找发送队列中有无发送任务，有就通过write把客户端发送缓冲区的数据发送，如果这轮数据没发送完，就注册写事件来处理函数，等epoll_wait发现可写后在处理。
2. 调用epoll_wait函数来等待事件

1. 1. 如果是连接事件来了，就调用连接事件处理函数：调用accept获取已连接的socket，再把该socket加入到epoll并注册读事件来处理函数。
   2. 如果是读事件来了，就调用读事件处理函数：调用read接受数据，然后解析并执行命令，再把客户端对象加入写发送队列，最后把执行结果写入发送缓存区来等待发送。
   3. 如果是写事件来了，就调用写事件处理函数：通过write发送客户端发送缓存区的数据，如果这轮数据没发送完，就注册写事件来处理函数，等epoll_wait发现可写后再处理。

Redis 采用单线程为什么还这么快？

单线程的 Redis 吞吐量可以达到 10W每秒

原因：

• 因为redis大部分操作都在内存中完成，并且使用了高效的数据结构。redis的效率瓶颈主要不在cpu，更多是在网络带宽和内存大小，所以单线程一般够用了。
• redis采用单线程模型可以避免多线程之间的竞争所造成的线程切换开销，以及避免死锁等问题。
• redis采用IO多路复用机制来处理客户端的socket请求，使得在单线程的情况下，可以同时监听多个socket，谁就绪了就处理其事件，可以充分利用cpu资源。（因为是单线程，在处理事件的时候，如果有socket就绪，会通过回调函数自动先加入就绪FD的链表（epoll特有），等线程处理完当前事件后，在从链表中继续获取就绪socket）

文件描述符（File Descriptor，简称FD）在Linux中，一切皆文件。Socket也是。

Redis 6.0 之前为什么使用单线程？6.0 之后为什么引入了多线程？

之前是因为cpu并不是redis性能的主要瓶颈。更多受限于内存大小和网络带宽。如果想要利用服务器的多核cpu，就启动多节点或者部署分片集群。而且使用多线程也会增加系统复杂度，带来程序执行顺序，死锁等问题，以及线程切换，加锁解锁等性能损耗。

之后有引入多线程来处理网络请求是因为随着网络硬件的性能提升，性能瓶颈也开始显现在网络IO上。所以为了提高网络IO的并行度，开始使用多线程处理网络IO。（执行命令仍然是使用单线程）

默认情况下，多线程只应用于发送响应数据，而想在处理读请求也使用多线程，需要自己在配置文件中配置。（也能配置多线程的个数）

在redis6.0之后，redis启动时将默认额外创建6个线程（不包括主线程）

• Redis-server ： Redis的主线程，主要负责执行命令；
• bio_close_file、bio_aof_fsync、bio_lazy_free：三个后台线程，分别异步处理关闭文件任务、AOF刷盘任务、释放内存任务；
• io_thd_1、io_thd_2、io_thd_3：三个 I/O 线程，io-threads 默认是 4 ，所以会启动 3（减去主线程）个 I/O 多线程，用来分担 Redis 网络 I/O 的压力。

持久化

写时复制：当父进程或子进程在向共享内存发起写操作时，cpu会因为它违反权限而触发写保护中断，然后操作系统就会在写保护中断函数里对物理内存进行复制，并重新设置内存映射的关系，然后那个进程的内存读写权限就可以改为可读写，就可以对内存进行写操作了。

为什么是写时复制——因为可以防止在fork子进程时，因为物理内存数据复制时间太长导致父进程长时间阻塞

坏处：如果共享内存修改的越多，物理内存复制的也就越多，极端情况下就要完整复制所有共享内存了。

Redis 如何实现数据不丢失？

通过数据持久化到磁盘，使redis能够读取磁盘文件恢复数据。

三种数据持久化的方式：

• AOF日志：每执行一条写操作命令，都会把该命令追加到一个文件里
• RDB快照：将某一刻的内存数据以二进制方式写入磁盘
• 混合持久化：同时使用AOF和RDB

AOF日志

定义：每执行一条写操作命令，都会把该命令追加到一个文件里。（主进程执行）redis重启时，会读取该文件内的命令来恢复数据，确保数据的一致性和完整性。

redis默认关闭AOF。

例子

「*3」表示当前命令有三个部分，每部分都是以「$+数字」开头，后面紧跟着具体的命令、键或值。然后，这里的「数字」表示这部分中的命令、键或值一共有多少字节。例如，「$3 set」表示这部分有 3 个字节，也就是「set」命令这个字符串的长度。

为什么先执行命令，再把数据写入日志呢？

• 避免额外的对语法检查开销
• 不会阻塞当前写的命令

坏处：

• 数据日志丢失
• 阻塞随后的操作

AOF 写回策略

redis写入AOF日志过程：

1. redis执行写操作命令后，命令会追加到server.aof_buf缓冲区
2. 然后通过write系统调用，把缓冲区的数据写入aof，此时数据还没写入硬盘，而是拷贝到了内核缓冲区page cache，等待内核把数据写入磁盘
3. 具体内核缓冲区什么时候写入磁盘由内核决定（写回硬盘策略）

redis有三种写回硬盘策略，在redis.conf配置文件中的appendfsync中填写：（本质就是调整调用fsync函数的时机）

• Always：每次写操作命令执行完，就把aof日志数据写回磁盘
• Everysec：每秒从aof文件的内核缓冲区把内容写回磁盘（异步）
• No：由操作系统来控制什么时候把内核缓冲区的数据写回磁盘

AOF 日志重写

原因：随着写操作越来越多，AOF日志文件就会越来越大。当redis需要通过AOF日志恢复数据时，速度就会变慢，比如redis重启时需要读AOF恢复数据。

定义：AOF日志重写时，会去读取数据库中相应的键值对，把每个键值对用一条命令记录到新的AOF文件。最后用新的AOF日志文件去替换原有的AOF日志文件。（防止AOF重写失败污染原有AOF文件）

触发：

• 手动触发：执行bgrewriteaof命令。
• 自动触发：redis配置中有 当前AOF日志和上次重写后AOF日志的文件大小比值 和 触发重写最小文件大小 这两配置项。

举例：多条命令对一个key的value进行修改，但通过重写后，就只会读取key-value的最新值，来生成命令并记录到AOF日志。

重写过程

重写AOF是由后台子进程bgrewriteaof来完成的，这么做有两个好处：

• 可以避免阻塞主进程，让它继续执行redis命令。
• 子进程是使用的主进程的数据副本，而如果是用子线程的话，多线程之间是共享内存，在多线程都要修改共享内存时，需要加锁保证数据一致，这样就会降低性能；而用父子进程它们在共享内存数据时，是以只读的形式，修改内存时，会发生写时复制，就不需要加锁来保证数据一致。

重写AOF时，主进程会创建重写aof的子进程，子进程会去读取数据库里相应的数据，并把键值对都转换为一条命令，然后写入一个新的AOF文件。

重写过程中，主进程仍可以处理命令。在修改到已经存在的key-value时，会发生写时复制。此时这个key-value的数据在父子进程不一致了。

为了解决该问题，redis设置了一个AOF重写缓冲区，在创建后台重写子进程时会使用。

在AOF重写期间，redis在执行完写命令后，会同时把该命令写入AOF缓冲区和AOF重写缓冲区

当子进程完成AOF重写后，会异步地向主进程发送信号，主进程接受到后，会调用信号处理函数，做以下工作：

1. 把AOF重写缓冲区的内容追加到新的AOF文件里
2. 新的AOF文件会覆盖现有的AOF文件

信号处理函数执行完，主进程就恢复往常来处理命令了。

RDB快照

定义：记录某一瞬间的内存数据。

相比AOF日志：因为AOF日志记录的是命令，所以占用内存更大，而且命令过多，里面有很多无效的命令，并且执行命令本身也需要时间，会导致redis数据恢复时速度很慢。

生成RDB快照

redis提供两个命令来生成RDB文件，它们区别在于是否在主线程执行。

• save：主线程上生成RDB文件，会阻塞主线程执行命令
• bgsave：在子进程中生成RDB文件，可以避免阻塞主线程，还可以通过配置文件来实现定时执行bgsave

redis的快照是全量快照，也就是要把内存中所有数据都记录到磁盘。所以它的效率比较低，频率要合理把控。太高会影响redis性能，太低可能在服务器故障时丢失很多数据。

redis在生成RDB快照时，也可以继续执行命令。原理和AOF重写时能执行命令一样，依靠写时复制技术（Copy on write）

执行bgsave时，会fork一个子进程，子进程会复制父进程的页表，但它们俩的页表（页表项可以标记内存为只读）都指向同一个物理内存。

• 读操作时，主线程和子进程互不影响。
• 主线程执行写操作时，被修改的数据就会复制一份副本，主线程就操作那个副本。因为两者不在指向同一物理内存了，所以子进程不会把该副本数据写入RDB文件，只能等待下次RDB快照生成。因此，主线程在生成RDB快照时，也可以继续执行命令。

混合持久化

• RDB优点是数据恢复快，缺点是快照生成频率不好把握
• AOF优点是丢失数据少，缺点是数据恢复慢（因为redis执行命令是单线程，aof日志恢复是顺序执行每一条命令）。

定义：同时使用RDB和AOF，来集成它们的优点。（redis4.0提出）

开启该功能在redis配置文件中改这个配置项

aof-use-rdb-preamble yes

持久化过程

混合持久化工作在AOF日志重写时，对于AOF日志中原有的数据将从内存中以RDB方式重写入AOF文件，然后在此期间，主线程处理的命令会记录在AOF重写缓冲区里，重写缓冲区里的命令就会以AOF的形式写入AOF文件。写入数据完成后，会通知主进程把新的含有RDB格式和AOF格式的AOF文件替换旧AOF文件。

也就是说如果使用混合持久化，AOF文件长这样：

好处：

• 加载速度更快——因为有RDB格式的数据
• 数据更少丢失——因为有重写AOF期间主线程处理的命令也能加载进AOF文件

坏处：

• 可读性差——有AOF和RDB两种格式内容
• 兼容性差——redis4.0之前版本未引入混合持久化

大Key对持久化的影响

对AOF日志的影响

如果使用的是Always策略来写入AOF日志，那因为写入的是大key，所以主线程在执行fsync()函数同步到磁盘的时候，阻塞时间会比较久。

而Everysec策略是异步执行的，所以不会影响主线程。
No策略不执行fsync函数，而是转移操作权给数据库，所以也不影响主线程。

对AOF日志重写和RDB的影响

在AOF重写和RDB文件生成时，需要fork子进程，如果页表很大，复制过程会很耗时，因为fork是主线程调用的，所以会阻塞主线程。

可以执行 info 命令获取到 latest_fork_usec 指标，表示 Redis 最近一次 fork 操作耗时。

# 最近一次 fork 操作耗时
latest_fork_usec:315

如果fork耗时很长，比如超过1秒，可以作以下优化：

• 把单个实例的内存占用控制在10G以下。
• 如果对redis数据恢复要求不高，可以关闭AOF，减少调用fork函数次数。
• 通过对一些缓冲区的大小修改（如repl-backlog-size，用于主从服务器之间传输数据）来可以减少全量同步，因为全量同步是要创建RDB文件的，也就是调用fork函数。

如果创建完子进程后，父进程对共享内存的大key进行修改，那么就会发送写时复制，把物理内存复制一份，而大key的内存占用是很大的，所以复制物理内存是比较耗时的，这就会导致父进程阻塞。

所以，有两个阶段会阻塞父进程：

• 创建子进程的时候，复制父进程的页表时，页表比较大会阻塞。
• 创建子进程后，如果父进程修改了共享内存触发了写时复制，物理内存比较大就会阻塞。

如果Linux开启了内存大页，也会影响redis性能。

linux支持内存大页机制，它支持2MB大小的内存页分配，而常规内存页分配只有4KB。

如果使用了内存大页，那么即使客户端只修改了4KB以内大小的共享数据，那么发送写时复制时，也要拷贝2MB的内存大页，而常规只需要拷贝4KB。这会拖慢写操作的执行时间。

解决方法：可以关闭linux的内存大页机制（默认是关的）。

echo never >  /sys/kernel/mm/transparent_hugepage/enabled

大key除了影响持久化以外，还影响：

• 客户端阻塞
• 网络阻塞
• 内存分配不均（分片集群下）

Redis集群（高可用篇todo）

Redis 实现服务高可用

主从复制

定义：一台服务器同步数据给其他从服务器，主从服务器之间采用读写分离模式。

主服务器可以进行读写操作，写操作会同步给从服务器；从服务器一般是只读，接收到主服务器同步过来的写操作时，才会执行该写命令。（命令复制是异步的）

主从复制无法保证强一致性，因为主服务器在把写操作同步给从服务器时，不会阻塞等待从服务器执行完命令，而是直接执行完命令后返回结果。如果此时从服务器没执行完命令，此时主从服务器之间的数据就不一致了。

哨兵模式

原因：使用redis主从服务时，redis主从服务器发生故障宕机时，需要手动恢复。

定义：可以监控主从服务器，并提供主从服务器故障转移功能。

切片集群模式

定义：把数据分布到不同的服务器，来提高redis数据的存储能力。

切片集群采用哈希槽（Hash Slot），来处理数据和节点之间的映射。一个切片集群有16384个哈希槽，每个键值对会根据它的key来映射到对应的哈希槽里：

• 根据键值对的 key，按照 CRC16 算法 计算一个 16 bit 的值。
• 再用 16bit 值对 16384 取模，得到 0~16383 范围内的模数，每个模数代表一个相应编号的哈希槽。

哈希槽映射到redis节点：

• 平均分配：创建集群时，redis会把所有哈希槽平均分配到集群的每个节点上。
• 手动分配：可以自己指定每个节点上的哈希槽个数。（必须把所有哈希槽都分配完才能正常工作）

集群脑裂导致数据丢失怎么办？

脑裂：集群中的不同节点因为通信故障等原因，而导致分开形成独立的子集，出现了多个主节点的情况。此时如进行数据操作，就可能导致数据不一致、丢失等情况。

举例：在redis的主从结构中，如果主节点突然出现网络问题，与其他从节点失联了，但它与客户端的通信仍然正常。此时客户端对主节点的写操作有效，但主节点无法把写操作同步给其他从节点。其他从节点通过哨兵机制会重新选出一个主节点，此时集群就有了两个主节点了（脑裂）。当失联主节点与其他节点恢复通信时，因为哨兵机制它会降级为从节点，然后清除数据做一次全量同步，因此之前和客户端之间的操作数据都丢失了。

解决方法

当主节点发现从节点下线或者主从复制的时间超时时，禁止主节点写数据，直接给客户端返回错误。

redis配置文件中参数：

• min-slaves-to-write x，主节点必须要有至少 x 个从节点连接，如果小于这个数，主节点会禁止写数据。
• min-slaves-max-lag x，主从数据复制和同步的延迟不能超过 x 秒，如果超过，主节点会禁止写数据。

两个参数可以搭配使用。这样如果原主库假故障，就会因为没有从节点连接，以及主从复制超时而被禁止写数据，等到新主节点上线，就可以接管它来处理客户端请求，而当它恢复通信时，因为没有新数据产生所以可以正常同步。

Redis 过期删除与内存淘汰

过期删除策略

redis对于设置了过期时间的key会把它存储到一个过期字典里，value就是过期时间。

当查询一个key时，会先去检查key在过期字典里是否存在：

• 如果不在，就正常去读取键值。
• 如果存在，就获得它的过期时间，并与系统时间进行对比，如果比系统时间大，就没有过期，否则就是过期。

redis使用的过期策略是 惰性删除+定期删除 。

惰性删除

定义：不主动删除过期的键值对，而是当访问到键值对，去判断它是否过期时，如果过期了再删除。

好处：

• 占用很少的系统资源

坏处：

• 如果过期的key长时间不被访问，会一直占用内存空间不被删除。

定期删除

定义：每隔一段时间去过期字典取出一些key来进行检查是否过期。（主线程执行）

流程：

1. 从过期字典中随机取出20个key
2. 检查是否过期，如果过期就删除
3. 最后去看本轮的过期key：所有检查的key，如果大于25%，就重复这个流程，直到小于为止。

当然定期删除如果遇到一坨过期的key可能会循环很久，为了防止主线程长期阻塞，设置了循环的时间上限，默认是25ms。

好处：

• 可以删除过期的但访问频率低的key

坏处：

• 难以确定定期删除策略的频率，太频繁占用cpu，频率太低又不能及时释放过期key占用的空间。

Redis 持久化时，对过期键会如何处理的？

• RDB文件生成阶段：会对key进行过期检查，过期的key不会被保存到RDB文件中。
• RDB文件加载阶段：

• • 如果是主服务器加载的话，会对保存的key进行过期检查，过期的键值不会保存到数据库。
  • 如果是从服务器加载的话，无论有没有过期都会保存到数据库。但因为主从服务器会进行全量同步，所以对从服务器数据没有影响。

• AOF文件写入阶段：正常添加过期键，当过期删除了就向AOF文件追加一条del命令
• AOF重写阶段：会对redis中的键值对检查，过期的key不会保存到重写后的AOF文件。

Redis 主从模式中，对过期键会如何处理？

redis 3.2版本之前，从库的数据过期处理是完全依赖主库的，所以如果如果直接访问从库的过期数据，依然是可以得到value的。所以需要主库保证及时处理过期键值对并同步删除命令给从库。

redis 3.2版本之后，从库能在读操作时判断数据是否过期了。当然不同服务器的时钟不一致，主库和从库的对于过期判断肯定也会有那么点偏差，但这是微乎其微的。（不能容忍还搞什么主从同步，读写分离）

内存淘汰策略

redis内存满了，会触发内存淘汰机制。阈值是我们设置的最大运行内存，在redis配置文件中。

内存淘汰策略有八种，大致分为 不进行数据淘汰 和 进行数据淘汰 两种。

• 不进行数据淘汰的策略

• • noeviction（默认）：当运行内存超过阈值，不淘汰任何数据，而是给客户端返回错误。

• 进行数据淘汰的策略

• • 对设置了过期时间的数据进行淘汰

• • • volatile-random：随机淘汰设置了过期时间的键值。
    • volatile-ttl：优先淘汰过期时间早的键值
    • volatile-lru：淘汰设置了过期时间的键值中，最长时间未使用的键值
    • volatile-lfu：淘汰设置了过期时间的键值中，最少使用的键值

• • 对所有数据进行淘汰

• • • allkeys-random：随机淘汰任意键值
    • allkeys-lru：淘汰所有键值中，最长时间未使用的键值
    • allkeys-lfu：淘汰所有键值中，最少使用的键值

LRU

定义：全称是Least Recently Used，会淘汰最长时间未使用的数据。

传统的LRU算法是由链表实现的，链表里的元素按元素操作时间顺序来排序，链表尾是最长时间未操作的元素，最新操作的元素会被移到表头，所以淘汰时直接直接删除链表尾部元素就行。

缺点：会造成缓存污染。——数据是根据时间来淘汰的，如果一次性访问大量缓存，然后这些缓存一直不再被使用，但它们却要很长时间后才能被清理，会占用空间。

redis并没有使用传统方法来实现LRU算法，因为它有两个缺点：

• 链表会产生空间开销
• 数据访问太多链表移动操作也会有很多，会降低redis性能

Redis的LRU算法实现

一种近似LRU算法，是在redis的对象结构中添加一个额外字段，来记录数据的最后一次访问时间。当redis要进行内存淘汰时，会随机取5个值根据它们的字段来淘汰数据。

好处：

• 不用为所有数据库数据维护链表，节省空间占用

LFU

定义：全称是 Least Frequently Used，会淘汰最少使用的数据。

LFU算法会记录每个数据的访问次数，当数据被访问一次，就会增加它的访问次数。这就解决了LRU中的缓存偶尔被访问一次，但却会被留存很长一段时间。

Redis的LFU算法实现

LFU 算法相比于 LRU 算法的实现，多记录了「数据的访问频次」的信息

typedef struct redisObject {
    ...
      
    // 24 bits，用于记录对象的访问信息
    unsigned lru:24;  
    ...
} robj;

redis对象头中的lru字段，在LRU算法和LFU算法下的使用方法不同。

• LRU：24bit都用来记录key的访问时间戳。
• LFU：lru字段分为两段，高16bit存储key的访问时间戳，低8bit存储key的访问频次。

Redis缓存设计

缓存雪崩

定义：大量缓存数据同时失效或者redis突然宕机，大量用户请求就不能在redis中处理，就全都去访问数据库。数据库可能会因为压力过大直接宕机。

可以看到，引起缓存雪崩的原因有两个：

• 大量缓存数据过期
• redis故障宕机

不同原因，应对策略也不同。

大量缓存同时过期

应对方法有：

均匀设置过期时间

给数据的过期时间加随机数，让缓存不在同一时间过期。

互斥锁

访问数据时，如果发现redis里不存在，就加上互斥锁，保证同一时间内只有一个请求来构建缓存（从数据库读数据，然后写回redis）。缓存构建完后，再释放锁。没能获取互斥锁的请求，要么等锁释放后去读缓存，要么就返回空值或默认值。

获取互斥锁时最好加上超时时间，防止请求出现意外一直不释放锁。

后台更新缓存

直接让缓存永久有效，并把缓存更新操作交给后台线程定时更新。但当redis内存紧张时，因为内存淘汰策略，一样有可能清理缓存。此时就可能导致业务线程读不到缓存。

解决方法：

• 让后台线程也同时负责检查缓存是否有效。如果失效了就去从数据库读取并缓存。（但需要比较频繁地检查）
• 在业务线程发现缓存失效后，通过消息队列发送消息让后台线程去更新缓存，后台线程收到后发现缓存确实没有就更新，有就不更新了。

在业务刚上线时，不要等待用户访问来触发缓存的构建，而是提前缓存。——缓存预热

Redis故障宕机

应对方法有：

服务熔断或请求限流机制

服务熔断机制来暂停业务对数据库的访问，直接返回错误。等redis恢复再允许业务访问。但这会使所有业务都无法工作。为了减少对业务的影响，可以启用请求限流机制，只让少部分请求发送到数据库处理，其他请求就拒绝，等redis恢复再解除请求限流。

构建Redis缓存高可靠集群

这是预防的手段。如果主节点故障宕机，从节点可以变为主节点继续提供服务。

缓存击穿

定义：某个热点数据过期了，大量请求同时访问该数据，读不到缓存就都去读数据库，导致数据库压力山大，可能会被冲垮。缓存击穿和缓存雪崩类似，可以说是它的一个子集（一个是侧重某个，一个侧重一群）

应对方法：

互斥锁（同缓存雪崩方案）。

后台更新缓存（同缓存雪崩方案）

缓存穿透

定义：访问的数据既不在缓存中，也不在数据库中。如果有大量请求访问，数据库压力就很大。

应对方法：

非法请求的限制

如果有大量恶意请求来访问不存在的数据时，就会发送缓存穿透。所以要我们在API入口处作判断，它的请求的数据是否合理，不合理就直接返回错误。

缓存空值或默认值

如果已经发生了一次缓存穿透，我们可以对查询的数据做个一个空值或默认值的缓存，这样以后相同的请求就可以直接通过查询缓存得到结果，而不用查询数据库。

布隆过滤器判断数据是否存在

在往数据库写入数据的时候，使用布隆过滤器做个标记，用户请求过来时发现缓存失效后，可以通过布隆过滤器来判断数据库里数据是否存在，存在再去获取，不存在就不去查询数据库。

Redis可以实现布隆过滤器（通过redis扩展模块）。

布隆过滤器

定义：由 初始值全为0的位图数组 和 多个哈希函数（具体个数原理todo） 组成。当我们往数据库写入数据时，就可以在布隆过滤器里做标记，下次访问数据库前，就可以通过布隆过滤器来判断数据是否存在，如果数据没被标记，说明就不存在；有标记则表示存在，可以借此来决定是否访问数据库，可以减轻数据库压力。

原理：

• 使用多个哈希函数对数据进行哈希运算，然后得到多个哈希值
• 让这些哈希值对位图数据长度进行取模，得到那些哈希值在位图数组里对应的下标。
• 把对应位置的位图数组里的数据设为1

当我们要查某个数据是否在数据库存在时，就可以通过该方法，获取该数据对应位图数组的各个元素，如果都为1，表示存在；否则表示不存在。

布隆过滤器是基于哈希函数实现的，所以也会存在哈希冲突的可能，就会导致误判。但如果布隆过滤器计算得出数据存在，它不一定真的存在；但如果计算得出不存在，它就一定不存在。

动态缓存热点数据策略

因为数据存储受限，不是所有数据都能放在缓存中的，所以我们只缓存热点数据。

设计思路：通过数据访问时间来做排名，过滤掉不常访问的，留下访问频率高的。可以使用Redis数据类型里的Zset，score作为访问频率来排名，value就是在另一个缓存数据结构中的id（通过该id再去读取那个缓存中存储的数据信息）。

举例：比如只要缓存访问量top1000的商品。

1. 用zset先做个排序队列来存放这些商品id，score作为商品的访问时间，越新排名越靠前。
2. 编写定时任务会定时清理掉队列最后的200个商品，然后再从数据库中随机获取200个商品加入队列（也要同时对商品信息缓存操作，保持数据一致）
3. 这样请求到达后，会先获取商品id，然后再去另一个缓存数据结构中读取实际商品信息并返回。

为什么不把访问时间排序队列和实际数据缓存整合在一起

• 有利于使用更好的数据结构存储实际数据
• 可以避免大key的出现

常见的缓存更新策略todo

实际开发中，mysql和redis使用的是Cache Aside，其他两种策略用不了。

Cache Aside 旁路缓存策略

数据库与缓存的一致性

更新数据库与缓存

该方法适合业务对缓存命中有高要求的，但该方法存在并发问题可能会导致数据不一致，所以需要方法解决：

• 使用分布式锁——保证同时只有一个请求来更新数据库和缓存，就不会产生并发问题了，但对性能有影响。
• 给缓存加过期时间——业务需要能允许短暂的数据不一致。

先更新数据库，再更新缓存

最后数据库的值为2，而缓存的值为1，两者数据不一致。

先更新缓存，再更新数据库

最后数据库的值为1，而缓存的值为2，两者数据还是不一致。

所以这两种方案都会存在并发问题。

所以我们不再同时更新数据和缓存。而是更新数据库的时候，把缓存删除。等数据被读取时，再从数据库读取数据写入缓存。——Cache Aside 策略（旁路缓存策略）

Cache Aside策略又可分为读策略和写策略

写策略：

1. 更新数据库
2. 删除缓存

读策略：

• 读到缓存就直接返回
• 没读到缓存就去读数据库，然后再把数据写入缓存

写策略中，两者的顺序该如何分配呢？

更新数据库并删除缓存

先删除缓存，再更新数据库

请求A删掉缓存后，请求B去访问数据库，就会把数据库的旧数据写回缓存，然后请求A再更新数据库为新值，此时缓存的旧值就会让数据不一致。所以读写并发时，还是会出现数据不一致。

解决方法：可以使用延迟双删。

#删除缓存
redis.delKey(X)
#更新数据库
db.update(X)
#睡眠，确保这段时间其他请求能完成数据库的读取和缓存的更新操作
Thread.sleep(N)
#再删除缓存
redis.delKey(X)

但这个方法有个问题，就是必须要求睡眠的时间里，其他请求一定要完成“数据库的读取和缓存的更新”操作，这对睡眠时间的设置有很严格的要求，所以该方法普遍也无法完全保证数据一致性。所以还是推荐使用“先更新数据库，再删除缓存”方案。

先更新数据库，再删除缓存

假设某数据在缓存中还不存在，请求B在读到数据库的旧值后，请求A会去更新数据库为新值，然后再删除缓存，然后请求B又去把旧值写入缓存。不过这种可能性在实际中不高，因为缓存的写入速度要远快于数据库的写入。很难出现先等数据库更新完，缓存才被写入。

所以该方法是相对能保证数据的一致性的。

而且，还可以给缓存加上过期时间，如果缓存数据不一致了，那也只会是一段时间的数据不一致。

但是，如果该方法的“删除缓存”操作失败了，还是会导致缓存是旧值。（不过倒是有过期时间作保底）

如何保证两个操作都能执行成功？

这个问题无论是更新数据库和删除缓存谁先谁后都会有。

解决方法：

重试机制

使用消息队列，把要删除的缓存这个数据加入消息队列，让消费者去处理。

• 如果缓存删除失败，就在消息队列中重新读取消息，然后再尝试删除缓存。这就是重试机制。 但如果重试次数过多，就需要向业务层发送报错信息。
• 如果缓存删除成功，就把缓存数据从消息队列中移除。

订阅MySQL的binlog，再操作缓存 （不过这跟能保证两个操作执行成功有什么关系）

只适用于”先更新数据库，再删除缓存“。

更新数据库成功后，会在binlog文件生成一条日志，然后我们可以去订阅binlog日志，拿到要操作的数据，再去执行缓存删除。

Canal中间件就是这样实现的。Canal伪装成一个MySQL的从节点，向主节点去发送dump请求，MySQL收到后就会推送binlog给Canal，然后Canal解析binlog字节流，转换为结构化数据，共下游程序订阅使用。

这两种方法有一个共同点，就是都是使用异步操作