[数据结构与算法]Redis知识（三）--底层数据结构

引言

??Redis常用的数据类型有5种：字符串(String)、哈希(Hash）、列表(List)、集合(Set)以及有序集合(Zset)。而这5中数据类型，实际由Redis底层数据结构实现。
??根据《Redis设计与实现》一书的介绍，可以了解到，Redis底层数据结构有如下类型：

• 简单动态字符串（simple dynamic string，SDS）
• 链表
• 字典
• 跳跃表
• 整数集合
• 压缩列表

一、简单动态字符串（simple dynamic string，SDS）

1、定义

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

??SDS遵循C字符串以空字符结尾的惯例，保存空字符的1字节不会计算在len属性里面。

2、与C字符串的区别

??传统的C 字符串 使用长度为N+1 的字符串数组来表示长度为N 的字符串，并且字符串的最后一个元素是空字符\0。
??对比C字符串，采用SDS有如下优势：
???1. 常数复杂度获取字符串长度
???2. 杜绝缓冲区溢出
???3. 减少修改字符串时带来的内存重分配次数
???4. 二进制安全

2.1、常数复杂度获取字符串长度

??C字符串并不记录自身的长度信息，所以为了获取字符串的长度，必须遍历整个字符串，时间复杂度是O(N)；而SDS使用len属性记录了字符串的长度，因此获取SDS字符串长度的时间复杂度是O(1)。

2.2、杜绝缓冲区溢出

??C字符串不记录自身长度带来的另一个问题是很容易造成缓存区溢出。SDS的空间分配策略完全杜绝了发生缓存区溢出的可能性：当SDS API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足的话，API会自动将SDS的空间扩展至执行修改所需大小，然后才执行实际的修改操作。

2.3、减少修改字符串时带来的内存重新分配

??Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场景，如果每次都像C字符串那样进行内存重分配的话，对性能影响太大了，显然是无法接受的。为了避免C字符串的这种缺陷，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联。通过空闲空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

1）空间预分配

??空间预分配是用于优化SDS字符串增长操作的：当SDS的API对一个SDS进行修改并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配所需要的空间，还会为SDS分配额外的未使用空间。具体分配策略如下：

• len小于1MB时：每次重分配时会多分配同样大小的空闲空间，这事free属性的值与len相同，即buf数组长度=len+free+1=2*len+1
• len大于等于1MB时：每次重分配时会多分配1MB大小的空闲空间，即buf数组长度=len+1MB+1

2）惰性空间释放

??惰性空间释放是用于优化SDS字符串缩短操作：当SDS API需要缩短SDS保存的字符串时，并不会立即重新分配内存来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，等待将来使用。

2.4、二进制安全

??C字符串中的字符必须符合某种编码，并且除了字符串末尾之外，其它位置不允许出现空字符，这些限制使得C字符串只能保存文本数据。但是对于Redis来说，不仅仅需要保存文本，还要支持保存二进制数据。为了实现这一目标，SDS的API全部做到了二进制安全(binary-safe)。

二、链表

1、数据结构

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

??链表节点由listNode结构表示，多个listNode可以通过prev和next指针组成双端链表。

??但是，为了方便操作，Redis使用list结构来持有链表。

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;

2、链表特性

??Redis链表实现特性总结如下：

1. 双端：链表节点带有prev和next指针，获取某个节点的前置节点和后置节点的复杂度都是O(n)
2. 无环：表头节点的prev指针和表尾节点的next指针都指向NULL，对链表的访问以NULL为终点
3. 带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂度为O(1)
4. 带链表长度计数器：程序使用list结构的len属性来对list持有的节点进行计数，程序获取链表中节点数量的复杂度为O(1)
5. 多态：链表节点使用void*指针来保存节点值，可以保存各种不同类型的值

三、字典

??字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。
?字典在Redis中应用相当广泛，比如Redis的数据库就是使用字典来实现的。除了数据库之外，字典还是哈希键的底层实现之一。

1、字典的实现

??Redis使用哈希表作为底层实现，哈希表定义如下：

typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;

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

??table属性是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。

typedef struct dictEntry {
    // 键
    void *key;

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

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

??key属性保存着键值对中的键，而v属性则保存了键值对中的值。值可以是一个指针，一个uint64_t整数或者是int64_t整数。next属性指向了另一个dictEntry节点，在数组桶位相同的情况下，将多个dictEntry节点串联成一个链表，以此来解决键冲突问题。(链地址法)

??Redis字典由dict结构表示：

typedef struct dict {

    // 类型特定函数
    dictType *type;

    // 私有数据
    void *privdata;
    
    // 哈希表
    dictht ht[2];

    //rehash索引
    // 当rehash不在进行时，值为-1
    int rehashidx;
}

??ht是大小为2，且每个元素都指向dictht哈希表。一般情况下，字典只会使用ht[0]哈希表，ht[1]哈希表只会在对ht[0]哈希表进行rehash时使用。rehashidx记录了rehash的进度，如果目前没有进行rehash，值为-1。

2、rehash

??字典用作数据库或者哈希键的底层实现时，Redis使用MurmurHash2算法来计算键的哈希值。哈希表使用链地址法解决键冲突，因为dictEntry节点组成的链表没有指向链表尾的指针，为了速度考虑，新节点总是添加到链表的头部（头插法，复杂度O(1)）。
??字典扩展和收缩哈希表可以通过执行rehash操作来完成。rehash步骤如下：

1. 为ht[1]哈希表分配空间：
   ?如果是扩展操作，那么ht[1]的大小为第一个大于等于h[0].used*2的 2ⁿ；
   ?如果是收缩操作，那么ht[1]的大小为第一个大于等于h[0].used的 2ⁿ
2. 将保存在ht[0]中的所有键值对rehash到ht[1]中
3. ht[0]所有键值对都迁移到ht[1]后，将ht[1]设置为ht[0]，并在ht[1]创建一个空白哈希表，为下次rehash准备

2.1、哈希表扩展收缩时机

1. 当服务器没有执行BGSAVE或者BGREWRITEAOF命令时，负载因子大于等于1触发哈希表的扩展操作。
2. 当服务器在执行BGSAVE或者BGREWRITEAOF命令，负载因子大于等于5触发哈希表的扩展操作。
3. 当哈希表负载因子小于0.1，触发哈希表的收缩操作。

??负载因子计算公式：负载因子=哈希表已保存节点数量/哈希表大小，即load_factor = ht[0].used / ht[0].size。

2.2、渐进式rehash

??扩展或者收缩需要将ht[0]里面的元素全部rehash到ht[1]中，如果ht[0]元素很多，显然一次性rehash成本会很大，从影响到Redis性能。为了解决上述问题，Redis使用了渐进式rehash技术，具体来说就是分多次，渐进式地将ht[0]里面的元素慢慢地rehash到ht[1]中。
??渐进式rehash步骤如下：

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]
2. 在字典中维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash正式开始
3. 在rehash进行期间，每次对字典执行添加、删除、查找或者更新时，除了会执行相应的操作之外，还会顺带将ht[0]在rehashidx索引位上的所有键值对rehash到ht[1]中，rehash完成之后，rehashidx值加1
4. 随着字典操作的不断进行，最终会在某个时间点迁移完成，此时将rehashidx值置为-1，表示rehash完成

??渐进式rehash一次迁移一个桶上所有的数据，设计上采用分而治之的思想，将原本集中式的操作分散到每个添加、删除、查找和更新操作上，从而避免集中式rehash带来的庞大计算。
??渐进式rehash时，字典会同时使用ht[0]和ht[1]两张表，所以此时对字典的删除、查找和更新操作都可能会在两个哈希表进行。比如在字典中查找一个键的话，会先在ht[0]中查找，没找到的话再到ht[1]中查找。
??另外，在渐进式rehash执行期间，新加的键值对一律会添加到ht[1]中，ht[0]不做任何添加操作。
??rehash过程演示：

四、跳跃表

1、跳跃表的实现

??跳跃表节点结构：

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

1. 层：level 数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。每次创建一个新跳跃表节点时，根据幂次定律随机生成一个1~32之间的值作为level数组的大小。
2. 前进指针：每个层都有志强表尾方向的前进指针（level[i].forward属性）
3. 跨度：层的跨度（level[i].span属性）用于记录两个节点之间的距离
4. 后退指针：节点后退指针（backward属性）用于从表尾向表头方向访问节点
5. 分值和成员：节点的分值（score属性）是double类型浮点数，跳跃表中节点按分值从小到大排序。节点成员对象（obj属性）是一个指向字符串对象的指针

??跳跃表结构：

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

五、整数集合

1、整数集合的实现

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

??整数集合（intset）可以保存类型为int16_t、int32_t、或int64_t的整数值，并且保证集合中不会出现重复元素。
??contents数组是整数集合的底层实现，元素在数组中按值大小从小到大有序排列。contents属性虽然声明为int8_t类型，但不保存任何int8_t类型的值，数组真正保存的类型取决于encoding属性。

升级

??当添加元素到整数集合时，如果新元素类型比整数集合现有类型要长，那么整数集合就需要升级。升级步骤如下：

1. 根据新元素的类型，扩展整数集合底层数组空间大小，并为新元素分配空间
2. 将地城数组现有所有元素转换成与新元素相同类型，并放置到正确的位上，原数组有序性不变
3. 将新元素添加到数组中

??Redis整数升级策略有两个好处：一是提升整数集合的灵活性；另一个是尽可能节约内存。
??集合一旦升级之后，编码就会一直保持升级后的状态，整数集合是不支持降级操作。因为降级需要一个时机来判定，假设最后一个最大类型元素删除，那么需要遍历整个底层数组来确定是否可降级，而且还需要确定降级至那种数据类型，这也需要遍历整数数组，遍历数组也就意味着消耗大量性能消耗在操作无关地方。

六、压缩列表

1、压缩列表的构成

??压缩列表（ziplist）为了节约内存而开发，是列表键和哈希键的底层实现之一。其结构如下：

1.1、压缩列表节点的组成

??如图，一个压缩列表节点由previous_entry_length、encoding、content三部分组成：

• previous_entry_length：记录压缩列表前一个节点的长度，属性可以是1字节（前一节点长度小于254字节）或者5字节（前一节点长度大于等于254字节）
• encoding：记录节点content属性所保存数据的类型和长度
• content：节点的值

七、对象

??前面介绍过Redis主要用到的底层数据结构，但Redis并没有直接使用直接数据结构来实现键值对数据库，而是基于这些数据结构构建一个对象系统。
??此外，Redis对象系统还实现了基于引用计数技术的内存回收机制，同时实现对象共享来节约内存。

1、对象类型和编码

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

??对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值可以不同的对象类型，通过TYPE命令可以知道一个键的类型。
??redisObject中type属性常量可以是下表中的一个：

??encoding属性也是一个常量：

1.1、对象所使用的编码

??每种类型的对象都至少使用了两种不同的编码：

1.2、编码转换

??在满足条件下，对象使用的编码会自动发生转换，转换规则如下：

??编码转换之后，不会回转。

2、内存回收与内存共享

2.1、内存回收

??Redis在对象系统中构建了一个引用计数（reference counting）技术实现的内存回收机制。

typedef struct redisObject {
    // ...
	// 引用计数
	int refcount;
    // ...
} robj;

• 在创建一个新对象时，引用计数的值会被初始化为1
• 当对象被一个新程序使用时，它的引用计数值会被增1
• 当对象不再被一个程序使用时，它的引用计数值会被减1
• 当对象引用计数值为0时，对象所站哟的内存会被释放

2.2、内存共享

??Redis中，让多个键共享一个值对象只需两个步骤

1. 将数据库键的值指向一个现有的值对象
2. 被共享的值对象引用计数加一

??Redis在初始化服务器时，会创建0~9999整数的一万个字符串对象，需要使用的时候可以直接使用这些共享对象。

总结

1、Redis底层数据结构主要包括简单动态字符串(SDS)、链表、字典、跳跃表、整数集合和压缩列表六种类型
2、利用基础数据结构实现了字符串对象、列表对象、哈希对象、集合对象以及有序集合对象五种常见的对象类型
3、Redis基于这些底层数据结构，构建了对象系统，并实现基于引用计数技术的内存回收机制和内存共享机制