三.Redis中那些你不知道的秘密-五大基本结构set的实现原理

本文涉及的产品
Redis 开源版,标准版 2GB
推荐场景:
搭建游戏排行榜
云数据库 Tair(兼容Redis),内存型 2GB
简介: Redis中的set和java中的set集合有相似之处,它的元素不会按照插入的向后顺序而存储,且元素是不允许重复的。set内部使用到了intset(整数集合)和hashtable(哈希表)两种方式来存储元素,如果set存储的元素是整数,且当元素个数小于512个会选择intset存储,目的是减少内存空间,遇到两种情况会发生变化,就是当存储的元素个数达到512(通过set-max-intset-entries 配置)或者添加了非整数值时如:‘b’,set会选择hashtable作为存储结构。

前言

Redis中的set和java中的set集合有相似之处,它的元素不会按照插入的向后顺序而存储,且元素是不允许重复的。set内部使用到了intset(整数集合)和hashtable(哈希表)两种方式来存储元素,如果set存储的元素是整数,且当元素个数小于512个会选择intset存储,目的是减少内存空间,遇到两种情况会发生变化,就是当存储的元素个数达到512(通过set-max-intset-entries 配置)或者添加了非整数值时如:‘b’,set会选择hashtable作为存储结构。
在这里插入图片描述

整数集合intset

整数集合intset是用来存储整数的集合,且存储是按照小到大的顺序来存储(可以二分查找),intset目的是用来节省内存,当Redis集合类型的元素都是整数并且都处在64位有符号整数范围之内时,使用该结构体存储,我们看一下它的结构:查看源码

typedef struct intset{
   
   
    //编码类型
    uint32_t encoding;
    //集合元素数量
    uint32_t length;
    //存储元素的数组
    int8_t contents[];
} intset;

//下面是相关函数
intset *intsetNew(void);
intset *intsetAdd(intset *is, int64_t value, uint8_t *success);
intset *intsetRemove(intset *is, int64_t value, int *success);
uint8_t intsetFind(intset *is, int64_t value);
int64_t intsetRandom(intset *is);
uint8_t intsetGet(intset *is, uint32_t pos, int64_t *value);
uint32_t intsetLen(const intset *is);
size_t intsetBlobLen(intset *is);
int intsetValidateIntegrity(const unsigned char *is, size_t size, int deep);

在这里插入图片描述

解释:

  • length: contents中元素的个数
  • contents:存储元素的数组,需要根据encoding来决定多少个字节表示一个元素

  • encoding: 编码类型,决定每个元素占用几个字节,有三种类型

编码
INTSET_ENC_INT16 该方式每个元素占2个字节,存储 -32768 到 32767
INTSET_ENC_INT32 该方式每个元素占4个字节,存储 32767到2147483647 或 -2147483647 到 -32768
INTSET_ENC_INT64 该方式每个元素占8个字节,存储 2147483647 到 922337203684775807 或 -922337203684775808 到 -2147483648

intset会根据插入的值判断是否扩容,根据插入内容来修改encoding使用什么类型,从而决定contents每个元素的字节数,紧跟着对contents进行扩容。

intset的升级

假如我们添加这样的数据 sadd 1 2 3 ,底层会执行intsetAdd函数,它会选择INTSET_ENC_INT16类型 去存储,且按照元素大小顺序,它在intset中的结构是这样的
在这里插入图片描述
如果我们再执行 sadd 32999 会发生什么?32999是超过了INTSET_ENC_INT16 类型的存储大小,如果硬塞进去就会内存溢出。所以为了防止内存溢出,intset在添加新元素的时候会先判断是直接插入新元素还是先扩容过后再插入新元素,扩容流程如下:

  • 判断新元素的编码类型是否大于以后元素的编码类型,如果大于就进行扩容
  • 根据新元素的编码类型,为contents的存储空间扩容,同时为新元素分配空间
  • 将所有元素都转换成和新元素相同的编码类型,并调整元素存储位置,且要保证底层数组的有序性质不变
  • 将新元素添加到contents中

intset升级源码如下:

/* Upgrades the intset to a larger encoding and inserts the given integer. */
static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
   
   
    uint8_t curenc = intrev32ifbe(is->encoding);
    uint8_t newenc = _intsetValueEncoding(value);
    int length = intrev32ifbe(is->length);
    / * 判断新插入的值是小于 0 就插首部,否则插尾部 */
    int prepend = value < 0 ? 1 : 0;

    / *首先设置新的编码并调整大小* /
    /* First set new encoding and resize */
    is->encoding = intrev32ifbe(newenc);
    is = intsetResize(is,intrev32ifbe(is->length)+1);
    / * 从最后一个往前扩容,否则会发生制的覆盖 */
    /* Upgrade back-to-front so we don't overwrite values.
     * Note that the "prepend" variable is used to make sure we have an empty
     * space at either the beginning or the end of the intset. */
    while(length--)
        _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    / *如果插入的值小于 0 ,则插头部,否则插入尾部。* /
    /* Set the value at the beginning or the end. */
    if (prepend)
        _intsetSet(is,0,value);
    else
        _intsetSet(is,intrev32ifbe(is->length),value);

    / *修改intset的长度,将其加1 */
    is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
    return is;
}

流程图如下:
在这里插入图片描述

上面案例升级之后的效果如下:
在这里插入图片描述

这样设计的目的就是为了节约内存,通常情况下当我们存储的元素在 -32768 到 32767之间,就使用更小的存储空间,INT16,当插入元素超过该范围就升级更大的内存空间去存储,我们可以任意的存储INT16,INT32,INT64类型的整数不用担心内存问题。

需要注意的是:intset是没有降级的概念,一旦存储了INT32类型的元素那么数组的元素一直都是INT32类型了。

set的添加流程

下面来分析一下添加的详细流程: 见Set源码

void saddCommand(redisClient *c) {
   
   
    robj *set;
    int j, added = 0;

    set = lookupKeyWrite(c->db,c->argv[1]);

    / *如果set是空的就创建一个set*/
    if (set == NULL) {
   
   
        set = setTypeCreate(c->argv[2]);
        dbAdd(c->db,c->argv[1],set);
    } else {
   
   
        if (set->type != REDIS_SET) {
   
   
            addReply(c,shared.wrongtypeerr);
            return;
        }
    }

    / *将元素添加到集合中*/
    for (j = 2; j < c->argc; j++) {
   
   
        c->argv[j] = tryObjectEncoding(c->argv[j]);
        / *setTypeAdd中会进行编码转化 */
        if (setTypeAdd(set,c->argv[j])) added++;
    }

    // 如果有添加成功
    if (added) {
   
   
        // 发送键修改信号
        signalModifiedKey(c->db,c->argv[1]);
        // 发送事件
        notifyKeyspaceEvent(REDIS_NOTIFY_SET,"sadd",c->argv[1],c->db->id);
    }

    // 将数据库设为dirty
    server.dirty += added;

    // 返回添加数量
    addReplyLongLong(c,added);
}

这里添加操作会判断set是否是空的,空的就创建一个set,然后执行setTypeAdd把元素依次添加到集合中,接着看setTypeAdd方法的源码

int setTypeAdd(robj *subject, robj *value) {
   
   
    long long llval;

    / * 这里判断编码,是选择 HT (hash)存储还是选择 intset */
    if (subject->encoding == REDIS_ENCODING_HT) {
   
   
        / * 将 value 作为键值为 NULL,把元素元素存储到字典中*/
        if (dictAdd(subject->ptr,value,NULL) == DICT_OK) {
   
   
            incrRefCount(value);
            return 1;
        }

    / * 这里判断encoding 是否为intset,如果是整数就可以 */
    } else if (subject->encoding == REDIS_ENCODING_INTSET) {
   
   

        / *  判断对象的值可以编码为整数,使用 intset存储 ,否则使用hash*/
        if (isObjectRepresentableAsLongLong(value,&llval) == REDIS_OK) {
   
   
            uint8_t success = 0;
            subject->ptr = intsetAdd(subject->ptr,llval,&success);
            if (success) {
   
   
                / *添加成功 ,这里在判断长度是否大于 512 ,大于就进行转换成hash*/
                / *  REDIS_SET_MAX_INTSET_ENTRIES 默认 512 */
                if (intsetLen(subject->ptr) > server.set_max_intset_entries)
                    setTypeConvert(subject,REDIS_ENCODING_HT);
                return 1;
            }

        / * 如果对象的值不能编码为整数,转换为 HT 编码 然后再执行添加操作*/
        } else {
   
   
            setTypeConvert(subject,REDIS_ENCODING_HT);

            redisAssertWithInfo(NULL,value,dictAdd(subject->ptr,value,NULL) == DICT_OK);
            incrRefCount(value);
            return 1;
        }

    / *编码错误* /
    } else {
   
   
        redisPanic("Unknown set encoding");
    }

    / *添加失败,元素已经存在* / 
    return 0;
}

setTypeAdd的流程是这样的

  • 首先判断对象的编码是否是REDIS_ENCODING_HT,是就走字典存储(hashtable)
  • 否则就判断如果编码是REDIS_ENCODING_INTSET,如果能转码成INTSET就使用INTSET场次,然后再判断保存的长度是否达到512,达到就转换成字典存储(hashtable)
  • 其他情况都用hashtable存储,当然如果对象的编码即不是REDIS_ENCODING_HT也不是REDIS_ENCODING_INTSET就做编码未知处理

总结

  • Redis的set用到了intset和hashtable两种结构,当元素是整数且少于512个就使用intset来存储,否则采用hashtable来存储。

  • intset是为了节约内存的设计,针对于不同范围的数据设定了INTSET_ENC_INT16(2字节),INTSET_ENC_INT32(4字节),INTSET_ENC_INT64(8字节)三种编码方式,如果存储元素过大会进行intset升级,从而扩充存储空间。

  • set在添加元素的时候会做一些判断,如果元素是整数,能转码成REDIS_ENCODING_INTSET就采用intset存储,当然如果存储的元素超过512就转换成hash存储,以value作为键,值为null存储到hash,和JDK里面的HashSet很像。

文章结束,希望对你有数帮助,喜欢的话别忘了给个好评

相关实践学习
基于Redis实现在线游戏积分排行榜
本场景将介绍如何基于Redis数据库实现在线游戏中的游戏玩家积分排行榜功能。
云数据库 Redis 版使用教程
云数据库Redis版是兼容Redis协议标准的、提供持久化的内存数据库服务,基于高可靠双机热备架构及可无缝扩展的集群架构,满足高读写性能场景及容量需弹性变配的业务需求。 产品详情:https://www.aliyun.com/product/kvstore &nbsp; &nbsp; ------------------------------------------------------------------------- 阿里云数据库体验:数据库上云实战 开发者云会免费提供一台带自建MySQL的源数据库&nbsp;ECS 实例和一台目标数据库&nbsp;RDS实例。跟着指引,您可以一步步实现将ECS自建数据库迁移到目标数据库RDS。 点击下方链接,领取免费ECS&amp;RDS资源,30分钟完成数据库上云实战!https://developer.aliyun.com/adc/scenario/51eefbd1894e42f6bb9acacadd3f9121?spm=a2c6h.13788135.J_3257954370.9.4ba85f24utseFl
相关文章
|
9天前
|
存储 NoSQL 关系型数据库
Redis 集合(Set)
10月更文挑战第17天
23 5
|
12天前
|
存储 算法 Java
解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用
在Java中,Set接口以其独特的“无重复”特性脱颖而出。本文通过解析HashSet的工作原理,揭示Set如何利用哈希算法和equals()方法确保元素唯一性,并通过示例代码展示了其“无重复”特性的具体应用。
30 3
|
7天前
|
存储 NoSQL 定位技术
Redis geo原理
Redis的GEO功能基于Earth Mapper(http://earth-api.org/)库,它允许存储地理位置信息并执行一些基于该信息的操作。
18 3
|
9天前
|
存储 NoSQL 关系型数据库
Redis 有序集合(sorted set)
10月更文挑战第17天
25 4
|
22天前
|
存储 分布式计算 NoSQL
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
大数据-40 Redis 类型集合 string list set sorted hash 指令列表 执行结果 附截图
23 3
|
22天前
|
设计模式 NoSQL 网络协议
大数据-48 Redis 通信协议原理RESP 事件处理机制原理 文件事件 时间事件 Reactor多路复用
大数据-48 Redis 通信协议原理RESP 事件处理机制原理 文件事件 时间事件 Reactor多路复用
34 2
|
22天前
|
存储 缓存 NoSQL
大数据-46 Redis 持久化 RDB AOF 配置参数 混合模式 具体原理 触发方式 优点与缺点
大数据-46 Redis 持久化 RDB AOF 配置参数 混合模式 具体原理 触发方式 优点与缺点
54 1
|
27天前
|
NoSQL 关系型数据库 MySQL
Redis 事务特性、原理、具体命令操作全方位诠释 —— 零基础可学习
本文全面阐述了Redis事务的特性、原理、具体命令操作,指出Redis事务具有原子性但不保证一致性、持久性和隔离性,并解释了Redis事务的适用场景和WATCH命令的乐观锁机制。
139 0
Redis 事务特性、原理、具体命令操作全方位诠释 —— 零基础可学习
|
2月前
|
存储 NoSQL Redis
6)深度解密 Redis 的集合(Set)
6)深度解密 Redis 的集合(Set)
46 1
|
22天前
|
消息中间件 NoSQL Kafka
大数据-116 - Flink DataStream Sink 原理、概念、常见Sink类型 配置与使用 附带案例1:消费Kafka写到Redis
大数据-116 - Flink DataStream Sink 原理、概念、常见Sink类型 配置与使用 附带案例1:消费Kafka写到Redis
86 0