楔子
下面来解密 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)); //… } //… }
里面创建了非常多的共享对象，可以进入源码中查看。
小结
Set 存储的如果都是数字，并且数量不超过 512 个，底层使用 intset；如果超过 512 个，或者出现了不是整数的元素，那么会将 intset 换成哈希表。
变长编码，数字范围不同，intset 会选择 int16_t / int32_t /int64_t 编码，具体可以查看 intset.c 的 _intsetValueEncoding 函数；
intset 在存储时是有序的，这意味着查找一个元素，可使用「二分查找」，具体可以查看 intset.c 的 intsetSearch 函数。
编码升级，当数据范围扩大时，会引发编码长度升级。
本文参考自：
- 极客时间蒋德钧：《Redis 源码剖析与实战》
- 小林 coding：《图解 Redis》
