发表文章

[最新] redis五大类型内存评估

qq35433716 2月前 1

关于Redis内部编码的转换,都符合以下规律:编码转换在Redis写入数据时完成,且转换过程不可逆,只能从小内存编码向大内存编码转换。

1、字符串

(1)概况

字符串是最基础的类型,因为所有的键都是字符串类型,且字符串之外的其他几种复杂类型的元素也是字符串。
字符串长度不能超过512MB。

(2)内部编码

字符串类型的内部编码有3种,它们的应用场景如下:
int:8个字节的长整型。字符串值是整型时,这个值使用long整型表示。
embstr:<=39字节的字符串。embstr与raw都使用redisObject和sds保存数据,区别在于,embstr的使用只分配一次内存空间(因此redisObject和sds是连续的),而raw需要分配两次内存空间(分别为redisObject和sds分配空间)。因此与raw相比,embstr的好处在于创建时少分配一次空间,删除时少释放一次空间,以及对象的所有数据连在一起,寻找方便。而embstr的坏处也很明显,如果字符串的长度增加需要重新分配内存时,整个redisObject和sds都需要重新分配空间,因此redis中的embstr实现为只读。
raw:大于39个字节的字符串
embstr和raw进行区分的长度,是39;是因为redisObject的长度是16字节,sds的长度是9+字符串长度;因此当字符串长度是39时,embstr的长度正好是16+9+39=64,jemalloc正好可以分配64字节的内存单元。

这里写图片描述

(3)编码转换
当int数据不再是整数,或大小超过了long的范围时,自动转化为raw。
而对于embstr,由于其实现是只读的,因此在对embstr对象进行修改时,都会先转化为raw再进行修改,因此,只要是修改embstr对象,修改后的对象一定是raw的,无论是否达到了39个字节。示例如下图所示:
这里写图片描述

2、列表

(1)概况

列表(list)用来存储多个有序的字符串,每个字符串称为元素;一个列表可以存储2^32-1个元素。Redis中的列表支持两端插入和弹出,并可以获得指定位置(或范围)的元素,可以充当数组、队列、栈等。

(2)内部编码

列表的内部编码可以是压缩列表(ziplist)或双端链表(linkedlist)。
双端链表:由一个list结构和多个listNode结构组成;典型结构如下图所示:
这里写图片描述
通过图中可以看出,双端链表同时保存了表头指针和表尾指针,并且每个节点都有指向前和指向后的指针;链表中保存了列表的长度;dup、free和match为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。而链表中每个节点指向的是type为字符串的redisObject。
压缩列表:压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构;具体结构相对比较复杂,略。与双端链表相比,压缩列表可以节省内存空间,但是进行修改或增删操作时,复杂度较高;因此当节点数量较少时,可以使用压缩列表;但是节点数量多时,还是使用双端链表划算。

(3)编码转换

只有同时满足下面两个条件时,才会使用压缩列表:列表中元素数量小于512个;列表中所有字符串对象都不足64字节。如果有一个条件不满足,则使用双端列表;且编码只可能由压缩列表转化为双端链表,反方向则不可能。
下图展示了列表编码转换的特点:
这里写图片描述
其中,单个字符串不能超过64字节,是为了便于统一分配每个节点的长度;这里的64字节是指字符串的长度,不包括SDS结构,因为压缩列表使用连续、定长内存块存储字符串,不需要SDS结构指明长度。后面提到压缩列表,也会强调长度不超过64字节,原理与这里类似。

3、哈希

(1)概况

哈希(作为一种数据结构),不仅是redis对外提供的5种对象类型的一种(与字符串、列表、集合、有序结合并列),也是Redis作为Key-Value数据库所使用的数据结构。为了说明的方便,在本文后面当使用“内层的哈希”时,代表的是redis对外提供的5种对象类型的一种;使用“外层的哈希”代指Redis作为Key-Value数据库所使用的数据结构。

(2)内部编码

内层的哈希使用的内部编码可以是压缩列表(ziplist)和哈希表(hashtable)两种;Redis的外层的哈希则只使用了hashtable。

压缩列表前面已介绍。与哈希表相比,压缩列表用于元素个数少、元素长度小的场景;其优势在于集中存储,节省空间;同时,虽然对于元素的操作复杂度也由O(n)变为了O(1),但由于哈希中元素数量较少,因此操作的时间并没有明显劣势。
hashtable:一个hashtable由1个dict结构、2个dictht结构、1个dictEntry指针数组(称为bucket)和多个dictEntry结构组成。

这里写图片描述

dictEntry

dictEntry结构用于保存键值对,结构定义如下:

typedef struct dictEntry{
        void *key;
        union{
            void *val;
            uint64_tu64;
            int64_ts64;
        }v;
        struct dictEntry *next;
    }dictEntry;

其中,各个属性的功能如下:
key:键值对中的键;
val:键值对中的值,使用union(即共用体)实现,存储的内容既可能是一个指向值的指针,也可能是64位整型,或无符号64位整型;
next:指向下一个dictEntry,用于解决哈希冲突问题
在64位系统中,一个dictEntry对象占24字节(key/val/next各占8字节)

bucket

bucket是一个数组,数组的每个元素都是指向dictEntry结构的指针。redis中bucket数组的大小计算规则如下:大于dictEntry的、最小的2^n;例如,如果有1000个dictEntry,那么bucket大小为1024;如果有1500个dictEntry,则bucket大小为2048。

dictht

dictht结构如下:

typedef struct dictht{
        dictEntry **table;
        unsigned long size;
        unsigned long sizemask;
        unsigned long used;
    }dictht;

其中,各个属性的功能说明如下:
table属性是一个指针,指向bucket;
size属性记录了哈希表的大小,即bucket的大小;
used记录了已使用的dictEntry的数量;
sizemask属性的值总是为size-1,这个属性和哈希值一起决定一个键在table中存储的位置。
dict
一般来说,通过使用dictht和dictEntry结构,便可以实现普通哈希表的功能;但是Redis的实现中,在dictht结构的上层,还有一个dict结构。下面说明dict结构的定义及作用。
dict结构如下:

typedef struct dict{
        dictType *type;
        void *privdata;
        dictht ht[2];
        int trehashidx;
    } dict;

其中,type属性和privdata属性是为了适应不同类型的键值对,用于创建多态字典。
ht属性和trehashidx属性则用于rehash,即当哈希表需要扩展或收缩时使用。ht是一个包含两个项的数组,每项都指向一个dictht结构,这也是Redis的哈希会有1个dict、2个dictht结构的原因。通常情况下,所有的数据都是存在放dict的ht[0]中,ht[1]只在rehash的时候使用。dict进行rehash操作的时候,将ht[0]中的所有数据rehash到ht[1]中。然后将ht[1]赋值给ht[0],并清空ht[1]。
因此,Redis中的哈希之所以在dictht和dictEntry结构之外还有一个dict结构,一方面是为了适应不同类型的键值对,另一方面是为了rehash。

(3)编码转换

如前所述,Redis中内层的哈希既可能使用哈希表,也可能使用压缩列表。
只有同时满足下面两个条件时,才会使用压缩列表:哈希中元素数量小于512个;哈希中所有键值对的键和值字符串长度都小于64字节。如果有一个条件不满足,则使用哈希表;且编码只可能由压缩列表转化为哈希表,反方向则不可能。

下图展示了Redis内层的哈希编码转换的特点:
这里写图片描述

4、集合

(1)概况
集合(set)与列表类似,都是用来保存多个字符串,但集合与列表有两点不同:集合中的元素是无序的,因此不能通过索引来操作元素;集合中的元素不能有重复。
一个集合中最多可以存储2^32-1个元素;除了支持常规的增删改查,Redis还支持多个集合取交集、并集、差集。

2)内部编码
集合的内部编码可以是整数集合(intset)或哈希表(hashtable)。
哈希表前面已经讲过,这里略过不提;需要注意的是,集合在使用哈希表时,值全部被置为null。
整数集合的结构定义如下:

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

其中,encoding代表contents中存储内容的类型,虽然contents(存储集合中的元素)是int8_t类型,但实际上其存储的值是int16_t、int32_t或int64_t,具体的类型便是由encoding决定的;length表示元素个数。
整数集合适用于集合所有元素都是整数且集合元素数量较小的时候,与哈希表相比,整数集合的优势在于集中存储,节省空间;同时,虽然对于元素的操作复杂度也由O(n)变为了O(1),但由于集合数量较少,因此操作的时间并没有明显劣势。
(3)编码转换
只有同时满足下面两个条件时,集合才会使用整数集合:集合中元素数量小于512个;集合中所有元素都是整数值。如果有一个条件不满足,则使用哈希表;且编码只可能由整数集合转化为哈希表,反方向则不可能。
下图展示了集合编码转换的特点:

这里写图片描述

有序集合

有序集合与集合一样,元素都不能重复;但与集合不同的是,有序集合中的元素是有顺序的。与列表使用索引下标作为排序依据不同,有序集合为每个元素设置一个分数(score)作为排序依据。
(2)内部编码
有序集合的内部编码可以是压缩列表(ziplist)或跳跃表(skiplist)。ziplist在列表和哈希中都有使用,前面已经讲过,这里略过不提。

跃表是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。除了跳跃表,实现有序数据结构的另一种典型实现是平衡树;大多数情况下,跳跃表的效率可以和平衡树媲美,且跳跃表实现比平衡树简单很多,因此redis中选用跳跃表代替平衡树。跳跃表支持平均O(logN)、最坏O(N)的复杂点进行节点查找,并支持顺序操作。Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成:前者用于保存跳跃表信息(如头结点、尾节点、长度等),后者用于表示跳跃表节点。具体结构相对比较复杂,略。

只有同时满足下面两个条件时,才会使用压缩列表:有序集合中元素数量小于128个;有序集合中所有成员长度都不足64字节。如果有一个条件不满足,则使用跳跃表;且编码只可能由压缩列表转化为跳跃表,反方向则不可能。
下图展示了有序集合编码转换的特点:
这里写图片描述

相关推荐
最新评论 (0)
返回
发表文章
qq35433716
文章数
94
评论数
0
注册排名
1340404