1.3　Redis

Redis是由C语言开发的一款开源、高性能的键值对内存数据库，为了适应不同场景的存储需求，它支持字符串、列表、有序集合、散列和集合等多种数据类型。Redis内置了复制、RDB与AOF持久化、Lua脚本以及Cluster集群高可用解决方案。关于Redis的高频面试知识点整理如下：Redis的5种基本数据类型及底层数据结构实现、RDB与AOF持久化、主从复制原理、Cluster集群、哈希槽、过期策略、Gossip协议、重定向、Pipeline、Redis为什么这么快、Redis实现分布式锁、Redis与Memcache的区别等。

1.3.1　Redis的5种基本数据类型及对应底层实现

Redis的5种基本数据类型是string、list、set、hash和sortedset。

表1-17给出了Redis的5种基本数据类型及其对应的底层实现。

1．Redis底层数据结构之SDS

与C字符串相比，SDS具有以下优点：

●　获取字符串长度的时间复杂度为O(1)。SDS使用len属性维护了本身的长度。

●　避免缓冲区溢出。SDS在修改时先检查空间是否满足需要，若不足则自动将SDS的空间扩展至修改所需的大小。

●　空间预分配与惰性释放减少内存重分配次数。

◆　空间预分配：字符串增长操作需要对SDS空间进行扩展，若SDS修改后的长度小于1MB，则程序分配和len属性同样大小的未使用空间；若SDS修改后的长度大于或等于1MB，则程序只分配1MB的多余空间。

◆　空间惰性释放：当需要缩短SDS保存的字符串时，程序不会立即通过内存重分配来回收字符串缩短后多余的空间，而是使用free属性标记可用空间大小等待将来使用。

●　二进制安全。SDS使用len属性的值而不是空字符来判断字符串是否结束。

2．Redis底层数据结构之压缩列表ziplist

一个压缩列表可以包含任意多个节点（entry），压缩列表各部分组成如图1-96所示。

图1-96中，每个压缩列表节点都由previous_entry_length、encoding、content三个部分组成，previous_entry_length属性以字节为单位，记录了压缩列表中前一个节点的长度。如果前一节点的长度小于254字节，那么previous_entry_length属性的长度为1字节；如果前一节点的长度大于或等于254字节，那么previous_entry_length属性的长度为5字节。虽然压缩列表节省空间，但由于节点的变长，在插入或者更新时可能引起连锁更新问题。

3．Redis底层数据结构之双端链表linkedlist

双端链表的组成如图1-97所示。

链表实现的特性：双端无环，相对于压缩列表来说更浪费空间。

4．Redis底层数据结构之快表quicklist

quicklist是zipList和linkedList的结合体，它将linkedList按段切分，每一段就是一个zipList，多个zipList之间使用双向指针连接起来，如图1-98所示。快表是压缩列表和双端列表的折中方案。

5．Redis底层数据结构之整数集合intset

intset整数集合是一个有序数组，只升级不降级。整数集合的升级规则是，当向一个int16类型数组的整数集合添加一个int64类型的整数值时，整数集合所有元素都会被转换成int64类型。

6．Redis底层数据结构之哈希表hashtable

Redis的哈希表如图1-99所示。Redis的哈希表使用链地址法来解决冲突，哈希表中的键值对增加或者减少太多可能会触发rehash。如果执行的是扩容操作，那么新哈希表的大小为第一个大于或等于当前键值对数量×2的2^n（2的n次方幂）；如果执行的是收缩操作，那么新哈希表的大小为第一个大于或等于当前键值对数量的2^n。rehash是渐进式完成的，rehash期间添加的键值对只会保存到新表，删除、查找、更新等操作会在两个哈希表上进行。每次对字典执行添加、删除、查找或者更新操作时，除了执行指定的操作以外，还会顺带将旧表里的部分键值对rehash到新表中。

7．Redis底层数据结构之跳表skiplist

跳表由多层组成，如图1-100所示，由下至上为1～L层，第k层是第k-1层的索引。每层都是一条有头节点的有序链表，第1层的链表包含跳表中的所有元素。如果某个元素在第k层出现，那么它在第1到k-1层一定会出现，在第k+1层则会按一定的概率出现。

在查找元素时，从最顶层链表的头节点开始遍历。如果当前节点的下一个节点包含的值比目标元素小，则继续往右查找；否则就跳转到下一层查找。如上重复向右和向下的操作，直到找到与目标值相等的元素为止。图1-100中的加粗箭头标记出查找元素24的过程。

1.3.2　Redis为什么这么快

Redis速度快的原因有以下4点：

（1）Redis是一个键值对内存数据库。

（2）使用IO多路复用技术。

（3）非CPU密集型任务。对大key进行非O(1)时间复杂度的操作（CPU密集）会阻塞后续请求，Redis快的前提是不会出现类似情况。

（4）单线程的优势。避免了多线程上下文切换以及共享资源加锁的性能损耗。

1.3.3　Redis持久化之RDB与AOF

1．挺久化的两种方式

Redis是内存数据库，服务器宕机等情况会导致数据丢失，为此Redis提供了两种持久化方案。

1）RDB持久化

RDB持久化是将Redis内存快照保存到硬盘上，Redis可以通过RDB文件还原数据库当时的状态。RDB文件可以通过SAVE或者BGSAVE生成：

●　SAVE：阻塞Redis服务进程，直至生成RDB文件。

●　BGSAVE：复刻一个子进程来创建RDB文件。

2）AOF持久化

AOF持久化流程如图1-101所示。

●　命令追加：写命令追加到AOF缓冲区。

●　文件持久化：AOF缓冲区的内容根据对应的策略写入AOF文件。

●　AOF重写：随着命令持续写入，AOF文件越来越大，重写AOF文件进行压缩。

●　数据恢复：当Redis重启时，可以加载AOF文件进行数据恢复。

3）RDB与AOF的区别

AOF数据同步实时、数据丢失少、磁盘IO开销大，数据恢复相对较慢；RDB快照文件尺寸小，数据恢复速度快，但RDB快照文件生成间隔一般较长，会丢失最后一次生成快照后的数据修改，同时Redis版本演进过程存在旧版本无法兼容新版RDB格式的问题。

2．AOF重写

AOF文件重写原理：从数据库中读取键值并用一条命令记录键值对，代替该键被修改的过程中产生的多条命令。如表1-18所示，list被修改5次，对应AOF文件保存了5条命令，AOF重写后，只需保存1条命令。

为了避免AOF重写阻塞主进程处理客户端的请求，一般复刻一个子进程完成AOF重写，由于子进程重写的同时Redis又接收客户端的写命令对当前数据库进行修改，因此可能导致数据库当前状态和重写后的AOF文件所保存的数据库状态不一致。为了解决该问题，Redis每执行一条写命令，就同时发送给AOF缓冲区和AOF重写缓冲区，如图1-102所示。

子进程完成AOF重写后向父进程发送一个信号，通知父进程完成以下工作：

●　将AOF重写缓冲区中的所有内容写入新的AOF文件。

●　重命名新旧AOF文件完成新旧文件的替换。

在整个AOF重写过程中，以上两个工作会对Redis主进程造成阻塞，如表1-19所示。

1.3.4　Redis实现分布式锁的关键点

Redis锁主要利用Redis的setnx命令实现，setnx是SET if Not exists的简写。执行setnx key value，当键不存在时，将key的值设置为value，此时锁抢占成功。可以通过删除键值对或者过期时间来释放锁。实现Redis锁需要注意的事项如下：

1．避免死锁

设置key的过期时间，以保证即使锁没有被显式释放，也可以在一定时间后自动释放，避免资源被永远锁住。

2．锁续期

当前线程获取锁后执行任务，当任务耗时大于Redis key过期时间时，锁会被释放，会存在其他线程获取到该锁的可能。此时可以为已经获取锁的线程增加守护线程，对将要过期但未释放的锁延长有效时间。

3．只允许获取锁的线程释放锁

将参与抢锁的客户端id设置在value中（setnx key value），释放锁前校验value中存放的id是否为自己。

4．互斥性

Redis正常运行时执行setnx命令可以保证只允许一个客户端持有锁；当Redis发生主从切换时，key未及时同步到从节点，锁可能被其他客户端再一次获取，针对该场景可引入红锁机制。

5．可重入（可选）

若允许当前线程在持有锁的情况下再次请求加锁，那么这个锁就是可重入的。Redis可对锁进行重入计数，加锁时加1，解锁时减1，当计数归0时释放锁。

补充说明ZooKeeper与Redis实现分布式锁的异同：从CAP的角度来说，ZooKeeper因为有过半策略保证数据的强一致性，所以ZooKeeper实现的分布式锁强调的是CP，Redis实现的分布式锁强调的是AP。

1.3.5　Redis与Memcache的区别

Redis与Memcache的区别主要体现在以下4个方面：

（1）数据结构方面：Redis数据类型更丰富，有String、List、Set、Zset、Hash等，Memcache只支持String类型。

（2）数据持久化方面：Redis支持AOF与RDB两种持久化方案，而Memcache不支持持久化。

（3）高可用方面：Redis原生支持集群模式，而MC需要客户端去实现集群。

（4）线程模型方面：Redis使用单线程模型（高版本存在多线程），MC是多线程模型。

1.3.6　Redis主从复制原理之SYNC与PSYNC

Redis全量复制（SYNC）一般发生在从节点初始化阶段，这时主节点生成快照传递给从节点，从节点载入快照进行数据恢复。全量复制流程如图1-103所示。

步骤01　Slave向Master发送SYNC命令，要求全量复制。

步骤02　Master执行BGSAVE命令生成RDB快照文件，同时使用缓冲区记录之后的写命令。

步骤03　Master生成RDB文件后发送给Slave，该期间Master继续记录来自客户端的写命令。

步骤04　Slave收到RDB文件后丢弃旧数据，载入Master传递过来的快照。

步骤05　Master完成RDB文件传输后开始向Slave发送缓冲区积累的写命令。

步骤06　Slave完成RDB快照的载入后，开始执行来自Master缓冲区的写命令。

SYNC命令的典型使用场景如下：

（1）Slave第一次和Master连接，即初次复制。

（2）主从断连后重新建立连接。

初次复制使用SYNC命令进行全量复制是高效且必要的，但主从断连后重新建立连接，可能从节点仅丢失了几个写命令，这时也使用全量复制并不划算，如图1-104所示。

为了解决该问题，Redis 2.8版本提供了PSYNC命令实现部分复制，PSYNC命令格式如下：

     PSYNC <runid> <offset>

其中runid代表主服务器id，offset表示从服务器最后接收命令的偏移量。

PSYNC命令执行流程如图1-105所示。

步骤01　当前节点向Master发送SLAVEOF命令，请求成为Slave。

步骤02　当前节点根据自己是否保存Master runid来判断是否是第一次复制，若是第一次复制，则向Master发送psync ? -1命令来进行全量复制，否则向Master发送psync < runid > < offset >命令。

步骤03　Master接收到psync命令，若runid与本机的id一致，并且offset和本机的偏移量相差没有超过复制积压缓冲区大小（复制积压缓冲区缓存了Master传播出去的命令），则Master只需传回失去连接期间丢失的命令，即部分复制；否则Master返回FULLRESYNC<runid> < offset>命令，Slave将runid保存起来，并进行全量复制。

1.3.7　过期删除策略

常见的过期删除策略有以下3种：

（1）定时删除策略。设置key过期时间的同时创建一个定时器，在键的过期时间来临时立即删除键。定时删除及时释放内存，但浪费CPU。

（2）惰性删除策略。在访问key时顺便检查它是否过期，若过期则删除，否则返回该键值对。惰性删除策略对CPU友好，但浪费内存空间。

（3）定期删除策略。该策略是定时删除和惰性删除方案的折中，每隔一段时间执行一次删除过期key的操作，删除哪些数据库的哪些过期键由算法决定。我们通过限制执行的时长和频率来减少对CPU的影响，同时定期主动删除过期键又有效地减少了内存浪费。

Redis使用的是惰性删除和定期删除策略。

1.3.8　Redis哈希槽

Redis集群包含16384个哈希槽通过CRC16(key)%16384来计算键归属于哪个槽。集群中的每一个节点负责处理一部分哈希槽。如图1-106所示，该Redis集群拥有3个节点，哈希槽平均分配。

这样的设计方便添加和删除集群中的节点。例如集群中存在3个节点A、B、C，如果想添加一个新节点D，只需要将节点A，B，C负责的部分槽转移到节点D。同样，如果想从集群中删除节点A，也只需将节点A负责的槽转移到节点B和节点C，之后即可将它从集群中删除。

1.3.9　Redis Gossip协议

Gossip协议（Gossip Protocol）是基于流行病传播方式的节点之间信息交换的协议。Redis集群中的每个节点都维护一份自己视角下的集群的状态，比如集群中各节点所负责的slots信息以及migrate状态等。为了交换不同节点的状态信息达到数据的最终一致性，集群节点之间相互发送多种消息进行通信，主要的消息命令有：

●　MEET：集群中的节点向新节点发送加入集群邀请，新节点收到MEET消息后，会回复PONG命令给发送者

●　PING：每个节点都会频繁地向其他节点发送PING消息，其中包含自己的状态和自己维护的集群元数据，节点之间互相通过PING交换元数据。

●　PONG：PING和MEET消息的回应，包含自己的状态和其他信息，也用于信息广播和更新。

●　FAIL：当一个节点判定另一个节点下线时，会向集群所有节点广播该节点挂掉的消息，其他节点收到消息后标记该节点已下线。

Redis采用Gossip协议数据同步如图1-107所示，只要每一个节点将自己的已知信息传递给其他节点，那么最终整个集群所有节点都会认知一致，类似于传染病无障碍传播最终感染整个人群。

1.3.10　重定向moved与ask

1．moved重定向

Redis客户端可以向集群中的任意节点发起请求，如果key所属的槽不在当前节点，那么Redis集群就向客户端响应一个moved重定向，客户端根据moved重定向所包含的信息找到目标节点，再一次发送命令请求，如图1-108所示。

2．ask重定向

ask重定向发生在集群伸缩时，当客户端发送请求至源节点时，数据因为集群伸缩而迁移到了目标节点，ask异常会告诉客户端访问的键值迁移到了哪里，客户端再据此访问目标节点，如图1-109所示。

1.3.11　Pipeline有什么好处

Redis客户端执行一条命令分为4个过程：发送命令、排队、执行、响应结果，如图1-110所示。

如图1-110所示，执行n条命令会产生n次RTT（Round Trip Time，往返时延），执行效率低下。

Pipeline机制允许将一组Redis命令组装后传输给Redis，Redis将这组命令的执行结果按顺序返回给客户端，整个过程只需一次RTT。

原生批命令是原子性的，但Pipeline不保证原子性，即使执行过程中某个命令出现异常，也会继续执行其他的命令。