无序和唯一

Sets是字符串类型的无序集合，集合中的元素是唯一的，不会出现重复的数据。Sets底层是用散列表实现的，散列表的key存储的是Sets元素中的value，散列表的value指向null。

使用场景

当你需要存储多个元素，且不允许出现重复数据，无需考虑元素有序性时，可以使用Sets。Sets还支持在集合之间做交集、并集、差集操作

• 共同关注：通过交集实现

• 每日新增关注数：对近两天的总注册用户量集合取差集

• 打标签：为自己收藏的文章打标签，例如微信收藏功能，这样可以快速找到被添加了某个标签的所有文章。

intset

当元素内容是64位以内的10进制整数，且元素个数不超过512时，Sets会使用更加省内存的intset来存储。相关结构源码如下：

1
2
3
4
5

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

• length：记录整数集合存储的元素个数，其实就是contents数组的长度

• contents：真正存储整数集合的数组，是一块连续的内存区域。数组中的元素会按照值的大小从小到大存储，并且不会有重复元素

• encoding：编码格式，决定数组类型，一共有三种不同的值。

  • INTSET_ENC_INT16：表示contents数组的存储元素是int16_t类型的，每2字节表示一个整数元素

  • INTSET_ENC_INT32：表示contents数组的存储元素是int32_t类型的，每4字节表示一个整数元素

  • INTSET_ENC_INT64：表示contents数组的存储元素是int64_t类型的，每8字节表示一个整数元素

intset升级

当往一个int16_t类型的intset中插入一个int64_t类型的值时会触发升级。也就是Sets的所有数据类型会转换成int64_t类型。步骤如下：

1. 根据新元素的类型和Sets元素数量，计算包括新添加的元素在内的新空间大小，对底层数组空间扩容，重新分配空间。

2. 将intset中原有的元素转换成新元素类型，按从大到小的顺序放到正确位置，需要保障intset元素的有序性。

3. 将encoding的值修改为length+1

因此，每次向intset添加新元素可能引起升级，升级又会对原始数据进行类型转换，时间复杂度是O(n)。

intset不支持降级操作

散列表原理

Redis的散列表的底层数据结构通常是dict，由数组和链表构成，数组元素占用的槽位叫做哈希桶。当出现散列冲突时，会在桶下挂一个链表，用 拉链法 解决散列冲突的问题。

存储结构

散列表的底层存储数据结构实际上有两种:

• dict数据结构

• listpack(7.0之前使用ziplist)数据结构

通常使用dict数据结构存储数据，每个field-value pairs构成一个dictEntry节点。只有 同时满足 以下两个条件，才会使用listpack数据结构替代dict。按照field在前，value在后紧密相连的方式，依次把每个field-value pairs放到列表的表尾。

• 每个field-value pairs中的field和value的字符串的字节数都小于64

• field-value pairs数量小于512

每次向散列表写数据时，都会调用相关函数来判断是否需要转换底层数据结构。

当插入和修改的数据不满足以上两个条件时，就把散列表底层存储的数据结构转换为dict。虽然使用了listpack无法实现O(1)时间复杂度操作数据，但能大大减少内存占用，由于数据量比较小，性能不会有太大差异。

需要注意的是，不能由dict退化成listpack。

dict结构体主要源码如下：

1
2
3
4
5
6
7
8

struct dict {
    dictType *type;
    dictEntry **ht_table[2];
    unsigned long ht_used[2];
    long rehashidx; 
    unsigned pauserehash; 
    signed char ht_size_exp[2]; 
};

• dictType *type：存放函数的结构体，定义了一些函数指针。可以通过配置自定义函数，实现在dict的key和value中存放任何类型的数据。

• dictEntry **ht_table[2]：存放大小为2的散列表指针数组，每个指针指向一个dictEntry类型的散列表。

• ht_used[2]：记录每个散列表使用了多少槽位。

• rehashidx：标记是否正在执行rehash操作，-1表示没有，如果正在执行rehash操作，那么其实表示当前执行rehash操作的ht_table[0]的dictEntry数组的索引。

• pauserehash：表示rehash的状态，大于0表示rehash暂停，等于0时表示继续执行，小于0时表示出错。

数组中每个元素都是dictEntry类型的，就是它存放了field-value pairs。其结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct dictEntry {
    struct dictEntry *next;  /* Must be first */
    void *key;               /* Must be second */
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v;
};

• *key指针指向field-value pairs中的field，实际上指向一个SDS实例

• v 是一个union联合体，表示field-value pairs中的value，同一时刻只有一个字段有value，用联合体的目的是节省内存。

  • *val：value是非数字类型时使用该指针存储

  • uint64_t u64：value是无符号整数时使用该字段

  • int64_t s64：value是有符号整数时使用该字段

  • double d：value是浮点数时使用该字段

• *next指针指向下一个节点。当发生哈希冲突时，使用此链表（链表法）。

扩容和缩容

扩容和缩容的步骤如下：

1. 为了提高性能，减少哈希冲突，会创建一个大小等于ht_used[0] * 2的散列表ht_used[1]，也就是每次扩容时根据散列表ht_table [0]已使用空间扩大一倍创建一个新散列表ht_table [1]。反之，如果是缩容操作，就根据ht_table [0]已使用空间缩小一半创建一个新的散列表。

2. 重新计算field-value pairs的哈希值，得到这个field-value pairs在新散列表ht_table [1]中的桶位置，将field-value pairs迁移到新的散列表上。

3. 所有field-value pairs迁移完成后，修改指针，释放空间。把ht_table [0]指针指向扩容后的散列表，回收原来的小的散列表空间，把ht_table [1]指针指向null，为下次扩容\缩容准备。

扩容\缩容时机

• 当前没有执行bgsave或者BGREWRITEAOF命令，同时负载因子大于等于1。也就是当前没有RDB子进程和AOF重写子进程在工作，这两个操作容易对性能造成影响。

• 正在执行bgsave或者BGREWRITEAOF命令，负载因子大于或等于5。这时哈希冲突比较严重，再不扩容，查询效率就太低了。

负载因子 = 散列表存储的dictEntry节点数量 / 哈希桶个数。理想情况下每个哈希桶存储一个dictEntry节点，这时负载因子 = 1。

扩容过程

为了防止阻塞主线程造成性能问题，不是一次性把全部key迁移，而是分多次将迁移操作分散到每次请求中，避免集中式rehash造成长时间阻塞。

在渐进式rehash期间，dict会同时使用ht_table[0]和ht_table[1]两个散列表，具体步骤如下：

1. 将rehashidx配置为0，表示rehash开始执行。

2. 在rehash期间，服务端每次处理客户端对dict散列表的增删改查操作时，除了执行指定操作外，还会检查当前dict是否处于rehash状态，如果是，就把散列表ht_table[0]上索引位置为rehashidx的哈希桶的链表的所有field-value pairs rehash到散列表ht_table[1]上，并将rehashidx加1。

3. 当所有field-value pairs迁移完成后将rehashidx配置为-1，表示操作已完成。

删除、修改和查找可能会在两个散列表上进行，第一个没找到就去第二个，但是增加操作只会在新的散列表上进行。