万字长文，九大方面归纳总结Redis

架构师（JiaGouX）我们都是架构师！
架构未来，你来不来？

因公众号更改推送规则，请点“在看”并加“星标”第一时间获取精彩技术分享

一、Redis简介

说到Redis, 我们的第一反应就是“快”。

下面来看几个问题：

1. Redis是单线程的吗？
   其实这么说不完全正确，我们知道Redis是一个Key-Value的非关系型数据库，我们所理解的Redis单线程主要是指网络IO和K-V的读写是由一个主线程来完成的。但Redis的其他功能，比如说持久化、异步删除、集群数据同步，其实是开启了额外的线程来完成的。
2. Redis单线程为什么还能这么快？
   因为Redis是基于内存的，所有的运算都是内存级别的，而且单线程避免了多线程的切换性能耗损问题。
3. Redis单线程如何处理那么多并发客户端连接？
   这里就要扯到NIO多路复用模型了，由于本篇主要是Redis的学习记录，这里等Netty的时候再详细学习。

二、Redis的基本数据结构在大厂是怎么用的？

Redis支持5种数据结构：String、Hash、List、Set、ZSet

PS: String类型可能是大部分人经常用做缓存，但是Redis不仅仅是只能做缓存而已，它的其他数据结构也很强大，甚至在早些年，Redis就支撑起了新浪微博的大部分核心功能，权重不亚于我们的开发语言。

下面的例子建立在各位对Redis的API熟悉的情况下

1. String

   

• 单值缓存(可以实现常规的缓存)
  set key value
  get key
• 对象缓存 (可以实现分布式Session, Key为sessionId, Value为用户对象)
  mset user_name boom  user_age 25
  mget user_name user_age
• 计数器(可以做限流, 阅读数，点赞数，分布式唯一ID等等)
  自增：incr num
  自减：decr num
  加N：incrby num N
  减N：decrby num N

• 分布式锁
  setnx key value (返回1获取锁成功，0失败)

Hash


• 对象缓存 (它相比于String, 更适合存放对象)
  hmset user name boom age 25
  hmget user name age
  很经典的一个例子：购物车
  添加商品到购物车：hset cart_用户id 商品id 购买数量
  增加购物车商品数量：hincrby cart_用户id 商品id 要增加的数量
  获取商品总数: hlen cart_用户id
  删除商品 hdel cart_用户id
  获取购物车所有的商品: hgetall cart_用户id

List


• 实现队列（FIFO）
  Lpush(左边进) + Rpop（右边出）
• 实现栈（FILO）
  Lpush(左边进) + Lpop（左边出）
• 实现阻塞队列
  Lpush(左边进) + BRpop（相比于Rpop会阻塞）
• 很经典的一个例子：公众号、微博消息推送
  我关注了公众号A

1. 公众号A发了篇文章：Lpush msg_公众号A的id 文章id
2. 我要查看公众号A最新的消息(一页四个消息)：Lrange msg_公众号A的id 0 4

Set


求交集：sinter set1 set2 set3 结果为 {c}

求并集：sunion set1 set2 set3 结果为 {a,b,c,d,e}

求差集：sdiff set1 set2 set3 结果为 {a}

• 很经典的一个例子：微博的关注模型

• 集合操作

1. boom关注了a,b,c: sadd boom a b c
2. Tom关注了b,c,d: sadd tom b c d
3. b关注了tom: sadd b tom
4. boom和tom的共同关注的人: sinter boom tom  得到c
5. boom关注的人也关注了tom: sismember tom b
6. boom可能认识的人: sdiff tom b

ZSet


• ZSet集合操作

• 很经典的一个例子：微博热搜排行榜

• ZSet常用操作
  并集计算: ZUNIONSTORE destkey numkeys key [key ...]
  交集计算: ZINTERSTORE destkey numkeys key [key…]

1. 往有序集合key中加入带分值元素:  ZADD key score member [[score member]…]
2. 从有序集合key中删除元素: ZREM key member [member…]
3. 返回有序集合key中元素member的分值: ZSCORE key member
4. 为有序集合key中元素member的分值加上increment: ZINCRBY key increment member
5. 返回有序集合key中元素个数: ZCARD key
6. 正序获取有序集合key从start下标到stop下标的元素: ZRANGE key start stop [WITHSCORES]
7. 倒序获取有序集合key从start下标到stop下标的元素: ZREVRANGE key start stop [WITHSCORES]
8. 点击新闻: ZINCRBY hotNews_20210728 基金大跌
9. 展示当日排行前十: ZREVRANGE hotNews_20210728 0 9 WITHSCORES
10. 七日搜索榜单计算: ZUNIONSTORE hotNews_20210722_20210728 7 hotNews_20210722 hotNews_20210723... hotNews_20210728
11. 展示七日排行前十: ZREVRANGE hotNews_20210722_20210728 0 9 WITHSCORES

三、Redis持久化

Redis最大的特点就是基于内存的，既然是基于内存，那么当Redis服务挂掉或者服务器宕机，数据则会丢失，所以Redis不可避免的得对数据持久化做一些处理，像MySQL,MQ数据就保留在磁盘上，那Redis同理。

Redis有3种持久化方式：RDB、AOF、混合持久化

RDB

在默认情况下， Redis 将内存数据库快照保存在名字为 dump.rdb 的二进制文件中。
你可以对 Redis 进行设置， 让它在“ N 秒内数据集至少有 M 个改动”这一条件被满足时，自动保存一次数据集。
比如说， 设置`save 60 1000`会让 Redis 在满足“ 60 秒内有至少有 1000 个键被改动”这一条件时， 自动保存一次数据集。
关闭RDB只需要将所有的save保存策略注释掉即可

还可以手动执行命令生成RDB快照，客户端执行命令save或bgsave可以生成dump.rdb文件，
每次命令执行都会将所有redis内存快照到一个新的rdb文件里，并覆盖原有rdb快照文件。

save是同步命令，bgsave是异步命令，bgsave会从Redis主进程fork（fork()是linux函数）出一个子进程专门用来生成rdb快照文件

Redis默认是使用的bgsave

save与bgsave对比：

AOF

AOF 持久化: 将修改的每一条指令记录进文件appendonly.aof中

你可以通过修改配置文件来打开 AOF 功能：`appendonly yes`

每当 Redis 执行一个改变数据集的命令时（比如 SET)， 这个命令就会被追加到 AOF 文件的末尾。
这样的话， 当 Redis 重新启动时， 程序就可以通过重新执行 AOF 文件中的命令来达到重建数据集的目的。

你可以配置 Redis 多久才将数据 fsync 到磁盘一次。
有三个选项：
1. appendfsync always：每次有新命令追加到 AOF 文件时就执行一次 fsync ，非常慢，也非常安全。
2. appendfsync everysec：每秒 fsync 一次，足够快（和使用 RDB 持久化差不多），并且在故障时只会丢失 1 秒钟的数据。
3. appendfsync no：从不 fsync ，将数据交给操作系统来处理。更快，也更不安全的选择。

推荐（并且也是默认）的措施为每秒 fsync 一次， 这种 fsync 策略可以兼顾速度和安全性。

AOF和RDB对比：

混合持久化（加强版的AOF）

重启 Redis 时，我们很少使用 RDB来恢复数据，因为会丢失大量数据。
我们通常使用 AOF 日志重放，但是重放 AOF 日志性能相对 RDB来说要慢很多，这样在 Redis 实例很大的情况下，启动需要花费很长的时间。
Redis 为了解决这个问题，带来了一个新的持久化方式——混合持久化。

通过如下配置可以开启混合持久化：`aof-use-rdb-preamble yes`

如果开启了混合持久化，AOF在重写时，不再是单纯将内存数据转换为RESP命令写入AOF文件，
而是将重写这一刻之前的内存做RDB快照处理，并且将RDB快照内容和增量的AOF修改内存数据的命令存在一起，都写入新的AOF文件，
新的文件一开始不叫appendonly.aof，等到重写完新的AOF文件才会进行改名，原子的覆盖原有的AOF文件，完成新旧两个AOF文件的替换。

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

混合持久化AOF文件结构：

四、Redis主从、哨兵、集群分析

主从架构

Redis主从工作原理

1. 如果你为master配置了一个slave，不管这个slave是否是第一次连接上Master，它都会发送一个SYNC命令(redis2.8版本之前的命令) master请求复制数据。(从2.8版本开始，redis改用可以支持部分数据复制的命令PSYNC去master同步数据)
2. master收到SYNC命令后，会在后台进行数据持久化通过bgsave生成最新的rdb快照文件，持久化期间，master会继续接收客户端的请求，它会把这些可能修改数据集的请求缓存在内存中。当持久化进行完毕以后，master会把这份rdb文件数据集发送给slave，slave会把接收到的数据进行持久化生成rdb，然后再加载到内存中。然后，master再将之前缓存在内存中的命令发送给slave。
3. 当master与slave之间的连接由于某些原因而断开时，slave能够自动重连Master，如果master收到了多个slave并发连接请求，它只会进行一次持久化，而不是一个连接一次，然后再把这一份持久化的数据发送给多个并发连接的slave。
4. 当master和slave断开重连后，一般都会对整份数据进行复制。但从redis2.8版本开始，master和slave断开重连后支持部分复制。

数据部分复制

master会在其内存中创建一个复制数据用的缓存队列，缓存最近一段时间的数据，master和它所有的slave都维护了复制的数据下标offset和master的进程id，因此，当网络连接断开后，slave会请求master继续进行未完成的复制，从所记录的数据下标开始。如果master进程id变化了，或者从节点数据下标offset太旧，已经不在master的缓存队列里了，那么将会进行一次全量数据的复制。

• Redis主从全量复制：

• Redis主从部分复制:

哨兵架构

sentinel哨兵是特殊的Redis服务，不提供读写服务，主要用来监控Redis实例节点。

哨兵架构下client端第一次从哨兵找出redis的主节点，后续就直接访问redis的主节点，不会每次都通过sentinel代理访问redis的主节点，当redis的主节点发生变化，哨兵会第一时间感知到，并且将新的redis主节点通知给client端(这里面redis的client端一般都实现了订阅功能，订阅sentinel发布的节点变动消息)

在redis3.0以前的版本要实现集群一般是借助哨兵sentinel工具来监控master节点的状态，如果master节点异常，则会做主从切换，将某一台slave作为master，哨兵的配置略微复杂，并且性能和高可用性等各方面表现一般，特别是在主从切换的瞬间存在访问瞬断的情况，而且哨兵模式只有一个主节点对外提供服务，没法支持很高的并发，且单个主节点内存也不宜设置得过大，否则会导致持久化文件过大，影响数据恢复或主从同步的效率

哨兵Leader选举流程

当一个master服务器被某sentinel视为客观下线状态后，该sentinel会与其他sentinel协商选出sentinel的leader进行故障转移工作。每个发现master服务器进入客观下线的sentinel都可以要求其他sentinel选自己为sentinel的leader，选举是先到先得。同时每个sentinel每次选举都会自增配置纪元(选举周期)，每个纪元中只会选择一个sentinel的leader。如果所有超过一半的sentinel选举某sentinel作为leader。之后该sentinel进行故障转移操作，从存活的slave中选举出新的master，这个选举过程跟集群的master选举很类似。

哨兵集群只有一个哨兵节点，redis的主从也能正常运行以及选举master，如果master挂了，那唯一的那个哨兵节点就是哨兵leader了，可以正常选举新master。

不过为了高可用一般都推荐至少部署三个哨兵节点。为什么推荐奇数个哨兵节点原理跟集群奇数个master节点类似。

集群架构

redis集群是一个由多个主从节点群组成的分布式服务器群，它具有复制、高可用和分片特性。Redis集群不需要sentinel哨兵也能完成节点移除和故障转移的功能。需要将每个节点设置成集群模式，这种集群模式没有中心节点，可水平扩展，据官方文档称可以线性扩展到上万个节点(官方推荐不超过1000个节点)。redis集群的性能和高可用性均优于之前版本的哨兵模式，且集群配置非常简单

Redis集群原理分析

Redis Cluster 将所有数据划分为 16384 个 slots(槽位)，每个节点负责其中一部分槽位。槽位的信息存储于每个节点中。

当 Redis Cluster 的客户端来连接集群时，它也会得到一份集群的槽位配置信息并将其缓存在客户端本地。这样当客户端要查找某个 key 时，可以直接定位到目标节点。同时因为槽位的信息可能会存在客户端与服务器不一致的情况，还需要纠正机制来实现槽位信息的校验调整。

槽位定位算法

Cluster默认会对 key 值使用 CRC16 算法进行 hash 得到一个整数值，然后用这个整数值对 16384 进行取模来得到具体槽位：HASH_SLOT = CRC16(key) mod 16384

跳转重定位

当客户端向一个错误的节点发出了指令，该节点会发现指令的 key 所在的槽位并不归自己管理，这时它会向客户端发送一个特殊的跳转指令携带目标操作的节点地址，告诉客户端去连这个节点去获取数据。客户端收到指令后除了跳转到正确的节点上去操作，还会同步更新纠正本地的槽位映射表缓存，后续所有 key 将使用新的槽位映射表。

Redis集群节点间的通信机制

redis cluster节点间采取gossip协议进行通信 

• 维护集群的元数据有两种方式：集中式和gossip
• 集中式： 优点在于元数据的更新和读取，时效性非常好，一旦元数据出现变更立即就会更新到集中式的存储中，其他节点读取的时候立即就可以立即感知到；不足在于所有的元数据的更新压力全部集中在一个地方，可能导致元数据的存储压力。
• gossip：

gossip协议包含多种消息，包括ping，pong，meet，fail等等。 

ping：每个节点都会频繁给其他节点发送ping，其中包含自己的状态还有自己维护的集群元数据，互相通过ping交换元数据； 

pong: 返回ping和meet，包含自己的状态和其他信息，也可以用于信息广播和更新； 

fail: 某个节点判断另一个节点fail之后，就发送fail给其他节点，通知其他节点，指定的节点宕机了。

meet：某个节点发送meet给新加入的节点，让新节点加入集群中，然后新节点就会开始与其他节点进行通信，不需要发送形成网络的所需的所有CLUSTER MEET命令。发送CLUSTER MEET消息以便每个节点能够达到其他每个节点只需通过一条已知的节点链就够了。由于在心跳包中会交换gossip信息，将会创建节点间缺失的链接。

gossip协议的优点在于元数据的更新比较分散，不是集中在一个地方，更新请求会陆陆续续，打到所有节点上去更新，有一定的延时，降低了压力；缺点在于元数据更新有延时可能导致集群的一些操作会有一些滞后。

ps: 10000端口 , 每个节点都有一个专门用于节点间通信的端口，就是自己提供服务的端口号+10000，比如7001，那么用于节点间通信的就是17001端口。 每个节点每隔一段时间都会往另外几个节点发送ping消息，同时其他几点接收到ping消息之后返回pong消息。

网络抖动: 真实世界的机房网络往往并不是风平浪静的，它们经常会发生各种各样的小问题。比如网络抖动就是非常常见的一种现象，突然之间部分连接变得不可访问，然后很快又恢复正常。为解决这种问题，Redis Cluster 提供了一种选项cluster-node-timeout，表示当某个节点持续 timeout 的时间失联时，才可以认定该节点出现故障，需要进行主从切换。如果没有这个选项，网络抖动会导致主从频繁切换 (数据的重新复制)。

Redis集群选举原理分析

当slave发现自己的master变为FAIL状态时，便尝试进行Failover，以期成为新的master。由于挂掉的master可能会有多个slave，从而存在多个slave竞争成为master节点的过程， 其过程如下：

1. slave发现自己的master变为FAIL
2. 将自己记录的集群currentEpoch加1，并广播FAILOVER_AUTH_REQUEST 信息
3. 其他节点收到该信息，只有master响应，判断请求者的合法性，并发送FAILOVER_AUTH_ACK，对每一个epoch只发送一次ack
4. 尝试failover的slave收集master返回的FAILOVER_AUTH_ACK
5. slave收到超过半数master的ack后变成新Master(这里解释了集群为什么至少需要三个主节点，如果只有两个，当其中一个挂了，只剩一个主节点是不能选举成功的)
6. slave广播Pong消息通知其他集群节点。

ps：从节点并不是在主节点一进入 FAIL 状态就马上尝试发起选举，而是有一定延迟，一定的延迟确保我们等待FAIL状态在集群中传播，slave如果立即尝试选举，其它masters或许尚未意识到FAIL状态，可能会拒绝投票。

集群是否完整才能对外提供服务？

当redis.conf的配置cluster-require-full-coverage为no时，表示当负责一个插槽的主库下线且没有相应的从库进行故障恢复时，
集群仍然可用，如果为yes则集群不可用。

Redis集群为什么至少需要三个master节点，并且推荐节点数为奇数？

因为新master的选举需要大于半数的集群master节点同意才能选举成功，如果只有两个master节点，当其中一个挂了，
是达不到选举新master的条件的。

奇数个master节点可以在满足选举该条件的基础上节省一个节点，比如三个master节点和四个master节点的集群相比，
大家如果都挂了一个master节点都能选举新master节点，如果都挂了两个master节点都没法选举新master节点了，
所以奇数的master节点更多的是从节省机器资源角度出发说的。

五、Redis缓存淘汰算法

缓存淘汰策略

因为Redis是基于内存的，内存的空间是非常宝贵的，所以数据不可能无上限的存储，必定会存在一个淘汰策略定期删除一些key。

那Redis的缓存淘汰策略有两种：定时删除和惰性删除

PS:  如果Redis采用的是主从架构，那么以上两种淘汰策略是基于Redis主库的，每当主库触发了淘汰策略，即会在AOF文件写入一个del命令，而从库的淘汰策略是基于主从同步来完成的。

• 定时删除：

Redis将每个设置了过期时间的key放到一个独立的Hash表中，默认每秒定时遍历这个hash而不是整个Redis内存空间，并且Redis不会遍历所有的key，而是采用一种贪心策略。步骤如下：

1、从过期key字典中，随机找20个key。

2、删除20个key中过期的key。

3、如果2中过期的key超过1/4，则重复第一步。

如果有大量的key在同一时间段内过期，就会造成数据库的集中访问，就是缓存雪崩！

• 惰性删除：

因为定时删除会漏掉一部分已过期的key而没有被删除,所以Redis引入一个惰性删除来删除那些漏掉了的key。

客户端访问的时候，会对这个key的过期时间进行检查，如果过期了就立即删除。

内存淘汰机制

思考一下，如果定期删除漏掉了大量的key, 且我们后面也没有访问这些key, 没有触发惰性删除，那么内存中会残留大量垃圾key, 直到某一个时刻，Redis内存总会被填满，此时Redis会触发他的内存淘汰机制。

Redis配置文件中可以设置maxmemory，内存的最大使用量，到达限度时会执行内存淘汰机制。没有配置时，默认为no-eviction

Redis中的内存淘汰机制：

六、从Redis底层搞懂它的渐进式Rehash

在Redis中，键值对（Key-Value）存储方式是由字典（Dict）保存的，而字典底层是通过哈希表来实现的。通过哈希表中的节点保存字典中的键值对。我们知道当HashMap中由于Hash冲突（负载因子）超过某个阈值时，出于链表性能的考虑，会进行Resize的操作。Redis也一样

在Redis的具体实现中，使用了一种叫做 渐进式哈希（Rehash） 的机制来提高字典的缩放效率，避免 rehash 对服务器性能造成影响，假如Redis中有大量的key, 如果一次性对全部的数据进行Rehash, 可能会导致Redis在一段时间内停止服务。

Redis中hash表的结点如下：

在Redis中，哈希表扩容需要将 哈希表0 里面的所有键值对 rehash 到 哈希表1 里面， 但是， 这个 rehash 动作并不是一次性完成的， 而是分多次、渐进式地完成的。

渐进式rehash的详细步骤

1. 为 哈希表1 分配空间，且空间大小为哈希表0的两倍， 让字典同时持有 哈希表0 和 哈希表1 两个哈希表。
2. 在字典中维持一个索引计数器变量 rehashidx（即哈希表的下标） ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3. 在 rehash 进行期间， 每次对字典执行CRUD操作时， 程序除了执行指定的操作以外， 还会顺带将 哈希表0 在 rehashidx 索引上的所有键值对 rehash 到 哈希表1 ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值+1。
4. 随着字典操作的不断执行， 最终在某个时间点上， 哈希表0 的所有键值对都会被 rehash 至 哈希表1 ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式rehash期间的CRUD操作

因为在进行渐进式 rehash 的过程中， 字典会同时使用  哈希表0 和 哈希表1 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的CRUD操作会在两个哈希表上进行， 比如要在字典里面查找一个键的话， 程序会先在  哈希表0 里面进行查找， 如果没找到的话， 就会继续到 哈希表1 里面进行查找， 诸如此类。

另外， 在渐进式 rehash 执行期间， 新添加到字典的键值对一律会被保存到 哈希表1 里面， 而 哈希表0则不再进行任何添加操作：这一措施保证了 哈希表0 包含的键值对数量会只减不增， 并随着 rehash 操作的执行而最终变成空表。

渐进式rehash带来的问题

渐进式rehash避免了redis阻塞，可以说非常完美，但是由于在rehash时，需要分配一个新的hash表，在rehash期间，同时有两个hash表在使用，会使得redis内存使用量瞬间突增，如果当前Redis结点的内存占用量达到maxmemory, 会触发内存淘汰机制，导致大量的Key被驱逐。

七、BitMap如何解决上亿日活的统计问题？

什么是 BitMap

BitMap，即位图，其实也就是 byte 数组，用二进制表示，只有 0 和 1 两个数字。我们知道8bit=1Byte，所以bitmap本身会极大的节省储存空间。

如图所示：

BitMap 有啥用？

假设某平台的用户数上亿，现在需要要统计日活、周活、月活

1. 用MySQL实现，虽然用MySQL是能实现的，但是为了实现一个统计功能，对MySQL来说将会是一次灾难性的打击。
2. 用Redis的自增，用户登录，我就+1，但是这样统计日活、周活的时候，会出现重复的情况。
3. 在涉及到大数据统计的时候，不妨想想BitMap, 它就是为大数据统计而生。

BitMap统计日活

为了统计今日登录的用户数，我们建立了一个bitmap,每一位标识一个用户ID（假设是1-1亿，空间使用量1亿/8/1024/1024=11MB, 仅仅只要11MB就能统计1亿用户的日活，且速度相当之快）。每次用户登录时会执行一次setbit key user_id 1。将bitmap中对应位置的值置为1，时间复杂度是O(1)。执行bitcount key 统计bitmap结果有多少个1（即活跃用户数）。

---

假设7月25日--7月31日用户登录情况如下：左边表示日期，右边为登录的用户id

20210731：{100,101,102,105}

20210730：{101,102,103}

20210729：{101,102}

20210728：{100,101,102}

20210727：{100,101,102,103}

20210726：{101,102,103}

20210725：{100,101,102,105}

统计一周内连续登录用户：

bitop语法：bitop operation destkey key [key ...],  operation 可以是 AND 、 OR 、 NOT 、 XOR 这四种操作中的任意一种：

• 　　BITOP AND destkey key [key ...] ，对一个或多个 key 求逻辑并，并将结果保存到 destkey 。
• 　　BITOP OR destkey key [key ...] ，对一个或多个 key 求逻辑或，并将结果保存到 destkey 。
• 　　BITOP XOR destkey key [key ...] ，对一个或多个 key 求逻辑异或，并将结果保存到 destkey 。
• 　　BITOP NOT destkey key ，对给定 key 求逻辑非，并将结果保存到 destkey 。

除了 NOT 操作之外，其他操作都可以接受一个或多个 key 作为输入。　　　　

返回值：保存到 destkey 的字符串的长度，和输入 key 中最长的字符串长度相等

描述：对一个或多个保存二进制位的字符串 key 进行位元操作，并将结果保存到 destkey 上。

即我们通过bitop对2021-07-25到2021-07-31进行逻辑并运算，结果放入result中，如下：最后得到七天内连续登录的用户数为2。

判断某个用户是否在七天内连续登录，只需要getbit result 用户id, 返回1，即七天内连续登录

统计周活：

通过bitop对2021-07-25到2021-07-31进行逻辑或运算，结果放入result中

bitop or result activity_20210725 activity_20210726 activity_20210727 activity_20210728 activity_20210729 activity_20210730 activity_20210731

然后bitcount result 即得到周活。

八、大名鼎鼎的Redis跳跃表

Redis 的 zset 是个复合结构, 是由一个 哈希表 和 skiplist 组成的, 其中 hash 用来保存 value 和 score 对应关系，skiplist 用来给 score 排序，在这里我们着重介绍 skiplist 的实现。

SkipList 跳跃表

因为zset需要高效的插入和删除,所以底层不适合使用数组实现, 数组插入删除的时间复杂度为O（n）。需要使用链表, 链表的插入删除的时间复杂度为O（1）, 当插入新元素时需要根据 score插入到链表合适的位置,保证链表的有序性， 高效的办法是通过二分查找去找到插入点。

那么问题就来了, 二分查找的对象必须是有序数组, 只有数组支持快速定位, 链表做不到该怎么办呢? 这时,跳跃表出场了。

如图所示, 采用了空间换时间的思想。跳跃表在链表的基础上加入了层级L0~L3的概念, Redis 的跳跃表共有 64 层, 可容纳2^{64}264 个元素.每个元素的层级是随机分配的,分配 L0 的概率是 100%,就是说每个元素至少会有一层.分配到 L1 的概率是 50%, 分配到 L2 的概率是 25%, 往上以此类推。

每个 kv 对应的结构为zslnode.kv 之间使用指针形成有序的双向链表.同一层的 kv 会使用指针串起来.每层元素的遍历都是从跳跃表的头指针 kv header 出发。

header 的结构也是 zslnode,当中 value 为 null, score 为 -1排在最前面， 为1排在最后面。

struct zslnode{
    string value;
    double score;
    zslnode*[] forwards;    //多层连接的指针
    zslnode* backward;        //回溯指针
}

struct zsl{
    zslnode* header;            //跳跃表头指针
    int maxLevel;                //当前节点的最高层
    map<String,zslnode*> ht;    //hash 中的键值对
}

查找

介绍完 skiplist的数据结构后,我们来具体看下skiplist 是怎样快速定位元素的.

在上图中，查找元素 117，skiplist 会从 header 的顶层出发遍历搜索找到第一个比目标元素小的开始降一层,直到降到最底层找到 117这个节点， 搜索路径为:

1. 比较 21， 比 21 大，往后面找
2. 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找
3. 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找
4. 比较 85， 比 85 大，从后面找
5. 比较 117， 等于 117， 找到了节点。

整个查找过程算法的时间复杂度为O(log(n))O(log(n)).

插入

先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的） 然后在 Level 1 ... Level K 各个层的链表都插入元素。

例子：插入 119， K = 2

如果 K 大于链表的层数，则要添加新的层。

例子：插入 119， K = 4

删除

在各个层中找到包含 x 的节点，使用标准的 删除链表中结点 的方法删除该节点。

例子：删除 71

九、MySQL和Redis双写、读写不一致问题

在大并发下，同时操作数据库与缓存会存在数据不一致性问题

双写不一致

读写并不一致

解决方案

1. 对于并发几率很小的数据(如个人维度的订单数据、用户数据等)，这种几乎不用考虑这个问题，很少会发生缓存不一致，可以给缓存数据加上过期时间，每隔一段时间触发读的主动更新即可。
2. 就算并发很高，如果业务上能容忍短时间的缓存数据不一致(如商品名称，商品分类菜单等)，缓存加上过期时间依然可以解决大部分业务对于缓存的要求。
3. 如果不能容忍缓存数据不一致，可以通过加读写锁保证并发读写或写写的时候按顺序排好队，读读的时候相当于无锁
4. 也可以用阿里开源的canal通过监听数据库的binlog日志及时的去修改缓存，但是引入了新的中间件，增加了系统的复杂度。

PS: canal的工作原理就是把自己伪装成MySQL slave，模拟MySQL slave的交互协议向MySQL Mater发送 dump协议，MySQL mater收到canal发送过来的dump请求，开始推送binary log给canal，然后canal解析binary log，再发送到存储目的地。

总结：以上我们针对的都是读多写少的情况加入缓存提高性能，如果写多读多的情况又不能容忍缓存数据不一致，那就没必要加缓存了，可以直接操作数据库。放入缓存的数据应该是对实时性、一致性要求不是很高的数据。

如喜欢本文，请点击右上角，把文章分享到朋友圈
如有想了解学习的技术点，请留言给若飞安排分享

·END·

相关阅读：

---

作者：Boom

来源：juejin.cn/post/6991080701365846046

版权申明：内容来源网络，仅供分享学习，版权归原创者所有。除非无法确认，我们都会标明作者及出处，如有侵权烦请告知，我们会立即删除并表示歉意。谢谢!

架构师

我们都是架构师！

关注架构师(JiaGouX)，添加“星标”

获取每天技术干货，一起成为牛逼架构师

技术群请加若飞：1321113940 进架构师群

投稿、合作、版权等邮箱：[e-mail]