IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 《Redis设计与实现》笔记 -> 正文阅读

[数据结构与算法]《Redis设计与实现》笔记

第2章 简单动态字符串(SDS)

2.1 SDS 的定义

SDS 数据结构:

struct sdshdr {
    // 记录 buf 数组中已使用字节的数量,等于 SDS 所保存字符串的长度
    int len;
    // 记录 buf 数组中未使用字节的数量
    int free;
    // 字节数组,用于保存字符串
    char buf[];
} ;

SDS 遵循 C 字符串以空字符结尾的惯例,保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面,并且为空字符分配额外的 1 字节空间,以及添加空字符到字符串末尾等操作,都是由 SDS 函数自动完成的,所以这个空字符对于 SDS 的使用者来说是完全透明的。遵循空字符结尾这一惯例的好处是,SDS 可以直接重用一部分 C 字符串函数库里面的函数。

2.2 SDS 与 C 字符串的区别

2.2.1 常数复杂度获取字符串长度

直接通过 SDS 的 len 属性获得。

2.2.2 杜绝缓冲区溢出

当 SDS API 需要对 SDS 进行修改时,API 会先检查 SDS 的空间是否满足修改所需的要求,如果不满足的话,API 会自动将 SDS 的空间扩展至执行修改所需的大小,然后才执行实际的修改操作。

2.2.3 减少修改字符串时带来的内存重分配次数

通过未使用空间(free 属性),SDS 实现了空间预分配和惰性空间释放两种优化策略。

空间预分配

  • 如果对 SDS 进行修改之后,SDS 的长度(也即是 len 属性的值)将小于 1MB,那么程序分配和 len 属性同样大小的未使用空间,这时 SDS len 属性的值将和 free 属性的值相同。

  • 如果对 SDS 进行修改之后,SDS 的长度将大于等于 1MB,那么程序会分配 1MB 的未使用空间。

惰性空间释放

  • 当 SDS 的 API 需要缩短 SDS 保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用 free 属性将这些字节的数量记录起来,并等待将来使用。

2.2.4 二进制安全

C 字符串中的字符必须符合某种编码(比如 ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得 C 字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。

SDS 使用 len 属性的值而不是空字符来判断字符串是否结束,因此可以用来保存任何格式的数据。

2.2.5 兼容部分 C 字符串函数

虽然 SDS 的 API 都是二进制安全的,但它们一样遵循 C 字符串以空字符结尾的惯例,因此可以复用部分 C 字符串操作函数。

第3章 链表

除了列表数据结构,发布与订阅、慢查询、监视器等功能也用到了链表。Redis 服务器本身还使用链表来保存多个客户端的状态信息,以及使用链表来构建客户端输出缓冲区(output buffer)。

3.1 链表和链表节点的实现

链表结点数据结构:

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

链表数据结构:

typedef struct list {
    // 表头节点
    listNode * head;
    // 表尾节点
    listNode * tail;
    // 链表所包含的节点数量
    unsigned long len;
    // 节点值复制函数
    void *(*dup)(void *ptr);
    // 节点值释放函数
    void (*free)(void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
};

其中,dupfreematch 成员是用于实现多态链表所需的类型特定函数:

  • dup 函数用于复制链表节点所保存的值;
  • free 函数用于释放链表节点所保存的值;
  • match 函数则用于对比链表节点所保存的值和另一个输入值是否相等。

链表节点使用 void* 指针来保存节点值,并且可以通过 list 结构的 dupfreematch 三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

第4章 字典

4.1 字典的实现

4.1.1 哈希表

哈希表数据结构:

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

说明:

  • table 属性为一个指向哈希表节点的指针数组;
  • 之所以要存储一个值永远为 size-1sizemask 属性,是为了以微小的空间代价换取极致的性能。哈希表的每一次读写操作,都需要进行 hash & (size-1) 操作计算出索引值。计算一次 size-1 值,耗时微不足道,但是考虑百万次、千万次操作,累计的耗时就很可观了。

4.1.2 哈希表节点

哈希表节点数据结构:

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

4.1.3 字典

字典的数据结构:

typedef struct dict {
    // 类型特定函数
    dictlype *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引,当 rehash 未进行时,值为 -1
    in trehashidx;
};

type 属性和 privdata 属性是针对不同类型的键值对,为创建多态字典而设置的:

  • type 属性是一个指向 dictType 结构的指针,每个 dictType 结构保存了一簇用于操作特定类型键值对的函数,Redis 会为用途不同的字典设置不同的类型特定函数。
  • privdata 属性则保存了需要传给那些类型特定函数的可选参数。

dictType 数据结构:

typedef struct dictType {
    // 计算哈希值的函数
    unsigned int (*hashFunction)(const void *key);
    // 复制键的函数
    void *(*keyDup)(void *privdata, const void *key);
    // 复制值的函数
    void *(*valDup)(void *privdata, const void *obj);
    // 对比键的函数
    int (*keyCompare)(void *privdata, const void *keyl, const void *key2);
    // 销毁键的函数
    void (keyDestructor)(void *privdata, void *key);
    // 销毁值的函数
    void (*valDestructor)(void *privdata,void *obj);
};

普通状态下的字典:
普通状态下的字典

4.2 哈希算法

# 使用字典设置的哈希函数,计算键 key 的哈希值
hash = dict->type- >hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值,计算出索引值
# 根据情况不同,ht[x] 可以是 ht[0] 或者 ht[1]
index = hash & dict->ht[x].sizemask;

4.3 解决键冲突

Redis 的哈希表使用链地址法(separate chaining)来解决键冲突,每个哈希表节点都有一个 next 指针,多个哈希表节点可以用 next 指针构成一个单向链表,被分配到同一个索引上的多个节点可以用这个单向链表连接起来,这就解决了键冲突的问题。

因为 dictEntry 节点组成的链表没有指向链表表尾的指针,所以为了速度考虑,程序总是将新节点添加到链表的表头位置(复杂度为O(1)),排在其他已有节点的前面。

4.4 rehash

扩展和收缩哈希表的工作可以通过执行 rehash(重新散列)操作来完成,Redis 对字典的哈希表执行 rehash 的步骤如下:

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

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

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

其中哈希表的负载因子可以通过公式:

负载因子=哈希表已保存节点数量/哈希表大小
load_factor = ht[0].used / ht[0].size

根据 BGSAVE 命令或 BGREWRITEAOF 命令是否正在执行,服务器执行扩展操作所需的负载因子并不相同,这是因为在执行 BGSAVE 命令或 BGREWRITEAOF 命令的过程中,Redis 需要创建当前服务器进程的子进程,而大多数操作系统都采用写时复制(copy-on-write)技术来优化子进程的使用效率,所以在子进程存在期间,服务器会提高执行扩展操作所需的负载因子,从而尽可能地避免在子进程存在期间进行哈希表扩展操作,这可以避免不必要的内存写入操作,最大限度地节约内存。

另一方面,当哈希表的负载因子小于0.1时,程序自动开始对哈希表执行收缩操作。

COW奶牛!Copy On Write机制了解一下

  数据结构与算法 最新文章
二叉树lc题集
关于单链表及其常用操作的简单实现
二叉排序树(二叉搜索树)的算法实现
leetcode-python3-1759. 统计同构子字符串的
4.寻找两个正序数组的中位数
【leetcode】Nim 游戏c++
算法基础之贪心
LeetCode 2021-07-14
C++使用cuBLAS加速矩阵乘法运算
剑指offer - 调整数组顺序使奇数位于偶数前
上一篇文章      下一篇文章      查看所有文章
加:2021-07-17 12:36:27  更:2021-07-17 12:36:29 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2021年9日历 -2021/9/27 3:21:19-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码