去年我写过一个《阿里云Redis开发规范》&＃xff0c;在网上转载很多&＃xff0c;但其实说心里话&＃xff0c;我并不认为写的多好&＃xff0c;受制一些客观因素和篇幅&＃xff0c;有些不够细致和深入&＃xff0c;所以想在公众号里详细解析下&＃xff0c;希望对大家有帮助。
本篇是第三篇&＃xff1a;一个Redis实例存储多少个键值对比较合适。
无原文
这个在当时的文章里没有讨论&＃xff0c;因为这个问题很难绝对化&＃xff0c;但背后的知识还是很有讨论价值的&＃xff0c;我们来看一段对话&＃xff1a;
解析
一、存在哪&＃xff1f;
1. 哈希表(hashtable)
要知道能存多少&＃xff0c;首先要知道Redis的键值对存在哪&＃xff1f;你可能已经猜到了哈希表&＃xff0c;它是天然的键值对数据结构&＃xff0c;各种语言都支持该数据结构&＃xff0c;基本上是使用数组链表的形式实现的(JDK 8用的红黑树)&＃xff0c;下面是一个整体结构。
dictEntry存储的是实际键值对&＃xff0c;它的的结构定义如下所示:
typedef struct dictEntry {
void *key;
union {
void *val;
uint64_t u64;
int64_t s64;
double d;
} v;
struct dictEntry *next;
} dictEntry;
dictht是哈希表&＃xff0c;它的定义如下&＃xff1a;
typedef struct dictht {
//dictEntry数组链表
dictEntry **table;
//数组的长度
unsigned long size;
//数组掩码&＃xff0c;等于size-1
unsigned long sizemask;
//键值个数
unsigned long used;
} dictht;
2.键值"路由"
对于一个key&＃xff0c;首先会通过哈希算法(见下面提示)计算它的哈希值&＃xff0c;然后与sizemask做&计算(等价于与size做%计算)&＃xff0c;算出所在的数组下标(index)&＃xff0c;然后生成dictEntry插入其中。
index &＃61; dictHashKey(key) & sizemask &＃61; dictHashKey(key) % size
其中哈希算法在Redis版本中也有迭代&＃xff1a;
提&＃xff1a;提示&＃xff1a;Redis 4开始使用siphash算法代替murmur2算法。
murmur2算法已经证实会受到HashDos的攻击(可以简单理解为破坏哈希的均匀性)。
bug detail&＃xff1a;https://paper.seebug.org/180/
假如我向一个空的Redis执行了一条如下命令&＃xff1a;
127.0.0.1:6379> set hello world
OK
首先Redis会使用siphash算法计算"hello"的哈希值&＃xff0c;然后与sizemask做&计算。
siphashKey("hello") & 3 &＃61; 984616787 & 3 &＃61; 3
计算出"hello"所对应的数组下标是3&＃xff0c;如下所示&＃xff1a;
注意kv里面不是直接存字符串&＃xff0c;k是sds,v是redisObject。
3.冲突处理
那么问题来了&＃xff0c;如果一个新的key算出的数组下标已经包含了其他dictEntry&＃xff0c;那么该如何处理呢&＃xff1f;这就要引出冲突处理问题&＃xff0c;实际上这个问题的处理方式也很简单&＃xff0c;因为每个数组下标对应的是一个链表&＃xff0c;如果发生冲突&＃xff0c;只需要把新的key对应dictEntry挂在链表的第一个位置即可(因为是新插入的&＃xff0c;可能马上会用到)&＃xff0c;例如插入两条数据后&＃xff1a;
4.扩缩容(rehash)
接下来问题又来了&＃xff0c;单纯依赖链表做冲突处理&＃xff0c;链表会越来越长&＃xff0c;读写效率会差&＃xff0c;所以需要对哈希表做扩容&＃xff0c;对于Redis来说&＃xff0c;一个哈希数据结构内置了两个哈希表(dictht)&＃xff0c;一个用于使用&＃xff0c;另一个平时闲置&＃xff0c;待时机成熟&＃xff0c;扩容一倍&＃xff0c;然后将数据迁移到另一个哈希表内&＃xff0c;如下图所示&＃xff1a;
typedef struct dict {
dictType *type;
void *privdata;
dictht ht[2];
long rehashidx; /* rehashing not in progress if rehashidx &＃61;&＃61; -1 */
unsigned long iterators; /* number of iterators currently running */
} dict;
其中rehashidx用来标识当前dict是否正在做rehash&＃xff0c;如果为-1表示没有做rehash。当used > 2^n时候&＃xff0c;就需要扩容了(rehashidx代表ht[0]在rehash时候所在的索引值)&＃xff0c;如下图所示。为了保证Redis单线程的高效性&＃xff0c;整个rehash是渐进式(一点点)完成的&＃xff0c;但全部迁移完成后&＃xff0c;将rehashidx置为-1&＃xff0c;表示rehash结束了。
对于key的路由来说&＃xff0c;它依然先从dict[0]去找&＃xff0c;如果找到了&＃xff0c;就顺便把它迁移到dict[1]。如果没找到就要从dict[1]去找。
二、能存多少呢&＃xff1f;
相信通过前面的介绍&＃xff0c;你已经对Redis的dict有了一定的认识&＃xff0c;如果现在有人问你一个Redis能存储多少个键值对&＃xff0c;相信这个问题不难回答了吧&＃xff0c;因为我们已经了解了Redis的哈希表实现方式&＃xff0c;知道size定义了数组的长度&＃xff0c;由于它是unsigned long类型(4个字节)&＃xff0c;所以Redis理论上可以存储2^32个元素(大约40亿个)。下面一段是官方的一段FAQ(引自&＃xff1a;https://redis.io/topics/faq)
What is the maximum number of keys a single Redis instance can hold?
Redis can handle up to 2^32 keys, and was tested in practice to
handle at least 250 million keys per instance.
从官方的回答可以看到&＃xff0c;Redis虽然可以承担2^32个(大约40亿个)键值对&＃xff0c;但是它建议你最佳实践是存放2.5亿个键值对&＃xff0c;没有给出具体的原因。
下面我们结合刚才介绍的内容大开脑洞想一下&＃xff1a;键值个数的增加可能会引发什么问题呢&＃xff1f;
三、可能引起的问题&＃xff1f;
1.rehash问题
通过前面的介绍&＃xff0c;相信你也简单了解了Redis的扩容是需要通过rehash来完成的&＃xff0c;也了解了扩容的相关机制&＃xff0c;但是一般来说很多人对于Redis中的这类机制只是浅尝辄止&＃xff0c;没有深层次的考虑。现实是残酷的&＃xff0c;下面我用一次我实际中遇到的问题来说明rehash可能带来的危险。
那是我在阿里云的时候&＃xff0c;有个客户反馈他的Redis内存突然涨了2GB&＃xff0c;如下图所示&＃xff1a;Redis实例的内存在一分钟内突然从7.46GB涨到9.46GB&＃xff0c;并持续了一段时间。
对于此类问题&＃xff0c;我们已经有了一套检测方式&＃xff1a;各类缓冲区检测、键值增长趋势、大键值、Lua引擎内存等等&＃xff0c;但我们进行了一轮检测后&＃xff0c;均未发现异常(注释&＃xff1a;当时使用的Redis 3.0&＃xff0c;内存统计信息不是很全)。经同事提醒后发现可能是rehash造成的&＃xff0c;于是抱着尝试的心态做了试验。
如下面的代码所示&＃xff0c;我向一个空的Redis写入简单的键值对&＃xff0c;2^n是rehash的临界点&＃xff0c;在临界点附近放慢键值的写入速度。
public static void testRehash(int n) {
//rehash的临界点
int rehashThreshold &＃61; (int) Math.pow(2, n);
//临界点左右的偏移量&＃xff0c;用于观察数据
int offset &＃61; 10;
for (int i &＃61; 0; i
jedis.set(String.valueOf(i), String.valueOf(i));
//用于观察临界点内存的变化。
if (i > rehashThreshold - offset) {
TimeUnit.SECONDS.sleep(1);
}
}
}
Redis的官方客户端redis-cli提供了一个简单的选项--stat用于定时观察Redis相关状态的变化。
(1) 当n&＃61;15时&＃xff0c;可以观察到&＃xff1a;当keys超过32768(2^15)时&＃xff0c;内存突然从3.45M涨到了3.70M。
redis-cli -h 127.0.0.1 -p 6379 --stat
keys mem clients blocked requests connections
32767 3.45M 2 0 1230010 (&＃43;2) 13
32768 3.45M 2 0 1230012 (&＃43;2) 13
32769 3.70M 2 0 1230014 (&＃43;2) 13
32770 3.70M 2 0 1230016 (&＃43;2) 13
32771 3.70M 2 0 1230018 (&＃43;2) 13
32772 3.70M 2 0 1230020 (&＃43;2) 13
(2) 当n&＃61;20时&＃xff0c;可以观察到&＃xff1a;当keys超过1048576(2^20)时&＃xff0c;内存突然从88.70M涨到了104.70M。
keys mem clients blocked requests connections
1048574 88.70M 2 0 2278689 (&＃43;2) 16
1048575 88.70M 2 0 2278691 (&＃43;2) 16
1048576 88.70M 2 0 2278693 (&＃43;2) 16
1048577 104.70M 2 0 2278695 (&＃43;2) 16
1048578 104.70M 2 0 2278697 (&＃43;2) 16
1048579 104.70M 2 0 2278699 (&＃43;2) 16
(3) 当n&＃61;26时&＃xff0c;效果更加明显&＃xff0c;当keys超过67108864(2^26)后&＃xff0c;内存直接从5.50G增长到6.50G。
keys mem clients blocked requests connections
67108862 5.50G 2 0 2574533 (&＃43;2) 23
67108863 5.50G 2 0 2574535 (&＃43;2) 23
67108864 5.50G 2 0 2574537 (&＃43;2) 23
67108865 6.50G 2 0 2574539 (&＃43;2) 23
67108866 6.50G 2 0 2574541 (&＃43;2) 23
67108867 6.50G 2 0 2574543 (&＃43;2) 23
再结合一下当时客户Redis的键值变化&＃xff0c;基本可以确定是由rehash造成的内存异常增长。至此我们已经分析出内存突然增长的原因。(过期键值的dictht也有1G的消耗)
dict: 67108864 * 16字节(dictEntry) &＃61; 1GB
expires: 67108864 * 16字节(dictEntry) &＃61; 1GB
但是还有更糟糕的情况&＃xff0c;如果内存暴增的一瞬间超过了Redis设置的最大内存&＃xff0c;不仅会产生大量的数据逐&＃xff0c;而且会造成客户端产生大量的超时。下面我们用一个例子来具体说明。
现在我们将Redis设置最大使用内存为6GB&＃xff0c;并设置最大内存淘汰策略是allkeys-lru。
127.0.0.1:6379> config set maxmemory 6GB
OK
127.0.0.1:6379> config set maxmemory-policy allkeys-lru
OK
127.0.0.1:6379> config rewrite
OK
我们继续设置n&＃61;26运行上述程序&＃xff0c;会发现在rehash临界点瞬间(67108864)&＃xff0c;redis-cli --stat会卡住&＃xff0c;过一段时间后内存虽然也增长了&＃xff0c;但是发现key大量丢失(rehash完成&＃xff0c;但是rehash一瞬间内存的使用已经超过maxmemory&＃xff0c;触发了maxmemory-policy)&＃xff0c;而且又长时间的卡顿&＃xff0c;如果放在生产环境&＃xff0c;如果对QPS要求很高的核心业务&＃xff0c;很可能就是一次事故。
67108862 5.50G 2 0 2710190 (&＃43;2) 26
67108863 5.50G 2 0 2710192 (&＃43;2) 26
67108864 5.50G 2 0 2710194 (&＃43;2) 26
&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;这里redis-cli --stat停顿&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;&＃61;
61202597 5.56G 2 0 2710196 (&＃43;2) 26
61202598 5.56G 1 0 2710198 (&＃43;2) 26
61202598 5.56G 1 0 2710199 (&＃43;1) 26
61202598 5.56G 1 0 2710200 (&＃43;1) 26
下表是每个n对应的键值个数和rehash瞬间的内存额外开销&＃xff1a;
| n | 键值个数 | rehash容量 |
|---|
| 20 | 1048576(百万) | 16MB |
| 26 | 67108864(千万) | 1GB |
| 27 | 134217728(亿) | 2GB |
| 28 | 268435456(亿) | 4GB |
2.小键值和分片过大问题
你可能经常听到一个建议&＃xff0c;Redis的分片(maxmemory)不要设置过大&＃xff0c;一般建议最大不要超过8G,这里面原因很多&＃xff1a;
(1) bgsave和bgrewriteaof要在主线程执行fork操作&＃xff0c;分片越大&＃xff0c;执行时间越长&＃xff0c;阻塞Redis可能性越大。
(2) 分片越大&＃xff0c;RDB落盘、网络传输、加载时间都是会较长&＃xff0c;对于CPU、网络、磁盘IO的开销也会越大。
这些内容在后面的持久化文章中都会有介绍&＃xff0c;那我们来看一下在不同键值个数、value字节数大小下&＃xff0c;内存的开销总和&＃xff0c;所以键值个数自己可以掂量下
| 类型 | 8字节 | 50字节 | 100字节 | 500字节 | 1KB |
|---|
| 10万 | 8.7MB | 12MB | 18MB | 56MB | 105MB |
| 100万 | 78MB | 116MB | 169MB | 550MB | 1.01GB |
| 500万 | 448M | 667MB | 980MB | 3.1G | 5.75GB |
| 1000万 | 790MB | 1.2GB | 1.7GB | 5.5GB | 10GB |
| 1亿 | 8GB | 12GB | 17GB | 55GB | 100GB |
3.死键问题
Redis将所有键值对保存dict中&＃xff0c;除此之外还有一个dict *expires用来保存过期键&＃xff0c;用于标记设置了过期时间的键值&＃xff0c;整个定义如下&＃xff1a;
typedef struct redisDb {
dict *dict; /* The keyspace for this DB */
dict *expires; /* Timeout of keys with a timeout set */
......
} redisDb;
Redis有两种过期键值处理机制&＃xff1a;
(1) 主动过期&＃xff1a;访问key时&＃xff0c;先去expires表访问&＃xff0c;如果发现已经过期就删除掉。 (2) 被动过期&＃xff1a;通过某种机制定期抽样扫描expires表&＃xff0c;如果发现过期就删除。
其中详细的机制这里就不多做介绍了&＃xff0c;而这个定时任务也是在Redis的单线程中完成的。也就是说&＃xff0c;如果执行过于频繁&＃xff0c;会影响Redis的性能&＃xff1b;但是如果执行不频繁的话&＃xff0c;会使得大量该过期的数据没有过期&＃xff0c;造成内存浪费。这种现象被称为“死键问题”。
如果键值数量过多&＃xff0c;并设置了过期时间&＃xff0c;很可能出现类似问题。从我的实际经验来看&＃xff0c;一旦键值个数超过千万级别&＃xff0c;就会有这样的情况发生&＃xff0c;下图中的下面两个节点是经过scan后的Redis实例&＃xff0c;可以发现内存量和键值个数急剧减少。
4.数据剔除问题
Redis有最大内存淘汰机制(maxmemory-policy)&＃xff0c;如果键值个数过多&＃xff0c;那么可能逐出的就会更多&＃xff0c;也就意味段时间内有大量的删除操作&＃xff0c;甚至会造成Redis段时间不可用&＃xff0c;如下图所示&＃xff1a;
总结&＃xff1a;
本文首先通过Redis到底能存储多少个键值对&＃xff0c;引出Redis的Hash表实现方式(数组链表)、扩缩容等原理&＃xff0c;最后通过一个开脑洞的思考探讨&＃xff0c;分析了各种利弊&＃xff0c;最终讨论Redis到底存储多少个键值对会比较好(最多千万级别)。
附图一张&＃xff1a;
欢迎订阅我的公众号(Redis开发运维实战)&＃xff1a;关注Redis开发运维实战相关问题&＃xff0c;干掉所有的坑。
京公网安备 11010802041100号