Redis 的底层数据结构10bet

来源:http://www.chinese-glasses.com 作者:Web前端 人气:112 发布时间:2020-04-22
摘要:时间: 2019-09-20阅读: 121标签: 结构         这两天看过《redis设计与实现》中的intset一章,配合着redis4.0.1中的源码,感觉自己对redis中的intset有了新的认识。在这里写下自己对于intset的理

时间: 2019-09-20阅读: 121标签: 结构

        这两天看过《redis设计与实现》中的intset一章,配合着redis 4.0.1中的源码,感觉自己对redis中的intset有了新的认识。在这里写下自己对于intset的理解,以及redis源码中的实现技巧。

当一个集合中只包含整数,并且元素的个数不是很多的话,redis 会用整数集合作为底层存储,它的一个优点就是可以节省很多内存,虽然字典结构的效率很高,但是它的实现结构相对复杂并且会分配较多的内存空间。

        intset作为redis中集合的底层实现之一,当集合中的元素数量不太多且都是整数值的时候,set使用intset作为其底层实现。个人认为,redis中intset的重要部分在于intset对于存储不同类型的整数使用不同的底层数组,巧妙的节约了内存的空间、提供了较高的灵活性。redis源码中对于intset的实现也比较简单,下面对自己在阅读源码的时候,当时不太熟悉的部分做一个简要的摘录。从redis中实现intset的基本数据结构和redis中数据类型的升级两方面进行介绍。

而我们的整数集合(intset)可以做到使用较少的内存空间却达到和字典一样效率的实现,但也是前提的,集合中只能包含整型数据并且数量不能太多。整数集合最多能存多少个元素在 redis 中也是有体现的。

        1、redis中intset数据结构

OBJ_SET_MAX_INTSET_ENTRIES 512

        typedef struct intset {

也就是超过 512 个元素,或者向集合中添加了字符串或其他数据结构,redis 会将整数集合向字典结构进行转换。

                uint32_t encoding;

一、基本的数据结构

                uint32_t length;

intset 的结构定义很简单,有以下成员构成:

                /* 柔性数组 */

typedef struct intset { uint32_t encoding; uint32_t length; int8_t contents [];} intset;

                int8_t contents[];

encoding 记录当前 intset 使用编码,有三个取值:

        } intset;

#define INTSET_ENC_INT16 (sizeof(int16_t))#define INTSET_ENC_INT32 (sizeof(int32_t))#define INTSET_ENC_INT64 (sizeof(int64_t))

        这里对struct intset需要说明的一点是,虽然contents的类型定义的是int8_t,但是其实际存储的数据的类型需要靠encoding指明,encoding的值为contents中存储的最大类型的值的类型。在redis的实现代码中定义了三种类型,分别如下。

length 记录整数集合中目前存储了多少个元素,contents 记录我们实际的数据集合,虽然我们看到结构体中给数组元素的类型定死成 int8_t,但实际上这个 int8_t 定义的毫无意义,因为这里的处理方式非常规的数组操作,content 字段虽然被定义成指向一个 int8_t 类型数据的指针,但实际上 redis 无论是读取数组元素还是新增元素进去都依赖 encoding 和 length 两个字段直接操作的内存。

        #define INTSET_ENC_INT16 (sizeof(int16_t))

基本数据结构还是非常的简单的,下面我们来看看它的一些核心方法。

        #define INTSET_ENC_INT32 (sizeof(int32_t))

二、核心 API 实现

        #define INTSET_ENC_INT64 (sizeof(int64_t))

1、初始化一个 intset

        从上面三种宏定义中可以看出redis为底层的contents提供了三种可选的类型,分别为INTSET_ENC_INT16、INTSET_ENC_INT32和INTSET_ENC_INT64,三种类型的值分别以对应的整数类型的值所占用的字节数。

intset *intsetNew(void) { intset *is = zmalloc(sizeof(intset)); is-encoding = intrev32ifbe(INTSET_ENC_INT16); is-length = 0; return is;}

        2、redis中数据类型的升级

可见,默认的 inset 配置是使用 INTSET_ENC_INT16 作为数据存储大小,并且不会为 content 数组初始化。常规的数组需要先预先确定数组长度,然后分配内存,继而通过 contents[x] 可以访问数组中任一元素。

        首先,创建一个空的redis中的intset集合使用的函数intsetNew中,创建的类型为INTSET_ENC_INT16类型,这种类型在放入的整数处于-32768~32767的时候,都是没有任何问题的。但是,假如要放入一个65535的整数值,那么int16_t类型将会溢出,所以此时intset要执行数据类型的升级操作。

但是,inset 这里是非常规式操作数组,encoding 字段定义了数组中每个元素实际类型,lenth 字段定义了数组中实际的元素个数,那么 contents[x] 是失效的,这种方式只会按照 int8_t 进行内存偏移,这种方式是拿不到正确的数据的,所以 redis 中通过 memcpy 按照 encoding 字段的值暴力直接偏移地址操作内存读取数据。

        在redis中只有执行插入value的时候才会执行升级操作。根据升级操作的条件---当前集合的数据类型无法表示value的大小,因此新插入的value的类型存在两种情况导致了intset的升级。

所以,这也是为什么 intset 初始化时不初始化 content 数组的原因所在,因为没有必要。而每当新增一个元素的时候都会去动态扩容原数组的长度以盛放下新插入进来的元素,扩容不会扩容很多,刚好一个新元素所占用的内存即可。具体的细节,我们接着看。

        ·value小于当前encoding表示的类型能够表示的最小值;

2、添加新元素

        ·value大于当前encoding表示的类型能够表示的最大值;

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) { //计算得到新插入的元素的编码 uint8_t valenc = _intsetValueEncoding(value); uint32_t pos; if (success) *success = 1; //如果大于 intset 目前存储元素的编码大小 if (valenc  intrev32ifbe(is-encoding)) { //触发 intset 升级 return intsetUpgradeAndAdd(is,value); } else { //二分搜索当前元素,如果元素已经存在会直接返回 //如果没找到元素,pos 的值就是该元素的位置索引 if (intsetSearch(is,value,pos)) { if (success) *success = 0; return is; } //resize 集合,扩容一个元素的内存空间 is = intsetResize(is,intrev32ifbe(is-length)+1); //移动 pos 后面的元素,以插入我们的新元素 if (pos  intrev32ifbe(is-length)) intsetMoveTail(is,pos,pos+1); } //赋值 _intsetSet(is,pos,value); is-length = intrev32ifbe(intrev32ifbe(is-length)+1); return is;}

        有且只有以上两种情况才会导致intset的升级操作。那么如果是第一种情况的时候,要插入的value应该处于的位置(pos)应该是contents中下标为0的地方;如果是第二种情况,要插入的value应该位于contents中下标为当前的length的位置上。总之,如果由于插入value导致intset中数据类型的升级,那么value要么位于intset中contents中的最开始的位置,要么位于最后的位置。

由此,我们应该知道为什么 intset 内的数据是有序且无重复的了,二分查找 O(logN),但是 intset 插入一个元素却不是 O(logN),因为有些情况会触发升级操作,或者极端情况下,会移动所有元素,时间复杂度达到 O(N)。

        当然,还需要说明的是,redis不会由于删除元素而降级。比如在上面插入了65535值之后,intset的encoding肯定是INTSET_ENC_INT32。但是,如果删除了65535,intset的encoding不会降级为INTSET_ENC_INT16。

3、升级

        下面,我们看redis中源码是如何实现升级和插入操作的。

我们先看示意图的变化,然后再分析源码,假设原 intset 使用 16 位的编码存储数据,先来了一个 32 位的数据,触发了我们的编码升级。

        static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {

原 intset 结构如下:

                /* 当前编码类型 */

新 intset 结构会扩容成这样:

                uint8_t curenc = intrev32ifbe(is->encoding);

虽然数据占用的内存已经分配好了,但是还需要做的是迁移每个元素占用的比特位。做法是这样的,假设我们的新元素是 int_32 类型的数值 65536,那么首先我们会将这个 65536 放到[128-159]比特位区间,然后将 78 放到[96-127]比特位区间,并向前以此类推,最后我们会得到升级完成之后 intset。

                /* 要转换成的编码类型 */

下面我们看 redis 中代码的实现:

                uint8_t newenc = _intsetValueEncoding(value);

本文由10bet发布于Web前端,转载请注明出处:Redis 的底层数据结构10bet

关键词:

最火资讯