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表节点数量只减不增。
参考:
转载请注明来源,欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 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" 转载请保留原文链接及作者。