Chanler

Redis 底层 C 语言

数据结构#

动态字符串 SDS#

Redis 并没有使用 C 语言的 String，因为它实际上是字符数组

例子:
char* s="hello" 为 {'h', 'e', 'l', 'l', 'o', '\0'}

所以 Redis 构建了一种新的字符串结构，称为简单动态字符串 Simple Dynamic String，简称 SDS

这里读取不根据 '\0' 只是为了符合 C 语言，实际用的是 len

小于 1M 时快速增加分配内存，之后 1M 为间隔申请，注申请内存消耗十分大

二进制安全是指根据 len 读取，不会因为中间出现 '\0' 而突然停止

IntSet#

IntSet 是 Redis 中 set 集合的一种实现方式，基于整数数组实现，长度可变、有序等特征

encoding 决定每个元素占据的大小，此处 16 位 即 2 字节，length 决定数组内存储元素个数

假如是 16 的编码方式，却加入了一个超过编码方式的元素，则倒序拷贝元素到正确位置（倒序是为了不覆盖），然后添加新元素，最后修改 Hearder 中的 encoding、length

IntSet 可以看做是特殊的整数数组，具备一些特点：

1. Redis 会确保 IntSet 中的元素唯一、有序
2. 具备类型升级机制，可以节省内存空间
3. 底层采用二分查找方式来查询

Dict#

Dict 键值关系对，哈希表的大小总是为 $2^n$，used 有可能超过 size，此时一定会有个桶退化成链表

union 指其中任意一个

sizemask = size - 1，二进制为 n 个 1

实际组成

扩容

Dict 中的 HashTable 是数组结合链表，所以考虑数据过多解决数据冲突，扩大到上取 $2^n$

收缩

每次删除时也会检查 loadFactor < 0.1 就会收缩到 used 上取 $2^n$ 最小为 4

重建

不管是扩容还是收缩都会涉及到重建，改变 size、sizemask，所以要 rehash，这就是为什么 dict 要有 ht [2]，一份用，一份空

扩容重建示例

当数据量十分大时，无法一次性重建完成，所以实际是渐进式 hash，慢慢迁移，以前的数据可能在 ht [0]/ht [1]，所以新增放在 ht [1]，ht [0] 只减不增

ZipList#

ZipList 是一种特殊的 “双端链表”，由一系列特殊编码的连续内存块组成。可以在任意一端进行压入 / 弹出操作，时间复杂度为 O (1)

大小

可以通过前一个 entry 占用长度得到上一个 entry 起始地址进行逆序遍历，可以通过计算结构中长度得到下一个 entry 起始地址进行正序遍历

注意 Redis 这里用小端字节序
字符串类型

整数类型 0-12 可以省去 content 直接在 encoding 的后 4 bit 中保存数值

ZipList 的连锁更新问题#

主要问题在于：记录前一个 entry 长度的 prevlen 字段会在长度大于等于 254 字节时由 1 字节变为 5 字节，导致下一个 entry 的 prevlen 可能发生连锁更新

在 ZipList 中插入或修改一个 entry1，使之大于等于 254 字节，此时这个 entry1 后面的 entry2 中 prevlen 字段就需要从 1 字节变为 5 字节去记录 entry1 的新长度

这个改变导致 entry2 后面的 entry3 也需要修改 prevlen3 字段去记录 entry2 变化后的新长度，一旦极端些，每个 entry 在 prevlen 字段由 1 字节变为 5 字节时都大于等于 254 字节，那会有一系列连锁更新，导致插入 O (1) 退化成 O (n)

为什么是大于等于 254 而不是 255 字节时 prevlen 采用 5 字节？
prevlen 有 8 位，可以表示 0~255，但是 255 即 0xff 被 zlend 特殊标记占据，标记压缩列表 ZipList 末端，而 prevlen 恰好又是一个 entry 的起始，用 255 分界会与 zlend 结束符冲突

ZipList 特性

1. 压缩列表的可以看做一种连续内存空间的 “双向链表 "
2. 列表的节点之间不是通过指针连接，而是记录上一节点和本节点长度来寻址，内存占用较低
3. 如果列表数据过多，导致链表过长，可能影响查询性能
4. 增或删较大数据时有可能发生连续更新问题

QuickList#

ZipList 问题：

1. 保存前后链表指针需要足足 16 字节，ZipList 节省了非常多内存，但却要求使用连续内存空间，申请内存效率比较低；限制 ZipList 长度以及 entry 大小
2. 要存储大量数据，超过了 ZipList 最佳存储上限；创建多个 ZipList 分片存储
3. 数据拆分后过于分散，不便管理查找；引入 QuickList 双端链表，节点记录 ZipList

配置项 list-max-ziplist-szie=-2 默认一个 ZipList 内存占用不超过 8kb

配置项是否压缩节点，即首尾各不压缩节点个数，解释为经常使用首尾节点，中间节点不怎么用的到

这里即首尾各 1 个节点不压缩，所以中间的两个 ZipList 被重编码

QuickList 特性：

1. 是一个节点为 ZipList 的双端链表；内存碎片多，连续占用少
2. 节点采用 ZipList，解决了传统链表的内存占用问题；ZipList 节省内存
3. 控制了 ZipList 大小，解决连续内存空间申请效率问题；分片 ZipList，不必要连续大内存
4. 中间节点可以压缩，进一步节省了内存；

SkipList#

跳表 SkipList 首先是链表
1. 元素按升序排列
2. 节点可能包含多个指针，指针跨度不同；这样起码比一个一个遍历快，最高允许 32 个

向后指针 backward，向前指针采用 level [] 数组，最起码有一个跨度指针，可以快速向前跨然后一步一步往后摸索到正确的节点

在查找时从高层级往下检索，类似于二分，空间换时间，提前存储了某跨度后的节点

SkipList 特性：

1. 跳表 SkipList 是一个双向链表，每个节点都包含 score 和 element
2. 节点按照 score 值排序，score 值一样则按照 element 字典排序
3. 每个节点都可以包含多层指针，层数是 1 到 32 之间的随机数
4. 不同层指针到下一个节点的跨度不同，层级越高，跨度越大
5. 增删改查效率与红黑树基本一致，实现却更简单

RedisObject#

Redis 中的任意数据类型的键和值都会被封装为 RedisObject，也叫做 Redis 对象

type、encoding、lru 共 32 bit，4 字节；refcount 4 字节；*ptr 8 字节，RedisObject 头部占 16 字节

如 String 类型，一个 key-value 就消耗一个 RedisObject 头，确实蛮占空间

编码方式 encoding

五种数据类型#

那 BitMap、HyperLogLog 呢？
这些衍生出来的数据结构实际上基于 String 这个数据结构实现，并不是新类型
还有 GEO 基于 SortedSet

String#

String 是 Redis 最常见的数据存储类型

String RAW 编码#

String 基本编码方式是 RAW，基于简单动态字符串 SDS 实现，存储上限为 512mb

String EmbStr 编码#

如果存储的 SDS 长度小于等于 44 字节，则会采用 EMBSTR 编码，此时 RedisObject Head 与 SDS 是一段连续空间；申请内存时只需要调用一次内存分配函数，效率更高；与 Redis 申请内存算法有关，总之就是如果 SDS 长度为 44 字节，Head + SDS 刚好 64 字节，不会产生内存碎片

String INT 编码#

如果存储的字符串是整数值，并且大小在 LONG_MAX 范围内，则会采用 INT 编码，直接将数据保存在 RedisObject 的 ptr 指针位置，刚好 8 字节，不再需要 SDS

String raw、embstr、int 编码#

List#

List 数据类型可以操作首尾两端的元素，底层使用 LinkedList + ZipList 结合起来的 QuickList 数据结构

List 结构

Set#

Set 数据类型是单列集合，不保证有序，保证元素唯一，可求交、并、差；对查也就是 SISMEMBER 非常频繁，所以选用 HashTable

采用 HT 编码 Dict，用 key 存元素，value 统一为 null
当存储全是整数，且元素数量不超过 set-max-intset-entries 时，Set 采用 IntSet 编码，节省内存

如果使用 IntSet 超过最大数或加入非整数，则转换成 HT 编码 Dict

IntSet 编码的 Set

HashTable 编码的 Set

ZSET#

ZSet 也就是 SortedSet，每一个元素都有一个 score 值和 member 值，可以根据 score 值排序，member 唯一性，可以查询 member 分数；member 和 score 类键值对关系，即 ZSet 要求键值存储、键唯一、可排序，所以可选 SkipList、HashTable

SkipList 根据 score 排序，满足键值存储和可排序，但是当根据 member 查 score 就退化成链表，并且 member 唯一也不方便

HashTable 设置 key-value 为 member-score 即可，但是无法满足根据 score 排序的功能

所以两个数据结构都使用，Dict 保证 member 唯一，ZSet 保证可排序、范围查询

ZSet 使用 Dict 和 SkipList 结合，编码设置为 SKIPLIST

但是当元素不多时选用 Dict + ZipList 结合非常占用内存而且又是不怎么明显，因此在满足以下条件时 ZSet 会选用 ZipList 结构节省内存

1. 元素数量小于 zset_max_ziplist_entries，默认值 128
2. 每个元素都小于 zset_max_ziplist_value 字节，默认值 64

在初始化创建时，如果初始值两个条件都同时满足，那么就使用 ZipList

在添加元素时如果是 ZipList 则会判断要不要转换成 SkipList + HashTable 结构

但是 ZipList 不满足 ZSet 的三个要求，为什么在小数据、小数据量下可以用 ZipList ？
可以用业务逻辑模拟支持排序、键值对排序，并且连续内存空间，element/member 在前 value/score 在后

Hash#

Hash 结构与 ZSet 结构类似，要求键值存储，键唯一，可以根据键获取值；必然是 hashTable 啊

和 ZSet 区别

1. ZS et 的键是 member，值是 score；hash 的键和值都是任意值
2. ZSet 要根据 score 排序；Hash 则无需排序

Hash 结构默认采用 ZipList 编码，用以节省内存，ZipList 中相邻的两个 entry 分别保存 field 和 value
当数据量较大时，Hash 结构会转为 HT 编码即 Dict，触发条件有两个

1. zipList 中的元素数量超过了 hash-max-ziplist-entries 默认 512
2. ZipList 中的任意 entry 大小超过了 hash-max-ziplist-value 默认 64 字节

打破了任意一个条件就转换成 HT 编码

Hash 源码，可以看到初始化时默认初始化成 ZipList

然后在尝试添加时判断要不要转换 HT 编码，根据元素大小进行判断

最后进行添加，添加时会判断有没有等，如果是 ZipList 再插入后检查长度，超过就转换成 HT 编码

此文由 Mix Space 同步更新至 xLog
原始链接为 https://blog.0xling.cyou/posts/redis/redis-3