Redis中的Set与Intset

1435597771 ·

什么是set

Set 是Redis的基本数据结构之一，他是一个无序并且唯一的键值集合，他的存储顺序不会按照插入的先后顺序进行存储。

在一个集合中最多可以存储2^32-1个元素。但是这个元素数量是对Dict作为底层实现而言的，默认情况下，只有当整数个数不超过 512 个时 Redis 才会使用 IntSet，超过这个阈值则会触发升级，转换为 Dict。

他的内部实现：

Set的底层数据结构是由Dict和Intset实现的。他们的区别是：

  • 如果集合中的元素都是整数且元素格式小于512个(默认值，可以通过set-maxintset-entries配置), Redis会使用Intset来作为Set的底层数据结构

  • 如果集合元素不满足上面的条件，那么Redis会使用Dict作为Set的底层结构，用Dict中的key存储值，Dict中的value设置为null

我们着重介绍intset这个底层结构

IntSet的结构如下：

type struct intset {
  //编码方式
  uint32_t encoding;
  //集合包含的元素数量
  uint32_t length;
  //保存元素的数组
  int8_t contents[]; // int8_t 并不是说明用来存储int8类型的整数，用来存储什么类型的整数由encoding编码来决定
}

保存元素的容器是一个数组，在redis中使用二分查找来查找元素，那么也就意味着在intset作为底层数据结构的情况下，set是有序的。那么为什么还要说set是无序的呢？

原因就是上面说的用intset的条件需要元素个数小于512并且全部都是整数，如果先存了数字，然后元素数量超过512，那么set的底层结构会立马从intset替换为dict，由于hash函数的平衡性，所以无法保证顺序。 所以，用intset作为底层数据结构造成的有序性，反而是代价。

那么为什么要用intset作为set的底层结构呢？

答案就是为了节约内存，拿100个32位的整数来举例子。

如果用dict来存储这些整数，

一个 Dict 节点需要：

  • dictEntry 结构体：24 字节（key 指针、val 指针、next 指针）

  • redisObject 封装层：16 字节

  • SDS 字符串封装：最少 10~15 字节

  • 哈希桶数组分配的指针：8 字节

那么起码需要都需要5800字节了。

而用intset呢？

  • encoding+length：8字节

  • 100个32位整数：400字节

加起来才408字节，远远小于用dict存储字节，所以在整数情况下数字小于512个情况下，选择用intset来作为底层接口

intset是如何转换为dict的

简单来说有4步

  • 创建： 创建全新的dict

  • 遍历：遍历所有intset中的元素

  • 迁移： 将元素从整数转换为字符串，然后迁移到dict中

  • 替换： 将set的编码修改为OBJ_ENCONDING_HT，ptr指向新创建的dict，然后释放原本的intset内存

Intset的升级规则

当我们将一个新的元素加入到整数集合中时，当这个元素的类型比原集合类型大的时候，就会触发这个升级规则。

整数集合的升级不会分配一个新类型的数组，而是在原本数组上扩展空间，然后将每个元素类型进行分割，如果enconding是INSET_ENC_INT16，那么每个元素的间隔就是16位

假设有3个16为大小的集合，现在新加入一个32位大小的整数。那么升级步骤如下：

  • 扩容：将content数组扩容，在原本内存上扩容80位（4 x 32- 3 x 16）=80，那么现在数组就有128位

  • 迁移：现将原本的数据转换为32位，然后从后往前依次移动对应的位置上，那么第三个数字的位置就是64～95位上

  • 添加新数据：在迁移的过程中，最后的空间预留下来，就是为了插入新数据的

那么为什么要升级呢？

答案是节约空间， 如果全部用32位存储16位的数字，那么会造成内存浪费，整数的升级可以在一定程度上避免内存浪费。

那么支持降级吗？

不支持，如果支持降级，那么会造成来回切换内存，造成震荡，反而会影响性能。

常用命令：

# 往集合key中存入元素，元素存在则忽略，若key不存在则新建
SADD key member [member...]
​
# 从集合key中删除元素
SREM key member [member...]
​
# 获取集合key中所有元素
SMEMBERS key 
​
# 获取集合key中的元素个数
SCARD key 
​
# 判断member 元素是否存在于key集合中
SISMEMBER key member 
​
# 从集合key中随机选出count个元素，元素不从key中删除
SRANDMEMBER key [count]
​
# 从集合key中随机选出count个元素，元素从key中删除
SPOP key [count ]
​
# 交集运算
SINTER key [key ...]
# 将交集结果存入新集合destination中
SINTERSTORE destination key [key ...]
​
# 并集运算
SUNION key [key ...]
# 将并集结果存入新集合destination中
SUNIONSTORE destination key [key ...]
​
# 差集运算
SDIFF key [key ...]
# 将差集结果存入新集合destination中
SDIFFSTORE destination key [key ...]

使用场景：

Set的集合运算如：差集、并集、交集运算复杂度较高，在数据量大的情况下，如果直接执行这些计算，会导致redis阻塞

  • 点赞

  • 共同关注

  • 抽奖活动