《redis设计与实现》第一版 阅读笔记（未看完）

一、文档介绍

本文仅作为本人读书笔记使用，不对其中内容做解释，记录以本人可以看懂为标准

原书链接：https://redisbook.readthedocs.io/en/latest/index.html

该书以简明的方式主要介绍了Redis内部的运行机制，从数据结构到服务器构造，值得推荐

                                                                                      第一部分  内部数据结构

Redis内存所使用的数据结构与算法

一、SDS(Simple Dynamic String) 简单动态字符串

1. SDS作用

  • 实现字符串对象。Redis内字符串对象并不代表就是字符串值，字符串对象还可以保存lang类型的值，包含字符串的字符串对象包含的才是SDS值
  • 取代C默认的char*类型。char*类型有很多限制，比如说数据追加与长度计算。在Redis内，客户端传递给服务器的aof缓存、协议内容、回复等都是SDS类型的存储

2. Redis中的字符串

Redis内的字符串不仅包含结尾的字符串，还包含简单的字节数组，还包括其他格式的数据等内容

Redi使用SDS类替换C语言默认字符串考虑到两点：高效、二进制安全（程序不对字符串里面保存的数据进行任何假设）

3. SDS实现

typedef char * sds;

struct sdshdr {
    len = 11;
    free = 0;
    buf = "hello world";  // buf 的实际长度为 len + 1
};

sds 是 char* 的一个别名

结构体里包含了三个属性：len、free、buffer三个属性

通过len属性可以O（1）的进行长度计算；通过buf分配额外的空间，并使用free记录未使用空间的大小，sds可以让执行追加操作所需的内存重分配次数大大减少；在char *实现中，追加只能通过重分配内存实现

于此同时对SDS的操作必须正确处理len与free属性

4. 如何减少内存重分配次数

创建：当调用set命令创建SDSHDR时，BUF不多申请，刚好给够所需的，free=0

追加：当再次追加的时候，如果free的长度大于所需，就直接append进去，不然的话，会给二倍的内存，但是如果大于SDSHDR允许的MAX_Preallocation，最大预分配，不会翻倍，会再给一个MAX_Preallocation

释放时间：当键值被删除时预分配空间会被删除；当重启Redis时，预分配的空间也会被释放，每个SDS对应的SDSHDR不存在预分配空间，BUFF大小等于所需空间

SDS是Redis对应的字符串表示，SDSHDR是对应的存储类型

二、双端链表

1. 双端链表作用

  • 双端链表是Redis列表（List）结构的底层实现之一，另一个是压缩列表，因为压缩列表占用的额内存更少，在需要的时候才会从压缩列表转换为双端链表
  • 事务模块使用双端链表依序保存输入的命令
  • 服务器模块使用双端链表来保存多个客户端
  • 订阅/发送模块使用双端链表来保存订阅模式的多个客户端
  • 事件模块使用双端链表来保存时间事件（time event）

2. 双端链表的实现

 双端链表是由两部分组成的，list与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;

listNode的value值的类型是void *，方法返回值的类型也是void *，代表对值得类型不做限制

3. 迭代器

typedef struct listIter {

    // 下一节点
    listNode *next;

    // 迭代方向
    int direction;

} listIter;

迭代器内保存一个listNode，并且指明迭代的方向

三、字典

 1. 字典的作用

  • 实现数据库键空间
  • 用作hash类型键的底层实现之一

Redis是一个键值对数据库，数据库中的键值对由字典保存，每个数据库都有一个字典，这个字典称为键空间（Key Space）,当用户添加一个键值对到数据库中时，无论键值对是什么类型，程序就会将该键值对添加到键空间

hash类型键的底层实现除了字典外就是压缩列表

2. 字典的实现

字典的实现方式有很多种，例如链表与数组，优点：简单   缺点：只适用于元素不多的情况

                                          哈希表，      优点：高效简单

                                          平衡树，      优点：稳定，排序操作更高效  缺点：实现更复杂

Redis采用哈希表实现字典，哈希表的子结构是dictEntry

dictEntry的实现

/*
 * 哈希表节点
 */
typedef struct dictEntry {

    // 键
    void *key;

    // 值
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;          //union关键字 三种中只能包含其中一种

    // 链往后继节点
    struct dictEntry *next;

} dictEntry;

next指针指向另一个dircEntry节点，之所以存在链是因为有的键值可能会哈希成同一值，于是采用链地址法来处理哈希值碰撞问题，当不同的键拥有相同的哈希值时，哈希表就将这些键链接起来

dircht（dirc hash table）的实现

/*
 * 哈希表
 */
typedef struct dictht {

    // 哈希表节点指针数组（俗称桶，bucket）
    dictEntry **table;

    // 指针数组的大小
    unsigned long size;

    // 指针数组的长度掩码，用于计算索引值
    unsigned long sizemask;

    // 哈希表现有的节点数量
    unsigned long used;

} dictht;

**table是一个数组，俗称桶（bucket）,每一个值对应一个dictEntry结构的指针

size代表数组大小，sizemask意思不清楚，used就是哈希表现有的键的数量

字典的定义

/*
 * 字典
 *
 * 每个字典使用两个哈希表，用于实现渐进式 rehash
 */
typedef struct dict {

    // 特定于类型的处理函数
    dictType *type;

    // 类型处理函数的私有数据
    void *privdata;

    // 哈希表（2 个）
    dictht ht[2];

    // 记录 rehash 进度的标志，值为 -1 表示 rehash 未进行
    int rehashidx;

    // 当前正在运作的安全迭代器数量
    int iterators;

} dict;

字典的实现使用了两个hash table，0号哈希表是字典主要使用的哈希表，1号哈希表只有当程序对0号哈希表进行rehash的时候才会使用

3. rehash

rehash：当键非常多，远大于table数组长度时，数组内的每个值将退化成一条链，hash Table的优势将不复存在，于是需要进行rehash操作，对hash table进行扩容，将比率尽量维持在1:1左右

rehash触发的条件有两种：1. 键与数组长度比率ratio>=1 && dict_can_resize为真

                                    2. ratio>=dict_force_resize_ratio dict_force_resize_ratio是强制改变大小的比率

当数据库执行后台持久化任务时，为了最大化利用系统的copy on write机制，程序会暂时将dict_can_resize置为假，避免执行自然resize，总而言之就是为了效率

4. 字典的收缩

与rehash相反

收缩操作是程序手动执行的，扩展操作是自动执行的，收缩程序决定填充率是多少的时候来执行收缩程序

对哈希表的扩展和收缩都是分多次、渐进式的进行的

四、跳跃表

跳跃表是一个有层次的链表，增删改查的时间复杂度都是O(logN)

跳跃表解释：http://blog.jobbole.com/111731/ 

2019-03-07  11:13:52  有时间再看吧 得有输出才行啊 干点活吧

跳跃表是为了提高链表的增删改查，对于一个链表来讲，选出一些领导者在上一层，于是在增删改查的时候，首先在上一层进行选择区间之后再下沉到下一层，提高了效率

1. 跳跃表的实现

跳跃表的实现

typedef struct zskiplist {

    // 头节点，尾节点
    struct zskiplistNode *header, *tail;

    // 节点数量
    unsigned long length;

    // 目前表内节点的最大层数
    int level;

} zskiplist;

 跳跃表节点（层）的实现

typedef struct zskiplistNode {

    // member 对象
    robj *obj;

    // 分值
    double score;

    // 后退指针
    struct zskiplistNode *backward;

    // 层
    struct zskiplistLevel {

        // 前进指针
        struct zskiplistNode *forward;

        // 这个层跨越的节点数量
        unsigned int span;

    } level[];

} zskiplistNode;

Q&A：

为什么Redis要使用C而不是C++的STL容器？

猜想：可能是基于内存或者效率的考虑吧

SDS如何实现二进制安全的？

跳跃表与平衡树比较？

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/Flower-Z/p/10488372.html