Redis 底层数据结构

在Redis数据结构和对象机制中提到的图中，我们知道，可以通过 redisObject 对象的 type 和 encoding 属性。可以决定Redis 主要的底层数据结构：SDS、QuickList、ZipList、HashTable、IntSet、ZskipList 。

一、简单动态字符串（SDS）

先来看看传统的C 语言如何存储字符串的：比如一个 "Redis" 字符串：

为什么不用传统的 C 语言的方式，因为我们知道数组方式在获取字符串长度或者扩容上存在缺陷：比如获得一个数组长度的复杂度为O(N), 而且数组扩容也不太方便。所以自己构建了一种名为简单动态字符串（simple dynamic String）的抽象数据类型。

• sdshdr : 表示SDS 类型，共有5种类型。每个类型的数字表示 unit
• alloc：还未被使用的空间, 这里为0
• len：表示这个 SDS 保存了5 个单位的字符串
• buf：char类型的数组，用于保存字符

1.1 SDS 的定义

SDS 位于 src/sds.h 和 src/sds.c 中，它的结构总共有五种（redis 6.0.6）

/* Note: sdshdr5 is never used, we just access the flags byte directly.
 * However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
    unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
    //所保存字符串的长度
    uint8_t len; /* used */
    //除了头部与末尾的\0以外，剩余的字节数
    uint8_t alloc; /* excluding the header and null terminator */
    //只有1字节，前5位未使用，后三位表示头部的类型（sdshdr5\8\16\32\64）
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    //用来保存字符串的元素
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
    uint16_t len; /* used */
    uint16_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
    uint32_t len; /* used */
    uint32_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
    uint64_t len; /* used */
    uint64_t alloc; /* excluding the header and null terminator */
    unsigned char flags; /* 3 lsb of type, 5 unused bits */
    char buf[];
};

1.2 SDS 和 C 字符串的区别

• SDS 能以O(1) 复杂度获取字符串长度：SDS 有 len 属性，而 C 字符串没有

• SDS 能杜绝缓冲区溢出 ：

  • 缓存区溢出：比如程序在执行拼接操作前，需要先通过内存重分配来扩展底层数组的空间大小——忘记则会产生缓冲区溢出
  • SDS 记录自身长度，所以在进行操作时会进行相应的空间扩展再进行修改，不会出现缓冲区溢出

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

  • 空间预分配：对字符串进行空间扩展时，扩展的内存比实际需要的多，这样可以减少连续执行字符串增长操作所需的内存重分配次数。
  • 惰性空间释放：对字符串进行缩短操作时，程序不立即使用内存重新分配来回收缩短后多余的字节，而是使用 alloc 属性将这些字节记录下来，等待将来使用。

• SDS 能实现二进制安全：

  • C 字符串中的字符必须符合编码格式，并且除了末尾外，中间不能包含空字符，否则会被误认为是空字符串结尾。这样会使得 C 字符串只能保存文本数据，而不能保存图片、视频等其他二进制数据
  • SDS 的 buf 属性则可以存储多种二进制数据，而且以 len 属性表示的长度来判断字符串是否结束

• SDS 兼容部分 C 字符串函数：

  • 遵从每个字符串都是以空字符串结尾的惯例，可以重用 C 语言库<string.h> 中的一部分函数

二、字典（Dict）

Redis 的字典使用哈希表作为底层实现，代码位于 src/dict.h

2.1 字典的实现

2.1.1 哈希表的结构定义

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

如图是一个大小为4的空哈希表：

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

  typedef struct dictEntry {
      //键key
      void *key;
      //值value，可以是指针、int64、double 等类型
      union {
          void *val;
          uint64_t u64;
          int64_t s64;
          double d;
      } v;
      //指向下一个 dictEntry 的指针，拉链法解决哈希冲突
      struct dictEntry *next;
  } dictEntry;
  

• size 属性：记录哈希表的大小

• sizemask 属性：总是等于 size - 1

• used 属性：记录哈希表目前已有节点（键值对）的数量

2.1.2 字典的结构定义

Redis 中的字典代码在 src/dict.h 中

typedef struct dict {
    //指向 dictType 结构的指针
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //索引，当 rehash 不在进行是，值为 01
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

一个没有进行 rehash 的字典

• type 属性：指向 dictType 结构的指针，每个 dictType 结构保存了一簇用于操作特定类型键值对的函数

  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;
  

• privdata 属性：保存了需要传给那些类型特定函数的可选参数

• ht 属性：包含两个项的数组，数组中的每个项都是一个 dictht 哈希表。一般情况，字典只使用 ht[0] 哈希表，ht[1] 哈希表在对 ht[0] 哈希表进行 rehash 时使用。

• rehashidx 属性：如果没有进行 rehash，它的值为 -1。

2.2 哈希冲突

2.2.1 哈希算法

Redis 中计算哈希值和索引值的方法为：

# 利用字典设置的哈希函数,计算键key的哈希值
hash = dict->type->hashFunction(key);
# 使用哈希表的 sizemask 属性和哈希值来计算出索引值（h[x] 指的是 ht[0] 或者 ht[1]）
index = hash & dict->ht[x].sizemask;

这里的 hashFunction(key)是使用 MurmurHash 算法来计算键的哈希值，这种算法的有点在于即使输入的键是有规律的，算法仍然能给出一个很好的随机分布性。算法的计算速度也非常快。

2.2.2 哈希冲突

前面提到过，Redis 中是通过拉链法来解决哈希冲突，每个哈希表节点都有一个 next 指针，多个哈希表节点可以用 next 指针构成一个单向链表，来解决哈希键冲突的问题。代码在 src/dict.c/dictAddRaw 中

dictEntry *dictAddRaw(dict *d, void *key)
{
    int index;
    dictEntry *entry;
    dictht *ht;
    if (dictIsRehashing(d)) _dictRehashStep(d);               // 1、执行rehash
    //如果索引等于 -1 表明字典中已经存在相同的 key
    if ((index = _dictKeyIndex(d, key)) == -1)                // 2、索引定位
        return NULL;
    ht = dictIsRehashing(d) ? &d->ht[1] : &d->ht[0];          // 3、根据是否 rehash ，选择哈希表
    entry = zmalloc(sizeof(*entry));                          // 4、分配内存空间，执行插入
    entry->next = ht->table[index];
    ht->table[index] = entry;
    ht->used++;
    dictSetKey(d, entry, key);                                // 5、设置键
    return entry;
}

其中 哈希算法的具体代码就在函数_dictKeyIndex()中

static int _dictKeyIndex(dict *d, const void *key)
{
    unsigned int h, idx, table;
    dictEntry *he;
 
    if (_dictExpandIfNeeded(d) == DICT_ERR)                            // 1、rehash 判断
        return -1;
    h = dictHashKey(d, key);                                           // 2、哈希函数计算哈希值
    for (table = 0; table <= 1; table++) {
        idx = h & d->ht[table].sizemask;                               // 3、哈希算法计算索引值
        he = d->ht[table].table[idx];
        while(he) {                          
            if (key==he->key || dictCompareKeys(d, key, he->key))      // 4、查找键是否已经存在
                return -1;
            he = he->next;
        }
        if (!dictIsRehashing(d)) break;                                // 5、rehash 判断 
    }
    return idx;
}

2.2.3 rehash

同 Java 中的 HashMap 底层数据结构一样，哈希表存储的键值对会增多或者减少，在 Redis 中是通过执行 rehash(重新散列) 来完成对表的扩展和收缩。也就是让哈希表中的负载因子维持在一个合理的范围中。这里的负载因子是：load_factor = ht[0].used / ht[0].size

• 扩展：1.服务器正在执行 BGSAVE 或者 BGREWRITEAOF 命令并且哈希表的负载因子大于等于 5 时；2.服务器目前没有执行 BGSAVE 或者 BGREWRITEAOF 命令并且哈希表的负载因子大于等于1时，为 ht[1] 分配空间，大小是大于原 ht[0] 两倍的2次幂

  • 从ht[0] 的值移动到 ht[1] 时，需要重新计算原 ht[0] 中元素的哈希值和索引；插入到ht[1] 中，插一个删除一个

  • ht[0] 中的元素全部迁移完后，释放 ht[0]，将新建的 ht[1] 设置为 ht[0] ，调用的是 dict.c/_dictExpandIfNeeded 函数：

    static int _dictExpandIfNeeded(dict *d)
    {
        if (dictIsRehashing(d)) return DICT_OK;
        if (d->ht[0].size == 0) return dictExpand(d, DICT_HT_INITIAL_SIZE);          // 大小为0需要设置初始哈希表大小为4
        if (d->ht[0].used >= d->ht[0].size &&
            (dict_can_resize ||
             d->ht[0].used/d->ht[0].size > dict_force_resize_ratio))                 // 负载因子超过5，执行 dictExpand
        {
            return dictExpand(d, d->ht[0].used*2);
        }
        return DICT_OK;
    }
    

• 收缩：当哈希表的负载因子小于 0.1 时，会对哈希表执行收缩操作，同样会分配 ht[1]，大小等于 max(ht[0].used, DICT_HT_INTIAL_SIZE)。同样也需要迁移元素，具体操作和扩展相同

2.2.4 渐进式 rehash

扩展或者收缩哈希表是需要将 ht[0]中的键值对 rehash 到 ht[1] 中。因为当键值对数量非常多的时候，如果是一次性、集中式的完成大量的 rehash 动作，很可能会导致服务器宕机。所以需要渐进式的 rehash 来完成。渐进式 rehash 的步骤如下：

1. 为 ht[1] 分配空间，在字典中的 rehashidx 变量设置为 0。这步代码在 dict.c/dictExpand 中实现

   int dictExpand(dict *d, unsigned long size)
   {
       dictht n;
       unsigned long realsize = _dictNextPower(size);                      // 找到比size大的最小的2的幂
       if (dictIsRehashing(d) || d->ht[0].used > size)
           return DICT_ERR;
       if (realsize == d->ht[0].size) return DICT_ERR;
    
       n.size = realsize;                                                 // 给ht[1]分配 realsize 的空间
       n.sizemask = realsize-1;
       n.table = zcalloc(realsize*sizeof(dictEntry*));
       n.used = 0;
       if (d->ht[0].table == NULL) {                                      // 处于初始化阶段
           d->ht[0] = n;
           return DICT_OK;
       }
       d->ht[1] = n;
       d->rehashidx = 0;                                                  // rehashidx 设置为0，开始渐进式 rehash
       return DICT_OK;
   }
   

2. 在 rehash 进行中对字典的 CRUD 操作时，除了这些制定的操作外。还会顺带将 ht[0] 的所有键值对被 rehash 到 ht[1] 中。 rehash 完成后，会将 rehashidx 属性的值加1。

   • rehash 时的 CRUD 操作会在两个哈希表中进行，比如分别在两个表中查找，添加元素在 ht[1] 中添加

3. 当 ht[0] 中所有键值对都被 rehash 到 ht[1] 后，将 rehashidx 属性值设为 -1，rehash 操作完成。

三、压缩列表（ZipList）

从本文开头图中可以看出，压缩列表(ZipList)是列表键和哈希键的底层实现原理。它是为了节约内存而开发出来的。一般用在一个列表中只含有很少的元素或者里面的元素是小整数、长度较短的字符串时， Redis 就会使用 ZipList 来做列表键的底层实现。

3.1 压缩列表的构成

压缩列表是由一系列特殊编码的连续内存块组成的顺序型数据结构，一个压缩列表可以包含多个节点，每个节点中可以保存相应的数据类型（字节数组或者一个整数值）。如下图

如图是一个压缩列表实例：

• zlbytes 属性值为 0xd2(十进制 210) ,表示压缩列表总长度为 210 字节
• zltail 属性值为 0xb3(十进制 179),表示起始指针p 到末尾指针的偏移量是 179
• zilen 属性值为 0x5(十进制 5),表示压缩列表包含了五个 entry 节点
• entry1~entry5 :表示各个列表
• zlend 属性值表示压缩列表的末端

3.2 压缩列表节点的构成

每个压缩列表节点可以保存一个字节数组或者一个整数值。其节点都由 previous_entry_length、encoding、content 三个属性组成。如下图：

1. previous_entry_length 属性: 以字节为单位，记录了压缩列表中的前一个字节的长度。

   • 若前一字节的长度小于 254 字节，则 previous_entry_length 的值为 1 字节
   • 若前一字节的长度大于等于 254 字节，则 previous_entry_length 的值为5字节：该属性的第一个字节被设置为 254，后面的四个字节用于存储超过 1 字节的剩余长度。

2. encoding 属性：记录了节点的 content 属性所保存数据的类型以及长度

   • 1字节、2字节或者5字节时，值的最高为00、01或者10的是字节数组编码：这种编码表示节点的 content 属性保存着字节数组。

     编码	编码长度	content 属性保存的值
     00bbbbbb	1 字节	长度小于等于 63 字节的字节数组。
     01bbbbbb xxxxxxxx	2 字节	长度小于等于 16383 字节的字节数组。
     10______ aaaaaaaa bbbbbbbb cccccccc dddddddd	5 字节	长度小于等于 4294967295 的字节数组。

   • 1字节，值的最高位以11开头的整数编码：整数值的类型和长度由编码除去最高两位之后的其他位记录。

     编码	编码长度	content 属性保存的值
     11000000	1 字节	int16_t 类型的整数。
     11010000	1 字节	int32_t 类型的整数。
     11100000	1 字节	int64_t 类型的整数。
     11110000	1 字节	24 位有符号整数。
     11111110	1 字节	8 位有符号整数。
     1111xxxx	1 字节	使用这一编码的节点没有相应的 content 属性， 因为编码本身的 xxxx 四个位已经保存了一个介于 0 和 12 之间的值， 所以它无须 content 属性。

3. content 属性：负责保存节点的值，节点值可以是一个字节数组或者整数，值的类型和长度由节点的 encoding 属性来决定。

   举个保存整数节点的例子：

   

   • encoding 是 11 开头表示存储的是整数类型
   • content 表示保存节点值是 10086

为何 ZipList 省能内存？

• 相对于普通的 list 而言，增加 encoding 属性来选择性让字节和整数类型进行存储
• 有了 previous_entry_length 属性，遍历元素时可以定位到下一个元素的精确位置，降低搜索的时间复杂度

四、跳表（ZSkipList）

跳表是一种有序数据结构，它就是作为有序列表（Zset）的使用。而且相较于平衡树比较更优雅，在 CRUD 等操作上可以在对数期望时间内完成。

如上图所示，是一个跳跃表实例，最左侧的是 zskiplist 结构，该结构包含的属性有：

• header属性：指向跳跃表的表头节点
• tail属性：指向跳跃表的表尾节点
• level属性：记录跳跃表中层数最大节点的层数
• length属性：记录跳跃表的长度，也就是跳跃表目前包含节点的数量

而右侧的四个是 zskiplistNode 结构，该结构包含的属性有：

• level属性：节点中用L1、L2、L3等等字样标记节点的各层
• backward属性：节点中用 BW字样标记节点的后退指针，它是指向当前结点的前一个节点
• score属性：节点中保存的诸如1.0、2.0等等分值
• obj属性：节点中的 o1、o2等等是节点所保存的成员对象

4.1 跳跃表结构定义

4.1.1 跳跃表的结构

如开始介绍的图，zskiplist 结构代码在 redis.h/zskiplist 中，其定义如下：

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

4.1.2 跳跃表节点的结构

其中 zskiplistNode 结构用于表示跳跃表节点，代码在 redis.h/zskiplistNode 中。

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    //对象属性,指向了一个字符串对象
    sds ele;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层level
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned int span;
    } level[];
} zskiplistNode;

• level 属性：level 层中可以包含多个元素，层的数量越多，访问其他节点的速度就越快。程序通过幂次定律（power law, 越大的数出现的概率越小）随机生成一个介于1和32之间的值作为 level 数组的大小作为层高:下图是不同层高的节点

  

• 前进和后退指针（*forward和* backforward）：用于访问遍历跳跃表中所有节点的路径

  

• span跨度属性：层的跨度是用于记录两个节点之间的距离：如上图箭头上的数字表示节点间的距离

• **分值和成员（score 、sds ele）**：

  • 分值是一个 double 类型的浮点数，跳跃表中的所有节点都按分值从小到大排序
  • 成员对象（如o1、o2等等），它是一个指针，指向一个字符串对象，这个对象保存着一个SDS 值
    • 在同一个跳跃表中，各个节点保存的成员对象必须是唯一的，分值可以相同。成员对象小的会排在前面（表头）、成员对象较大的节点会排在后面（表尾）。还是这张图，图中 o1、o2和o3三个节点都保存了相同的整数值 10086.0。但是成员对象的排序却是 o1->o2->o3

五、整数集合（IntSet）

当一个集合中只有整数值元素，并且集合中的元素数量不多时，Redis则会使用整数集合作为集合键的底层实现

5.1 整数集合结构定义

intset 可以保存类型为int16_t、int32_t或者int64_t的整数值，而且保证集合中不会出现重复元素。其结构代码在 intset.h/intset 中,下面以32为编码方式为例：

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

以一个具体的整数集合为例：

• encoding属性值为 INTSET_ENC_INT16 :表示 contents 数组是一个 16 位的数组
• length属性值为5，表示contents 数组中包含五个元素
• contents 数组，表示该数组中从小到大存储着五个元素

5.2 整数集合的升级

新元素的类型比现有的类型要长，比如说16位变成32位，在整数集合里叫做升级（upgrade）。经过升级后，才能将新元素添加到整数集合中，升级整数集合并且添加新元素的步骤为：

1. 根据新元素的类型，扩展底层数组的空间大小，为新元素分配空间
2. 将底层数组现有的所有元素都转换成新元素相同的类型，将类型转换后的元素放置在正确的位置上。
3. 将新元素添加到contents数组里面

集合也不会做降级操作，比如在原16位数组中新加了一个32位元素，然后把这个新加的元素删除后，整数集合也不会做降级操作。

六、快速链表（QuickList）

quicklist 结构时一种以 ziplist 为节点的双端链表结构，整体上是一个链表，但是链表中的每一个节点都是一个 ziplist.

6.1 快速链表的结构

其代码结构为，在src/quicklist.h 中

我们先来看看quicklistNode 节点的结构：

typedef struct quicklistNode {
    //上一个quicklistNode节点
    struct quicklistNode *prev;
    //下一个quicklistNode节点
    struct quicklistNode *next;
    //数据指针，
    unsigned char *zl;
    //表示zl指向 ziplist 的总大小
    unsigned int sz;             /* ziplist size in bytes */
    //表示ziplist里面包含的数据项个数
    unsigned int count : 16;     /* count of items in ziplist */
    //ziplist是否被压缩,1是没有，2是被压缩
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    //预留字段，目前是固定值，表示使用 ziplist 作为数据容器
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    //需要把数据暂时解压，此时设置 recompress = 1,有机会再将数据重新压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    //Redis 自动化测试时用
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    //扩展字段，目前没有被使用
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

再来看看 quicklistLZF 结构，表示一个被压缩过的 ziplist，它的结构是：

typedef struct quicklistLZF {
    //压缩后 ziplist 的大小
    unsigned int sz; /* LZF size in bytes*/
    //柔性数组，存放压缩后的 ziplist 字节数组
    char compressed[];
} quicklistLZF;

再看看最后的 quicklist 结构

typedef struct quicklist {
    //指向头节点（quicklistnode 头节点）
    quicklistNode *head;
    //指向尾节点（最右侧节点）
    quicklistNode *tail;
    //所有ziplist 的数量
    unsigned long count;        /* total count of all entries in all ziplists */
    //quicklist节点的个数
    unsigned long len;          /* number of quicklistNodes */
    //设置ziplist 的大小，存放 list-max-ziplist-size 参数的值
    int fill : QL_FILL_BITS;              /* fill factor for individual nodes */
    //节点压缩深度设置，存放 list-comress-depth 参数的值，为0的时候关闭
    unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0=off */
    //尾部增加的书签，只有在大量节点的多余内存使用量可以忽略不计的情况，才分批迭代他们，不使用时不会增加内存开销
    unsigned int bookmark_count: QL_BM_BITS;
    quicklistBookmark bookmarks[];
} quicklist;

6.2 快速链表的内部操作

6.2.1 插入操作

1. 可以选择在头部或者尾部插入：

• ziplist大小没有超过限制，新数据直接插入到 ziplist 中
• ziplist超过限制，那么新创建一个 quicklistNode 节点，然后将新节点插入到 quicklist 双向链表中

2. 从中间位置插入：

• 需要把当前 ziplist 分裂成两个节点，然后在其中一个节点上插入数据

6.2.2 查找操作

根据node 的个数找到对应的 ziplist,然后再调用 ziplist 的 index 就能成功找到

6.2.3 删除操作

利用 quicklistDelRange 函数：返回1时表示成功删除指定区间元素，返回0表示没有删除任何元素

在区间删除时，会先找到 start 所在的 quicklistNode ，计算删除的元素是否小于删除的 count，如果不满足删除的个数，则会移动至下一个 quicklistNode 继续删除，依次循环直到删除完成为止。

参考资料：

《Redis 设计与实现》

《Redis 开发与运维》

Redis数据结构——快速列表(quicklist)

https://pdai.tech/md/db/nosql-redis/db-redis-x-redis-ds.html