1.基本数据结构
1.string
命令
set key1 val1
//用来向一个key后添加，因此key支持动态扩展
append key1 m
结构
struct SDS<T> {
T capacity; // 数组容量
T len; // 数组长度
byte flags; // 特殊标识位，不理睬它
byte[] content; // 数组内容
}
类似java中的ArrayList，支持动态扩展。而且用了泛型，当字符串较短时，节省空间。
字符串大小在1M以内，每次扩容翻倍，否则每次增加1M
2.list
命令：
rpush books python java golang
lpop books
- 是列表不是数组
- 当列表弹出了最后一个元素之后，该数据结构自动被删除，内存被回收。
-
常用来做异步队列，一个线程塞进去任务，另一个线程轮询数据进行处理
结构：
quicklist图示
在ziplist内部连续存放数据
struct ziplist<T> {
int32 zlbytes; // 整个压缩列表占用字节数
int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
int16 zllength; // 元素个数
T[] entries; // 元素内容列表，挨个挨个紧凑存储
int8 zlend; // 标志压缩列表的结束，值恒为 0xFF
}
entry 块随着容纳的元素类型不同，也会有不一样的结构。
struct entry {
int<var> prevlen; // 前一个 entry 的字节长度
int<var> encoding; // 元素类型编码
optional byte[] content; // 元素内容
}
prevlen是前一个entry的长度，用户倒着遍历是定位前一个entry。如果entry小于254字节，prevlen用1个字节存储，否则用5个字节。如果 ziplist 里面每个 entry 恰好都存储了 253 字节的内容，那么第一个 entry 内容的修改就会导致后续所有 entry 的级联更新，这就是一个比较耗费计算资源的操作。
quicklist压缩深度：
默认压缩深度是0，如果两边第一个元素都不压缩，压缩深度是1。如果两边的第二个元素都不压缩，压缩深度是2。
3.hash
和HashMap的不同：
- key只能是字符串
- rehash的方式不一样。HashMap字典很大时，rehash很耗时。Redis不能阻塞，采用渐进式rehash。
- redis的dict存储了两个hashtable，分表存储旧的和新的hashtable,迁移时每次迁移一个桶，数据存在哪个桶不重要，如果旧hashtable没有，就从新hashtable中 找
- HashMap超过加载因子会扩容，而hash是当容量超过数组长度扩容为2倍，小于数组长度/10会缩容
4.set
用于存储中奖用户的id
命令：
5.zset
结构：
它类似于 Java 的 SortedSet 和 HashMap 的结合体，一方面它是一个 set，保证了内部 value 的唯一性，另一方面它可以给每个 value 赋予一个 score，代表这个 value 的排序权重。它的内部实现用的是一种叫着「跳跃列表」的数据结
应用：
zset 可以用来存粉丝列表，value 值是粉丝的用户 ID，score 是关注时间。我们可以对粉丝列表按关注时间进行排序。
zset 还可以用来存储学生的成绩，value 值是学生的 ID，score 是他的考试成绩。我们可以对成绩按分数进行排序就可以得到他的名次。
跳表：
要支持随机插入和删除，使用链表需要遍历
L0:100%元素都有
L1: 50%元素有
L2: 25%元素有
........
定位时先在顶层定位，再在低层定位
结构：
struct zslnode {
string value;
double score;
zslnode*[] forwards; // 多层连接指针
zslnode* backward; // 回溯指针
}
struct zsl {
zslnode* header; // 跳跃列表头指针
int maxLevel; // 跳跃列表当前的最高层
map<string, zslnode*> ht; // hash 结构的所有键值对
}
其中zslnode的结构如下：
2.基本数据结构相关问题
- 为什么跳表要用hash和跳表
用hash使得查找value的复杂度为O(1) 用跳表是因为hash是无序的，而执行zran zrange等需要有序 - 为什么用跳表不用红黑树
范围查询
3.分布式锁
- 定义
如果不设置过期时间由于进程崩了（顺便带走锁）可能导致死锁问题，如果不是原子操作，在setnx和ex之间由于断点也可能导致死锁。因此将setnx ex作为一个原子操作。 - 超时问题
如果锁过期了，任务没有执行完成，第二个线程在锁过期后拿到锁，而任务完成又会释放锁（删除），此时其他线程就可以在第二个线程没有执行结束前获取锁。解决方法是在value设置一个UUID，那么每次要删除锁时判断是否是当前线程加的锁，如果是再删除。这么做由于get和del不是原子操作，因此可以采用lua脚本。lua脚本可以通过一个指令将其完成。 - 集群问题
原先第一个客户端在主节点中申请成功了一把锁，但是这把锁还没有来得及同步到从节点，主节点突然挂掉了。然后从节点变成了主节点，这个新的节点内部没有这个锁，所以当另一个客户端过来请求加锁时，立即就批准了。这样就会导致系统中同样一把锁被两个客户端同时持有。
解决（RedLock）：
有多个独立的Redis实例（不是主从关系），获取锁需要向每个实例发送set，只有一半以上set成功，才会成功，释放锁时向所有实例发送del指令，性能会低一些。
4.过期数据的删除策略
- 定期删除（对内存好）
- 惰性删除（对CPU好）
- redis采用的：
将所有设置了过期时间的key放到一个字典里，然后
1、从过期字典中随机 20 个 key；
2、删除这 20 个 key 中已经过期的 key；
3、如果过期的 key 比率超过 1/4，那就重复步骤 1； - 从库不会进行过期扫描，从库对过期的处理是被动的。主库在 key 到期时，会在 AOF 文件里增加一条 del 指令，同步到所有的从库，从库通过执行这条 del 指令来删除过期的 key。
5.内存淘汰策略
volatile-lru
volatile-ttl
volatile-random
allkeys-lru
allkeys-random
4.0版本新增：
allkeys-lfu
volatile-lfu
6.持久化
快照（RDB）：
由于IO需要另外一个进程，因此父进程在处理客户端的请求的同时，fork出子进程，子进程和父进程共享数据段和代码段，当数据修改时，使用CopyOnWrite机制，父进程将数据复制一份并进行修改，而子进程只需要要序列化就可以了。
AOF:
先写将指令写到内核为文件描述符分配的内存缓存中，然后内核再异步将其写到磁盘，再执行指令。如果没来得及写磁盘就宕机了，可以使用glibc提供的fsync函数将指定文件内容强制从内核缓存刷到磁盘。
混合持久化：
先rdb，再aof
6.主从复制
出现分区时，不保证一致性，保证可用性，但保证最终一致性，
- 增量同步
redis将对自己产生状态变化的指令流放到一个buffer(环形数组)中，异步将里面的指令同步到从节点，从节点一边执行同步，一边告诉主节点同步到哪里。但如果网络状况不好，会将前面的指令覆盖。 - 快照同步
主节点将内存所有数据通过快照形式存到磁盘，再传给从节点，从节点先清空原来的内存，再加载，加载完继续增量同步。如果同步时又出现主节点的覆盖，将会导致死循环。
7.Sentinel
负责持续监控主从节点的健康，当主节点挂掉时，自动选择一个最优的从节点切换为主节点。客户端来连接集群时，会首先连接 sentinel，通过 sentinel 来查询主节点的地址，然后再去连接主节点进行数据交互。当主节点发生故障时，客户端会重新向 sentinel 要地址，sentinel 会将最新的主节点地址告诉客户端
8.Redis数据丢失问题
参考这里
9.Codis
- 用于支持多个Redis实例，当客户端向 Codis 发送指令时，Codis 负责将指令转发到后面的 Redis 实例来执行，并将返回结果再转回给客户端。使用多个Codis代理可用增加QPS
- 将所有key划分为1024个槽位（slot）,首先对客户端的key进行crc生成哈希值，再对1024求余，即槽位，每个槽位对应一个Redis实例（不同槽位可能对应一个相同的槽位），转发到对应实例。
- 不同Codis中的槽位和Redis实例的对应关系通过zookeeper维护
- 每增加一个Redis实例，会进行迁移，增加了slotsscan指令，可用通过槽位得到所有key，然后迁移。迁移时如果客户端的请求打在正在迁移的槽位上，立刻强制对当前的key进行迁移，迁移后旧Redis实例就不存在了，就可以响应客户端请求了。
- Codis会在空闲时自动均衡
- Codis不支持事务，不支持rename等某些命令，但提供了DashBoard方面对槽位和key进行管理
10.RedisCluster
- 由三个节点去中心化，每个节点负责一部分槽位。槽位信息存储在每个节点，也在客户端缓存。
- 客户端不需要经过代理，可以直接定位到目标节点。槽位信息在客户端和服务器可能不一致，由槽位信息校验纠正。
- 跳转
某个节点不存在响应key时，发送 减号表示不在当前节点，3999是对应的槽位号，后面是所在节点，客户端收到后去新的节点取，并更新槽位信息。
GET x
-MOVED 3999 127.0.0.1:6381
4.迁移
迁移工具redis-trib会在源节点使用dump指令得到序列号内容，通过向目标节点发送restore携带序列号内容，目标节点反序列化，返回源节点OK,源节点删除key
- 客户端请求key
- A 发送去B找
- 客户端给B发送asking（表示要下一个指令不能不理）
-
客户端发送get
asking使用的原因，如果向B发送请求，此时数据在传输中，B会响应客户端，去A找，因此形成重定向循环。
image.png - gossip协议
比如一个节点发现某个节点失联了 (PFail)，它会将这条信息向整个集群广播，其它节点也就可以收到这点失联信息。如果一个节点收到了某个节点失联的数量 (PFail Count) 已经达到了集群的大多数，就可以标记该节点为确定下线状态 (Fail)，然后向整个集群广播，强迫其它节点也接收该节点已经下线的事实，并立即对该失联节点进行主从切换。
