精华内容
下载资源
问答
  • Redis底层数据结构

    2020-08-31 17:12:07
    Redis底层数据结构

    Redis:开源,C语言编写的key-value数据库

    字符串:Redis中的字符串并没有直接使用C语言传统的字符串表示,而是自己构建了一种名为简单动态字符串(simple dynamic string SDS)的抽象类型,并且将SDS作为Redis的默认字符串表示,C字符串和SDS的区别:

    C 字符串

    SDS

    获取字符串长度的复杂度为O(N)

    获取字符串长度的复杂度为O(1)

    API 是不安全的,可能会造成缓冲区溢出

    API 是安全的,不会造成缓冲区溢出

    修改字符串长度N次必然需要执行N次内存重分配

    修改字符串长度N次最多执行N次内存重分配

    只能保存文本数据

    可以保存二进制数据和文本文数据

     

    • 链表:提供了高效的节点重排能力,顺序性的节点访问方式,并且可以通过增删节点来灵活地调整链表的长度,其主要的特性:
    1. 双端:链表节点带有prev 和next 指针,获取某个节点的前置节点和后置节点的时间复杂度都是O(N)
    2. 无环:表头节点的 prev 指针和表尾节点的next 都指向NULL,对立案表的访问时以NULL为截止
    3. 表头和表尾:因为链表带有head指针和tail 指针,程序获取链表头结点和尾节点的时间复杂度为O(1)
    4. 长度计数器:链表中存有记录链表长度的属性 len
    5. 多态:链表节点使用 void* 指针来保存节点值,并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

     

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

    层:跳跃表节点的层信息,保存在level数组中,数组的size范围为1-32。一般层数越多,访问其他节点的速度越快。
    前进指针:指向表尾方向的下一个节点,如上图指向右方箭头所示,用于从表头向表尾访问节点。(遍历操作)
    跨度:用于记录两个节点的距离,如上图箭头上的的数字所示,指向NULL的指针的跨度为0,用于计算排位(排位:查找某个节点时,沿途的所有层的跨度之和)。
    后退指针:用于从表尾向表头方向访问节点,每次只能后退至前一个节点。
    分值:用于节点的排序,节点按照分值从小到大排序。
    成员对象:是一个指向字符串对象的指针,用于存储对象。(只用于保存字符串)。
    注意:各节点的成员对象必须是惟一的,但是分值可以相同。分值相同的节点按照成员对象在字典序中的大小排序(从小到大)。

    展开全文
  • redis底层数据结构

    2019-03-19 23:51:15
    Redis 是一个基于键值对(key-...redis底层数据结构主要有:简单动态字符串(SDS),链表,字典,跳跃表,整数集合,压缩列表。 1. 简单动态字符串 先看其底层源码 /* * 保存字符串对象的结构 */ struct sd...

    Redis 是一个基于键值对(key-value)的分布式存储系统。它常用的类型主要是 String、List、Hash、Set、ZSet 这5种。通过学习其底层数据类型,来探究其存储过程。
    redis底层数据结构主要有:简单动态字符串(SDS),链表,字典,跳跃表,整数集合,压缩列表。

    1. 简单动态字符串

    先看其底层源码

    /*  
     * 保存字符串对象的结构  
     */  
    struct sdshdr {  
          
        // 用于记录buf中已使用的空间长度
        int len;  
      
        // 用于记录buf中剩余可用空间的长度(初次分配空间时,一般为0,字符串进行修改后会多出空余空间)  
        int free;  
      
        // 数据空间,用于存储字符串  
        char buf[];  
    };
    

    补一张结构图
    在这里插入图片描述
    简单的对比一下java的String类型。

    //数据空间,用于存储字符串
    private final char value[];
    //字符串的hash值
    private int hash;
    

    简单看这两个实现方式的话,除了sds多出2个字段的,其他并未太大差距。但是我们通过几个方法来看其性能上面的区别

    1.1获取字符串长度

    java字符串底层采用的是字符数组存储。使用长度为N+1 的字符串数组来表示长度为N 的字符串,所以为了获取一个长度为C字符串的长度,必须遍历整个字符串。而通过查看sds的源码我们可以看到有专门的一个字段len 来进行存储。直接就可以获取字符串长度

    1.2 减少修改字符串时带来的内存重分配次数

    java的字符串在进行修改时是会进行地址的重新分配的。而sds在字符串进行修改时也会进行分配。但是分配的时候会预留空闲空间。举个例子:我们需要对SDS进行拓展,则需要进行空间的拓展,这时候redis 会将SDS的长度修改为13字节,并且将未使用空间同样修改为1字节,在我们下次修改sds时。如果只需要增加一个字节。那redis则不需要在进行内存分配,就可以修改字符串。通过这种预分配策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次

    2. 链表

    redis的链表结构和java的linkedlist双端列表结构是相似的。

    typedef struct listNode {
         // 前置节点
        struct listNode *prev;
        // 后置节点
        struct listNode *next;
        // 节点的值
        void *value;
     } listNode;
    
     typedef struct list {
         // 表头节点
        listNode *head;
        // 表尾节点
        listNode *tail;
        // 节点值复制函数
        void *(*dup)(void *ptr);
        // 节点值释放函数
        void (*free)(void *ptr);
         // 节点值对比函数
        int (*match)(void *ptr, void *key);
         // 链表所包含的节点数量
        unsigned long len;
     } list;
    

    在这里插入图片描述
    其特性简单可以总结为:
    1.双端:链表节点带有prev 和next 指针,获取某个节点的前置节点和后置节点的时间复杂度都是O(N)
    2.无环:表头节点的 prev 指针和表尾节点的next 都指向NULL,对立案表的访问 时以NULL为截止
    3.表头和表尾:因为链表带有head指针和tail 指针,程序获取链表头结点和尾节点的时间复杂度为O(1)
    4.长度计数器:链表中存有记录链表长度的属性 len
    5.多态:链表节点使用 void* 指针来保存节点值,并且可以通过list 结构的dup 、 free、 match三个属性为节点值设置类型特定函数。

    3. 字典

    其存储方式的本质还是hash散列表。我们查看其源码

    //字典类
    typedef struct dict {
        // 类型特定函数
        dictType *type;
        // 私有数据
        void *privedata;
        // 哈希表
        dictht  ht[2];
        // rehash 索引
        in trehashidx;
    
    }
    //dictht 类
    typedef struct dictht {
       //哈希表数组
       dictEntry **table;
       //哈希表大小
       unsigned long size;
    
       //哈希表大小掩码,用于计算索引值
       unsigned long sizemask;
       //该哈希表已有节点的数量
       unsigned long used;
    }
    //dictEntry 哈希表数组
    typeof struct dictEntry{
       //键
       void *key;
       //值
       union{
          void *val;
          uint64_tu64;
          int64_ts64;
       }
       struct dictEntry *next;
    
    }
    

    其结构图如下所示
    在这里插入图片描述
    可以看出其结构方式和HashMap是集齐相似的。不同的在于其含有2个哈希表的数组。为何它要分配2个数组呢。主要是用于Rehash。我们可以对比java的HashMap的Rehash操作。

    void resize(intnewCapacity)
    {
        Entry[] oldTable = table;
        intoldCapacity = oldTable.length;
        ......
        //创建一个新的Hash Table
        Entry[] newTable =new Entry[newCapacity];
        //将Old Hash Table上的数据迁移到New Hash Table上
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
    void transfer(Entry[] newTable)
    {
        Entry[] src = table;
        intnewCapacity = newTable.length;
        //下面这段代码的意思是:
        //  从OldTable里摘一个元素出来,然后放到NewTable中
        for(intj = 0; j < src.length; j++) {
            Entry<K,V> e = src[j];
            if(e != null) {
                src[j] =null;
                do{
                    Entry<K,V> next = e.next;
                    inti = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                }while (e != null);
            }
        }
    }
    

    redis分配方式也一样。它是将ht[0]中的数据转移到ht[1]中,在转移的过程中,需要对哈希表节点的数据重新进行哈希值计算。转移完成后将ht[0]释放,然后将ht[1]设置成ht[0],最后为ht[1]分配一个空白哈希表。为何要这样进行呢?,这是因为在实际开发过程中,reids的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 结束。
    采用渐进式rehash 的好处在于它采取分而治之的方式,避免了集中式rehash 带来的庞大计算量。

    4. 跳跃表

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

    typedef struct zskiplist {
         //表头节点和表尾节点
         structz skiplistNode *header,*tail;
         //表中节点数量
         unsigned long length;
         //表中层数最大的节点的层数
         int level;
    
    }zskiplist;
    typedef struct zskiplistNode{
       //层 level 数组可以包含多个元素,每个元素都包含一个指向其他节点的指针
         struct zskiplistLevel{
         // 前进指针:用于指向表尾方向的前进指针
            struct zskiplistNode *forward;
        //跨度:用于记录两个节点之间的距离
            unsigned int span;
        } level[];
      //后退指针:用于从表尾向表头方向访问节点
        struct zskiplistNode *backward;
      //分值和成员:跳跃表中的所有节点都按分值从小到大排序。成员对象指向一个字符串,这个字符串对象保存着一个SDS值
        double score;
      //成员对象
        robj *obj;
    }
    

    在这里插入图片描述

    5. 整数集合

    其实就是一个特殊的集合,里面存储的数据只能够是整数,并且数据量不能过大。

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

    在这里插入图片描述
    intset 在默认情况下会帮我们设定整数集合中的编码方式,但是当我们存入的整数不符合整数集合中的编码格式时,就需要使用到Redis 中的升级策略来解决。根据新元素的类型,扩展整数集合底层数组的空间大小,并为新元素分配空间,将底层数组现有的所有元素都转换成新的编码格式,重新分配空间。将新元素加入到底层数组中。这样做尽可能的节约了内存资源。但是需要注意整数集合只支持升级操作,不支持降级操作。

    6. 压缩列表

    压缩列表是列表键和哈希键的底层实现之一

    struct ziplist<T> {
        int32 zlbytes; // 整个压缩列表占用字节数
        int32 zltail_offset; // 最后一个元素距离压缩列表起始位置的偏移量,用于快速定位到最后一个节点
        int16 zllength; // 元素个数
        T[] entries; // 元素内容列表,挨个挨个紧凑存储
        int8 zlend; // 标志压缩列表的结束,值恒为 0xFF
    
    }
    struct entry {
        int<var> prevlen; // 前一个 entry 的字节长度
        int<var> encoding; // 元素类型编码
        optional byte[] content; // 元素内容
    }
    
    

    在这里插入图片描述
    在这里插入图片描述
    Redis对于每种数据结构、无论是列表、哈希表还是有序集合,在决定是否应用压缩列表作为当前数据结构类型的底层编码的时候都会依赖一个开关和一个阈值,开关用来决定我们是否要启用压缩列表编码,阈值总的来说通常指当前结构存储的key数量有没有达到一个数值(条件),或者是value值长度有没有达到一定的长度(条件)。任何策略都有其应用场景,不同场景应用不同策略。为什么当前结构存储的数据条目达到一定数值使用压缩列表就不好?压缩列表的新增、删除的操作平均时间复杂度为O(N),随着N的增大,时间必然会增加,他不像哈希表可以以O(1)的时间复杂度找到存取位置,然而在一定N内的时间复杂度我们可以容忍。然而压缩列表利用巧妙的编码技术除了存储内容尽可能的减少不必要的内存开销,将数据存储于连续的内存区域

    展开全文
  • Redis 底层数据结构

    千次阅读 2018-12-21 11:46:15
    Redis数据结构和底层数据结构的对应关系如下: 简单动态字符串 Redis没有直接使用C字符串来保存字符串值,而是自己实现了名为SDS的结构体。Redis中数据的值都是使用sds保存。 sds是一个结构体,包含三个成员。 ...

    Redis底层使用了6种数据结构来实现上层的各种数据结构,本文将对这6种数据结构分别进行简单的介绍。本文中的图片来自《Redis设计与实现第二版》。
    Redis数据结构和底层数据结构的对应关系如下:
    在这里插入图片描述

    简单动态字符串

    Redis没有直接使用C字符串来保存字符串值,而是自己实现了名为SDS的结构体。Redis中数据的值都是使用sds保存。
    sds是一个结构体,包含三个成员。
    在这里插入图片描述
    上图中的sds中保存了字符串"Redis"。
    SDS相对于单纯使用C字符串有以下优点:

    1. 记录了长度信息,strlen命令的开销变小
    2. 防止了缓冲区溢出,如果使用C的字符数组保存数据,那么当字符串的长度超过数组时会覆盖掉后面的数据,造成溢出。而SDS在保存字符串的时候会首先检查空间是否足够,不够的话会先补足缺少的空间。
    3. C字符串每次修改都要重新分配内存,开销较大,而SDS使用空间预分配和惰性空间释放两个策略避免频繁空间分配操作。
      空间预分配:
      如果SDS占用的空间小于1MB,那么每次扩展空间的时候会额外为SDS多分配一倍的空间,如果SDS占有的空间大于1MB,那么每次扩展之后额外分配1MB。
      如对上面保存了redis的sds赋值redis-server,那么空间不够,会重分配,重分配之后额外给一倍就是12+12=24。
      惰性释放:
      惰性释放指sds占用的空间缩小之后不会马上回收,而是标记起来,等下次要用的时候就直接取消标记,这样就省去了回收和重新分配的开销。
      可以看出上面的两个特性虽然对CPU友好,减少了执行的指令,但是对内存不太友好,不过选择这样实现是Redis的特性,牺牲了内存而保证执行速度。
    4. SDS二进制安全,C字符串使用空字符来标志字符串结束,那么就无法表示含有空字符的字符串,而SDS使用长度来标志结束,可以含有空字符。

    链表

    链表是一种访问较慢,修改很快的数据结构。Redis列表的底层实现是链表。链表的节点是一个如下的结构体,可以看出是一个双向链表。
    在这里插入图片描述
    除了节点之外,Redis专门针对链表做了一些封装:
    在这里插入图片描述
    可以看到,里面还专门放了三个指向函数的指针,用来提供复制,释放,对比操作。

    字典

    字典类似于Java中的Map,Python中的dict,是一种保存键值对的数据结构。Redis中的Hash由字典实现。其实Redis自身可以看成一个大的dict。
    dict的实现如下:
    在这里插入图片描述
    table属性是一个数组,里面包含多个dictEntry,每个dictEntry保存了一个键值对。下面是一个空的dict。
    在这里插入图片描述
    dictEntry是一个如下的结构体:
    在这里插入图片描述
    dictEntry里面包含一个dictEntry*的next,可以看出,这里是使用的拉链法来解决键冲突的,即hash值相同的键会保存在一个链表中。最后在dictht之上,Redis还做了一层封装,真正使用的dict是这样的:
    在这里插入图片描述
    其中dictType的作用是针对不同需要的dict而封装了不同的dict操作函数:
    在这里插入图片描述
    而privatedata保存了需要传递给类型特定函数的参数。
    ht属性中保存了两个dictht,这是为了rehash,也就是在容量不足时将一个表的数据迁移到另一个表中。rehashidx是是否在进行rehash的标志位,如果不是那么值为-1,一个没有进行rehash的dict 如图所示:
    在这里插入图片描述
    Redis使用MumurHash2来计算键的hash值,在键冲突时,为了提高速度,总是将冲突的键插入在链表的头部。

    dict 的rehash

    dict的rehash和java中的hashMap rehash的过程几乎相同,唯一的不同是dict支持缩小,以扩大的过程来看,主要分为三个步骤:

    1. 初始化新表,将ht[1]的大小设置为ht[0]的两倍,注意这里ht的大小也是2的幂次,所以每次扩大两倍,而且bucket index的算法也和java HashMap一样,是hash&(length-1),将对应的属性都更新好之后就为table属性分配新的内存空间,使ht[1]可以开始存放数据。
    2. 初始化ht[1]之后就开始transfer数据了,由于都是2的幂次,那么重新计算index也将变得很简单,同时rehash之后的数据也会分布得很均匀,具体计算的方式就是index&length=length的dictEntry新的index=旧index+length,剩下的不变,length是ht[0]的长度。
    3. 完成了transfer之后需要将ht[0]的空间都释放掉,然后将ht[0]指向ht[1],为ht[1]重新创建一个上图所示的空的dictht。
      是否进行rehash由loadfactor决定,
      loadfactor=ht[0].used/ht[0].sizeload factor=ht[0].used/ht[0].size
      Redis规定,在没有进行BGSAVE或BGREWIRTE的时候load factor大于1 就开始rehash,如果在进行BGSAVE或BGREWRITE,那么load factor大于5就开始rehash,这是因为rehash 需要的内存空间非常大,在BGSAVE或者BGREWRITE正在进行的时候内存资源比较紧张,要尽量避免rehash。
      在rehash进行的过程中,程序还是可以正常执行命令的,但是新增的操作会统一添加到ht[1]中,保证ht[0]的只增不减,另外为了减少rehash线程的压力,每次对dict执行查询,更新,删除的时候会顺便将这个键值对转移到ht[1],转移的时候使用rehashidx进行计数,每次操作一个就增加1,当计数等于键值的时候就全部转移完毕。

    跳跃表

    跳跃表非常类似于平衡二叉树,是一种为了快速查找而设计的数据结构。跳跃表的查找时间复杂度是O(log(n)),最坏情况下是O(n) 。
    Redis使用跳跃表来实现ZSET。
    Redis的跳跃表数据结构成员如下:

    1. header,表头节点
    2. tail 表尾节点
    3. level,当前表中层级最高的节点的层数
    4. length,跳跃表的长度,即含有的节点的个数
      一个跳跃表如图所示:
      在这里插入图片描述
      跳跃表节点定义如下:
      在这里插入图片描述
      这是一个嵌套定义的结构体,一共有四个属性:
      level:level数组保存了到其它node的指针,每个节点可以指向很多个节点,查询的时候就通过顺序从这些指针开始递归地查找来查找数据。
      backward:每个节点的backword指向逻辑顺序上靠后一位的一个节点,不管level的话,仅仅使用backward,所有的节点练成了一个链表。
      score:所有的节点按照score升序排列,以此确定逻辑上的前后顺序,分值可以相同,当分值相同的时候按照obj的顺序排列,这里默认obj互相之间可以比较。
      obj: 指向数据的指针

    这里介绍一下跳跃表的查询时间复杂度分析:
    首先,在每个节点插入的时候会随机产生一个层数,这个层数的计算方式如下

    level = 1
    // random()返回服从均匀分布的[0,1)上的随机数
    while(random()<p && level<MaxLevel){
    	level++;
    }
    return level;
    

    在redis中maxLevel=32
    要分析查找的性能,先看看查找的过程:
    查找的过程从头节点的最上面开始,可以看到,头节点是满的32层,没有数据。查找要走的步数就是查找的时间复杂度,分析步数可以使用从结果倒推到起点的方法。
    首先假设跳跃表最高有h层,结果在第j个数据的第i层的时候被找到,那第j列的第i层是起点。设C(k)为向上跳k层的期望步数,C(0)=0。
    假设第j列只有i层,因为现在已经在第i层了,所以这个概率是(1-p),那么说明回到起点需要C(h-i)+1步
    假设第j列存在第i+1层,这个概率是p,那么回到起点要C(h-i-1)+1
    推出C(h-i)=(1-p)*(C(h-i)+1)+p*(C(h-i-1)+1)
    代入k=h-i以及C(0)=0求得C(K)=k/p
    那么查找一个数据的过程也应当是这样的,如果这个数据最终会在第几层被找到,那么需要走的步数就是层数/p,也就是时间复杂度的关键在于层数的阶。现在假设一共有n个数据,根据之前的层数算法,不同高度的层可以构成一个等比数列,显然最高层只有一个数据,即
    nph1=1n*p^{h-1}=1,可以解得h=log(p)1/n=log(1/p)n=O(log(n))h=log(p)1/n=log(1/p)n=O(log(n))

    整数集合

    整数集合石集合的实现方式之一,当一个集合里面的内容全部是整数,且集合的大小不超过512的时候,使用整数集合来实现集合。
    整数集合由以下结构体实现:
    在这里插入图片描述
    contents里面保存了整数集合内的数据,且按照大小升序排列。
    encoding指示了contents里面保存的证书的类型,如果encoding是INTSET_ENC_INT16,那么contents里面的元素就都是16位的整数,假设存储了5个元素,那么占用的空间大小就是16*5=80

    整数集合升级

    之所以使用最小的int8_t来作为数组的最基本元素,是为了节约空间,但是当放入的整数太大int8_t放不下时集合就要通过调整编码的格式来升级。
    例如当前的整数集合保存了1,2,3,4这几个整数,当前编码是16位整数,现在要将65535放入,65535需要用int32_t来表示,所以需要升级,升级分为三个步骤:

    1. 重新分配数组空间,由于类型变化了,那么需要的空间也要相应地调整,如之前是416=64,变化后应该是532=160
    2. 将已有的元素按新类型重新编码,然后调整他们的位置。需要注意的是,如果从前往后调整,那么有可能会覆盖到后面的数据,所以Redis是从后往前调整,调整位置的同时修改编码。
    3. 将新的元素插入到数组中去。在第三步插入的时候会根据每个元素原来的位置计算得出在新的数组中的位置,注意引发升级的时候新插入的数据一定是大于或者小于所有元素的,是正的就大是负的就小。
      需要注意的是整数集合只有升级,没有降级。

    压缩列表

    压缩列表是Redis的重要数据结构,Redis list,hash,zset底层都使用了压缩列表作为实现方式。
    压缩列表的格式如下:
    在这里插入图片描述
    可以看到,压缩列表的格式很类似一些文件的编码方式,在文件开头有一些元数据,记录数据区域的位置和数据的条数。这种紧凑的格式避免了内存对齐这样的为了方便访问而引发的内存开销,压缩列表是在数据结构中元素较少时采取的数据结构,使用压缩列表节约了内存开支,但是降低了访问的速度,不过对于规模较小的对象,这样的损失可以忽略不记。

    压缩列表节点构成

    在这里插入图片描述
    为了能表示各种数据,压缩列表为每个entry都设置了一个encoding,指定entry可以保存如下几种数据:
    1 长度小于63的字节数组
    2 长度小于等于16383(21612^{16}-1)的字节数组
    3 长度小于等于(23212^{32}-1)的字节数组
    4 4位长,介于0-12之间的整数
    5 1字节长的有符号整数
    6 3 字节长的有符号整数
    7 int16_t类型的整数
    8 int32_t类型的整数
    9 int64_t类型的整数
    其中后面几种都是整数
    previous entry length
    这个字段保存了前一个entry的长度,这个字段的长短会随着它需要保存的数字的大小发生变化,当前一个entry的长度小于254的时候,这个字段使用1字节来保存,当前一个entry的长度大于254,就使用5个字节来存这个数据。记录这个字段方便了从表尾向表头遍历整个压缩列表,每次往前访问一个元素只需要将指针减去这个值就可以了,而当前entry的长度可以根据编码的内容计算得知,所以往后遍历不需要额外保存本entry的长度。

    连锁更新

    为了省内存空间,previous entry length的大小会随着前一个entry的大小变化而变化,这种策略会导致当有连续很多个entry的长度都恰好大于等于250,小于254,并且这连续的多个entry的第一个entry的previous entry length恰好是1,当这个entry的前一个entry变大之后会到这这个entry的previous entry length变大,然后这个entry也会变大,然后就会导致后继的若干个entry的连锁变大以及更新,连锁更新发生的概率非常小,但是最坏情况下,连锁更新的时间复杂度为O(n2)O(n^2)

    展开全文
  • redis 底层数据结构

    2021-02-23 22:44:09
    Redis作为Key-Value存储系统,数据结构如下: Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间。 RedisDB结构 Redis中存在“数据库”的概念,该结构由redis.h中的redisDb定义。 当...

    一、底层结构

    Redis作为Key-Value存储系统,数据结构如下:
    在这里插入图片描述
    Redis没有表的概念,Redis实例所对应的db以编号区分,db本身就是key的命名空间。

    RedisDB结构

    Redis中存在“数据库”的概念,该结构由redis.h中的redisDb定义。
    当redis 服务器初始化时,会预先分配 16 个数据库
    所有数据库保存到结构 redisServer 的一个成员 redisServer.db 数组中
    redisClient中存在一个名叫db的指针指向当前使用的数据库
    RedisDB结构体源码:

    typedef struct redisDb {
    	int id; //id是数据库序号,为0-15(默认Redis有16个数据库)
    	long avg_ttl; //存储的数据库对象的平均ttl(time to live),用于统计
    	dict *dict; //存储数据库所有的key-value
    	dict *expires; //存储key的过期时间
    	dict *blocking_keys;//blpop 存储阻塞key和客户端对象
    	dict *ready_keys;//阻塞后push 响应阻塞客户端 存储阻塞后push的key和客户端对象
    	dict *watched_keys;//存储watch监控的的key和客户端对象
    } redisDb;
    

    id
    id是数据库序号,为0-15(默认Redis有16个数据库)
    dict
    存储数据库所有的key-value,后面要详细讲解
    expires
    存储key的过期时间,后面要详细讲解

    RedisObject结构

    Value是一个对象,包含字符串对象,列表对象,哈希对象,集合对象和有序集合对象

    结构信息概览

    typedef struct redisObject {
    	unsigned type:4;//类型 五种对象类型
    	unsigned encoding:4;//编码
    	void *ptr;//指向底层实现数据结构的指针
    	//...
    	int refcount;//引用计数
    	//...
    	unsigned lru:LRU_BITS; //LRU_BITS为24bit 记录最后一次被命令程序访问的时间
    	//...
    }robj;
    

    4位type
    type 字段表示对象的类型,占 4 位;
    REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。
    当我们执行 type 命令时,便是通过读取 RedisObject 的 type 字段获得对象的类型

    4位encoding
    encoding 表示对象的内部编码,占 4 位
    每个对象有不同的实现编码
    Redis 可以根据不同的使用场景来为对象设置不同的编码,大大提高了 Redis 的灵活性和效率。
    通过 object encoding 命令,可以查看对象采用的编码方式

    24位LRU
    lru 记录的是对象最后一次被命令程序访问的时间,( 4.0 版本占 24 位,2.6 版本占 22 位)。
    高16位存储一个分钟数级别的时间戳,低8位存储访问计数(lfu : 最近访问次数)
    lru----> 高16位: 最后被访问的时间
    lfu----->低8位:最近访问次数

    refcount

    refcount 记录的是该对象被引用的次数,类型为整型。
    refcount 的作用,主要在于对象的引用计数和内存回收。
    当对象的refcount>1时,称为共享对象
    Redis 为了节省内存,当有一些对象重复出现时,新的程序不会创建新的对象,而是仍然使用原来的对象。

    ptr
    ptr 指针指向具体的数据,比如:set hello world,ptr 指向包含字符串 world 的 SDS

    二、7种type

    1. 字符串对象

    Redis 使用了 SDS(Simple Dynamic String)。用于存储字符串和整型数据。
    在这里插入图片描述

    struct sdshdr{
    	//记录buf数组中已使用字节的数量
    	int len;
    	//记录 buf 数组中未使用字节的数量
    	int free;
    	//字符数组,用于保存字符串
    	char buf[];
    }
    

    SDS的优势:

    1. SDS 在 C 字符串的基础上加入了 free 和 len 字段,获取字符串长度:SDS 是 O(1),C 字符串是O(n)。buf数组的长度=free+len+1
    2. SDS 由于记录了长度,在可能造成缓冲区溢出时会自动重新分配内存,杜绝了缓冲区溢出。
    3. 可以存取二进制数据,以字符串长度len来作为结束标识
      C: \0 空字符串 二进制数据包括空字符串,所以没有办法存取二进制数据
      SDS : 非二进制 \0
      二进制: 字符串长度 可以存二进制数据

    使用场景:

    SDS的主要应用在:存储字符串和整型数据、存储key、AOF缓冲区和用户输入缓冲。

    2. 跳跃表(重点)

    跳跃表是有序集合(sorted-set)的底层实现,效率高,实现简单。
    跳跃表的基本思想:
    将有序链表中的部分节点分层,每一层都是一个有序链表。

    查找
    在查找时优先从最高层开始向后查找,当到达某个节点时,如果next节点值大于要查找的值或next指针指向null,则从当前节点下降一层继续向后查找。
    在这里插入图片描述
    插入
    上面例子中,9个结点,一共4层,是理想的跳跃表。
    通过抛硬币(概率1/2)的方式来决定新插入结点跨越的层数:

    • 正面:插入上层
    • 背面:不插入

    删除
    找到指定元素并删除每层的该元素即可

    跳跃表特点
    每层都是一个有序链表,查找次数近似于层数(1/2),底层包含所有元素,空间复杂度 O(n) 扩充了一倍

    Redis跳跃表的实现

    //跳跃表节点
    typedef struct zskiplistNode {
    	sds ele; /* 存储字符串类型数据 redis3.0版本中使用robj类型表示,
    	但是在redis4.0.1中直接使用sds类型表示 */
    	double score;//存储排序的分值
    	struct zskiplistNode *backward;//后退指针,指向当前节点最底层的前一个节点
    	/*
    	层,柔性数组,随机生成1-64的值
    	*/
    	struct zskiplistLevel {
    	struct zskiplistNode *forward; //指向本层下一个节点
    	unsigned int span;//本层下个节点到本节点的元素个数
    	} level[];
    	} zskiplistNode;
    	//链表
    	typedef struct zskiplist{
    	//表头节点和表尾节点
    	structz skiplistNode *header, *tail;
    	//表中节点的数量
    	unsigned long length;
    	//表中层数最大的节点的层数
    	int level;
    }zskiplist;
    

    完整的跳跃表结构体:
    在这里插入图片描述
    跳跃表的优势:
    1、可以快速查找到需要的节点
    2、可以在O(1)的时间复杂度下,快速获得跳跃表的头节点、尾结点、长度和高度。

    3. 字典(重点+难点)

    字典dict又称散列表(hash),是用来存储键值对的一种数据结构。
    Redis整个数据库是用字典来存储的。(K-V结构)
    对Redis进行CURD操作其实就是对字典中的数据进行CURD操作。

    字典的结构

    使用数组作为存储容器,Hash函数来计算数据存储的位置,如果发生Hash冲突,采用单链表在相同的下标位置处存储原始key和value。

    数组
    数组:是字典用来存储数据的容器,采用头指针+偏移量的方式能够以O(1)的时间复杂度定位到数据所在的内存地址。Redis,海量存储,快,就是因为使用数组。

    Hash函数
    Hash(散列),作用是把任意长度的输入通过散列算法转换成固定类型、固定长度的散列值。
    hash函数可以把Redis里的key:包括字符串、整数、浮点数统一转换成整数。
    key=100.1 String “100.1” 5位长度的字符串
    Redis-cli :times 33
    Redis-Server : siphash
    数组下标=hash(key)%数组容量(hash值%数组容量得到的余数

    Hash冲突
    不同的key经过计算后出现数组下标一致,称为Hash冲突。
    采用单链表在相同的下标位置处存储原始key和value
    当根据key找Value时,找到数组下标,遍历单链表可以找出key相同的value
    在这里插入图片描述

    Redis字典的实现

    Redis字典实现包括:字典(dict)、Hash表(dictht)、Hash表节点(dictEntry)。
    在这里插入图片描述
    Hash表

    typedef struct dictht {
     dictEntry **table; // 哈希表数组
     unsigned long size; // 哈希表数组的大小 
     unsigned long sizemask; // 用于映射位置的掩码,值永远等于(size-1) 
     unsigned long used;// 哈希表已有节点的数量,包含next单链表数据 
     } dictht;
    

    1、hash表的数组初始容量为4,随着k-v存储量的增加需要对hash表数组进行扩容,新扩容量为当前量的一倍,即4,8,16,32
    2、索引值=Hash值&掩码值(Hash值与Hash表容量取余)

    Hash表节点

    typedef struct dictEntry { 
    	void *key; // 键
    	union { // 值v的类型可以是以下4种类型
    	  void *val; 
    	  uint64_t u64; 
    	  int64_t s64; 
    	  double d;
    	 } v;
      struct dictEntry *next; // 指向下一个哈希表节点,形成单向链表 解决hash冲突 
    } dictEntry;
    

    key字段存储的是键值对中的键
    v字段是个联合体,存储的是键值对中的值。
    next指向下一个哈希表节点,用于解决hash冲突
    在这里插入图片描述
    dict字典
    在这里插入图片描述
    type字段,指向dictType结构体,里边包括了对该字典操作的函数指针
    在这里插入图片描述
    Redis字典除了主数据库的K-V数据存储以外,还可以用于:散列表对象、哨兵模式中的主从节点管理等在不同的应用中,字典的形态都可能不同,dictType是为了实现各种形态的字典而抽象出来的操作函数(多态)。

    完整的Redis字典数据结构:
    在这里插入图片描述

    字典扩容

    字典达到存储上限,需要rehash(扩容)
    扩容流程:
    在这里插入图片描述
    说明:

    1. 初次申请默认容量为4个dictEntry,非初次申请为当前hash表容量的一倍。
    2. rehashidx=0表示要进行rehash操作。
    3. 新增加的数据在新的hash表h[1]
    4. 修改、删除、查询在老hash表h[0]、新hash表h[1]中(rehash中)
    5. 将老的hash表h[0]的数据重新计算索引值后全部迁移到新的hash表h[1]中,这个过程称为rehash。

    渐进式rehash
    当数据量巨大时rehash的过程是非常缓慢的,所以需要进行优化。
    服务器忙,则只对一个节点进行rehash
    服务器闲,可批量rehash(100节点)
    应用场景:
    1、主数据库的K-V数据存储
    2、散列表对象(hash) 3、哨兵模式中的主从节点管理

    4. 压缩列表

    压缩列表(ziplist)是由一系列特殊编码的连续内存块组成的顺序型数据结构

    压缩列表的数据结构如下:
    在这里插入图片描述
    zlbytes:压缩列表的字节长度
    zltail:压缩列表尾元素相对于压缩列表起始地址的偏移量
    zllen:压缩列表的元素个数
    entry1…entryX : 压缩列表的各个节点
    zlend:压缩列表的结尾,占一个字节,恒为0xFF(255)

    entryX元素的编码结构:
    在这里插入图片描述
    previous_entry_length:前一个元素的字节长度
    encoding:表示当前元素的编码
    content:数据内容

    ziplist结构体如下:
    在这里插入图片描述
    应用场景:
    sorted-set和hash元素个数少且是小整数或短字符串(直接使用)
    list用快速链表(quicklist)数据结构存储,而快速链表是双向列表与压缩列表的组合。(间接使用)

    5. 整数集合

    整数集合(intset)是一个有序的(整数升序)、存储整数的连续存储结构。

    intset的结构图如下:
    在这里插入图片描述

    6. 快速列表(重要)

    快速列表(quicklist)是Redis底层重要的数据结构。是列表的底层实现。(在Redis3.2之前,Redis采用双向链表(adlist)和压缩列表(ziplist)实现。)在Redis3.2以后结合adlist和ziplist的优势Redis设计出了quicklist。

    双向列表(adlist)
    在这里插入图片描述
    双向链表优势:

    1. 双向:链表具有前置节点和后置节点的引用,获取这两个节点时间复杂度都为O(1)。
    2. 普通链表(单链表):节点类保留下一节点的引用。链表类只保留头节点的引用,只能从头节点插入删除
    3. 无环:表头节点的 prev 指针和表尾节点的 next 指针都指向 NULL,对链表的访问都是以 NULL 结束。
      环状:头的前一个节点指向尾节点
    4. 带链表长度计数器:通过 len 属性获取链表长度的时间复杂度为 O(1)。 5. 多态:链表节点使用 void* 指针来保存节点值,可以保存各种不同类型的值。

    快速列表
    quicklist是一个双向链表,链表中的每个节点时一个ziplist结构。quicklist中的每个节点ziplist都能够存储多个数据元素。
    在这里插入图片描述
    quicklist的结构定义如下:
    在这里插入图片描述
    quicklistNode的结构定义如下:
    在这里插入图片描述
    数据压缩
    quicklist每个节点的实际数据存储结构为ziplist,这种结构的优势在于节省存储空间。为了进一步降低ziplist的存储空间,还可以对ziplist进行压缩。Redis采用的压缩算法是LZF。其基本思想是:数据与前面重复的记录重复位置及长度,不重复的记录原始数据。

    压缩过后的数据可以分成多个片段,每个片段有两个部分:解释字段和数据字段。quicklistLZF的结构体如下:
    在这里插入图片描述
    应用场景
    列表(List)的底层实现、发布与订阅、慢查询、监视器等功能。

    7. 流对象

    stream主要由:消息、生产者、消费者和消费组构成。
    在这里插入图片描述
    Redis Stream的底层主要使用了listpack(紧凑列表)和Rax树(基数树)。

    三、10种encoding

    encoding 表示对象的内部编码,占 4 位。Redis通过 encoding 属性为对象设置不同的编码,对于少的和小的数据,Redis采用小的和压缩的存储方式,体现Redis的灵活性,大大提高了 Redis 的存储量和执行效率。

    • String
      int、raw、embstr
    • int
      REDIS_ENCODING_INT(int类型的整数)
    • embstr
      REDIS_ENCODING_EMBSTR(编码的简单动态字符串)
      小字符串 长度小于44个字节
    • raw
      REDIS_ENCODING_RAW (简单动态字符串)
      大字符串 长度大于44个字节
    • list
      列表的编码是quicklist
    • hash
      散列的编码是字典和压缩列表
    • dict
      REDIS_ENCODING_HT(字典)
      当散列表元素的个数比较多或元素不是小整数或短字符串时。
    • ziplist
      REDIS_ENCODING_ZIPLIST(压缩列表)
      当散列表元素的个数比较少,且元素都是小整数或短字符串时
    • set
      集合的编码是整形集合和字典
    • intset
      REDIS_ENCODING_INTSET(整数集合)
      当Redis集合类型的元素都是整数并且都处在64位有符号整数范围内(<18446744073709551616)
    • dict
      REDIS_ENCODING_HT(字典)
    • zset
      有序集合的编码是压缩列表和跳跃表+字典
    • ziplist
      REDIS_ENCODING_ZIPLIST(压缩列表)
    • skiplist + dict
      REDIS_ENCODING_SKIPLIST(跳跃表+字典)
      当元素的个数比较多或元素不是小整数或短字符串时。
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,452
精华内容 1,380
关键字:

redis底层数据结构

redis 订阅
数据结构 订阅