Redis数据类型和数据结构

数据类型

常见的有五种：String（字符串），Hash（哈希），List（列表），Set（集合）、Zset（有序集合）。
随着 Redis 版本的更新，后面又支持了四种数据类型： BitMap（2.2 版新增）、HyperLogLog（2.8 版新增）、GEO（3.2 版新增）、Stream（5.0 版新增）。

String类型

是redis中最基本的数据类型，一个key对应一个value。内部由SDS数据结构实现

如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成 long），并将字符串对象的编码设置为int
如果字符串对象保存的是一个字符串，并且这个字符申的长度小于等于 32 字节（redis 2.+版本），那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，并将对象的编码设置为embstr， embstr编码是专门用于保存短字符串的一种优化编码方式
如果字符串对象保存的是一个字符串，并且这个字符串的长度大于 32 字节（redis 2.+版本），那么字符串对象将使用一个简单动态字符串（SDS）来保存这个字符串，并将对象的编码设置为raw

embstr优点：
embstr会通过一次内存分配函数来分配一块连续的内存空间来保存redisObject和SDS，raw编码会通过调用两次内存分配函数来分别分配两块空间来保存redisObject和SDS
因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面可以更好的利用 CPU 缓存提升性能。

embstr缺点：
embstr编码的字符串对象实际上是只读的，redis没有为embstr编码的字符串对象编写任何相应的修改程序。当我们对embstr编码的字符串对象执行任何修改命令（例如append）时，程序会先将对象的编码从embstr转换成raw，然后再执行修改命令。
如果字符串的长度增加需要重新分配内存时，整个redisObject和sds都需要重新分配空间，

127.0.0.1:6379> set hello world
OK
127.0.0.1:6379> get hello
"world"

使用场景：

缓存对象
常规计数
分布式锁

List类型

List 类型的底层数据结构是由双向链表或压缩列表实现的

如果列表的元素个数小于 512 个（默认值，可由 list-max-ziplist-entries 配置），列表每个元素的值都小于 64 字节（默认值，可由 list-max-ziplist-value 配置），Redis 会使用压缩列表作为 List 类型的底层数据结构；
如果列表的元素不满足上面的条件，Redis 会使用双向链表作为 List 类型的底层数据结构；
在 Redis 3.2 版本之后，List 数据类型底层数据结构就只由 quicklist 实现了，替代了双向链表和压缩列表。

使用列表的技巧:

lpush+lpop=Stack(栈)
lpush+rpop=Queue（队列）
lpush+ltrim=Capped Collection（有限集合）

lpush+brpop=Message Queue（消息队列）

127.0.0.1:6379> lpush mylist 1 2 ll ls mem
(integer) 5
127.0.0.1:6379> lrange mylist 0 -1
1) "mem"
2) "ls"
3) "ll"
4) "2"
5) "1"
127.0.0.1:6379>

应用场景：
消息队列

消息保序：使用 LPUSH + RPOP；
阻塞读取：使用 BRPOP；
重复消息处理：生产者自行实现全局唯一 ID；
消息的可靠性：使用 BRPOPLPUSH

Hash类型

是一个Mapmap，指值本身又是一种键值对结构，Hash 类型的底层数据结构是由压缩列表或哈希表实现的：

如果哈希类型元素个数小于 512 个（默认值，可由 hash-max-ziplist-entries 配置），所有值小于 64 字节（默认值，可由 hash-max-ziplist-value 配置）的话，Redis 会使用压缩列表作为 Hash 类型的底层数据结构；
如果哈希类型元素不满足上面条件，Redis 会使用哈希表作为 Hash 类型的底层数据结构。
在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

使用：所有hash的命令都是 h 开头的 hget 、hset 、 hdel 等

127.0.0.1:6379> hset user name1 hao
(integer) 1
127.0.0.1:6379> hset user email1 hao@163.com
(integer) 1
127.0.0.1:6379> hgetall user
1) "name1"
2) "hao"
3) "email1"
4) "hao@163.com"

应用场景

缓存对象
购物车

Set类型

Set 类型的底层数据结构是由哈希表或整数集合实现的：

如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

使用：命令都是以s开头的 sset 、srem、scard、smembers、sismember

127.0.0.1:6379> sadd myset hao hao1 xiaohao hao
(integer) 3
127.0.0.1:6379> SMEMBERS myset
1) "xiaohao"
2) "hao1"
3) "hao"
127.0.0.1:6379> SISMEMBER myset hao
(integer) 1

Set 类型和 List 类型的区别如下：

List 可以存储重复元素，Set 只能存储非重复元素；
List 是按照元素的先后顺序存储元素的，而 Set 则是无序方式存储元素的。
集合中的元素是无序的，不能通过索引下标获取元素

Set 的差集、并集和交集的计算复杂度较高，在数据量较大的情况下，如果直接执行这些计算，会导致 Redis 实例阻塞

应用场景：
点赞
共同关注
抽奖活动

ZSet类型

Zset 类型的底层数据结构是由压缩列表或跳表实现的：

如果有序集合的元素个数小于 128 个，并且每个元素的值小于 64 字节时，Redis 会使用压缩列表作为 Zset 类型的底层数据结构；
如果有序集合的元素不满足上面的条件，Redis 会使用跳表作为 Zset 类型的底层数据结构；
在 Redis 7.0 中，压缩列表数据结构已经废弃了，交由 listpack 数据结构来实现了。

对于有序集合 ZSet 来说，每个存储元素相当于有两个值组成的，一个是有序集合的元素值，一个是排序值。
有序集合和集合有着必然的联系，保留了集合不能有重复成员的特性，区别是，有序集合中的元素是可以排序的，它给每个元素设置一个分数，作为排序的依据。

使用：有序集合的命令都是以 z 开头 zadd 、 zrange、 zscore

127.0.0.1:6379> zadd myscoreset 100 hao 90 xiaohao
(integer) 2
127.0.0.1:6379> ZRANGE myscoreset 0 -1
1) "xiaohao"
2) "hao"
127.0.0.1:6379> ZSCORE myscoreset hao
"100"

BitMap类型

Bitmap，即位图，是一串连续的二进制数组（0和1），可以通过偏移量（offset）定位元素。BitMap通过最小的单位bit来进行0|1的设置，表示某个元素的值或者状态，时间复杂度为O(1)。

由于 bit 是计算机中最小的单位，使用它进行储存将非常节省空间，特别适合一些数据量大且使用二值统计的场景。

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

# 获取值
GETBIT key offset

内部实现:
Bitmap 本身是用 String 类型作为底层数据结构实现的一种统计二值状态的数据类型。
String 类型是会保存为二进制的字节数组，所以，Redis 就把字节数组的每个 bit 位利用起来，用来表示一个元素的二值状态，你可以把 Bitmap 看作是一个 bit 数组

应用场景
签到统计
判断用户登陆态
连续签到用户总数

HyperLogLog类型

HyperLogLog 提供不精确的去重计数, 是统计规则是基于概率完成的，不是非常准确，标准误算率是 0.81%。
HyperLogLog 的优点是，在输入元素的数量或者体积非常非常大时，计算基数所需的内存空间总是固定的、并且是很小的。
每个 HyperLogLog 键只需要花费 12 KB 内存，就可以计算接近 2^64 个不同元素的基数，和元素越多就越耗费内存的 Set 和 Hash 类型相比，HyperLogLog 就非常节省空间:
HyperLogLog数学原理

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

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

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

应用场景
百万级网页 UV 计数

GEO类型

内部实现
GEO 本身并没有设计新的底层数据结构，而是直接使用了 Sorted Set 集合类型。

GEO 类型使用 GeoHash 编码方法实现了经纬度到 Sorted Set 中元素权重分数的转换，这其中的两个关键机制就是「对二维地图做区间划分」和「对区间进行编码」。一组经纬度落在某个区间后，就用区间的编码值来表示，并把编码值作为 Sorted Set 元素的权重分数。

这样一来，我们就可以把经纬度保存到 Sorted Set 中，利用 Sorted Set 提供的“按权重进行有序范围查找”的特性，实现 LBS 服务中频繁使用的“搜索附近”的需求。

# 存储指定的地理空间位置，可以将一个或多个经度(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]

应用场景
滴滴叫车
这里以滴滴叫车的场景为例，介绍下具体如何使用 GEO 命令：GEOADD 和 GEORADIUS 这两个命令。

假设车辆 ID 是 33，经纬度位置是（116.034579，39.030452），我们可以用一个 GEO 集合保存所有车辆的经纬度，集合 key 是 cars:locations。

执行下面的这个命令，就可以把 ID 号为 33 的车辆的当前经纬度位置存入 GEO 集合中：

1	GEOADD cars:locations 116.034579 39.030452 33

当用户想要寻找自己附近的网约车时，LBS 应用就可以使用 GEORADIUS 命令。

例如，LBS 应用执行下面的命令时，Redis 会根据输入的用户的经纬度信息（116.054579，39.030452 ），查找以这个经纬度为中心的 5 公里内的车辆信息，并返回给 LBS 应用。

1	RADIUS cars:locations 116.054579 39.030452 5 km ASC COUNT 10

Stream类型

Redis Stream 是 Redis 5.0 版本新增加的数据类型，Redis 专门为消息队列设计的数据类型。它支持消息的持久化、支持自动生成全局唯一 ID、支持 ack 确认消息的模式、支持消费组模式等，让消息队列更加的稳定和可靠。

在 Redis 5.0 Stream 没出来之前，消息队列的实现方式都有着各自的缺陷，例如：

发布订阅模式，不能持久化也就无法可靠的保存消息，并且对于离线重连的客户端不能读取历史消息的缺陷；
List 实现消息队列的方式不能重复消费，一个消息消费完就会被删除，而且生产者需要自行实现全局唯一 ID。

常见命令
Stream 消息队列操作命令：

XADD：插入消息，保证有序，可以自动生成全局唯一 ID；
XLEN ：查询消息长度；
XREAD：用于读取消息，可以按 ID 读取数据；
XDEL ：根据消息 ID 删除消息；
DEL ：删除整个 Stream；
XRANGE ：读取区间消息
XREADGROUP：按消费组形式读取消息；
XPENDING 和 XACK：
XPENDING 命令可以用来查询每个消费组内所有消费者「已读取、但尚未确认」的消息；
XACK 命令用于向消息队列确认消息处理已完成；

应用场景

消息队列

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

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

如果想要实现阻塞读（当没有数据时，阻塞住），可以调用 XRAED 时设定 BLOCK 配置项，实现类似于 BRPOP 的阻塞读取操作。

Stream 可以以使用 XGROUP 创建消费组，创建消费组之后，Stream 可以使用 XREADGROUP 命令让消费组内的消费者读取消息。

创建两个消费组，这两个消费组消费的消息队列是 mymq，都指定从第一条消息开始读取：

# 创建一个名为 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"

消息队列中的消息一旦被消费组里的一个消费者读取了，就不能再被该消费组内的其他消费者读取了，即同一个消费组里的消费者不能消费同一条消息。

比如说，我们执行完刚才的 XREADGROUP 命令后，再执行一次同样的命令，此时读到的就是空值了：

1 2	> XREADGROUP GROUP group1 consumer1 STREAMS mymq > (nil)

但是，不同消费组的消费者可以消费同一条消息（但是有前提条件，创建消息组的时候，不同消费组指定了相同位置开始读取消息）。
比如说，刚才 group1 消费组里的 consumer1 消费者消费了一条 id 为 1654254953808-0 的消息，现在用 group2 消费组里的 consumer1 消费者消费消息：

> XREADGROUP GROUP group2 consumer1 STREAMS mymq >
1) 1) "mymq"
   2) 1) 1) "1654254953808-0"
         2) 1) "name"
            2) "xiaolin"

因为我创建两组的消费组都是从第一条消息开始读取，所以可以看到第二组的消费者依然可以消费 id 为 1654254953808-0 的这一条消息。因此，不同的消费组的消费者可以消费同一条消息。

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

Streams 会自动使用内部队列（也称为 PENDING List）留存消费组里每个消费者读取的消息，直到消费者使用 XACK 命令通知 Streams“消息已经处理完成”。

消费确认增加了消息的可靠性，一般在业务处理完成之后，需要执行 XACK 命令确认消息已经被消费完成，整个流程的执行如下图所示：

如果消费者没有成功处理消息，它就不会给 Streams 发送 XACK 命令，消息仍然会留存。此时，消费者可以在重启后，用 XPENDING 命令查看已读取、但尚未确认处理完成的消息。

一旦消息 1654256265584-0 被 consumer2 处理了，consumer2 就可以使用 XACK 命令通知 Streams，然后这条消息就会被删除。

1 2	> XACK mymq group2 1654256265584-0 (integer) 1

当我们再使用 XPENDING 命令查看时，就可以看到，consumer2 已经没有已读取、但尚未确认处理的消息了。

1
2
3

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

总结：

消息保序：XADD/XREAD
阻塞读取：XREAD block
重复消息处理：Stream 在使用 XADD 命令，会自动生成全局唯一 ID；
消息可靠性：内部使用 PENDING List 自动保存消息，使用 XPENDING 命令查看消费组已经读取但是未被确认的消息，消费者使用 XACK 确认消息；
支持消费组形式消费数据

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

消息不丢?

生产者会不会丢消息，消费者不会丢消息,,Redis 消息中间件会丢消息, Redis 在以下 2 个场景下，都会导致数据丢失：

AOF 持久化配置为每秒写盘，但这个写盘过程是异步的，Redis 宕机时会存在数据丢失的可能
主从复制也是异步的，主从切换时，也存在丢失数据的可能。

消息可堆积?
Redis 的数据都存储在内存中，这就意味着一旦发生消息积压，则会导致 Redis 的内存持续增长，如果超过机器内存上限，就会面临被 OOM 的风险。但 Kafka、RabbitMQ 专业的消息队列它们的数据都是存储在磁盘上

关键看业务场景：
如果你的业务场景足够简单，对于数据丢失不敏感，而且消息积压概率比较小的情况下，把 Redis 当作队列是完全可以的。
如果你的业务有海量消息，消息积压的概率比较大，并且不能接受数据丢失，那么还是用专业的消息队列中间件吧。

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

发布/订阅机制没有基于任何数据类型实现，所以不具备「数据持久化」的能力，也就是发布/订阅机制的相关操作，不会写入到 RDB 和 AOF 中，当 Redis 宕机重启，发布/订阅机制的数据也会全部丢失。
发布订阅模式是“发后既忘”的工作模式，如果有订阅者离线重连之后不能消费之前的历史消息。
当消费端有一定的消息积压时，也就是生产者发送的消息，消费者消费不过来时，如果超过 32M 或者是 60s 内持续保持在 8M 以上，消费端会被强行断开，这个参数是在配置文件中设置的，默认值是client-output-buffer-limit pubsub 32mb 8mb 60

数据结构实现

redisDb 结构，表示 Redis 数据库的结构，结构体里存放了指向了 dict 结构的指针；
dict 结构，结构体里存放了 2 个哈希表，正常情况下都是用「哈希表1」，「哈希表2」只有在 rehash 的时候才用，具体什么是 rehash，我在本文的哈希表数据结构会讲；
ditctht 结构，表示哈希表的结构，结构里存放了哈希表数组，数组中的每个元素都是指向一个哈希表节点结构（dictEntry）的指针；
dictEntry 结构，表示哈希表节点的结构，结构里存放了 *void key 和 void * value 指针， key 指向的是 String 对象，而 value 则可以指向 String 对象，也可以指向集合类型的对象，比如 List 对象、Hash 对象、Set 对象和 Zset 对象。

数据结构

SDS—String类型

点击此处跳转到String类型

C 语言字符串的缺陷

字符数组的结尾位置就用“\0”表示，意思是指字符串的结束。
C 语言获取字符串长度的时间复杂度是 O（N）
不能保存像图片、音频、视频文化这样的二进制数据，有个 “\0” 字符，这时在操作这个字符串时就会提早结束
必须提前分配足够多的内存，可以容纳所有内容，否则就会发生缓冲区溢出将可能会造成程序运行终止。

SDS设计

O（1）复杂度获取字符串长度
二进制安全， SDS 的所有 API 都会以处理二进制的方式处理存放在 buf[] 数组里的数据。所以 SDS 不光能存放文本数据，而且能保存图片、音频、视频、压缩文件这样的二进制数据。

不会发生缓冲区溢出，当判断出缓冲区大小不够用时，Redis 会自动将扩大 SDS 的空间大小，如果所需的 sds 长度小于 1 MB，那么最后的扩容是按照翻倍扩容来执行的，即 2 倍的newlen，如果所需的 sds 长度超过 1 MB，那么最后的扩容长度应该是 newlen + 1MB。

hisds hi_sdsMakeRoomFor(hisds s, size_t addlen)
{
    ... ...
    // s目前的剩余空间已足够，无需扩展，直接返回
    if (avail >= addlen)
        return s;
    //获取目前s的长度
    len = hi_sdslen(s);
    sh = (char *)s - hi_sdsHdrSize(oldtype);
    //扩展之后 s 至少需要的长度
    newlen = (len + addlen);
    //根据新长度，为s分配新空间所需要的大小
    if (newlen < HI_SDS_MAX_PREALLOC)
        //新长度<HI_SDS_MAX_PREALLOC 则分配所需空间*2的空间
        newlen *= 2;
    else
        //否则，分配长度为目前长度+1MB
        newlen += HI_SDS_MAX_PREALLOC;
       ...
}

节省内存空间
flags 成员变量，表示的是 SDS 类型。设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。
比如 sdshdr16 和 sdshdr32 这两个类型，它们的定义分别如下：

//数据结构中的 len 和 alloc 成员变量的数据类型不同。
struct __attribute__ ((__packed__)) sdshdr16 {            //表示字符数组长度和分配空间大小不能超过 2 的 16 次方。
    uint16_t len;                                
    uint16_t alloc; 
    unsigned char flags; 
    char buf[];
};

struct __attribute__ ((__packed__)) sdshdr32 {     //表示表示字符数组长度和分配空间大小不能超过 2 的 32 次方
    uint32_t len;
    uint32_t alloc; 
    unsigned char flags;
    char buf[];
};

Redis在struct 声明了attribute ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行对齐。

Redis的对齐方式：

链表—List类型

点击此处跳转到List类型
C 语言本身没有链表这个数据结构的，所以 Redis 自己设计了一个链表数据结构。

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;

压缩列表—List类型&Hash类型&Zset类型

点击此处跳转到List类型
 点击此处跳转到Hash类型
 点击此处跳转到Zset类型
压缩列表的最大特点，就是它被设计成一种内存紧凑型的数据结构，由连续内存块组成的顺序型数据结构，有点类似于数组。占用一块连续的内存空间，不仅可以利用 CPU 缓存，而且会针对不同长度的数据，进行相应编码，这种方法可以有效地节省内存开销。

zlbytes：记录整个压缩列表占用对内存字节数；
zltail：记录压缩列表「尾部」节点距离起始地址由多少字节，也就是列表尾的偏移量；
zllen：记录压缩列表包含的节点数量；
zlend：标记压缩列表的结束点，固定值 0xFF（十进制255）。
prevlen：记录了「前一个节点」的长度，目的是为了实现从后向前遍历；
如果前一个节点的长度小于 254 字节，那么 prevlen 属性需要用 1 字节的空间来保存这个长度值；
如果前一个节点的长度大于等于 254 字节，那么 prevlen 属性需要用 5 字节的空间来保存这个长度值；
encoding：记录了当前节点实际数据的「类型和长度」，类型主要有两种：字符串和整数。
data：记录了当前节点的实际数据，类型和长度都由 encoding 决定；

缺点：

查找定位第一个元素和最后一个元素较快，其它元素查找复杂度高
连锁更新：造成访问压缩列表性能的下降。

什么是连锁更新？

如果将一个长度大于等于 254 字节的新节点加入到压缩列表的表头节点，即新节点将成为 e1 的前置节点，因为 e1 节点的 prevlen 属性只有 1 个字节大小，无法保存新节点的长度，此时就需要对压缩列表的空间重分配操作，并将 e1 节点的 prevlen 属性从原来的 1 字节大小扩展为 5 字节大小。

哈希表—Hash类型&Set类型

点击此处跳转到Hash类型
 点击此处跳转到Set类型

哈希表的结构如下：

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

哈希表是一个数组（dictEntry **table），数组的每个元素是一个指向「哈希表节点（dictEntry）」的指针。

哈希表节点的结构如下：

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

链式哈希—Redis解决哈希冲突

可参考其它—如何解决哈希冲突篇

实现的方式就是每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next 指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

Rehash

随着链表长度的增加，在查询这一位置上的数据的耗时就会增加，毕竟链表的查询的时间复杂度是 O(n)。要想解决这一问题，就需要进行 rehash，也就是对哈希表的大小进行扩展。Redis 定义一个 dict 结构体，这个结构体里定义了两个哈希表（ht[2]）。

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

随着数据逐步增多，触发了 rehash 操作，这个过程分为三步

给「哈希表 2」分配空间，一般会比「哈希表 1」大一倍（两倍的意思）；
将「哈希表 1 」的数据迁移到「哈希表 2」中；
迁移完成后，「哈希表 1 」的空间会被释放，并把「哈希表 2」设置为「哈希表 1」，然后在「哈希表 2」新创建一个空白的哈希表，为下次 rehash 做准备。
如果「哈希表 1 」的数据量非常大，那么在迁移至「哈希表 2 」的时候，因为会涉及大量的数据拷贝，此时可能会对 Redis 造成阻塞，无法服务其他请求。

渐进式Rehash

为了避免拷贝数据影响Redis性能，采用了渐进式 rehash，也就是将数据的迁移的工作不再是一次性迁移完成，而是分多次迁移。

给「哈希表 2」分配空间；
在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」上；
随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

在渐进式 rehash 进行期间，新增一个 key-value 时，会被保存到「哈希表 2 」里面，而「哈希表 1」则不再进行任何添加操作，这样保证了「哈希表 1 」的 key-value 数量只会减少，随着 rehash 操作的完成，最终「哈希表 1 」就会变成空表。

触发条件

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

跳表—Zset类型

点击此处跳转到Zset类型

跳表是在链表基础上改进过来的，实现了一种多层的有序链表，这样的好处是能快读定位数据。当数据量很大时，跳表的查找复杂度就是 O(logN)。

typedef struct zskiplist {
    struct zskiplistNode *header, *tail; //头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；
    unsigned long length;                //长度，便于在O(1)时间复杂度获取跳表节点的数量；
    int level;                           //最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量；
} zskiplist;

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

每个跳表节点都有一个后向指针（*backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。
跳表是一个带有层级关系的链表，而且每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。level 数组中的每一个元素代表跳表的一层，也就是由 zskiplistLevel 结构体表示，

跳表查询

从头节点的最高层开始，在遍历某一层的跳表节点时，会用跳表节点中的 SDS 类型的元素和元素的权重来进行判断
如果当前节点的权重「小于」要查找的权重时，跳表就会访问该层上的下一个节点。
如果当前节点的权重「等于」要查找的权重时，并且当前节点的 SDS 类型数据「小于」要查找的数据时，跳表就会访问该层上的下一个节点。
如果上面两个条件都不满足，或者下一个节点为空时，跳表就会使用目前遍历到的节点的 level 数组里的下一层指针，然后沿着下一层指针继续查找，这就相当于跳到了下一层接着查找。

如果要查找「元素：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)

那怎样才能维持相邻两层的节点数量的比例为 2 : 1 呢？

如果采用新增节点或者删除节点时，来调整跳表节点以维持比例的方法的话，会带来额外的开销。Redis跳表在创建节点的时候，随机生成每个节点的层数，并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。
具体的做法是，跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。
这样的做法，相当于每增加一层的概率不超过 25%，层数越高，概率越低，层高限制 7.0 定义为 32，R 5.0 定义为 64， 3.0 定义为 32。

那么为什么是小于0.25呢？

直接上干货：

首先，每个节点肯定都有第1层指针（每个节点都在第1层链表里）。
如果一个节点有第i层(i>=1)指针（即节点已经在第1层到第i层链表中），那么它有第(i+1)层指针的概率为p。
节点最大的层数不允许超过一个最大值，记为MaxLevel（即层高限制）。

产生越高的节点层数，概率越低,无论如何层数总是满足幂次定律（power law，越大的数出现的概率越小）。定量的分析如下：

• 节点层数至少为1。而大于1的节点层数，满足一个概率分布。
• 节点层数恰好等于1的概率为1-p。
• 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。
……..

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

$1 \times (1 - p) + 2p(1 - p) + 3p^2(1 - p) + 4p^3(1 - p) + ... = (1 - p) \sum_{k=1}^{+\infty} kp^{k-1} = (1 - p) \cdot \frac{1}{(1 - p)^2} = \frac{1}{1 - p}$

当p=1/2时，每个节点所包含的平均指针数目为2；当p=1/4时，每个节点所包含的平均指针数目为1.33，你，听懂了吗？

为什么不用平衡树

为什么 Zset 的实现用跳表而不用平衡树（如 AVL树、红黑树等）？

@antirez的回答：

There are a few reasons:
They are not very memory intensive. It’s up to you basically. Changing parameters about the probability of a node to have a given number of levels will make then less memory intensive than btrees.
A sorted set is often target of many ZRANGE or ZREVRANGE operations, that is, traversing the skip list as a linked list. With this operation the cache locality of skip lists is at least as good as with other kind of balanced trees.
They are simpler to implement, debug, and so forth. For instance thanks to the skip list simplicity I received a patch (already in Redis master) with augmented skip lists implementing ZRANK in O(log(N)). It required little changes to the code.

平衡树不是非常内存密集型的。改变关于节点具有给定级别数的概率的参数将使其比 btree 占用更少的内存。
Zset 经常需要执行 ZRANGE 或 ZREVRANGE 的命令，即作为链表遍历跳表。通过此操作，跳表的缓存局部性至少与其他类型的平衡树一样好。(在做范围查找的时候，跳表比平衡树操作要简单)
它们更易于实现、调试等。例如，由于跳表的简单性，我收到了一个补丁（已经在Redis master中），其中扩展了跳表，在 O(log(N) 中实现了 ZRANK。它只需要对代码进行少量修改。

整数集合

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

整数集合的升级操作

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

往这个整数集合中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，所以整数集合要进行升级操作，首先需要为 contents 数组扩容，在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。

扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变，整个转换过程如下：

整数集合的升级操作

quicklist

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

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;

在向 quicklist 添加一个元素的时候，会检查插入位置的压缩列表是否能容纳该元素，如果能容纳就直接保存到 quicklistNode 结构里的压缩列表，如果不能容纳，才会新建一个新的 quicklistNode 结构。
quicklist 会控制 quicklistNode 结构里的压缩列表的大小或者元素个数，来规避潜在的连锁更新的风险，但是这并没有完全解决连锁更新的问题。

listpack

Redis 在 5.0 新设计一个数据结构叫 listpack，目的是替代压缩列表，它最大特点是 listpack 中每个节点不再包含前一个节点的长度了，压缩列表每个节点正因为需要保存前一个节点的长度字段，就会有连锁更新的隐患。

encoding，定义该元素的编码类型，会对不同长度的整数和字符串进行编码；
data，实际存放的数据；
len，encoding+data的总长度；

listpack 没有压缩列表中记录前一个节点长度的字段了，listpack 只记录当前节点的长度，当我们向 listpack 加入一个新元素的时候，不会影响其他节点的长度字段的变化，从而避免了压缩列表的连锁更新问题。

Redis持久化

RDB快照

RDB 快照就是记录某一个瞬间的内存数据，记录的是实际数据，并写入.rdb格式的二进制文件保存在磁盘，这样如果服务器崩溃内存内数据丢失，重新连接后redis会自动读取默认名称为dump.rdb（可以在redis.conf内修改为其他名称）的rdb备份文件，恢复其上次备份时redis存在的所有数据。

save命令：会在主线程生成 RDB 文件，阻塞当前Redis，直到RDB持久化过程完成为止，若内存实例比较大会造成长时间阻塞，线上环境不建议用它
bgsave命令：redis进程执行fork操作创建子线程，由子线程完成持久化，阻塞时间很短（微秒级），是save的优化, 在执行redis-cli shutdown关闭redis服务时，如果没有开启AOF持久化，自动执行bgsave;

Redis 的快照是全量快照，执行的频率不能太频繁，否则会影响 Redis 性能，

执行快照时，数据能被修改吗？

写时复制技术

如果主线程（父进程）要修改共享数据里的某一块数据（比如键值对 A）时，就会发生写时复制，于是这块数据的物理内存就会被复制一份（键值对 A’），然后主线程在这个数据副本（键值对 A’）进行修改操作。与此同时，bgsave 子进程可以继续把原来的数据（键值对 A）写入到 RDB 文件。

注意：发生了写时复制后，RDB 快照保存的是原本的内存数据，而主线程刚修改的数据，是没办法在这一时间写入 RDB 文件的，只能交由下一次的 bgsave 快照。

快照的频率不好把握：

如果频率太低，两次快照间一旦服务器发生宕机，就可能会比较多的数据丢失；
如果频率太高，频繁写入磁盘和创建子进程会带来额外的性能开销。

AOF日志持久化

*3
$3
set
$4
name
$7
xiaolin

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

先执行写操作命令后，才记录到 AOF 日志
好处：

避免额外的检查开销。
不会阻塞当前写操作命令的执行

坏处：

服务器发生宕机，这个数据就会有丢失的风险
可能会给「下一个」命令带来阻塞风险

AOF何时写回磁盘？

此操作在主进程中，是同步的

在 redis.conf 配置文件中的 appendfsync 配置项可以有以下 3 种参数可填：

Always，这个单词的意思是「总是」，所以它的意思是每次写操作命令执行完后，同步将 AOF 日志数据写回硬盘；
Everysec，这个单词的意思是「每秒」，所以它的意思是每次写操作命令执行完后，先将命令写入到 AOF 文件的内核缓冲区，然后每隔一秒将缓冲区里的内容写回到硬盘；
No，意味着不由 Redis 控制写回硬盘的时机，转交给操作系统控制写回的时机，也就是每次写操作命令执行完后，先将命令写入到 AOF 文件的内核缓冲区，再由操作系统决定何时将缓冲区内容写回硬盘。

这三种策略控制的是fsync()系统调用的时机，详情参照《操作系统》

AOF重写机制

AOF 日志是一个文件，随着执行的写操作命令越来越多，文件的大小会越来越大。如果当 AOF 日志文件过大就会带来性能问题，比如重启 Redis 后，需要读 AOF 文件的内容以恢复数据，如果文件过大，整个恢复的过程就会很慢。所以，Redis 为了避免 AOF 文件越写越大，提供了 AOF 重写机制，当 AOF 文件的大小超过所设定的阈值后，Redis 就会启用 AOF 重写机制，来压缩 AOF 文件。

AOF 重写机制是在重写时，读取当前数据库中的所有键值对，然后将每一个键值对用一条命令记录到「新的 AOF 文件」，等到全部记录完后，就将新的 AOF 文件替换掉现有的 AOF 文件。

使用重写机制后，就会读取 key 最新的 value（键值对），然后用最新的命令值记录到新的 AOF 文件，最终也只需要根据这个「键值对」当前的最新状态，然后用一条命令去记录键值对，如果 AOF 重写过程中失败了，放弃新的AOF文件

AOF后台重写

重写 AOF 过程是由后台子进程 bgrewriteaof 来完成的。子进程进行 AOF 重写期间，主进程可以继续处理命令请求，从而避免阻塞主进程

为何使用子进程？不是线程？（考虑写时复制和共享数据）

修改的数据量比较大的 key-value 的时候，这时写时复制的物理内存数据的过程就会比较耗时，有阻塞主进程的风险。还有个问题，重写 AOF 日志过程中，如果主进程修改了已经存在 key-value，此时这个 key-value 数据在子进程的内存数据就跟主进程的内存数据不一致了

为了解决这种数据不一致问题，Redis 设置了一个 AOF 重写缓冲区，这个缓冲区在创建 bgrewriteaof 子进程之后开始使用。在重写 AOF 期间，当 Redis 执行完一个写命令之后，它会同时将这个写命令写入到「AOF 缓冲区」和「AOF 重写缓冲区」。

在 bgrewriteaof 子进程执行 AOF 重写期间，主进程需要执行以下三个工作:

执行客户端发来的命令；
将执行后的写命令追加到「AOF 缓冲区」；
将执行后的写命令追加到「AOF 重写缓冲区」；

AOF重写完成后：

将 AOF 重写缓冲区中的所有内容追加到新的 AOF 的文件中，使得新旧两个 AOF 文件所保存的数据库状态一致；（两个缓冲区的作用是一样的）
新的 AOF 的文件进行改名，覆盖现有的 AOF 文件因为如果 AOF 重写过程中失败了，现有的 AOF 文件就会造成污染，可能无法用于恢复使用。所以 AOF 重写过程，先重写到新的 AOF 文件，重写失败的话，就直接删除这个文件就好，不会对现有的 AOF 文件造成影响

在整个 AOF 后台重写过程中，除了发生写时复制会对主进程造成阻塞，还有信号处理函数执行时也会对主进程造成阻塞，在其他时候，AOF 后台重写都不会阻塞主进程。

针对RDB不适合实时持久化，redis提供了AOF持久化方式来解决

AOF持久化采取的是日志式添加记录每次修改操作的方式，每次执行修改后，AOF持久化只需要将新执行的操作添加到appendonly.aof文件的末尾，对文件进行简单的append操作的IO消耗很小，这种文件是可读的，也就意味着可以被手动修改，拥有更强的灵活性。
比如Redis不小心执行了flushall指令，清空了所有数据，只要是aof没有被rewrite，只需要复制一份aof文件，去掉最后的flushall命令，再重启redis，redis会自动读取aof文件进行恢复（即从头到尾依次执行记录的操作）。
AOF持久化默认不开启，需要在redis.conf配置文件中将appendonly no改为appendonly yes开启。可以设置为每秒进行一次，或每次修改都进行持久化。
相同数据产生的AOF文件比RDB文件更大，而且开启AOF持久化对Redis主线程的性能影响也比RDB更大，但是可以更好保证数据完整性。

双剑合璧

如果想要开启混合持久化功能，可以在 Redis 配置文件将下面这个配置项设置成 yes：

1	aof-use-rdb-preamble yes

混合持久化工作在 AOF 日志重写过程。

当开启了混合持久化时，在 AOF 重写日志时，fork 出来的重写子进程会先将与主线程共享的内存数据以 RDB 方式写入到 AOF 文件，然后主线程处理的操作命令会被记录在重写缓冲区里，重写缓冲区里的增量命令会以 AOF 方式写入到 AOF 文件，写入完成后通知主进程将新的含有 RDB 格式和 AOF 格式的 AOF 文件替换旧的的 AOF 文件。

简单来说，如下图：其它与AOF重写一致
AOF 文件的前半部分是 RDB 格式的全量数据，后半部分是 AOF 格式的增量数据。

大key对持久化的影响

大 Key 对 AOF 日志的影响：参照 fsync() 系统调用函数
大 Key 对 AOF 重写的影响：考虑频繁触发重写，写时复制的性能
大 Key 对 RDB 快照的影响：考虑写时复制的性能

如果 Linux 开启了内存大页，会影响 Redis 的性能的。
常规的内存页分配是按 4KB 的粒度来执行的。内存大页机制支持 2MB 大小的内存页分配

禁用方法如下：

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

Redis的内存策略

如何判定 key 已过期了？

每当我们对一个 key 设置了过期时间时，Redis 会把该 key 带上过期时间存储到一个过期字典（expires dict）中，也就是说「过期字典」保存了数据库中所有 key 的过期时间。

过期字典存储在 redisDb 结构中，如下：

typedef struct redisDb {
    dict *dict;    /* 数据库键空间，存放着所有的键值对 */
    dict *expires; /* 键的过期时间 */
    ....
} redisDb;

过期字典数据结构结构如下：

过期字典的 key 是一个指针，指向某个键对象；
过期字典的 value 是一个 long long 类型的整数，这个整数保存了 key 的过期时间；

过期删除策略有哪些？

定时删除：在设置 key 的过期时间时，同时创建一个定时事件，当时间到达时，由事件处理器自动执行 key 的删除操作。对内存友好，对CPU不友好
惰性删除：不主动删除过期键，每次从数据库访问 key 时，都检测 key 是否过期，如果过期则删除该 key。对CPU友好，对内存不友好
定期删除：隔一段时间「随机」从数据库中取出一定数量的 key 进行检查，并删除其中的过期key。减少对CPU影响，难以确定删除操作执行的时长和频率

Redis 过期删除策略是什么？

Redis 选择「惰性删除+定期删除」这两种策略配和使用

惰性删除：
Redis 在访问或者修改 key 之前，都会调用 expireIfNeeded 函数对其进行检查，检查 key 是否过期：如果过期，则删除该 key，至于选择异步删除，还是选择同步删除，根据 lazyfree_lazy_expire 参数配置决定，然后返回 null 客户端；如果没有过期，不做任何处理，然后返回正常的键值对给客户端；
定期删除：
1、这个间隔检查的时间是多长呢？
在 Redis 中，默认每秒进行 10 次过期检查一次数据库
2、随机抽查的数量是多少呢？
定期删除的实现在 expire.c 文件下的 activeExpireCycle 函数中，其中随机抽查的数量由 ACTIVE_EXPIRE_CYCLE_LOOKUPS_PER_LOOP 定义的，它是写死在代码中的，数值是 20。

Redis 的定期删除的流程：

从过期字典中随机抽取 20 个 key；
检查这 20 个 key 是否过期，并删除已过期的 key；
如果本轮检查的已过期 key 的数量，超过 5 个（20/4），也就是「已过期 key 的数量」占比「随机抽取 key 的数量」大于 25%，则继续重复步骤 1；如果已过期的 key 比例小于 25%，则停止继续删除过期 key，然后等待下一轮再检查。
定期删除是一个循环的流程。Redis 为了保证定期删除不会出现循环过度，导致线程卡死现象，为此增加了定期删除循环流程的时间上限，默认不会超过 25ms。

内存淘汰策略

1、不进行数据淘汰的策略
noeviction（Redis3.0之后，默认的内存淘汰策略）：

2、进行数据淘汰的策略
针对「进行数据淘汰」这一类策略，又可以细分为「在设置了过期时间的数据中进行淘汰」和「在所有数据范围内进行淘汰」这两类策略。

在设置了过期时间的数据中进行淘汰：

volatile-random：随机淘汰设置了过期时间的任意键值；
volatile-ttl：优先淘汰更早过期的键值。
volatile-lru（Redis3.0 之前，默认的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最久未使用的键值；
volatile-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰所有设置了过期时间的键值中，最少使用的键值；

在所有数据范围内进行淘汰：

allkeys-random：随机淘汰任意键值;
allkeys-lru：淘汰整个键值中最久未使用的键值；
allkeys-lfu（Redis 4.0 后新增的内存淘汰策略）：淘汰整个键值中最少使用的键值。

1
2
3

127.0.0.1:6379> config get maxmemory-policy
1) "maxmemory-policy"
2) "noeviction"

LRU和LFU

Redis 实现的是一种近似 LRU 算法，目的是为了更好的节约内存，它的实现方式是在 Redis 的对象结构体中添加一个额外的字段，用于记录此数据的最后一次访问时间。
当 Redis 进行内存淘汰时，会使用随机采样的方式来淘汰数据，它是随机取 5 个值（此值可配置），然后淘汰最久没有使用的那个。但无法解决缓存污染问题

LFU 全称是 Least Frequently Used 翻译为最近最不常用，LFU 算法是根据数据访问次数来淘汰数据的，它的核心思想是“如果数据过去被访问多次，那么将来被访问的频率也更高”。
LFU 算法会记录每个数据的访问次数。当一个数据被再次访问时，就会增加该数据的访问次数。这样就解决了偶尔被访问一次之后，数据留存在缓存中很长一段时间的问题，相比于 LRU 算法也更合理一些。

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

Redis 对象头中的 lru 字段，在 LRU 算法下和 LFU 算法下使用方式并不相同。
在 LRU 算法中，Redis 对象头的 24 bits 的 lru 字段是用来记录 key 的访问时间戳，因此在 LRU 模式下，Redis可以根据对象头中的 lru 字段记录的值，来比较最后一次 key 的访问时间长，从而淘汰最久未被使用的 key。
在 LFU 算法中，Redis对象头的 24 bits 的 lru 字段被分成两段来存储，高 16bit 存储 ldt(Last Decrement Time)，低 8bit 存储 logc(Logistic Counter)。

注意，logc 并不是单纯的访问次数，而是访问频次（访问频率），因为 logc 会随时间推移而衰减的。

在每次 key 被访问时，会先对 logc 做一个衰减操作，衰减的值跟前后访问时间的差距有关系，如果上一次访问的时间与这一次访问的时间差距很大，那么衰减的值就越大，这样实现的 LFU 算法是根据访问频率来淘汰数据的，而不只是访问次数。访问频率需要考虑 key 的访问是多长时间段内发生的。key 的先前访问距离当前时间越长，那么这个 key 的访问频率相应地也就会降低，这样被淘汰的概率也会更大。

对 logc 做完衰减操作后，就开始对 logc 进行增加操作，增加操作并不是单纯的 + 1，而是根据概率增加，如果 logc 越大的 key，它的 logc 就越难再增加。

redis.conf 提供了两个配置项，用于调整 LFU 算法从而控制 logc 的增长和衰减：
lfu-decay-time 用于调整 logc 的衰减速度，它是一个以分钟为单位的数值，默认值为1，lfu-decay-time 值越大，衰减越慢；
lfu-log-factor 用于调整 logc 的增长速度，lfu-log-factor 值越大，logc 增长越慢。

Redis的高可用

主从结构

在服务器 B 上执行下面这条命令：

1	replicaof <服务器 A 的 IP 地址> <服务器 A 的 Redis 端口号>

接着，服务器 B 就会变成服务器 A 的「从服务器」，然后与主服务器进行第一次同步。

主从服务器间的第一次同步的过程可分为三个阶段：

全量同步

第一阶段是建立链接、协商同步

从服务器会给主服务器发送 psync 命令，表示要进行数据同步。psync 命令包含两个参数，分别是主服务器的 runID 和复制进度 offset。

runID，每个 Redis 服务器在启动时都会自动生产一个随机的 ID 来唯一标识自己。当从服务器和主服务器第一次同步时，因为不知道主服务器的 run ID，所以将其设置为 “?”。
offset，表示复制的进度，第一次同步时，其值为 -1。

主服务器收到 psync 命令后，会用 FULLRESYNC 作为响应命令返回给对方。并且这个响应命令会带上这两个参数。从服务器收到响应后，会记录这两个值。FULLRESYNC 响应命令的意图是采用全量复制的方式

第二阶段是主服务器同步数据给从服务器；

主服务器会执行 bgsave 命令（异步）来生成 RDB 文件，然后把文件发送给从服务器。从服务器收到 RDB 文件后，会先清空当前的数据，然后载入 RDB 文件。
但是，这期间的写操作命令并没有记录到刚刚生成的 RDB 文件中，这时主从服务器间的数据就不一致了。
为了保证主从服务器的数据一致性，主服务器在下面这三个时间间隙中将收到的写操作命令，写入到replication buffer 缓冲区里：

主服务器生成 RDB 文件期间；
主服务器发送 RDB 文件给从服务器期间；
「从服务器」加载 RDB 文件期间；

第三阶段是主服务器发送新写操作命令给从服务器。

从服务器完成 RDB 的载入后，会回复一个确认消息给主服务器。主服务器将 replication buffer 缓冲区里所记录的写操作命令发送给从服务器，从服务器执行来自主服务器 replication buffer 缓冲区里发来的命令，这时主从服务器的数据就一致了。

命令传播

主从服务器在完成第一次同步后，双方之间就会维护一个 TCP 连接，而且这个连接是长连接的，目的是避免频繁的 TCP 连接和断开带来的性能开销。

分摊主服务器的压力

主服务器是可以有多个从服务器的，如果从服务器数量非常多，而且都与主服务器进行全量同步的话，就会带来两个问题：

bgsave生成 RDB文件的，主服务器就会忙于使用 fork() 创建子进程，如果主服务器的内存数据很大，在执行 fork() 函数时会阻塞主线程，从而使得 Redis 无法正常处理请求
传输 RDB 文件会占用主服务器的网络带宽，会对主服务器响应命令请求产生影响。

从服务器可以有自己的从服务器，可以把拥有从服务器的从服务器当作经理角色，它不仅可以接收主服务器的同步数据，自己也可以同时作为主服务器的形式将数据同步给从服务器，主服务器生成 RDB 和传输 RDB 的压力可以分摊到充当经理角色的从服务器

在「从服务器」上执行下面这条命令，使其作为目标服务器的从服务器：

1	replicaof <目标服务器的IP> 6379

增量同步

如果主从服务器间的网络连接断开了，那么就无法进行命令传播了，这时从服务器的数据就没办法和主服务器保持一致了，客户端就可能从「从服务器」读到旧的数据。
从 Redis 2.8 开始，网络断开又恢复后，从主从服务器会采用增量复制的方式继续同步，也就是只会把网络断开期间主服务器接收到的写操作命令，同步给从服务器。

从服务器在恢复网络后，会发送 psync 命令给主服务器，此时的 psync 命令里的 offset 参数不是 -1；
主服务器收到该命令后，然后用 CONTINUE 响应命令告诉从服务器接下来采用增量复制的方式同步数据；
然后主服务将主从服务器断线期间，所执行的写命令发送给从服务器，然后从服务器执行这些命令。

主服务器怎么知道要将哪些增量数据发送给从服务器呢？
repl_backlog_buffer，是一个「环形」缓冲区，用于主从服务器断连后，从中找到差异的数据；
replication offset，标记上面那个缓冲区的同步进度，主从服务器都有各自的偏移量，主服务器使用 master_repl_offset 来记录自己「写」到的位置，从服务器使用 slave_repl_offset 来记录自己「读」到的位置。

从Redis完成初始化后，每一个对主Redis的操作会被发送到从Redis执行相同操作，这被称为增量同步，以保证主从Redis数据一致性。
默认情况下，slave只读不写，所以一般对Redis的读操作都在slave上进行，以达到分担master压力的目的，master上只进行写操作。

repl_backlog_buffer 缓冲区是什么时候写入的呢？

在主服务器进行命令传播时，不仅会将写命令发送给从服务器，还会将写命令写入到 repl_backlog_buffer 缓冲区里，因此这个缓冲区里会保存着最近传播的写命令。

网络断开后，当从服务器重新连上主服务器时，从服务器会通过 psync 命令将自己的复制偏移量 slave_repl_offset 发送给主服务器，主服务器根据自己的 master_repl_offset 和 slave_repl_offset 之间的差距，然后来决定对从服务器执行哪种同步操作：从服务器要读取的数据还在 repl_backlog_buffer 缓冲区里，那么主服务器将采用增量同步的方式；相反，主服务器将采用全量同步的方式。

repl_backlog_buffer 缓行缓冲区的默认大小是 1M，为了避免在网络恢复时，主服务器频繁地使用全量同步的方式，应该调整repl_backlog_buffer 缓冲区大小，尽可能的大一些，减少出现从服务器要读取的数据被覆盖的概率，从而使得主服务器采用增量同步的方式。

主从同步策略

主从刚刚连接的时候，进行全量同步；全同步结束后，进行增量同步。如果有需要，slave 在任何时候都可以发起全量同步。redis 策略是，无论如何，首先会尝试进行增量同步，如不成功，要求从机进行全量同步。

如何应对主从数据不一致？

主从节点间的命令复制是异步进行的，所以会主从数据不一致

保证主从节点间的网络连接状况良好，避免主从节点在不同的机房。
可以开发一个外部程序来监控主从节点间的复制进度。具体做法：
Redis 的 INFO replication 命令可以查看主节点接收写命令的进度信息（master_repl_offset）和从节点复制写命令的进度信息（slave_repl_offset），所以，我们就可以开发一个监控程序，先用 INFO replication 命令查到主、从节点的进度，这样就能得到从节点和主节点间的复制进度差值了。
如果某个从节点的进度差值大于我们预设的阈值，我们可以让客户端不再和这个从节点连接进行数据读取，这样就可以减少读到不一致数据的情况。不过，为了避免出现客户端和所有从节点都不能连接的情况，我们需要把复制进度差值的阈值设置得大一些。

哨兵机制

哨兵的职责

哨兵节点主要负责三件事情：监控、通知、选主。

检测主从节点是否运转正常
收集主从节点信息，出错的时候可以通过API通知系统管理员
自动failover：当一个master节点出现了问题，多个哨兵需要沟通是否真的确认出现问题，确认出现问题要检查其他slave节点的情况，自动选举新的适合充当master节点的slave，改变其状态成为新的master，继续提供服务并管理其他slave

第三个职责自动failover是哨兵最重要的职责，配合主从架构很好的保证了系统的高可用性，前面讲过主从架构中所有master和slave的数据都是一致的，所以当提供主要服务的master宕机，可以立刻把拥有相同数据的slave推举为新的master继续提供服务，而不会造成业务的不可用。

注：一个哨兵可以设置监测多个redis节点，但是没必要设置监测slave节点，监测master节点时会自动获取到slave节点的信息。

如何判断主节点真的故障了？

主管下线
如果主节点或者从节点没有在规定的时间内发送PONG，响应哨兵的 PING 命令，哨兵就会将它们标记为主观下线（sdown状态）。这个「规定的时间」是配置项 down-after-milliseconds 参数设定的
客观下线
可能只是因为主节点的系统压力比较大或者网络发送了拥塞，当一个哨兵判断主节点为「主观下线」后，就会向其他哨兵发起命令（is-master-down-by-addr），其他哨兵收到这个命令后，就会根据自身和主节点的网络状况，做出赞成投票或者拒绝投票的响应。
如果超过规定数量的哨兵将该Redis节点标注成了sdown状态，即可确定这个服务确实成为了不可用状态，将该状态改为odown，也就是客观的不可用状态，准备进行新master节点的推举来代替该redis节点继续提供服务。

由哪个哨兵进行主从故障转移？

需要在哨兵集群中选出一个 leader，让 leader 来执行主从切换。哪个哨兵节点判断主节点为「客观下线」，这个哨兵节点就是候选者。

任何一个「候选者」，要满足两个条件：

第一，拿到半数以上的赞成票；
第二，拿到的票数同时还需要大于等于哨兵配置文件中的 quorum 值。

如果某个时间点，刚好有两个哨兵节点判断到主节点为客观下线？
每位候选者都会先给自己投一票，然后向其他哨兵发起投票请求。投票者先收到谁的投票请求，就会先投票给它，如果投票者用完投票机会后，就会拒绝投票。

三个哨兵原则

哨兵在部署的时候不会只部署一个节点，而是用多个节点部署成哨兵集群（最少需要三台机器来部署哨兵集群），通过多个哨兵节点一起判断，就可以就可以避免单个哨兵因为自身网络状况不好，而误判主节点下线的情况。同时，多个哨兵的网络同时不稳定的概率较小，由它们一起做决策，误判率也能降低。

一个高可用的架构应该至少包括三个部署在不同服务器上的哨兵，因为如果只有两个哨兵，有一台服务器挂了，哨兵也就只剩下了一个，即使能确定服务器上redis服务的odown状态，也没有超过半数（超过2/2 = 1个哨兵）的哨兵来选举出哨兵执行failover，因此一个合理的系统至少有三台服务器，三个哨兵来保证系统的高可用性

Redis 1 主 4 从，5 个哨兵，quorum 设置为 3，如果 2 个哨兵故障，当主节点宕机时，哨兵能否判断主节点“客观下线”？主从能否自动切换？
哨兵集群可以判定主节点“客观下线”。哨兵集群还剩下 3 个哨兵，当一个哨兵判断主节点“主观下线”后，询问另外 2 个哨兵后，有可能能拿到 3 张赞同票，这时就达到了 quorum 的值，因此，哨兵集群可以判定主节点为“客观下线”。

哨兵集群可以完成主从切换。当有个哨兵标记主节点为「客观下线」后，就会进行选举 Leader 的过程，因为此时哨兵集群还剩下 3 个哨兵，那么还是可以拿到半数以上（5/2+1=3）的票，而且也达到了 quorum 值，满足了选举 Leader 的两个条件，所以就能选举成功，因此哨兵集群可以完成主从切换。

如果 quorum 设置为 2，并且如果有 3 个哨兵故障的话。此时哨兵集群还是可以判定主节点为“客观下线”，但是哨兵不能完成主从切换了，大家可以自己推演下。

如果 quorum 设置为 3，并且如果有 3 个哨兵故障的话，哨兵集群即不能判定主节点为“客观下线”，也不能完成主从切换了。

quorum 的值建议设置为哨兵个数的二分之一加 1，例如 3 个哨兵就设置 2，5 个哨兵设置为 3，而且哨兵节点的数量应该是奇数。

脑裂现象

如果主节点的网络突然发生了问题，它与所有的从节点都失联了，但是此时的主节点和客户端的网络是正常的。
这个客户端并不知道 Redis 内部已经出现了问题，还在照样的向这个失联的主节点写数据，此时这些数据被主节点缓存到了缓冲区里，因为主从节点之间的网络问题，这些数据都是无法同步给从节点的。
这时，哨兵也发现主节点失联了，它就认为主节点挂了（但实际上主节点正常运行，只是网络出问题了），于是哨兵就会在从节点中选举出一个 leeder 作为主节点，这时集群就有两个主节点了 —— 脑裂出现了。

主从切换如何减少数据丢失？

异步复制同步丢失
当客户端发送写请求给主节点的时候，客户端会返回 ok，接着主节点将写请求异步同步给各个从节点，但是如果此时主节点还没来得及同步给从节点时发生了断电，那么主节点内存中的数据会丢失。
Redis 配置里有一个参数 min-slaves-max-lag，表示一旦所有的从节点数据复制和同步的延迟都超过了 min-slaves-max-lag 定义的值，那么主节点就会拒绝接收任何请求，即使 master 宕机也只是这未复制的 10s 数据。
当客户端发现 master 不可写后，可以采取降级措施，将数据暂时写入本地缓存、磁盘、kafka 消息队列中，在一段时间（等 master 恢复正常）后重新写入 master 来保证数据不丢失。
集群产生脑裂数据丢失
脑裂现象产生后，这时候网络突然好了，哨兵因为之前已经选举出一个新主节点了，它就会把旧主节点降级为从节点（A），然后从节点（A）会向新主节点请求数据同步，因为第一次同步是全量同步的方式，此时的从节点（A）会清空掉自己本地的数据，然后再做全量同步。所以，之前客户端在过程 A 写入的数据就会丢失了，也就是集群产生脑裂数据丢失的问题。
解决方案：
当主节点发现「从节点下线的数量太多」，或者「网络延迟太大」的时候，那么主节点会禁止写操作，直接把错误返回给客户端。

在 Redis 的配置文件中有两个参数我们可以设置：

min-slaves-to-write x，主节点必须要有至少 x 个从节点连接，如果小于这个数，主节点会禁止写数据。
min-slaves-max-lag x，主从数据复制和同步的延迟不能超过 x 秒，如果主从同步的延迟超过 x 秒，主节点会禁止写数据。
分别给它们设置一定的阈值，假设为 N 和 T。这两个配置项组合后的要求是，主节点连接的从节点中至少有 N 个从节点，「并且」主节点进行数据复制时的 ACK 消息延迟不能超过 T 秒，否则，主节点就不会再接收客户端的写请求了。

等到新主节点上线时，就只有新主节点能接收和处理客户端请求，此时，新写的数据会被直接写到新主节点中。而原主节点会被哨兵降为从节点，即使它的数据被清空了，也不会有新数据丢失。

高可用架构

主从故障转移的过程是怎样的？

主从故障转移操作包含以下四个步骤：

在已下线主节点（旧主节点）属下的所有「从节点」里面，挑选出一个从节点，并将其转换为主节点。
让已下线主节点属下的所有「从节点」修改复制目标，修改为复制「新主节点」；
将新主节点的 IP 地址和信息，通过「发布者/订阅者机制」通知给客户端；
继续监视旧主节点，当这个旧主节点重新上线时，将它设置为新主节点的从节点；

选出新主节点

故障转移操作第一步要做的就是在已下线主节点属下的所有「从节点」中，挑选出一个状态良好、数据完整的从节点，然后向这个「从节点」发送 SLAVEOF no one 命令，将这个「从节点」转换为「主节点」。

那么多「从节点」，到底选择哪个从节点作为新主节点的？

先进行网络过滤
Redis 有个叫 down-after-milliseconds * 10 配置项，其 down-after-milliseconds 是主从节点断连的最大连接超时时间。如果在 down-after-milliseconds 毫秒内，主从节点都没有通过网络联系上，我们就可以认为主从节点断连了。如果发生断连的次数超过了 10 次，就说明这个从节点的网络状况不好，不适合作为新主节点。

再进行三轮考察：优先级、复制进度、ID 号。

哨兵首先会根据从节点的优先级来进行排序，优先级越小排名越靠前，
Redis 有个叫 slave-priority 配置项，可以给从节点设置优先级。如果「A 从节点」的物理内存是所有从节点中最大的，那么我们可以把「A 从节点」的优先级设置成最高。
如果优先级相同，则查看复制的下标，哪个从「主节点」接收的复制数据多，哪个就靠前。
如果某个从节点的 slave_repl_offset 最接近 master_repl_offset，说明它的复制进度是最靠前的，于是就可以将它选为新主节点。
如果优先级和下标都相同，就选择从节点 ID 较小的那个。
每个从节点都有一个编号，这个编号就是 ID 号，是用来唯一标识从节点的。

如下图，哨兵 leader 向被选中的从节点 server2 发送 SLAVEOF no one 命令，将该从节点升级为新主节点。

在发送 SLAVEOF no one 命令之后，哨兵 leader 会以每秒一次的频率向被升级的从节点发送 INFO 命令（没进行故障转移之前，INFO 命令的频率是每十秒一次），并观察命令回复中的角色信息，当被升级节点的角色信息从原来的 slave 变为 master 时，哨兵 leader 就知道被选中的从节点已经顺利升级为主节点了。

将从节点指向新主节点

向「从节点」发送 SLAVEOF 命令来实现。

通知客户的主节点已更换

通过 Redis 的发布者/订阅者机制来实现，主从切换完成后，哨兵就会向 +switch-master 频道发布新主节点的 IP 地址和端口的消息，这个时候客户端就可以收到这条信息，然后用这里面的新主节点的 IP 地址和端口进行通信了。

将旧主节点变为从节点

继续监视旧主节点，当旧主节点重新上线时，哨兵集群就会向它发送 SLAVEOF 命令，让它成为新主节点的从节点

哨兵集群是如何组成的？

1	sentinel monitor <master-name> <ip> <redis-port> <quorum>

为什么只需要执行命令设置主节点名字、主节点的 IP 地址和端口号以及 quorum 值，就能搭建哨兵集群？

在主从集群中，主节点上有一个名为sentinel:hello的频道，不同哨兵就是通过它来相互发现，实现互相通信的。

哨兵 A 把自己的 IP 地址和端口的信息发布到sentinel:hello 频道上，哨兵 B 和 C 订阅了该频道。那么此时，哨兵 B 和 C 就可以从这个频道直接获取哨兵 A 的 IP 地址和端口号。然后，哨兵 B、C 可以和哨兵 A 建立网络连接。

那哨兵集群如何知道「从节点」的信息？

主节点知道所有「从节点」的信息，所以哨兵会每 10 秒一次的频率向主节点发送 INFO 命令来获取所有「从节点」的信息。

Redis的缓存机制

缓存污染和预读失效

详情请见操作系统—内存篇

缓存雪崩

大量缓存数据在同一时间过期（失效）
Redis 故障宕机
此时如果有大量的用户请求，都无法在 Redis 中处理，于是全部请求都直接访问数据库，从而导致数据库的压力骤增，严重的会造成数据库宕机，从而形成一系列连锁反应，造成整个系统崩溃。

大量数据同时过期

均匀设置过期时间

如果要给缓存数据设置过期时间，应该避免将大量的数据设置成同一个过期时间。我们可以在对缓存数据设置过期时间时，给这些数据的过期时间加上一个随机数，这样就保证数据不会在同一时间过期。

互斥锁

当业务线程在处理用户请求时，如果发现访问的数据不在 Redis 里，就加个互斥锁，保证同一时间内只有一个请求来构建缓存（从数据库读取数据，再将数据更新到 Redis 里），当缓存构建完成后，再释放锁。未能获取互斥锁的请求，要么等待锁释放后重新读取缓存，要么就返回空值或者默认值。

实现互斥锁的时候，最好设置超时时间，不然第一个请求拿到了锁，然后这个请求发生了某种意外而一直阻塞，一直不释放锁，这时其他请求也一直拿不到锁，整个系统就会出现无响应的现象。

后台更新缓存

业务线程不再负责更新缓存，缓存也不设置有效期，而是让缓存“永久有效”，并将更新缓存的工作交由后台线程定时更新。

事实上，缓存数据不设置有效期，并不是意味着数据一直能在内存里，因为当系统内存紧张的时候，有些缓存数据会被淘汰，而在缓存被“淘汰”到下一次后台定时更新缓存的这段时间内，业务线程读取缓存失败就返回空值，业务的视角就以为是数据丢失了。

后台线程不仅负责定时更新缓存，而且也负责频繁地检测缓存是否有效，检测到缓存失效了，原因可能是系统紧张而被淘汰的，于是就要马上从数据库读取数据，并更新到缓存。

这种方式的检测时间间隔不能太长，太长也导致用户获取的数据是一个空值而不是真正的数据，所以检测的间隔最好是毫秒级的，但是总归是有个间隔时间，用户体验一般。

在业务线程发现缓存数据失效后（缓存数据被淘汰），通过消息队列发送一条消息通知后台线程更新缓存，后台线程收到消息后，在更新缓存前可以判断缓存是否存在，存在就不执行更新缓存操作；不存在就读取数据库数据，并将数据加载到缓存。这种方式相比第一种方式缓存的更新会更及时，用户体验也比较好。

缓存预热

在业务刚上线的时候，我提前把数据缓起来，而不是等待用户访问才来触发缓存构建，这就是所谓的缓存预热，后台更新缓存的机制刚好也适合干这个事情。
Redis自带缓存预读，注意甄别区别

Redis 故障宕机

服务熔断或请求限流机制

可以启动服务熔断机制，暂停业务应用对缓存服务的访问，直接返回错误，不用再继续访问数据库，从而降低对数据库的访问压力，保证数据库系统的正常运行，然后等到 Redis 恢复正常后，再允许业务应用访问缓存服务。
为了减少对业务的影响，可以启用请求限流机制，只将少部分请求发送到数据库进行处理，再多的请求就在入口直接拒绝服务，等到 Redis 恢复正常并把缓存预热完后，再解除请求限流的机制。

构建 Redis 缓存高可靠集群

主从节点的方式构建 Redis 缓存高可靠集群。

缓存击穿

热点数据过期，大量的请求访问了该热点数据，就无法从缓存中读取，直接访问数据库，数据库很容易就被高并发的请求冲垮。
可以认为缓存击穿是缓存雪崩的一个子集。应对缓存击穿可以采取前面说到两种方案：

互斥锁方案，保证同一时间只有一个业务线程更新缓存，未能获取互斥锁的请求，要么等待锁释放后重新读取缓存，要么就返回空值或者默认值。
不给热点数据设置过期时间，由后台异步更新缓存，或者在热点数据准备要过期前，提前通知后台线程更新缓存以及重新设置过期时间；

缓存穿透

当用户访问的数据，既不在缓存中，也不在数据库中，导致请求在访问缓存时，发现缓存缺失，再去访问数据库时，发现数据库中也没有要访问的数据，没办法构建缓存数据，来服务后续的请求。那么当有大量这样的请求到来时，数据库的压力骤增，这就是缓存穿透的问题。

缓存穿透的发生一般有这两种情况：

业务误操作，缓存中的数据和数据库中的数据都被误删除了，所以导致缓存和数据库中都没有数据；
黑客恶意攻击，故意大量访问某些读取不存在数据的业务；

应对缓存穿透的方案，常见的方案有三种。

非法请求的限制

在入口处进行参数校验，如果判断出是恶意请求就直接返回错误，避免进一步访问缓存和数据库。

缓存空值或者默认值

可以针对查询的数据，在缓存中设置一个空值或者默认值，这样后续请求就可以从缓存中读取到空值或者默认值，返回给应用，而不会继续查询数据库。

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

可以在写入数据库数据时，使用布隆过滤器做个标记，然后在用户请求到来时，业务线程确认缓存失效后，可以通过查询布隆过滤器快速判断数据是否存在，如果不存在，就不用通过查询数据库来判断数据是否存在。
即使发生了缓存穿透，大量请求只会查询 Redis 和布隆过滤器，而不会查询数据库，保证了数据库能正常运行，Redis 自身也是支持布隆过滤器的。

布隆过滤器

布隆过滤器由「初始值都为 0 的位图数组」和「 N 个哈希函数」两部分组成。

布隆过滤器会通过 3 个操作完成标记：

使用 N 个哈希函数分别对数据做哈希计算，得到 N 个哈希值；
将第一步得到的 N 个哈希值对位图数组的长度取模，得到每个哈希值在位图数组的对应位置。
将每个哈希值在位图数组的对应位置的值设置为 1；

假设有一个位图数组长度为 8，哈希函数 3 个的布隆过滤器。

当应用要查询数据 x 是否数据库时，通过布隆过滤器只要查到位图数组的第 1、4、6 位置的值是否全为 1，只要有一个为 0，就认为数据 x 不在数据库中。

布隆过滤器由于是基于哈希函数实现查找的，高效查找的同时存在哈希冲突的可能性，比如数据 x 和数据 y 可能都落在第 1、4、6 位置，而事实上，可能数据库中并不存在数据 y，存在误判的情况。

查询布隆过滤器查询到数据不存在，数据库中一定就不存在这个数据，数据存在，并不一定证明数据库中存在这个数据。

Redis的系统设计

数据库和缓存的数据如何保持一致性

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

并发问题导致：

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

如果业务对缓存命中率有很高的要求，可以采用「更新数据库 + 更新缓存」的方案，因为更新缓存并不会出现缓存未命中的情况。
在更新缓存前先加个分布式锁，保证同一时间只运行一个请求更新缓存，就会不会产生并发问题了，当然引入了锁后，对于写入的性能就会带来影响。
在更新完缓存时，给缓存加上较短的过期时间，这样即时出现缓存不一致的情况，缓存的数据也会很快过期，对业务还是能接受的。

所以先更新数据库，还是先删除缓存？

是否可以借用cpu三级缓存失效策略？可以，详情请见操作系统—cpu篇

Cache Aside 策略(旁路缓存策略):不更新缓存，而是删除缓存中的数据。然后，到读取数据时，发现缓存中没了数据之后，再从数据库中读取数据，更新到缓存中。

这样的话在写时又会带来两个问题

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

先删除缓存，再更新数据库，在「读 + 写」并发的时候，还是会出现缓存和数据库的数据不一致的问题。

解决方法可以使用延迟双删，延迟双删实现的伪代码如下：

#删除缓存
redis.delKey(X)
#更新数据库
db.update(X)
#睡眠
Thread.sleep(N)
#再删除缓存
redis.delKey(X)

请求 A 的睡眠时间就需要大于请求 B 「从数据库读取数据 + 写入缓存」的时间。但是具体睡眠多久其实是个玄学，

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

先更新数据库，再删除缓存也是会出现数据不一致性的问题

但是：
redis运行在内存中，数据库实例在磁盘中，内存的速度远大于磁盘，所以上述的情况基本不存在，「先更新数据库 + 再删除缓存」的方案，是可以保证数据一致性的。
为了确保万无一失，还可以给缓存数据加上了「过期时间」，就算在这期间存在缓存数据不一致，有过期时间来兜底，这样也能达到最终一致。

问题：
明明更新了数据，但是数据要过一段时间才生效，客户接受不了。
如果在删除缓存（第二个操作）的时候失败了，会导致缓存中的数据是旧值。加上了过期时间，所以才会出现客户说的过一段时间才更新生效的现象，假设如果没有这个过期时间的兜底，那后续的请求读到的就会一直是缓存中的旧数据，这样问题就更大了。

如何保证「先更新数据库，再删除缓存」这两个操作能执行成功？
其实不管是先操作数据库，还是先操作缓存，只要第二个操作失败都会出现数据一致的问题。有两种方法：都是采用异步操作缓存。

重试机制。
可以引入消息队列，将第二个操作（删除缓存）要操作的数据加入到消息队列，由消费者来操作数据。
如果应用删除缓存失败，可以从消息队列中重新读取数据，然后再次删除缓存，这个就是重试机制。当然，如果重试超过的一定次数，还是没有成功，我们就需要向业务层发送报错信息了。
如果删除缓存成功，就要把数据从消息队列中移除，避免重复操作，否则就继续重试。
订阅 MySQL binlog，再操作缓存。
第一步是更新数据库，那么更新数据库成功，就会产生一条变更日志，记录在 binlog 里。通过订阅 binlog 日志，拿到具体要操作的数据，然后再执行缓存删除，阿里巴巴开源的 Canal 中间件就是基于这个实现的。
Canal 模拟 MySQL 主从复制的交互协议，把自己伪装成一个 MySQL 的从节点，向 MySQL 主节点发送 dump 请求，MySQL 收到请求后，就会开始推送 Binlog 给 Canal，Canal 解析 Binlog 字节流之后，转换为便于读取的结构化数据，供下游程序订阅使用。

Redis常见面试题和总结

Redis 和 Memcached 有什么区别？

Redis 支持的数据类型更丰富（String、Hash、List、Set、ZSet），而 Memcached 只支持最简单的 key-value 数据类型；
Redis 支持数据的持久化，可以将内存中的数据保持在磁盘中，重启的时候可以再次加载进行使用，而 Memcached 没有持久化功能，数据全部存在内存之中，Memcached 重启或者挂掉后，数据就没了；
Redis 原生支持集群模式，Memcached 没有原生的集群模式，需要依靠客户端来实现往集群中分片写入数据；
Redis 支持发布订阅模型、Lua 脚本、事务等功能，而 Memcached 不支持；

为什么用 Redis 作为 MySQL 的缓存？

Redis 具备高性能
运行在内存中
Redis 具备高并发
单台设备的 Redis 的 QPS（Query Per Second，每秒钟处理完请求的次数）是 MySQL 的 10 倍，Redis 单机的 QPS 能轻松破 10w，而 MySQL 单机的 QPS 很难破 1w。

Redis 6.0 之前为什么使用单线程？

CPU 并不是制约 Redis 性能表现的瓶颈所在，更多情况下是受到内存大小和网络I/O的限制，

Redis 6.0 之后为什么引入了多线程？

Redis 的性能瓶颈有时会出现在网络 I/O 的处理上。Redis 6.0 版本引入的多线程 I/O 特性对性能提升至少是一倍以上。

默认情况下 I/O 多线程只针对发送响应数据（write client socket），并不会以多线程的方式处理读请求（read client socket）。要想开启多线程处理客户端读请求，就需要把 Redis.conf 配置文件中的 io-threads-do-reads 配置项设为 yes。

1 2	//读请求也使用io多线程 io-threads-do-reads yes

同时， Redis.conf 配置文件中提供了 IO 多线程个数的配置项。

1 2	// io-threads N，表示启用 N-1 个 I/O 多线程（主线程也算一个 I/O 线程） io-threads 4

默认情况下会额外创建 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（4-1）个 I/O 多线程，用来分担 Redis 网络 I/O 的压力。

怎么判断 Redis 某个节点是否正常工作？

Redis 判断节点是否正常工作，基本都是通过互相的 ping-pong 心态检测机制，如果有一半以上的节点去 ping 一个节点的时候没有 pong 回应，集群就会认为这个节点挂掉了，会断开与这个节点的连接。

Redis 主从节点发送的心态间隔是不一样的，而且作用也有一点区别：

Redis 主节点默认每隔 10 秒对从节点发送 ping 命令，判断从节点的存活性和连接状态，可通过参数repl-ping-slave-period控制发送频率。
Redis 从节点每隔 1 秒发送 replconf ack{offset} 命令，给主节点上报自身当前的复制偏移量，目的是为了：
实时监测主从节点网络状态；
上报自身复制偏移量，检查复制数据是否丢失，如果从节点数据丢失，再从主节点的复制缓冲区中拉取丢失数据。

主从复制架构中，过期key如何处理？

主节点处理了一个key或者通过淘汰算法淘汰了一个key，这个时间主节点模拟一条del命令发送给从节点，从节点收到该命令后，就进行删除key的操作。

主从复制中两个Buffer有什么区别？

replication buffer 、repl backlog buffer 区别如下：

出现的阶段不一样：
repl backlog buffer 是在增量复制阶段出现，一个主节点只分配一个 repl backlog buffer；
replication buffer 是在全量复制阶段和增量复制阶段都会出现，主节点会给每个新连接的从节点，分配一个 replication buffer；
这两个 Buffer 都有大小限制的，当缓冲区满了之后，发生的事情不一样：
当 repl backlog buffer 满了，因为是环形结构，会直接覆盖起始位置数据;
当 replication buffer 满了，会导致连接断开，删除缓存，从节点重新连接，重新开始全量复制。

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

当 Redis 运行在主从模式下时，从库不会进行过期扫描，从库对过期的处理是被动的。也就是即使从库中的 key 过期了，如果有客户端访问从库时，依然可以得到 key 对应的值，像未过期的键值对一样返回。

从库的过期键处理依靠主服务器控制，主库在 key 到期时，会在 AOF 文件里增加一条 del 指令，同步到所有的从库，从库通过执行这条 del 指令来删除过期的 key。

Redis 内存满了，会发生什么？

在 Redis 的运行内存达到了某个阀值，就会触发内存淘汰机制(OOM)，这个阀值就是我们设置的最大运行内存，此值在 Redis 的配置文件中可以找到，配置项为 maxmemory。

如何设计一个缓存策略，可以动态缓存热点数据呢？

由于数据存储受限，系统并不是将所有数据都需要存放到缓存中的，而只是将其中一部分热点数据缓存起来，所以我们要设计一个热点数据动态缓存的策略。

热点数据动态缓存的策略总体思路：通过数据最新访问时间来做排名，并过滤掉不常访问的数据，只留下经常访问的数据。

以电商平台场景中的例子，现在要求只缓存用户经常访问的 Top 1000 的商品。具体细节如下：

先通过缓存系统做一个排序队列（比如存放 1000 个商品），系统会根据商品的访问时间，更新队列信息，越是最近访问的商品排名越靠前；
同时系统会定期过滤掉队列中排名最后的 200 个商品，然后再从数据库中随机读取出 200 个商品加入队列中；
这样当请求每次到达的时候，会先从队列中获取商品 ID，如果命中，就根据 ID 再从另一个缓存数据结构中读取实际的商品信息，并返回。
在 Redis 中可以用 zadd 方法和 zrange 方法来完成排序队列和获取 200 个商品的操作。

Redis 如何实现延迟队列？

延迟队列是指把当前要做的事情，往后推迟一段时间再做。延迟队列的常见使用场景有以下几种：

在淘宝、京东等购物平台上下单，超过一定时间未付款，订单会自动取消；
打车的时候，在规定时间没有车主接单，平台会取消你的单并提醒你暂时没有车主接单；
点外卖的时候，如果商家在10分钟还没接单，就会自动取消订单；

在 Redis 可以使用有序集合（ZSet）的方式来实现延迟消息队列的，ZSet 有一个 Score 属性可以用来存储延迟执行的时间。

使用 zadd score1 value1 命令就可以一直往内存中生产消息。再利用 zrangebysocre 查询符合条件的所有待处理的任务，通过循环执行队列任务即可。

Redis 的大 key 如何处理？

key 对应的 value 很大。String 类型的值大于 10 KB；Hash、List、Set、ZSet 类型的元素的个数超过 5000个；
大 key 会带来以下四种影响：

客户端超时阻塞。
由于 Redis 执行命令是单线程处理，然后在操作大 key 时会比较耗时，那么就会阻塞 Redis，从客户端这一视角看，就是很久很久都没有响应。
引发网络阻塞。
每次获取大 key 产生的网络流量较大，如果一个 key 的大小是 1 MB，每秒访问量为 1000，那么每秒会产生 1000MB 的流量，这对于普通千兆网卡的服务器来说是灾难性的。
阻塞工作线程。
如果使用 del 删除大 key 时，会阻塞工作线程，这样就没办法处理后续的命令。
内存分布不均。
集群模型在 slot 分片均匀情况下，会出现数据和查询倾斜情况，部分有大 key 的 Redis 节点占用内存多，QPS 也会比较大。

如何查找大key

redis-cli —bigkeys 查找大key

1	redis-cli -h 127.0.0.1 -p6379 -a "password" -- bigkeys

注意事项：
最好选择在从节点上执行该命令。因为主节点上执行时，会阻塞主节点；
如果没有从节点，那么可以选择在 Redis 实例业务压力的低峰阶段进行扫描查询，以免影响到实例的正常运行；或者可以使用 -i 参数控制扫描间隔，避免长时间扫描降低 Redis 实例的性能。

该方式的不足之处：

这个方法只能返回每种类型中最大的那个 bigkey，无法得到大小排在前 N 位的 bigkey；
对于集合类型来说，这个方法只统计集合元素个数的多少，而不是实际占用的内存量。但是，一个集合中的元素个数多，并不一定占用的内存就多。因为，有可能每个元素占用的内存很小，这样的话，即使元素个数有很多，总内存开销也不大；

使用 SCAN 命令查找大 key

使用 SCAN 命令对数据库扫描，然后用 TYPE 命令获取返回的每一个 key 的类型。

对于 String 类型，可以直接使用 STRLEN 命令获取字符串的长度，也就是占用的内存空间字节数。

对于集合类型来说，有两种方法可以获得它占用的内存大小：

如果能够预先从业务层知道集合元素的平均大小，那么，可以使用下面的命令获取集合元素的个数，然后乘以集合元素的平均大小，这样就能获得集合占用的内存大小了。List 类型：LLEN 命令；Hash 类型：HLEN 命令；Set 类型：SCARD 命令；Sorted Set 类型：ZCARD 命令；
如果不能提前知道写入集合的元素大小，可以使用 MEMORY USAGE 命令（需要 Redis 4.0 及以上版本），查询一个键值对占用的内存空间。

使用 RdbTools 工具查找大 key

使用 RdbTools 第三方开源工具，可以用来解析 Redis 快照（RDB）文件，找到其中的大 key。
比如，下面这条命令，将大于 10 kb 的 key 输出到一个表格文件。

1	rdb dump.rdb -c memory --bytes 10240 -f redis.csv

如何删除大key？

在应用程序释放内存时，操作系统需要把释放掉的内存块插入一个空闲内存块的链表，以便后续进行管理和再分配。这个过程本身需要一定时间，而且会阻塞当前释放内存的应用程序。

如果一下子释放了大量内存，空闲内存块链表操作时间就会增加，相应地就会造成 Redis 主线程的阻塞，如果主线程发生了阻塞，其他所有请求可能都会超时，超时越来越多，会造成 Redis 连接耗尽，产生各种异常。

分批次删除

对于删除大 Hash，使用 hscan 命令，每次获取 100 个字段，再用 hdel 命令，每次删除 1 个字段。

def del_large_hash():
  r = redis.StrictRedis(host='redis-host1', port=6379)
    large_hash_key ="xxx" #要删除的大hash键名
    cursor = '0'
    while cursor != 0:
        # 使用 hscan 命令，每次获取 100 个字段
        cursor, data = r.hscan(large_hash_key, cursor=cursor, count=100)
        for item in data.items():
                # 再用 hdel 命令，每次删除1个字段
                r.hdel(large_hash_key, item[0])

对于删除大 List，通过 ltrim 命令，每次删除少量元素。

def del_large_list():
  r = redis.StrictRedis(host='redis-host1', port=6379)
  large_list_key = 'xxx'  #要删除的大list的键名
  while r.llen(large_list_key)>0:
      #每次只删除最右100个元素
      r.ltrim(large_list_key, 0, -101)

对于删除大 Set，使用 sscan 命令，每次扫描集合中 100 个元素，再用 srem 命令每次删除一个键。

def del_large_set():
  r = redis.StrictRedis(host='redis-host1', port=6379)
  large_set_key = 'xxx'   # 要删除的大set的键名
  cursor = '0'
  while cursor != 0:
    # 使用 sscan 命令，每次扫描集合中 100 个元素
    cursor, data = r.sscan(large_set_key, cursor=cursor, count=100)
    for item in data:
      # 再用 srem 命令每次删除一个键
      r.srem(large_size_key, item)

对于删除大 ZSet，使用 zremrangebyrank 命令，每次删除 top 100个元素。

def del_large_sortedset():
  r = redis.StrictRedis(host='large_sortedset_key', port=6379)
  large_sortedset_key='xxx'
  while r.zcard(large_sortedset_key)>0:
    # 使用 zremrangebyrank 命令，每次删除 top 100个元素
    r.zremrangebyrank(large_sortedset_key,0,99)

异步删除

用 unlink 命令代替 del 来删除。这样 Redis 会将这个 key 放入到一个异步线程中进行删除，这样不会阻塞主线程。

lazyfree-lazy-eviction：表示当 Redis 运行内存超过 maxmeory 时，是否开启 lazy free 机制删除；
lazyfree-lazy-expire：表示设置了过期时间的键值，当过期之后是否开启 lazy free 机制删除；
lazyfree-lazy-server-del：有些指令在处理已存在的键时，会带有一个隐式的 del 键的操作，比如 rename 命令，当目标键已存在，Redis 会先删除目标键，如果这些目标键是一个 big key，就会造成阻塞删除的问题，此配置表示在这种场景中是否开启 lazy free 机制删除；
slave-lazy-flush：针对 slave (从节点) 进行全量数据同步，slave 在加载 master 的 RDB 文件前，会运行 flushall 来清理自己的数据，它表示此时是否开启 lazy free 机制删除。

建议开启其中的 lazyfree-lazy-eviction、lazyfree-lazy-expire、lazyfree-lazy-server-del 等配置，这样就可以有效的提高主线程的执行效率。

Redis 事务支持回滚吗？

Redis 中并没有提供回滚机制，Redis 并不一定保证原子性

#获取name原本的值
127.0.0.1:6379> GET name
"xiaolin"
#开启事务
127.0.0.1:6379> MULTI
OK
#设置新值
127.0.0.1:6379(TX)> SET name xialincoding
QUEUED
#注意，这条命令是错误的
# expire 过期时间正确来说是数字，并不是‘10s’字符串，但是还是入队成功了
127.0.0.1:6379(TX)> EXPIRE name 10s
QUEUED
#提交事务，执行报错
#可以看到 set 执行成功，而 expire 执行错误。
127.0.0.1:6379(TX)> EXEC
1) OK
2) (error) ERR value is not an integer or out of range
#可以看到，name 还是被设置为新值了
127.0.0.1:6379> GET name
"xialincoding"

作者不支持事务回滚的原因有以下两个：

他认为 Redis 事务的执行时，错误通常都是编程错误造成的，这种错误通常只会出现在开发环境中，而很少会在实际的生产环境中出现，所以他认为没有必要为 Redis 开发事务回滚功能；
不支持事务回滚是因为这种复杂的功能和 Redis 追求的简单高效的设计主旨不符合。这里不支持事务回滚，指的是不支持事务运行时错误的事务回滚。

如何用 Redis 实现分布式锁的？

Redis 的 SET 命令有个 NX 参数可以实现「key不存在才插入」，所以可以用它来实现分布式锁：

如果 key 不存在，则显示插入成功，可以用来表示加锁成功；
如果 key 存在，则会显示插入失败，可以用来表示加锁失败。

1	SET lock_key unique_value NX PX\|EX 10000

解锁的时候，要先判断锁的 unique_value 是否为加锁客户端，是的话，才将 lock_key 键删除。解锁是有两个操作，这时就需要 Lua 脚本来保证解锁的原子性，因为 Redis 在执行 Lua 脚本时，可以以原子性的方式执行，保证了锁释放操作的原子性

// 释放锁时，先比较 unique_value 是否相等，避免锁的误释放
if redis.call("get",KEYS[1]) == ARGV[1] then
    return redis.call("del",KEYS[1])
else
    return 0
end

Redis 主从复制模式中的数据是异步复制的，这样导致分布式锁的不可靠性，如果在 Redis 主节点获取到锁后，在没有同步到其他节点时，Redis 主节点宕机了，此时新的 Redis 主节点依然可以获取锁，所以多个应用服务就可以同时获取到锁。

【转载】基于 Redis 的分布式锁到底安全吗？

Redis 如何解决集群情况下分布式锁的可靠性？

考虑下面的执行序列：

客户端1从Master获取了锁。
Master宕机了，存储锁的key还没有来得及同步到Slave上。
Slave升级为Master。
客户端2从新的Master获取到了对应同一个资源的锁。

此时的锁是不可靠的

分布式锁算法 Redlock（红锁）
官方推荐是至少部署 5 个 Redis 节点，而且都是主节点，它们之间没有任何关系，都是一个个孤立的节点。

Redlock 算法的基本思路，是让客户端和多个独立的 Redis 节点依次请求申请加锁，如果客户端能够和半数以上的节点成功地完成加锁操作，那么我们就认为，客户端成功地获得分布式锁，否则加锁失败。
条件一：客户端从超过半数（大于等于 N/2+1）的 Redis 节点上成功获取到了锁；
条件二：客户端从大多数节点获取锁的总耗时（t2-t1）小于锁设置的过期时间。

Redlock 算法加锁三个过程：

客户端获取当前时间（t1）。
客户端按顺序依次向 N 个 Redis 节点执行加锁操作：
如果某个 Redis 节点发生故障了，为了保证在这种情况下，Redlock 算法能够继续运行，需要给「加锁操作」设置一个超时时间（不是对「锁」设置超时时间，而是对「加锁操作」设置超时时间），加锁操作的超时时间需要远远地小于锁的过期时间，一般也就是设置为几十毫秒。
一旦客户端从超过半数（大于等于 N/2+1）的 Redis 节点上成功获取到了锁，就再次获取当前时间（t2），然后计算计算整个加锁过程的总耗时（t2-t1）。如果 t2-t1 < 锁的过期时间，此时，认为客户端加锁成功，否则认为加锁失败。

加锁成功后，客户端需要重新计算这把锁的有效时间，计算的结果是「锁最初设置的过期时间」减去「客户端从大多数节点获取锁的总耗时（t2-t1）」。如果计算的结果已经来不及完成共享数据的操作了，我们可以释放锁，以免出现还没完成数据操作，锁就过期了的情况。

加锁失败后，客户端向所有 Redis 节点发起释放锁的操作，释放锁的操作和在单节点上释放锁的操作一样，只要执行释放锁的 Lua 脚本就可以了。