一、简单动态字符串SDS

SDS: Simple Dynamic String, 简单动态字符串

1.1 SDS结构

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

1.2 SDS与C字符串的区别

1.2.1 获取字符串长度的时间复杂度是O(1)

C字符串中不记录自身长度，通过判断结尾的空字符\0，来确定长度。所以获取字符串长度需要遍历到字符串结尾，时间复杂度是O(N)；
SDS内部有len属性记录字符串长度，设置和更新SDS时，API会自动更新len的值。所以，获取字符串长度可以直接读取len的值，时间复杂度是O(1)；

1.2.2 杜绝缓冲区溢出

C字符串不记录本身长度，通过结尾的空字符\0判断结束，在扩展字符串时，如果不预先分配足够的空间，会造成缓冲区溢出；
SDS的API在需要对SDS进行修改时，会先检查SDS的空间是否满足需求，如果不满足会自动将SDS的空间大小扩展至所需的大小，然后才执行扩展操作；
总结：

C字符串的API是不安全的，在字符串扩展时不执行空间检查与分配，需要使用者自己执行空间检查与分配操作，如果忘记执行，可能会造成缓冲区溢出；
SDS的API是安全的，在字符串扩展时封装了空间检查与空间分配，不需要使用者自己执行，杜绝了缓冲区溢出的可能；

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

每次增长或缩短一个C字符串时，程序都需要对保存这个C字符串的数组进行一次内存重分配操作：

增长字符串时，程序需要先通过内存重分配来扩展底层数组的空间大小，如果忘了这一步会产生缓冲区溢出；
缩短字符串时，程序需要通过内存重分配来释放字符串不再使用的那部分空间，如果忘记这一步会产生内存泄漏；

为什么要减少内存重分配次数：

内存重分配涉及复杂的算法，并且可能需要执行系统调用，通常是一个比较耗时的操作；
Redis作为数据库，经常被用于速度要求严苛，数据被频繁修改的场合，如果频繁的执行内存重分配，会对性能产生影响；

SDS通过free属性记录未使用空间，实现了空间预分配和惰性空间释放两种优化策略，来减少内存重分配次数：

空间预分配：当SDS的API对一个SDS进行修改，并且需要进行空间扩展时，不仅会为SDS分配修改所必须的空间，还会为SDS分配额外的未使用空间(由free记录)。
- 如果对SDS进行修改后，SDS的长度(即len的值)小于1MB时，那么程序分配和len属性同样大小的的未使用空间；
- 如果对SDS进行修改后，SDS的长度(即len的值)大于等于1MB，那么程序会分配1MB的未使用空间；
惰性空间释放：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节数量记录起来，并等待将来使用。
总结：
- 通过空间预分配，将SDS连续增长N次字符串所需的内存重分配次数，从必定N次降低为最多N次；
- 通过惰性空间释放，SDS避免了缩短字符串时所需的内存重分配操作，并为将来可能有的增长操作提供了优化；

1.2.4 二进制安全

C字符串中字符必须符合某种编码(比如ASCII)，由于使用空字符表示字符串结尾，所以除了字符串的末尾外，字符串里面不能包含空字符(\0),否则最先被程序读入的空字符将被误认为是字符串的结尾。所以C字符串只能保存文本数据，而不能保存图片、音频、视频、压缩文件这样的二进制数据；
SDS不使用空字符来判断字符串结束，而是使用len属性来判断，所以SDS的数组可以保存一系列的二进制数据。SDS的API都会以处理二进制的方式来处理SDS存放在buf数组里的数据，不会对其中的数据做任何限制、过滤、假设，数据在写入时是什么样，被读取时就是什么样；

1.2.5 兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但他们都遵守C字符串以空字符结尾的惯例：这些API总会将SDS保存的数据的末尾设置空字符，并且为buf数组分配空间时多分配一个字节来容纳这个空字符。这是为了让那些保存文本数据的SDS可以重用一部分C语言里的字符串函数；

二、链表

2.1 节点结构

链表节点使用listNode结构(链表中每个结点的结构)

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

每个结点都有指向前置节点的指针和指向后置节点的指针，实现的是一个双向链表；
使用void * 指针来保存节点值，可以保存各种不同类型的值；

2.2 链表结构

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;

获取链表长度时间复杂度O(1): 链表中带长度计数器len，可以在O(1)里直接读取链表长度；
无环：表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点；

三、字典

字典，又称为map,是一种用于保存键值对的抽象数据结构；
Redis所使用的C语言没有内置的这种数据结构，因此Redis构建了自己的字典实现；

3.1 字典的实现

哈希节点

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

哈希表节点保存着一个键值对；
key属性保存着键值对中的键；
v属性保存着键值对中的值，其中值可以是一个指针，或者一个uint64_t整数，又或者是int64_t整数；
next属性指向另一个哈希表节点的指针，这个指针可以将多个哈希值相同的键值对连接在一起。使用链地址法解决hash冲突；

哈希表

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

table属性是一个数组，数组中的元素是一个指向哈希节点dictEntry的指针；
size属性记录了哈希表的大小，也即table数组的大小(hash链地址法中数组的大小)；
used属性记录哈希表目前已有节点的数量(hash节点总数);
sizemask属性值总是等于size-1,size的值总是2的n次方，所以sizemask是2的n次方-1，通过按位与运算能够根据hash值快速的计算出索引位置(参考java中hashmap的实现);

字典

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

/**
 * 一簇用于操作特定类型键值对的函数 
 */
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 *key1, const void *key2);
    
    // 销毁键的函数
    void (*keyDestructor) (void *privdata, void *key);
    
    // 销毁值的函数
    void (*valDestructor) (void *privdata, void *obj);
}

type属性是一个指向dictType结构的指针，每个dictType结构保存了一簇用于操作特定类型键值对的函数，Redis会为用途不同的字典设置不同的类型特定函数；
privdata属性则保存了需要传给那些类型特定函数的可选参数；
ht属性是一个包含两个项的数组。数组中每个项都是一个dictht哈希表，一般情况下只使用ht[0],ht[1]用于进行rehash，只会在对ht[0]进行rehash时使用；

3.2 链地址法存储

Redis的哈希表使用链地址法解决哈希冲突；
向链表添加元素时，使用头插法添加到链表表头，添加节点时时间复杂度是O(1)；

3.3 收缩与扩容rehash

哈希表的负载因子(load=ht[0].used/ht[0].size)维护在一个合理范围内，当负载因子过高时进行扩容，过低时进行收缩；
负载因子小于0.1时，执行缩容；
如果服务器目前没有执行BGSAVE或BGREWRITEAOF命令，则哈希表的负载因子大于等于1时，执行扩容；
如果服务器目前正在执行BGSAVE或BGREWRITEAOF命令，则哈希表的负载因子大于等于5时，执行缩容；
- 因为：执行BGSAVE或BGREWRITEAOF命令时，Redis需要创建当前服务器进程的子进程，而大多数操作系统都采用写时复制技术来优化子进程的使用效率，所以在子进程存在期间，服务器会提高执行扩展操作所需的负载因子，从而尽可能的避免在子进程存在期间进行哈希表扩展操作，可以避免不必要的内存写入操作，最大限度的节约内存；
- 写时复制技术：是一种推迟甚至避免拷贝数据的技术，创建子进程时，并不立即把所有的资源复制给子进程，而是让父子进程共享同一个地址空间，只有在需要写入时，才会复制地址空间，从而使各个进程拥有各自的地址空间。也就是说资源的复制是在需要写入的时候才进行，在此之前以只读方式共享。
扩容时的新数组大小为：第一个大于等于ht[0].used*2且值为2的n次方的数字；
缩容时的新数组大小为：第一个大于等于ht[0].used且值为2的n次方的数字；
哈希表一直使用的是ht[0],只有在rehash过程中会使用ht[1],rehash完成后会将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表，为下一次rehash做准备；

3.4 扩容或收缩步骤

当ht[0]的负载因子超过合理范围时，执行扩展或缩容，步骤如下：

为字典ht[1]哈希表分配空间。根据ht[0].used计算需要分配给ht[1]的数组大小；
将保存在ht[0]中的所有键值对rehash到ht[1]上面，rehash会重新计算键的哈希值和索引值，然后将键值对放置到ht[1]哈希表指定的位置上；
当ht[0]包含的所有键值对放置到ht[1]之后(ht[0]变成空表)，释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表，为下一次rehash做准备；

3.5 渐进式rehash

当ht[0]中键值对数量较多时，如果一次性将全部的键值对rehash到ht[1],那么庞大的计算量可能会导致服务器在一段时间内停止服务；
所以采用分多次、渐进式地将ht[0]里面的键值对慢慢的rehash到ht[1];

渐进式rehash的步骤：

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

总结说明

渐进式rehash的操作是将ht[0]上的键值对rehash到ht[1]的过程分布到每次对字典执行添加、删除、查找或者更新操作时执行，从而避免了一次性rehash大量数据带来的服务器短时间内的大量计算；
在渐进式rehash期间，字典的删除、查找和更新操作会在ht[0]和ht[1]两个哈希表上进行；
在渐进式rehash期间，字典的添加操作只会在ht[1]上进行，从而保证了ht[0]中的键值对数量只减不增，并随着rehash操作的执行最终变成空表；

四、跳跃表

4.1 有序链表

有序链表的搜索：由于链表的搜索不能使用二分查找，所以查找的复杂度为O(N);
有序链表查找优化：如果把一些中间元素提取出来作为索引，在查找时，先查找索引，确定节点范围后再向下查找，从而减少比较次数，提高查找效率；

4.2 跳跃表

跳跃表具有如下性质：

由很多层结构组成；
每一层都是一个有序的链表；
最底层的链表(Level 1 层)包含所有元素；
如果一个元素出现在Levle i层，则它在Level i之下的所有层都会出现(上层索引是从下层抽取的节点)；
每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素；

4.3 Redis中的跳跃表

跳跃表：是一种有序数据结构，通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的；

Redis中的跳跃表由zskiplistNode和zskiplist两个结构实现。

如下图，是一个有三个节点{<o1,1.0>,<o2,2.0>,<o3,3.0>}的跳跃表；
表头节点和其他节点构造一样，都是zskiplistNode类型，表头节点的后退指针、分值、成员对象不会被用到；

Redis跳跃表结构

4.3.1 跳跃表节点：zskiplistNode

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

后退指针：从表尾向表头方向访问节点，每个节点只有一个后退指针，所以每次只能后退至前一个节点；
分值：double类型的浮点数，跳跃表中所有节点都按照分值从小到大排序；
成员：是一个指针，指向一个字符串对象，而字符串对象则保存着一个SDS值(ZSet里面的key值)；
- 各个节点保存的成员对象必须是唯一的(即ZSet里的key唯一)，但是多个节点保存的分值却可以是相同的。分值相同的节点按照成员对象的顺序进行排序；
层：level数组可以包含多个元素，每个元素包含一个指向其他节点的指针，程序可以通过这些层来加快访问其他节点的速度；
- 每次创建一个新跳跃表节点时，程序根据幂次定律(越大的数据出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小，这个大小就是层的高度；
前进指针:指向该层后续节点的指针；
跨度：用于记录两个节点之间的距离；

4.3.2 跳跃表 zskiplist

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

header:指向跳跃表的表头节点；
tail: 指向跳跃表的表尾节点；
length:记录跳跃表的长度；
level:记录跳跃表目前最高层数(表头节点的层数不计算在内)

五、整数集合

整数集合(intset)是用于保存整数值的抽象数据结构，它可以保存类型为int16_t、int32_t、int64_t的整数，并且保证集合中不会出现重复元素。是集合(Set)的底层实现之一。
当一个集合只包含整数值元素，并且整个集合的元素数量不多时，Redis就会使用整数集合作为集合键的底层实现；
整数集合的底层实现是一个数组(contents[]),数组中的值按从小到大有序排列，并且数组中不包含重复元素；

5.1 数据结构

typedef struct intset{
    // 编码方式
    uint32_t encoding;
    
    // 集合中包含的元素数量
    uint32_t length;
    
    // 保存元素的数组
    int8_t contents[];
}intset

length：记录整数集合中包含的元素数量，即contents数组的长度；
encoding：决定contents数组中保存的数据类型，取值有：INTSET_ENC_INT16、INTSET_ENC_INT32、INTSET_ENC_64;
contents：数组中并不保存任何int8_t类型的值，真正类型取决于encoding属性的值；各个项在数组中按值从小到大的顺序排列，并且数组中不包含任何重复项；
- encoding取值INTSET_ENC_INT16时，数组中每一项都是一个int16_t类型的整数值；数组所占空间大小为：length * 16 位;
- encoding取值INTSET_ENC_INT32时，数组中每一项都是一个int32_t类型的整数值；数组所占空间大小为：length * 32 位;
- encoding取值INTSET_ENC_INT64时，数组中每一项都是一个int64_t类型的整数值；数组所占空间大小为：length * 64 位;

5.2 数据类型升级

整数集合的数据初始类型并不用最长类型int64_t保存，而是从最短类型int16_t保存，当要添加到集合中的新元素超过现有类型长度时，集合先对现有元素进行类型升级，然后才将新元素添加到集合里；
升级的好处：

节约空间：如果不使用动态升级，则数组类型需要使用最长类型int64_t才能保存所有类型的整数，这样一来，即使添加到整数集合里面的都是int16_t类型或者int32_t类型的值，数组都需要使用int64_t类型的空间去保存，从而出现浪费内存的情况；
提示灵活性：C语言是静态类型语言，通常不会将两种不同类型的值放在同一个数据结构里，使用整数集合自动升级来适应新元素，可以同时将int16_t、int32_t、int64_t类型的整数添加到集合里，而不必担心出现类型错误；

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

六、压缩列表

压缩列表是Redis为节约内存而开发的顺序型数据结构；
当一个列表键只包含少量列表项，并且每个列表项要么是小整数，要么是短字符串时，Redis就会使用压缩列表来做列表键的底层实现；
压缩列表是列表键、哈希键和有序集合键的底层实现之一；

6.1 数据结构

压缩列表(ziplist)由列表和列表节点构成

列表节点

+-----------------------+----------+--------+
| previous_entry_length | encoding | content|
+-----------------------+----------+--------+

列表节点由三部分组成：previouse_entry_length、encoding、content;
previouse_entry_length：记录压缩列表中前一个节点的长度；字段长度是1字节或5字节：
- 当前一个列表节点长度小于254字节时，previouse_entry_length属性用1个字节记录；
- 当前一个列表节点长度大于等于2554字节时，用5个字节记录；
encoding：记录节点的content属性所保存数据的类型以及长度：
- 字节数组：开头两位保存字节数组编码，去除最高两位数据记录数组长度，encoding属性长度有1字节(00开头)、2字节(01开头)、5字节(10开头)；
- 整数数组：开头两位(11)表示整数数字，后续两位保存编码长度(00:int16_t类型、01:int32_t类型、11:int64_t类型)
content：保存节点的值，可以是一个字节数组或者整数，值的类型和长度由encoding属性决定；

列表

+---------+--------+-------+--------+-----+--------+-------+
| zlbytes | zltail | zllen | entry1 | ... | entryN | zlend |
+---------+--------+-------+--------+-----+--------+-------+

zlbytes：uint32_t，4字节，记录整个压缩列表占用的内存字节数；
zltail：uint32_t，4字节，记录压缩列表表尾节点举例起始地址有多少字节；
zllen：uint16_t，2字节，记录压缩列表包含的节点数量，当属性值大于UINT16_MAX=65535时，需要遍历压缩列表才能及时节点真实数量；
entryX：列表节点，长度不定，由保存的内存决定；
zlend：uint8_t，1字节，特殊值0xFF用于标记压缩列表的末端；

6.2 特性

压缩列表是一个顺序存储结构；
压缩列表可以通过zltail无需遍历整个列表，就能确定表尾节点的地址；
通过节点的previous_entry记录的上一个节点长度，可以从表尾向表头遍历；

6.3 连锁更新

列表节点中使用previouse_entry属性记录上一个节点的长度，如果在前边添加一个节点，该节点的长度超过254字节(previouse_entry需要用5个字节保存)，导致previouse_entry属性需要扩容,而扩容时刚好导致当前节点长度超过254字节，则后续节点的previouse_entry属性也需要扩容，依次类推，会导致节点连锁更新；
删除节点时也可能会导致连锁更新,当删除的节点长度小于245字节，而删除节点的前一个节点长度超过254字节，则节点删除后，会导致后续节点的previouse_entry属性扩容，当扩容后刚好后续节点长度超过254，依次类推，会导致后续节点的连锁更新；
连锁更新发生的情况是：一个压缩列表中，有多个连续的、长度介于250字节到253字节的节点(previouse_entry从1字节扩容到5字节时刚好导致该节点长度超过254字节)。

原文链接：https://blog.csdn.net/godloveayuan/article/details/106570623

Redis六种存储结构详解

文章目录