Redis数据结构—动态字符串-链表-字典-跳跃表

妖狐艹你老母 2023-03-01 13:29 1阅读 0赞

读《Redis设计与实现》笔记

# 一、简单动态字符串 #

一个sdshdr结构表示一个SDS值：

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70]  
SDS还是遵循了C字符串以空字符结尾的惯例，最后一个字节保存空字符’\\0’。这样做的好处是SDS可以重用一些C字符串函数库里面的函数。

字符串拼接，例如执行sdscat(s,“Cluster”);其中SDS值s如上图，那么sdscat将在执行拼接操作之前检查s的长度是否足够，如果空间不足以拼接，sdscat就会先扩展s的空间。

Redis 作为数据库，对性能的要求极高，如果每次修改长度都需要一次内存重分配的话，那么光执行内存重分配的时间就会占用修改字符串所用时间的一大部分，如果这种修改频繁的发生可能还会对性能造成影响。

在 SDS 中，buf 数组的长度不一定就是字符数量加一，数字里面可以包含未使用的字节，这就是一种预分配空间的做法。  
这里通过未使用空间， SDS 实现了空间预分配和惰性空间释放的优化策略：

1.  空间预分配，程序不仅会为 SDS 分配修改所必要的空间，还会为 SDS 分配额外的未使用空间。  
    SDS 分配额外的未使用空间：修改后，SDS 的 len 改为了 13 字节，那么程序也会预分配 13 字节给 free 属性，SDS 的 buf 数组的实际长度将变成 13B+13B+1B=27 字节。如果修改完 SDS 后，SDS 的长度将大于 1 MB，那么程序会分配 1 MB 的未使用空间。比如修改后，SDS 的 len 改为 30 MB，那么程序会分配 1 MB 的未使用空间，SDS 的 buf 数组的实际长度将变成 30MB + 1MB + 1B。  
    通过这种空间预分配策略，Redis 可以 减少 连续执行字符串涉及长度修改操作所需的 内存重分配次数 。
2.  惰性空间释放，惰性空间释放用于优化 SDS 的字符串缩短操作：当 SDS 的 API 需要缩短 SDS 保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用 free 属性将这些字节的数量记录起来，并等待将来使用。

# 二、链表 #

每个链表节点使用一个 adlist.h/listNode 结构来表示：

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

使用 adlist.h/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;

下图是由一个 list 结构和三个 listNode 结构组成的链表：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 1]

# 三、字典 #

## 结构定义 ##

redis的字典使用哈希表作为底层实现，redis中的字典结构表示：

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

哈希表结构定义：

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

每个dictEntry结构都保存着一个键值对：

typedef struct dictEntry{ 
         //键
         void *key;
         //值
         union{ 
              void *val;
              uint64_tu64;
              int64_ts64;
         }v;
         //指向下一个哈希表节点，形成链表
         struct dictEntry *next;
    }dictEntry；

以下是普通状态下（没有进行rehash）的字典。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 2]  
next 属性是指向另一个哈希表节点的指针， 这个指针可以将多个哈希值相同的键值对连接在一起， 以此来解决键冲突（collision）的问题。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 3]  
每个哈希表节点都有一个 next 指针， 多个哈希表节点可以用 next 指针构成一个单向链表， 被分配到同一个索引上的多个节点可以用这个单向链表连接起来， 这就解决了键冲突的问题。

## rehash ##

随着操作的不断执行，哈希表保存的键值对会逐渐地增多或减少，为了让哈希表的负载因子维持在一个合理的范围内当哈希表保存的键值对数量太多或者太少时程序需要对哈希表的大小进行相应的扩展或者收缩

redis对字典的哈希表执行rehash的步骤如下;

1.  为字典ht\[1\]哈希表分配空间，这个哈希表的空间大小取决于要执行的操作以及ht\[0\]当前包含的键值对数量（ht\[0\].used）  
    1.1 如果执行的是扩展操作，那么ht\[1\]的大小为第一个大于等于ht\[0\].used\*2的n次幂  
    1.2 如果执行的是收缩操作，那么ht\[1\]的大小为第一个大于等于ht\[0\].used的2的n次幂
2.  将保存在ht\[0\]中的所有键值对rehash到ht\[1\]上面rehash指的是重新计算键的哈希值和索引值,然后将键值对放置到ht\[1\]哈希表的指定位置上
3.  当ht\[0\]包含的所有键值对都迁移到了ht\[1\]之后释放ht\[0\]将ht\[1\]设置为ht\[0\],并在ht\[1\]新创键一个空白哈希表为下一次rehash做准备

## 哈希表的扩展和收缩 ##

当以下条件中的任意一个被满足时，程序会自动开始对哈希表执行扩展操作

1.  服务器目前没有在执行bgsave命令或者bgrewriteaof命令、并且哈希表的负载因子大于等于
2.  服务器目前正在执行bgsave命令或者bgrewriteaof命令并且哈希表的负载因子大于等于5

其中哈希表的负载因子可以通过公式：  
负载因子 = 哈希表已保存节点数量 / 哈希表大小

load_factor = ht[0].used / ht[0].size

计算得出。  
比如说， 对于一个大小为 4 ， 包含 4 个键值对的哈希表来说， 这个哈希表的负载因子为：  
load\_factor = 4 / 4 = 1  
又比如说， 对于一个大小为 512 ， 包含 256 个键值对的哈希表来说， 这个哈希表的负载因子为：  
load\_factor = 256 / 512 = 0.5

## 渐进式rehash ##

rehash 动作并不是一次性、集中式地完成的， 而是分多次、渐进式地完成的。这样做的原因在于， 如果 ht\[0\] 里只保存着四个键值对， 那么服务器可以在瞬间就将这些键值对全部 rehash 到 ht\[1\] ； 但是， 如果哈希表里保存的键值对数量不是四个， 而是四百万、四千万甚至四亿个键值对， 那么要一次性将这些键值对全部 rehash 到 ht\[1\] 的话， 庞大的计算量可能会导致服务器在一段时间内停止服务。  
在进行渐进式rehash的过程中,字典会同时使用ht\[0\] ht\[1\]两个哈希表所以在渐进式rehash进行期间字典的删除 查找 更新等操作会在两个哈希表上进行 新添加到字典的键值对一律会保存到ht\[1\]里面则  
以下是哈希表渐进式 rehash 的详细步骤：

1.  为 ht\[1\] 分配空间， 让字典同时持有 ht\[0\] 和 ht\[1\] 两个哈希表。
2.  在字典中维持一个索引计数器变量 rehashidx ， 并将它的值设置为 0 ， 表示 rehash 工作正式开始。
3.  在 rehash 进行期间， 每次对字典执行添加、删除、查找或者更新操作时， 程序除了执行指定的操作以外， 还会顺带将 ht\[0\] 哈希表在 rehashidx 索引上的所有键值对 rehash 到 ht\[1\] ， 当 rehash 工作完成之后， 程序将 rehashidx 属性的值增一。
4.  随着字典操作的不断执行， 最终在某个时间点上， ht\[0\] 的所有键值对都会被 rehash 至 ht\[1\] ， 这时程序将 rehashidx 属性的值设为 -1 ， 表示 rehash 操作已完成。

渐进式 rehash 的好处在于它采取分而治之的方式， 将 rehash 键值对所需的计算工作均滩到对字典的每个添加、删除、查找和更新操作上， 从而避免了集中式 rehash 而带来的庞大计算量。

以下展示了一次完整的渐进式 rehash 过程：  
准备开始rehash：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 4]  
rehash索引0上的键值对  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 5]  
rehash索引1上的键值对  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 6]  
rehash索引2上的键值对  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 7]  
rehash索引3上的键值对  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 8]  
rehash执行完毕  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 9]

# 四、跳跃表 #

跳跃表(skiplist)是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。  
跳跃表支持平均O(logN)、最坏O(N)复杂度的节点查找。Redis使用跳跃表作为有序集合键的底层实现之一。  
Redis只在两个地方用到了跳跃表，一个是实现有序集合键，另一个是在集群节点中用作内部数据结构，除此之外，跳跃表在Redis里面没有其他用途。

跳跃表zskiplist结构的定义如下：

typedef struct zskiplist { 
        // 表头节点和表尾节点
        struct zskiplistNode *header, *tail;
        // 表中节点的数量
        unsigned long length;
        // 表中层数最大的节点的层数
        int level;
    } zskiplist;

跳跃表节点的实现由 redis.h/zskiplistNode 结构定义：

typedef struct zskiplistNode { 
        // 后退指针
        struct zskiplistNode *backward;
        // 分值
        double score;
        // 成员对象
        robj *obj;
        // 层
        struct zskiplistLevel { 
            // 前进指针
            struct zskiplistNode *forward;
            // 跨度
            unsigned int span;
        } level[];
    } zskiplistNode;

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 10]  
每次创建一个新跳跃表节点的时候， 随机生成一个介于 1 和 32 之间的值作为 level 数组的大小， 这个大小就是层的“高度”。  
在同一个跳跃表中， 各个节点保存的成员对象必须是唯一的， 但是多个节点保存的分值却可以是相同的： 分值相同的节点将按照成员对象在字典序中的大小来进行排序， 成员对象较小的节点会排在前面（靠近表头的方向）， 而成员对象较大的节点则会排在后面（靠近表尾的方向）。  
跳跃表的查找过程：  
![在这里插入图片描述][20200730221658186.png]  
跳跃表的优秀表现在于查询功能，以上图中查找值为90的节点为例，如果在链表中继续要进行顺序查找，需要进行9步才能查询到，而在上图的跳跃表中则需要6步就能完成，具体步骤如下：

1.  由最高层L4层开始查询，L4层当前节点值10，小于90，则取当前点的下一个节点120，大于90，这时降层到L3层查找；即查找值处于当前节点的值和当前节点下一节点的值之间时，降层查询。
2.  当前节点为10，L3层，取其下一节点40比较，小于90，进行下一步。
3.  节点40，取其下一节点80比较，小于90，进行下一步。
4.  节点80，取其下一节点120比较，大于90，此时将80设置为当前节点，并在当前节点上降层，进行下一步。
5.  当前节点80，L2层，取下一节点100比较，大于90，当前节点不变，直接降层，进行下一步。
6.  当前节点80，L1层，取下一节点90比较，等于90，结束，返回。

![在这里插入图片描述][20200730221720384.png]  
插入和删除操作，参考[数据结构（一）— 跳跃表][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70]: /images/20230208/4b6d98b436b54d1c9ba61063e512f576.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200729222301634.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200729222930293.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200729223235415.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200729225744541.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200729225857913.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200729230106720.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200729230141676.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/20200729230206649.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 9]: https://img-blog.csdnimg.cn/20200729230235397.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw_size_16_color_FFFFFF_t_70 10]: https://img-blog.csdnimg.cn/20200729235526293.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xpaHVheW9uZw==,size_16,color_FFFFFF,t_70
[20200730221658186.png]: https://img-blog.csdnimg.cn/20200730221658186.png
[20200730221720384.png]: https://img-blog.csdnimg.cn/20200730221720384.png
[Link 1]: https://www.lmlphp.com/user/7152/article/item/354954/