Redis- 中会涉及那么多数据结构，那你数据对象的底层实现方式你都了解吗？
常数复杂度获取字符串长度，因为 SDS 在 len 属性中记录了 SDS 本身的长度，所以获取一个 SDS 长度的复杂度仅为 O（1）
杜绝缓冲区溢出，SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小
减少修改字符串时带来的内存重分配次数，SDS 通过未使用空间解除了字符串长度和底层数组长度之间的关联 ：在 SDS 中，buf 数组的长度不一定就是字符数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由 SDS 的 free 属性记录
空间预分配策略，如果对 SDS 进行修改之后，SDS 的长度（也即是 len 属性的值）将小于 1MB，那么程序分配和 len 属性同样大小的未使用空间，这时 SDS len 属性的值将和 free 属性的值相同，如果对 SDS 进行修改之后，SDS 的长度将大于等于 1MB，那么程序会分配 1MB 的未使用空间。也就是说 1M 以下倍增，1M 以上只增加 1M，防止存储过大对象，通过空间预分配策略，Redis 可以减少连续执行字符串增长操作所需的内存重分配次数
惰性空间释放策略，惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。SDS 也提供了相应的 API，在有需要时，我们可以真正地释放 SDS 的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费通过惰性空间释放策略，Redis 可以减少执行字符串缩短操作所需的内存重分配次数
二进制安全，SDS 的 API 都是二进制安全的（binary-safe），所有 SDS API 都会以处理二进制的方式来处理 SDS 存放在 buf 数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，数据在写入时是什么样的，它被读取时就是什么样，例如，使用 SDS 来保存包含空字符格式的数据格式就没有任何问题，因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束 Redis 不仅可以保存文本数据，还可以保存任意格式的二进制数据
总而言之，动态字符串用额外的 free 和 len 空间来弥补了很多 C 语言性能上的问题。
链表
链表提供了高效的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度，但是由于 C 语言没有链表的数据结构，所以 Redis 的链表是自己定义的结构。
链表结构
链表单节点的数据结构如下，包含三部分属性 prev、next 以及 value，用来描述一个链表单节点的结构体：
typedef struct listNode{// 前置节点 struct listNode *prev;// 后置节点 struct listNode *next;// 节点的值 void *value;} listNode;
示例如下图所示： 
同时 Redis 为了方便的操作链表，提供了一个 list 结构来持有链表，也就是我们的链表结构，如下所示
在这里插入图片描述 list 结构为链表提供了表头指针 head、表尾指针 tail，以及链表长度计数器 len，而 dup、free 和 match 成员则是用于实现多态链表所需的类型特定函数：
dup 函数用于复制链表节点所保存的值
free 函数用于释放链表节点所保存的值
match 函数则用于对比链表节点所保存的值和另一个输入值是否相等
用代码来描述如下所示：
typedef struct list{//表头节点 listNode *head;//表尾节点 listNode *tail;//链表所包含的节点数量 unsigned long len;//节点值复制函数 void *(*dup)(void *ptr);//节点值释放函数 void *(*free)(void *ptr);//节点值对比函数 int (*match)(void *ptr,void *key);}list;
链表结构优势
链表结构的优势其实在很多语言中都有体现，在 Redis 这里由于特殊的设计结构，又有些不一样的地方，总而言之如下：
双端：链表节点带有 prev 和 next 指针，获取某个节点的前置节点和后置节点的复杂度都是 O（1）
无环：表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL，对链表的访问以 NULL 为终点
带表头指针和表尾指针：通过 list 结构的 head 指针和 tail 指针，程序获取链表的表头节点和表尾节点的复杂度为 O（1）
带链表长度计数器：程序使用 list 结构的 len 属性来对 list 持有的链表节点进行计数，程序获取链表中节点数量的复杂度为 O（1）
多态：链表节点使用 void*指针来保存节点值，并且可以通过 list 结构的 dup、free、match 三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值
正是由于这些优势，链表编码有广泛的用途：比如 Redis 列表数据对象、发布与订阅、慢查询、监视器等
字典
字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对（key-value pair）的抽象数据结构，字典中的每个键都是独一无二的，程序可以在字典中根据键查找与之关联的值，或者通过键来更新值，又或者根据键来删除整个键值对
Redis 数据库就是一个字典模型，key 和 value 组成
同时 hash 对象的底层实现之一也包括字典
总而言之，字典有较为广泛的用途，但是同链表一样，C 语言没有字典这种数据结构，所以 Redis 自己实现了这种结构。
字典结构
字典是由哈希表加上一系列属性方法组成，而哈希表又是由哈希表节点加上一系列哈希表结构组成的：
哈希表节点
哈希表节点使用 dictEntry 结构表示，每个 dictEntry 结构都保存着一个键值对，但是有链式结构：
typedef struct dictEntry {
// 键 void *key;// 值 union {void *val;uint64_t u64;int64_t s64;} v;
// 指向下个哈希表节点，形成链表 struct dictEntry *next;
} dictEntry;
各个属性部分如下：
key 属性保存着键值对中的键
v 属性则保存着键值对中的值，其中键值对的值可以是一个指针，或者是一个 uint64t 整数，又或者是一个 int64t 整数。
next 属性是指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一次，以此来解决键冲突（collision）的问题
也就是说在相同键上的多个哈希表节点存在链式关系，有链表实现。
哈希表
哈希表结构定义如下，包括哈希表数组，哈希表大小【已用+未用】的变量，哈希表大小的掩码值，哈希表已有节点数量
typedef struct dictht {
// 哈希表数组 dictEntry **table;// 哈希表大小 unsigned long size;// 哈希表大小掩码，用于计算索引值，总是等于 size - 1unsigned long sizemask;// 该哈希表已有节点的数量 unsigned long used;
} dictht;
各个属性部分如下：
table 属性是一个数组，数组中的每个元素都是一个指向 dict.h/dictEntry 结构的指针，每个 dictEntry 结构保存着一个键值对
size 属性记录了哈希表的大小，也即是 table 数组的大小
used 属性则记录了哈希表目前已有节点（键值对）的数量
sizemask 属性的值总是等于 size-1，这个属性和哈希值一起决定一个键应该被放到 table 数组的哪个索引上面
其中 table 是我们这个结构的核心。
字典又是由哈希表和一系列属性和函数组成的，为了满足 Redis 快而增加的一些空间占用属性：
typedef struct dict {
// 类型特定函数 dictType *type;// 私有数据 void privdata;// 哈希表 dictht ht[2];// rehash 索引，当 rehash 不再进行时，值为 -1int rehashidx; / rehashing not in progress if rehashidx == -1 */
各个属性含义如下：
type 属性和 privdata 属性是针对不同类型的键值对，而创建多态字典而设置的：type 属性是一个指向 dictType 结构的指针，每个 dictType 结构保存了一组用于操作特定类型键值对的函数，Redis 会为用途不同的字典设置不同类型的特定函数。而 privadata 属性则保存了需要传给那些类型特定函数的可选参数。
ht 属性是一个包含了两个项的数组，数组中每个项都是一个 dictht 哈希表，一般情况下，字典只使用 ht[0]哈希表，而 ht[1]哈希表只对 ht[0]哈希表进行 rehash 时使用。
rehashidx 属性，与 rehash 相关，它积累了 rehash 目前的进度，如果没有进行 rehash，则它的值为-1
关于 rehash 算法在接下来的内容重点看，其中 ht 属性是较为核心的属性。
哈希算法
当要将一个新的键值对添加到字典里面时，程序需要先根据键值对的键计算出哈希值和索引值，然后再根据索引值，将包含新键值对的哈希表节点放到哈希表数组的指定索引上面：
使用字典设置的哈希函数，计算键 key 的哈希值 hash = dict->type->hashFunction(key);
使用哈希表的 sizemask 属性和哈希值，计算出索引值，index = hash & dict->ht[x].sizemask，根据情况不同， ht[x] 可以是 ht[0] 或者 ht[1]，
举个例子，假设 hash 计算结果为 8，且掩码为 3，则相与的结果为 0，所以被放到 ht[0]哈希表的字典索引 0 的位置
解决键冲突
当有两个或以上数量的键被分配到了哈希表数组的同一个索引上面时，我们称这些键发生了冲突（collision）。Redis 的哈希表使用链地址法（separate chaining）来解决键冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，被分配到同一个索引上的多个节点可以用这个单向链表连接起来，这就解决了键冲突的问题：
另外因为 dictEntry 节点组成的链表没有指向链表表尾的指针，为了考虑速度，程序总是将新节点添加到链表的表头位置（这样添加节点的时间复杂度为 O(1)）
rehash
随着操作的不断进行，哈希表保存的键值对会逐渐增多或减少，为了让哈希表负载因子【哈希表已保存节点数量/哈希表的 size，可以理解为 used/size】维持在一个合理范围之内，当哈希表保存的键值对太多或太少时，程序要对哈希表的大小进行相应的扩展或收缩。
Redis 对字典的哈希表执行 rehash 的步骤如下：
1.为字典的 ht[1]哈希表分配空间，这个空间大小取决于要执行的操作
如果执行扩展操作，则 ht[1]的大小为第一个大于等于等于 ht[0].used*2 的 2^n；
如果执行收缩操作，则 ht[1]的大小为第一个大于等于 ht[0].used 的 2^n；当哈希表负载因子小于 0.1 时，程序自动开始对哈希表执行收缩操作
2.将保存在 ht[0]中的所有键值对 rehash 到 ht[1]上面：rehash 指的是重新计算键的哈希值和索引值，然后将键值对放置到 ht[1]的指定位置上。
3.当 ht[0]包含的所有键值对都迁移到 ht[1]之后，释放 ht[0]，将 ht[1]设置为 ht[0]，并在 ht[1]新创建一个空白哈希表，为下一次 rehash 做准备。
以上就是 rehash 的全流程。当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作：
1）服务器目前没有在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 1
2）服务器目前正在执行 BGSAVE 命令或者 BGREWRITEAOF 命令，并且哈希表的负载因子大于等于 5。
BGSAVE 或 BGREWRITEAOF 操作是 Redis 的持久化操作，在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中，Redis 需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制（copy-on-write）【只有进程空间的各段的内容要发生变化时，才会将父进程的内容复制一份给子进程】技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能地避免在子进程存在期间进行哈希表扩展操作，这可以避免不必要的内存写入操作，最大限度地节约内存。
渐进式 rehash
Redis 中的 rehash 动作并不是一次性、集中式完成的，而是分多次、渐进式的完成的。这样做的目的是，如果服务器中包含很多键值对，要一次性的将这些键值对全部 rehash 到 ht[1]的话，庞大的计算量可能导致服务器在一段时间内停止服务。渐进式 Rehash 操作
1.为 ht[1]分配空间，让字典同时持有 ht[0]和 ht[1]两个哈希表。在字典中维持一个索引计数器变量 rehashidx，并将它置为 0，表示 rehash 工作开始。
还未添加个人签名 2021.11.08 加入
还未添加个人简介
评论