Redis原理

Redis对象：

// src/redis.h
typedef struct redisObject {
    unsigned type:4;
    unsigned encoding:4;
    unsigned lru:24; /* lru time (relative to server.lruclock) */
    int refcount;  // see lifecycle below。 当为零时，对象被销毁，
    void *ptr;
} robj;

我们通过refcount的变化看看其生命周期。首先是来自client的请求（to args）：

  1. set 对Key和Value的refcount++

  2. get 对Key的refcount++，两条通道

    • freeClientArgv：refcount(key)--

    • sendApplytoClient：refcount(value)++, 待replyList处理时，refcount(value)--

因为redis的场景不会出现循环引用的情况，可以使用引用计数法进行GC

SDS

内部结构

Simple Dynamic String是Redis字符串的内部实现。相较于C语言的char*，支持了以下Feature:

  • 以O(1)的时间复杂度获取长度。

  • 支持\0 字符，以兼容二进制数据的保存（但是 SDS 为了兼容部分 C 语言标准库的函数， SDS 字符串结尾还是会加上 \0 字符）

  • 避免缓冲区溢出的风险。

Redis 一共设计了 5 种类型，分别是 sdshdr5、sdshdr8、sdshdr16、sdshdr32 和 sdshdr64。区别在于，它们数据结构中的 len 和 capacity 成员变量的数据类型（位数）不同，为了能灵活保存不同大小的字符串。

除了设计不同类型的结构体，Redis 在编程上还使用了专门的编译优化来节省内存空间，即在 struct 声明了 __attribute__ ((packed)) ，它的作用是：告诉编译器取消结构体在编译过程中的优化对齐，按照实际占用字节数进行紧凑对齐。

扩容规则

  • 如果所需的 sds 长度小于 1 MB，那么最后的扩容是按照翻倍扩容来执行的，即 2 倍的newlen

  • 如果所需的 sds 长度超过 1 MB，那么最后的扩容长度应该是 newlen + 1MB。

内部编码（encoding）

  1. int：如果一个字符串对象保存的是整数值，并且这个整数值可以用long类型来表示，那么字符串对象会将整数值保存在字符串对象结构的ptr属性里面（将void*转换成 long），并将字符串对象的编码设置为int。

  2. embstr：串长度不大于44（Redis5.0+），调用一次内存分配函数来分配一块连续的内存空间来保存redisObject和SDS。

  3. raw：串长度大于44；调用两次内存分配函数来分别分配两块空间来保存redisObject和SDS。

为什么是44B？因为按64B的单元，16B用于存储对象元信息，3B用于存储字符串元信息，最后还需要一个\0标识位。

embstr实际上是只读的，执行任何修改命令（如append）时，程序会先将对象的编码从embstr转换成raw，然后再执行修改。

字典

  • 哈希函数：默认的哈希函数是siphash，快且随机性好。

根据负载因子的值（哈希表已保存结点数量 / 哈希表大小）触发rehash：

  • 扩容机制：负载因子 >= 1时，就会开始扩容，新数组是原数组大小的 2 倍。如果正在bgsave（COW操作），尽量不去扩容，除非 hash 表已经非常满了（负载因子 >= 5）强制扩容。

  • 缩容机制：当 hash 表因为元素逐渐被删除变得越来越稀疏时（负载因子 < 0.1），进行缩容。不会考虑 Redis 是否正在做 bgsave 。

渐进式rehash机制：

  • 给「哈希表 2」 分配空间；

  • 在 rehash 进行期间，每次哈希表元素进行新增、删除、查找或者更新操作时，Redis 除了会执行对应的操作之外，还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上；

  • 随着处理客户端发起的哈希表操作请求数量越多，最终在某个时间点会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」，从而完成 rehash 操作。

快速列表

压缩列表

为了节约内存空间使用，Redis对象（List 对象、Hash 对象、Zset 对象）在包含的元素数量较少，或者元素值不大的情况才会使用压缩列表作为底层数据结构。压缩列表是一块连续的内存空间，元素之间紧接着存储，没有任何冗余空隙。

entry随着容纳的元素类型不同，也会有不同的结构：

连锁更新

插入一个新的元素就需要调用 realloc 扩展内存。空间扩展操作也就是重新分配内存，因此连锁更新一旦发生，就会导致压缩列表占用的内存空间要多次重新分配，这就会直接影响到压缩列表的访问性能。下图是连锁更新的例子：

quicklist 结构设计

通过控制每个链表节点中的压缩列表的大小或者元素个数，来规避连锁更新的问题。 因为压缩列表元素越少或越小，连锁更新带来的影响就越小，从而提供了更好的访问性能。为了进－步节约空间，还会对 ziplist 进行 LZF 算法压缩存储，可以选择压缩深度。

quicklist 内部默认单个 ziplist 长度为 8KB list-max-ziplist-size，默认的压缩深度是 0 list-compress-depth，也就是不压缩。为了支持快速 push/pop 操作，quicklist 的首尾两个 ziplist 不压缩，此时压缩深度就是1。如果压缩深度为 2，就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

listpack

quicklistNode 还是用了压缩列表来保存元素，还是存在连锁更新的问题。Redis 在 5.0 新设计一个数据结构叫 listpack，最大特点是每个节点不再包含前一个节点的长度了。结构如下：

此结构的逆序遍历也采用了新方式：从 tail 开始，取element-total-len，获取元素总长度elem-len，往前移到元素开头，重复此访问步骤。

整数集合

整数集合是 Set 对象的底层实现之一。当一个 Set 对象只包含整数值元素，并且元素数量不大时，就会使用整数集这个数据结构作为底层实现。

如果往一个已有3个int16整数集合INTSET_ENC_INT16中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，整数集合要进行升级操作。首先需要为 contents 数组扩容，在原本空间的大小之上再扩容多 80 位（4x32-3x16=80），这样就能保存下 4 个类型为 int32_t 的元素。

不支持降级操作.

跳表

zset 结构体里有两个数据结构：一个是跳表，一个是哈希表。这样的好处是既能进行高效的范围查询，也能进行高效单点查询。

内部实现

跳表节点是怎么实现多层级的呢? 每一层级可以包含多个节点，每一个节点通过指针连接起来，实现这一特性就是靠跳表节点结构体中的zskiplistLevel 结构体类型的 level 数组。

zset 对象要同时保存元素和元素的权重，对应到跳表节点结构里就是 sds 类型的 ele 变量和 double 类型的 score 变量。每个跳表节点都有一个后向指针（struct zskiplistNode* backward），指向前一个节点，目的是为了方便从跳表的尾节点开始访问节点，这样倒序查找时很方便。

跳表结构里包含了：

  • 跳表的头尾节点，便于在O(1)时间复杂度内访问跳表的头节点和尾节点；

  • 跳表的长度，便于在O(1)时间复杂度获取跳表节点的数量；

  • 跳表的最大层数，便于在O(1)时间复杂度获取跳表中层高最大的那个节点的层数量

查询与更新

Redis 跳表在创建节点时候，会生成范围为[0-1]的一个随机数，如果这个随机数小于 0.25（ZSKIPLIST_P，相当于概率 25%），那么层数就增加 1 层，然后继续生成下一个随机数，直到随机数的结果大于 0.25 结束，最终确定该节点的层数。 并没有严格维持相邻两层的节点数量比例为 2 : 1 的情况。

基数树

rax 是 Redis 内部比较特殊的一个数据结构，它是一个按Key有序字典树（基数树Radix Tree），支持快速地定位、插入和删除操作。个人理解为前缀树变种。

rax 被用在 Redis Stream 结构里面用于存储消息ID，在 Redis Cluster 中被用来记录槽位和 key 的对应关系slots_to_keys

节点
图示

压缩结构

非压缩结构

AE循环和命令处理

通过IO多路复用epoll监听fd： ReadQueryFromRequest -> fd -> query -> args -> process cmd -> AddReply -> sendReplyToClient

上一页Redis集群下一页计算机网络

最后更新于

这有帮助吗？