Redis设计与实现（一）——数据结构与对象

Redis中的数据结构

  • 简单动态字符串
  • 链表
  • 字典
  • 跳跃表
  • 整数集合
  • 压缩列表
  • 对象

1.简单动态字符串

Redis底层是用C语言实现的，所以，在很多数据结构上可以直接使用C语言中已经存在的数据结构和库函数。

Redis的字符串数据结构并没有直接使用C语言的字符数组，而是用了一个结构体，名为简单动态字符串（SDS），这是Redis默认实现字符串的数据结构。

SDS的定义

SDS由一个C语言结构体定义，里面包含当前已使用长度、未使用长度和字节数组。

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

结构图示如下：
在这里插入图片描述
因为Redis使用C语言实现，同时为了可以使用C中的很多库函数，所以，需要遵照C数组的惯例，在数组末尾用一个'/0'表示数组结尾。因此，给字符串分配空间的时候都会多一个字节。

SDS的功能

  • 保存字符串值。
  • 用作缓冲区，包括AOF模块的缓冲区，客户端状态中的输入缓冲区。

SDS的特点

1.常数时间获取字符串的长度

在C语言环境下，如果需要获取一个数组的长度，就需要遍历这个数组，并进行计数，直到遍历到末尾的结尾字符，就能计算出长度。这样做的问题就是每次想要获取字符串的长度时间复杂度都是O(n)的，对于需要经常获取字符串长度的应用，就会造成很大的开销。

而SDS中，利用空间换时间，通过维护结构体中的一个整型，保存当前结构体所表示的字符串的长度，就可以在O(1)的时间获取长度。这样做的代价就是需要增加一个整型的内存，同时也需要在变更字符串的时候，需要对这个整型进行维护，也会带来开销。

2.防止缓冲区溢出

如果仅仅对字符数组进行操作，给数组添加了大于其分配了的内存的数据，就会导师溢出，将数据覆盖到了后面的数组上，造成错误。

而SDS中，对添加数据的操作都会进行一个扩容检查，如果原有的空间无法装下添加的数据，就会对数组进行一次扩容操作。

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

首先，对于内存的重分配是一个比较耗时的工作。

如果每次添加数据和删减数据，都对数据存储数组进行一个重分配修改，那么造成的开销就很大。SDS采用以下两种策略进行一个优化：

  • 空间预分配
    对于数组的扩容操作，每次都会扩得多一点，而不是刚刚好。如果数组大小小于1MB，每次增加一倍；如果数组大小大于30MB，那么每次扩容增加1MB。这样下一次数据增加的时候，直接添加就完了，不需要立马又要扩容。
  • 惰性空间释放
    对于数据的数据删除，不需要马上减少数组的空间，而是动一动表示使用数据长度和空闲数据长度的两个值就行了。但也需要避免空间浪费，SDS提供API实现真正的空间释放。

4.二进制安全

Redis中的字符串图片、音频等很多数据，其数据基本单元是字节而不是字符，所以，不能让字符数组中的'/0'表示数组的结尾。

SDS的中的数组不只是可以用来保存字符，而是通过字节形式保存一系列二进制数据，通过len和free，就可以避免使用'/0'结尾。

5.兼容C字符串函数库

对于很多字符串的操作，SDS的字符数组和C的普通字符数组是一样的，也都有'/0'，那么就可以重用<string.h>中的部分库函数，避免了代码的重复。

总结

比起C字符数组，SDS有以下优点：

  1. 常数复杂度获取字符串的长度；
  2. 杜绝缓冲区溢出；
  3. 减少修改字符串长度时需要内存重新分配的次数；
  4. 二进制安全；
  5. 兼容部分C字符串函数。

2.链表

C语言中没有实现链表的数据结构，所以Redis构建了自己的链表实现。这里的链表就是很普通的双向链表。

链表的定义

链表由链表节点和链表构成。其中链表节点的定义如下：

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

从这里可以看出，redis中的链表是双向链表。

链表的结构定义如下：

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

其中，dump函数用于复制表系欸但所保存的值；free用于释放链表节点所保存的值；match函数用于对比链表节点所保存的值与另一个输入值是否相等。

链表结构示例如下图所示：
在这里插入图片描述

链表的功能

链表在Redis中使用很广泛，提供了如下特性：

  • 高效的节点重排；
  • 顺序性的节点访问方式；
  • 通过增删节点来灵活地调整链表的长度。

在Redis中，使用链表数据结构的地方主要有：

  • 链表键
  • 发布与订阅
  • 慢查询
  • 监视器
  • 保存多个客户端的状态信息
  • 构建客户端输出缓冲区

链表的特点

  • 双向：每个节点都有前置指针和后置指针，这样获取某个节点的前置和后置节点的时间复杂度都是O(1)的。
  • 无环：表头节点前置指针和表尾的后置指针指向空，这样对链表的访问以null为终点。
  • 具有表头节点和表尾节点：这样可以分别从表头或者表尾开始对标进行遍历。
  • 存有表节点的个数：这样获取表长度的时间复杂度是O(1)的。
  • 多态：表节点中值的指针是用过void*来定义的，并且还可以通过dup、free、match三个属性给节点值设置类型的特定函数，所以，可以用链表保存不同类型的数据。

3.字典

字典就是映射，在python中也称为字典，是用于保存键值对的数据结构，键唯一，值可以重复。

字典的定义

Redis字典使用哈希表作为底层的实现，其实大致的原理和JDK1.8之前的HashMap差不多，都采用基于链表的拉链法解决哈希冲突。

字典中的结构定义主要分为哈希表、哈希表节点以及字典的实现。

1.哈希表

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

其中table就是一个存储哈希链表头节点的数组。

2.哈希表节点

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

这里值的定义很奇怪，是一个C语言的联合体，什么是联合体呢，就是里面的变量是共享一块空间的，彼此之间可能会相互覆盖对方，所以，同时只能使用其中的一个类型。这里为了实现值的多态，所以，采用这种联合体的方式，就能实现不同类型数据的存储。

next用于形成链表，用于解决哈希冲突的问题。

3.字典

typedef struct dict 
{
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];
    // rehash 索引
    // 当 rehash 不在进行时，值为 -1
    int rehashidx; /* rehashing not in progress if rehashidx == -1 */
    // 目前正在运行的安全迭代器的数量
    int iterators; /* number of iterators currently running */
} dict;

其中type属性和privdata是用于不同类的键值对，实现多态字典而设置的。

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);
} dictType;

dictType结构体中主要是对键值进行操作的函数指针，可以依据不同的键值类型，传入对于的操作函数，实现了多态。

回到上面的字典，ht包含了两个哈希表，在一般的情况下，数据存储在ht[0]中，ht[1]主要用于哈希表的rehash。rehashidx记录当前rehash的进度，如果没有在rehash，该值就是-1。

字典的结构示例如下图所示。
在这里插入图片描述

字典的功能

  • Redis的数据库底层就是使用字典来实现的，对数据库的增删改查都是在对字典的操作。
  • 还可以用来实现哈希键，当一个哈希键包含的键值对比较多，或者键值对的元素较长，就会使用字典作为哈希键的底层实现。
  • 还有其他的功能。

字典的算法

1.解决哈希冲突

Redis采用的链地址法来解决。键冲突的节点就用过链表，一个个连在一起，等待遍历查询。

和JDK1.7中的HashMap一样，Redis采用的是头插法，总是将新的节点添加到链表头的位置，这样可以提高速度，但是会导致在多线程下的死循环。在JDK1.8中采用了尾插法。

2.rehash

当节点变多的时候，会造成大量的哈系冲突，这样哈希表的效率就下降了，所以，需要对数组进行扩容，减少哈希冲突。同时节点变少的时候，需要减少数组的大小，节约空间。

rehash就是用来在扩容或者收缩的时候，解决原有哈希值映射到新表上的哈希值的问题。

扩容的大小每次是2的n次幂。这些原理上和Java的实现几乎一致。将当前表中的节点重新计算哈希值，然后放到新表h1中的指定位置上。最后将h0指向h1，再将h1指向空。rehash的具体流程如下：

  1. 为ht[1]分配空间：如果执行扩容操作，则ht[1]的大小为第一个大于等于ht[0].used*2的2**n(2的n次方)；如果执行收缩操作，则ht[1]的大小为第一个大于等于ht[0].used的2 **n。
  2. 将ht[0]上的元素rehash到ht[1]上，即重新计算哈希值，将元素保存到ht[1]中。
  3. 当元素全部迁移完成后，释放ht[0]，将ht[1]设置为ht[0]，并为ht[1]新创建一个空白的哈希表。

扩容的条件是大于其设定的负载因子。

  • 服务器当前未执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于1。
  • 服务器目前正在执行BGSAVE或者BGREWRITEAOF命令，并且哈希表的负载因子大于等于5。

不同于Java的HashMap，Redis的字典具有缩容功能，用于节省内存。
参考Java HashMap

3.渐进式rehash

在将h0的数据复制到h1时，可能不是一次性将数据复制过去的，而是分多次实现，这样做的原因是当节点数量太多的时候，防止复制节点造成的系统停顿。

在复制的过程中，通过rehashidx来保存复制的进度，每次完成一部分的时候，就更新rehashidx的值，直到完成所有的复制，就可以将rehash置为-1。如果是查找修改操作，会先在h0中进行查找，没有找到再去h1；如果是添加操作，则一律添加到h1中。

总结

  • 字典被广泛用于Redis的各种功能，其中包括数据库和哈希键。
  • Redis字典采用哈希表作为底层实现，每个字典有两个哈希表，一个平时用，另一个仅仅在rehash的时候使用。
  • 通过拉链法解决哈希冲突的问题。
  • 扩容或者缩容不是一次性完成，而是分批次，渐进式完成的。

4.跳跃表

跳跃表是一种有序的数据结构，通过在每个节点中位置多个指向其他节点的指针，实现快速访问。

跳跃表的定义

Redis跳跃表由跳跃表和跳跃表节点两个结构实现。

1.跳跃表节点

typedef struct zskiplistNode 
{
    // 成员对象
    robj *obj;
    // 分值
    double score;
    // 后退指针
    struct zskiplistNode *backward;
    // 层
    struct zskiplistLevel {
        // 前进指针
        struct zskiplistNode *forward;
        // 跨度
        unsigned int span;
    } level[];
} zskiplistNode;
  • 层：一个节点有很多层，每一个层中包含指向其他节点的前进指针和该指针指向的节点的跨度。根据幂次定律随机生成一个介于1和32的值作为层数。节点中存储的数值越大，层数就会越少。
  • 前进指针：指向下面的节点。
  • 跨度：用于记录两个节点之间的距离。如果跨度为0，那么表示该层指向的是null。
  • 后退指针：用于指向前一个节点，只能退一个位置。
  • 分值：用于给节点进行排序，分值可以相等，如果分值相等，那么就根据成员对象的字典序进行排序。
  • 成员对象：它指向一个字符串对象，而字符串对象中保存着一个SDS值。

2.跳跃表

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

跳跃表结构示例如下图所示：
在这里插入图片描述

跳跃表的功能

Redis中只有两个地方用到跳跃表。

  • 实现有序集合键。
  • 集群节点中作为内部数据结构。

跳跃表的特点

  • 支持平均O(logN)，最坏O(N)时间复杂度的节点查找。
  • 可以通过顺序性操作来批量处理节点。

5.整数集合

整数是用来保存整数值的数据结构，并且集合内不会出现重复元素，且有序排列。

整数集合的定义

typedef struct intset
{
	// 编码方式
	uint32_t encoding;
	// 集合包含的元素数量
	uint32_t length;
	// 保存元素的数组，一个字节位单位存储
	uint8_t contents[];
} intset;

在这里插入图片描述

其中，encoding表示数组中数据的真正类型，可以是16位、32位或者64位的整型。

整数集合的功能

是集合键的底层实现之一，当一个集合只包含整数值的元素，而且元素数量不多，Redis就会采用整数集合作为集合键的底层实现。

整数集合的升级

当新添加的元素类型超出了现有的类型长度，就需要对集合进行升级，也就是提升存储数组的类型。再添加元素进去。

升级整数集合并添加新元素的步骤如下：

  1. 根据新元素类型，扩容底层的数组空间大小，并为新元素分配空间；
  2. 将底层所有的元素都转化为新元素的相同的类型，并放在正确的位置上，还要维持元素的有序性；
  3. 添加新元素到数组中。

对于原有元素类型的升级和移动，其实就是再数组中根据前面元素偏移的位置进行一个再偏移。其中可能需要空出新元素的位置。

升级的好处：

  • 提升灵活性，可以随意添加不同类型的整型到集合中。
  • 节约内存，尽可能用最小的类型来保存元素。

不支持降级的操作。

6.压缩列表

压缩列表的功能

是列表键和哈希键的底层实现之一，当一个列表键只包含少量列表项，并且每个列表项中只有整数或者长度比较短的字符串，那么Redis就会采用压缩列表来做列表键的底层实现。

压缩列表的构成

一个压缩列表中包含多个节点，每个节点中保存一个字节数组或者整型。

列表中包含的属性：

  • zlbytes：记录整个列表占用的内存数量，用于对列表的内存再分配。
  • zltail：记录列表尾节点到起始地址之间有多少个字节，通过这个偏移量，就不需要遍历就能获得尾节点的地址。
  • zllen：记录列表包含的节点数量。
  • entryX：包含的各个节点。
  • zlend：用于标记列表的末端，0xFF。

节点中包含：

  • previous_entry_length：记录前一个节点的长度。
  • encoding：表示当前节点存储数据的类型，有不同长度的字节数组和不同整型等。
  • content：保存系欸但的值，值得类型和长度由encoding决定。

对象

Redis并没有直接使用上面讲的数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，这个系统主要包含五类对象：

  • 字符串
  • 列表
  • 哈希
  • 集合
  • 有序集合

使用对象的好处：

  • 可以根据不同的使用场景，为对象设置不同的数据结构，从而优化不同场景下的效率。
  • Redis对象系统实现了基于引用计数法的垃圾回收机制，同时可以让多个数据库键共享一个对象来节约内存。
  • 对象具有访问时间记录，这样可以实现类似LRU的内存换页机制。

对象的类型和编码

Redis中对象都由一个redisObject结构表示：

typedef struct redisObject 
{
	// 类型
	unsigned type:4;
	// 编码
	unsigned encoding:4;
	// 指向底层数据结构的指针
	void *ptr;
}

其中，类型就是上面提到的五类对象。对象的ptr指向了底层的数据结构，而这些数据结构就是由编码属性来决定的。实现同一对象类型可以有很多不同的数据结构，一次适应实际的场景。

字符串对象

字符串对象的编码有三种：

  • int：如果字符串保存的整数，那么就用这种编码，里面用了一个long来保存。
  • raw：如果保存的是一个字符串值，而且字符串的长度大于32，那么就用会这种编码，里面就是用了SDS。
  • embstr：如果保存的字符串值长度小于32，就会用这种编码。

在对字符串操作过程中，如果发生了修改使其不满足原先编码的条件，那就就会进行编码的转换。

列表对象

列表对象的编码有两种：

  • ziplist：利用压缩列表作为底层实现。列表中保存的所有的字符串长度小于53字节，列表中保存的元素数量小于612。
  • linkedlist：利用双端链表作为底层实现。如果压缩列表的条件不满足，才会使用链表。

哈希对象

哈希对象的编码两种：

  • ziplist：使用压缩列表作为底层实现。保存键值对的时候，分别生成键和值的两个节点，键节点在前，值节点在后，一起从表尾压缩列表。如果所有键和值的字符串长度小于64字节，同时，键值对数量小于512个，就会采用这种编码。
  • hashtable：使用字典作为底层实现，每个键值对都使用字典键值来保存，每个键和值都是字符串对象。

集合对象

集合对象的编码有两种：

  • intset：使用整数集合作为底层实现，所有元素都保存在整数集合中。保存的元素都是整数，同时保存元素的个数小于等于512个，就会采用这种编码。
  • hashtable：使用字典作为底层实现。

有序集合对象

有序结合对象编码有两种：

  • ziplist：采用压缩列表作为底层的实现，每个集合元素用两个挨在一起的压缩列表节点来保存，第一个保存元素的成员，第二个保存元素的分值。压缩列表内的元素从小到达进行排序。
  • skiplist：使用zset结构作为底层实现，一个zset结构包含一个字典和一个跳跃表。
    在这里插入图片描述

为什么需要同时使用字典和跳跃表的方式来实现？
如果只用字典，那么无法保证集合有序，范围型操作就需要排序，这样时间复杂度就是nlongn的；如果只使用跳跃表，那么查询的时候就要遍历查询跳表，时间复杂度是longn的。所以，同时使用这两种数据结构，就能将查询和范围操作的时间复杂度都为O1，空间换时间。

内存回收

Redis采用引用计数法进行垃圾回收，在每个对象中添加了引用计数，如果计数值为0，说明对象不会再被使用，那么对象就会被释放。

怎么解决循环引用的问题？

对象共享

Redis会共享值为0到9999的字符串对象。有点像JVM的常量池。

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