探索Redis设计与实现7:Redis内部数据结构详解——int

2019-11-17  本文已影响0人  da3acf50377b

本文转自互联网

本系列文章将整理到我在GitHub上的《Java面试指南》仓库,更多精彩内容请到我的仓库里查看

https://github.com/h2pl/Java-Tutorial

喜欢的话麻烦点下Star哈

文章首发于我的个人博客:

www.how2playlife.com

本文是微信公众号【Java技术江湖】的《探索Redis设计与实现》其中一篇,本文部分内容来源于网络,为了把本文主题讲得清晰透彻,也整合了很多我认为不错的技术博客内容,引用其中了一些比较好的博客文章,如有侵权,请联系作者。

该系列博文会告诉你如何从入门到进阶,Redis基本的使用方法,Redis的基本数据结构,以及一些进阶的使用方法,同时也需要进一步了解Redis的底层数据结构,再接着,还会带来Redis主从复制、集群、分布式锁等方面的相关内容,以及作为缓存的一些使用方法和注意事项,以便让你更完整地了解整个Redis相关的技术体系,形成自己的知识框架。

如果对本系列文章有什么建议,或者是有什么疑问的话,也可以关注公众号【Java技术江湖】联系作者,欢迎你参与本系列博文的创作和修订。

本文是《Redis内部数据结构详解》系列的第七篇。在本文中,我们围绕一个Redis的内部数据结构——intset展开讨论。

Redis里面使用intset是为了实现集合(set)这种对外的数据结构。set结构类似于数学上的集合的概念,它包含的元素无序,且不能重复。Redis里的set结构还实现了基础的集合并、交、差的操作。与Redis对外暴露的其它数据结构类似,set的底层实现,随着元素类型是否是整型以及添加的元素的数目多少,而有所变化。概括来讲,当set中添加的元素都是整型且元素数目较少时,set使用intset作为底层数据结构,否则,set使用dict作为底层数据结构。

在本文中我们将大体分成三个部分进行介绍:

  1. 集中介绍intset数据结构。
  2. 讨论set是如何在intset和dict基础上构建起来的。
  3. 集中讨论set的并、交、差的算法实现以及时间复杂度。注意,其中差集的计算在Redis中实现了两种算法。

我们在讨论中还会涉及到一个Redis配置(在redis.conf中的ADVANCED CONFIG部分):

set-max-intset-entries 512

注:本文讨论的代码实现基于Redis源码的3.2分支。

intset数据结构简介

intset顾名思义,是由整数组成的集合。实际上,intset是一个由整数组成的有序集合,从而便于在上面进行二分查找,用于快速地判断一个元素是否属于这个集合。它在内存分配上与ziplist有些类似,是连续的一整块内存空间,而且对于大整数和小整数(按绝对值)采取了不同的编码,尽量对内存的使用进行了优化。

intset的数据结构定义如下(出自intset.h和intset.c):

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

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

各个字段含义如下:

其中需要注意的是,intset可能会随着数据的添加而改变它的数据编码:

下图给出了一个添加数据的具体例子(点击看大图)。

intset添加数据举例

在上图中:

intset与ziplist相比:

intset的查找和添加操作

要理解intset的一些实现细节,只需要关注intset的两个关键操作基本就可以了:查找(intsetFind)和添加(intsetAdd)元素。

intsetFind的关键代码如下所示(出自intset.c):

uint8_t intsetFind(intset *is, int64_t value) {
    uint8_t valenc = _intsetValueEncoding(value);
    return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
}

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);
            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;
    }
}

关于以上代码,我们需要注意的地方包括:

intsetAdd的关键代码如下所示(出自intset.c):

intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
    uint8_t valenc = _intsetValueEncoding(value);
    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)) {
        /* 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;
            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;
}

关于以上代码,我们需要注意的地方包括:

Redis的set

为了更好地理解Redis对外暴露的set数据结构,我们先看一下set的一些关键的命令。下面是一些命令举例:

set命令举例

上面这些命令的含义:

我们前面提到过,set的底层实现,随着元素类型是否是整型以及添加的元素的数目多少,而有所变化。例如,具体到上述命令的执行过程中,集合s1的底层数据结构会发生如下变化:

我们知道,dict是一个用于维护key和value映射关系的数据结构,那么当set底层用dict表示的时候,它的key和value分别是什么呢?实际上,key就是要添加的集合元素,而value是NULL。

除了前面提到的由于添加非数字元素造成集合底层由intset转成dict之外,还有两种情况可能造成这种转换:

对于小集合使用intset来存储,主要的原因是节省内存。特别是当存储的元素个数较少的时候,dict所带来的内存开销要大得多(包含两个哈希表、链表指针以及大量的其它元数据)。所以,当存储大量的小集合而且集合元素都是数字的时候,用intset能节省下一笔可观的内存空间。

实际上,从时间复杂度上比较,intset的平均情况是没有dict性能高的。以查找为例,intset是O(log n)的,而dict可以认为是O(1)的。但是,由于使用intset的时候集合元素个数比较少,所以这个影响不大。

Redis set的并、交、差算法

Redis set的并、交、差算法的实现代码,在t_set.c中。其中计算交集调用的是sinterGenericCommand,计算并集和差集调用的是sunionDiffGenericCommand。它们都能同时对多个(可以多于2个)集合进行运算。当对多个集合进行差集运算时,它表达的含义是:用第一个集合与第二个集合做差集,所得结果再与第三个集合做差集,依次向后类推。

我们在这里简要介绍一下三个算法的实现思路。

交集

计算交集的过程大概可以分为三部分:

  1. 检查各个集合,对于不存在的集合当做空集来处理。一旦出现空集,则不用继续计算了,最终的交集就是空集。
  2. 对各个集合按照元素个数由少到多进行排序。这个排序有利于后面计算的时候从最小的集合开始,需要处理的元素个数较少。
  3. 对排序后第一个集合(也就是最小集合)进行遍历,对于它的每一个元素,依次在后面的所有集合中进行查找。只有在所有集合中都能找到的元素,才加入到最后的结果集合中。

需要注意的是,上述第3步在集合中进行查找,对于intset和dict的存储来说时间复杂度分别是O(log n)和O(1)。但由于只有小集合才使用intset,所以可以粗略地认为intset的查找也是常数时间复杂度的。因此,如Redis官方文档上所说(http://redis.io/commands/sinter),sinter命令的时间复杂度为:

O(N*M) worst case where N is the cardinality of the smallest set and M is the number of sets.

并集

计算并集最简单,只需要遍历所有集合,将每一个元素都添加到最后的结果集合中。向集合中添加元素会自动去重。

由于要遍历所有集合的每个元素,所以Redis官方文档给出的sunion命令的时间复杂度为(http://redis.io/commands/sunion):

O(N) where N is the total number of elements in all given sets.

注意,这里同前面讨论交集计算一样,将元素插入到结果集合的过程,忽略intset的情况,认为时间复杂度为O(1)。

差集

计算差集有两种可能的算法,它们的时间复杂度有所区别。

第一种算法:

这种算法的时间复杂度为O(N*M),其中N是第一个集合的元素个数,M是集合数目。

第二种算法:

这种算法的时间复杂度为O(N),其中N是所有集合的元素个数总和。

在计算差集的开始部分,会先分别估算一下两种算法预期的时间复杂度,然后选择复杂度低的算法来进行运算。还有两点需要注意:

对于sdiff的时间复杂度,Redis官方文档(http://redis.io/commands/sdiff)只给出了第二种算法的结果,是不准确的。


系列下一篇待续,敬请期待。

原创文章,转载请注明出处,并包含下面的二维码!否则拒绝转载!
本文链接:http://zhangtielei.com/posts/blog-redis-intset.html

我的微信公众号: tielei-blog (张铁蕾)
上一篇下一篇

猜你喜欢

热点阅读