Redis设计与实现（二）、内部映射数据结构

| 分类 redis  | 标签 redis 

##前言

上一章我们介绍了redis的内部结构：

  • 字符串
  • 双端链表
  • 字典
  • 跳跃表

但是，创建这些完整的数据结构是比较耗费内存的，如果对于一个特别简单的元素，使用这些数据结构无异于大材小用。为了解决这个问题，redis在条件允许的情况下，会使用内存映射数据结构来代替内部数据结构，主要有：

  1. 整数集合 intset
  2. 压缩列表 ziplist

当然了，因为这些结构是和内存直接打交道的，就有节省内存的优点，而又因为对内存的操作比较复杂，所以也有操作复杂，占用的CPU时间更多的缺点。

这个要掌握一个平衡，才能使redis的总体效率更好。目前，redis使用两种内存映射数据结构。

###1. 整数集合

整数集合用于有序、无重复的保存多个整数值，它会根据元素的值，自动选择该用什么长度的整数类型来保存元素。比如，在一个int set中，最大的元素可以用int16_t保存，那么这个int set的所有元素都是int16_t，当插入一个元素是int32_t的时候，int set会先将所有元素升级为int32_t，再插入这个元素。总的来说，整数集合会自动升级。

看名字我们就知道它的用途：

  1. 只保存整数元素
  2. 元素的数量不多[因为它不费内存，费CPU。量多的话，肯定是CPU为第一考虑]

那么我们看一下 intset 的定义：

1
2
3
4
5
6
7
8
9
10
11
12

typedef struct intset {

    // 保存元素所使用的类型的长度
    uint32_t encoding;

    // 元素个数
    uint32_t length;    

    // 保存元素的数组
    int8_t contents[];  

} intset;

其中 encoding 保存的是 intset 中元素的编码类型，比如是 int16_t还是 int32_t等等。具体的定义在 intset.c 中：

1
2
3

#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

length 肯定就是元素的个数喽，然后是具体的元素，我们发现是 int8_t 类型的，实现上它只是一个象征意义上的类型，到实际分配时候，会根据具体元素的类型选择合适的类型。而且 contents 有两个特点：

  1. 没有重复元素
  2. 元素在数组中从小到大排序

所以，添加元素到intset有下面几个步骤：

  1. 判断插入元素是否存在于集合，如果存在，没有任何操作(无重复元素)
  2. 看元素的长度是否需要把intset升级，如果需要，先升级
  3. 插入元素，而且要保证在contents数组中，从小到大排序
  4. 维护length

简单总结一下整数集合的特点：

  1. 保存有序、无重复的整数元素
  2. 根据元素的值自动选择对应的类型，但是int set只升级、不降级
  3. 升级会引起整个int set中的contents数组重新内存分配，并移动所有的元素（因为内存不一样了），所以复杂度为O(N)
  4. 因为int set是有序的，所以查找使用的是binary search

###2. 压缩列表

本质来说，压缩列表就是由一系列特殊编码的内存块构成的列表，一个压缩列表可以包含多个节点，每个节点可以保存一个长度受限的字符数组（不以为\0结尾的char数组）或者整数。说白了，它是以内存为中心的数据结构，一般列表是以元素类型的字节总数为大小，而压缩列表是以它最小内存块进行扩展组成的列表。下面我来说一下。

压缩列表分为3个部分：

  • header：10字节，保存整个压缩列表的信息，有尾节点到head的偏移量、节点个数、整个压缩列表的内存（字节）
  • 节点：一个结构体、由前一个节点的大小（用于向前遍历）、元素类型and长度、具体值组成
  • 哨兵：就是一个1字节的全为1的内存，表示一个压缩列表的结束

其中压缩列表的节点值得说一下，它可以存储两类数据：

  • 字符串
  • 整数

那么，怎样实现呢？很简单，通过 encoding + length 就可以搞定。encoding 占2位，00，01，10，11表示不明的类型，只有11代表的是节点中存放的是整型，其他3个代表节点中存放的都是字符串。而根据这2位的不同，又对应着不同的长度。

所以，由 encoding 可以知道元素的类型和这个元素的范围（比如 encoding 为01，包括 encoding 在内的2byte 代表长度，所以最长是2^14 - 1；如果 encoding 为00，包括 encoding 在内的1byte 代表元素的长度，所以最大值为2^6 -1 ）

然后添加元素大概是下面酱紫滴（对于列表来说，添加元素默认是加在列表尾巴的）：

  • 首先通过压缩列表的head信息，找到压缩列表的尾巴到head的偏移量（因为可能重新分配内存，所以指针的话会失效）
  • 根据要插入的值，计算出编码类型和插入值的长度。然后还有前一个节点所用的空间、然后对压缩列表进行内存充分配
  • 初始化entry节点的所有相关信息：pre_entry_length、encoding、length、content
  • 更新head中的长度啦、尾偏移啦、压缩列表总字节啦

上面吐槽了压缩列表没有next指针，现在发现有了= =，但是不是指针，因为压缩列表会进行内存充分配，所以指针代表的内存地址需要一直维护，而当使用偏移量的话，就不需要更改一次维护一次。向后遍历是通过头指针+节点的大小（pre_entry_length+encoding+length的总大小）就可以跳到下一个节点了

不过，说实话，压缩列表这个设计的好处我还没有看到，可能还需要和后面的东西结合吧。

重读之后看到了，(^__^) 嘻嘻……

本质上面已经说的很清楚了——节省内存。所以它不像上一章讲到的那种分配固定的大小，而 intset 和 ziplist 完全是根据内存定做的，一个字节也不多（当然，有些操作还是会有浪费的）。


上一篇     下一篇