Redis数据结构

在redis中，自己实现了一套字符串数据结构，使用一个sdshdr来表示一个字符串：

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

至于redis为什么要这么设计，首先是有三个好处：

1. 结构体中记录了字符串的长度，可以在O（1）时间内获取长度。如果只使用char数组来保存，得需要O（n)的时间
2. 结构体内有free类型，减少了因为修改字符串所带来的内存重分配次数。
3. 二进制安全。

为什么说减少了修改字符串所带来的内存重分配次数呢，因为有一个free类型在，并且当需要扩展字符串长度的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。这样在下一次再次扩容的时候，可能就不需要再次重新分配了，因为上次分配的已经够了。

那么在redis中，每次扩容要分配多少额外空间呢？ 这个其实是有一个算法的。下面来看一下这个算法

• 如果对SDS进行修改之后，SDS的长度（也就是len属性的值）小于1MB，那么程序就会分配和len一样大小的未使用空间
• 如果修改之后大于1MB，那么会分配1MB大小的未使用空间。

到这里可能会有疑问了，字符串增长的话会分配额外空间，那字符串len减少会是怎么样呢。

在redis中，采用了惰性释放策略，也就是当我们的len从20减少到10之后，这个时候SDS的大小是不变的，也就是不释放那些空闲的空间，这个样子的话，如果之后字符串增长的话也许就不需要重新分配了，减少内存重新分配的次数。 但是可能又有人会问了，这个样子就会很浪费空间啊，如果之前一个10M的字符串变为了1b，那么就有将近10M的空间被浪费掉了，其实，在redis中还有对应的api函数来释放掉SDS的未使用空间。所以也不需要担心了。

SDS是二进制安全的，
说到二进制安全可能有些人不明白，但是一说肯定就知道了，在c字符串中，所有的字符必须符合一定的编码规则，并且除了在字符串的末尾外，字符串里不能包含空字符。否则最先被程序读入程序的空字符将会被误认为是字符串结尾。 所以c风格字符串限定了不能存储2进制数据，比如图片等。但是，SDS是二进制安全的，因为他会将所有的数据都当成是二进制数据来处理，并且在SDS中是通过len属性来判断是否数据读完，所以也就不会有中间插入的空白字符影响读取了。

redis的链表和普通的双向链表节点一样：

struct listNode{
    struct listNode *prev;
    struct listNode *next;
    void *val;
}

在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)
}

由于这里保存节点使用的是void*，所以链表中可以存储任意类型的值。

• 双向链表，获取头结点和尾节点的时间复杂度尾O（n)
• 无环，表头结点的prev和尾节点的next都指向null
• 带有链表长度，获取长度为O(1)
• 多态，使用void *来保存值

哈希表，在redis中的定义如下：

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

这里的table是一个数组，数组中的每个元素都是一个指向dictEntry结构的指针，每个dictEntry结构保存着一个键值对。 size属性记录哈希表的大小，used则记录键值对的数量。

上图就是一个大小为4的空哈希表。

哈希表节点

哈希表节点使用dictEntry结构表示，每个dictEntry结构保存着一个键值对

typedef struct dictEntry{
    void *key;
    union{
        void *val;
        uint64_tu64;
        int64_ts64;
    }v;

struct dictEntry *next;
}dictEntry;

从这个Entry就能看出来，这里的哈希表是通过链地址法来解决hash冲突的。他有一个next指针。

Redis中的字典定义如下：

typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    // 哈希表
    dictht ht[2];

// rehash索引
    // 在rehash没有进行时候为-1
    int rehashidx;
}

• 这个里面的dictType主要就是包含了一系列用于操作对应类型键值对的函数。Redis会为用途不同的字典设置不同的类型特性函数。
  • privdata这是保存了需要传给那些类型特定函数的可选参数。 这两个字段主要是为了实现多态的，根据不同的类型设置不同的操作函数。
  • ht属性包含两个项的数组，每个项都是一个dictht哈希表，一般只会用ht[0]，ht[1]是在rehash的时候才会用到的。
  • rehash 保存了rehash目前的进度，如果没有在rehash，则为-1；

解决键冲突

上面也看到了，hash表中的节点都是dictEntry节点，每个dictEntry节点都有一个next指针，因此，Redis使用的是链地址法来解决冲突，但是由于dictEntry中没有指向链表尾部的指针，并且这里是使用的头插法。(这个并没有关系，因为链地址法的话每次插入必须遍历链上的每一个节点，不然可能出现一条链上出现两个相同的对象。因此头插和尾插时间都必须是O(n)) 。 但是可能就是 最近使用的数据会更多的使用，这样插入到头部，然后获取效率会很高。

rehash

对于hash表来说，当数据量越来越多，为了保证负载因子维持在一个合理的范围，当哈希表保存的键值对数量太多或者太少时候，程序需要对哈希表的大小进行相应的扩展和收缩。 对于hash表的扩容来说，每次扩容大小为之前大小的二倍。

扩展和收缩一般是通过rehash来操作完成的。Redis对字典执行rehash采用了渐进式hash来进行，也就是说整个rehash并不是一次性就完成的。而是分多次，一次一次进行。下面来看一下具体的rehash的步骤。

1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个hash表。
2. 在字典中维持一个索引计数器变量，rehashidx，将它设置为0，表示rehash正式开始。
3. 在rehash期间，每次对字典执行添加、删除、查找或更新操作时，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表上在rehashidx索引上的所有键值对都rehash到ht[1]上，在这个索引上的节点都被rehash到ht[1]上了的话，就将rehashidx自增1.
4. 随着对字典操作的不断进行，在某个时刻，ht[0]哈希表上的所有键值对都被移动到了ht[1]上，这个时候将rehashidx赋值为-1，到此rehash操作完成。

这里渐进式rehash的好处就是采取分而治之的方式，将rehash键值对所需要的计算工作摊到对字典的每个添加、删除、查找和更新
上。从而避免了集中式rehash带来的一时的程序不能运作。

扩容期间进行的操作

在扩容期间因为有两个表存在，所以操作会和平时显得不一样。

• 查找，查找首先会在ht[0]进行查找，如果找到了，则返回，如果没有找到，会再去ht[1]里面找
• 插入，首先会先执行查找，如果找到了就会返回错误。没有找到会直接插入到ht[1]表中
• 删除，也是会先查找，查找的步骤和上面一样，找到了就删除。没找到则说明不存在。

要注意一下： 在rehash期间，对于键值对的添加删除和更新查找操作和平时是不一样的。比如查找的话会同时在两个表中查询。现在ht[0]中查找，如果没找到再到ht[1]中去查找。

hash表扩展和收缩的情况

先来看一下会发生扩展的情况：

• 服务器没有在执行BGSAVE和BGREWRITEAOF命令，并且哈希表的负载因子大于等于1
• 服务器在执行这两个命令但是哈希表负载因子大于5

• 当哈希表的负载因子小于0.1的时候，程序会对哈希表进行收缩操作。

跳跃表这里的实现和普通跳跃表类似，没有太多可以说的， 不懂可以去看看跳跃表数据结构。

跳跃表主要是由zskiplistNode和zskiplist两个结构来定义的。zskiplistNode用来表示跳跃表节点。而zskiplist则用于保存跳跃表的相关信息，比如节点的数量、头结点或者尾节点。

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

typedef struct zskiplistNode{
    //
    struct zskiplistLevel{
        //前进指针
        struct zskiplistNode *forward;
        //跨度，表示这一层的下一个节点跨过了多少个节点
        unsigned int span;
    } level[];
    //后退指针
    struct zskiplistNode *backward;
    //分值，按分值类排序
    double score;
    //成员对象
    robj *obj;
} zskiplistNode;

整个结构如下图：

具体的跳跃表的原理参见百度。

跳跃表节点每一层的前进指针都只指向下一个具有此层的节点。

跳跃表在redis一般用来表示整数集合和集群节点用作内部数据结构，其他地方是没有用到的。

整数集合是集合键的底层实现之一，就是在Redis中会有一些优化，当一个集合只包含有整数值元素，并且这个元素不多，Redis会使用整数集合来作为底层的集合数据结构。下面来对整数集合做一下讲解。

整数集合可以保存int16_t、int32_t、int64_t的数值，并且保证集合中不会出现重复元素。整数集合用一个intset结构来表示：

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

• contents是整数集合的底层实现，就是用数组实现的。整数集合的数据是按照值得大小从小到大排列的，并且不包含任何重复项。虽然说，contents类型是int8_t类型的，但是contents并不保存int8_t类型的数据，而是根据encoding类型来保存不同类型的数据。比如如果encoding是int16_t类型，那么contents就保存int16_t类型的数据。
• length 是整数集合包含的元素数量
• encoding 也就是说的编码方式，有三种，分别是16位，32位和64位的整数集合。

通过这个encoding类型，能够极大的减少内存的浪费，如果说整数集合都是存储的很小的整数，那么就可以int16_t来保存数据，减少内存浪费，但是这个时候又有一个问题出现了，就是如果这个时候来一个int32_t大小的数据该怎么办呢，Redis肯定有他的解决办法，这个办法就是升级操作。

每次添加一个新元素到整数集合里面，并且新元素的类型比整数集合现在的类型长度要长，那么就会先对这个整数集合进行升级，然后再将新元素添加到整数集合中。 下面看一下升级步骤：

1. 根据新元素的类型，扩展整数集合底层数组大小，并且为新元素分配空间
2. 将底层数据现有的元素全部都转换成与新元素相同的类型，并且将类型转换后的元素放到对应的位置，并且保证元素的有序性
3. 将新元素添加到底层数组中。

Redis只支持升级操作而不支持降级操作，降级操作需要遍历所有的元素看是否能降级，得不偿失。所以就不支持降级操作。

注意 整数集合的扩容大小为之前的length+1，所以每次插入都会重新分配空间扩容。 而对于删除操作来说，首先找见要删除的元素，然后将之后的元素向前移动，之后再释放掉多余的空间。

所以在整数集合中，每次插入或者删除元素都是要进行空间的重新分配的。

压缩列表是列表键和哈希键的底层实现之一，当一个列表键只包含少量的列表项，并且每个列表项要么是小整数值，要么就是长度比较短的字符串，这个时候Redis就会使用压缩列表来实现列表键。 又或者一个哈希键的键值对都是小整数或者较短的字符串，也会使用压缩列表来实现。

压缩列表主要是为了节约内存而开发的。是由一系列特殊编码的连续内存块组成的顺序性数据结构， 一个压缩列表包含任意多个节点（entry），每个节点保存一个字节数组或者一个整数值。
如下图所示：

压缩列表的节点

每个压缩列表节点都可以保存一个字节数组或者一个整数值，对于字节数组来说可以是一下三种长度的一种

• 长度小于等于64字节
• 长度小于等于16383字节
• 长度小于2的32次方-1字节的字节数组

整数值可以是各种长度，4位长，1字节长，3字节长，16位，32位，64位的。

每个压缩列表的节点都是由privious_entry_length、encoding、content三个部分组成

• privious_entry_length 这个字段记录了压缩列表的前一个节点的长度，它的长度可以是1字节或者5字节，如果前一节点的长度小于254字节，那么privious_entry_length的长度为1字节，保存着上一个节点的长度； 如果前一节点的长度大于等于254字节，那么privious_entry_length的长度为5字节，第一个字节设置为0xFE（254），之后四个字节保存前一个节点的长度。
  • 由于这个属性保存了上一个节点的长度，所以我们可以通过这个字段计算出上一个字段的起始地址，这样就能够实现从表尾遍历了。

• encoding 属性记录了节点的content属性保存的数据的类型以及长度。分一下几种情况

  • 1字节，两字节，五字节长，值得最高两位为00、01或10的是字节数组编码，这种编码表示节点的content属性保存的是字节数组，并且除去最高两位其余的表示字节数组的长度
  • 1字节，值最高两位以11开头的是整数编码：这种编码表示节点的content属性，保存着整数值，整数值的类型和长度由编码除去最高两位之后的其他记录。

• content属性则是存储真正值得地方。根据encoding类型，存储不同的类型值。

从它的结构来看，就可以看出来，压缩列表是很节省空间的，尽可能的不浪费空间，要存多少东西就分配多少。不够了再动态扩张。这也是它叫压缩列表的原因。

但是在极端情况下，压缩列表可能会出现一个连锁更新的问题。比如说，现在在压缩列表中的节点大小都为250到253字节大小，但是这个时候向压缩列表头部插入一个259字节的数据，那么之后的第一个节点的privious_entry_length会变成5字节，导致节点大小超过254字节，接着就得更新下一个节点的privious_entry_length值，知道最后，引发了连锁更新。删除也可能会出现这种情况。但是这种情况一般很少见，其实是可以忽略的。