Redis内部数据详解

sorted set:当数据较少时,使用ziplist实现,数据较多时,使用zset(dict+skiplist)实现。

zset-max-ziplist-entries 128
zset-max-ziplist-value 64

这两个配置是当sorted set中元素数量超过128个,即ziplist数据项超过256个(数据,score)或任意一个数据值长度超过64时,ziplist会转化为zset(dict+skiplist)

skiplist

节点每增加一层的概率为P(0.25),每个节点的最大成熟记为MaxLevel(32)

跳表节点的平均层数为:1/(1-P)

平均查找长度约为:C(log1/pn-1)=(log(1/p^(n-1))/p,平均时间复杂度为:O(log N)

ziplist

Ziplist 是为了尽可能地节约内存而设计的特殊编码双端链表。

ziplist结构中,每个entry储存了前一个entry的byte长度,用于反向定位上一个节点的位置。

这个节点长度所占用的字节数可能是1或5,导致增加和删除节点时,需要同步更新后续entry的值。

ziplist的修改操作效率很差,每次数据变动都会引发一次内存realloc,会导致大量的数据拷贝。

quicklist

内部节点采用LZF无损压缩算法。

sds

sds正是在Redis中被广泛使用的字符串结构,它的全称是Simple Dynamic String。

sds是一个二进制安全的字符指针(char *)的形式, 但不完全等同于char *。它由一个header结构构成,可以储存 \0

dict

字典(dict)是由键值对组成的结构,Redis中的db和hash key都基于dict实现,dict的底层实现为hash表。hash算法有两种,广泛应用的为MurmurHash算法(算法的分布率和速度都非常好),另一种 djb 算法用于命令表和lua脚本缓存。

每个字典有两个哈希表,用于进行 渐进式rehash 过程。rehash过程开启后,每次对hash表进行 增/删/改/查 操作都会让rehash过程执行一帧,每帧将第一个hash表ht[0]上第一个不为空的索引上的所有节点迁往第二个hash表ht[1]。rehash过程中,所有的 删/改/查 操作,都要在两个hash表上进行, 操作只会添加到新hash表上,保证旧的hash表节点数量只减不增。

参考:

压缩列表——Redis设计与实现

Redis 为什么用跳表而不用平衡树?

跳表──没听过但很犀利的数据结构

Redis内部数据结构详解(4)——sds

Redis内部数据结构详解(4)——ziplist

Redis内部数据结构详解(5)——quicklist


转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 using1174@foxmail.com

文章标题: Redis内部数据详解

文章字数: 641

本文作者: Jun

发布时间: 2019-12-18, 11:40:00

最后更新: 2019-12-18, 17:49:41

原始链接: http://yoursite.com/2019/12/18/Redis内部数据详解/

版权声明: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

目录
×

喜欢就点赞,疼爱就打赏