Redis 데이터 구조 유형 예제 코드 분석

intset

집합 컬렉션이 정수를 저장하는 경우 인코딩은 intset 유형(작은 정수 컬렉션)입니다.

typedef struct intset {
    int32 encoding;
    int32 length;
    int contents[];
}

을 나타냅니다.

Field	Description	Explanation
encoding	정수 비트 너비를 16비트로 결정 , 32비트 또는 64비트	열거형은
길이	요소 수
contents	정수 배열, 요소 값 저장

intset은 다음에서 정렬됩니다. 작은 것에서 큰 것 순서대로 요소를 저장합니다. 요소를 저장할 때 정수 크기를 기준으로 인코딩 업그레이드 여부를 결정하고 요소가 삽입될 위치를 찾아 마지막 위치가 아니면 해당 위치 이후의 요소를 한 위치 이동한 후 마지막으로 삽입한다. 요소. 삽입된 요소가 정수가 아닌 경우 저장 형식은 해시 구조가 됩니다.

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;
}

zlend 표시 압축된 목록의 끝 항상 FFprevlen첫 번째 항목은 항상 0 및 바이트 문자열 길이가 254보다 작으면 1바이트를 사용하고, 그렇지 않으면 5바이트를 사용합니다.encodingencoding type

field	description	description
zlbytes	ziplist가 차지하는 바이트 수
zltail_offset	압축된 목록의 시작 위치에서 마지막 요소의 오프셋	마지막 노드를 빠르게 찾은 다음 역순으로 탐색하는 데 사용됩니다.
Field	Description	Explanation

요소의 내용에 따라 인코딩 유형이 동적으로 변경됩니다. 이 글에서는 자세히 설명하지 않습니다. ziplist 인코딩 유형content 요소 콘텐츠, 선택사항

에서 검색할 수 있습니다.

下图是一个ziplist的demo

• 第1-4字节，zlbytes为25，说明该压缩列表共占用25个字节

• 第5-8字节，zltail_offset为22，说明最后一个元素从22开始

• 第9-10字节，zllength为3，说明共有3个元素

• 第11-16字节，第一个entry: 其中prevlen=0，因为它前面没有数据项；encoding=4，表示后面4byte按照字符串存储，数据的值为name

• 第17-21字节，第二个entry: 其中prevlen=6，表示前一个entry共占用6byte；encoding=3，表示后面3byte按照字符串存储，数据的值为why

• 第22-24字节，第三个entry: 其中prevlen=5，表示前一个entry共占用5byte；encoding=0xFE，表示后面1byte存储整数，数据的值为14

• 第25字节，zlend为FF，标志压缩列表的结束

当用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作为单线程内存服务，在响应、数据结构上作出了很多的优化，值得我们学习

对象类型	编码类型
string	int、raw、embstr
list	quicklist
hash	dict、ziplist
set	intset、dict
zset	ziplist、skiplist+dict

HyperLogLog

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

pfadd

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

低14位为桶

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

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

• 低14位的二进制转为10进制，值为5（regnum），即我们把数据放在第5个桶

• 高50位第一个1的位置是3，即count值为3

• registers[5]取出历史值oldcount

• 如果count > oldcount，则更新 registers[5] = count

• 如果count

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;
}

위 내용은 Redis 데이터 구조 유형 예제 코드 분석의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!