Redis

关于redis相关的技术文章我一直没什么思路
直到最近的端午节,我偶然和一个程序员朋友聊到了关于redis数据结构相关的知识点,
所以我决定写一篇文章记录一下

首先我们需要知道redis支持哪些数据类型

• Strings (字符串)
• Lists(列表)
• Hashes(哈希)
• Sets(集合)
• Sorted Sets(有序集合)

关于这几种数据类型的操作不是我们的重点

底层数据结构:SDS

SDS（Simple Dynamic String）是 Redis 中用来表示字符串对象的一种动态字符串结构;SDS 为 Redis 中的字符串表示提供了一种高效,灵活的实现方式.

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组，用于保存字符串内容
    char buf[];
};

具有以下特点:

1.动态增长的字符串长度 :

• SDS可以根据需要动态地调整其内存大小并且在扩展时会预留一定的额外空间,通过这种方式来减少频繁的内存分配和复制操作

2.二进制安全 :

• 简单点说就是通过len字段就可以知道实际的字符串,而不是通过C语言的\0空字符串

3.惰性空间释放 :

• 和第一点类似,当我们需要减少字符串所占用的空间时,SDS不会立即释放掉这部分空间,减少频繁的内存分配和复制操作

底层数据结构:双向链表

列表中包含的元素都是比较长的字符串的时，Redis 就会使用链表作为 list 的底层实现

在 Redis 中，双向链表由 listNode 和 list 两个结构体组成:

1. listNode 结构体： 表示双向链表的节点，包含了指向前驱节点和后继节点的指针，以及存储实际数据的指针。
2. list 结构体： 表示整个双向链表，包含了指向链表表头和表尾的指针，以及链表的长度、复制函数和释放函数等信息。

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;

typedef struct listNode {
    //前置节点
    struct listNode
    //后置节点
    * prev;
    struct listNode
    //节点的值
    void *value;
    * next;
} listNode;

具有以下特点:

1.灵活的插入和删除操作 :

• 双向链表支持在任意位置高效地进行插入和删除操作，由于每个节点都保存了指向前一个节点和后一个节点的指针，可以在 O(1) 时间内完成插入或删除操作。

2.反向遍历 :

• 从前往后或者从后往前查询效率都是很客观的

3.封装了复制和释放函数 :

• 三个函数指针,链表可以轻松地处理包含动态内存分配的数据类型

底层数据结构:字典

1.哈希表 (Hash Table)
Redis 的字典主要是通过哈希表实现的。每个字典包含两个哈希表（ht[0] 和 ht[1]），其中一个用于存储当前的数据，另一个在 rehashing 过程中使用。

2.哈希表节点 (Hash Table Node)
每个哈希表节点包含一个键值对。节点结构如下：

typedef struct dictEntry {
    void *key;
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
    struct dictEntry *next;
} dictEntry;

这个结构体定义了一个哈希表节点，包括键、值和指向下一个节点的指针（实现链地址法解决哈希冲突）。

3.哈希表结构 (Hash Table Structure)
哈希表结构包含指向哈希表数组的指针、大小、已使用节点数以及 rehash 索引：

typedef struct dictht {
    dictEntry **table;
    unsigned long size;
    unsigned long sizemask;
    unsigned long used;
} dictht;

table 是一个指向哈希表数组的指针。
size 是哈希表的大小。
sizemask 是用来计算索引的掩码。
used 是哈希表中已使用节点的数量。

4.字典结构 (Dictionary Structure)
字典结构包含两个哈希表和一些控制字段：

typedef struct dict {
    dictType *type;
    void *privdata;
    dictht ht[2];
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

type 是一个指向函数指针的结构体，用于实现特定类型的键和值操作。
privdata 是私有数据指针，一般用作回调函数的参数。
ht 是包含两个哈希表的数组。
rehashidx 是 rehashing 的索引，如果没有进行 rehashing，则为 -1。
iterators 表示当前运行的迭代器数量。

5.渐进式 Rehashing
Redis 使用渐进式 rehashing 来避免在哈希表扩展或缩减时阻塞服务器。rehashing 过程会逐步将 ht[0] 中的条目移动到 ht[1] 中，而不是一次性完成。这样做的好处是可以将 rehashing 的时间均摊到多个操作中，减少单次 rehashing 对性能的影响。

rehashing 过程的步骤一般如下：

1. 初始化：创建一个新的哈希表（ht[1]），并设置 rehashidx 为 0。
2. 渐进式迁移：在每次字典操作时（插入、删除、查找等），都会顺便将 ht[0] 中的一些条目迁移到 ht[1]。
3. 完成：当 ht[0] 中的所有条目都迁移到 ht[1] 后，释放 ht[0]，将 ht[1] 赋值给 ht[0]，然后重置 ht[1] 和 rehashidx。
   通过这种方式，Redis 可以保持较高的性能，即使在哈希表需要扩展或缩减的情况下。

总结而言，Redis 的字典数据结构依赖于高效的哈希表实现，并通过渐进式 rehashing 机制来确保在动态调整哈希表大小时的性能稳定。这种设计使得 Redis 能够在处理大量数据时仍然保持快速响应。

底层数据结构:跳表

上图:

跳表是在双向链表之上加多层索引构成的，相对于双向链表，支持快速查找，更新，删除，所以适用于需求灵活的场景。

具有以下特点:

• 跳表结合了链表和类似二分查找的思想；

• 有很多层结构，由原始链表和一些通过“跳跃”生成的链表组成；

• 每一层都是一个有序的链表；

• 最底层(Level 1)的链表包含所有元素，越上层“跳跃”的越高，元素(索引)越少；

• 查找时从顶层向下，不断缩小搜索范围；

• 上层链表是下层链表的子序列；

• 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

跳表最经典的应用就是在Redis中实现有序集合(ZSet)。

跳表在Redis中的唯一作用也就是对该数据类型的实现，但是除了使用跳表作为有序集类型的底层数据结构外，还使用了字典来构成有序集。

底层数据结构:整数集合

我好像没有遇到过需要设置集合的应用场景,我需要在学习一下

整数集合是一种紧凑的、有序的数据结构，用于存储整数值。它可以在节省内存的同时提供快速的插入、删除和查找操作。整数集合主要用于优化存储少量整数值的情况。

typedef struct intset {
    //编码方式
    uint32
    _t encoding;
    //集合包含的元素数量
    uint32_t length;
    //保存元素的数组
    int8 t contents[];
} intset;

整数集合主要用于优化存储在 Redis 中的数据，特别适用于存储一些特定场景下的计数器、唯一标识等整数类型的数据。由于整数集合具有紧凑、高效和支持快速查找的特性，能够节省内存并提供良好的性能。

具有以下特点:

1.节约内存空间：

整数集合根据存储的整数值决定了内部的编码方式，尽可能地节省内存空间。例如，如果所有的整数值都可以用 int16 来表示，那么整数集合将采用 int16 的编码方式存储。

2.支持快速查找：

整数集合内部的整数值是有序的，采用升序排列。这使得在整数集合中进行查找操作时，可以使用二分查找算法，从而快速定位目标元素。

3.支持动态扩容：

当插入新的整数值时，如果整数集合已满，它会自动进行扩容操作。扩容过程中，整数集合会根据当前存储的最大整数类型进行扩容，并将原有的整数值转移到新的存储空间中。

4.不支持重复元素：

整数集合中的元素是唯一的，不允许重复的整数值出现。

底层数据结构:压缩列表

当列表类型的数据量较小时，Redis 会使用压缩列表来存储 LIST 数据

压缩列表由几个部分组成：
zlbytes:记录整个压缩列表占用的字节数，用于重新分配和释放内存时使用。
zltail:到达压缩列表尾节点的偏移量，方便从尾部快速获取数据。
zllen:记录压缩列表包含的节点数量。当节点数量超过 2^16-1 时，该字段值为 0xffff，此时需要遍历整个列表来获取节点数量。
entryX:压缩列表中的各个节点，每个节点包含实际的数据。
zlend:特殊值 0xff，表示压缩列表的结束。

节点由几个部分组成：
previous_entry_length:记录前一个节点的长度，以便实现反向遍历。
encoding:记录当前节点的数据类型和长度。它可以存储不同类型的数据（如字符串或整数），并以不同的编码方式表示数据长度。
content:存储实际的数据内容，具体内容取决于 encoding 字段。

1.内存效率高:由于采用紧凑的内存布局，压缩列表非常节省内存

2.适合小数据量:当数据量增加到一定程度后，压缩列表的性能会急剧下降，不适合存储大量数据