【原】6）深度解密 Redis 的集合（Set）

古明地觉O_o 2022-12-08 发布于北京

展开全文

楔子

下面来解密 Redis 的集合，整篇文章分为三个部分。

Redis 集合的相关命令；
Redis 集合的应用场景；
Redis 集合的实现原理；

Redis 集合的相关命令

先来看看集合的相关命令，我们首先要学会如何使用它。

sadd key value1 value2 ···：向集合插入多个元素，如果重复会自动去重

Redis的集合和列表是类似的，都是用来存储多个标量，但是它和列表又有不同：

列表中的元素是可以重复的，而集合中的元素不会重复；
列表在插入元素的时候可以保持顺序，而集合不保证顺序；

# 返回成功插入的元素的个数，这里是 3 个
# 因为元素有重复，两个 1，只会插入一个
127.0.0.1:6379> sadd set1 1 1 2 3
(integer) 3  
127.0.0.1:6379>

smembers key：查看集合的所有元素

127.0.0.1:6379> smembers set1
1) "1"
2) "2"
3) "3"
127.0.0.1:6379>

sismember key value：查看 value 是否在集合中

127.0.0.1:6379> sismember set1 1
(integer) 1  # 在的话返回 1
127.0.0.1:6379> sismember set1 5
(integer) 0  # 不在返回 0
127.0.0.1:6379>

scard key：查看集合的元素个数

127.0.0.1:6379> scard set1
(integer) 3
127.0.0.1:6379>

srem key value1 value2 ···：删除集合中的元素

127.0.0.1:6379> srem set1 1 2
(integer) 2  # 返回删除成功的元素个数
127.0.0.1:6379> srem set1 1 2
(integer) 0
127.0.0.1:6379>

spop key count：随机弹出集合中 count 个元素

注意：count 是可以省略的，如果省略则弹出 1 个。另外一旦弹出，原来的集合里面也就没有了。

127.0.0.1:6379> smembers set1
1) "3"  # 还有一个元素
127.0.0.1:6379> sadd set1 1 2
(integer) 2  # 添加两个进去
127.0.0.1:6379> 
127.0.0.1:6379> smembers set1
1) "1"
2) "2"
3) "3"
127.0.0.1:6379> spop set1 1
1) "2"  # 弹出 1 个元素，返回弹出的元素
127.0.0.1:6379> smembers set1
1) "1"
2) "3"
127.0.0.1:6379>

srandmember key count：随机获取集合中 count 个元素

注意：count 是可以省略的，如果省略则获取 1 个。可以看到类似 spop，但是 srandmember 不会删除集合中的元素。

127.0.0.1:6379> smembers set1
1) "1"
2) "3"
127.0.0.1:6379> srandmember set1 1
1) "1"
127.0.0.1:6379> smembers set1
1) "1"
2) "3"

smove key1 key2 value：将 key1 当中的 value 移动到 key2 当中

因此 key1 当中的元素会少一个，key2 会多一个（前提是 value 在 key2 中不重复，否则 key2 还和原来保持一致）。

127.0.0.1:6379> smembers set1
1) "1"
2) "3"
127.0.0.1:6379> smembers set2
1) "1"
127.0.0.1:6379> smove set1 set2 3
(integer) 1
127.0.0.1:6379> smembers set1
1) "1"
127.0.0.1:6379> smembers set2
1) "1"
2) "3"
127.0.0.1:6379>

sinter/sunion/sdiff key1 key2：对 key1 和 key2 分别求交集、并集、差集

127.0.0.1:6379> sinter set1 set2
1) "2"
2) "3"
127.0.0.1:6379> sunion set1 set2
1) "1"
2) "2"
3) "3"
4) "4"
127.0.0.1:6379> sdiff set1 set2
1) "1"
127.0.0.1:6379> sdiff set2 set1
1) "4"
127.0.0.1:6379>

以上就是 Redis 的集合，用法还是很简单的，和 Python 的集合有着相似之处。

Redis 集合的使用场景

集合类型的经典使用场景如下：

1）保存社交软件上关注我的人和我关注的人，因为他们是不重复的；

2）中奖人信息也适合用集合类型存储，这样可以保证一个人不会重复中奖；

总之对于那些需要保证唯一性的场景，都适合使用集合。

Redis 集合的实现原理

集合的底层实现有两种，分别是整数集合（intset）和哈希表，当集合类型用哈希表存储时，哈希表的 key 为要插入的元素值，而哈希表的 value 则为 Null，如下图所示：

当集合中所有的值都为整数时，Redis 会使用 intset 结构（Redis 为整数专门设计的一种集合结构）来存储，如下代码所示：

127.0.0.1:6379> sadd s 1 2 3
(integer) 3
127.0.0.1:6379> object encoding s
"intset"
127.0.0.1:6379>

从上面代码可以看出，当所有元素都为整数时，集合会以 intset 结构进行数据存储。但当发生以下两种情况时，会导致集合类型使用 hashtable 而非 intset：

当元素个数超过 512 个时，该值可通过参数 set-max-intset-entries 来配置；
当元素为非整数时；

import redis

client = redis.Redis(host="...", 
                     decode_responses="utf-8")

client.sadd("s1", *range(513))
# 超过 512 个，使用哈希表存储
print(
    client.object("encoding", "s1")
)  # hashtable

client.sadd("s2", *range(512))
# 没超过 512 个，使用 intset
print(
    client.object("encoding", "s2")
)  # intset

client.sadd("s3", "satori")
# 不是整数，使用哈希表存储
print(
    client.object("encoding", "s3")
)  # hashtable

由于哈希表我们在介绍 Hash 的时候已经说过了，下面就来看看整数集合（intset）是怎么实现的。相关源码位于 intset.h 和 intset.c 中，前者是定义，后者是实现。

typedef struct intset {
    // 编码方式
    uint32_t encoding;
    // 集合包含的元素数量
    uint32_t length;
    // 保存元素的数组
    int8_t contents[];
} intset;

整数集合是一块连续的内存空间，从定义上也能看出。而且保存元素的容器是一个 contents 数组，从内存使用的角度来看，由于整数集合是一块连续的内存空间，所以这样就避免了内存碎片，并提升了内存使用效率。

另外虽然 contents 被声明为 int8_t 类型的数组，但实际上 contents 数组并不保存 int8_t 类型的元素，contents 数组的真正类型取决于 intset 结构体里的 encoding 字段的值。比如：

如果 encoding 字段为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；
如果 encoding 字段为 INTSET_ENC_INT32，那么 contents 就是一个 int32_t 类型的数组，数组中每一个元素的类型都是 int32_t；
如果 encoding 字段为 INTSET_ENC_INT64，那么 contents 就是一个 int64_t 类型的数组，数组中每一个元素的类型都是 int64_t；

不同类型的 contents 数组，意味着数组的大小也会不同。

于是这就产生了一个问题，假设 contents 数组的类型是 int16_t，但现在插入一个 int32_t 类型的元素，这个时候要怎么办？

由于 C 数组只能保存相同类型的元素，所以为了能够存储 int32_t，整个集合中已存在的所有元素都要先变成 int32_t 类型。也就是按新元素的类型（int32_t）扩展 contents 数组的空间大小，然后才能将新元素加入到整数集合里。

上述这个过程叫做升级，当然升级的过程中，也要维持整数集合的有序性。

注意：整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后再将每个元素转成指定类型。举个例子，假设有一个整数集合，里面存了 3 个元素，并且类型为 int16_t。

现在需要往这个整数集合中加入一个新元素 65535，这个新元素需要用 int32_t 类型来保存，所以整数集合要进行升级操作。

首先会为 contents 数组扩容，在原本空间的大小之上再扩容多 80 个位（10 字节）。因为新来的元素占 4 字节，之前的 3 个元素本来是 int16_t（2 字节），变成 int32_t 之后每个元素大小要增加 2 字节，所以总共要扩容 10（ 4 + 3 * 2 ）字节，这样才能保存 4 个 int32_t 类型的数据。

扩容完 contents 数组空间大小后，需要将之前的三个元素转换为 int32_t 类型，并将转换后的元素放置到正确的位上面，并且需要维持底层数组的有序性不变，整个转换过程如下：

逻辑不难理解，重点是整数集合升级的具体实现，也是非常考验编程功底的地方。正如使用数组实现大整数一样，思路都很简单，但具体实现非常考验技巧，有兴趣可以自己尝试一下。那么问题来了，整数集合升级有什么好处呢？不用想绝对是省内存。

如果要让一个数组同时保存 int16_t, int32_t, int64_t 类型的元素，最简单的做法就是直接使用 int64_t 类型的数组。不过这样的话，当元素都是 int16_t 类型时，就会造成内存浪费的情况，每个元素都要浪费 6 字节。

而整数集合升级就能避免这种情况，如果一直向整数集合添加 int16_t 类型的元素，那么整数集合的底层就会一直使用 int16_t 类型的数组。只有在我们要将 int32_t 或 int64_t 类型的元素添加到集合时，才会对数组进行升级操作。

因此整数集合升级的好处就是节省内存资源。

另外，整数集合不支持降级操作，一旦对数组进行了升级，就会一直保持升级后的状态。比如前面升级操作的例子，如果删除了 65535 元素，整数集合的数组还是 int32_t 类型的，并不会因此降级为 int16_t 类型。

所以 Redis 在数据结构的设计上可谓是下足了功夫，作为一款内存数据库，对内存的使用做足了优化。特别是在数据结构上面，Redis 给我们提供了两个思路：

1）使用连续的内存空间，避免内存碎片；
2）针对不同长度的实体数据，采用不同大小的元信息，以避免使用统一大小的元数据，造成内存浪费。因为如果统一大小，必然要选择最大的；

此外 Redis 在数据访问上也进行了优化，有一些数据是经常需要被访问的，比如常见的整数，Redis 协议中常见的回复信息，以及常见的报错信息等等。

而为了避免在内存中反复创建这些经常被访问的数据，Redis 就采用了共享对象的设计思想。这个设计思想很简单，就是把这些常用数据创建为共享对象，当上层应用需要访问它们时，直接读取就行。

// server.c
void createSharedObjects(void) {
    // …
    //常见回复信息
    shared.ok = createObject(OBJ_STRING,
                             sdsnew("+OK\r\n"));
    shared.err = createObject(OBJ_STRING,
                              sdsnew("-ERR\r\n"));
    //…
    //常见报错信息
    shared.nokeyerr = createObject(
        OBJ_STRING,sdsnew("-ERR no such key\r\n"));
    shared.syntaxerr = createObject(
        OBJ_STRING,sdsnew("-ERR syntax error\r\n"));
    //0 到 9999 的整数
    for (j = 0; j < OBJ_SHARED_INTEGERS; j++) {
        shared.integers[j] =
        makeObjectShared(
            createObject(OBJ_STRING,(void*)(long)j));
        //…
    }
   //…
}