redis 数据结构与对象

﹏ヽ暗。殇╰゛Y 2022-02-15 10:11 197阅读 0赞

本文基于《Redis 设计与实现》黄建宏著：第一部分整理。

# 数据结构 #

简单说下redis的数据结构，这些在网上也都有很详细的解释，《Redis 设计与实现》这本书基于Redis3.0的，但是现在已经5.0 了，所以有些数据结构发生了变化，其中我自己实现发现了一部分，可能还有没发现的。慢慢实践吧

## 简单动态字符串(Simple dynamic string) ##

简单动态字符串是在C语音传统的字符串基础上构建的，其数据结构为：

struct sdshdr {  
        // buf 中已占用空间的长度  
        // 等于SDS所保存字符串的长度
        int len; 
        
        // buf 中剩余可用空间的长度  
        int free;  
      
        // 数据空间 ，用于保存字符串
        char buf[];  
    };

与C语音传统字符串区别为：

<table> 
 <thead> 
  <tr> 
   <th>C字符串</th> 
   <th>SDS</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>获取字符串长度的复杂度为O(N)</td> 
   <td>获取字符串长度的复杂度为O(1)</td> 
  </tr> 
  <tr> 
   <td>API是不安全的，可能会造成缓冲区溢出</td> 
   <td>API是安全的，不会造成缓冲区溢出</td> 
  </tr> 
  <tr> 
   <td>修改字符串长度N次必然需要执行N次内存重分配</td> 
   <td>修改字符串长度N次最多需要执行N次内存重分配</td> 
  </tr> 
  <tr> 
   <td>只能保存文本数据</td> 
   <td>可以保存文本或者二进制数据</td> 
  </tr> 
  <tr> 
   <td>可以使用所有&lt;stirng.h&gt;库中的函数</td> 
   <td>可以使用一部分&lt;string.h&gt;库中的函数</td> 
  </tr> 
 </tbody> 
</table>

所以简单动态字符串，我对简单和动态的理解是：  
简单：

1.  查询字符串长度方便
2.  可以使用部分<string.h>库中的函数
3.  可以保存不止文本的数据

动态：

1.  api是安全的，不会因为增加字符串长度造成缓冲区溢出

## 链表（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);
    } list;
    
    typedef struct listNode {
    	// 前置节点
    	struct listNode * prev;
    	// 后直节点
    	struct listNode * next;
    	// 节点的值
    	void * value;
    } listNode；

多个listNode可以通过prev和next指针组成双端链表。虽然仅仅使用多个listNode结构就可以组成链表，但是用list来持有链表的话，操作起来会更方便。

redis链表实现的特性可以总结如下：

1.  双端：链表节点带有prev 和 next 指针，获取某个节点的前置节点后和后置节点的复杂度都是O(1)。
2.  无环：表头节点的prev指针和表尾节点的next指针都只想null，对链表的访问以NULL为终点。
3.  带表头指针和表尾指针：通过list结构的head指针和tail指针，程序获取链表的表头节点和表尾节点的复杂都都是O(1)。
4.  带链表长度计数器：程序使用list结构的len属性来对list持有的链表节点进行技术，程序获取链表中节点数量的复杂度为O(1)。
5.  多态：链表节点使用void\* 指针来保存节点值，并且可以通过list结构的dup、free、match三个属性为节点值设置类型特定函数，所以链表可以用于保存各种不同类型的值。

## 字典 ##

字典，又称为符号表（symbol table），关联数组（associative array）或者 映射（map），是一种用于保存键值对的抽象数据结构。

字典也是哈希键的底层实现之一：当一个哈希键包含的键值对比较多，又或者键值对中的元素都是比较长的字符串时，Redis就会使用字段作为哈希键的底层实现。

### Redis字典所使用的哈希表有dictht结构定义 ###

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

### 哈希表节点 ###

typeof struct dictEntry{
       //键
       void *key;
       //值
       union{
          void *val;
          uint64_tu64;
          int64_ts64;
       } v;
       // 指向下个哈希表节点，形成链表
       struct dictEntry *next;
    } dictEntry

### Redis中的字典由dict结构表示： ###

typedef struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privedata;
        // 哈希表
        dictht  ht[2];
        // rehash 索引，当rehash不再进行时，值为-1
        in trehashidx;
    } dict

#### 哈希算法 & 哈希冲突 ####

既然是哈希表，那么一定要有要通过哈希算法来插入数据，同时还要解决哈希冲突。  
这里不去细说哈希算法，而Redis字典通过**链地址法**来解决键冲突。

#### 渐进式rehash ####

同样随着操作的不断进行。哈希表的键值对会逐渐的增多或者减少。为了让哈希表的负载因子维持在一个合理的范围之内，当哈希表保存的键值对数量太多或者太少时，程序需要对哈希表的大小进行相应的拓展或者收缩。拓展和收缩哈希表的工作可以通过制定rehash(重新散列)操作来完成。同时rehash动作不是一次性、集中式的完成的，而是分多次、渐进式的完成的。

> 每个字典带有两个哈希表，一个平时使用(ht\[0\])，另一个仅在进行rehash时使用(ht\[1\])。在rehash过程中，新添加到字典的键值对一律会被保存到ht\[1\]里面，而ht\[0\]则不再进行任何添加操作，这一措施保证了ht\[0\]包含的键值对数量会只减不增，并随着rehash操作的执行而最终变成空表。

哈希表渐进式rehash的详细步骤：

1.  为ht\[1\] 分配空间，让字典同时持有ht\[0\]和ht\[1\]两个哈希表。
2.  在字典维持一个索引计数器变量 rehashidx，并将它的值设置为0，表示rehash 开始。
3.  在rehash 进行期间，每次对字典执行添加、删除、查找或者更新操作时，程序除了执行指定的操作以外，还会将ht\[0\]哈希表在 rehashidx 索引上的所有键值对 rehash到 ht\[1\]，当rehash工作完成之后，程序将 rehashidx 属性的值增一。
4.  随着字典操作的不断执行，最终在某个时间点上 ht\[0\] 的所有键值对都会被rehash 至 ht\[1\]，这时程序将 rehashidx 属性的值设置为 -1，表示rehash操作已经完成。

## 跳跃表 ##

跳跃表（skiplist）是一种有序数据结构，它通过在每个节点中维持多个指向其他节点的指针，从而达到快速访问节点的目的。

跳跃表是一种随机化的数据,跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 ——查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

Redis 只在两个地方用到了跳跃表，一个是实现有序集合键，另外一个是在集群节点中用作内部数据结构。

redis的跳跃表实现由zskiplist 和 zskiplistNode 两个结构组成，其中zskiplist 用于保存跳跃表信息（比如表头界定啊，表尾节点，长度），而zskiplistNode 则用于表示跳跃表节点。

### zskiplistNode ###

zskiplistNode 数据结构

typedef struct zskiplistNode{
    　//后退指针
        struct zskiplistNode *backward;
    	//分值
        double score;
    　//成员对象
        robj *obj;
    　  //层
         struct zskiplistLevel{
    　　	//前进指针
            struct zskiplistNode *forward;
    　　//跨度
            unsigned int span;
        } level[];
    } zskiplistNode;

## 整数集合 ##

整数集合是集合建的底层实现之一，当一个集合中只包含整数，且这个集合中的元素数量不多时，redis就会使用整数集合intset作为集合的底层实现。整数集合可以存储INT16，INT32，INT64类型的整数。

### intset ###

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

contents数组是整数集合的底层实现，contents数字的真正类型取决于encoding属性的值。  
支持整数集合的升级：提升整数集合的灵活性，同时尽可能的节约内存。但是整数集合不支持降级操作。一旦升级后，就会位置升级后的状态。

## 压缩列表 ##

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

压缩列表的构成：

<table> 
 <thead> 
  <tr> 
   <th>zlbytes</th> 
   <th>zltail</th> 
   <th>zllen</th> 
   <th>entry-1</th> 
   <th>entry-2</th> 
   <th>…</th> 
   <th>zlend</th> 
  </tr> 
 </thead> 
 <tbody></tbody> 
</table>

1.  zlbytes:用于记录整个压缩列表占用的内存字节数
2.  zltail：记录要列表尾节点距离压缩列表的起始地址有多少字节
3.  zllen：记录了压缩列表包含的节点数量。
4.  entry-x：要说列表包含的各个节点
5.  zlend：用于标记压缩列表的末端

## quickList ##

quickList并没有在书中提到，因为quickList是一个3.2版本之后新增的基础数据结构，是 redis 自定义的一种复杂数据结构。将ziplist和adlist结合到了一个数据结构中。主要是作为list的基础数据结构。  
在3.2之前，list是根据元素数量的多少采用ziplist或者adlist作为基础数据结构，3.2之后统一改用quicklist，从数据结构的角度来说quicklist结合了两种数据结构的优缺点，复杂但是实用：

### quickList ###

typedef struct quicklist {
        quicklistNode *head;        // 指向quicklist的头部
        quicklistNode *tail;        // 指向quicklist的尾部
        unsigned long count;        // 列表中所有数据项的个数总和
        unsigned int len;           // quicklist节点的个数，即ziplist的个数
        int fill : 16;              // ziplist大小限定，由list-max-ziplist-size给定
        unsigned int compress : 16; // 节点压缩深度设置，由list-compress-depth给定
    } quicklist;

### quicklistNode： ###

typedef struct quicklistNode {
        struct quicklistNode *prev; // 前一个节点
        struct quicklistNode *next; // 后一个节点
        unsigned char *zl;  // ziplist-------重点
        unsigned int sz;             // ziplist的内存大小
        unsigned int count : 16;     // zpilist中数据项的个数
        unsigned int encoding : 2;   // 1为ziplist 2是LZF压缩存储方式
        unsigned int container : 2;  
        unsigned int recompress : 1;   // 压缩标志, 为1 是压缩
        unsigned int attempted_compress : 1; // 节点是否能够被压缩,只用在测试
        unsigned int extra : 10; /* more bits to steal for future usage */
    } quicklistNode;

由于quicklist结构包含了压缩表和链表，那么每个quicklistNode的大小就是一个需要仔细考量的点。如果单个quicklistNode存储的数据太多，就会影响插入效率；但是如果单个quicklistNode太小，就会变得跟链表一样造成空间浪费。

quicklist通过源代码中fill对单个quicklistNode的大小进行限制，而fill字段会读取配置中的list-max-ziplist-size参数值。  
`list-max-ziplist-size -2`：fill可以被赋值为正整数或负整数，当fill为负数时：

*  \-1：单个节点最多存储4kb
 *  \-2：单个节点最多存储8kb（-2是Redis给出的默认值）
 *  \-3：单个节点最多存储16kb
 *  \-4：单个节点最多存储32kb
 *  \-5：单个节点最多存储64kb
 *  为正数时，表示单个节点最大允许的元素个数，最大为32768个

还有一个参数list-compress-depth表示列表两头不压缩的节点的个数

*  0 特殊值，表示不压缩
 *  1 表示quicklist两端各有一个节点不压缩，中间的节点压缩
 *  2 表示quicklist两端各有两个节点不压缩，中间的节点压缩
 *  3 表示quicklist两端各有三个节点不压缩，中间的节点压缩

### 总结 ###

quicklist除了常用的增删改查外还提供了merge、将ziplist转换为quicklist等api，这里就不详解了，可以具体查看quicklist.h和quicklist.c文件。

*  quicklist是 redis 在ziplist和adlist两种数据结构的基础上融合而成的一个实用的复杂数据结构
 *  quicklist在3.2之后取代adlist和ziplist作为list的基础数据类型
 *  quicklist的大部分api都是直接复用ziplist
 *  quicklist的单个节点最大存储默认为8kb
 *  quicklist提供了基于lzf算法的压缩api，通过将不常用的中间节点数据压缩达到节省内存的目的