Nicksxs's Blog

What hurts more, the pain of hard work or the pain of regret?

0%

redis数据结构介绍三-第三部分 整数集合

redis中对于 set 其实有两种处理,对于元素均为整型,并且元素数目较少时,使用 intset 作为底层数据结构,否则使用 dict 作为底层数据结构,先看一下代码先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct intset {
// 编码方式
uint32_t encoding;
// 集合包含的元素数量
uint32_t length;
// 保存元素的数组
int8_t contents[];
} intset;

/* Note that these encodings are ordered, so:
* INTSET_ENC_INT16 < INTSET_ENC_INT32 < INTSET_ENC_INT64. */
#define INTSET_ENC_INT16 (sizeof(int16_t))
#define INTSET_ENC_INT32 (sizeof(int32_t))
#define INTSET_ENC_INT64 (sizeof(int64_t))

一眼看,为啥整型还需要编码,然后 int8_t 怎么能存下大整形呢,带着这些疑问,我们一步步分析下去,这里的编码其实指的是这个整型集合里存的究竟是多大的整型,16 位,还是 32 位,还是 64 位,结构体下面的宏定义就是表示了 encoding 的可能取值,INTSET_ENC_INT16 表示每个元素用2个字节存储,INTSET_ENC_INT32 表示每个元素用4个字节存储,INTSET_ENC_INT64 表示每个元素用8个字节存储。因此,intset中存储的整数最多只能占用64bit。length 就是正常的表示集合中元素的数量。最奇怪的应该就是这个 contents 了,是个 int8_t 的数组,那放毛线数据啊,最小的都有 16 位,这里我在看代码和《redis 设计与实现》的时候也有点懵逼,后来查了下发现这是个比较取巧的用法,这里我用自己的理解表述一下,先看看 8,16,32,64 的关系,一眼看就知道都是 2 的 N 次,并且呈两倍关系,而且 8 位刚好一个字节,所以呢其实这里的contents 不是个常规意义上的 int8_t 类型的数组,而是个柔性数组。看下 wiki 的定义

Flexible array members1 were introduced in the C99 standard of the C programming language (in particular, in section §6.7.2.1, item 16, page 103).2 It is a member of a struct, which is an array without a given dimension. It must be the last member of such a struct and it must be accompanied by at least one other member, as in the following example:

1
2
3
4
struct vectord {
size_t len;
double arr[]; // the flexible array member must be last
};

在初始化这个 intset 的时候,这个contents数组是不占用空间的,后面的反正用到了申请,那么这里就有一个问题,给出了三种可能的 encoding 值,他们能随便换吗,显然不行,首先在 intset 中数据的存放是有序的,这个有部分原因是方便二分查找,然后存放数据其实随着数据的大小不同会有一个升级的过程,看下图

新创建的intset只有一个header,总共8个字节。其中encoding = 2, length = 0, 类型都是uint32_t,各占 4 字节,添加15, 5两个元素之后,因为它们是比较小的整数,都能使用2个字节表示,所以encoding不变,值还是2,也就是默认的 INTSET_ENC_INT16,当添加32768的时候,它不再能用2个字节来表示了(2个字节能表达的数据范围是-215~215-1,而32768等于215,超出范围了),因此encoding必须升级到INTSET_ENC_INT32(值为4),即用4个字节表示一个元素。在添加每个元素的过程中,intset始终保持从小到大有序。与ziplist类似,intset也是按小端(little endian)模式存储的(参见维基百科词条Endianness)。比如,在上图中intset添加完所有数据之后,表示encoding字段的4个字节应该解释成0x00000004,而第4个数据应该解释成0x00008000 = 32768

请我喝杯咖啡