亲宝软件园·资讯

展开

Redis数据结构类型示例解析

yunmengmeng 人气:0

intset

当set集合存储的是整数时,encoding为intset类型(小整数集合)

typedef struct intset {
    int32 encoding;
    int32 length;
    int contents[];
}
字段描述说明
encoding决定整数位宽是16位、32位还是64位枚举表示
length元素个数
contents整数数组,存储元素值

intset按照从小到大的顺序保存元素。存储元素时,根据整数大小决定是否要将encoding升级,找到要插入元素的位置,如果不是最后一位,会将所在位置之后的元素后移一位,最后插入元素。如果插入的元素不为整数,存储形式将变成hash结构。

ziplist

当hash与zset满足如下条件条件时,编码类型为ziplist(压缩列表),具体可在配置文件中查看。

hash-max-ziplist-entries 512 # 当hash元素个数小于512时
hash-max-ziplist-value 64 # 当hash键或值长度小于64时
zset-max-ziplist-entries 128 # 当zset元素个数小于128时
zset-max-ziplist-value 64 # 当zset值小于64时
typedef struct ziplist {
    int32 zlbytes;
    int32 zltail_offset;
    int16 zllength;
    T[] entries;
    int8 zlend;
}
typedef struct entry {
    int<var> prevlen;
    int<var> encoding;
    byte[] content;
}
字段描述说明
zlbytesziplist所占字节数
zltail_offset最后一个元素距离压缩列表起始位置的偏移量用于快速定位到最后一个节点,然后倒序遍历
zllength元素个数
entries压缩元素
zlend标志压缩列表的结束恒为FF
字段描述说明
prevlen前一个entry的字节长度第一个entry恒为0,字节长度动态变化,当字符串长度小于254时,用一个字节,否则用五个字节
encoding编码类型编码类型根据元素内容动态变化,极为复杂,本篇不作详细描述,具体可搜索ziplist编码类型
content元素内容,可选

下图是一个ziplist的demo

当用ziplist存储hash结构时,将key与value分别当作一个entry存储。

可见压缩列表存储非常的紧凑,当某一个entry长度变为254时,下一个entry的prevlen将从1个字节扩展到5个字节,这就是级联更新

quicklist

quicklist(快速列表)用于存储list集合,它是ziplist与linkedlist的混合体,linkedlist与双向列表结构类似

quicklist内部默认单个ziplist长度为8K,超过这个长度,就会另起一个node,可在配置文件中配置。

# -2表示8k,枚举类型可在配置文件中查看
list-max-ziplist-size -2

quicklist默认的压缩深度为0,也就是不压缩。如果压缩深度为1,那么就是首尾不压缩,如果压缩深度为2,那么就是首2个、尾2个不压缩,可在配置文件中配置。

list-compress-depth 0

skiplist

zset使用dict存储value与score的映射,另一方面还需要按照score提供排序功能,于是就有了skiplist(跳跃列表)

先看skiplist的一个demo

typedef struct zsl {
    zslnode* header;
    zslnode* tail;
    int maxLevel;
}
typedef struct zslnode {
    sds value;
    double score;
    zslforward*[] forwards;
    zslnode* backward;
}
typedef struct zslforward {
    zslnode* item;
    int span;
}
字段描述说明
header指向跳跃列表的头指针value固定为NULL,score固定为0,backward为null
tail指向跳跃列表的尾指针
maxLevel当前跳跃表最大层数最大为64
value用于存储字符串类型的数据
score用于存储分值
backward回退节点图中的←箭头
forwards前进节点图中的→箭头,每一层对应一个
span跨度,存储一个节点跳到下一个节点中间跳过了多少节点如score1指向score5,则span值为4,这是排名的实现原理

最小分值的backward固定null,对于每一个新插入的节点,会调用一个随机算法,来给它分配一个合理的层数

level1的概率为1-0.25=0.75,实际为100%,因为跳跃列表的最小层数为1

level2的概率为0.75*0.25=0.1875level3的概率为0.1875*0.25=0.0468 ......

leveln的概率为(1-0.25)*Math.pow(0.25,n-1)

总结

Redis作为单线程内存服务,在响应、数据结构上作出了很多的优化,值得我们学习

对象类型编码类型
stringint、raw、embstr
listquicklist
hashdict、ziplist
setintset、dict
zsetziplist、skiplist+dict

HyperLogLog

HyperLogLog的原理为伯努利试验,即丢硬币,根据连续出现反面的次数X,推算出一共丢了2的X次方次硬币,当X很大时,推算出来的总数与实际总数误差就很接近了。具体可查询其他文章。

pfadd

element经过hash算法之后是一个64位的固定值

低14位为桶

查找高50位第一个为1的位数,如果大于当前桶的位数,就将其设置为当前桶的位数

假设hash值是 :{此处省略45位}01100 00000000000101

HyperLogLog用了16384个桶,每个桶占用6bit,因此说一个HyperLogLog所占用内存是12K。

调和平均数:

假设我的工资为10_000,马云的工资为1_000_000,那我和马云的平均工资为505_000,我肯定是不认同的。。。

如果使用调和平均数,则为2/(1/10_000+1/1_000_000)=19_801

同理,桶位数的平均数为:n/(1/桶1位数+1/桶2位数+...+1/桶n位数)

桶的平均个数为:Math.pow(2,桶位数的平均数)

总数量:const*桶总数n*桶的平均个数,其中constant为不定值,与桶个数有关,假设m为桶个数,取对数

pfcount

p=log2m
switch (p) {
   case 4:
       constant = 0.673 * m * m;
   case 5:
       constant = 0.697 * m * m;
   case 6:
       constant = 0.709 * m * m;
   default:
       constant = (0.7213 / (1 + 1.079 / m)) * m * m;
}

加载全部内容

相关教程
猜你喜欢
用户评论