搜搜吧

查看: 18|回复: 0

【数据存储】【Redis】 Redis五大数据类型底层实现原理

[复制链接]

超级钻石贵宾会员

2万

主题

4万

帖子

4万

搜搜币

Rank: 1

UID
15150
威望
32
在线时间
321 小时
注册时间
2015-10-2
发表于 2021-10-11 15:10:51 | 显示全部楼层 |阅读模式


6c7e1ae090d240cfb3d24da6dd81f553.jpeg
Redis五大数据类型实现原理
对于五大数据类型(String,list,Hash,Set,Zset)实现原理,Redis在底层用到了多种数据结构,通过数据结构来实现键值对,将数据结构创建了一个对象redisObject,根据对象的类型type,为对象设置多种不同的数据结构,对象可以执行特定的命令。
本章主要涉及到的知识点有:
- redisObject的属性 - 五大数据类型编码注意:本章内容每一小节可单独学习,无论先后。
redisObject属性
学完本章中,读者需要回答:
1.Redis底层数据结构如何实现?2.Redis是如何回收内存?
Redis的一个键值对,有两个对象,一个是键对象,一个是值对象,键总是一个字符串对象,而值可以是字符串、列表、集合等对象,Redis中的值对象都是由 redisObject 结构来表示。
typedef struct redisObject{//表示类型:string,list,hash,set,zsetunsigned type:4;//编码:比如字符串的编码有int编码,embstr编码,raw编码unsigned encoding:4;//指向底层数据结构的指针,prt是个指针变量,存放地址,指向数据存储的位置void *ptr;//引用计数,类似java里的引用计数int refcount;//记录最后一次被程序访问的时间unsigned lru:22;}robj
type属性
redisObject 对象的type属性记录了对象的类型(string,list,hash,set,zset),可以通过type key命令来判断对象类型,从而区分redis中key-value的类型
127.0.0.1:6379> set testString testValueOK127.0.0.1:6379> lpush testList testValue1 testValue2 testValue3(integer) 3127.0.0.1:6379> hmset testhash 1:testvalue 2:testvalue2OK127.0.0.1:6379> sadd testset testvalue(integer) 1127.0.0.1:6379> zadd testzset 1 testvalue(integer) 1127.0.0.1:6379> type testStringstring127.0.0.1:6379> type testListlist127.0.0.1:6379> type testhashhash127.0.0.1:6379> type testsetset127.0.0.1:6379> type testzsetzset
prt和encoding属性
redisObject 对象的 prt 指针,存放数据的地址,指向对象底层的数据结构,通过它可以找到数据的位置,而数据结构由 encoding 属性,也就是编码,由它来决定,可以通过object encoding key命令查看一个值对象的编码。
127.0.0.1:6379> object encoding testString
"embstr"127.0.0.1:6379> object encoding testList"quicklist"127.0.0.1:6379> object encoding testhash"ziplist"127.0.0.1:6379> object encoding testset"hashtable"127.0.0.1:6379> object encoding testzset"ziplist"
refcount 属性
由于C语言跟贴近操作系统,直接跟操作系统交互,命令执行响应比较快,所以Redis选择C语言进行编写可以提高性能,但是C 语言不具备自动回收内存功能,于是乎Redis自己构建了一个内存回收机制。
创建一个新对象,redisObject 对象中的refcount属性就会加1,对象被一个新程序使用,调用incrRefCount函数进行加 1,如果有对象不再被应用程序使用了,那么它就会调用decrRefCount函数进行减 1,当对象的引用计数值为 0 的时候,那么这个对象所占用的内存就会被释放。
从这里可以看出来,这其实就是Java虚拟机中引用计数的内存回收机制,在Java中这种回收机制不被使用,因为它不能解决循环引用的问题。循环引用举例:A引用B,B引用C,C引用A。Redis通过在配置文件中修改相关的配置,来达到解决循环引用的问题,在Redis的配置文件里,windows的配置文件是redis.windows.conf,linux系统的配置文件是redis.conf。在配置文件中有一个配置:maxmemory-policy,当内存使用达到最大值时,redis使用的清楚策略,默认配置是noeviction> 1)volatile-lru 删除已有的过期时间的key > 2)allkeys-lru 删除所有的key > 3)volatile-random 已有过期时间的key 随机删除 > 4)allkeys-random 随机删除key> 5)volatile-ttl 删除即将过期的key > 6)noeviction 不删除任何key,只是返回一个写错误,这个是默认选项 对于整数值的字符串对象(例如:1,2,3这种的)可实现内存共享。问题:什么是内存共享?定义:键不同,值相同。举例:输入命令set key1 1024,键为 key1,值为1024的字符串对象,接着输入命令 set key2 1024 ,键为 key2,值为1024 的字符串对象。这个时候,有二个不同的键,一个相同的值。实现原理:键的值,指针指向一个有值的对象,被共享的值对象引用refcount 加 1。局限性:判断两个对象是否相等需要消耗运算的额外的时间。整数值,判断操作复杂度低;普通字符串,判断复杂度相比较而已是高的;哈希、列表、集合和有序集合,判断的复杂度更高,所以内存共享只适用于整数值的字符串。
lru 属性
Lru属性是redisObject 记录对象最后一次被命令程序访问的时间,用来辅助lru算法删除过期内存的。在Redis 配置文件中有三个配置,最大内存配置 maxmemory,触发数据淘汰后的淘汰策略 maxmemory_policy,随机采样的精度maxmemory_samples。当有条件符合配置文件中三个配置的时候,继续往Redis中加key时,会触发执行 lru 策略,进行内存清除。最近最少使用,lru算法根据数据的历史访问记录进行数据淘汰。
Lru策略的运行原理是数据插入到链表头部,当缓存数据被访问之后,数据会移到链表头,链表满的时候,链表尾部的数据会被丢弃。
redis配置中的淘汰策略(maxmemory_policy)对应的值:> - Noeviction:缓存里的数据超过maxmemory值,这个时候如果客户端正在执行命令,会让内存分配,给客户端返回错误响应> - allkeys-lru: 所有的key都用LRU进行淘汰。 > - volatile-lru: LRU策略淘汰已经设置过过期时间的键。> - allkeys-random:随机淘汰使用的。> - key volatile-random:随机淘汰已设置过过期时间的key> - volatile-ttl:只回收设置了过期时间的key
从redis缓存中淘汰数据,我们的需求是淘汰一些不可能被使用的数据,保留有些以后可能会频繁访问的数据,频繁访问的数据,将来被访问的可能性大很多,所以redis它记录每个数据的最后一次访问时间(lru记录的时间),通过当前时间减去键值对象lru记录的时间,最后可以计算出最少空闲时间,最少空闲时间的数据是最有可能被访问到,这就是LRU淘汰策略的设计思想,是不是很棒。
举例说明:A数据每10s访问一次,B数据每5s访问一次,C数据每50s访问一次,|代表计算空闲时间的截止点。
~~~~~A~~~~~A~~~~~A~~~~A~~~~~A~~~~~A~~|
~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~~B~|
~~~~~~~~~~C~~~~~~~~~C~~~~~~~~~C~~~~~~|
预测被访问的概率是B > A > C。过期key的删除策略有两种:惰性删除:每次获取键时,都检查键是否过期,过期的话,就删除该键;未过期,就返回该键。定期删除:每隔一段时间,进行一次检查,删除里面的过期键。
String 编码
我们最常使用的redis的一个数据类型就是String类型,实现单值缓存,分布式锁,计数器,分布式系统全局序列号等等功能。它的底层编码分为三种,int,raw或者embstr。int编码:存储整数值(例如:1,2,3),当 int 编码保存的值不再是整数值,又或者值的大小超过了long的范围,会自动转化成raw。例如:(1,2,3)->(a,b,c)embstr编码:存储短字符串。它只分配一次内存空间,redisObject和sds是连续的内存,查询效率会快很多,也正是因为redisObject和sds是连续在一起,伴随了一些缺点:当字符串增加的时候,它长度会增加,这个时候又需要重新分配内存,导致的结果就是整个redisObject和sds都需要重新分配空间,这样是会影响性能的,所以redis用embstr实现一次分配而后,只允许读,如果修改数据,那么它就会转成raw编码,不再用embstr编码了。raw编码:用来存储长字符串。它可以分配两次内存空间,一个是redisObject,一个是sds,二个内存空间不是连续的内存空间。和embstr编码相比,它创建的时候会多分配一次空间,删除时多释放一次空间。版本区别:embstr编码版本之间的区别:在redis3.2版本之前,用来存储39字节以内的数据,在这之后用来存储44字节以内的数据。raw编码版本之间的区别:和embstr相反,redis3.2版本之前,可用来存储超过39字节的数据,3.2版本之后,它可以存储超过44字节的数据。问题一:为什么是39字节?从上面可以得知,embstr是一块连续的内存区域,由redisObject和sdshdr组成。embstr最多占64字节场景:redisObject占16个字节
struct RedisObject {int4 type; // 4bits,不同的redis对象会有不同的数据类型(string、list、hash等),type记录类型,会用到4bits。int4 encoding; // 4bits,存储编码形式,用4bits。int24 lru; // 24bits,用24bits记录对象的LRU信息int32 refcount; // 4bytes = 32bits,引用计数器,用到32bitsvoid *ptr; // 8bytes,64-bit system,指针指向对象的具体内容,需要64bits}
计算: 4 + 4 + 24 + 32 + 64 = 128bits = 16bytessdshdr占48字节
struct sdshdr {unsigned int len;//4个字节unsigned int free;//4个字节char buf[];//假设buf里面是39个字节};if (ptr) {memcpy(sh->buf,ptr,len);sh->buf[len] = '';//一个字节
sdshdr的大小为8+39+1=48那么一个embstr最多占64字节:16+48(4+4+1+39)=64从2.4版本开始,redis用jemalloc内存分配器,比glibc的malloc要好一些,省内存,jemalloc会分配8,16,32,64等类型字节的内存。embstr最小为33字节场景:从上面我们可以得知redisObject占16个字节,现在buf中取8字节。
struct sdshdr {unsigned int len;//4个字节unsigned int free;//4个字节char buf[];//假设buf里面是8个字节};if (ptr) {memcpy(sh->buf,ptr,len);sh->buf[len] = '';//一个字节
sdshdr的大小为4+4+8+1=17计算得出:16+17(4+4+1+8)=338,16,32都比33字节小,所以最小分配64字节。通过对比:16+17(4+4+1+8)=3316+48(4+4+1+39)=64当字符数大于8时,会分配64字节。当字符数小于39时,会分配64字节。这个默认39就是这样来的。问题二:为什么分界值由39字节会变成44字节?被暴打的回答是:REDIS_ENCODING_EMBSTR_SIZE_LIMIT值被换成了44了。
#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 39#define REDIS_ENCODING_EMBSTR_SIZE_LIMIT 44
正经的回答是:每个sds都有一个sdshdr,里面的len和free记录了这个sds的长度和空闲空间。
struct sdshdr {unsigned int len;unsigned int free;
用的unsigned int可以表示很大的范围,短的sds空间被浪费了(unsigned int len和unsigned int free 8个字节)commit之后,unsigned int 变成了uint8_t,uint16_t,uint32_t
struct __attribute__ ((__packed__)) sdshdr8 {uint8_t len; /* used */uint8_t alloc; /* excluding the header and null terminator */char flags; /* 2 lsb of type, and 6 msb of refcount */char buf[];};struct __attribute__ ((__packed__)) sdshdr16 {uint16_t len; /* used */uint16_t alloc; /* excluding the header and null terminator */char flags; /* 2 lsb of type, and 6 msb of refcount */char buf[];};struct __attribute__ ((__packed__)) sdshdr32 {uint32_t len; /* used */uint32_t alloc; /* excluding the header and null terminator */char flags; /* 2 lsb of type, and 6 msb of refcount */char buf[];};struct __attribute__ ((__packed__)) sdshdr64 {uint64_t len; /* used */uint64_t alloc; /* excluding the header and null terminator */char flags; /* 2 lsb of type, and 6 msb of refcount */
除此之外还将原来的sdshdr改成了sdshdr16,sdshdr32,sdshdr64
sizes = sdscatprintf(sizes,"sdshdr:%d", (int)sizeof(struct sdshdr));改成了sizes = sdscatprintf(sizes,"sdshdr8:%d", (int)sizeof(struct sdshdr8));sizes = sdscatprintf(sizes,"sdshdr16:%d", (int)sizeof(struct sdshdr16));sizes = sdscatprintf(sizes,"sdshdr32:%d", (int)sizeof(struct sdshdr32));sizes = sdscatprintf(sizes,"sdshdr64:%d", (int)sizeof(struct sdshdr64));
unsigned int占四个字节uint8_t 占1个字节Char 占一个字节我们通过计算可以得出为什么优化之后会多出5个字节了,短字符串的embstr用最小的sdshdr8。sdsdr8 = uint8_t * 2 + char = 1*2+1 = 3sdshdr = unsigned int * 2 = 4 * 2 = 8这么一算是不是少了五个字节了,所以3.2版本更新之后,由于优化小sds的内存使用,使得原本39个字节可以多使用5个字节,这就变成了44字节了。
问题三:Redis字符串最大长度是多少?
512M,查看源码可知。
static int checkStringLength(redisClient *c, long long size) {if (size > 512*1024*1024) {addReplyError(c,"string exceeds maximum allowed size (512MB)");return REDIS_ERR;}return REDIS_OK;}
List编码
List类型可以实现栈,队列,阻塞队列等数据结构,底层是个链表结构,它的底层编码分二种:ziplist(压缩列表) 和 linkedlist(双端链表)。
超过配置的数量或者最大的元素超过临界值时,符合配置的值,触发机制会选择不同的编码。列表保存元素个数小于512个,每个元素长度小于64字节的时候触发机制会使用ziplist(压缩列表)编码,否则使用linkedlist(双端链表)。在redis.conf(linux系统)或者redis.windows.conf(windows系统)对应的配置:
list-max-ziplist-entries 512list-max-ziplist-value 64
通过修改配置这二个配置,设置触发条件选择编码。比如我修改列表保存元素个数小于1024个并且每个元素长度小于128字节时使用ziplist(压缩列表)编码,否则使用linkedlist(双端链表)。修改配置如下:
list-max-ziplist-entries 1024list-max-ziplist-value 128
Hash 编码
Hash类型比string类型消耗内存和cpu更小。Hash的编码有二种 ziplist编码 或者 hashtable。
超过指定的值,最大的元素超过临界值时,符合配置的值,触发机制选择不同的编码。列表保存元素个数小于512个,每个元素长度小于64字节的时候,使用ziplist(压缩列表)编码,否则使用hashtable 。配置文件中可以通过修改set-max-intset-entries 1024达到改变列表保存元素个数小于1024个,原理类似。hashtable 编码是字典作为底层实现,字典的键是字符串对象,值则全部设置为 null。在上面的字典也有详细介绍。
Set集合对象
Set类型可以实现抽奖小程序,点赞,收藏,加标签,关注模型等功能。Set的编码有二种intset 或者 hashtable。
超过指定的值,最大的元素超过临界值时,符合配置条件,触发机制选择不同的编码。集合对象中所有元素都是整数,对象元素数量不超过512时,使用intset编码,否则使用hashtable。原理大致和上面的类型相同。列表保存元素个数的配置也是通过set-max-intset-entries进行修改的。intset 编码用整数集合作为底层实现,hashtable编码可以类比HashMap的实现,HashTable类中存储的实际数据是Entry对象,数据结构与HashMap是相同的。
Zset有序集合对象
Zset适合做排序以及范围查询等功能,比如实现实现排行榜等。有序集合的编码有二种 ziplist 或者 skiplist。保存的元素数量小于128,存储的所有元素长度小于64字节的时候,使用ziplist编码,否则用skiplist编码。修改配置如下:
zset-max-ziplist-entries 128zset-max-ziplist-value 64
ziplist 编码底层是用压缩列表实现的,集合元素是两个紧挨在一起的压缩列表节点来保存,第一个节点保存元素的成员,第二个节点保存元素的分值。 压缩列表的集合元素按照设置的分值从小到大的顺序进行排列,小的放置在靠近表头的位置,大的放置在靠近表尾的位置。skiplist 编码的有序集合对象使用 zet 结构作为底层实现,一个 zset 结构同时包含一个字典和一个跳跃表。字典的键保存元素的值,字典的值则保存元素的分值;跳跃表节点的 object 属性保存元素的成员,跳跃表节点的 score 属性保存元素的分值。这两种数据结构会通过指针来共享相同元素的成员和分值,所以不会产生重复成员和分值,造成内存的浪费。
问题:为什么需要二种数据结构?
有序集合单独使用字典或跳跃表,其中一种数据结构都可以实现,但是这里用两种数据结构组合起来。原因是我们单独用字典,时间复杂度虽然低一些,查找成员的分值也快,但是字典以无序的方式来保存集合元素的,所以每次进行范围操作的时候都要重新进行排序,对性能有影响。单独用跳跃表,虽然可以进行范围操作,但是查询复杂度变高了。因此Redis使用了两种数据结构来共同实现有序集合,可以保证排序的效率

Powered by www.sosoba.org Copyright © 2013-2021 搜搜吧社区 小黑屋|手机版|Archiver|地图|联系站长|腾讯云代金券|公共DNS|seo优化服务|搜搜吧
广告服务/项目合作/会员购买:QQ 侵权举报邮箱: fuwu-sosoba@qq.com 举报流程必看 搜搜吧建站时间:创建于2013年07月23日
免责声明:本站所有的内容均来自互联网以及第三方作者自由发布,版权归原作者版权所有,搜搜吧不承担任何的法律责任,若有侵权请来信告知,我们立即删除!
版权声明:搜搜吧影视资源均收集自互联网,没有提供影片资源存储和下载,也未参与录制上传,若本站收录的资源涉及您的版权或知识产权或其他利益,我们会立即删除

GMT+8, 2021-10-21 09:44 , Processed in 0.028853 second(s), 9 queries , Redis On.

快速回复 返回顶部 返回列表