侧边栏壁纸
博主头像
一定会去到彩虹海的麦当

说什么呢?约定好的事就一定要做到啊!

  • 累计撰写 63 篇文章
  • 累计创建 16 个标签
  • 累计收到 3 条评论

目 录CONTENT

文章目录

[redis]——内部数据类型

一定会去到彩虹海的麦当
2022-04-22 / 0 评论 / 1 点赞 / 35 阅读 / 5,527 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

概述

数据类型

提供给用户的数据类型 有String,List,Hash,Set,ZSet

Redis内部数据结构有:SDS(简单动态字符串),链表,字典,跳跃表,整数集合,压缩列表

Redis数据类型与内部数据结构的关系

Redis没有直接使用基础数据结构来实现键值对数据库,而是基于这些数据结构创建了一个对象系统,这些对象是供用户直接使用的。Redis数据库中的每个键值对的键和值都是一个对象,五种类型的对象至少都支持两种或者两种以上的基础数据结构,不同的数据结构可以在不同的使用场景上优化对象的使用效率。

img

String是唯一一个会被其它四种对象嵌套使用的对象。List、Hash、Set、ZSet之所以会虚线指向SDS也是嵌套使用String的原因。

简单动态字符串

定义

Redis没有直接使用C语言字符串,而是自己创建了一个名为简单动态字符串(Simple Dynamic String)的抽象类型来表示字符串。

image-20220424124704964

SDS比C字符串更适合用于Redis的原因

  1. 常数复杂度获取字符串长度

    只要访问SDS的len属性就可以立即知道SDS的长度

  2. 杜绝缓冲区溢出

    当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS的空间大小,也不会出现缓冲区溢出问题。

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

    SDS通过未使用空间解除了字符申长度和底层数组长度之间的关联:在SDS中,buf数组的长度不一定就是字符数量加一,数组里面可以包含未使用的字节,而这些字节的数量就由SDS的free属性记录

    通过未使用空间, SDS实现了空间预分配和惰性空间释放两种优化策略

  4. 二进制安全

C字符串的字符必须符合某种编码,并且中间不能有空字符,否则读取时会被误以为是字符串结尾。种种局限使得C字符串只能存文本,不能存图片,音频,视频,压缩文件等二进制数据。 为确保Redis对不同使用场景的支持,SDS API都是二进制安全的,也就是所有SDS API都会以二进制的方式存取buf中的数据,数据的写入和读出都是一个样的。由于SDS读取时并不是依靠空字符来判断结束的,而是len属性,所以是二进制安全的。

  1. 兼容部分C字符串函数

    image-20220424125955066

内存分配策略

空间预分配

空间预分配用于优化SDS字符串增长操作。在扩展SDS空间前,SDS API会先检查未使用空间够不够,如果不够,则进行空间预分配。此时,程序不仅会为SDS分配修改所必须要的空间,还为其分配额外未使用的空间。

  • 修改后的SDS<1MB,程序分配和len属性同样大小的未使用空间,此时SDS的len与free大小相等。
  • 修改后SDS>=1MB。程序会分配1MB的未使用空间。

通过空间的预分配,将连续增长N次字符串需要的内存分配次数从一定需要N次变为最多N次。因而可以减少连续执行字符串增长操作所需的内存重分配的次数。

惰性空间释放

惰性空间的释放用于优化SDS字符串缩短操作。当SDS API需要缩短保存的字符串时,程序并不立即回收这部分内存,而是使用free属性将字节的数量记录,等待使用。与此同时,SDS提供了相关API,在有需要时,真正释放未使用空间,不需要担心惰性空间造成的内存浪费

链表

定义

typedef struct listNode{
    //前置节点
    struct listNode *prev;
    //后置节点
    struct listNode *next;
    //节点的值
    void *value;
}listNode;

节点由前驱后继组成,多个节点组成的链表为双端链表。

image-20220424130518054

使用adlist.h/list来持有,操作链表:

image-20220424130556005

Redis链表特性可以总结如下:

双端:链表节点带有prev和next指针,获取前置和后置节点的复杂度都是O(1)。
无环:表头节点的prev指针和表尾节点的next指针都指向NULL,对链表的访问以NULL为终点。 带表头指针和表尾指针 带链表长度计数器 。
头尾指针:将程序获取头尾节点的复杂度降为O(1)。
长度计数器:将程序获取表长的复杂度降为O(1)。
多态:链表节点使用void*指针来保存节点值,并且可以通过list结构的dup、free、match为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。

字典

Redis的字典使用哈希表作为底层实现,一个哈希表里面可以有多个哈希表节点,每个哈希表节点保存了字典中的一个键值对

哈希表

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

image-20220424130652493

哈希表节点

哈希表节点使用dictEntry实现,每个dictEntry都存储着一个键值对:

typedef struct dictEntry{
    //键
    void *key;
    //值
    union{
        void *val;
        uint64_t u64;
        int64_t s64;
    } v;
    //指向下个哈希表节点,形成链表
    struct dictEntry *next;
} dictEntry;

image-20220424130721344

键值对的值可以是一个指针,或一个uint64_t整数,或一个int64_t整数。next是指向另一个哈希节点的指针,可将多个哈希值相同的键值对连接在一起,以此来解决冲突。

字典

Redis中的字典由dict.h/dict结构表示 ,由这个数据结构将哈希表组织在一起

typedef struct dict{
    //类型特定函数
    dictType *type;
    //私有数据
    void *privdata;
    //哈希表
    dictht ht[2];
    //rehash索引
    //当rehash不在进行时,值为-1
    int rehashidx;
} dict;
  • type属性是一个指向dictType的结构指针,每个dictType结构保存了一簇用于操作特定类型键值对的函数,Redis为用途不同的字典设置不同类型特定函数。
  • privdata属性保存了需要传给那些类型特定函数的可选参数。
  • ht属性是包含两个项的数组,每项都是一个哈希表,ht[0]平时使用,而ht[1]仅在rehash时使用。
  • rehashidx记录了rehash的进度,初始为-1。

普通状态下,没有进行rehash的字典:

image-20220424130920284

如何解决Hash冲突? 与Java的HashMap有哪些异同点?

Redis采用链地址法来解决冲突(解决冲突的方法基本上有链地址法,开放定址法,再哈希法等),与Java的HashMap的异同点:绿色为相同点,橙色为不同点。

为什么Redis字典没有使用红黑树来提高查询效率?

  1. Redis负载因子是使用了 已经存在的节点数量/数组长度,基本上链表节点个数不会超过数组的长度。Java HashMap负载因子是使用的数组中已有节点数量/数组长度。

  2. Redis的链表结构已经做了优化,红黑树插入新节点时要进行颜色切换,树扭转,更消耗空间。

rehash

当哈希表保存的键值对数量太多或者太少时,程序需要对哈希表的大小进行响应的扩容或缩容

(1)为字典ht[1]哈希表分配空间,大小取决于要执行的操作与ht[0]当前键值对的数量

  • 如果执行的是扩展操作,那么ht[1]的大小为第一个大于等于ht[0].used * 2 的2^n (2的n次方幂)
  • 如果执行的是收缩操作,那么ht[1]的大小为第一个大于等于ht[0].used的2^n

(2)将保存在ht[0]中的所有键值对存放到ht[1]指定的位置

(3)当ht[0]的所有键值对都迁移完毕后,释放ht[0],并指向ht[1],并在ht[1]上创建一个空的哈希表,为下次rehash准备。

image-20220424131207748

渐进式rehash

ehash时会将ht[0]中所有的键值对rehash到ht[1],如果键值对很多并且一次性操作的话,容易导致服务器在一段时间内停止服务。为避免这种情况,Redis采用渐进式rehash,将ht[0]中的键值对分多次,慢慢的rehash到ht[1]之中。

因为在进行渐进式rehash的过程中,字典会同时使用ht[0] , ht[1]两个哈希表,所以在渐进式rehash期间,字典的删除(delete)、查找(find)、更新(update)等操作会在两个哈希表上进行。例如,要在字典里面查找一个键的话,程序会先在ht[0]里面进行查找,如果没找到的话,就会继续到ht[1]里面进行查找,诸如此类。

跳跃表

定义

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

Redis的跳跃表由redis.h/zskiplistNoderedis.h/zskiplist两个数据结构定义。

typedef struct zskiplist{
    //表头节点和表尾节点
    structz zskiplistNode *header,* tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点的层数
    int level;
} zskiplist;

跳跃表由zskiplist组织,通过多个跳跃表节点zskiplistNode组成一个跳跃表。值得注意的是,记录level时,表头结点的层高不会记录在内。

image-20220424131406786

跳跃表节点

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

    跳跃表的每个节点都会包含多个层,每次创建一个新跳跃表时,都会根据幂次定律,随机生成一个1~32之间的数作为层的大小。每个层都会包含前进指针和跨度。

  2. 前进指针(forword)

    用于访问下一个节点。跨度表示两个节点之间的距离,指向NULL的所有前进指针的跨度为0。跨度用于计算排位,访问某一结点的经过的跨度之和就是当前节点的排位

  3. 后退指针–backward

    用于从表尾向表头方向访问节点,前进指针可以一次跳过多个节点,后退指针只能后退至前一个节点,因为每个节点只有一个后退指针。

  4. 分值–score

    分值是一个double类型的浮点数,跳跃表中节点都按照分值排序。

  5. 成员对象–obj

    是一个指针,指向字符串SDS对象。一个跳跃表中,对象必须是唯一的,但分值可以相同。相同时按对象字典序来排序。

    字典序的大小是指成员对象在字典中的排序

整数集合

定义

当一个集合只包含整数元素,并且元素不多时,Redis就会使用整数集合作为集合键的底层实现。

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

contents数组是整数集合的底层实现:整数集合的每个元素都是contents数据的一个数组项(item) ,各个项在数组中按值得大小从小到大有序地排列,并且数组中不包含任何重复项。

length属性记录了整数集合包含的元素数量,contents是整数集合的底层实现。contents存储元素的真实类型取决于encoding,比如encoding==INT_ENC_INT16时,contents数组中每个向都是int16_t类型的整数。可以为int16_t,int32_tint64_t

image-20220424131941382

升级

当我们要将一个新元素添加至集合时,并且新元素的类型比现有集合类型都长时,整数集合就要升级。

步骤:

  1. 根据新元素类型,扩展数组空间,为新元素分配空间。
  2. 将底层数组现有所有元素都转为新元素相同类型,并将类型转换后的元素放到正确位置。
  3. 将新元素添加到底层数组。

由于每次向整数集合添加新元素都可能会引起升级,而每次升级都需要对底层数组中已有元素进行类型转换,所以添加的时间复杂度为O(N)

升级的好处

有两个好处,可以提升整数集合的灵活性,也能尽可能地节约内存
C语言是静态类型语言,一般数组中的元素类型都相同,使用升级可以不用担心类型兼容问题,提升灵活性。元素统一以最大类型存储,而不是都用int64_t,可节约内存。

降级

整数集合不支持降低,一旦升级就不能降级。

压缩列表

定义

为节约内存而开发的,由一系列特殊编码连续内存块组成的顺序型数据结构。

image-20220424132113019

image-20220424132120306

压缩列表节点

image-20220424132153858

previous_entry_length

单位是字节,记录压缩列表前一个节点的长度。该属性长度为1字节或5字节,前两位表示该属性长度为2位还是10位。

encoding

encoding记录了节点的content属性所保存数据类型长度高两位表示存储的是字节数组还是整数。

content

存储节点的值。

连续更新

多个连续的长度介于250字节到253字节之间的节点,插入新的头节点(长度大于等于245字节),后面节点的previous_entry_length就要新增4字节的空间(1字节变成5字节),需要进行内存重分配,由于前一个节点的变更,每个节点的previous_entry_length属性也需要记录之前的长度而发生相应的变更,所以会出现连锁更新。除了新增节点,删除节点也可能会遇到这种情况。

因为连锁更新在最坏情况下需要对压缩列表执行N次空间重分配操作,每次重分配的的最坏时间复杂度

1

评论区