carlosfu
作者carlosfu2021-09-29 10:47
软件开发工程师, 快手

Redis开发规范解析(三)--一个Redis最好存多少key

字数 6928阅读 776评论 0赞 0

这个在当时的文章里没有讨论,因为这个问题很难绝对化,但背后的知识还是很有讨论价值的,我们来看一段对话:

解析

一、存在哪?

1. 哈希表(hashtable)

要知道能存多少,首先要知道Redis的键值对存在哪?你可能已经猜到了哈希表,它是天然的键值对数据结构,各种语言都支持该数据结构,基本上是使用数组链表的形式实现的(JDK 8用的红黑树),下面是一个整体结构。

dictEntry存储的是实际键值对,它的的结构定义如下所示:

  1. typedef struct dictEntry {
  2. void *key;
  3. union {
  4. void *val;
  5. uint64_t u64;
  6. int64_t s64;
  7. double d;
  8. } v;
  9. struct dictEntry *next;
  10. } dictEntry;

dictht是哈希表,它的定义如下:

  1. typedef struct dictht {
  2. //dictEntry数组链表
  3. dictEntry **table;
  4. //数组的长度
  5. unsigned long size;
  6. //数组掩码,等于size-1
  7. unsigned long sizemask;
  8. //键值个数
  9. unsigned long used;
  10. } dictht;

2.键值"路由"

对于一个key,首先会通过哈希算法(见下面提示)计算它的哈希值,然后与sizemask做&计算(等价于与size做%计算),算出所在的数组下标(index),然后生成dictEntry插入其中。

  1. index = dictHashKey(key) & sizemask = dictHashKey(key) % size

其中哈希算法在Redis版本中也有迭代:

提:提示:Redis 4开始使用siphash算法代替murmur2算法。

murmur2算法已经证实会受到HashDos的攻击(可以简单理解为破坏哈希的均匀性)。

  1. bug detail:https://paper.seebug.org/180/

假如我向一个空的Redis执行了一条如下命令:

  1. 127.0.0.1:6379> set hello world
  2. OK

首先Redis会使用siphash算法计算"hello"的哈希值,然后与sizemask做&计算。

  1. siphashKey("hello") & 3 = 984616787 & 3 = 3

计算出"hello"所对应的数组下标是3,如下所示:

  1. 注意kv里面不是直接存字符串,k是sds,v是redisObject。

3.冲突处理

那么问题来了,如果一个新的key算出的数组下标已经包含了其他dictEntry,那么该如何处理呢?这就要引出冲突处理问题,实际上这个问题的处理方式也很简单,因为每个数组下标对应的是一个链表,如果发生冲突,只需要把新的key对应dictEntry挂在链表的第一个位置即可(因为是新插入的,可能马上会用到),例如插入两条数据后:

4.扩缩容(rehash)

接下来问题又来了,单纯依赖链表做冲突处理,链表会越来越长,读写效率会差,所以需要对哈希表做扩容,对于Redis来说,一个哈希数据结构内置了两个哈希表(dictht),一个用于使用,另一个平时闲置,待时机成熟,扩容一倍,然后将数据迁移到另一个哈希表内,如下图所示:

  1. typedef struct dict {
  2. dictType *type;
  3. void *privdata;
  4. dictht ht[2];
  5. long rehashidx; / rehashing not in progress if rehashidx == -1 /
  6. unsigned long iterators; / number of iterators currently running /
  7. } dict;

其中rehashidx用来标识当前dict是否正在做rehash,如果为-1表示没有做rehash。当used > 2^n时候,就需要扩容了(rehashidx代表ht[0]在rehash时候所在的索引值),如下图所示。为了保证Redis单线程的高效性,整个rehash是渐进式(一点点)完成的,但全部迁移完成后,将rehashidx置为-1,表示rehash结束了。

对于key的路由来说,它依然先从dict[0]去找,如果找到了,就顺便把它迁移到dict[1]。如果没找到就要从dict[1]去找。

二、能存多少呢?

相信通过前面的介绍,你已经对Redis的dict有了一定的认识,如果现在有人问你一个Redis能存储多少个键值对,相信这个问题不难回答了吧,因为我们已经了解了Redis的哈希表实现方式,知道size定义了数组的长度,由于它是unsigned long类型(4个字节),所以Redis理论上可以存储2^32个元素(大约40亿个)。下面一段是官方的一段FAQ(引自:https://redis.io/topics/faq

  1. What is the maximum number of keys a single Redis instance can hold?
  2. Redis can handle up to 2^32 keys, and was tested in practice to
  3. handle at least 250 million keys per instance.

从官方的回答可以看到,Redis虽然可以承担2^32个(大约40亿个)键值对,但是它建议你最佳实践是存放2.5亿个键值对,没有给出具体的原因。

下面我们结合刚才介绍的内容大开脑洞想一下:键值个数的增加可能会引发什么问题呢?

三、可能引起的问题?

1.rehash问题

通过前面的介绍,相信你也简单了解了Redis的扩容是需要通过rehash来完成的,也了解了扩容的相关机制,但是一般来说很多人对于Redis中的这类机制只是浅尝辄止,没有深层次的考虑。现实是残酷的,下面我用一次我实际中遇到的问题来说明rehash可能带来的危险。

那是我在阿里云的时候,有个客户反馈他的Redis内存突然涨了2GB,如下图所示:Redis实例的内存在一分钟内突然从7.46GB涨到9.46GB,并持续了一段时间。

对于此类问题,我们已经有了一套检测方式:各类缓冲区检测、键值增长趋势、大键值、Lua引擎内存等等,但我们进行了一轮检测后,均未发现异常(注释:当时使用的Redis 3.0,内存统计信息不是很全)。经同事提醒后发现可能是rehash造成的,于是抱着尝试的心态做了试验。

如下面的代码所示,我向一个空的Redis写入简单的键值对,2^n是rehash的临界点,在临界点附近放慢键值的写入速度。

  1. public static void testRehash(int n) {
  2. //rehash的临界点
  3. int rehashThreshold = (int) Math.pow(2, n);
  4. //临界点左右的偏移量,用于观察数据
  5. int offset = 10;
  6. for (int i = 0; i < rehashThreshold + offset; i++) {
  7. jedis.set(String.valueOf(i), String.valueOf(i));
  8. //用于观察临界点内存的变化。
  9. if (i > rehashThreshold - offset) {
  10. TimeUnit.SECONDS.sleep(1);
  11. }
  12. }
  13. }

Redis的官方客户端redis-cli提供了一个简单的选项--stat用于定时观察Redis相关状态的变化。

(1) 当n=15时,可以观察到:当keys超过32768(2^15)时,内存突然从3.45M涨到了3.70M。

  1. redis-cli -h 127.0.0.1 -p 6379 --stat
  2. keys mem clients blocked requests connections
  3. 32767 3.45M 2 0 1230010 (+2) 13
  4. 32768 3.45M 2 0 1230012 (+2) 13
  5. 32769 3.70M 2 0 1230014 (+2) 13
  6. 32770 3.70M 2 0 1230016 (+2) 13
  7. 32771 3.70M 2 0 1230018 (+2) 13
  8. 32772 3.70M 2 0 1230020 (+2) 13

(2) 当n=20时,可以观察到:当keys超过1048576(2^20)时,内存突然从88.70M涨到了104.70M。

  1. keys mem clients blocked requests connections
  2. 1048574 88.70M 2 0 2278689 (+2) 16
  3. 1048575 88.70M 2 0 2278691 (+2) 16
  4. 1048576 88.70M 2 0 2278693 (+2) 16
  5. 1048577 104.70M 2 0 2278695 (+2) 16
  6. 1048578 104.70M 2 0 2278697 (+2) 16
  7. 1048579 104.70M 2 0 2278699 (+2) 16

(3) 当n=26时,效果更加明显,当keys超过67108864(2^26)后,内存直接从5.50G增长到6.50G。

  1. keys mem clients blocked requests connections
  2. 67108862 5.50G 2 0 2574533 (+2) 23
  3. 67108863 5.50G 2 0 2574535 (+2) 23
  4. 67108864 5.50G 2 0 2574537 (+2) 23
  5. 67108865 6.50G 2 0 2574539 (+2) 23
  6. 67108866 6.50G 2 0 2574541 (+2) 23
  7. 67108867 6.50G 2 0 2574543 (+2) 23

再结合一下当时客户Redis的键值变化,基本可以确定是由rehash造成的内存异常增长。至此我们已经分析出内存突然增长的原因。(过期键值的dictht也有1G的消耗)

  1. dict: 67108864 * 16字节(dictEntry) = 1GB
  2. expires: 67108864 * 16字节(dictEntry) = 1GB

但是还有更糟糕的情况,如果内存暴增的一瞬间超过了Redis设置的最大内存,不仅会产生大量的数据逐,而且会造成客户端产生大量的超时。下面我们用一个例子来具体说明。

现在我们将Redis设置最大使用内存为6GB,并设置最大内存淘汰策略是allkeys-lru。

  1. 127.0.0.1:6379> config set maxmemory 6GB
  2. OK
  3. 127.0.0.1:6379> config set maxmemory-policy allkeys-lru
  4. OK
  5. 127.0.0.1:6379> config rewrite
  6. OK

我们继续设置n=26运行上述程序,会发现在rehash临界点瞬间(67108864),redis-cli --stat会卡住,过一段时间后内存虽然也增长了,但是发现key大量丢失(rehash完成,但是rehash一瞬间内存的使用已经超过maxmemory,触发了maxmemory-policy),而且又长时间的卡顿,如果放在生产环境,如果对QPS要求很高的核心业务,很可能就是一次事故。

  1. 67108862 5.50G 2 0 2710190 (+2) 26
  2. 67108863 5.50G 2 0 2710192 (+2) 26
  3. 67108864 5.50G 2 0 2710194 (+2) 26
  4. ======================这里redis-cli --stat停顿======================
  5. 61202597 5.56G 2 0 2710196 (+2) 26
  6. 61202598 5.56G 1 0 2710198 (+2) 26
  7. 61202598 5.56G 1 0 2710199 (+1) 26
  8. 61202598 5.56G 1 0 2710200 (+1) 26

下表是每个n对应的键值个数和rehash瞬间的内存额外开销:

n键值个数rehash容量
201048576(百万)16MB
2667108864(千万)1GB
27134217728(亿)2GB
28268435456(亿)4GB

2.小键值和分片过大问题

你可能经常听到一个建议,Redis的分片(maxmemory)不要设置过大,一般建议最大不要超过8G,这里面原因很多:

(1) bgsave和bgrewriteaof要在主线程执行fork操作,分片越大,执行时间越长,阻塞Redis可能性越大。

(2) 分片越大,RDB落盘、网络传输、加载时间都是会较长,对于CPU、网络、磁盘IO的开销也会越大。

这些内容在后面的持久化文章中都会有介绍,那我们来看一下在不同键值个数、value字节数大小下,内存的开销总和,所以键值个数自己可以掂量下

类型8字节50字节100字节500字节1KB
10万8.7MB12MB18MB56MB105MB
100万78MB116MB169MB550MB1.01GB
500万448M667MB980MB3.1G5.75GB
1000万790MB1.2GB1.7GB5.5GB10GB
1亿8GB12GB17GB55GB100GB

3.死键问题

Redis将所有键值对保存dict中,除此之外还有一个dict *expires用来保存过期键,用于标记设置了过期时间的键值,整个定义如下:

  1. typedef struct redisDb {
  2. dict dict; / The keyspace for this DB */
  3. dict expires; / Timeout of keys with a timeout set */
  4. ......
  5. } redisDb;

Redis有两种过期键值处理机制:

(1) 主动过期:访问key时,先去expires表访问,如果发现已经过期就删除掉。 (2) 被动过期:通过某种机制定期抽样扫描expires表,如果发现过期就删除。

其中详细的机制这里就不多做介绍了,而这个定时任务也是在Redis的单线程中完成的。也就是说,如果执行过于频繁,会影响Redis的性能;但是如果执行不频繁的话,会使得大量该过期的数据没有过期,造成内存浪费。这种现象被称为“死键问题”。

如果键值数量过多,并设置了过期时间,很可能出现类似问题。从我的实际经验来看,一旦键值个数超过千万级别,就会有这样的情况发生,下图中的下面两个节点是经过scan后的Redis实例,可以发现内存量和键值个数急剧减少。

4.数据剔除问题

Redis有最大内存淘汰机制(maxmemory-policy),如果键值个数过多,那么可能逐出的就会更多,也就意味段时间内有大量的删除操作,甚至会造成Redis段时间不可用,如下图所示:

总结:

本文首先通过Redis到底能存储多少个键值对,引出Redis的Hash表实现方式(数组链表)、扩缩容等原理,最后通过一个开脑洞的思考探讨,分析了各种利弊,最终讨论Redis到底存储多少个键值对会比较好(最多千万级别)。

如果觉得我的文章对您有用,请点赞。您的支持将鼓励我继续创作!

0

添加新评论0 条评论

Ctrl+Enter 发表

作者其他文章

相关文章

相关问题

相关资料

X社区推广