redis

数据类型

Redis支持五种数据类型：string（字符串），hash（哈希），list（列表），set（集合）及zset(sorted set：有序集合)。
string：底层是由SDS实现。字符串类型的值能存储最大容量：512M
Set：底层实现是hashtable（哈希表）和intset（整数集合）组成。
ZSet：底层实现是ziplist（压缩列表）和skiplist（跳跃表）实现。

数据结构

SDS：简单动态字符串，SDS在redis的源码中主要有int len、int free、char buf[]三个属性构成。len保存字符串的长度，free标识buf数组中未使用的字节数量，buf数组则表示每一个存储的字符元素。
假如存储的字符串长度大于32字节则设置encoding为raw，若长度小于32字节，则encoding设置为embstr。

字典：底层是使用hashtable实现的，其中hashtable在计算出hashcode值后，还要通过sizemask属性和hashcode值再次得到数组下标。

rehash：当hash表中的数据不断增加或减少时，需要对hash进行扩容或者收缩，而这里就是进行rehash操作进行重新散列排布。
hash表结构中分别有dictEntry table、unsigned long size、unsigned long sizemask、unsigned long used 表示哈希表数组、hash表大小、用于计算索引值，总是等于size-1、hash表中已有的数量。
扩容操作是原来大小的2倍，缩小操作是原来的一半。

渐进式rehash：加入hash中的数据非常多，redis不会一次性全部数据rehash成功，而redis内部为了处理这种情况采用渐进式rehash。
redis将rehash分成多步操作，知道全部操作完成，其中具体的实现与对象中的rehashindex属性相关，若rehashindex为-1则表示没有进行rehash操作。

ziplist：ziplist压缩列表，指的是一组连续内存块组成顺序的数据结构，压缩列表能够节省空间，压缩列表中使用多个节点来存储数据。
压缩列表并不是通过使用某种算法进行压缩数据，而是通过使用一组连续的内存空间来节省空间。

skiplist：跳跃表，是一种有序的数据结构，它通过每一个节点维持多个指向其他节点的指针，从而达到快速访问的目的。

intset：整数集合，用于保存整数值的数据结构类型，可以保存int16_t、int32_t、int64_t的整数值。共有三个属性分别是encoding、length、contents[]，分别表示编码、长度、内容。
如果在新增元素阶段超出了集合的长度大小，就会对集合进行升级，升级过程如下：首先扩展底层数组的大小，并且新数组的元素类型为新类型。然后将原来的元素转化为新的元素类型，并将原来的元素的放置到新的数组对应的位置。数组集合升级后就不会降级了，一直保持升级后的状态。

HyperLogLog用来做基数统计。在redis内部每个HyperLogLog只需要花费12KB内存，就可以计算2^64个不同元素的基数，并且无论根据元素多少计算基数所需的空间都是固定的。但是HyperLogLog只能计算基数而不会存储元素本身。

Geo数据结构主要用来存储地理位置信息，并对存储的信息进行操作。
geoadd用于添加地理位置信息，可以将一个或多个经度、纬度、位置名称添加到指定的key中。
geopos从指定的key中获取指定名称的位置(经度和纬度)，不存在的返回nil。
geodist用于返回两个地方之间的距离。默认单位:米。

BloomFilter(布隆过滤器)是由一串很长的二进制向量组成，也可以将其看成是一个二进制的数组。最主要的作用就是判断某个元素是否存在于某个集合中。
原理:在添加一个元素时计算这个key的hashcode值，然后经过处理映射到BloomFilter上，并将这个位置指定为1。判断元素是否存在，也是将key计算hashcode值然后映射到BloomFilter上，值如果为1则存在，不为1则不存在。总的来说BloomFilter可以判断一个元素肯定不存在，而不能判断一定存在。
优缺点:二进制存储，占用内存空间小，插入和查找都很快速。随着数据的增多，错误率也会增加，还有一点是数据无法删除。
应用:解决缓存穿透问题。黑名单校验问题。

线程模型

Redis基于Reactor模式开发了网络事件处理器，这个处理器被称为文件事件处理器（file event handler）。
它的组成结构为4部分：多个套接字、IO多路复用程序、文件事件分派器、事件处理器。因为文件事件分派器队列的消费是单线程的，所以Redis才叫单线程模型。
文件事件处理器使用 I/O 多路复用（multiplexing）程序来同时监听多个套接字，并根据套接字目前执行的任务来为套接字关联不同的事件处理器。
当被监听的套接字准备好执行连接应答（accept）、读取（read）、写入（write）、关闭（close）等操作时，与操作相对应的文件事件就会产生，这时文件事件处理器就会调用套接字之前关联好的事件处理器来处理这些事件。

内存

Redis 内存使用完毕：如果达到设置的上限，Redis的写命令会返回错误信息（但是读命令还可以正常返回。）或者你可以配置内存淘汰机制，当Redis达到内存上限时会冲刷掉旧的内容。
Redis 内存优化：可以好好利用Hash,list,sorted set,set等集合类型数据，因为通常情况下很多小的Key-Value可以用更紧凑的方式存放到一起。尽可能使用散列表（hashes），散列表（是说散列表里面存储的数少）使用的内存非常小。

缓存淘汰策略

一般的剔除策略有 FIFO 淘汰最早数据、LRU 剔除最近最少使用、和 LFU 剔除最近使用频率最低的数据几种策略。
noeviction: 返回错误当内存限制达到并且客户端尝试执行会让更多内存被使用的命令（大部分的写入指令，但DEL和几个例外）
allkeys-lru: 尝试回收最少使用的键（LRU），使得新添加的数据有空间存放。
volatile-lru: 尝试回收最少使用的键（LRU），但仅限于在过期集合的键,使得新添加的数据有空间存放。
allkeys-random: 回收随机的键使得新添加的数据有空间存放。
volatile-random: 回收随机的键使得新添加的数据有空间存放，但仅限于在过期集合的键。
volatile-ttl: 回收在过期集合的键，并且优先回收存活时间（TTL）较短的键,使得新添加的数据有空间存放。

持久化

Redis 提供了 RDB 和 AOF 两种持久化方式。
RDB 是把内存中的数据集以快照形式写入磁盘，实际操作是通过 fork 子进程执行，采用二进制压缩存储。
AOF 是以文本日志的形式记录 Redis 的每一个命令或者每一秒保存一次（不一定需要根据Redis状态判断）或者不保存AOF持久化。为了解决 AOF 文件体积膨胀的问题，Redis 提供了 AOF 文件重写(rewrite)功能，实际上重写并不需要对原有的 AOF 文件进行任何写入和读取，而是针对数据库中键的当前值。。

高可用

Redis 支持主从同步，提供 Cluster 集群部署模式，通过 Sentinel 哨兵来监控 Redis 主服务器的状态。当主挂掉时，在从节点中根据一定策略选出新主，并调整其他从 slaveof 到新主。
选主的策略简单来说有三个：
slave 的 priority 设置的越低，优先级越高；
同等情况下，slave 复制的数据越多优先级越高；
相同的条件下 runid 越小越容易被选中。
在 Redis 集群中，sentinel 也会进行多实例部署，sentinel 之间通过 Raft 协议来保证自身的高可用。

哨兵-Sentinel

哨兵必须用三个实例去保证自己的健壮性的，哨兵+主从并不能保证数据不丢失，但是可以保证集群的高可用。
哨兵组件的主要功能：
集群监控：负责监控 Redis master 和 slave 进程是否正常工作。
消息通知：如果某个 Redis 实例有故障，那么哨兵负责发送消息作为报警通知给管理员。
故障转移：如果 master node 挂掉了，会自动转移到 slave node 上。
配置中心：如果故障转移发生了，通知 client 客户端新的 master 地址。

Sentinel的选举流程：
Sentinel集群正常运行的时候每个节点epoch相同，当需要故障转移的时候会在集群中选出Leader执行故障转移操作。Sentinel采用了Raft协议实现了Sentinel间选举Leader的算法。Sentinel集群运行过程中故障转移完成，所有Sentinel又会恢复平等。Leader仅仅是故障转移操作出现的角色。

raft选举Leader协议：用来解决分布式系统一致性问题的协议。
Raft协议描述的节点共有三种状态：Leader, Follower, Candidate。
redis实例正常运行时只有Leader, Follower状态，当出现异常时会转变为Candidate状态，此时Candidate状态会去竞选Leader状态，向其他节点发送竞选投票，如果大多数节点同意，他就会替代原有的Leader节点，原有Leader节点降级为Follower节点。

term：在分布式系统中，各个节点的时间同步是一个很大的难题，但是为了识别过期时间。Raft协议引入了term（任期）的概念。 Raft协议将时间切分为一个个的Term，可以认为是一种“逻辑时间”。

Raft协议在选举阶段交互的RPC信息有两类：RequestVote是用来向其他节点发送竞选投票。AppendEntries是当该节点得到更多的选票后，成为Leader，向其他节点确认消息。

选举流程：

Raft采用心跳机制来触发Leader选举。系统启动时，全部节点初始化为Follower节点。term为0时节点如果收到RPC消息，首先会保持自己的Follower状态。如果选举超时时间内都没有收到AppendEntries消息，自己的Follower状态就会转变为Candidate状态，然后分别向其他节点发送RequestVote消息、增加自己的term时间片、启动一个新的定时器、和给自己投票。如果在这过程中收到了AppendEntries消息则表示Leader节点已经产生，自己也将转变为Follower状态，选举结束。如果在计时器超时前，节点收到大多数节点的同意投票，就会转换为Leader状态，向其他节点发送AppendEntries消息，告知该节点称为Leader状态。

每个节点在一个term内只能投一次票。

Raft协议的定时器采取随机超时时间，这是选举Leader的关键。

主从复制

主从复制，是指将一台Redis服务器的数据复制到其他的Redis服务器。前者称为主节点(master)，后者称为从节点(slave)。数据的复制是单向的，只能由主节点到从节点。

核心原理：当启动一个 slave node 的时候，它会发送一个 PSYNC 命令给 master node。如果这是 slave node 初次连接到 master node，那么会触发一次 full resynchronization 全量复制。此时 master 会启动一个后台线程，开始生成一份RDB 快照文件，同时还会将从客户端 client 新收到的所有写命令缓存在内存中。RDB 文件生成完毕后， master 会将这个 RDB 发送给 slave，slave 会先写入本地磁盘，然后再从本地磁盘加载到内存中，接着 master 会将内存中缓存的写命令发送到 slave，slave 也会同步这些数据。slave node 如果跟 master node 有网络故障，断开了连接，会自动重连，连接之后 master node 仅会复制给 slave 部分缺少的数据。

主从复制过程大体可以分为3个阶段：连接建立阶段（即准备阶段）、数据同步阶段、命令传播阶段：
连接建立阶段：
保存主节点信息：从节点服务器内部维护了两个字段，即masterhost和masterport字段，用于存储主节点的ip和port信息。slaveof是异步命令，从节点完成主节点ip和port的保存后，向发送slaveof命令的客户端直接返回OK，实际的复制操作在这之后才开始进行。
建立 socket 连接：从节点每秒1次调用复制定时函数replicationCron()，如果发现了有主节点可以连接，便会根据主节点的ip和port，创建socket连接。
发送 ping 命令：从节点成为主节点的客户端之后，发送ping命令进行首次请求。目的在于检查socket 的连接和检查主服务器是否可以处理从服务器的请求。
身份验证：如果从节点中设置了masterauth选项，则从节点需要向主节点进行身份验证；没有设置该选项，则不需要验证。
发送从端口信息：身份验证之后，从节点会向主节点发送其监听的端口号（前述例子中为6380），主节点将该信息保存到该从节点对应的客户端的slave_listening_port字段中。
数据同步阶段：具体执行的方式是，从节点向主节点发送psync命令（Redis2.8以前是sync命令），开始同步。根据主从节点当前状态的不同，可以分为全量复制和部分复制。
命令传播阶段：在这个阶段主节点将自己执行的写命令发送给从节点，从节点接收命令并执行，从而保证主从节点数据的一致性。

分布式锁

redlock算法：全名 Redis Distributed Lock，即使用redis实现的分布式锁。这个算法实现了多redis实例的情况，这样避免了单节点故障的情况并且在多节点的设计和崩溃中有着独到的设计。
使用场景：多个服务间保证同一时刻同一时间段内同一用户只能有一个请求（防止关键业务出现并发攻击）。
TTL：Time To Live。指 redis key 的过期时间或有效生存时间。
clock drift:时钟漂移；指两个电脑间时间流速基本相同的情况下，两个电脑（或两个进程间）时间的差值；如果电脑距离过远会造成时钟漂移值过大。
保证分布式锁的要求如下：
互斥：在任何时刻只能有一个client获得锁。
释放死锁：即使锁定资源的服务崩溃或者分区，也有可以释放锁。
容错性：只要多数（一半）redis节点在使用，client就可以获取到锁。

多节点的redlock算法：
1、获取当前时间戳。
2、client尝试按照顺序获取相同的key，value获取redis的锁。获取锁的过程中的时间比锁过期时间小很多。
3、client获取所有能获得锁的最后一个redis的时间减去第一个时间，这个时间差小于TTL时间b并且至少一半以上redis服务器获取成功才能真正获取到锁。
4、如果成功获取到锁，则锁的过期时间是 TTL减去第三步的时间差的时间。
5、client因为其他原因获取锁失败，就会解锁所有的redis实例。
这里多台redis服务器之间没有进行时钟同步，可以看成是同步算法。

基于故障转移实现的redis主从无法真正实现Redlock：redis的主从复制是基于异步复制完成的，在主redis失败还未复制到从节点，该锁就可以被其他client获取，导致互斥失效。
RedLock失败重试：当client不能获取锁时，会在随机时间后重试获取锁。并且在同一时刻并发的把set命令发送给所有redis实例。最后在锁使用完成后及时释放锁。
RedLock释放锁：由于释放锁的时候会判断该锁是否是自己设置的锁，所以释放锁时只需要向所有的redis实例发出释放锁的命令即可，不考虑是否成功释放锁。
RedLock性能及崩溃恢复的相关解决方法：启用AOF存储的话，由于AOF是按秒存储的，所以立即重启会丢失一秒的数据导致锁互斥失效。解决办法就是等待TTL时间后延时重启，但缺点就是在TTL时间内redis服务处于暂停状态。

Redis 锁主要利用 Redis 的 setnx 命令。加锁命令：SETNX key value。解锁命令：DEL key 或者使用lua脚本（先获取锁判断存在并且是自己设置的锁就删除，其他则跳过。）。锁超时：EXPIRE key timeout。
问题：
SETNX 和 EXPIRE 非原子性操作。 set resourceName value ex 5 nx
锁误解除。由于锁超时自动释放，导致线程A释放的是线程B获取到的锁。解决办法就是在释放锁的适合检查加锁的线程和释放锁的线程是否为同一个线程。
超时解锁导致并发。增加一个守护线程，在锁即将超时释放时再次更新锁的超时时间。或者锁的释放时间较大于线程A的使用时间。
不可重入。在本地的map中实现分布式锁，即存储锁的标识也存储锁的重入次数。

幂等性

接口幂等性就是用户对于同一操作发起的一次请求或者多次请求的结果是一致的，不会因为多次点击而产生了副作用。
实际场景：订单支付。
解决方案：在真正需要调用幂等性接口时，会首先去调用另外一个获取到一个token，也可以理解为请求唯一标识ID。然后客户端携带该请求标识ID再次去调用支付接口，接口在接收到对应的token之后，会去redis中查询是否存在对应的ID，存在即执行业务，不存在返回重复交易。如果业务途中交易失败，只需要客户端再次请求token，再次重试。
还有一种办法就是使用状态机来保证交易上的不可逆转。
redis中token过期或者丢失：让客户端重试。

一致性hash算法

一致性哈希算法主要是针对分布式缓存系统的算法，指的是通过一致性哈希把数据映射到0到2^32次方个哈希块的空间，形成一个哈希环。然后将数据key使用相同的Hash函数计算出哈希值，并确定在环上的位置，然后通过根据当前可用的redis实例的数量进行取模运算得到最终具体的redis实例。
一致性hash算法为什么空间范围是0到2^32区间？java中的int最大值刚好是2^32。int占据4个字节。
一致性hash算法特点：容错性（一台实例宕机不会影响到其他的实例）。可扩展性（可以在系统中增加实例，无影响）。
数据的倾斜问题：一致性hash算法在节点较少时，容易因为节点分布不均导致数据倾斜（多数请求打到同一台实例上）。解决办法就是根据实际节点复制虚拟节点这样可以解决实例节点少导致的数据倾斜问题。

集群

集群工作原理：
通过哈希的方式，将数据分片，每个节点均匀分存储一定哈希槽(哈希值)区间的数据，默认分配了16384（2^14）个槽位。每份数据分片会存储在多个互为主从的多节点上。数据写入先写主节点，再同步到从节点(支持配置为阻塞同步)。同一分片多个节点间的数据不保持一致性。读取数据时，当客户端操作的key没有分配在该节点上时，redis会返回转向指令，指向正确的节点。扩容时时需要把旧节点的数据迁移一部分到新节点。
在 redis cluster 架构下，每个 redis 要放开两个端口号，比如一个是 6379，另外一个就是加1w 的端口号，比如 16379。
其中16379 端口号是用来进行节点间通信的，也就是 cluster bus 的东西，cluster bus 的通信，用来进行故障检测、配置更新、故障转移授权。
cluster bus 用了另外一种二进制的协议，gossip 协议，用于节点间进行高效的数据交换，占用更少的网络带宽和处理时间。

关于为什么为16384（2^14）个槽位？redis主从节点之间交换的报文信息的报文头中会存储某个节点负责存储信息的槽位，该槽位使用bitmap（位图），每一个位代表一个槽，如果槽位过多就会导致报文头过大（2^14为2k）导致网络堵塞，另外槽位越少并且节点越少的情况下，bitmap的压缩率就高。

主备切换：主从同步数据有同步和异步两种方式。Redis 将指令记录在本地内存 buffer 中，然后异步将 buffer 中的指令同步到从节点，从节点一边执行同步的指令流来达到和主节点一致的状态，一边和主节点反馈数据同步情况。

集群脑裂：集群脑裂是因为网络问题，导致 Redis master 节点和 slave 节点和 sentinel 集群处于不同的网络分区。因为 sentinel 集群无法感知到 master 节点的存在，所以将 slave 节点提升为 master 节点，此时存在两个不同的 master 节点。当客户端连接不同的 master 节点时，两个客户端可以同时拥有同一把锁。

codis集群部署：

架构完全体

数据怕丢失 -> 持久化（RDB/AOF）
恢复时间久 -> 主从副本（副本随时可切）
故障手动切换慢 -> 哨兵集群（自动切换）
读存在压力 -> 扩容副本（读写分离）
写存在压力/容量瓶颈 -> 分片集群
分片集群社区方案 -> Twemproxy、Codis（Redis节点之间无通信，需要部署哨兵，可横向扩容）
分片集群官方方案 -> Redis Cluster（Redis节点之间Gossip协议，无需部署哨兵，可横向扩容）
业务侧升级困难 -> Proxy+Redis Cluster（不侵入业务侧）

缓存问题

缓存雪崩：由于原有的大量缓存失效，而新的缓存还未到达，就会导致原本查询缓存的请求全部去查询数据库，造成数据库短时的巨大压力，造成系统的崩溃。
设置缓存的过期时间加上随机值。二级缓存。
缓存穿透：用户在查询数据的时候，在缓存中没有找到，请求全部到达数据库中，导致数据库压力剧增。
缓存查询为空的结果，避免再次查询。
缓存击穿：某一时刻，大量请求同时查询一个 key，而此时这个 key 已经失效，这就会导致大量的请求都进入到数据库上，造成短时数据库压力剧增。
多个线程请求一个数据，可以使用互斥锁来锁住数据，其他线程等待。

缓存与数据库双写一致

更新数据库。删除缓存，删除成功则退出。若缓存删除失败，则将需要删除的 key 加入到队列中，提供重试机制。从队列中获取到需要删除的 key。重复删除操作。