我们来看一段对话：

一、存在哪？

1. 哈希表(hashtable)

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

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

typedefstruct dictEntry {void*key;union{void*val;uint64_t u64;int64_t s64;double d;} v;struct dictEntry *next;} dictEntry;

typedef
struct
 dictht {








//dictEntry数组链表




    dictEntry **table;








//数组的长度




unsigned
long
 size;








//数组掩码，等于size-1




unsigned
long
 sizemask;








//键值个数




unsigned
long
 used;




} dictht;

2.键值"路由"

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

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

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

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




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








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

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

127.0.0.1:6379> set hello worldOK

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

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

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

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

3.冲突处理

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

4.扩缩容(rehash)

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

typedefstruct dict {    dictType *type;void*privdata;    dictht ht[2];long rehashidx; /* rehashing not in progress if rehashidx == -1 */unsignedlong iterators; /* number of iterators currently running */} dict;

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

二、能存多少呢？

相信通过前面的介绍，你已经对Redis的dict有了一定的认识，如果现在有人问你一个Redis能存储多少个键值对，相信这个问题不难回答了吧，因为我们已经了解了Redis的哈希表实现方式，知道size定义了数组的长度，由于它是unsigned long类型（4个字节），所以Redis理论上可以存储2^32个元素（大约40亿个）。下面一段是官方的一段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.

从官方的回答可以看到，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的临界点，在临界点附近放慢键值的写入速度。

publicstaticvoid testRehash(int n) {//rehash的临界点int rehashThreshold = (int) Math.pow(2, n);//临界点左右的偏移量，用于观察数据int offset = 10;for(int i = 0; i < rehashThreshold + offset; i++) {        jedis.set(String.valueOf(i), String.valueOf(i));//用于观察临界点内存的变化。if(i > rehashThreshold - offset) {TimeUnit.SECONDS.sleep(1);}}}

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

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

redis-cli -h 127.0.0.1-p 6379--statkeys       mem      clients blocked requests            connections327673.45M201230010(+2)        13327683.45M201230012(+2)        13327693.70M201230014(+2)        13327703.70M201230016(+2)        13327713.70M201230018(+2)        13327723.70M201230020(+2)        13

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

keys       mem      clients blocked requests            connections104857488.70M202278689(+2)        16104857588.70M202278691(+2)        16104857688.70M202278693(+2)        161048577104.70M202278695(+2)        161048578104.70M202278697(+2)        161048579104.70M202278699(+2)        16

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

keys       mem      clients blocked requests            connections671088625.50G202574533(+2)        23671088635.50G202574535(+2)        23671088645.50G202574537(+2)        23671088656.50G202574539(+2)        23671088666.50G202574541(+2)        23671088676.50G202574543(+2)        23

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

dict: 67108864* 16字节(dictEntry) = 1GBexpires: 67108864* 16字节(dictEntry) = 1GB

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

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

127.0.0.1:6379> config set maxmemory 6GBOK127.0.0.1:6379> config set maxmemory-policy allkeys-lruOK127.0.0.1:6379> config rewriteOK

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

671088625.50G202710190(+2)        26671088635.50G202710192(+2)        26671088645.50G202710194(+2)        26======================这里redis-cli --stat停顿======================612025975.56G202710196(+2)        26612025985.56G102710198(+2)        26612025985.56G102710199(+1)        26612025985.56G102710200(+1)        26

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

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

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

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

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

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

3.死键问题

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

typedefstruct redisDb {    dict *dict;    /* The keyspace for this DB */    dict *expires; /* Timeout of keys with a timeout set */......} redisDb;

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

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

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

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

4.数据剔除问题

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

总结：

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