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

前言

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会根据插入的值判断是否扩容，根据插入内容来修改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很像。

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