1. 数据结构
1.1 SDS
1.1.1 数据结构
我们都知道 Redis 中保存的 Key 是字符串，value 往往是字符串或者字符串的集合。可见字符串是 Redis 中最常用的一种数据结构
不过 Redis 没有直接使用 C 语言中的字符串，因为 C 语言字符串存在很多问题：
- 获取字符串长度的需要通过运算
- 非二进制安全
不可修改
// 本质是字符数组： {'h', 'e', 'l', 'l', 'o', '\0'}char *s="hello"
Redis 构建了一种新的字符串结构，称为简单动态字符串（Simple Dynamic String），简称 SDS
例如，我们执行命令set name zhangsan，那么 Redis 将在底层创建两个 SDS，其中一个是包含 “name” 的SDS，另一个是包含 “zhangsan” 的SDS ```c struct attribute ((packed)) sdshdr8 { // buf 已保存的字符串字节数，不包含结束标示 uint8_t len; / used /// buf 申请的总的字节数，不包含结束标示 uint8_t alloc; / excluding the header and null terminator /
// 不同 SDS 的头类型，用来控制 SDS 的头大小 unsigned char flags; / 3 lsb of type, 5 unused bits /
// 实际存储内容 char buf[]; };
// SDS 头类型
define SDS_TYPE_5 0
define SDS_TYPE_8 1
define SDS_TYPE_16 2
define SDS_TYPE_32 3
define SDS_TYPE_64 4
例如，一个包含字符串 "name" 的 sds 结构如下<br /><a name="tLjDb"></a>### 1.1.2 动态扩容SDS 之所以叫做动态字符串，是因为它具备动态扩容的能力，例如一个内容为 "hi" 的SDS：<br /><br />现在要给 SDS 追加一段字符串 ",Amy"，这里首先会申请新内存空间，遵循内存预分配- 如果新字符串小于 1M，则新空间为扩展后字符串长度的两倍- 如果新字符串大于 1M，则新空间为扩展后字符串长度 + 1M![image.png](https://cdn.nlark.com/yuque/0/2022/png/432786/1657017899972-370fc94e-365d-4ada-9e41-1c64f64972e3.png#clientId=u8439ac84-7a74-4&crop=0&crop=0&crop=1&crop=1&from=paste&height=78&id=u05791177&margin=%5Bobject%20Object%5D&name=image.png&originHeight=156&originWidth=1650&originalType=binary&ratio=1&rotation=0&showTitle=true&size=16191&status=done&style=none&taskId=u82cf6894-8fcb-4ea1-a422-a5852fdc0da&title=%22hi%2CAmy%22%20%E9%95%BF%E5%BA%A6%E4%B8%BA%206%20%E4%B8%AA%E5%AD%97%E8%8A%82%EF%BC%8C%E6%89%A9%E5%AE%B9%E5%90%8E%E4%B8%BA%2012%20%E4%B8%AA%E5%AD%97%E8%8A%82&width=825 ""hi,Amy" 长度为 6 个字节，扩容后为 12 个字节")<a name="fHOMS"></a>### 1.1.3 特点- 获取字符串长度的时间复杂度为 O(1)- 支持动态扩容- 减少内存分配次数- 二进制安全<a name="eA1Go"></a>## 1.2 IntSet<a name="QGMGb"></a>### 1.2.1 数据结构```ctypedef struct intset {// 编码方式，支持存放16位、32位、64位整数uint32_t encoding;// 元素个数uint32_t length;// 整数数组，保存集合数据int8_t contents[];} intset;// 其中的encoding包含三种模式，表示存储的整数大小不同// 2 个字节整数，类似 Java 中的 short#define INTSET_ENC_INT16 (sizeof(int16_t))// 4 个字节整数，类似 Java 中的 int#define INTSET_ENC_INT32 (sizeof(int32_t))// 8 个字节整数，类似 Java 中的 long#define INTSET_ENC_INT64 (sizeof(int64_t))
为了方便查找，Redis 会将 intset 中所有的整数按照升序依次保存在 contents 数组中，结构如图
现在，数组中每个数字都在int16_t的范围内，因此采用的编码方式是INTSET_ENC_INT16，每部分占用的字节大小为
- encoding：4 字节
- length：4 字节
-
1.2.2 动态扩容
现在向其中添加一个数字：50000，这个数字超出了 int16_t 的范围，intset 会自动升级编码方式到合适的大小
升级流程是： 升级编码为 INTSET_ENC_INT32，每个整数占 4 字节，并按照新的编码方式及元素个数扩容数组
- 倒序依次将数组中的元素拷贝到扩容后的正确位置
- 将待添加的元素放入数组末尾
最后，将 inset 的 encoding 属性改为 INTSET_ENC_INT32，将 length 属性改为 4
1.2.3 特点
Redis 会确保 Intset 中的元素唯一、有序
- 具备类型升级机制，可以节省内存空间
-
1.3 Dict
1.3.1 数据结构
Redis 是一个键值型（Key-Value Pair）的数据库，我们可以根据键实现快速的增删改查。而键与值的映射关系正是通过 Dict 来实现的
Dict 由三部分组成，分别是：哈希表（DictHashTable）、哈希节点（DictEntry）、字典（Dict） ```c typedef struct dict { // dict 类型，内置不同的 hash 函数 dictType *type;// 私有数据，在做特殊 hash 运算时用 void *privdata;
// 一个 Dict 包含两个哈希表，其中一个是当前数据，另一个一般是空，rehash 时使用 dictht ht[2];
// rehash 的进度，-1 表示未进行 long rehashidx; / rehashing not in progress if rehashidx == -1 /
// rehash 是否暂停，1 则暂停，0 则继续 int16_t pauserehash; / If >0 rehashing is paused (<0 indicates coding error) / } dict;
typedef struct dictht {
// entry 数组，数组中保存的是指向 entry 的指针dictEntry **table;// 哈希表大小unsigned long size;// 哈希表大小的掩码，总等于 size - 1unsigned long sizemask;// entry个数unsigned long used;
} dictht;
typedef struct dictEntry { // key void *key;
// valueunion {void *val;uint64_t u64;int64_t s64;double d;} v;// 下一个Entry的指针struct dictEntry *next;
} dictEntry;
```
当我们向 Dict 添加键值对时，Redis 首先根据 key 计算出 hash 值（h），然后利用 h & sizemask 来计算元素应该存储到数组中的哪个索引位置
我们存储 k1=v1，假设 k1 的哈希值 h =1，则 1&3 =1，因此 k1=v1 要存储到数组角标 1 位置
1.3.2 动态扩容
Dict 中的 HashTable 就是数组结合单向链表的实现，当集合中元素较多时，必然导致哈希冲突增多，链表过长，则查询效率会大大降低。Dict在每次新增键值对时都会检查负载因子（LoadFactor = used/size） ，满足以下两种情况时会触发哈希表扩容：哈希表的 LoadFactor >= 1，并且服务器没有执行 BGSAVE 或者 BGREWRITEAOF 等后台进程；哈希表的 LoadFactor > 5 ；
1.3.3 特点
1.4 ZipList
1.5 QuickList
1.6 SkipList
1.7 RedisObject
1.8 五种数据结构
2. 网络模型
3. 通信协议
4. 内存策略
若有收获，就点个赞吧
0 人点赞
