【Redis】基础结构（四）：Set 类型命令、应用、原理

分手后的思念是犯贱 2022-10-22 10:49 125阅读 0赞

Redis 的集合相当于 Java 语言里面的 HashSet，它内部的键值对是无序的唯一的。它的内部实现相当于一个特殊的字典，字典中所有的 value 都是一个值NULL。 **当集合中最后一个元素移除之后，数据结构自动删除，内存被回收**。

### 1.常用命令 ###

**1.存（sadd）**

sadd key member [member...]				// 向集合中存入元素，元素存在则忽略，key不存在则新建

**2 取（srandmember&spop）**

srandmember key [count] 				// 随机取count个元素，不删除
    spop key [count]					    // 随机取count个元素，删除

**3.查 & 删**

smembers key							 // 获取集合key中所有元素
    scard key								 // 获取集合key的元素个数
    smember key member 						 // 判断元素member是否在集合key中
    
    srem key member [member...]				 // 从集合key中删除元素

**4.集合操作**

sinter key [key...] 					 // 多个key的Set 取交集
    sunion key [key...]				         // 并集
    sdiff key [key...]						 // 差集

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center][]

### 2.应用示例 ###

**1.微信抽奖小程序（随机出队）**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1][]

将参与抽奖的user放入set，可以查看抽奖人数，然后随机抽取count个（srandmember），并决定是否删除中奖用户。

sadd key {userId}			    // 将参与抽奖用户放入集合。
    smembers act:1			 		// 查看所有参与抽奖用户
    srandmemeber key [count]        // 抽取count名中奖者（不删除中奖人）
    spop key [count] 				// 抽取count名中奖者（删除中奖人）

**2.点赞（不可重复性）**

将点赞的人放入set，可以判断该用户是否点过赞

sadd like:{消息ID} {用户ID}		 //	点赞
    srem like:{消息ID} {用户ID}		 // 取消点赞
    sismember like:{消息ID} {用户ID}	 // 检查用户是否点过赞
    smembers like:{消息ID} 			 // 获取点赞用户列表
    scard like:{消息ID} 				 // 获取点赞用户数

**3.微信微博关注模型（集合运算）**

通过set的集合运算可以得到，用户间互相关注的都有谁

sinter love:uId1 love:uId2 		 // 得到user1与user2的共同关注（交集）

**4.实现电商商品筛选**  
![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2][]

sadd brand:huawei P30
    sadd brand:xiaomi mi-6X
    sadd brand:iphone iphone8
    sadd os:android P30 mi-6X
    sadd cpu:brand:intel P30 mi-6X
    sadd ram:8G P30 mi-6X iphone8
    
    sinter os:android cpu:brand:intel ram:8G ==> {P30, mi-6X}

### 3.存储原理 ###

Set 集合采用了整数集合和字典两种方式来实现的，当满足如下两个条件的时候，采用整数集合实现；一旦有一个条件不满足时则采用字典来实现。

*  **Set 集合中的所有元素都为整数**
 *  **Set 集合中的元素个数不大于 512（默认 512，可以通过修改 set-max-intset-entries 配置调整集合大小）**

**整数集合（intset）**

intset 顾名思义，是由整数组成的集合。实际上，intset 是一个由整数组成的有序集合，从而便于在上面进行**二分查找**，用于快速地判断一个元素是否属于这个集合。

它在内存分配上与 [ziplist][] 有些类似，是连续的一整块内存空间，而且对于大整数和小整数（按绝对值）采取了不同的编码，尽量对内存的使用进行了优化。

intset 的数据结构定义如下（出自intset.h和intset.c）：

typedef struct intset {
    
    	/* 数据编码，表示 intset 中的每个数据元素用几个字节来存储 */
        uint32_t encoding;
        /* intset中的元素个数 */
        uint32_t length;
        /* 柔性数组，表示 intset 的 header 后面紧跟着数据元素 */
        int8_t contents[];
    } intset;

> PS：`encoding`和`length`两个字段构成了intset的头部（header）

encoding 它有三种可能的取值：

*  INTSET\_ENC\_INT16：每个元素用2个字节存储
 *  INTSET\_ENC\_INT32：每个元素用4个字节存储
 *  INTSET\_ENC\_INT64：每个元素用8个字节存储

因此，intset中存储的整数最多只能占用 64 bit。

其中需要注意的是，intset 可能会随着数据的添加而改变它的数据编码：

*  最开始，新创建的 intset 使用占内存最小的 INTSET\_ENC\_INT16（值为2）作为数据编码
 *  每添加一个新元素，则根据元素大小决定是否对数据编码进行升级

下图给出了一个添加数据的具体例子  
![img][]在上图中：

*  新创建的 intset 只有一个 header，总共8个字节。其中`encoding` = 2, `length` = 0
 *  添加 13, 5 两个元素之后，因为它们是比较小的整数，都能使用2个字节表示，所以`encoding`不变，值还是2
 *  当添加 32768 的时候，它不再能用2个字节来表示了（2个字节能表达的数据范围是-215~215-1，而32768等于215，超出范围了），因此 `encoding` 必须升级到 INTSET\_ENC\_INT32（值为4），即用4个字节表示一个元素。

在添加每个元素的过程中，intset 始终保持从小到大有序。

> PS：intset 与 [ziplist][] 对比
> 
>  *  ziplist 可以存储任意二进制串，而 intset 只能存储整数
>  *  ziplist 是无序的，而 intset 是从小到大有序的。因此，在 ziplist 上查找只能遍历，而在 intset 上可以进行二分查找，性能更高
>  *  ziplist 可以对每个数据项进行不同的变长编码（每个数据项前面都有数据长度字段`len`），而 intset 只能整体使用一个统一的编码（`encoding`）

要理解 intset 的一些实现细节，只需要关注 intset 的两个关键操作基本就可以了：查找（`intsetFind`）和添加（`intsetAdd`）元素。

intsetFind 查找元素的关键代码如下所示（出自intset.c）：

// 在指定的 intset 中查找指定的元素 value，找到返回1，没找到返回0
    uint8_t intsetFind(intset *is, int64_t value) {
        
    	// 根据要查找的 value 落在哪个范围而计算出相应的数据编码（即它应该用几个字节来存储）
        uint8_t valenc = _intsetValueEncoding(value);
        // 如果 value 所需的数据编码比当前 intset 的编码要大，则它肯定在当前 intset 所能存储的数据范围之外（特别大或特别小）,所以这时会直接返回0
        // 否则调用`intsetSearch`执行一个二分查找算法
        return valenc <= intrev32ifbe(is->encoding) && intsetSearch(is,value,NULL);
    }
    
    // 在指定的 intset 中查找指定的元素 value ，如果找到，则返回1并且将参数 pos指向找到的元素位置；
    // 如果没找到，则返回0并且将参数 pos 指向能插入该元素的位置
    static uint8_t intsetSearch(intset *is, int64_t value, uint32_t *pos) {
        
        int min = 0, max = intrev32ifbe(is->length)-1, mid = -1;
        int64_t cur = -1;
    
        // 特殊处理 intset  为空的情况
        if (intrev32ifbe(is->length) == 0) {
        
            if (pos) *pos = 0;
            return 0;
        // 特殊处理两个边界情况：当要查找的 value 比最后一个元素还要大或者比第一个元素还要小的时候
        // 实际上，这两部分的特殊处理，在二分查找中并不是必须的，但它们在这里提供了特殊情况下快速失败的可能
        } 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;
            }
        }
    	
    	// 真正执行二分查找过程
        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;
            }
        }
    	
        if (value == cur) {
        
            if (pos) *pos = mid;
            return 1;
        // 如果最后没找到，插入位置在 min 指定的位置
        } else {
        
            if (pos) *pos = min;
            return 0;
        }
    }

> 这个查找算法的总的时间复杂度为O(log n)

intsetAdd 添加元素的关键代码如下所示（出自intset.c）：

// 在 intset 中添加新元素 value
    // 如果 value 在添加前已经存在，则不会重复添加，这时参数 success 被置为0
    // 如果 value 在原来 intset 中不存在，则将 value 插入到适当位置，这时参数 success 被置为0
    intset *intsetAdd(intset *is, int64_t value, uint8_t *success) {
        
        uint8_t valenc = _intsetValueEncoding(value);
        uint32_t pos;
        if (success) *success = 1;
    
        // 如果要添加的元素 value 所需的数据编码比当前 intset 的编码要大
        // 那么则调用 intsetUpgradeAndAdd 将 intset 的编码进行升级后再插入 value
        if (valenc > intrev32ifbe(is->encoding)) {
        
            return intsetUpgradeAndAdd(is,value);
        } else {
        
            
            // 如果能查到，则不会重复添加
            if (intsetSearch(is,value,&pos)) {
        
                if (success) *success = 0;
                return is;
            }
    		
    		// 如果没查到，则调用 intsetResize 对 intset 进行内存扩充，使得它能够容纳新添加的元素
    		// 因为intset是一块连续空间，因此这个操作会引发内存的 realloc, 这有可能带来一次数据拷贝
    		// 注：intsetUpgradeAndAdd 的实现中也会调用 intsetResize 来完成内存扩充。在进行编码升级时，会把原来intset中的每个元素取出来，再用新的编码重新写入新的位置
            is = intsetResize(is,intrev32ifbe(is->length)+1);
            // 调用 intsetMoveTail 将待插入位置后面的元素统一向后移动1个位置，这也涉及到一次数据拷贝
            if (pos < intrev32ifbe(is->length)) intsetMoveTail(is,pos,pos+1);
        }
    
        _intsetSet(is,pos,value);
        is->length = intrev32ifbe(intrev32ifbe(is->length)+1);
        // 返回一个新的intset指针，它可能与传入的 intset 指针 is 相同，也可能不同
        // 注：调用方必须用这里返回的新的 intset，替换之前传进来的旧的 intset 变量
        return is;
    }

> 显然，这个 intsetAdd 添加算法总的时间复杂度为O(n)

**字典（dict）**

在 Redis 中，hashtable 被称为字典（dictionary），它是一个数组+链表的结构。

在之前的文章我们介绍了，Redis 的 KV 结构是通过一个 dictEntry 来实现的：

typedef struct dictEntry {
        
    
       /* key 关键字定义 */
       void *key; 
       union {
        
        /* value 定义 */
       void *val; uint64_t u64;
       int64_t s64; double d;
       } v;
       /* 指向下一个键值对节点 */
       struct dictEntry *next; 
       
    } dictEntry;

dictht 又对 dictEntry 进行了多层的封装：

/* This is our hash table structure. Every dictionary has two of this as we
    * implement incremental rehashing, for the old to the new table. */
    typedef struct dictht {
        
    
    	/* 哈希表数组 */
        dictEntry **table; 
        /* 哈希表大小 */
        unsigned long size; 
        /* 掩码大小，用于计算索引值。总是等于 size-1 */
        unsigned long sizemask; 
        /* 已有节点数 */
        unsigned long used; 
        
    } dictht

ht 又放到了 dict 里面：

typedef struct dict {
        
    	
    	/* 字典类型 */
        dictType *type; 
        /* 私有数据 */
        void *privdata; 
        /* 一个字典有两个哈希表 */
        dictht ht[2]; 
        /* rehash 索引 */
        long rehashidx; 
        /* 当前正在使用的迭代器数量 */
        unsigned long iterators; 
        
    } dict;

从最底层到最高层 dictEntry——dictht——dict——OBJ\_ENCODING\_HT

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]

> 注意：dictht 后面是 NULL 说明第二个 ht 还没用到。dictEntry\* 后面是 NULL 说明没有 hash 到这个地址。dictEntry 后面是 NULL 说明没有发生哈希冲突。

最后，利用所有 dictEntry 的 key 唯一性，然后使 value 为 null，就形成了 Set 结构。

![img][img 1]

对于小集合使用intset来存储，主要的原因是**节省内存**。特别是当存储的元素个数较少的时候，dict 所带来的内存开销要大得多（包含两个哈希表、链表指针以及大量的其它元数据）。所以，当存储大量的小集合而且集合元素都是数字的时候，用 intset 能节省下一笔可观的内存空间。

实际上，从时间复杂度上比较，**intset 的平均情况是没有 dict 性能高的**。以查找为例，intset 是O(log n)的，而 dict 可以认为是 O(1) 的。但是，由于使用 intset 的时候集合元素个数比较少，所以这个影响不大。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221022/3819ceb6adf947eabec26a8d72dfa00e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221022/016e8b4dcb1440abbe1110cc6166bc47.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221022/8a45b79ce6e34200936683fae05d1c1b.png
[ziplist]: http://mp.weixin.qq.com/s?__biz=MzA4NTg1MjM0Mg==&mid=2657261265&idx=1&sn=e105c4b86a5640c5fc8212cd824f750b&scene=21#wechat_redirect
[img]: /images/20221022/7ae16ed564674a8b9c99a416e167c1dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkzNTkyNw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221022/ccc93de81d2941dab5195edc7202abc2.png
[img 1]: /images/20221022/dd832c3a1f444789bf7b200a66e4d21e.png