您当前的位置:首页 > 电脑百科 > 数据库 > Redis

Redis底层数据结构解密

时间:2021-01-18 12:02:50  来源:  作者:

不要虚度每一天,你的经验就是这样积累出来,然后用在了你的事情上面。
一:摘要概述

很多 redis 的使用者都可以清晰明白的道出Redis中常用的对象如string、list、hash、set、zset,一些场景比较丰富的使用者可能会说布隆过滤器、geo、Hash等。但是对于这些对象底层实现的数据结构却是知之甚少,将会详细阐述redis中的底层数据结构。为了弥补大家的创伤,今天分享Redis底层数据结构内容。

 

二:SDS

string作为redis中常用对象之一,普遍用于用户信息缓存等场景。当string对象中encoding编码为embstr或raw时都是采用sds作为其底层实现

 

2.1 SDS结构

源码文件位于redis安装目录src下的sds.h,sds声明了五种头部类型,分别为sdshdr5、sdshdr8、sdshdr16、sdshdr32、sdshdr64。根据字符串长度创建不同头部的sds实例

 

struct __attribute__ ((__packed__)) sdshdr8 {

uint8_t len;

uint8_t alloc;

unsigned char flags;

char buf[];

};

 

属性名称作用含义

len字符串长度

alloc预分配空间大小

flags低三位用于表示sds类型,可以查看sds.h文件76-82行定义

buf[]存储字符串用数组

2.2 SDS与C字符串区别

区别描述

长度计算 c中的字符串长度计算需要数组遍历,但是redis中的sds自身维护了len属性。所以O(1)时间复杂度即可

缓冲区溢出c中字符串更改如果未提前做好内存分配则会内存溢出,但是sds则会根据alloc与len计算预留内存是否足够分配重新申请内存

动态扩展 缓冲区溢出已经阐述这个概念,sds的内存空间会在字符串内容变更时自动扩展计算。策略为当字符换小于1M时*2翻倍,大于1M时每次扩容1M

惰性释放 与空间预分配相似操作的还有内存惰性释放,即字符串删除某些内容后所占用的内存空间并不会立即释放,后续字符串变更扩展就无需再申请内存

二:ZipList

ziplist可以说把redis对于内存的极致操作体现的淋漓尽致,链表除了节点值之外还需要维护前后节点两个指针,并且还会造成内存碎片。压缩列表紧凑的内存布局,所有节点都维护在整块内存中处理

 

2.1 ZipList结构

属性名称作用含义

zlbytes列表健占用内存的总字节数,在对列表健内存重分配或者是计算zlend的时候使用

zltail 指向压缩列表起始地址的指针

zllen 压缩列表的节点数量

entry压缩列表保存的节点数据

zlend压缩列表的尾节点

2.2 Entry节点结构

 

属性名称作用含义

previous_entry_length 字节为单位记录上一个节点的长度,如果上一个字节长度小于254占用1字节。大于254占用5字节,第一个字节设置为OxFE(十进制254),后面四个字节储存长度

encoding 记录content记录的数据类型以及长度。长度一、二、五字节,值的最高位为00、01、10表示类型为字节数组,长度使用除去最高位的其它位记录。11开头表示储存整数,除去最高位其他位置表示content数据长度

content 记录压缩列表记录的数据

2.3 连锁更新

一个压缩列表节点在保存上一个节点长度使用previous_entry_length属性,这个属性可以使用1字节或者是5字节。假设现有一个压缩列表里面保存的节点长度全部都是250-253,这时候previous_entry_length使用一字节记录就行。但是这时候添加一个新节点到头节点的位置,恰好这个节点的大小大于254字节,这时候所有后面字节都需要更新,因为他们的previous_entry_length都会变成5字节

 

三:QuickList

list 链表是redis中常用对象之一,之前一些版本中底层编码数据采用双向链表、压缩列表的数据结构。但是后续考虑链表指针维护开销以及内存碎片原因,开发新的数据结构quicklist,这是一个双向链表和压缩列表的混合体

 

3.1 quicklist图示

 

3.2 结构描述

typedef struct quicklist {

quicklistNode *head;

quicklistNode *tail;

unsigned long count;

unsigned long len;

int fill : 16;

unsigned int compress : 16;

} quicklist;

 

属性名称作用含义

head头部节点

tail 尾部节点

count压缩列表元素数量总数

len ziplist节点数量

fill 单个ziplist节点的填充因子

compress不压缩节点的深度

3.3 ziplist节点

quicklist 内部默认单个 ziplist 长度为 8k字节,超出了这个字节数就会新建一个 ziplist。ziplist 的长度由配置参数 list-max-ziplist-size决定

Redis底层数据结构解密

 

3.4 LZF压缩

快速列表ziplist为了push与pop操作的效率默认首尾节点不进行LZF压缩,如果需要设置更多节点不进行LZF压缩可以通过redis.conf配置文件中1099行list-compress-depth 0参数定义

 

四:Dict

redis中的hash、set等对象都有使用到字典这个数据结构,字典底层实现使用哈希表的结构。字典中主要掌握它的渐进式hash,结构源码位置位于dict.h文件中

 

4.1 字典结构

typedef struct dict {

dictType *type;

void *privdata;

dictht ht[2];

long rehashidx;

} dict;

 

属性名称作用含义

type 自定义一些操作的方法,拷贝key、拷贝value、销毁key、销毁value等

privdate创建dict时传入,用于某些特殊操作回传给调用函数

ht [0]用于数据存储,[1]用于rehash变更

rehashidx表示rehash进度,-1表示未进行rehash

4.2 哈希表结构

typedef struct dictht {

dictEntry **table;

unsigned long size;

unsigned long sizemask;

unsigned long used;

} dictht;

 

属性名称作用含义

tablehash表节点

size hash表大小

sizemark哈希表大小掩码,计算索引值。大小等于size -1

used哈希表已有的节点数量

4.3 哈希表节点结构

typedef struct dictEntry{

void *key;

union{

void *val;

uint64_tu64;

int64_ts64;

}v;

struct dictEntry *next;

}dictEntry

 

属性名称作用含义

key 保存数据的key值

union值对象,可以是一个对象,因为有个对象空指针或者是uint64、int64的整数

next 指向下一个Entry的指针,形成一个链表

4.4 渐进式rehash

字典的rehash操作数据量过大时并不是一次完成,而是分批次逐渐进行

rehash过程中新插入字典数据放在[1]哈希表中,并将原[0]中数据重新进行hash计算加入[1]中。读操作将会读取[0]、[1]两个哈希表

rehash过程标志使用dict中属性rehashidx标识

rehash采用cow写时复制技术

五:Intset

redis中常用对象set会用到的底层数据结构

 

5.1 整数集合特点

1:内容全是数字

2:内存连续

3:元素有序,不可重复

5.2 Intset结构

typedef struct intset{

uint32_t encoding;

uint32_t length;

int8_t contents[];

}intset;

 

属性名称作用含义

encoding整数集合可以有三种编码方式16、32、64

length整数集合数组中保存的元素个数

contents从小到大保存的整数集合中的元素

六:ZipList

zset中用到的一个数据结构,性能可以和红黑树、AVL树不相上下

Redis底层数据结构解密

 

6.1 跳跃表结构

typedef struct zskiplist{

//表头结点和尾节点

structz skiplistNode *heade,*tail;

//表中节点数量

unsigned long length;

//表中层数最大的节点的层数

int level;

}zskiplist;

 

属性名称作用含义

head跳跃表头结点

tail 跳跃表尾节点

length跳跃表节点数量,表头结点不记录在里面

level 跳跃表最大层数,不记录表头节点

6.2 跳跃表节点

typedof struct zskiplistNode{

//层

struct zskiplistNode{

//前进指针

struct zskiplistNode *forward;

//跨度

unsihned int span;

}level[];

//后退指针

struct zskiplistNode *backward;

//分值

double score;

//成员对象

robj *obj;

}zsikplistNode;

 

属性名称作用含义

zskiplistNode集合记录该节点位于的每一层

forward 每一层节点对应的下一个节点

span 距离下一个节点需要跨越的层数

backward 后退指针

score 节点分数值

obj 跳跃表节点保存的对象



Tags:Redis   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Tags: Redis  点击:(16)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  Tags: Redis  点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  Tags: Redis  点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  Tags: Redis  点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  Tags: Redis  点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  Tags: Redis  点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  Tags: Redis  点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  Tags: Redis  点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  Tags: Redis  点击:(77)  评论:(0)  加入收藏
Nginx来限制访问控制的方法有多种,nginx主要有2个模块控制,但是那些不支持自定义,非常死,在大多数场景下并不实用。今天分享一个:利用openresty+lua+redis 实现封杀频繁恶意访问I...【详细内容】
2021-08-12  Tags: Redis  点击:(118)  评论:(0)  加入收藏
▌简易百科推荐
来源: my.oschina.net/xiaomu0082/blog/2990388首先说下问题现象:内网sandbox环境API持续1周出现应用卡死,所有api无响应现象刚开始当测试抱怨环境响应慢的时候 ,我们重启一下应...【详细内容】
2021-12-08  Java识堂    Tags:Redis   点击:(16)  评论:(0)  加入收藏
我不知道为什么你会选择对特定数量的“错误”(或警告)如此具体。听起来您正在寻找将要发布到 Yahoo! 的某些文章的内容。 Insider (N Foos to Blah for the BlahBlah)。那说:...【详细内容】
2021-12-07  富集云科技有限公司    Tags:Redis   点击:(14)  评论:(0)  加入收藏
目录 一、背景 二、步骤 0.理论支持 1、获取数据 2、结果 3、分析数据并评估大小 三、关于repl-backlog-size 一、背景 repl-backlog-size控制这个环形缓冲区. ​ 主从断...【详细内容】
2021-11-05  弈秋的美好生活    Tags:redis   点击:(41)  评论:(0)  加入收藏
Redis 性能测试是通过同时执行多个命令实现的。1,Redis-benchmarkRedis性能命令:redis性能命令格式: redis-benchmark [option] [option value] redis 性能测试工具可选参数如...【详细内容】
2021-11-02  川石信息    Tags:Redis   点击:(41)  评论:(0)  加入收藏
1 概述数据结构和内部编码 无传统关系型数据库的 Table 模型schema 所对应的db仅以编号区分。同一 db 内,key 作为顶层模型,它的值是扁平化的。即 db 就是key的命名空间。 key...【详细内容】
2021-11-01  JavaEdge    Tags:Redis   点击:(28)  评论:(0)  加入收藏
普通java中使用引用Java redis 驱动,即可连接:import redis.clients.jedis.Jedis; public class RedisTestJava { public static void main(String[] args) { //连...【详细内容】
2021-10-13  faesuite    Tags:Redis   点击:(34)  评论:(0)  加入收藏
Redis常用的数据结构有 string list set zset hashstringstring 是 Redis 的基本的数据类型,一个 key 对应一个 value。string 类型是二进制安全的,Redis的string可以包含任...【详细内容】
2021-10-12  语霖    Tags:Redis   点击:(36)  评论:(0)  加入收藏
列表类型可以存储一组按插入顺序排序的字符串,它非常灵活,支持在两端插入、弹出数据,可以充当栈和队列的角色。> LPUSH fruit apple(integer) 1> RPUSH fruit banana(integer)...【详细内容】
2021-09-17  深夜敲代码    Tags:Redis   点击:(54)  评论:(0)  加入收藏
Redis持久化意义 是做灾难恢复,数据恢复,也可以归类到高可用的一个环节里面去,比如你的redis整个挂了,然后redis就不可用了,你要做的事情是让redis变得可用,尽快变得可用 大量的请...【详细内容】
2021-08-12  小李说IT    Tags:Redis   点击:(77)  评论:(0)  加入收藏
当查询Redis中没有的数据时,该查询会下沉到数据库层,同时数据库层也没有该数据,当这种情况大量出现或被恶意攻击时,接口的访问全部透过Redis访问数据库,而数据库中也没有这些数据...【详细内容】
2021-07-30  随便t    Tags:缓存穿透   点击:(90)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条