参考文档：redis设计与实现读书笔记 第二版

一、数据结构和对象

1.关于字符串

redis底层存储字符串结构为SDS结构

image.png

分别有free，空余多少长度，len占用多少长度，buf，实际的字符串，自动以'\0'结尾
和C语言的字符串实现相比，有以下优点

• 减轻了统计长度复杂度，从O(N)变为O(1)
• 减少修改字符串带来的内存重分配次数
  redis的使用场景，可能会有大量修改操作，重新分配内存代价比较大，因此有通过空间预分配，free字段进行优化

1.关于链表

链表提供了高效的节点重排能力， 以及顺序性的节点访问方式， 并且可以通过增删节点来灵活地调整链表的长度

image.png

这里普通双端的listNode自不用多说，关键是list结构，是为了2个功能：
通过 list 结构的 head 指针和 tail 指针， 程序获取链表的表头节点和表尾节点的复杂度为 O(1)
程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数， 程序获取链表中节点数量的复杂度为 O(1)

2.关于字典

字典， 又称符号表（symbol table）、关联数组（associative array）或者映射（map）， 是一种用于保存键值对（key-value pair）的抽象数据结构。而Redis 的数据库就是使用字典来作为底层实现的
关于字典的实现
Redis 的字典使用哈希表作为底层实现， 解决键冲突的方法为链地址法（seperate chaining）,就是数组+链的方式

关于哈希表resize的实现

image.png

• 注意点，redis为了避免rehash时数据过大，造成服务中断 。这个 rehash 动作并不是一次性、集中式地完成的， 而是分多次、渐进式地完成的。
  以下是哈希表渐进式 rehash 的详细步骤：

1.为 ht[1] 分配空间， 让字典同时持有 ht[0] 和 ht[1] 两个哈希表。
2.在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3.在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht[0] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht[1] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
4.随着字典操作的不断执行， 最终在某个时间点上， ht[0] 的所有键值对都会被 rehash 至 ht[1] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。
在进行渐进式 rehash 的过程中， 字典会同时使用 ht[0] 和 ht[1] 两个哈希表， 所以在渐进式 rehash 进行期间， 字典的删除（delete）、查找（find）、更新（update）等操作会在两个哈希表上进行： 比如说， 要在字典里面查找一个键的话， 程序会先在 ht[0] 里面进行查找， 如果没找到的话， 就会继续到 ht[1] 里面进行查找， 诸如此类。

3.跳跃表

跳跃表（skiplist）是一种有序数据结构， 它通过在每个节点中维持多个指向其他节点的指针， 从而达到快速访问节点的目的。
参考文档：https://www.jianshu.com/writer#/notebooks/40650988/notes/57616632
跳跃表的实现中可以看出，跳跃表实现的基础是有序且key不重复，，那自然是sorted set的底层实现

4.其他

底层还有整数集合，压缩列表等
简单的提一句，压缩列表是redis的一种优化，当数据少，数据字段长度短的时候会使用压缩列表
整数集合是当集合元素全是整数值，且元素数量不多时的底层结构

二、对象

以上我们介绍了 Redis 用到的所有主要底层数据结构， 比如简单动态字符串（SDS）、双端链表、字典、压缩列表、整数集合， 等等。

Redis 并没有直接使用这些数据结构来实现键值对数据库， 而是基于这些数据结构创建了一个对象系统，在实际的使用中，我们适合包装好的对象打交道的
对象包括
1.字符串对象
2.列表对象
3.哈希对象
4.集合对象
5.有序集合对象

2.1 字符串对象

字符串对象，首先要和之前底层数据结构里的字符串区分开
redis里的字符串对象，包含了int，raw和embstr。即这个对象会根据实际值的不同，选择底层结构，如果是数字，可能就是int了，如果是字符串，会根据长度选择raw和embstr。

2.2 列表对象

列表对象的底层是ziplist（压缩列表）或者linkedlist

2.3 哈希对象

哈希对象的底层是ziplist或者hashtable
hashtable表示哈希对象很容易理解，KV的键值对，map很适合。那么压缩列表是如何表示的？
它将key和value统一作为元素，压到列表队尾，key在前，value在后。同一个键值对，总是紧挨在一起

2.4 集合对象

集合的底层实现是整数集合和hashtable

2.5 有序集合对象

底层实现是ziplist或者skiplist
注意，这里分值才是真正按序排列的key，value是存储的object

2.6对象的其他

• redis是用 C写的，C没有内存回收，因此redis采用了引用计数器的方式，判断是否回收对象。

• redis对于整形的字符串对象会默认对象共享，这是为了节省内存

• redisObject 结构包含的最后一个属性为 lru 属性，该属性记录了对象最后一次被命令程序访问的时间。这样，通过当前时间减去lru时间，就得到了改建的空转时长，这个值可以用于redis的内存满了后的清理策略

2.7 redis对象的重要属性

image.png

三、单机数据库的实现

3.1.数据库

redis的键空间是一个字典，所有的操作其实都是通过对键空间字典进行操作来实现的。

比如我们插入一个字符串对象，实际上就是在键空间里插入了一个键，他的值就是字符串对象。

3.2 redis如何实现expire

redisDB中有一个过期时间字典，相对于键空间保存所有数据库的键值对，过期字典保存了数据库键的过期时间，格式是unix时间戳

这样，当你查询键的存活时间时，你可以通过当前时间减过期时间戳，得到存活时间

tip：redis原生只有setex字符串对象，才能将set和expire作为一个命令输入，如果是其他对象类型，有事务性要求，是需要手动写事务的

• 过期key的删除策略
  主动策略有2中：1.定时删除（每个key一个定时器任务，对cpu最不友好），定期删除（服务器定时任务），redis默认配置10hz，即每秒查10次。限制了频率和单次时长来减小cpu时间的影响
  被动策略：惰性删除（访问key时检查）
  首先要确认一点：不同的删除策略是cpu资源和内存资源的抉择平衡，redis采用的删除策略是 定期删除和惰性删除相结合

• AOF,RDB,复制对于过期键的处理
  1.生成RDB文件，是会过滤到过期的键的
  2.载入RDB文件，主服务器载入RDB文件时，是会检查过期的，保证载入的都没过期。但从服务器模式启动时，是不会检查的。
  3.AOF模式，当键已经过期，但主动和被动删除都没被触发时，AOF文件不会管过期。只有当主动或被动删除触发时，才会显示添加del命令
  4.AOF重写，重启的时候，会对过期的进行检查，过期的会被忽略
  5.复制，我们知道从服务器的键状态是由主服务器控制的。这意味着，只有主上删除了，发送del命令同步给从，从才会删除。
  tip：当主服务器上没有删除键，从收到了读的请求，是会正常返回的，使用读写分离的时候，如果大规模的key同时失效，同步不及时，也容易导致这个问题。

3.事件

提取到文章https://www.jianshu.com/writer#/notebooks/22084004/notes/57731622

4.客户端和服务端

redis服务端用redisClient结构保存了客户端的各类信息：包括客户端的输入缓冲区和输出缓冲区 querybuf

三、多机数据库

1.复制，主从结构

redis 2.8以前的复制，由2个步骤 1.初始的同步 2.命令传播
存在问题：同步时出现主从 断线，需要重新发送同步sync信号，非常消耗性能

redis2.8以后新版复制
采用命令psync，有2种模式 完整重同步和部分重同步
部分重同步时通过，主从都维护一个复制偏移量、有复制缓冲区保持持续更新

2.哨兵

sentinal 本质上是运行在特殊模式下的redis

Sentinel 状态中的masters字典记录了所有被Sentinel监视的主服务器相关信息。字典的key是主服务名字，字典的value则是主服务器对应的实例结构（包括主服务器，从服务器，或者另外一个Sentinel）

• Sentinel如何获得服务器的信息
  Sentinel通过配置监视的主服务器，info命令获得相关从服务器的信息，包括tp，端口等
  Sentinel是通过订阅模式获得信息的，有一个专门的 sentinel：hello的频道，通过订阅这个频道，可以知道其他sentinel的信息。从而使得监视同一个主服务器的多个Sentinel可以走动发现对方。发现后就可以互相创建命令连接

• 故障转移
  当有问题发生时，首先Sentinel进行主观下线和客观下线的判断（区别在于主管是自己认为的，客观是达到了认同下线的最小赞同数量）。第一步要进行Sentinel头领的选举，选举成功后，由Sentinel的首领对redis进行故障转移，包括但不仅仅是各个从服务器的选举，更新各个字典，修改复制目标等工作

3.集群

由于redis集群功能在版本3上才支持，且不怎么推荐，不做深入了解

四、独立功能的实现

1.事务 transaction

redis的事务是如何完成的，因为redis的单线程模型，使得redis的事务执行逻辑就非常简单的，不用考虑并发问题。

实现原理
主要包含3个步骤 1.事务开始 2.命令入队 3.事务执行

image.png

我们类比于数据库等，可以知道，事务是针对某一个客户端连接而言的，客户端的链接有一个客户端状态，里面包含了事务状态。
1.开始事务
multi
这标志着事务开始，将客户端从非事务状态转变为事务状态。

2.命令入队
redis服务器有一个事务队列，按照FIFO的策略写入命令

3.执行事务
exec
服务器遍历事务队列的每个项，读取并执行，最后从事务状态转变为非事务状态，返回回复
这就起到了事务的功能

watch命令
redis单线程执行保证了事务真正执行的时候是事物的。
但可能某些人，是想保证，从事务开始到执行完毕的数据有没有被修改过，尽管我想不出有什么场景。但redis仍然提供了watch机制帮助你。

• redis库有一个watch_keys字典，所有被watch命令监听的key都会放在里面，它对应的值，是一个链表，链表里存的是一个个客户端。

  
  
  image.png
  
  

  当数据库对监听的key进行修改后，redis会打开客户端连接的redis_dirty_cas标志，表示客户端事务的安全性已被破坏，服务器在执行事务时会拒绝客户端提交的事务

ACID特性
当我们评价某一个数据库的事务时，都是拿其中的ACID属性去评价。

• 原子性，普通的事务都有原子性，要么全部成功，要么全部失败。但redis不支持事务回滚，如果事务当中有个命令错误时，之前成功执行的语句是不会回滚的，并会继续执行接下去的语句。redis作者认为，命令错误肯定能在开发环境发现，不需要那么复杂的机制
• 一致性:错误命令后，不会回滚，想想就知道一致性是很弱的
• 持久化：RDB或者AOF
• 隔离性：单线程天生就没有并发问题

2.lua脚本

redis服务器创建了lua脚本的执行环境，通过一个伪客户端和redis进行操作

3.慢查询日志

slowlog-log-slower-than，超过多少微妙的请求记录会被记录到日志上，此功能可以用于分析查询语句的问题
慢查询只记录命令执行时间，并不包含命令排队和网络传输的时间。默认超过10ms，如果是高QPS场景，建议设置为1ms，1ms单机才1000QPS

4.地址位置

redis在3.2版本支持了地理GEO信息，使用hash字符串，实现常见的地理信息功能

5.redis cluster

数据分区是分布式存储的核心，理解了数据如何分区，其他的操作本质上是为了实现这个功能及其相关的功能

redis3.0 集群主要有3个步骤1.准备节点以集群方式启动 2.节点握手 3.分配槽

redis集群节点的请求路由：当节点收到属于自己slot的请求，直接返回，如果不是自己节点的，会计算出正确的节点，然后发给客户端重定向命令，让客户端再请求一次。（无法在客户端进行，因为只有服务端是集群状态，可以实时了解哪个slot分配在哪个节点。

• 由于有重定向，可以看出效率很低，在大多数情况下，都要增加一次IO开销

• 如何实现优化呢
  1.就是计算hash对应slot的关系，可以指定hash的范围，用{}内的数据进行计算，这样就可以实现同一项业务都到同一个slot了。批操作在集群模式下只有在同一个节点才可以进行

2.smart客户端
在客户端内部维护 slot-节点的映射表，如果出错，就随机找一个活跃节点连接，重新更新映射表