redis 数据结构分析

   REDIS底层数据结构

 一.redis的字符串

   redis底层使用SDS(simple dynamic string) 作为默认字符串表示.SDS还被用作缓冲区,AOF模块的缓冲区以及客户端状态中的输入缓冲区.

 

    1.1  SDS的定义    

struct sdshdr{
   int len;//字符串长度
   int free;//数组中未使用的长度
   char buff[];//字符数组
}

   

   与C语言的字符串相比,SDS获取字符串长度的时间复杂度为o(1),SDS还杜绝了缓冲区溢出的情况。

   

   1.2 SDS的空间分配优化策略

      

        1.2.1 空间预分配

            

          如果对SDS进行修改,长度小于1MB,那么程序分配和len属性同样大小的空间.如果大于1M,那么会分配1MB的未使用空间.

 

         1.2.2 惰性空间释放

 

  1.3 二进制安全

 

     C语言默认以空字符结尾,所以不能保存图片,音频等,SDS通过len属性来判断是否到结尾了,所以可以保存二进制数据.

 

             

二.redis的链表结构

 

    2.1 链表的数据结构

     

typedef struct  listNode{
    listNode *head;
    listNode *tail;
   unsigned long len;//节点数量
   void * dup(void * ptr)//复制函数
   void * free(void * ptr)//释放函数
   void * match(void * ptr,void * key)//对比函数
}

 

typedef struct  listNode{

   struct  listNode *prev;
   struct listNode * next;
   void * value;//节点的值
}

    

     列表被广泛用于实现redis的各种功能,比如列表键,发布于订阅,慢查询,监视器.

     

三.redis的字典结构(SET)

    字典使用哈希表作为底层的实现.

    3.1 哈希表的数据结构

               

typede struct dictht{
   dicEntry **table;//哈希表数组
   unsigned long size;//哈希表大小
   unsigned  long sizemark;//掩码用于计算索引值
   unsigned long used;//已有节点的数量
}

    table是一个数组,每个元素都指向一个dictEntry结构的指针,每个dicEntry保存一个键值对

   

       

        3.1.1 哈希表节点

          

typedef struct dictEntry{
    
    void *key;

    union{
      void *val;
      uint64_tu64;
      int64_ts64;

   }
   struct dictEntry * next;
}

       3.1.2 字典 

         

typede struct dict{

   dictType *type;
   void * privdata;//私有数据
   dicttht ht[2];//哈希表
    ／／rehash索引,当rehash不在进行时,值为-1
    int rehashidx;
}

     一般情况下,只用ht[0]哈希表,ht[1]只会在rehash时使用.rehashidx 记录目前rehash的进度.因为dictEntry节点组成的链表没有指向链表表尾的指针,所以总是把新节点添加到链表的表头位置.

 当哈希表的键值对过多或者过少,需要对哈希表进行rehash.

 

      为字典ht[1]分配空间

• 如果是扩展操作,ht[1]的大小为第一个大于等于ht[0].used*2的2的n次方,
• 如果是收缩操作,ht[1]的大小为第一个大于等于ht[0].used的2的n次方.
• 将所有ht[0]的键值对rehash到ht[1]上
• 当ht[0]的所有键值对都rehash完毕,释放ht[0]的空间,将ht[1]设置成ht[0],并在ht[1]创建一个空的哈希表. 
•  
  
   
  
   
  
   
  
      3.1.3 rehash的条件

        当以下其中一个条件满足时,会进行rehash

•    服务器目前没有在进行bgsave或者bgrewriteaof,并且负载因子大于等于1
•    服务器目前在进行bgsave或者bgrewriteaof,并且负载因子大于等于5

           load_factor = ht[0].used/ht[0].size(负载因子 = 已保存的节点数量/哈希表大小).另一方面, 当负载因子小于0.1的时候,会采取收缩操作.

        3.1.4  渐进式rehash

           rehash并不是一次性完成的,而是分多次渐进式完成的.这样做的原因在于,如果数据了过大,可能导致服务器在一定时间内停止服务.

           以下是rehash的详细步骤:

•    为ht[1]分配空间,让字典同时拥有两个哈希表
•    把rehashidx值设置为0，表示正在进行rehash
•    在rehash期间,对字典的操作都会映射到两个哈希表,同时还会顺带奖ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],rehash完成时,rehashidx自动加一.
•    随着字典操作的不断执行,最终在某个时间点ht[0]的所有键值对会被全部rehash到ht[1]上,这时,rehashidx被设置成-1,表示rehash完成.
• 
   
  
   
  
   
  
   
  
   
  四.redis的跳跃表(skiplist)

       跳表是一种有序的数据结构,采用了用空间换时间的思想来加快访问的速度.它主要用于有序集合键以及集群节点中用做内部结构. 

       4.1跳表的实现

        

   最左边的结构是zskiplist：

     header:指向跳表表头

     tail:指向跳表表尾

 .   level:代表跳表的层数.

     length:代表跳表的节点数量

   

 

  右边的代表zskiplistnode结构:

    层:节点中L1代表第一层,L2代表第二次,以此类推

    分值(score):各个节点的值,按从小到大排序

    成员对象(obj):o1,o2,o3是节点保存的成员变量

  

   3.2跳表的数据结构

 

typedef struct zskiplistNode {  
    robj *obj; //节点数据  
    double score;  
    struct zskiplistNode*backward; //后退指针  
    struct zskiplistLevel {  
        struct zskiplistNode*forward;//前进指针
        unsigned int span;//该层跨越的节点数量  
    } level[];  
} zskiplistNode;  
   
typedef struct zskiplist {  
    struct zskiplistNode*header, *tail;  
    unsigned long length;//节点的数目  
    int level;//目前表的最大层数  
} zskiplist;

 （PS:每个跳表节点的层高都在0-32之间）

  五.整数集合（intset）

   整数集合是集合键的底层实现之一,当一个集合只包含整数元素,并且数量不多的时候,会作为集合键的底层实现.

     

typedef struct intset {

    /*
 虽然 intset 结构将 contents 属性声明为 int8_t 类型的数组， 但实际上 contents 数组的真正类型取决于 encoding 属性的值：
如果 encoding 属性的值为 INTSET_ENC_INT16 ， 那么 contents 就是一个 int16_t 类型的数组， 数组里的每个项都是一个 int16_t类型的整数值 
（最小值为 -32,768 ，最大值为 32,767 ）。
如果 encoding 属性的值为 INTSET_ENC_INT32 ， 那么 contents 就是一个 int32_t 类型的数组， 数组里的每个项都是一个 int32_t类型的整数值 
（最小值为 -2,147,483,648 ，最大值为 2,147,483,647 ）。
如果 encoding 属性的值为 INTSET_ENC_INT64 ， 那么 contents 就是一个 int64_t 类型的数组， 数组里的每个项都是一个 int64_t类型的整数值 
（最小值为 -9,223,372,036,854,775,808 ，最大值为9,223,372,036,854,775,807 ）。
 */
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

  如果新插入的元素比现有类型的encoding属性的值要长,就要进行升级.

  1.根据新元素的类型,重新计算并分配空间

  2.将所有元素都转换成新元素相同的类型,并重新放置.

  ps:整数集合不支持降级操作

 

六.压缩列表（ziplist）

  ziplist是列表键和哈希键的底层实现之一.如果数据量少并且都是小整数值或者长度较短的字符串,那么redis就用它作为列表键的底层实现.

    6.1 压缩列表的构成

    压缩列表是为了节约内存而开发的.一个压缩列表可以包含任意多个节点,每个节点保存一个字节数组或者一个整数值.

   

      

属性	类型	长度	用途
zlbytes	uint32_t	4字节	计算整个压缩列表占用的内存字节数
zltail	uint32_t	4字节	记录压缩列表表尾节点距离起始地址有多少字节:上图中p代表起始节点的指针,加上(0x3c=60)就是表尾节点的位置.
zllen	uint16_t	2字节	记录节点数量,如果数量大于2^16,就需要遍历整个列表才能知道数量了.
entry		不定
zlend	uint8_t	1字节	(0xFF),用于标记压缩列表的末端

  

     6.2压缩列表节点的结构

     

  

 

属性	类型	长度	用途
previoud_entry_length		1～5个字节	前一个节点的长度
encoding		1,2,5字节	记录节点content属性保存的类型以及长度
content			保存节点内容