首页 > 编程知识 正文

redis有序集合底层实现方式,redis数据类型及底层数据结构

时间:2023-05-04 00:08:55 阅读:23172 作者:759

Redis源代码的核心部分: src软件包下该怎么办?

Redis基本的数据结构(骨架):

1 .简单动态字符串sds.c

2 .整数集合intset.c

3 .压缩列表ziplist.c

4 .快速链接表quicklist.c

5 .词典dict.c

6 .流基础实现结构listpack.c和rax.c

Redis数据类型的底层实现:

Github官网说明:

https://github.com/redis/redis

Redis对象object.c

字符串t_string.c

列表t_list.c

词典t_hash.c

以及有序集合t_set.c和t_zset.c

数据流t_stream.c

Redis数据库的实现:

1 .数据库的基础实现数据库

2 .持久化rdb.c和aof.c

Redis服务端和客户端实现:

事件驱动的ae.c和ae_epoll.c

网络连接anet.c和networking.c

服务端程序server.c

客户端程序redis-cli.c

其他:

主从复制复制. c

哨兵sentinel.c

集群cluster.c

其他数据结构,如hyperloglog.c和geo.c

其他功能,如pub/sub和Lua脚本

我们平时说redis是字典数据库KV键值对到底是什么?

一句话:

redis是密钥值存储系统。

其中key类型一般为字符串,value 类型则为redis对象(redisObject)

图解:

6大类型说明(粗分):

1 .传统的五种类型

2 .新介绍的三种类型

位图---------实质字符串

hyperloglog---------实质上是字符串

GeO---------实质Zset

上帝的观点:

3359 redis src.readthedocs.io/en/latest/data struct/dict.html

3359 redis src.readthedocs.io/en/latest/index.html

Redis定义了表示字符串、散列、列表、集、zset等数据类型的redisObjec结构

c语言结构语法概述:

Redis 中每个对象都是一个 redisObject 结构

词典,什么是kv:http://www.Sina.com /

RedisObject Redis数据类型redis所有编码(基本实现)的关系:

每个键值对都会有一个dictEntry

从set hello world开始吧:

以set hello word为例,每个键值对都有一个dictEntry (源位置: dict.h ),因为Redis是KV键值对的数据库。

其中指向key和value指针,next指向以下目录条目:

key是字符串,但Redis不直接使用c字符数组,而是存储在Redis自定义的SDS中。

value既不会直接存储在字符串中,也不会存储在SDS中,而是存储在redisObject中。

实际上,redisObject存储五种常见数据类型之一。

每个键-值对都有一个dictEntry。

看看类型------------type键

看代码----------------objectencodinghello

调试结构---------------调试对象人员

5大结构底层C语言源码分析:

为了便于操作,Redis采用了RedisObject结构来统一五种不同的数据类型,

所有这种数据类型都可以在函数之间以相同的形式传递

特定类型的结构。 另外,为了识别不同的数据类型,在redisObject中

type和encoding字段是按数据类型区分的。 简而言之,redisObjec结构的作用:

edisObject就是string,hash,list,set,zset,的父类,
可以在函数间传递时隐藏具体的类型信息,所以作者抽象了redisObject结构
来达到同样的目的。

RedisObject各字段的含义:



1.4位的type表示具体的数据类型
2.4位的encoding表示该类型的物理编码,同一种数据类型可能有不同的编码方式。
(比如String就提供了3种:int embstr raw)

3. lru字段表示当内存超限时采用LRU算法清除内存中的对象。
4. refcount表示对象的引用计数。
5. ptr指针指向真正的底层数据结构的指针。

案例:
set age 17



数据类型以及数据结构的关系:


程序员写代码时脑子底层思维:

String数据结构介绍:

3大编码格式:
1.int
保存long 型(长整型)的64位(8个字节)有符号整数
9223372036854775807

上面数字最多19位
只有整数才会使用 int,如果是浮点数, Redis 内部其实先将浮点数转化为字符串值,然后再保存。

2.embstr:代表 embstr 格式的 SDS(Simple Dynamic String 简单动态字符串),保存长度小于44字节的字符串EMBSTR 顾名思义即:embedded string,表示嵌入式的String3.raw保存长度大于44字节的字符串

3大编码案例:
案例测试:

C语言中字符串的展现:


Redis没有直接复用C语言的字符串,而是新建了属于自己的结构-----SDS
在Redis数据库里,包含字符串值的键值对都是由SDS实现的(Redis中所有的键都是由字符串对象实现的即底层是由SDS实现,Redis中所有的值对象中包含的字符串对象底层也是由SDS实现)。


SDS简单动态字符串:


Redis中字符串的实现,SDS有多种结构(sds.h):
sdshdr5、(2^5=32byte)
sdshdr8、(2 ^ 8=256byte)
sdshdr16、(2 ^ 16=65536byte=64KB)
sdshdr32、 (2 ^ 32byte=4GB)
sdshdr64,2的64次方byte=17179869184G用于存储不同的长度的字符串。

len 表示 SDS 的长度,使我们在获取字符串长度的时候可以在 O(1)情况下拿到,而不是像 C 那样需要遍历一遍字符串。

alloc 可以用来计算 free 就是字符串已经分配的未使用的空间,有了这个值就可以引入预分配空间的算法了,而不用去考虑内存分配的问题。

buf 表示字符串数组,真存数据的。


Redis为什么重新设计一个 SDS 数据结构?


C语言没有Java里面的String类型,只能是靠自己的char[]来实现,字符串在C语言中的存储方式,
想要获取Redis的长度,需要从头开始遍历,直到遇到‘’为止。所以,Redis没有直接使用C语言
传统的字符串标识,而是自己构建了一种名为简单动态字符串SDS的抽象类型,并将SDS作为
Redis的默认字符串。


源码分析:

用户API:set k1 v1底层发生了什么?调用关系


三大编码:

INT 编码格式:
set k1 123
命令示例: set k1 123
当字符串键值的内容可以用一个64位有符号整形来表示时,Redis会将键值转化为long型来进行存储,此时即对应 OBJ_ENCODING_INT 编码类型。内部的内存结构表示如下:

Redis 启动时会预先建立 10000 个分别存储 0~9999 的 redisObject 变量作为共享对象,这就意味着如果 set字符串的键值在 0~10000 之间的话,则可以 直接指向共享对象 而不需要再建立新对象,此时键值不占空间!
set k1 123
set k2 123

redis源代码:object.c


EMBSTR编码格式
set k1 abc
redis源代码:object.c


对于长度小于 44的字符串,Redis 对键值采用OBJ_ENCODING_EMBSTR 方式,EMBSTR 顾名思义即:embedded string,表示嵌入式的String。从内存结构上来讲 即字符串 sds结构体与其对应的 redisObject 对象分配在同一块连续的内存空间,字符串sds嵌入在redisObject对象之中一样。


进一步
redis源代码:object.c


RAW 编码格式:

set k1 大于44长度的一个字符串,随便写


当字符串的键值为长度大于44的超长字符串时,Redis则会将键值内部的编码方式改为
OBJ_ENCODING_RAW格式,这与OBJ_ENCODING_EMBSTR编码方式的不同之处在于,
此时动态字符串sds的内存与其依赖的redisObject的内存不再连续了

明明没有超过阈值,为什么变成 raw 了?

转变逻辑图:

案例结论:

只有整数才会使用int,如果是浮点数,Redis内部其实先将浮点数转化为字符串值,然后再保存。
embstr 与 raw 类型底层的数据结构其实都是SDS(简单动态字符串,Redis内部定义sdshdr一种结构)

两者的区别如下:

int : Long类型的整数时,RedisObject的ptr指针直接赋值为整数数据,不在额外的指针再指向整数了,节省了指针的空间开销。
embstr : 当保存的是字符串数据且字符串小于等于44字节时,embstr类型将会调用内存分配函数,只分配一块连续的内存空间,空间中依次包含的redisObject与sdshdr两个数据结构,
让元数据、指针和SDS是一块连续的内存区域,这样就可以避免内存碎片

raw: 当字符串大于44字节时,SDS的数据量变多变大了,SDS和RedisObject布局分家各自过,会给SDS分配多个空间并用指针指向SDS结构,raw类型将会调用两次内存分配函数,
分配两块内存空间,一块用于包含redisObject结构,而另一块用于包含sdshdr结构。


Redis内部会根据用户给的不同键值而使用不同的编码格式,自适应地选择较优化的内部编码格式,而这一切对用户完全透明!

流程图:

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。