背景

• 我们有一个类似用户中心，其中有百万级别用户以user_id + id号为key存放在redis中。有一个需求是将user_为前缀进行匹配查询进行key的匹配，就在进行这个的操作命令的时候出现服务卡顿和redis 有部分链接超时。最后排查出来的问题所在就是keys的时候查出来的key太多导致的问题。具体原因那就从他这个命令的原理看起
• 最后的解决方案是：使用scan命令

Keys

简介

1. 通过简单的正则就可以进行模糊匹配，没有分页，没有游标。就是暴力查找遍历。
2. 好处就是方便，坏处应有仅有，redis是单线程的，那就是如果说我这个线程查询的内容过多，导致查询时间很长就会出现其他线程的阻塞，或者超时的问题。查询的时间复杂度是O（n）

Scan

简介

1. scan 复杂度为O（n）可带游标进行分步进行查询，不会阻塞线程
2. 可以进行模糊匹配和keys一样，只不过每一次都要带上一次返回的游标，可以使用limit限制最大条数，有可能少但是不会超过（http://doc.redisfans.com/key/scan.html#scan）
3. 每次根据游标返回的数据有可能为空也有可能为多个。只要返回的游标不为0，就不代表数据没有了。
4. 但是问题还是有的，就是有可能返回重复的key值这个得我们应用程序进行一次去重，可以使用set进行存储或者Map
   因为他两的数据结构本身就是不可以重复的。

SCAN 内部探究

1. redis 的全局就是使用的是key-value形式存储，使用的也就是他底层的数据结构dict字典。字典内部存储和java中的hashmap差不多，其底层都是通过数组和链表实现的。

2. 在dict中我们所存储的key就是底下的数组下标，数组下表是通过计算hash值出来的。正是因为有了hash冲突也就有了链表。

3. 在使用scan的时候我们其中scan的游标就是数组的下标，因为在存储的时候进行的是计算hash后进行存储，所以在数组上不是顺序存储，所以在一段数组上有可能有值也有可能没有值。也有可能一个slot上有多个值。所以这就是scan为什么会在增量式的过程中出现多个和0个的原因，如下图
   

4. 如果说按数组的下标顺序便利下去那要是扩容了怎么办，因为扩容之后需要进行进行重新hash，数组下标的位置就会改变，那么这个过程中我们我们在扩容之前scan返回的游标就不准确了吗？

5. redis处理扩容下表的方案是：它不是从第一维数组的第 0 位一直遍历到末尾，而是采用
   了高位进位加法来遍历。之所以使用这样特殊的方式进行遍历，是考虑到字典的扩容和缩容
   时避免槽位的遍历重复和遗漏。

6. 选择高位进位加法的主要原因还是他进行扩容的特点，和hashMap的差不多，采用的是：
   *Java 中的 HashMap 有扩容的概念，当 loadFactor 达到阈值时，需要重新分配一个新的
   2 倍大小的数组，然后将所有的元素全部 rehash 挂到新的数组下面。rehash 就是将元素的
   hash 值对数组长度进行取模运算，因为长度变了，所以每个元素挂接的槽位可能也发生了变
   化。又因为数组的长度是 2n（我们在进行扩容的时候其容量都为2n的原因） 次方，所以取模运算等价于位与操作。
   

抽象一点说，假设开始槽位的二进制数是 xxx，那么该槽位中的元素将被 rehash 到
0xxx 和 1xxx(xxx+8) 中。 如果字典长度由 16 位扩容到 32 位，那么对于二进制槽位
xxxx 中的元素将被 rehash 到 0xxxx 和 1xxxx(xxxx+16) 中。*

a mod 8 = a & (8-1) = a & 7
a mod 16 = a & (16-1) = a & 15
a mod 32 = a & (32-1) = a & 31

如下图就是缩容和扩容的一个对比

 

所以说redis采用了高位进位加法来遍历的。

return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); Java 1.8计算hash的方法

7. 还有就是在进行扩容的时候，会进行copy和rehash，redis的数据量会很大，所以一次性进行rehash会出现卡顿问题。所以redis采用的是渐进式的rehash。也就是不一次性进行rehash 而是慢慢的继续进行，所以这也是scan乎过程中得注意的，也就新老dict 都进行扫描，最后合并返回。
8. 我们可以再想想keys 是不是就不用考虑以上问题呢？，因为他是每次都是全量扫，不担心扩容了等问题。

总结

1. redis scan 和 keys的使用
2. scan的内部扫描介绍
3. dict的基本数据结构和扩容的大概过程