文章目录

  • Set
    • 概念
    • 常用命令
    • 底层数据结构
      • INTSET（整数集合）
      • HASHTABLE（哈希表）
    • 应用场景
  • HSet
    • 底层数据结构

Set

概念

  • Redis的set是一个不重复、无序并唯一的键值集合。（方便管理无序集合）
  • 它支持交集、并集、差集等等

set和list区别

  • List 可以存储重复元素，Set 只能存储非重复元素；
  • List 是按照元素的先后顺序存储元素的，而 Set 则是无序方式存储元素的。

常用命令

'Set常用操作'# 往集合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]'Set运算操作'# 交集运算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 类型的底层数据结构是由哈希表或整数集合实现的：

  • 如果集合中的元素都是整数且元素个数小于 512 （默认值，set-maxintset-entries配置）个，Redis 会使用整数集合作为 Set 类型的底层数据结构；
  • 如果集合中的元素不满足上面条件，则 Redis 使用哈希表作为 Set 类型的底层数据结构。

INTSET（整数集合）

  • 集群元素都是整数，且元素数量不超过512个，就可以使用INTSET编码，INTSET排列比较紧凑，内存占用少，但是查询时需要二分查找。
typedef struct intset{uint32_t encoding;uint32_t length; //元素数量int8_t contents[]; //保存元素的数组}

  • contents 数组的真正类型取决于 intset 结构体里的 encoding 属性的值。

    • 如果 encoding 属性值为 INTSET_ENC_INT16，那么 contents 就是一个 int16_t 类型的数组，数组中每一个元素的类型都是 int16_t；

  • 整数集合升级的过程不会重新分配一个新类型的数组，而是在原本的数组上扩展空间，然后在将每个元素按间隔类型大小分割

  • intset用来保存元素数组，默认是int16编码，后续如果插入更大的整数，才会升级到int32。但是升级也有弊端，整数数组的编码会变成与最大元素的类型一致，如果这时候元素数量非常多，就不节约内存了。

  • 整数集合不支持降级操作


HASHTABLE（哈希表）

  • 不满足INTSET条件，就需要使用HASHTABLE,能在O(1)时间找到一个元素是否存在

hashtable结构

  • hashtable初始化为4
  • dictEntry是链表，是为了解决哈希冲突。
'dict底层结构'typedef struct dict {dictType *type;void *private;dictht ht[2];//包含了两个dictht结构，也就是两个hashtable.long rehashidx;//标志位，-1表示不再扩容，0代表rehashunsigned long iterators}dict;'dictht底层结构'typedef struct dictht {dictEntry **table;//指向实际hash存储(dictEntry看作数组，数组中都是一个个的bucket)unsigned long size; //哈希表大小，实际就行hidictEntry有多少元素空间unsigned long sizemask; //哈希表大小的掩码，总等于size-1unsigned long used; //表示已经使用的节点数量}dictht;'dictEntry底层结构'typedef struct dictEntry {void *key; // 键union {void *val;uint64_t u64;int64_t s64;double d;} v; // 值struct dictEntry *next; // 下一个节点} dictEntry;

哈希算法原理

  • 当向字典中添加一个元素时（假设此时 rehashidx = -1，也就是没有进行rehash），首先通过hashFunction计算该元素的hash值，然后通过index=hash&sizemask。如果该元素对应的下标没有数据，则直接添加，否则采用链地址法添加到hash对应index元素的链表尾部。

哈希冲突

  • 哈希表实际上是一个数组，数组里多每一个元素就是一个哈希桶。桶里面装着链表来解决哈希冲突。
  • Redis 采用了「链式哈希」的方法来解决哈希冲突。

链式哈希实现方式

  • 每个哈希表节点都有一个 next 指针，用于指向下一个哈希表节点，因此多个哈希表节点可以用 next 指针构成一个单项链表，被分配到同一个哈希桶上的多个节点可以用这个单项链表连接起来，这样就解决了哈希冲突。

渐进式rehash原理

  • 渐进式rehash核心：定时迁移+顺带迁移

  1. 为ht[1]分配空间，让字典同时持有ht[0]和ht[1]两个哈希表

  2. 将rehashindex的值设置为0，表示rehash工作正式开始

  3. 在rehash期间，每次对字典执行增删改查操作是，程序除了执行指定的操作以外，还会顺带将ht[0]哈希表在rehashindex索引上的所有键值对rehash到ht[1]，当rehash工作完成以后，rehashindex的值+1

  4. 随着字典操作的不断执行，最终会在某一时间段上ht[0]的所有键值对都会被rehash到ht[1]，这时将rehashindex的值设置为-1，表示rehash操作结束

  5. 渐进式rehash采用的是一种分而治之的方式，将rehash的操作分摊在每一个的访问中，避免集中式rehash而带来的庞大计算量。

注意：

  • 在渐进式rehash的过程，如果有增删改查操作时，如果index大于rehashindex，访问ht[0]，否则访问ht[1]
  • 新表的大小为第一个大于等于原表2倍used的2次方幂。
  • 移动完一个index里面的entry list，就把rehashIndex++。
  • 假设现在需要迁移table[0]上的某一个数据，迁移的是bucket,该bucket上的整条链表上的元素全部迁移过去。

问题

多线程问题：rehashidx = 9, 线程1：在对idx10的list进行写操作。线程2：在rehash idx10的list会不会丢失数据。还是说redis里面也有锁机制。

  • Redis的多线程部分只是用来处理网络数据的读写和协议分析（网络处理是瓶颈），对于redis的读写命令，依然是单线程处理(因为单线程实现简单，而且不需要考虑线程安全问题)

扩容时机

  • 负载因子k=ht[0].used/ht[0].size 使用空间和总空间的大小比例
    • k >= 1时，空间已经紧张，越来越多的数据无法在O(1)时间复杂度找到，还需要遍历一次链表，如果此时服务器没有执行BGSAVE或BGREWRITEAOF这两个复制命令，就会发生扩容。
    • k > 5,此时即使有复制命令进行，也要进行Rehash扩容

注意：如果进程正在执行BGSAVE或BGREWRITEAOF这两个复制命令，就会创建新的子进程，此时如果进行扩展哈希表，那么相当于往父进程写入数据，同时会导致子进程进行复制操作。

缩容

  • Redis使用负载因子控制缩容，当负载因此小于0.1，即负载率小于10%，此时进行缩容，信标大小为第一个大于等于原表used的2次方幂。

应用场景

  • Set 类型比较适合用来数据去重和保障数据的唯一性，还可以用来统计多个集合的交集、错集和并集等

1. 点赞

  • Set 类型可以保证一个用户只能点一个赞
# uid:1 用户对文章 article:1 点赞> SADD article:1 uid:1(integer) 1# uid:2 用户对文章 article:1 点赞> SADD article:1 uid:2(integer) 1# uid:3 用户对文章 article:1 点赞> SADD article:1 uid:3(integer) 1

2. 共同关注

  • Set 类型支持交集运算，所以可以用来计算共同关注的好友、公众号等。
  • key 可以是用户id，value 则是已关注的公众号的id。
# uid:1 用户关注公众号 id 为 5、6、7、8、9> SADD uid:1 5 6 7 8 9(integer) 5# uid:2用户关注公众号 id 为 7、8、9、10、11> SADD uid:2 7 8 9 10 11(integer) 5# 获取共同关注> SINTER uid:1 uid:21) "7"2) "8"3) "9"'给 uid:2 推荐 uid:1 关注的公众号：'> SDIFF uid:1 uid:21) "5"2) "6"

3. 抽奖活动

  • Set 类型因为有去重功能，可以保证同一个用户不会中奖两次。
>SADD lucky Tom Jerry John Sean Marry Lindy Sary Mark(integer) 5'重复抽奖'# 抽取 1 个一等奖：> SRANDMEMBER lucky 11) "Tom"# 抽取 2 个二等奖：> SRANDMEMBER lucky 21) "Mark"2) "Jerry"# 抽取 3 个三等奖：> SRANDMEMBER lucky 31) "Sary"2) "Tom"3) "Jerry"'不重复抽奖'# 抽取一等奖1个> SPOP lucky 11) "Sary"# 抽取二等奖2个> SPOP lucky 21) "Jerry"2) "Mark"# 抽取三等奖3个> SPOP lucky 31) "John"2) "Sean"3) "Lindy"

HSet

  • HSET是HASH字典，可以存储多个field（集合） – value映射关系，但是都为string的hash表，存储在Redis的内存中。适用于O(1)的时间查找

底层数据结构

  • HSET底层有俩种编码结构：压缩列表和HASHTABLE
  • 当HSET对象保存的所有值和键的长度都小于64字节，并且HSET对象元素个数少于512个时，使用压缩列表。
  • 当上述两个条件任何一条不满足时，编码结构就用HASHTABLE。

    压缩列表
  • 数据量较小时将数据紧凑排列，对应到HSET，就是将filed-value当作entry放入压缩列表。

HASHTABLE

  • HASHTABLE在之前无序集合Set中也有应用，和Set区别，在于，Set中的value始终为NULL（因为Set中只存储一个值），但是在HSET中，是有对应值的。