redis——数据结构（字典、链表、字符串）

墨蓝 2022-02-19 13:29 299阅读 0赞

# 1 字符串 #

redis并未使用传统的c语言字符串表示，它自己构建了一种简单的动态字符串抽象类型。

在redis里，c语言字符串只会作为字符串字面量出现，用在无需修改的地方。

当需要一个可以被修改的字符串时，redis就会使用自己实现的SDS（simple dynamic string）。比如在redis数据库里，包含字符串的键值对底层都是SDS实现的，不止如此，SDS还被用作缓冲区（buffer）：比如AOF模块中的AOF缓冲区以及客户端状态中的输入缓冲区。

下面来具体看一下sds的实现：

struct sdshdr
    {
        int len;//buf已使用字节数量（保存的字符串长度）
        int free;//未使用的字节数量
        char buf[];//用来保存字符串的字节数组
    };

sds遵循c中字符串以'\\0'结尾的惯例，这一字节的空间不算在len之内。

这样的好处是，我们可以直接重用c中的一部分函数。比如printf；

### sds相对c的改进 ###

获取长度：c字符串并不记录自身长度，所以获取长度只能遍历一遍字符串，redis直接读取len即可。

缓冲区安全：c字符串容易造成缓冲区溢出，比如：程序员没有分配足够的空间就执行拼接操作。而redis会先检查sds的空间是否满足所需要求，如果不满足会自动扩充。

内存分配：由于c不记录字符串长度，对于包含了n个字符的字符串，底层总是一个长度n+1的数组，每一次长度变化，总是要对这个数组进行一次内存重新分配的操作。因为内存分配涉及复杂算法并且可能需要执行系统调用，所以它通常是比较耗时的操作。

redis内存分配：

1、空间预分配：如果修改后大小小于1MB，程序分配和len大小一样的未使用空间，如果修改后大于1MB，程序分配 1MB的未使用空间。修改长度时检查，够的话就直接使用未使用空间，不用再分配。

2、惰性空间释放：字符串缩短时不需要释放空间，用free记录即可，留作以后使用。

### 二进制安全 ###

c字符串除了末尾外，不能包含空字符，否则程序读到空字符会误以为是结尾，这就限制了c字符串只能保存文本，二进制文件就不能保存了。

而redis字符串都是二进制安全的，因为有len来记录长度。

# 2 链表 #

作为一种常用数据结构，链表内置在很多高级语言中，因为c并没有，所以redis实现了自己的链表。

链表在redis也有一定的应用，比如列表键的底层实现之一就是链表。（当列表键包含大量元素或者元素都是很长的字符串时）

发布与订阅、慢查询、监视器等功能也用到了链表。

具体实现：

//redis的节点使用了双向链表结构
    typedef struct listNode {
        // 前置节点
        struct listNode *prev;
        // 后置节点
        struct listNode *next;
        // 节点的值
        void *value;
    } listNode;

//其实学过数据结构的应该都实现过
    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链表特性：

双端、无环、带长度记录、

多态：使用 `void*` 指针来保存节点值， 可以通过 `dup` 、 `free` 、 `match` 为节点值设置类型特定函数， 可以保存不同类型的值。

# 3、字典 #

其实字典这种数据结构也内置在很多高级语言中，但是c语言没有，所以redis自己实现了。

应用也比较广泛，比如redis的数据库就是字典实现的。不仅如此，当一个哈希键包含的键值对比较多，或者都是很长的字符串，redis就会用字典作为哈希键的底层实现。

来看看具体是实现：

//redis的字典使用哈希表作为底层实现
    typedef struct dictht {
        // 哈希表数组
        dictEntry **table;
        // 哈希表大小
        unsigned long size;
        // 哈希表大小掩码，用于计算索引值
        // 总是等于 size - 1
        unsigned long sizemask;
    
        // 该哈希表已有节点的数量
        unsigned long used;
    
    } dictht;

`table` 是一个数组， 数组中的每个元素都是一个指向`dictEntry` 结构的指针， **每个 `dictEntry` 结构保存着一个键值对**。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70][]

图为一个大小为4的空哈希表。

我们接着就来看`dictEntry的实现：`

typedef struct dictEntry {
        // 键
        void *key;
        // 值
        union {
            void *val;
            uint64_t u64;
            int64_t s64;
        } v;
    
        // 指向下个哈希表节点，形成链表
        struct dictEntry *next;
    } dictEntry;

（v可以是一个指针， 或者是一个 `uint64_t` 整数， 又或者是一个 `int64_t` 整数。）

next就是解决键冲突问题的，冲突了就挂后面，这个学过数据结构的应该都知道吧，不说了。

下面我们来说字典是怎么实现的了。

typedef struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privdata;
        // 哈希表
        dictht ht[2];
        // rehash 索引
        int rehashidx; //* rehashing not in progress if rehashidx == -1 
    } dict;

`type` 和 `privdata` 是对不同类型的键值对， 为创建多态字典而设置的：

`type` 指向 `dictType` ， 每个 `dictType` 保存了用于操作特定类型键值对的函数， 可以为用途不同的字典设置不同的类型特定函数。

而 `privdata` 属性则保存了需要传给那些类型特定函数的可选参数。

而dictType就暂时不展示了，不重要而且字有点多。。。还是讲有意思的东西吧

### rehash（重新散列） ###

随着我们不断的操作，哈希表保存的键值可能会增多或者减少，为了让哈希表的负载因子维持在合理的范围内，有时需要对哈希表进行合理的扩展或者收缩。 一般情况下， 字典只使用 `ht[0]` 哈希表， `ht[1]` 哈希表只会在对 `ht[0]` 哈希表进行 rehash 时使用。

redis字典哈希rehash的步骤如下：

1）为ht\[1\]分配合理空间：如果是扩展操作，大小为第一个大于等于ht\[0\]\*used\*2的，2的n次幂。

如果是收缩操作，大小为第一个大于等于ht\[0\]\*used的，2的n次幂。

2）将ht\[0\]中的数据rehash到ht\[1\]上。

3）释放ht\[0\]，将ht\[1\]设置为ht\[0\]，ht\[1\]创建空表，为下次做准备。

### 渐进rehash ###

数据量特别大时，rehash可能对服务器造成影响。为了避免，服务器不是一次性rehash的，而是分多次。

我们维持一个变量rehashidx，设置为0，代表rehash开始，然后开始rehash，在这期间，每个对字典的操作，程序都会把索引rehashidx上的数据移动到ht\[1\]。

随着操作不断执行，最终我们会完成rehash，设置rehashidx为-1.

需要注意：rehash过程中，每一次增删改查也是在两个表进行的。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9mYW50aWFuenVvLmJsb2cuY3Nkbi5uZXQ_size_16_color_FFFFFF_t_70]: /images/20220219/e76b67315ca24266ae3834de276b51e8.png