美文网首页redis学习PHP经验分享redis
Redis3.2源码分析-整数集合intset

Redis3.2源码分析-整数集合intset

作者: llinvokerl | 来源:发表于2018-03-21 17:06 被阅读14次

    intset是Redis集合的底层实现之一,当存储整数集合并且数据量较小的情况下Redis会使用intset作为set的底层实现。当数据量较大或者集合元素为字符串时则会使用dict实现set。
    intset将整数元素按顺序存储在数组里,并通过二分法降低查找元素的时间复杂度。数据量大时,依赖于“查找”的命令(如SISMEMBER)就会由于O(logn)的时间复杂度而遇到一定的瓶颈,所以数据量大时会用dict来代替intset。但是intset的优势就在于比dict更省内存,而且数据量小的时候O(logn)未必会慢于O(1)的hash function。这也是intset存在的原因。

    intset结构体声明

    intset的结构体非常简单

    typedef struct intset {
        uint32_t encoding; //intset的类型编码
        uint32_t length; //成员元素的个数
        int8_t contents[];//用来存储成员的柔性数组
    }
    

    需要注意contents数组成员被声明为int8_t类型并不表示contents里存的是int8_t类型的成员,这个类型声明对于contents来说可以认为是毫无意义的,因为intset成员是什么类型完全取决于encoding变量的值。encoding提供下面三种值:

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

    如果intset的encoding为INTSET_ENC_INT16,则contents的每个成员的“逻辑类型”都为int16_t。
    虽然每个成员的“实际类型”是int8_t,无法直接通过contents[x]取出索引为x的成员元素,但是intset.c里提供了些函数,可以按照不同的encoding方式设置/取出contents的成员。(用指针设置,memcpy取出)
    由于这种方法在内存上暴力地赋值与取值,所以希望元素在不同机器上存储的字节序一致,但是不同处理器 在内存中存放数据的方式不一定相同,主要分为大端字节序和小端字节序。快速复习字节序:不论大端小端,内存中数据按照8位(1字节)分割。大端字节序就是高位的字节存放在低地址处;小端字节序就是高位的字节存放在高地址处。举个例子:

    int d = 1415926;
    

    整数d对应的16进制表示是0x159AF6。8个二进制位可以被2个十六进制位表示,所以15、9A、F6各是一个字节,15是高位字节,F6是低位字节。
    大端的处理器在内存中这样存放d:

    而小端的处理器在内存中这样存放d:


    如果老老实实通过contents[x]的方式赋值取值,我们就不需要考虑这个字节序的问题,但是intset根据encoding的值指定元素的地址偏移,暴力地对内存进行操作。若数据被截断了,则大端机器和小端机器会表现出不统一的状况。为了避免这种情况发生,intset不管在什么机器上都按照同一种字节序(小端)在内存中存intset的成员变量。

    /* variants of the function doing the actual convertion only if the target
     * host is big endian */
    #if (BYTE_ORDER == LITTLE_ENDIAN)
    #define memrev16ifbe(p)
    #define memrev32ifbe(p)
    #define memrev64ifbe(p)
    #define intrev16ifbe(v) (v)
    #define intrev32ifbe(v) (v)
    #define intrev64ifbe(v) (v)
    #else
    #define memrev16ifbe(p) memrev16(p)
    #define memrev32ifbe(p) memrev32(p)
    #define memrev64ifbe(p) memrev64(p)
    #define intrev16ifbe(v) intrev16(v)
    #define intrev32ifbe(v) intrev32(v)
    #define intrev64ifbe(v) intrev64(v)
    #endif
    
    //翻转
    void memrev64(void *p) {
        unsigned char *x = p, t;
    
        t = x[0];
        x[0] = x[7];
        x[7] = t;
        t = x[1];
        x[1] = x[6];
        x[6] = t;
        t = x[2];
        x[2] = x[5];
        x[5] = t;
        t = x[3];
        x[3] = x[4];
        x[4] = t;
    }
    uint64_t intrev64(uint64_t v) {
        memrev64(&v);
        return v;
    }
    
    

    intset基本操作

    底层赋值/取值操作

    通过_intsetSet和_intsetGet这两个工具函数,可以根据intset的encoding 读/写contents里索引为pos的值。这是后续intset操作的基础。

    /* Set the value at pos, using the configured encoding. */
    //按照intset的encoding设置指定位置pos的值
    static void _intsetSet(intset *is, int pos, int64_t value) {
        uint32_t encoding = intrev32ifbe(is->encoding);
    
        if (encoding == INTSET_ENC_INT64) {
            ((int64_t*)is->contents)[pos] = value;
            //大端机器在设置contents时将数据按字节翻转,按照小端序存储
            memrev64ifbe(((int64_t*)is->contents)+pos);
        } else if (encoding == INTSET_ENC_INT32) {
            ((int32_t*)is->contents)[pos] = value;
            memrev32ifbe(((int32_t*)is->contents)+pos);
        } else {
            ((int16_t*)is->contents)[pos] = value;
            memrev16ifbe(((int16_t*)is->contents)+pos);
        }
    }
    /* Return the value at pos, using the configured encoding. */
    //按照intset的encoding取出指定位置pos的值
    //不对pos进行越界判断,可能会导致undefined behavior
    static int64_t _intsetGet(intset *is, int pos) {
        return _intsetGetEncoded(is,pos,intrev32ifbe(is->encoding));
    }
    /* Return the value at pos, given an encoding. */
    //以enc为编码取出整数集合is在pos索引上的值
    //不对pos进行越界判断,可能会导致undefined behavior
    static int64_t _intsetGetEncoded(intset *is, int pos, uint8_t enc) {
        int64_t v64;
        int32_t v32;
        int16_t v16;
    
        if (enc == INTSET_ENC_INT64) {
            //将contents在pos位置的值赋给v64
            //不能直接写contents[pos]的原因是contents时int8_t类型的,contents[pos]表示是以sizeof(int8_t)为单位移动的指针,而实际的编码是INTSET_ENC_INT64,先将contents指针的类型变为int64_t*
            memcpy(&v64,((int64_t*)is->contents)+pos,sizeof(v64));
            //大端机器在取出contents时将原本按照小端序存储的数据按字节翻转,读出正确的值
            memrev64ifbe(&v64);
            return v64;
        } else if (enc == INTSET_ENC_INT32) {
            memcpy(&v32,((int32_t*)is->contents)+pos,sizeof(v32));
            memrev32ifbe(&v32);
            return v32;
        } else {
            memcpy(&v16,((int16_t*)is->contents)+pos,sizeof(v16));
            memrev16ifbe(&v16);
            return v16;
        }
    }
    

    创建一个空intset

    空intset的默认encoding是INTSET_ENC_INT16,contents每个成员的逻辑类型是int16_t(虽然还没有成员)

    /* Create an empty intset. */
    intset *intsetNew(void) {
        intset *is = zmalloc(sizeof(intset));
        is->encoding = intrev32ifbe(INTSET_ENC_INT16);
        is->length = 0;
        return is;
    }
    

    查询一个成员

    前面说了intset是将元素按大小顺序存储在contents数组里,所以在插入新元素之前,必须通过二分法找到合理的插入位置,这由intsetSearch(intset *is, int64_t value, uint32_t *pos)函数实现。
    它的作用是在整数集合里用二分法找到value的位置,并把位置写给pos参数,函数返回1;若没找到,则写给pos的是能被插入的value的位置(intset按顺序存储),函数返回0。

    static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
        int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
        int64_t cur = -1;
    
        /* The value can never be found when the set is empty */
        if (intrev32ifbe(is->length) == 0) {
            if (pos) *pos = 0;
            return 0;
        } else {
            /* Check for the case where we know we cannot find the value,
             * but do know the insert position. */
            //判断是否大于小于边界值
            if (value > _intsetGet(is,intrev32ifbe(is->length)-1)) {
                if (pos) *pos = intrev32ifbe(is->length);//value可以被插入的位置
                return 0;
            } else if (value < _intsetGet(is,0)) {
                if (pos) *pos = 0;
                return 0;
            }
        }
    
        //二分
        while(max >= min) {
            mid = ((unsigned int)min + (unsigned int)max) >> 1;
            cur = _intsetGet(is,mid);
            if (value > cur) {
                min = mid+1;
            } else if (value < cur) {
                max = mid-1;
            } else {
                break;
            }
        }
    
        if (value == cur) {
            if (pos) *pos = mid;//找到了
            return 1;
        } else {
            if (pos) *pos = min;
            return 0;
        }
    }
    

    插入一个成员

    插入一个值为value的成员时,会做以下判断逻辑:

    • 计算value的encoding
    • 若value的encoding大于要插入的intset的encoding,则调用intsetUpgradeAndAdd直接升级intset的encoding并插入到首部或者尾部。
    • 若value的encoding小于要插入的intset的encoding,则不需要升级intset的encoding,调用intsetSearch找到合适的插入位置,再将该位置到contents尾部的数据全部右移一格,最后将value插入到pos。

    代码如下

    /* Insert an integer in the intset */
    //success传null进来则说明外层调用者不需要知道是否插入成功(value是否已存在),否则success用于此目的
    intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
        uint8_t valenc = _intsetValueEncoding(value);//根据value的大小计算value的encoding
        uint32_t pos;
        if (success) *success = 1;
    
        /* Upgrade encoding if necessary. If we need to upgrade, we know that
         * this value should be either appended (if > 0) or prepended (if < 0),
         * because it lies outside the range of existing values. */
        if (valenc > intrev32ifbe(is->encoding)) {
            //这种插入需要改变encoding(不需要search,因为encoding改变说明value一定插入在contents首部或者尾部)
            /* This always succeeds, so we don't need to curry *success. */
            return intsetUpgradeAndAdd(is,value);
        } else {
            /* Abort if the value is already present in the set.
             * This call will populate "pos" with the right position to insert
             * the value when it cannot be found. */
            if (intsetSearch(is,value,&pos)) {
                if (success) *success = 0;//intset里已存在该值,返回失败
                return is;
            }
    
            is = intsetResize(is,intrev32ifbe(is->length)+1);
            if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);//右移一格
        }
    
        _intsetSet(is,pos,value);//插入值
        is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
        return is;
    }
    
    /* Return the required encoding for the provided value. */
    //根据v值的大小决定需要的编码类型
    static uint8_t _intsetValueEncoding(int64_t v) {
        if (v < INT32_MIN || v > INT32_MAX)
            return INTSET_ENC_INT64;
        else if (v < INT16_MIN || v > INT16_MAX)
            return INTSET_ENC_INT32;
        else
            return INTSET_ENC_INT16;
    }
    
    /* Upgrades the intset to a larger encoding and inserts the given integer. */
    //这个函数执行的前提是value参数的大小超过了当前编码
    //为is->content重新分配内存并修改编码添加value进这个intset
    static intset *intsetUpgradeAndAdd(intset *is, int64_t value) {
        uint8_t curenc = intrev32ifbe(is->encoding);//当前编码类型
        uint8_t newenc = _intsetValueEncoding(value);//新的编码类型
        int length = intrev32ifbe(is->length);
        int prepend = value < 0 ? 1 : 0;//因为value一定超过了编码的限制,所以看value是大于0还是小于0以此决定value放置在content[0]还是content[length]
    
        /* 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--)
            //以curenc为编码倒序取出所有值并赋值给新的位置
            _intsetSet(is,length+prepend,_intsetGetEncoded(is,length,curenc));
    
        /* Set the value at the beginning or the end. */
        if (prepend)
            _intsetSet(is,0,value);
        else
            _intsetSet(is,intrev32ifbe(is->length),value);
        is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
        return is;
    }
    
    /* Resize the intset */
    //解除is的内存分配并重新分配长度为len的intset的内存
    static intset *intsetResize(intset *is, uint32_t len) {
        uint32_t size = len*intrev32ifbe(is->encoding);
        is = zrealloc(is,sizeof(intset)+size);
        return is;
    }
    
    //把from索引到intset尾部的整块数据复制to索引(复制之后from值不变,但是可以被覆盖)
    static void intsetMoveTail(intset *is, uint32_t from, uint32_t to) {
        void *src, *dst;
        uint32_t bytes = intrev32ifbe(is->length)-from;
        uint32_t encoding = intrev32ifbe(is->encoding);
    
        if (encoding == INTSET_ENC_INT64) {
            src = (int64_t*)is->contents+from;
            dst = (int64_t*)is->contents+to;
            bytes *= sizeof(int64_t);
        } else if (encoding == INTSET_ENC_INT32) {
            src = (int32_t*)is->contents+from;
            dst = (int32_t*)is->contents+to;
            bytes *= sizeof(int32_t);
        } else {
            src = (int16_t*)is->contents+from;
            dst = (int16_t*)is->contents+to;
            bytes *= sizeof(int16_t);
        }
        memmove(dst,src,bytes);
    }
    

    移除一个成员

    不同于插入一个成员,移除一个成员时不会改变intset的encoding,尽管移除这个成员之后所有成员的encoding都小于所在intset的encoding。

    /* Delete integer from intset */
    intset *intsetRemove(intset *is, int64_t value, int *success) {
        uint8_t valenc = _intsetValueEncoding(value);
        uint32_t pos;
        if (success) *success = 0;
    
        //valenc不可能大于当前编码,否则value一定不在该intset中
        if (valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,&pos)) {
            uint32_t len = intrev32ifbe(is->length);
    
            /* We know we can delete */
            if (success) *success = 1;
    
            /* Overwrite value with tail and update length */
            if (pos < (len-1)) intsetMoveTail(is,pos+1,pos);
            is = intsetResize(is,len-1);//减小内存分配
            is->length = intrev32ifbe(len-1);//size-1
        }
        return is;
    }
    

    总结

    通过intset底层实现我们可以发现:基于顺序存储的整数集合 执行一些需要用到查询的命令时 其时间复杂度不会是文档里注明O(1),例如:SADD、SREM 操作一个成员时,时间复杂度会是O(logn)。所以当整数集合数据量变大的时候,redis会用dict作为集合的底层实现,将SADD、SREM、SISMEMBER这些命令的时间复杂度降至O(1),当然,这会比intset消耗更多内存。

    相关文章

      网友评论

        本文标题:Redis3.2源码分析-整数集合intset

        本文链接:https://www.haomeiwen.com/subject/jzsrqftx.html