Redis原理

Posted on | In

数据结构

字符串

简单动态字符串（SDS），比起 C 字符串， SDS 具有以下优点：

  1. 常数复杂度O1获取字符串长度。
  2. 杜绝缓冲区溢出。
  3. 减少修改字符串长度时所需的内存重分配次数：空间预分配未使用空间，SDS修改后，长度少于1m酒会分配跟len相同大小的未使用空间，大于1m分配1m的未使用空间。
  4. 二进制安全。
  5. 兼容部分 C 字符串函数。

链表

  1. 每个链表节点由一个 listNode 结构来表示， 每个节点都有一个指向前置节点和后置节点的指针， 所以 Redis 的链表实现是双端链表。
  2. 每个链表使用一个 list 结构来表示， 这个结构带有表头节点指针、表尾节点指针、以及链表长度等信息。
  3. 因为链表表头节点的前置节点和表尾节点的后置节点都指向 NULL ， 所以 Redis 的链表实现是无环链表。
  4. 通过为链表设置不同的类型特定函数， Redis 的链表可以用于保存各种不同类型的值。

字典

  1. Redis 中的字典使用哈希表作为底层实现， 每个字典带有两个哈希表， 一个用于平时使用， 另一个仅在进行 rehash 时使用。
  2. 当字典被用作数据库的底层实现， 或者哈希键的底层实现时， Redis 使用 MurmurHash2 算法来计算键的哈希值。
  3. 哈希表使用链地址法来解决键冲突， 被分配到同一个索引上的多个键值对会连接成一个单向链表。
  4. 在对哈希表进行扩展或者收缩操作时， 程序需要将现有哈希表包含的所有键值对 rehash 到新哈希表里面， 并且这个 rehash 过程并不是一次性地完成的， 而是渐进式地完成的。
  5. 负载因子 ＝哈希表已保存节点数量 / 哈希表大小
  6. 索引值计算
  • 使用字典设置的哈希函数，计算键 key 的哈希值
    hash = dict->type->hashFunction(key);
  • 使用哈希表的 sizemask 属性和哈希值，计算出索引值
  • 根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]
    index = hash & dict->ht[x].sizemask;

跳跃表

  1. 跳跃表是有序集合的底层实现之一， 除此之外它在 Redis 中没有其他应用。
  2. Redis 的跳跃表实现由 zskiplist 和 zskiplistNode 两个结构组成， 其中 zskiplist 用于保存跳跃表信息（比如表头节点、表尾节点、长度）， 而 zskiplistNode 则用于表示跳跃表节点。
  3. 每个跳跃表节点的层高都是 1 至 32 之间的随机数。
  4. 在同一个跳跃表中， 多个节点可以包含相同的分值， 但每个节点的成员对象必须是唯一的。
  5. 跳跃表中的节点按照分值大小进行排序， 当分值相同时， 节点按照成员对象的大小进行排序。

整数集合

  1. 整数集合是集合键的底层实现之一。
  2. 整数集合的底层实现为数组， 这个数组以有序、无重复的方式保存集合元素， 在有需要时， 程序会根据新添加元素的类型， 改变这个数组的类型。
  3. 升级操作为整数集合带来了操作上的灵活性， 并且尽可能地节约了内存。
  4. 整数集合只支持升级操作， 不支持降级操作。

压缩列表

  1. 压缩列表是一种为节约内存而开发的顺序型数据结构。
  2. 压缩列表被用作列表键和哈希键的底层实现之一。
  3. 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值。
  4. 添加新节点到压缩列表， 或者从压缩列表中删除节点， 可能会引发连锁更新操作， 但这种操作出现的几率并不高。

quicklist(v3.2新增）

  1. 由ziplist组成的双向链表，链表中的每一个节点都以压缩列表ziplist的结构保存着数据，而ziplist有多个entry节点，保存着数据。
  2. quicklist宏观上是一个双向链表，因此，它具有一个双向链表的有点，进行插入或删除操作时非常方便，虽然复杂度为O(n)，但是不需要内存的复制，提高了效率，而且访问两端元素复杂度为O(1)。
  3. quicklist微观上是一片片entry节点，每一片entry节点内存连续且顺序存储，可以通过二分查找以 log2(n)log2(n)的复杂度进行定位

编码

  1. 字符串对象的编码可以是int、raw、embstr
  2. 列表对象的编码可以是ziplist、linkedlist（quick list？）
  3. 哈希对象的编码可以是ziplist、hashtable
  4. 集合对象的编码可以是intset（整数集合）、hashtable
  5. 有序集合的编码可以是ziplist、skiplist

内存

  1. c语言不具备自动内存回收，redis构建了引用技术实现
  2. 只对包含整数值字符串对象进行内存共享：1. 将数据库键值的值指针指向一个现有的值对象。2. 将被共享的值对象引用计数增加一
  3. redis在服务器初始化时，创建0到9999一万个字符串对象
  4. 空转时长：对象记录了最后一次被访问时间

数据库

  1. 初始化服务时候，根据dbnum（可配默认16）创建数据库
  2. 键空间（字典）：保存了所有键值对
  3. 命中次数（keyspace_hits) 不命中次数(keyspace_misses) ，INFO stats命令查看
  4. 过期字典：保存了所有键的过期时间（毫秒级时间戳）
  5. persist 实际是把键从过期字典中删除
  6. 过期删除策略：惰性删除（所有命令操作键时进行检查）＋定期删除（定期从一定数量数据库取一定数量随机键检查并删除过期键）
  7. RDB持久化（在指定的时间间隔内，执行指定次数的写操作，则会将内存中的数据写入到磁盘中），生成RDB文件时已过期键不会保存，载入RDB文件时，主服务器模式运行时，过期键将被忽略，从服务器模式运行时会载入所有键，但在主从同步时过期键将被删除。
  8. AOF持久化（采用日志的形式来记录每个写操作，并追加到文件中。Redis 重启的会根据日志文件的内容将写指令从前到后执行一次以完成数据的恢复工作），当过期键被删除的时候，向AOF文件追加一条DEL命令。AOF重写时，过期键被检查而不会保存到AOF文件。
  9. 数据库通知功能（notifyKeyspaceEvent)

持久化

RDB持久化

  1. 生成RDB文件命令：SAVE，阻赛Redis服务器进程，直到RDB文件创建完毕为止。BGSAVE，派生出一个子进程，由子进程负责生成RDB文件，服务器主进程基础处理命令请求。
  2. serverCron默认每隔100ms执行检查save选项保存条件（dirty,lastsave)是否满足，如满足执行BGSAVE

AOF持久化

  1. appendfsync选项。安全性always>every sec>no。 效率no>everysec>always

事件

  1. redis是事件驱动程序，服务器处理事件分为时间事件、文件事件
  2. 文件事件是对套接字操作的抽奖
  3. 服务器在一半情况下只执行serverCron函数一个时间事件
  4. 因为事件循环，时间事件的实际处理事件会比设定时间晚一些

客户端

  1. 服务器状态结构使用 clients 链表连接起多个客户端状态，新添加的客户端状态会被放到链表的末尾。
  2. 客户端状态的 flags 属性使用不同标志来表示客户端的角色， 以及客户端当前所处的状态。
  3. 输入缓冲区记录了客户端发送的命令请求， 这个缓冲区的大小不能超过 1 GB 。
  4. 命令的参数和参数个数会被记录在客户端状态的 argv 和 argc 属性里面， 而 cmd 属性则记录了客户端要执行命令的实现函数。
  5. 客户端有固定大小缓冲区和可变大小缓冲区两种缓冲区可用， 其中固定大小缓冲区的最大大小为 16 KB ， 而可变大小缓冲区的最大大小不能超过服务器设置的硬性限制值。
  6. 输出缓冲区限制值有两种， 如果输出缓冲区的大小超过了服务器设置的硬性限制， 那么客户端会被立即关闭； 除此之外， 如果客户端在一定时间内， 一直超过服务器设置的软性限制， 那么客户端也会被关闭。
  7. 当一个客户端通过网络连接连上服务器时， 服务器会为这个客户端创建相应的客户端状态。 网络连接关闭、 发送了不合协议格式的命令请求、 成为 CLIENT_KILL 命令的目标、 空转时间超时、 输出缓冲区的大小超出限制， 以上这些原因都会造成客户端被关闭。
  8. 处理 Lua 脚本的伪客户端在服务器初始化时创建， 这个客户端会一直存在， 直到服务器关闭。
  9. 载入 AOF 文件时使用的伪客户端在载入工作开始时动态创建， 载入工作完毕之后关闭。

服务端

  1. 一个命令请求从发送到完成主要包括以下步骤：
    • 客户端将命令请求发送给服务器；
    • 服务器读取命令请求，并分析出命令参数；
    • 命令执行器根据参数查找命令的实现函数，然后执行实现函数并得出命令回复；
    • 服务器将命令回复返回给客户端。
  2. serverCron 函数默认每隔 100 毫秒执行一次， 它的工作主要包括更新服务器状态信息， 处理服务器接收的 SIGTERM 信号， 管理客户端资源和数据库状态， 检查并执行持久化操作， 等等。
  3. 服务器从启动到能够处理客户端的命令请求需要执行以下步骤：
    • 初始化服务器状态；
    • 载入服务器配置；
    • 初始化服务器数据结构；
    • 还原数据库状态；
    • 执行事件循环。

复制

  1. 部分重同步通过复制偏移量、复制积压缓冲区、服务器运行 ID 三个部分来实现。
  2. 在复制操作刚开始的时候， 从服务器会成为主服务器的客户端， 并通过向主服务器发送命令请求来执行复制步骤， 而在复制操作的后期， 主从服务器会互相成为对方的客户端。
  3. 主服务器通过向从服务器传播命令来更新从服务器的状态， 保持主从服务器一致， 而从服务器则通过向主服务器发送命令(REPLACONFACK)来进行心跳检测， 以及命令丢失检测。

Sentinel

  1. 一个运行在特殊模式下的 Redis 服务器， 它使用了和普通模式不同的命令表， 所以 Sentinel 模式能够使用的命令和普通 Redis 服务器能够使用的命令不同。
  2. Sentinel 会读入用户指定的配置文件， 为每个要被监视的主服务器创建相应的实例结构， 并创建连向主服务器的命令连接和订阅连接， 其中命令连接用于向主服务器发送命令请求， 而订阅连接则用于接收指定频道的消息。
  3. Sentinel 通过向主服务器发送 INFO 命令来获得主服务器属下所有从服务器的地址信息， 并为这些从服务器创建相应的实例结构， 以及连向这些从服务器的命令连接和订阅连接。
  4. 在一般情况下， Sentinel 以每十秒一次的频率向被监视的主服务器和从服务器发送 INFO 命令， 当主服务器处于下线状态， 或者 Sentinel 正在对主服务器进行故障转移操作时， Sentinel 向从服务器发送 INFO 命令的频率会改为每秒一次。
  5. 对于监视同一个主服务器和从服务器的多个 Sentinel 来说， 它们会以每两秒一次的频率， 通过向被监视服务器的 sentinel:hello 频道发送消息来向其他 Sentinel 宣告自己的存在。
  6. 每个 Sentinel 也会从 sentinel:hello 频道中接收其他 Sentinel 发来的信息， 并根据这些信息为其他 Sentinel 创建相应的实例结构， 以及命令连接。
  7. Sentinel 只会与主服务器和从服务器创建命令连接和订阅连接， Sentinel 与 Sentinel 之间则只创建命令连接。
  8. Sentinel 以每秒一次的频率向实例（包括主服务器、从服务器、其他 Sentinel）发送 PING 命令， 并根据实例对 PING 命令的回复来判断实例是否在线： 当一个实例在指定的时长中连续向 Sentinel 发送无效回复时， Sentinel 会将这个实例判断为主观下线。
  9. 当 Sentinel 将一个主服务器判断为主观下线时， 它会向同样监视这个主服务器的其他 Sentinel 进行询问， 看它们是否同意这个主服务器已经进入主观下线状态。
  10. 当 Sentinel 收集到足够多的主观下线投票之后， 它会将主服务器判断为客观下线， 并发起一次针对主服务器的故障转移操作。
  11. 相似RAFT算法选取领头Sentinel

集群

  1. 节点通过握手来将其他节点添加到自己所处的集群当中。
  2. 集群中的 16384 个槽可以分别指派给集群中的各个节点， 每个节点都会记录哪些槽指派给了自己， 而哪些槽又被指派给了其他节点。
  3. 节点在接到一个命令请求时， 会先检查这个命令请求要处理的键所在的槽是否由自己负责， 如果不是的话， 节点将向客户端返回一个 MOVED 错误， MOVED 错误携带的信息可以指引客户端转向至正在负责相关槽的节点。
  4. 对 Redis 集群的重新分片工作是由客户端执行的， 重新分片的关键是将属于某个槽的所有键值对从一个节点转移至另一个节点。
  5. 如果节点 A 正在迁移槽 i 至节点 B ， 那么当节点 A 没能在自己的数据库中找到命令指定的数据库键时， 节点 A 会向客户端返回一个 ASK 错误， 指引客户端到节点 B 继续查找指定的数据库键。
  6. MOVED 错误表示槽的负责权已经从一个节点转移到了另一个节点， 而 ASK 错误只是两个节点在迁移槽的过程中使用的一种临时措施。
  7. 集群里的从节点用于复制主节点， 并在主节点下线时， 代替主节点继续处理命令请求。
  8. 集群中的节点通过发送和接收消息来进行通讯， 常见的消息包括 MEET 、 PING 、 PONG 、 PUBLISH 、 FAIL 五种。

发布订阅模式

  1. 服务器状态在 pubsub_channels 字典保存了所有频道的订阅关系： SUBSCRIBE 命令负责将客户端和被订阅的频道关联到这个字典里面， 而 UNSUBSCRIBE 命令则负责解除客户端和被退订频道之间的关联。
  2. 服务器状态在 pubsub_patterns 链表保存了所有模式的订阅关系： PSUBSCRIBE 命令负责将客户端和被订阅的模式记录到这个链表中， 而 UNSUBSCRIBE 命令则负责移除客户端和被退订模式在链表中的记录。
  3. PUBLISH 命令通过访问 pubsub_channels 字典来向频道的所有订阅者发送消息， 通过访问 pubsub_patterns 链表来向所有匹配频道的模式的订阅者发送消息。
  4. PUBSUB 命令的三个子命令都是通过读取 pubsub_channels 字典和 pubsub_patterns 链表中的信息来实现的。

事务

  1. 事务提供了一种将多个命令打包， 然后一次性、有序地执行的机制。
  2. 多个命令会被入队到事务队列中， 然后按先进先出（FIFO）的顺序执行。
  3. 事务在执行过程中不会被中断， 当事务队列中的所有命令都被执行完毕之后， 事务才会结束。
  4. 带有 WATCH 命令的事务会将客户端和被监视的键在数据库的 watched_keys 字典中进行关联， 当键被修改时， 程序会将所有监视被修改键的客户端的 REDIS_DIRTY_CAS 标志打开。
  5. 只有在客户端的 REDIS_DIRTY_CAS 标志未被打开时， 服务器才会执行客户端提交的事务， 否则的话， 服务器将拒绝执行客户端提交的事务。
  6. Redis 的事务总是保证 ACID 中的原子性、一致性和隔离性， 当服务器运行在 AOF 持久化模式下， 并且 appendfsync 选项的值为 always 时， 事务也具有耐久性。
  7. Redis事务不支持事务回滚机制，即使实行期间出现了错误也会全部执行所有命令。

排序

  1. SORT 命令通过将被排序键包含的元素载入到数组里面， 然后对数组进行排序来完成对键进行排序的工作。
  2. 在默认情况下， SORT 命令假设被排序键包含的都是数字值， 并且以数字值的方式来进行排序。
  3. 如果 SORT 命令使用了 ALPHA 选项， 那么 SORT 命令假设被排序键包含的都是字符串值， 并且以字符串的方式来进行排序。
  4. SORT 命令的排序操作由快速排序算法实现。
  5. SORT 命令会根据用户是否使用了 DESC 选项来决定是使用升序对比还是降序对比来比较被排序的元素
  6. 当 SORT 命令使用了 BY 选项时， 命令使用其他键的值作为权重来进行排序操作。
  7. 当 SORT 命令使用了 LIMIT 选项时， 命令只保留排序结果集中 LIMIT 选项指定的元素。
  8. 当 SORT 命令使用了 GET 选项时， 命令会根据排序结果集中的元素， 以及 GET 选项给定的模式， 查找并返回其他键的值， 而不是返回被排序的元素。
  9. 当 SORT 命令使用了 STORE 选项时， 命令会将排序结果集保存在指定的键里面。
  10. 当 SORT 命令同时使用多个选项时， 命令先执行排序操作（可用的选项为 ALPHA 、 ASC 或 DESC 、 BY ）， 然后执行 LIMIT 选项， 之后执行 GET 选项， 再之后执行 STORE 选项， 最后才将排序结果集返回给客户端。
  11. 除了 GET 选项之外， 调整选项的摆放位置不会影响 SORT 命令的排序结果。

二进制位数组

  1. Redis 使用 SDS 来保存位数组。
  2. SDS 使用逆序来保存位数组， 这种保存顺序简化了 SETBIT 命令的实现， 使得 SETBIT 命令可以在不移动现有二进制位的情况下， 对位数组进行空间扩展。
  3. BITCOUNT 命令使用了查表算法和 variable-precision SWAR 算法来优化命令的执行效率。
  4. BITOP 命令的所有操作都使用 C 语言内置的位操作来实现。

慢日志

  1. Redis 的慢查询日志功能用于记录执行时间超过指定时长的命令。
  2. Redis 服务器将所有的慢查询日志保存在服务器状态的 slowlog 链表中， 每个链表节点都包含一个 slowlogEntry 结构， 每个 slowlogEntry 结构代表一条慢查询日志。
  3. 打印和删除慢查询日志可以通过遍历 slowlog 链表来完成。
  4. slowlog 链表的长度就是服务器所保存慢查询日志的数量。
  5. 新的慢查询日志会被添加到 slowlog 链表的表头， 如果日志的数量超过 slowlog-max-len 选项的值， 那么多出来的日志会被删除。

监视器

  1. 客户端可以通过执行 MONITOR 命令， 将客户端转换成监视器， 接收并打印服务器处理的每个命令请求的相关信息。
  2. 当一个客户端从普通客户端变为监视器时， 该客户端的 REDIS_MONITOR 标识会被打开。
  3. 服务器将所有监视器都记录在 monitors 链表中。
  4. 每次处理命令请求时， 服务器都会遍历 monitors 链表， 将相关信息发送给监视器。

LUA

好处

  1. ［原子操作］lua脚本式在redis中原子执行的，在执行过程中不会插入其他命令
  2. ［可复用］lua脚本可以帮助开发和运维人员创造出自己定制的命令，并可以将这些命令常驻在Redis内存中，实现复用的效果。
  3. ［高性能］lua脚本可以将多条命令一次性打包，有效的减少网络开销。

要点：

  1. Redis 服务器在启动时， 会对内嵌的 Lua 环境执行一系列修改操作， 从而确保内嵌的 Lua 环境可以满足 Redis 在功能性、安全性等方面的需要。
  2. Redis 服务器专门使用一个伪客户端来执行 Lua 脚本中包含的 Redis 命令。
  3. Redis 使用脚本字典来保存所有被 EVAL 命令执行过， 或者被 SCRIPT_LOAD 命令载入过的 Lua 脚本， 这些脚本可以用于实现 SCRIPT_EXISTS 命令， 以及实现脚本复制功能。
  4. EVAL 命令为客户端输入的脚本在 Lua 环境中定义一个函数， 并通过调用这个函数来执行脚本。
  5. EVALSHA 命令通过直接调用 Lua 环境中已定义的函数来执行脚本。
  6. SCRIPT_FLUSH 命令会清空服务器 lua_scripts 字典中保存的脚本， 并重置 Lua 环境。
  7. SCRIPT_EXISTS 命令接受一个或多个 SHA1 校验和为参数， 并通过检查 lua_scripts 字典来确认校验和对应的脚本是否存在。
  8. SCRIPT_LOAD 命令接受一个 Lua 脚本为参数， 为该脚本在 Lua 环境中创建函数， 并将脚本保存到 lua_scripts 字典中。
  9. 服务器在执行脚本之前， 会为 Lua 环境设置一个超时处理钩子， 当脚本出现超时运行情况时， 客户端可以通过向服务器发送 SCRIPT_KILL 命令来让钩子停止正在执行的脚本， 或者发送 SHUTDOWN nosave 命令来让钩子关闭整个服务器。
  10. 主服务器复制 EVAL 、 SCRIPT_FLUSH 、 SCRIPT_LOAD 三个命令的方法和复制普通 Redis 命令一样 —— 只要将相同的命令传播给从服务器就可以了。
  11. 主服务器在复制 EVALSHA 命令时， 必须确保所有从服务器都已经载入了 EVALSHA 命令指定的 SHA1 校验和所对应的 Lua 脚本， 如果不能确保这一点的话， 主服务器会将 EVALSHA 命令转换成等效的 EVAL 命令， 并通过传播 EVAL 命令来获得相同的脚本执行效果。

Redis与MC对比

对比
why redis

参考：
Redis 设计与实现（第一版）