Redis设计与实现（四）

逃离我推掉我的手 2022-02-25 01:10 235阅读 0赞

# 整数集合和压缩列表 #

## 整数集合（intset） ##

### 整数集合概念 ###

*  整数集合是一个集合（set）
 *  整数集合里只包含整数，并且集合元素不能太多
 *  整数集合不会有重复的元素（有重复元素集合就没意义了）

### 整数集合的实现方式 ###

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

*  encoding : 保存编码方式
 *  length ： 保存元素的数量（数组的元素个数）
 *  contents : 保存set里的元素，数组里的元素按从小到大有序排列

> 那么在整数集合怎么保证它的有序性？

它根据的是数组的插入排序，先确定好位置，然后插进去，后边的元素后移。

> 在整数集合中可以保存int\_16,int\_32,int\_64的整数

那在整数集合中怎样处理这几种整数类型之间的关系呢？假设数组中的最大值为x。

*  \-32768（-2e15） < x < 32761（（2e15）-1） : 那么它就是用int\_16的编码方式
 *  \-2147483648（-2e31） < x < 2147483647((2e31)-1) : 那么它就是用的int\_32的编码方式
 *  \-9223372036854775808(-2e63) < x < 9223372036854775807((2e63)-1) : 那么它就使用int\_64的编码方式

> 那如果我在集合中加了超过此编码方式的极限呢？比如：本来是16位，但是我要存100000，因此就有了下边的升级操作了。

### 升级 ###

当我们要添加一个新元素并且新元素的值**大于或小于**当前的所能存取值的极限，因此，在存之前内部要对整数集合进行升级，然后将我们的值存进去。

升级的步骤：

1.  根据新元素类型，扩展空间，并为新元素分配空间
2.  将其余数也换位该元素类型，并维持底层有序性
3.  将新元素加到数组里

升级的好处：

1.  节约空间
2.  提升整数集合的灵活性（随意添加元素不怕类型有误，内部会自动转类型）

> 那升级了，然后我把超出极限的元素移出来了，是不是能降级了？

整数集合不支持降级操作，升级后就一直保存这种编码方式，除非再次升级。就和我们玩的象棋里的士兵一样。

## 压缩列表（ziplist） ##

### 压缩列表的概念 ###

*  Redis为节约内存而开发的，由一系列特殊编码的连续内存块组成的顺序型（sequential）数据结构。
 *  在Redis里被用作哈希键的底层实现之一：当列表键只包含少量的列表项，并且每个列表项都要是小整数或者是短字符串。
 *  由多个节点（entry）组成，每个节点保存一个字节数组（字符串）或者一个整数。

### 压缩列表的实现方式 ###

struct ziplist<T> {
    
        // 整个压缩列表占用字节数
        int32 zlbytes; 
    
        // 最后一个元素距离压缩列表起始位置的偏移量，用于快速定位到最后一个节点
        int32 zltail_offset; 
    
        //元素个数，键值对的个数，也就的T的长度
        int16 zllen; 
        
        //键值对，顺序存储
        T[] entries; 
    
         // 标志压缩列表的结束，值恒为 0xFF
        int8 zlend;
    }

*  zlbytes : 记录整个压缩列表占的字节数：在内存重分配或者计算zlend时使用
 *  zltail\_offset : 通过偏移量可以很方便的找到尾节点
 *  zllen ： 记录节点数量，如果数量超过或等于65535（zllen占用2个字节）时需要遍历整个压缩列表才能得出。
 *  entries ： 保存节点内容
 *  zlend ： 是一个常量标志结束。

### 压缩列表节点的实现方式 ###

struct entry {
    
         // 前一个 entry 的字节长度
        int<var> previous_entry_length;
    
        //元素的编码
        int<var> encoding; 
        
        //内容
        optional byte[] content;
    
    }

*  previous\_entry\_length : 保存前一个节点长度，长度可以为1个字节或5个字节。
    
    1.  1个字节 ： 在这个字节里就保存前一个节点的长度（小于254）
    2.  5个字节 ： 当前一个节点的长度大于等于254，那就采用五个字节。前一个字节为固定的OxFE（254），后四个字节存  
        储前一个节点的长度。比如：OxFE00002768 表示的是Ox00002766（十进制是10088）
 *  encoding ： 记录的是content属性中保存的类型和长度。
    
    1.  如果是字节数组，encoding可以是一字节，两字节，五字节分别以00，01，10打头。
    2.  如果是整数，那就是一个字节以11打头。
 *  content ： 保存节点的内容

### 连锁更新问题 ###

> 那如果由一个这样的情况 ： 在压缩列表由多个长度介于250-253的节点，我们要在表头节点插入一个新的节点（比较大的），但是它后一个节点的previous\_entry\_length用一个字节保存不了，因此它会采用五个字节来保存，因此新节点的后一个节点占用的字节数就增多为254以上，然后又很巧合这个节点的下一个节点长度也是介于250-253，然后它也增多为254以上，然后导致它后边节点的字节变化。这个就是连锁更新问题。程序需要对压缩列表不断的进行重分配操作。

当然，上边的情况只是连锁更新的一种，删除节点也同样会发生连锁更新问题。

> 比如是在一个small节点（小于254），它的前边是一个big节点（大于254），然后在small节点后都是介于250-253大小的节点，当我们删除small节点时，就会引起后边节点的存储空间变化，也同样会导致连锁更新。

那连锁更新会不会让我们的性能很低下，那为什么redis还要使用这种数据结构呢？

> 虽然有连锁更新，但是如上边案例的事件发生率很小，要连续多个介于250-253大小的节点的概率很小，就算有的话，不是特别多也能很快的解决，不会影响效率。