一、Redis rehash问题回顾

简单回顾下超出key阈值后，需要额外的hash表内存大小：

随着key个数越多，rehash需要的额外内存也越大，所带来的可用性风险(大量逐出，Redis同步)和数据丢失(逐出)风险也越高。

二、Redis 6.2&7+ Rehash相关优化

Redis 6.2后对Rehash做了相关优化：

Limit the main db dictionaries expansion to prevent key eviction (
#7954)

  In the past big dictionary rehashing could result 
in massive data eviction.Now this rehashing is delayed (up to a 
limit), 
which can result 
in performance loss due to 
hash collisions.

简单翻译：

在大的
hash表(键值数多)场景下，
rehash会延迟执行防止大量数据丢失和可用性问题。

三、实验

1. 版本选择

• Redis 6.0.15

• Redis 7.0.11

2. 实验条件

• maxmemory = 5.6GB
• 第一次灌入：67,100,000个key，观察内存
• 第二次灌入：2,000,000个key，观察可用性和逐出

3. 开始实验

(1) Redis 6.0.15

第一次灌入：67,100,000个key，观察内存：

maxmemory:         5.6GB

used_memory_human: 5.5GB

dbsize:            67,100,000  

第二次灌入：2,000,000个key，观察可用性和逐出

• 客户端执行超时， 超时近30秒以上，redis-cli --latency-history

  min: 0, max: 1, avg: 0.06 (1485 samples) -- 15.01 seconds range
  
  min: 0, max: 36511, avg: 45.63 (801 samples) -- 44.61 seconds range
  
  

• 逐出大量key：500万以上

evicted_keys:5,909,376

• 峰值内存：rehash多了一个GB

used_memory_peak_human:6.50G

(2) Redis 7.0.11

第一次灌入：67,100,000个key，观察内存：

maxmemory:         5.6GB

used_memory_human: 5.5GB

dbsize:            67,100,000  

第二次灌入：2,000,000个key，观察可用性和逐出

• 客户端执行无超时，redis-cli --latency-history

  min: 0, max: 2, avg: 0.05 (1484 samples) -- 15.01 seconds range
  
  min: 0, max: 3, avg: 0.24 (1454 samples) -- 15.00 seconds range
  
  

• 正常逐出 （还剩0.1GB）

evicted_keys:152485

evicted_keys:443253

evicted_keys:751165

evicted_keys:1058191

evicted_keys:1367445

evicted_keys:1662485

evicted_keys:1662485

• 峰值内存：没有进行rehash

used_memory_peak_human:5.50G

4. 实验对比

四、代码解析

1. dict：

新加的expandAllowed，决定dict当前是否做rehash

typedef struct dictType {

   ....

    int (*expandAllowed)(size_t moreMem, double usedRatio);

  ....

} dictType;

dict在做扩容时候会加入新的判断dictTypeExpandAllowed

/* Expand the 
hash table 
if needed */

static int _dictExpandIfNeeded(dict *d)

{

   ......

    
if (!dictTypeExpandAllowed(d))

        
return DICT_OK;

    ......

}

若dict的expandAllowed为空则允许rehash，否则执行expandAllowed

static int dictTypeExpandAllowed(dict *d) {

    
if (d->
type->expandAllowed == NULL) 
return 1;

    
return d->
type->expandAllowed(

                    DICTHT_SIZE(_dictNextExp(d->ht_used[0] + 1)) * sizeof(dictEntry*),

                    (double)d->ht_used[0] / DICTHT_SIZE(d->ht_size_exp[0]));

}

2. redis的dict

redis的dbDictType和dbExpiresDictType

/* Db->dict, keys are sds strings, vals are Redis objects. */

dictType dbDictType = {

    dictSdsHash,                /* 
hash 
function */

    NULL,                       /* key dup */

    NULL,                       /* val dup */

    dictSdsKeyCompare,          /* key compare */

    dictSdsDestructor,          /* key destructor */

    dictObjectDestructor,       /* val destructor */

    dictExpandAllowed,          /* allow to expand */

    dictEntryMetadataSize       /* size of entry metadata 
in bytes */

};



/* Db->expires */

dictType dbExpiresDictType = {

    dictSdsHash,                /* 
hash 
function */

    NULL,                       /* key dup */

    NULL,                       /* val dup */

    dictSdsKeyCompare,          /* key compare */

    NULL,                       /* key destructor */

    NULL,                       /* val destructor */

    dictExpandAllowed           /* allow to expand */

};

可以看到：

• dict使用率大于hash负载因子：可以做rehash
• dict使用率小于hash负载因子：
• 如果maxmemory=0，可以做rehash
• 如果当前使用内存 + rehash需要内存小于maxmemory，可以做rehash
• 如果当前对象内存(使用内存 - 额外内存(各种缓冲区))  + rehash需要内存小于maxmemory，可以做rehash

int dictExpandAllowed(size_t moreMem, double usedRatio) {

    
if (usedRatio <= HASHTABLE_MAX_LOAD_FACTOR) {

        
return !overMaxmemoryAfterAlloc(moreMem);

    } 
else {

        
return 1;

    }

}



/* Return 1 
if used memory is more than maxmemory after allocating more memory,

 * 
return 0 
if not. Redis may reject user
's requests or evict some keys if used

 * memory exceeds maxmemory, especially, when we allocate huge memory at once. */

int overMaxmemoryAfterAlloc(size_t moremem) {

    if (!server.maxmemory) return  0; /* No limit. */



    /* Check quickly. */

    size_t mem_used = zmalloc_used_memory();

    if (mem_used + moremem <= server.maxmemory) return 0;



    size_t overhead = freeMemoryGetNotCountedMemory();

    mem_used = (mem_used > overhead) ? mem_used - overhead : 0;

    return mem_used + moremem > server.maxmemory;

}

五、结论

• Redis6.2+以上版本有效解决了rehash在大dict下产生的可用性和逐出问题
• Redis7目前已经比较稳定(2022年4月release)，目前已经在线上大量使用7.0.11。
• 新版本只是做了rehash的延迟处理，并不是不再做rehash了，由于负载因子可能产生的性能问题需要适度关注。
• Redis6.2+对逐出也做了一定优化，后续将进行介绍：Incremental eviction processing