Redis data structure type example code analysis

intset

When the set collection stores integers, the encoding is intset type (small integer collection)

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

##FieldDescriptionDescriptionencodingDetermines whether the integer bit width is 16 bits, 32 bits or 64 bitsEnumeration representation lengthNumber of elements##contentsintset saves elements in order from small to large. When storing elements, decide whether to upgrade the encoding based on the size of the integer, find the position where the element is to be inserted, if it is not the last position, move the element after the position one position, and finally insert the element. If the inserted element is not an integer, the storage form will become a hash structure.

Integer array, storing element values ​​

ziplist

If the following conditions are met in the configuration file, the encoding type of hash and zset will be ziplist (compressed list).

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

##FieldDescriptionDescriptionzlbytes Number of bytes occupied by ziplistThe offset of the last element from the starting position of the compressed listNumber of elementsCompressed elementsMarks the end of the compressed list HengweiFF##Field

		##zltail_offset
Used to quickly locate the last node, and then traverse in reverse order		zllength
		entries
		##zlend

DescriptionDescriptionThe first entry is always 0, and the byte length changes dynamically. When the string length is less than 254 When, use one byte, otherwise use five bytesThe encoding type changes dynamically according to the element content, which is extremely complex , this article will not describe in detail, you can search for the ziplist encoding type

下图是一个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;
}

	prevlen	The byte length of the previous entry
	encoding	Encoding type
	content	element content, optional

字段	描述	说明
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 <= oldcount，则不做任何处理

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

The above is the detailed content of Redis data structure type example code analysis. For more information, please follow other related articles on the PHP Chinese website!