redis底层采用的数据结构

发表于 更新于 分类于
本文字数： 5.4k 阅读时长 ≈ 5 分钟

介绍

  redis是用C语言编写的，底层自己设计了一些数据结构，用这些数据结构完成了对外功能的提供。常说的redis可以存储的几种数据结构，底层就是采用这些数据结构实现的。

  redis底层的数据结构有：

  • SDS：简单动态字符串
  • list：链表
  • dict：字典
  • skiplist：跳跃表
  • intset：整数集合
  • ziplist：压缩列表

实现

SDS：简单动态字符串

定义

  redis采用C语言编写，但是redis中的字符串并没有使用C语言提供的字符串，而是自己定义了一种SDS的结构体，用来保存字符串。

1
2
3
4
5
6
7
8
9
10
11
struct sdshdr {  
      
    // buf 中已占用空间的长度  
    int len;  
  
    // buf 中剩余可用空间的长度  
    int free;  
  
    // 数据空间  
    char buf[];  
};
  • len变量：用于记录buf中已经使用的空间长度
  • free变量：用于记录buf中还空余的空间
  • buf：字符数组，用于记录我们的字符串

区别

  传统的C语言中，采用长度为N+1的字符数组来保存长度为N的字符串，这样做在获取长度，字符串扩展等操作中效率缓慢。
  SDS与传统的C语言字符串有一些优点：

  • 获取字符串长度快速O(1)与O(n)
  • 杜绝缓冲区溢出
    • C语言不记录字符串长度，除了获取的时候复杂度高以外，还容易导致缓冲区溢出。修改前面的字符串，不重新分配空间的情况下，有可能覆盖后面的字符串。
    • SDS中不会发生溢出，当我们需要对一个SDS 进行修改的时候，redis 会在执行拼接操作之前，预先检查给定SDS 空间是否足够，如果不够，会先拓展SDS 的空间，然后再执行拼接操作。
  • 减少修改字符串时带来的内存重新分配次数
    • 字符串拼接会产生字符串的内存空间的扩充，在拼接的过程中，原来的字符串的大小很可能小于拼接后的字符串的大小，那么这样的话，就会导致一旦忘记申请分配空间，就会导致内存的溢出。
    • 字符串在进行收缩的时候，内存空间会相应的收缩，而如果在进行字符串的切割的时候，没有对内存的空间进行一个重新分配，那么这部分多出来的空间就成为了内存泄露。
  • 二进制安全

      字符串中的字符必须符合某种编码，并且除了字符串的末尾之外，字符串里面不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存想图片，音频，视频，压缩文件这样的二进制数据。
      但是在Redis中，不是靠空字符来判断字符串的结束的，而是通过len这个属性。那么，即便是中间出现了空字符对于SDS来说，读取该字符仍然是可以的。

  • 惰性空间释放

    通过len与free参数，减少了扩展与收缩操作的次数。

  • 兼容部分C语言字符串

List：链表

  链表提供了搞笑的节点重排能力，以及顺序性的节点访问方式，并且可以通过增删节点来灵活地调整链表的长度。
  列表键的底层实现之一就是链表。当一个列表键包含了数量较多的元素，又或者列表中包含的元素都是比较长的字符串时，Redis就会使用链表作为列表键的底层实现。

定义

  链表的定义分为链表节点的定义和链表的定义。redis中的链表是一个双端链表。

  链表节点的定义：

1
2
3
4
5
typedef struct listNode{
      struct listNode * prev;
      struct listNode * next;
      void * value;  
}

  链表的定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct list{
    // 表头节点
    listNode  * head;
    // 表尾节点
    listNode  * tail;
    // 链表长度
    unsigned long len;
    // 节点值复制函数
    void *(*dup) (void *ptr);
    // 节点值释放函数
    void (*free) (void *ptr);
    // 节点值对比函数
    int (*match)(void *ptr, void *key);
}

特点

  • 双端：链表节点带有prev 和next 指针，获取某个节点的前置节点和后置节点的时间复杂度都是O（N）
  • 无环：表头节点的 prev 指针和表尾节点的next 都指向NULL，对立案表的访问时以NULL为截止
  • 表头和表尾：因为链表带有head指针和tail 指针，程序获取链表头结点和尾节点的时间复杂度为O(1)
  • 长度计数：链表中存有记录链表长度的属性 len
  • 多态：链表节点使用 void* 指针来保存节点值，并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

Dict：字典

  字典，又称为符号表（symbol table）、关联数组（associative array）或映射（map），是一种用于保存键值对的抽象数据结构。
  在字典中，一个键（key）可以和一个值（value）进行关联，字典中的每个键都是独一无二的。在C语言中，并没有这种数据结构，但是Redis 中构建了自己的字典实现。

定义

  字典的定义分为三块，分别是字典定义，哈希表定义，哈希节点定义。

  字典定义：

1
2
3
4
5
6
7
8
9
10
11
typedef struct dict {
    // 类型特定函数
    dictType *type;
    // 私有数据
    void *privedata;
    // 哈希表
    dictht  ht[2];
    // rehash 索引
    in trehashidx;

}

  哈希表定义：

1
2
3
4
5
6
7
8
9
10
11
typedef struct dictht {
   //哈希表数组
   dictEntry **table;
   //哈希表大小
   unsigned long size;

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

  哈希节点定义：

1
2
3
4
5
6
7
8
9
10
11
typeof struct dictEntry{
   //键
   void *key;
   //值
   union{
      void *val;
      uint64_tu64;
      int64_ts64;
   }
   struct dictEntry *next;
}

  它们之间的结构关系如下图：

redis字典的结构

  可以看出来，结构的后半程同hashmap的接口类似，同样也是采用了链地址法来解决hash冲突的问题。

扩展与收缩

  随着对哈希表的不断操作，哈希表保存的键值对会逐渐的发生改变，为了让哈希表的负载因子维持在一个合理的范围之内，我们需要对哈希表的大小进行相应的扩展或者压缩，这时候，我们可以通过 rehash（重新散列）操作来完成。
  哈希表的空间分配规则：

  1. 如果执行的是拓展操作，那么ht[1]的大小为第一个大于等于ht[0]的2的n次幂
  2. 如果执行的是收缩操作，那么ht[1] 的大小为第一个大于等于ht[0] 的2的n次幂

  扩展流程：

  1. ht[0]满数据的情况下
  2. 为ht[1]按照上面的逻辑分配空间
  3. 讲ht[0]的数据转移进ht[1]，这个过程中需要重新进行hash计算
  4. 将ht[0]释放，将ht[1]设置为新的ht[0]

  数据量较小的时候，可以通过这种方式进行扩容，实际情况下一般采用渐进式rehash。采用渐进式rehash 的好处在于它采取分而治之的方式，避免了集中式rehash 带来的庞大计算量。流程基本是：

  1. 为ht[1] 分配空间，让字典同时持有ht[0]和ht[1]两个哈希表
  2. 在几点钟维持一个索引计数器变量rehashidx，并将它的值设置为0，表示rehash开始
  3. 在rehash进行期间，每次对字典执行CRUD操作时，程序除了执行指定的操作以外，还会将ht[0]中的数据rehash到ht[1]表中，并且将rehashidx加一
  4. 当ht[0]中所有数据转移到ht[1]中时，将rehashidx 设置成-1，表示rehash结束

SkipList：跳表

  跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。
  Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另外一个是在集群节点中用作内部数据结构。

定义

  跳跃表的定义分为两块，表定义和节点定义。
  数据节点定义：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
typedef struct zskiplistNode{
　　　//层
     struct zskiplistLevel{
　　　　　//前进指针
        struct zskiplistNode *forward;
　　　　//跨度
        unsigned int span;
    } level[];
　　//后退指针
    struct zskiplistNode *backward;
　　//分值
    double score;
　　//成员对象
    robj *obj;
}
  • 层：level数组可以包含多个元素，每个元素都包含一个指向其他节点的指针。
  • 前进指针：用于指向表尾方向的前进指针
  • 跨度：用于记录两个节点之间的距离
  • 后退指针：用于从表尾向表头方向访问节点
  • 分值和成员：跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串，这个字符串对象保存着一个SDS值

  跳跃表定义：

1
2
3
4
5
6
7
8
9
typedef struct zskiplist {
     //表头节点和表尾节点
     struct zskiplistNode *header,*tail;
     //表中节点数量
     unsigned long length;
     //表中层数最大的节点的层数
     int level;

}zskiplist;

特点

  • 跳跃表是有序集合的底层实现之一
  • 主要有zskiplist 和zskiplistNode两个结构组成
  • 每个跳跃表节点的层高都是1至32之间的随机数
  • 在同一个跳跃表中，多个节点可以包含相同的分值，但每个节点的对象必须是唯一的
  • 节点按照分值的大小从大到小排序，如果分值相同，则按成员对象大小排序

IntSet：整数集合

  整数集合是集合建的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。
  其实就是一个特殊的集合，里面存储的数据只能够是整数，并且数据量不能过大。

定义

1
2
3
4
5
6
7
8
9
typedef struct intset{
    //编码方式
    uint32_t enconding;
   // 集合包含的元素数量
    uint32_t length;
    //保存元素的数组    
    int8_t contents[];

}
  • encoding：整数集合的编码方式
  • length：集合中的元素数量
  • contents：用于保存元素的数组

升级

  intset 在默认情况下会帮我们设定整数集合中的编码方式，但是当我们存入的整数不符合整数集合中的编码格式时，就需要使用到Redis 中的升级策略来解决。流程基本有：

  1. 根据新元素的类型，扩展整数集合底层数组的空间大小，并为新元素分配空间
  2. 将底层数组现有的所有元素都转换成新的编码格式，重新分配空间
  3. 将新元素加入到底层数组中

  升级策略的实现可以提升整数集合的灵活性，节约内存。

特点

  • 整数集合是集合建的底层实现之一
  • 整数集合的底层实现为数组，这个数组以有序，无重复的范式保存集合元素，在有需要时，程序会根据新添加的元素类型改变这个数组的类型
  • 升级操作为整数集合带来了操作上的灵活性，并且尽可能地节约了内存
  • 整数集合只支持升级操作，不支持降级操作

ZipList：压缩列表

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

定义

  压缩列表的结构如图所示：

压缩列表的结构

  • zlbytes：用于记录整个压缩列表占用的内存字节数
  • zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节
  • zllen：记录了压缩列表包含的节点数量
  • entryX：列表保存的各个节点
  • zlend：用于标记压缩列表的末端

特点

  • 压缩列表是一种为了节约内存而开发的顺序型数据结构
  • 压缩列表被用作列表键和哈希键的底层实现之一
  • 压缩列表可以包含多个节点，每个节点可以保存一个字节数组或者整数值
  • 添加新节点到压缩列表，可能会引发连锁更新操作

参考文献 & 鸣谢

相关文章