从源码看Redis的'set'结构

sadd 命令用来往 set 结构中存入数据

> sadd a 1
(integer) 1

smembers可以查到存储的内容

> smembers a
1) "1"

sadd命令执行追踪

sadd的执行入口在 saddCommand,如果key不存在那么第一件事情就是确认底层的存储结构

 Code.SLICE.source("robj *setTypeCreate(sds value) {" +
      "    if (isSdsRepresentableAsLongLong(value,NULL) == C_OK)" +
      "        return createIntsetObject();" +
      "    return createSetObject();" +
      "}")
      .interpretation("看set中要添加的值是否能够转成long long类型，如果可以，set的类型为IntSet,否则使用hash table");

确定好结构之后，可以往里面去增加

• 如果原本是 hashtable,那么直接插入即可；
• 如果原本是intset,则需要看新插入的元素是否满足intset的结构，否则转成hashtable存储

Code.SLICE.source("else if (subject->encoding == OBJ_ENCODING_INTSET) {" +
        "        if (isSdsRepresentableAsLongLong(value,&llval) == C_OK) {" +
        "            uint8_t success = 0;" +
        "            subject->ptr = intsetAdd(subject->ptr,llval,&success);" +
        "            if (success) {" +
        "                /* Convert to regular set when the intset contains" +
        "                 * too many entries. */" +
        "                if (intsetLen(subject->ptr) > server.set_max_intset_entries)" +
        "                    setTypeConvert(subject,OBJ_ENCODING_HT);" +
        "                return 1;" +
        "            }" +
        "        } else {" +
        "            /* Failed to get integer from object, convert to regular set. */" +
        "            setTypeConvert(subject,OBJ_ENCODING_HT);" +
        "" +
        "            /* The set *was* an intset and this value is not integer" +
        "             * encodable, so dictAdd should always work. */" +
        "            serverAssert(dictAdd(subject->ptr,sdsdup(value),NULL) == DICT_OK);" +
        "            return 1;" +
        "        }" +
        "    }")
        .interpretation("set的另外一种数据结构，intset ,只要当前数据还能够转换成 longlong,那么继续在set中增加，否则将结构转换成 hashtable")
        .interpretation("1: 往intset添加成功之后，如果集合的元素个数已经超过了 配置的 set_max_intset_entries ，那么转换成 hashtable");

在往intset中插入的时候，需要确保不存存储一样的元素，因此会先查找是否有一样值的元素

Code.SLICE.source("int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;")
        .interpretation("先记下最小值和最大值的下标");
Code.SLICE.source("  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;" +
        "        }" +
        "    }")
        .interpretation("处理边界情况")
        .interpretation("1: 如果集合中是空的，直接在开始插入即可")
        .interpretation("2: 如果新插入的值小于当前最小的值，在开头插入即可")
        .interpretation("3: 如果插入新值大于当前最大的值，在结尾插入即可");
Code.SLICE.source("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;" +
        "        }" +
        "    }")
        .interpretation("二分查找，找到插入的位置，这里要么找到现有值元素的位置，要么找到要插入的位置");

总结

1、 set 底层使用了两种结构 intset和hashtable ;
2、 intset 内部是按照升序排列；
3、 intset根据数值大小会分成不同的数据结构，方便节省空间

附录

sadd命令源码完整的追踪过程

Redis开发与运维

Redis的设计与实现

文章永久链接：https://tech.souyunku.com/47057