Java 面试之 Redis-ldwcool's Blog

Redis 简介

主流应用架构为了提升性能一般都会在客户端和存储层之间添加一个缓存层，当客户端向后端发送请求时会先去缓存层查找，如果缓存层有则直接返回，没有则到存储层查询并将结果回写到缓存层中，这样可以减轻存储层的压力。

缓存层中没有时穿透缓存到存储层中查询的行为叫做缓存穿透。
将存储层中查询的结果回写到缓存层中的行为叫做回种。

而且此架构还能实现所谓高大上的熔断机制，当存储层挂掉或无法向外提供服务时可以让客户端的请求直接打在缓存层上，不管有没有获取到数据都直接返回，在有损的情况下对外提供服务。

缓存中间件 —— Memcache 和 Redis 的区别：

Memcache：代码层次类似 Hash。

支持简单数据类型；
不支持数据持久化存储；
不支持主从同步；
不支持分片。

Redis

数据类型丰富；
支持数据磁盘持久化存储；
支持主从同步；
支持分片。

Redis 性能很高，官方给出的数据其可达到 100000+QPS（QPS 即 query per second，每秒内查询次数）。

为什么 Redis 能这么快？

完全基于内存，绝大部分请求是纯粹的内存操作，执行效率高；

Redis 是单进程单线程的键值数据库，由 C语言编写，将数据储存在内存中，因此读写数据时不会受到硬盘 IO的限制，速度极快。
数据结构简单，对数据操作也简单；

Redis 不使用表，其数据库不会预定义和强制用户对其存储的不同数据进行关联，其性能相比关系型数据库高出不止一个量级，其存储结构就是键值对，类似于HashMap。
采用单线程，单线程也能处理高并发请求，想多核也可启动多实例；

Redis 单线程结构是指其主线程是单线程的，主线程负责 IO事件的处理、 IO对应的相关请求的业务处理，过期键的处理、主从协调、集群协调等；除了 IO事件之外的逻辑会被封装成周期性的任务由主线程周期性的处理。

正因为采用单线程，所以客户端的所有读写请求都是由主线程串行处理，因此多个客户端对同一个键进行写操作时就不会有并发的问题，避免了频繁的上下文切换和锁之间的竞争，使得 Redis 效率更高。
使用多路I/O复用模型，非阻塞IO。
FD：File Descriptor，文件描述符。一个打开的文件通过唯一的描述符进行引用，该描述符是打开文件的元数据到文件本身的映射，用一个整数表示。

若采用传统的阻塞I/O模型，当使用read或write对某个文件描述符（FD）进行读写时，如果当前文件描述符不可读或不可写时，整个 Redis 服务将不会对其它的操作做出响应，导致服务不可用。

多路I/O复用模型

其中最重要的函数调用就是Select系统调用，Select方法可同时监控多个文件描述符的可读可写状态，当其中的某些文件描述符可读或可写时Select方法就会返回对应的文件描述符，即Select负责监听文件描述符的状态，将监听的任务交给Selector之后，主线程又可以做其它的事情了，不会被阻塞住。

除select之外还有比起更优秀的epoll、kqueue、evport等多路I/O复用函数。

那么 Redis 具体采用使用哪个函数呢？
- 因地制宜：不同的操作系统上采用不同的多路I/O复用函数作为子模块，给上层提供统一的接口；
- 优先选择时间复杂度为O(1)的 I/O多路复用函数作为底层实现；
- 以时间复杂度为O(n)的select作为保底；
- 基于react设计模式监听I/O事件。
  
  Redis 正是采用react设计模式实现其文件事件处理器的，文件事件处理器采用 I/O多路复用模块同时监听多个文件描述符（FD），当accept、read、write、close文件事件产生时，文件事件处理器就会回调文件描述符（FD）绑定的事件处理器。
  
  因此尽管文件事件处理器是在单线程上进行的，但是通过I/O多路复用模块的引用实现了同时对多个文件描述符（FD）读写的监控，提高了网络通信的性能也保证了 Redis 服务实现的简单。

Redis 常用数据类型

供用户使用的数据类型：String、Hash、List、Set、Sorted Set、HyperLogLog、Geo。

String：最基本的数据类型，二进制安全。

最大可存储 512M的数据，二进制安全表示String类型可以包含任何数据，如 JPG图片，序列化后的对象等。

String支持存储如此多的数据类型离不开其底层的简单动态字符串SDS，它的结构如下：

String类型常用方式如下：

# 设置一条数据，键：name 值："redis"（字符串类型）
set name "redis"

# 获取键为 name 对应的值
get name

# 设置一条数据，键：name 值："memcache"（字符串类型），会覆盖已存在的数据
set name "memcache"

# 设置一条数据，键：name 值：1（数字类型）
set count 1

# 获取键为 count 对应的值
get count

# 将键为 count 对应的值自增一
incr count

Redis 的单个操作都是原子性的，使得我们不用考虑并发问题，方便的利用原子性自增操作incr实现简单的计数功能。

Hash：String元素组成的字典，适合用于存储对象。

# 设置键：lilei 对应三个属性分别是 name、age、title
hmset lilei name "LiLei" age 26 title "Senior"

# 获取键 lilei 的 age 属性值
hget lilei age

# 获取键 lilei 的 title 属性值
hget lilei title

# 重新设置键 lilei 的 title 属性值
hset lilei title "Pricipal"

List：列表，按照String元素插入顺序排序。

List大约可存储 40亿个元素。

可使用List实现栈的功能，因此可使用它实现最新消息、排行榜等功能。

# 创建 mylist 列表并从其左边添加元素 aaa
lpush mylist aaa

# 从 mylist 列表左边添加元素 bbb
lpush mylist bbb

# 从 mylist 列表左边添加元素 ccc
lpush mylist ccc

# 从左往右取出 mylist 中的数据，从索引 0 的位置开始，共取 10 个元素出来
lrange mylist 0 10

Set：String元素组成的无序集合，通过哈希表实现，不允许重复。

因为通过哈希表实现，所以添加、删除、查找的时间复杂度都是O(1)。

例如在微博应用中可以将一个用户的所有关注人存在一个Set中，将其粉丝存在另一个Set中，由于人性化的提供了求交集、并集、差集等操作，可以非常容易的实现共同关注、共同喜好等功能。

# 创建 myset 并添加元素 111，成功添加返回 1，如果 myset 已经存在此元素返回 0
sadd myset 111

# 向 myset 中添加元素 222
sadd myset 222

# 查看 myset 中的元素，打印的顺序是无序的
smembers myset

Sorted Set：通过分数来为集合中的成员进行从小到大的排序。

与Set一样Sorted Set也是String元素组成的无序集合，通过哈希表实现，不允许重复，不同的是每个元素都会关联一个double类型的分数，Redis 通过此分数值实现从小到大排序，Sorted Set中元素是唯一的但分数值可以重复。

例如：

存储全班同学的Sorted Set，值为学号，score为考试的得分，这样在数据插入集合中时就已经进行了天然的排序；
还可以使用Sorted Set实现带权重的队列，普通消息的score为 2，重要消息的score为 1，工作线程按照score的大小获取任务，实现重要的任务优先执行。

# 创建 myzset 并添加元素 abc 设置其分数为 3，成功添加返回 1，如果 myzset 已经存在此元素返回 0
zadd myzset 3 abc

# 向 myzset 中添加元素 abd，设置其分数为 1
zadd myzset 1 abd

# 打印 myset 中的元素，从索引 0 开始，打印 10 个元素，按照分数值从小到大排序
zrangebyscore myzset 0 10

除了上面 5 个常用的数据结构之外还有：

用于计数的HyperLogLog；
用于支持存储地理位置信息的Geo。

实现这些数据结构的底层数据类型基础：

简单动态字符串
链表
字典
跳跃表
整数集合
压缩列表
对象

正是通过这些底层数据类型的组合才有了上面这些简单易用的 Redis 数据结构。

从海量 Key 里查询出某一固定前缀的 Key

问题详述：假设 Redis 中有 1亿个 key，其中有 10万个 key 拥有相同的前缀，如何将其全部找出来？

为了方便测试需要批量生成测试数据，以下操作在 Linux bash 中执行：

生成2千万条 redis 批量设置 kv 的语句 (key=kn,value=vn) 写入到 /tmp 目录下的 redisTest.txt 文件中；
```
  for((i=1;i<=20000000;i++)); do echo "set k$i v$i" >> /tmp/redisTest.txt ;done;
```

用vim去掉行尾的^M符号；a

vim /tmp/redisTest.txt

:set fileformat=dos #设置文件的格式，通过这句话去掉每行结尾的^M符号

::wq #保存退出

通过redis提供的管道--pipe形式，去跑 redis，传入文件的指令批量灌数据，需要花10分钟左右。
```
cat /tmp/redisTest.txt | 路径/redis-5.0.0/src/redis-cli -h 主机ip -p 端口号 --pipe
```

如果使用keys指令的话，它会一次性返回所有匹配到的数据，由于数量过大，会造成客户端被卡住。

KEYS pattern：查找所有符合给定模式 pattern 的 key。

KEYS 指令一次性返回所有匹配的 key；

键的数量过大会使服务卡顿。

# 取出所有 k1 开头的 key
keys k1*

对于此种情况更适合用SCAN指令。

SCAN指令可以无阻塞的提取出指定模式的 KEY 列表，SCAN每次执行都只会返回少量元素，不会造成卡顿。

# 命令格式：
#    cursor：游标，从哪个位置开始查找；
#    MATCH pattern：需要查找的模式；
#    COUNT count：期望返回的数量，但实际返回数量并不一定与之相同，每次迭代可随意改变此值。
SCAN cursor [MATCH pattern] [COUNT count]

基于游标的迭代器，需要基于上一次的游标延续之前的迭代过程；
以 0 作为游标时将开始一次新的迭代，直到命令返回游标 0 完成一次遍历；
不保证每次执行都返回某个给定数量的元素，支持模糊查询；
一次返回的数量不可控，只能是大概率符合 count 参数。

# 开始一次新的迭代，返回 k1 开头的键，期望本次迭代返回 10 个键
scan 0 match k1* count 10

# 从第一次迭代返回结果中的游标值 11534336 继续迭代
scan 11534336 match k1* count 10

# 从第二次迭代返回结果中的游标值 30932992 继续迭代
scan 30932992 match k1* count 10

# 从第三次迭代返回结果中的游标值 23330816 继续迭代，期望本次迭代返回 5 个键
# 注意返回游标的大小可能比之前的还小，意味着可能获取到重复的 key，需要使用 Java 的 HashSet 去重
scan 23330816 match k1* count 5

如何通过 Redis 实现分布式锁

分布式锁是控制分布式系统或不同系统之间共同访问共享资源的一种锁的实现，不同系统或同一个系统的不同主机之间共享某资源时往往需要互斥防止彼此干扰，保证一致性。

分布式锁需要解决的问题：

互斥性；

任意时刻，只能有一个客户端获取锁。
安全性；

分布式锁只能被持有该锁的客户端删除，不能被其它客户端删除。
死锁；

获取锁的客户端发生故障宕机而未能释放锁时，其它客户端再也不能获取到该锁，导致死锁，需要有机制来避免此问题的发生。
容错；

当部分 Redis 节点宕机时要保证客户端仍能获取锁和释放锁。

SETNX key value：如果key不存在，则创建并赋值。

时间复杂度：O(1)；
返回值：设置成功，返回 1；设置失败，返回 0。

# 设置值 键：locknx 值：test
setnx locknx test

# 获取键：locknx 对应的值
get locknx

使用setnx设置成功后，它是长期有效的，若使用setnx设置值的客户端发生了宕机，就会造成死锁的问题。

可以使用expire指令对其设置的键加一个过期时间。

EXPIRE key seconds

设置 key 的生存时间，当 key 过期时（生存时间为 0），会被自动删除；
缺点：原子性得不到满足。

例如使用如下伪代码实现分布式锁时，若在执行sexnx指令之后，执行expire指令之前客户端宕机则还是会导致死锁问题的发生。

之所以介绍上面这个不好的方法是为了让大家意识到原子操作的重要性。

更好的实现方法如下：

在 Redis 2.6.12 版本开始，就可以使用set指令以原子操作的方式实现setnx + expire。

SET key value [EX seconds] [PX milliseconds] [NX|XX]

EX second: 设置键的过期时间为 second 秒；
PX millisecond：设置键的过期时间为 millisecond 毫秒；
NX：只在键不存在时，才对键进行设置操作；
XX：只在键已经存在时，才对键进行设置操作；
SET操作成功完成时，返回 OK，否则返回 nil。

# 设置数据 键：locktarget 值：12345，过期事件为 10 秒，并且只在键不存在时，才对键进行设置操作
set locktarget 12345 ex 10 nx

# 如果键：locktarget 未过期则返回 nil，已过期则返回 OK 表示设置成功
set locktarget 12223 ex 10 nx

可在程序中通过类似下面这个伪代码实现分布式锁：

如何使用 Redis 做异步队列

有两种实现方式：List集合和pub/sub主题订阅模式。

使用List作为队列，RPUSH生产消息，LPOP消费消息。

缺点：没有等待队列里有值就直接消费；
弥补：可以通过在应用层引入Sleep机制去调用LPOP重试。

# 从右侧向 List 中添加数据，类似于向队尾添加数据
rpush testlist aaa

# 从左侧取出一个 List 中数据，类似于从队头取出数据
lpop testlist

如果不想在应用层引入Sleep机制去调用LPOP重试，也是有办法的。

BLPOP key [key..] timeout：阻塞直到队列有消息或者超时。

缺点：只能供一个消费者消费。

# 从左侧取出一个 testlist 中数据，至多等待 30 秒
blpop testlist 30

为了解决BLPOP只能供一个消费者消费的问题可使用下面这个pub/sub主题订阅模式。

pub/sub：主题订阅模式。

发送者（pub）发送消息，订阅者（sub）接收消息；
订阅者可以订阅任意数量的频道；
缺点：消息的发布是无状态的，无法保证可达。

发布完消息后无法确认消息是否被接收到，是否在传输过程中丢失，对于发布者来说消息是即发即失的。若某个消费者在生产者发送消息时下线，重新上线之后是接收不到刚刚发送的消息的，要解决此问题就需要使用专业的消息队列应用。

当有消息通过publish指令给频道Topic时，该消息就会被发送给订阅此频道的三个客户端。

# 订阅 myTopic 频道，不需要事先创建此频道
subscribe myTopic

# 向 myTopic 频道发送消息
publish myTopic "Hello"

Redis 如何做持久化

Redis 是内存性数据库，一旦服务器进程退出，数据库的数据就会丢失，为了解决这个问题 Redis 提供了 3 种持久化的方法，将内存中数据保存到磁盘中，避免数据丢失。

持久化方式之 RDB

RDB（快照）持久化：保存某个时间点的全量数据快照。

手动触发 RDB 持久化的方式：

SAVE：由主线程执行持久化，会阻塞 Redis 的服务器进程，直到 RDB 文件被创建完毕；
BGSAVE：Fork 出一个子进程来创建 RDB 文件，不阻塞服务器进程。

全量数据快照会保存在dump.rdb文件中，可使用lastsave指令查询上次创建 RDB 文件的时间。

redis.conf配置文件中关于 RDB 的相关配置：

# 900 秒之内有一条写入指令就产生一次快照，即进行一次备份
save 900 1

# 300 秒之内有 10 条写入指令就产生一次快照，即进行一次备份，如果未到 10 次就会等待到 900 秒的时候备份
save 300 10

# 60 秒之内有 10000 条写入指令就产生一次快照，即进行一次备份
save 60 10000

# 上面三个规则是可以同时配置的，也可以增加更多其它的配置
# 使用这么多配置的原因是 Redis 不同时段的读写是不均衡，为了平衡性能和数据安全 Redis 允许我们自由定制什么情况下触发备份

# 禁用 rdb 配置
# save ""

# 设置为 yes 表示 bgsave 备份出错时主进程停止接受写入操作，保护持久化数据一致性问题
# 除非业务有完善的监控系统，否则请开启此项配置
stop-writes-on-bgsave-error yes

# 表示备份时是否需要压缩 rdb 文件，建议设置为 no，因为 redis 属于 cpu 密集型服务，开启压缩会带来更多 cpu 的消耗
rdbcompression yes

自动化触发 RDB 持久化的方式：

根据redis.conf配置里的SAVE m n定时触发（用的是BGSAVE指令）；
主从复制时，主节点自动触发；

从节点全量复制时，主节点会发送 RDB 文件给从节点完成复制操作，此时主节点就会触发BGSAVE。
执行Debug Reload之林；
执行Shutdown指令且没有开启AOF持久化。

BGSAVE原理：

执行BGSAVE指令之后首先会检查当前主进程有没有正在执行的 AOF / RDB 子进程，有则返回错误，没有相关子进程就会触发持久化，调用 Redis 源码中的rdbSaveBackground()方法执行fork()系统调用。

系统调用fork()：创建进程，Linux 中实现了Copy-on-Write(写时复制)。

传统方式下fork()函数在创建子进程时直接把所有资源复制给子进程，这种实现方式简单，但效率低下，而且复制过去的资源可能对子进程毫无用处，Linux 为了降低创建子进程的成本改进了fork()的实现方式，当父进程创建子进程时，内核只为子进程创建虚拟空间，父子两个进程共享相同的物理空间，只有父进程或子进程发生更改操作时才为子进程分配独立的物理空间，这种改进方式称为写时复制。

写时复制的核心思想是：如果有多个调用者同时要求相同资源（如内存或磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者试图修改资源的内容时，系统才会真正复制一份专用副本给该调用者，而其他调用者所见到的最初的资源仍然保持不变。

此过程对其它的调用者是透明的，它优点是如果调用者没有修改资源就不会创建副本，因此多个调用者只是读取操作时可以共享同一份资源。

COW处理过程中需要维持一个为读请求使用的指针，在新数据写入后更新这个指针提升读写并发能力，因此COW间接提供了数据更新过程中的原子性，在保证数据完整性的同时还保证了一定的读写效率。

Redis 做 RDB 持久化时会调用fork()创建一个子进程，父进程继续处理客户端的请求，子进程负责将内存内容写入到临时文件中，由于系统的Copy-on-Write机制，父子进程会共享相同的物理页面，当父进程处理写请求时，系统会要修改的页面创建副本，而不是写共享的页面，所以子进程地址空间内的数据是fork时刻的整个数据库的快照，当子进程完成临时文件的写入操作时会替换掉之前的快照文件，子进程退出，从而完成一次快照操作。

RDB 文件的载入一般是自动的，Redis 服务在启动时如果检测到了 rdb 文件的存在就会自动载入此文件。

缺点：

内存数据的全量同步，数据量大会由于 I/O 而严重影响性能；
可能会因为 Redis 挂掉而丢失从当前至最近一次快照期间的数据。

持久化方式之 AOF

AOF（Append-Only-File）持久化：保存写状态。

记录下除了查询以外的所有变更数据库状态的指令；
以append的形式追加保存到 AOF 文件中（增量）。

redis.conf配置文件中关于 AOF 的相关配置：

# 是否开启 AOF，默认是关闭的
appendonly yes

# 配置 aof 生成文件的名称
appendfilename "appendonly.aof"

# 配置 aof 文件的写入方式，有三个值：always、everysec、no，推荐 everysec
#      always：缓存区的内容发生变化时，就将其内容写入到 aof 文件
#      everysec：每隔一秒将缓存区的内容写入到 aof 文件
#      no：将写入 aof 的时机交给操作系统决定，一般会等待缓存区被填满才会进行一次写入
appendfsync everysec

更改配置文件中的内容后需要重启redis服务才可生效。

随着写操作的不断增多，aof 文件的大小也会不断的增大，但其实很多的写操作是没必要保存的，例如递增某个计数器 100 次，其实只需要保留最终的结果即可，但 aof 会完整的保存这 100 次递增操作，是没有必要的，所以 Redis 提供了不中断服务的情况下在后台重建 aof 的功能。

日志重写解决 AOF 文件大小不断增大的问题，原理如下：

调用fork()，创建一个子进程；
子进程把新的 AOF 写到一个临时文件里，不依赖原来的 AOF 文件；
主进程持续将新的变动同时写到内存和原来的 AOF 里；
主进程获取子进程重写 AOF 的完成信号，往新 AOF 同步增量变动；
使用新的 AOF 文件替换掉I日的 AOF 文件。

可以使用BGREWRITEAOF指令手动触发 AOF 的重写。

持久化方式之混合模式

RDB 和 AOF 的优缺点：

RDB 优点：全量数据快照，文件小，恢复快；
RDB 缺点：无法保存最近一次快照之后的数据；
AOF 优点：可读性高，适合保存增量数据，数据不易丢失；
AOF 缺点：文件体积大，恢复时间长。

RDB-AOF混合持久化方式：BGSAVE做镜像全量持久化，AOF做增量持久化；

Pipeline

使用 Pipeline 的好处：

Pipeline和 Linux 的管道类似；
Redis 基于请求/响应模型，单个请求处理需要要——应答；
Pipeline批量执行指令可节省多次IO往返的时间
有顺序依赖的指令建议还是分批发送。

例如之前模拟生成测试数据时就用到了Pipeline。

# 通过redis提供的管道`--pipe`形式，去跑 redis，传入文件的指令批量灌数据，需要花10分钟左右。
cat /tmp/redisTest.txt | 路径/redis-5.0.0/src/redis-cli -h 主机ip -p 端口号 --pipe

Redis 主从同步

主从同步原理：

Redis 正常部署中使用一个 Master 节点用来提供写操作，其余的若干 Slave 节点提供读操作。

定期的数据备份操作是单独选一个 Slave 节点，最大程度发挥 Redis 的性能。

不需要实时保证 Master 和 Slave 节点数据都是同步的，只需保证数据的弱一致性（最终一致性），即过了一段时间后 Master 和 Slave 节点数据是趋于同步的。

Redis 可以使用主从同步，从从同步，首次同步时主节点执行BGSAVE并将后续的修改操作记录到内存的 Buffer 中，待完成后将 RDB 文件全量同步到从节点中，从节点接收到之后就会将 RDB 文件内容全量加载到内存中，等到加载完成后再通知主节点将生成 RDB 全量数据文件后产生的增量数据同步到从节点，从节点再进行重放，因此分为全同步和增量同步两个过程。

全同步过程：

Slave 发送sync命令到 Master；
Master 启动一个后台进程，将 Redis 中的数据快照保存到文件中；
Master 将保存数据快照期间接收到的写命令缓存起来；
Master 完成写文件操作后，将该文件发送给 Slave 使用；
新的 RDB 文件替换掉I日的 RDB 文件；
Master 将这期间收集的增量写命令发送给 Slave 端。

增量同步过程：

Master接收到用户的操作指令，判断是否需要传播到 Slave，一般增删改都需要传播；
将操作记录追加到 AOF 文件；
将操作传播到其他 Slave，分为两步：
1. 首先需要对齐主从库，确保从数据库是该命令所对应的数据库；
2. 将指令和参数按照 Redis 协议格式写入响应 Slave 的缓存中；
将缓存中的数据发送给 Slave。

主从模式的弊端就是不具备高可用，当主节点挂掉后将无法对外提供写入操作，因此 Redis Sentinel（哨兵）应运而生。

Redis Sentinel（哨兵）是 Redis 官方提供的集群管理工具，其本身也是一个独立允许的进程，它能监控多个主从集群，发现主节点挂掉后能自动进行主从切换。

解决主从同步 Master 宕机后的主从切换问题：

监控：检查主从服务器是否运行正常；
提醒：通过 API 向管理员或者其他应用程序发送故障通知；
自动故障迁移：主从切换；

当主节点挂掉后，Sentinel 会将某个从节点升级为主节点，并让其它的从节点识别新的主节点做主从同步，客户端试图连接挂掉的主节点时也会返回新的主节点地址。

Redis Sentinel 是一个分布式系统，可在一个架构中运行多个 Redis Sentinel 进程，它们之间使用流言协议（Gossip）接收主节点是否下线的信息，使用投票协议决定是否执行自动故障迁移并决定选择哪个从节点作为新的主节点。

流言协议 Gossip

Gossip 算法又被称为反熵，在杂乱无章中寻求一致。

每个节点都随机地与对方通信，最终所有节点的状态达成一致；

种子节点定期随机向其他节点发送节点列表以及需要传播的消息；

不保证信息一定会传递给所有节点，但是最终会趋于一致。

Redis 集群

Redis 集群技术是构建高性能网站架构的重要手段，在网站承受高并发访问压力的同时还需要从海量数据中查询出满足条件的数据并快速响应该怎么办？

如何从海量数据里快速找到所需？

数据分片：按照某种规则去划分数据，分散存储在多个节点上；

使用数据分片降低单节点服务器的压力，Redis 集群采用无中心结构，每个节点保存不同的数据和整个集群的状态，每个节点都和其它节点连接，节点之间使用流言协议（Gossip）传播信息及发现新的节点。
常规的按照哈希划分无法实现节点的动态增减。

常规的做法是获取 key 的哈希值，然后根据节点数求模，但这样的做法一个明显的弊端是动态增加节点后会造成大量的 key 无法被命中。

为了解决常规的按照哈希划分无法实现节点的动态增减的问题 Redis 中引入了一致性哈希算法。

一致性哈希算法：

对2^32取模，将哈希值空间组织成虚拟的圆环；

将各个服务器进行 Hash 变化，可使用 IP，主机名等作为关键字进行 Hash ，确定每台服务器在哈希环上的位置。假设 4 台服务器进行 Hash 运算之后在哈希环上的位置如下：
将数据 key 使用相同的函数 Hash 计算出哈希值，确定在哈希环上的位置，沿环顺时针寻找，遇到的第一台服务器就是要存储的服务器了，例如Object A会被存到Node A上，Object B会被存到Node B上：
假设 Node C 宕机，此时 ABD 并不会受到影响，只有 C 的对象会被重写定位到 D 中，即 Object C会被重写定位到Node D上：
新增服务器 Node X，Object A，Object B，Object D写入并不受影响，只有Object C需要重写定位到Node X上：

从上面可知，一致性哈希算法中增加服务器受影响的仅仅是新服务器到其环空间中前一台服务器之间的数据，减少服务器同理，因此一致性哈希算法对于节点的增减都只需要定位环空间中的一小部分数据，具有较好的容错性和扩展性。

但是它也并不是十全十美的，它也有问题：Hash环的数据倾斜问题：

一致性哈希算法在服务器节点很少时容易因为节点分布不均匀造成数据倾斜，即大部分数据被缓存在某台服务器上，例如下图中大量的数据集中的存储在 A 上：

为了解决此问题一致性哈希算法引入了虚拟节点的机制，即对每个服务器节点计算多个 Hash，每个计算结果位置放置一个此服务器节点，称为虚拟节点，具体做法可在服务器 IP 或主机名后面增加编号实现，例如为上图中的 A 和 B 节点各计算三个虚拟节点，将其均匀分不到哈希环上，数据定位算法不变，只是多了一步虚拟节点到实际节点之间的映射：

实际应用中通常将虚拟节点设置为 32 个或更多个，所以即便实际节点很少也能做到相对均匀的数据分布。

Redis 集群技术还可以在其中引入主从同步，Redis 哨兵机制进一步提高集群的高可用性，这也是主流应用的做法。

参考资料

剑指Java面试-Offer直通车-慕课网实战 (imooc.com)

目录CONTENT

Java 面试之 Redis