redis设计与实现读书笔记——底层数据结构

简单动态字符串

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

    //字节数组，用于保存字符串
    char[] buf;
}

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

C字符串要获取长度必须遍历整个字符串；而对于SDS，len记录了字符串长度。

• 杜绝缓冲区溢出

与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性：当SDSAPI需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。

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

1. 空间预分配：空间预分配用于优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间：如果修改后的SDS长度将小于1MB，那么程序分配和len属性同样大小的问使用空间，free = len；如果修改后的SDS长度将大于等于1MB，那么程序分配1MB的未使用空间，free = 1MB。
2. 惰性空间释放：惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是用free属性将这些字节的数量记录下来，并等待将来使用

• 二进制安全

如果有一种使用空字符串来分割多个单词的特殊数据格式，那么这种格式就不能使用C字符串来保存，因为C字符串所用的函数只会识别出第一个字符串而忽略空字符串后面的字符串；而SDS使用len记录了字符串长度，就不会出现这个问题。

链表

//链表
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 *next;

    //节点的值
    void *value;
}listNode;

字典

typedef struct dict{
    
    //类型特定函数
    dictType *type;
    
    //私有数据
    void *privdata;

    //哈希表
    dictht ht[2];

    //rehash索引：当rehash不在进行时，值为1
    int trehashidx;

}dict;

=============================================================================

//哈希表
typedef struct dictht{
    
    //哈希表数组
    dictEntry **table;

    //哈希表大小
    unsigned long size;

    //哈希表大小掩码，用于计算索引值，总是等于size-1
    unsigned long sizemask;

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

}dictht;

=============================================================================

typedef struct dictEntry{
    
    //键
    void *key;

    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    }v;

    //指向下个哈希表节点，形成链表
    struct dictEntry *next;
}dictEntry;

• 哈希算法

#使用字典设置的哈希函数，计算键key的哈希值
hash = dict->type->hashFuction(key);

#使用哈希表的sizemask属性和哈希值算出所引致
index = hash & dict->ht[x].sizemask;

• 解决键冲突

redis的哈希表使用链地址法解决键冲突，每个哈希表节点都有一个next指针，多个哈希表节点可以用next指针构成一个单向链表，这就解决了键冲突问题

• rehash

为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的扩展或收缩：

1. 为字典的ht[1]哈希表分配空间：如果执行的是扩展操作，那么ht[1]的大小为第一个大于等于ht[0].used*2的2^n；如果执行的是收缩操作，那么ht[1]的大小为第一个大于等于ht[0].used的2^n。
2. 将保存在ht[0]中的所有键值对rehash到ht[1]上面
3. 释放ht[0]，将ht[1]设置为ht[0]，并在ht[1]新建一个空白哈希表，为下一次rehash做准备

• 哈希表的扩展与收缩

1. 扩展：服务器目前没有在执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于1；服务器目前在执行BGSAVE或者BGREWRITEAOF，并且哈希表负载因子大于等于5
2. 收缩：当哈希表的负载因子小于0.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操作已完成。

跳跃表

typedef struct zskiplist{

    //表头节点和表尾节点
    structz skiplistNode *header,*tail;

    //表中节点的数量
    unsigned long length;

    //表中层数最大的节点的层数
    int level;

}zskiplist;

============================================================================

typedef struct zskiplistNode{
    
    //后退指针
    struct zskiplistNode *backward;

    //分值
    double score;

    //成员对象
    robj *obj;

    //层
    struct zskip;istLevel{

        //前进指针
        struct zskiplistNode *forward;

        //跨度
        unsigned int span;

    }level[];
    
}zskiplistNode;

 整数集合

typedef struct intset{

    //编码方式
    uint32_t encoding;

    //集合包含的元素数量
    uint32_t length;

    //保存元素的数组
    int8_t contents[];

}intset;

• 升级

每当我们要将一个新元素添加到整数集合里面，并且新元素的类型比整数集合现有的所有元素类型都要长时，整数集合需要先进行升级，然后才能将新元素添加到集合中去：

1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
2. 将底层数组现有的所有元素都转换成与新元素相同的类型，并将类型转换后的元素放到正确的位置上，而且在放置元素的过程中，需要维持底层数组的有序性质不变。
3. 将新元素添加到底层数组里面

• 降级

整数集合不支持降级，一旦对数组进行了升级，编码就会一直保持升级后的状态

压缩列表

对象

• 字符串对象
• 列表对象：链表|压缩表
• 集合对象：整数集合|字典表
• 哈希对象：字典表|压缩表
• 有序集合对象：压缩表|跳跃表