流殃的博客

| Comments

image.png
redis有五种基本数据类型,分别是

  1. string 底层是SDS
  2. list 由「双向链表」或「压缩表列表」实现;
  3. hash 由「压缩列表」或「哈希表」实现;
  4. set 「哈希表」或「整数集合」实现;
  5. zset 「压缩列表」或「跳表」实现;

String

应用场景

这是最简单的类型,就是普通的 set 和 get,做简单的 KV 缓存。
使用这个类型需要注意的是,不要什么都用string来存储,还是要选择合适的数据机构,而不是无脑string,String类型的值最大存储是512MB
现在应用比较广泛的有:

  • 缓存功能:String字符串是最常用的数据类型,不仅仅是Redis,各个语言都是最基本类型,因此,利用Redis作为缓存,配合其它数据库作为存储层,利用Redis支持高并发的特点,可以大大加快系统的读写速度、以及降低后端数据库的压力。
  • 计数器:许多系统都会使用Redis作为系统的实时计数器,可以快速实现计数和查询的功能。而且最终的数据结果可以按照特定的时间落地到数据库或者其它存储介质当中进行永久保存。
  • 共享用户Session:用户重新刷新一次界面,可能需要访问一下数据进行重新登录,或者访问页面缓存Cookie,但是可以利用Redis将用户的Session集中管理,在这种模式只需要保证Redis的高可用,每次用户Session的更新和获取都可以快速完成。大大提高效率。
  • 统计多单位的数量:eg,uid:gongming count:0 根据不同的uid更新count数量。

类型转换

  • 当保存的值为整数且值的大小不超过long的范围,使用整数存储
  • 当字符串长度不超过44字节时,使用EMBSTR 编码
    它只分配一次内存空间,redisObject和sds是连续的内存,查询效率会快很多,也正是因为redisObject和sds是连续在一起,伴随了一些缺点:当字符串增加的时候,它长度会增加,这个时候又需要重新分配内存,导致的结果就是整个redisObject和sds都需要重新分配空间,这样是会影响性能的,所以redis用embstr实现一次分配而后,只允许读,如果修改数据,那么它就会转成raw编码,不再用embstr编码了。
  • 大于44字符时,使用raw编码

命令

set name shy     #设置name为shy的键值对
get name    #获取键为name的值
keys *    #查看所有键值对
exits key名字 #返回1,表示key存在,0表示不存在
move key名字 1  #1表示当前数据库,删除key
expire key名字 10  #设置key名字的过期时间为10秒
ttl key名字 #查看key名字的过期时间还剩多少秒
type key名字 #key的类型
append key名字 值 #向key的值追加数据
strlen key名字 #获取key的长度
incr key  #给key+1
decr key   #给key-1
incrby key 步长  #key每次加多少
decrby  key 步长# key每次减多少
getrange key 0 3  #截取字符串从0到3
getrange key 0 -1  #查看所有内容
setrange key 1 xx   #将第1位的值替换为xx
setex(set with expire)  #设置过期时间
setex key3 30 “hello” #设置key3的值为hello,30秒后会过期
setnx(set if not exist)  #不存在设置
setnx key3 “redis”  #如果不存在key3,就创建
mset key value  #一次设置多个键值对
mget key1 key2  #一次获取多个键的值
msetnx 多键值对版本 #是一个原子性的操作,要么都成功,要么都失败 
mset user:1:name zhangsan  user:1:age 12
#设置一个对象的两个属性 对象名:ID:属性名
mget user:1:name user:1:age
#获取一个对象的两个属性
setget v1 redis
#如果不存在v1,则返回空,但是将v1的值设置为redis
#,如果存在,则返回v1的值,然后将v1的设置为redis

SDS

embstr和raw都为sds编码,看一下sds的结构体
采用sds结构来存储字符串,结果如下

image-20210423141456702

redis中使用这样的sds的结构来构建字符串主要有以下几个原因:

  1. 当获取长度的时候,时间复杂度为0(1)
  2. 二进制安全,当比如用一个空字符串作为字符串中的一个特殊变量的时候,由于c中的字符串是通过\0这个空字符来区分一个字符串是否结尾的,所以它只能用于保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据
  3. 杜绝缓冲区溢出(sds是通过预分配策略和惰性空间释放来减少的)
  4. 减少修改字符串时带来的内存重分配次数(sds是通过预分配策略和惰性空间释放来减少的)
  5. 可以使用c语言的一些函数,因为sds字符串的也是以\0 作为结尾的,但是sds字符串是通过sds的len属性来确定这个字符串是不是结束的,c的字符串则是单一的通过\0来确认一个字符串是否结束

预分配策略

如果对SDS进行修改之后,SDS的长度(也即是len属性的值)将小于1MB,那么程序分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同。举个例子,如果进行修改之后,SDS的len将变成13字节,那么程序也会分配13字节的未使用空间,SDS的buf数组的实际长度将变成13+13+1=27字节(额外的一字节用于保存空字符)。

如果对SDS进行修改之后,SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。举个例子,如果进行修改之后,SDS的len将变成30MB,那么程序会分配1MB的未使用空间,SDS的buf数组的实际长度将为30MB+1MB+1byte。

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

sds和c字符串的区别

image-20210423141537291

List

底层结构

  1. Redis3.2之前的底层实现方式:压缩列表ziplist 或者 双向循环链表linkedlist

Redis3.2之前,当list存储的数据量比较少且同时满足下面两个条件时,list就使用ziplist存储数据:

  • list中保存的每个元素的长度小于 64 字节;
  • 列表中数据个数少于512个
  1. Redis3.2及之后的底层实现方式:quicklist

quicklist是一个双向链表,而且是一个基于ziplist的双向链表,quicklist的每个节点都是一个ziplist,结合了双向链表和ziplist的优点

ziplist

ziplist是一种压缩链表,它的好处是更能节省内存空间,因为它所存储的内容都是在连续的内存区域当中的。当列表对象元素不大,每个元素也不大的时候,就采用ziplist存储。但当数据量过大时就ziplist就不是那么好用了。因为为了保证他存储内容在内存中的连续性,插入的复杂度是O(N),即每次插入都会重新进行realloc。如下图所示,redisObject对象结构中ptr所指向的就是一个ziplist。整个ziplist只需要malloc一次,它们在内存中是一块连续的区域。

ziplist结构如下:
image.png

  1. zlbytes:用于记录整个压缩列表占用的内存字节数
  2. zltail:记录要列表尾节点距离压缩列表的起始地址有多少字节
  3. zllen:记录了压缩列表包含的节点数量。
  4. entryX:要说列表包含的各个节点
  5. zlend:用于标记压缩列表的末端
    为什么数据量大时不用ziplist?
    因为ziplist是一段连续的内存,插入的时间复杂化度为O(n),而且每当插入新的元素需要realloc做内存扩展;而且如果超出ziplist内存大小,还会做重新分配的内存空间,并将内容复制到新的地址。如果数量大的话,重新分配内存和拷贝内存会消耗大量时间。所以不适合大型字符串,也不适合存储量多的元素。

quickList

快速列表是ziplist和linkedlist的混合体,是将linkedlist按段切分,每一段用ziplist来紧凑存储,多个ziplist之间使用双向指针链接。
为什么不直接使用linkedlist?
linkedlist的附加空间相对太高,prev和next指针就要占去16个字节,而且每一个结点都是单独分配,会加剧内存的碎片化,影响内存管理效率。

结构


typedef struct quicklist {
    // 指向quicklist的头部
    quicklistNode *head;
    // 指向quicklist的尾部
    quicklistNode *tail;
    unsigned long count;
    unsigned int len;
    // ziplist大小限定,由list-max-ziplist-size给定
    int fill : 16;
    // 节点压缩深度设置,由list-compress-depth给定
    unsigned int compress : 16;
} quicklist;

typedef struct quicklistNode {
    // 指向上一个ziplist节点
    struct quicklistNode *prev;
    // 指向下一个ziplist节点
    struct quicklistNode *next;
    // 数据指针,如果没有被压缩,就指向ziplist结构,反之指向quicklistLZF结构
    unsigned char *zl;
    // 表示指向ziplist结构的总长度(内存占用长度)
    unsigned int sz;
    // ziplist数量
    unsigned int count : 16;     /* count of items in ziplist */
    unsigned int encoding : 2;   /* RAW==1 or LZF==2 */
    // 预留字段,存放数据的方式,1--NONE,2--ziplist
    unsigned int container : 2;  /* NONE==1 or ZIPLIST==2 */
    // 解压标记,当查看一个被压缩的数据时,需要暂时解压,标记此参数为1,之后再重新进行压缩
    unsigned int recompress : 1; /* was this node previous compressed? */
    unsigned int attempted_compress : 1; /* node can't compress; too small */
    // 扩展字段
    unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode;

typedef struct quicklistLZF {
    // LZF压缩后占用的字节数
    unsigned int sz; /* LZF size in bytes*/
    // 柔性数组,存放压缩后的ziplist字节数组
    char compressed[];
} quicklistLZF;

image.png
ziplist的长度

quicklist内部默认单个ziplist长度为8k字节,超出了这个字节数,就会新起一个ziplist。关于长度可以使用list-max-ziplist-size决定。

压缩深度

我们上面说到了quicklist下是用多个ziplist组成的,同时为了进一步节约空间,Redis还会对ziplist进行压缩存储,使用LZF算法压缩,可以选择压缩深度。quicklist默认的压缩深度是0,也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。为了支持快速push/pop操作,quicklist 的首尾两个 ziplist 不压缩,此时深度就是 1。如果深度为 2,就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。

应用场景

List 是有序列表,这个还是可以玩儿出很多花样的。
比如可以通过 List 存储一些列表型的数据结构,类似粉丝列表、文章的评论列表之类的东西。
比如可以通过 lrange 命令,读取某个闭区间内的元素,可以基于 List 实现分页查询,这个是很棒的一个功能,基于 Redis 实现简单的高性能分页,可以做类似微博那种下拉不断分页的东西,性能高,就一页一页走。
比如可以搞个简单的消息队列,从 List 头怼进去,从 List 屁股那里弄出来。

  • 消息队列:Redis的链表结构,可以轻松实现阻塞队列,可以使用左进右出的命令组成来完成队列的设计。比如:数据的生产者可以通过Lpush命令从左边插入数据,多个数据消费者,可以使用BRpop命令阻塞的“抢”列表尾部的数据。
  • 文章列表或者数据分页展示的应用。
    比如,我们常用的博客网站的文章列表,当用户量越来越多时,而且每一个用户都有自己的文章列表,而且当文章多时,都需要分页展示,这时可以考虑使用Redis的列表,列表不但有序同时还支持按照范围内获取元素,可以完美解决分页查询功能。大大提高查询效率。

常用语法

在redis中可以将list玩成栈,队列,阻塞队列

list中所有的命令以l开头

lpush list one  #将一个或多个值插入到列表头部(左)
rpush list one  # 将一个或多个值插入到列表尾部(右)
lrange list 0 -1 # 获取list中的值!
lpop list  # 移除列表的第一个元素
rpop #移除列表的最后一个元素
lindex list 0  # 获取list的第0个值
llen list   # 获取list的长度
lrem list 1 one # 移除list结合中指定个数的value
ltrim list 1 2 #通过下标截取指定的长度
rpoplpush list list1 #移除list列表中最后一个元素到新的list1列表中
exists list #判断list是否存在
lset list 0 item #将list【0】的值设为item 注意:如果list没有创建,会报错
linsert list before/after ss # aa在list集合中的值ss的前面(或后面)aa

why

结构

img

image-20210509075856037

特性

  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三个属性为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值

Set

  1. redis集合(set)类型和list列表类型类似,都可以用来存储多个字符串元素的集合。
  2. 但是和list不同的是set集合当中不允许重复的元素。而且set集合当中元素是没有顺序的,不存在元素下标。
  3. redis的set类型是使用哈希表构造的,因此复杂度是O(1),它支持集合内的增删改查,
    并且支持多个集合间的交集、并集、差集操作。可以利用这些集合操作,解决程序开发过程当中很多数据集合间的问题。

应用场景

1、标签:比如我们博客网站常常使用到的兴趣标签,把一个个有着相同爱好,关注类似内容的用户利用一个标签把他们进行归并。

2、共同好友功能,共同喜好,或者可以引申到二度好友之类的扩展应用。

3、统计网站的独立IP。利用set集合当中元素不唯一性,可以快速实时统计访问网站的独立IP。

sorted set

redis有序集合也是集合类型的一部分,所以它保留了集合中元素不能重复的特性,但是不同的是,有序集合给每个元素多设置了一个分数,,利用该分数作为排序的依据。

应用场景

  1. 排行榜:有序集合经典使用场景。例如视频网站需要对用户上传的视频做排行榜,榜单维护可能是多方面:按照时间、按照播放量、按照获得的赞数等
  2. 用Sorted Sets来做带权重的队列,比如普通消息的score为1,重要消息的score为2,然后工作线程可以选择按score的倒序来获取工作任务。让重要的任务优先执行

hash

Redis hash数据结构 是一个键值对(key-value)集合,它是一个 string 类型的 field 和 value 的映射表,
redis本身就是一个key-value型数据库,因此hash数据结构相当于在value中又套了一层key-value型数据。
所以redis中hash数据结构特别适合存储关系型对象

应用场景

  1. 由于hash数据类型的key-value的特性,用来存储关系型数据库中表记录,是redis中哈希类型最常用的场景。一条记录作为一个key-value,把每列属性值对应成field-value存储在哈希表当中,然后通过key值来区分表当中的主键
  2. 经常被用来存储用户相关信息。优化用户信息的获取,不需要重复从数据库当中读取,提高系统性能

结构

image-20210509085530594

image-20210509085552656

底层数据结构

链表

结构

一般链表的实现

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

有前置节点和后置节点,可以看的出,这个是一个双向链表。
image.png
redis链表结构

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;

list 结构为链表提供了链表头指针 head、链表尾节点 tail、链表节点数量 len、以及可以自定义实现的 dup、free、match 函数。

举个例子,下面是由 list 结构和 3 个 listNode 结构组成的链表。
image.png
Redis 的链表实现优点如下:

  • listNode 链表节点带有 prev 和 next 指针,获取某个节点的前置节点或后置节点的时间复杂度只需O(1),而且这两个指针都可以指向 NULL,所以链表是无环链表;

  • list 结构因为提供了表头指针 head 和表尾节点 tail,所以获取链表的表头节点和表尾节点的时间复杂度只需O(1);

  • list 结构因为提供了链表节点数量 len,所以获取链表中的节点数量的时间复杂度只需O(1);

  • listNode 链表节使用 void* 指针保存节点值,并且可以通过 list 结构的 dup、free、match 函数指针为节点设置该节点类型特定的函数,因此链表节点可以保存各种不同类型的值;
    链表的缺陷也是有的,链表每个节点之间的内存都是不连续的,意味着无法很好利用 CPU 缓存。
    能很好利用 CPU 缓存的数据结构就是数组,因为数组的内存是连续的,这样就可以充分利用 CPU 缓存来加速访问。
    因此,Redis 的 list 数据类型在数据量比较少的情况下,会采用「压缩列表」作为底层数据结构的实现,压缩列表就是由数组实现的.

压缩列表

压缩列表是 Redis 数据类型为 list 和 hash 的底层实现之一。

  • 当一个列表键(list)只包含少量的列表项,并且每个列表项都是小整数值,或者长度比较短的字符串,那么 Redis 就会使用压缩列表作为列表键(list)的底层实现。

  • 当一个哈希键(hash)只包含少量键值对,并且每个键值对的键和值都是小整数值,或者长度比较短的字符串,那么 Redis 就会使用压缩列表作为哈希键(hash)的底层实现。

结构

压缩列表是 Redis 为了节约内存而开发的,它是由连续内存块组成的顺序型数据结构,有点类似于数组。
image.png
压缩列表在表头有三个字段:

  • zlbytes,记录整个压缩列表占用对内存字节数;

  • zltail,记录压缩列表「尾部」节点距离起始地址由多少字节,也就是列表尾的偏移量;

  • zllen,记录压缩列表包含的节点数量;

  • zlend,标记压缩列表的结束点,特殊值 OxFF(十进制255)。
    在压缩列表中,如果我们要查找定位第一个元素和最后一个元素,可以通过表头三个字段的长度直接定位,复杂度是 O(1)。而查找其他元素时,就没有这么高效了,只能逐个查找,此时的复杂度就是 O(N) 了。

另外,压缩列表节点(entry)的构成如下:
image.png

压缩列表节点包含三部分内容:

  • prevlen,记录了前一个节点的长度;

  • encoding,记录了当前节点实际数据的类型以及长度;

  • data,记录了当前节点的实际数据;

当我们往压缩列表中插入数据时,压缩列表 就会根据数据是字符串还是整数,以及它们的大小会在 prevlen 和 encoding 这两个元素里保存不同的信息,这种根据数据大小进行对应信息保存的设计思想,正是 Redis 为了节省内存而采用的。

连锁更新

压缩列表除了查找复杂度高的问题,压缩列表在插入元素时,如果内存空间不够了,压缩列表还需要重新分配一块连续的内存空间,而这可能会引发连锁更新的问题。

压缩列表里的每个节点中的 prevlen 属性都记录了「前一个节点的长度」,而且 prevlen 属性的空间大小跟前一个节点长度值有关,比如:

  • 如果前一个节点的长度小于 254 字节,那么 prevlen 属性需要用 1 字节的空间来保存这个长度值;

  • 如果前一个节点的长度大于等于 254 字节,那么 prevlen 属性需要用 5 字节的空间来保存这个长度值;
    当每个节点都小于254字节,然后突然有一个大于254字节的节点插到第二个节点的前面,那么根据压缩列表的规则,就要进行空间重新发配,第二个节点长度大于254字节,就需要5字节空间,然后依次类推,每个都要让后面的重新分配,这种现象就叫做 连锁更新。

连锁更新一旦发生,就会导致压缩列表 占用的内存空间要多次重新分配,这就会直接影响到压缩列表的访问性能。

所以说,虽然压缩列表紧凑型的内存布局能节省内存开销,但是如果保存的元素数量增加了,或是元素变大了,压缩列表就会面临「连锁更新」的风险。

因此,压缩列表只会用于保存的节点数量不多的场景,只要节点数量足够小,即使发生连锁更新,也是能接受的。

hash表

典型的 key value的数据结构,优点就是O(1)的快速查询,缺点就是容易产生hash冲突,redis的hash冲突的解决方式就是 链式哈希

rehash

Redis 会使用了两个全局哈希表进行 rehash。

在正常服务请求阶段,插入的数据,都会写入到「哈希表 1」,此时的「哈希表 2 」 并没有被分配空间。
随着数据逐步增多,触发了 rehash 操作,这个过程分为三步:

给「哈希表 2」 分配空间,一般会比「哈希表 1」 大 2 倍;

将「哈希表 1 」的数据迁移到「哈希表 2」 中;

迁移完成后,「哈希表 1 」的空间会被释放,并把「哈希表 2」 设置为「哈希表 1」,然后在「哈希表 2」 新创建一个空白的哈希表,为下次 rehash 做准备。

渐进式 rehash

为了避免 rehash 在数据迁移过程中,因拷贝数据的耗时,影响 Redis 性能的情况,所以 Redis 采用了渐进式 rehash,也就是将数据的迁移的工作不再是一次性迁移完成,而是分多次迁移。

渐进式 rehash 步骤如下:

  • 给「哈希表 2」 分配空间;

  • 在 rehash 进行期间,每次哈希表元素进行新增、删除、查找或者更新操作时,Redis 除了会执行对应的操作之外,还会顺序将「哈希表 1 」中索引位置上的所有 key-value 迁移到「哈希表 2」 上;

  • 随着处理客户端发起的哈希表操作请求数量越多,最终会把「哈希表 1 」的所有 key-value 迁移到「哈希表 2」,从而完成 rehash 操作。

这样就巧妙地把一次性大量数据迁移工作的开销,分摊到了多次处理请求的过程中,避免了一次性 rehash 的耗时操作。

在进行渐进式 rehash 的过程中,会有两个哈希表,所以在渐进式 rehash 进行期间,哈希表元素的删除、查找、更新等操作都会在这两个哈希表进行。

比如,查找一个 key 的值的话,先会在哈希表 1 里面进行查找,如果没找到,就会继续到哈希表 2 里面进行找到。

另外,在渐进式 rehash 进行期间,新增一个 key-value 时,会被保存到「哈希表 2 」里面,而「哈希表 1」 则不再进行任何添加操作,这样保证了「哈希表 1 」的 key-value 数量只会减少,随着 rehash 操作的完成,最终「哈希表 1 」就会变成空表。

rehash 触发条件

和负载因子有关系
image.png

  • 当负载因子大于等于 1 ,并且 Redis 没有在执行 bgsave 命令或者 bgrewiteaof 命令,也就是没有执行 RDB 快照或没有进行 AOF 重写的时候,就会进行 rehash 操作。

  • 当负载因子大于等于 5 时,此时说明哈希冲突非常严重了,不管有没有有在执行 RDB 快照或 AOF 重写,都会强制进行 rehash 操作。

参考

Comments

评论