本文是Redis成本优化系列文章的第3篇，讲述了hashtable的相关优化。

一、几个实验

hash相关配置
before 7.0
hash-max-ziplist-entries:512
hash-max-ziplist-value:64

after 7.0
hash-max-listpack-entries 512
hash-max-listpack-value 64
如下三个场景，hash的内部实现都是hashtable，而不是ziplist：

1.写入100万条hash键值对：key为37字节(hash-32字节uuid)、2对field(f0、f1)-value(100字节)

2. 写入1万条hash键值对：key为37字节(hash-32字节uuid)、514对field(f0..f513)-value(5字节)

3. 写入1万条hash键值对：key为37字节(hash-32字节uuid)、514对field(f0..f513)-value(100字节)

初步结论：

• 2.8到3.0：hashtable容量无变化
• 3.0到3.2：优化来源于sdshdr拆分，详见[Redis成本优化-版本升级-1.SDS优化历史]
• 3.2到4.0：优化来源于复杂数据架构中的元素去掉robj，详见[Redis成本优化-版本升级-2.复杂数据结构robj优化
• 4.0->5.0->6.0->6.2：无容量变化

• 7.0：在实验1和实验场景2下容量有一定程度缩减（8%、14%）

  二、7.0已知hash优化：dict结构简化

  dict是Redis的基础数据结构，Redis的全部键值、过期键值、hash|set|zset数据结构均用到了dict，Redis 7做了重要优化：
  来源：Significant memory savings in case of many hash or zset keys (#9228)

  1 优化前的dict结构

  7.0之前：dict内部包含了两个dictht
  

相关代码：

typedef struct dictht {  
dictEntry **table;  
unsigned long size;  
unsigned long sizemask;  
unsigned long used;  

} dictht;

typedef struct dict {

dictType *type;  
void *privdata;  
dictht ht[2];  
long rehashidx;  
int16_t pauserehash;  

} dict;

2 Redis 7.0的相关优化

• 去掉privdata
• 去掉dictht，相关元数据放到了dict中。
  

相关代码变为：

struct dict {  
dictType *type;  
dictEntry **ht_table[2];  
unsigned long ht_used[2];  
long rehashidx;  
int16_t pauserehash;  
signed char ht_size_exp[2];   

};

• dictht ht[2]用dictEntry **ht_table[2]代替
• 原来两个dictht的used用unsigned long ht_used[2]代替

• 原来两个dictht的size用signed char ht_size_exp[2]代替，且由8个字节变为1个字节，计算方法如下：
  #define DICTHT_SIZE(exp) ((exp) == -1 ? 0 : (unsigned long)1<<(exp))

  define DICTHT_SIZE_MASK(exp) ((exp) == -1 ? 0 : (DICTHT_SIZE(exp))-1)

  3. github上的相关效果：

  通过数据结构的优化（96->56字节），必然会在hash|set|zset key较多且为小value时，效果更为明显。由于要对单一功能进行测试，所以这里直接使用PR中的测试结果（https://github.com/redis/redis/pull/9228），
  (1) 内存优化：提升较为明显

  original dict	original dict	optimized dict
  1000000 65 byte one field hashes	290.38M	252.23M
  1000 hashes with 1000 20 byte fields	62.22M	62.1M
  1000000 sets with 1 1 byte entry	214.84M	176.69M
  dict struct size (theoretical improvement)	96b	56b

  
  

  (2) 性能变化：除了get random keys外，其他整体有提升。

  dict benchmark 10000000	Inserting	Linear access of existing	2nd round	Random access of existing	Accessing random keys	Accessing missing	Removing and adding
  original	5371	2531	2507	4135	1447	2893	4882
  optimized	5253	2488	2481	4076	1600	2841	4801
  improvement	2.20%	1.70%	1.04%	1.43%	-10.57%	1.80%	1.66%

  
  

  三、Redis 7.0 hash其他优化？

  1. 问题分析

  

按照上一节分析，我们可以计算下相关实验

• 实验1：1000000(key) * (96-56) = 38.14MB (基本符合预期)

• 实验2、3：10000(key) * (96-56) = 0.38MB ，完全不符合预期！
  翻遍了Redis 7 release notes好像没发现其他hash优化，并且对测试程序多次测试，数值上没什么异常!

  2. 问题定位

  我们对实验2中的hash key进行debug可以发现
  (1) 针对每个hash key， Redis 6.2.5会比Redis 7.0.12的table size大512个，也就是512*8字节(指针) = 4KB，针对上述实验二正好吻合。
  10000个hash * 4KB 约等于 40MB

• Redis 6.2.15正在进行rehash，table size = 512 + 1024
  Redis:6.2.15> debug HTSTATS-KEY hash-c25f6e05-8cd7-4c00-9776-d1d53e3e3b00
  Hash table 0 stats (main hash table):
  table size: 512
  number of elements: 509
  different slots: 325
  max chain length: 6
  avg chain length (counted): 1.57
  avg chain length (computed): 1.57
  Chain length distribution:
  0: 187 (36.52%)
  1: 200 (39.06%)
  2: 83 (16.21%)
  3: 30 (5.86%)
  4: 8 (1.56%)
  5: 3 (0.59%)
  6: 1 (0.20%)
  Hash table 1 stats (rehashing target):
  table size: 1024
  number of elements: 5
  different slots: 4
  max chain length: 2
  avg chain length (counted): 1.25
  avg chain length (computed): 1.25
  Chain length distribution:
  0: 1020 (99.61%)
  1: 3 (0.29%)
  2: 1 (0.10%)
• Redis 7.0.12只用了一个dictht, table size=1024
  Hash table 0 stats (main hash table):
  table size: 1024
  number of elements: 514
  different slots: 395
  max chain length: 4
  avg chain length (counted): 1.30
  avg chain length (computed): 1.30
  Chain length distribution:
  0: 629 (61.43%)
  1: 296 (28.91%)
  2: 81 (7.91%)
  3: 16 (1.56%)
  4: 2 (0.20%)
  (2) 相关优化：https://github.com/redis/redis/pull/8943
  

每次对hash类型(当前是ziplist实现)进行添加元素时，会进行元素个数的检测，当ziplist的长度 > hash-max-ziplist-entries时，会将其转成一个hashtable
t_hash(before 7.0)：具体方法是创建一个空的dict然后逐个遍历ziplist执行dictAdd，在这个过程中会触发到rehash(512这个元素这个点，有关rehash可以参考Redis开发规范解析(三)--一个Redis最好存多少key)，所以hash的内部实现有两个dictht。

void hashTypeConvertZiplist(robj *o, int enc) {  
serverAssert(o->encoding == OBJ_ENCODING_ZIPLIST);  

if (enc == OBJ_ENCODING_HT) {

    hashTypeIterator *hi;  
    dict *dict;  
    int ret;  
    hi = hashTypeInitIterator(o);  
    dict = dictCreate(&hashDictType, NULL);  
    while (hashTypeNext(hi) != C_ERR) {  
        sds key, value;  
        key = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_KEY);  
        value = hashTypeCurrentObjectNewSds(hi,OBJ_HASH_VALUE);  
        ret = dictAdd(dict, key, value);  
        if (ret != DICT_OK) {  
            //忽略内容  
        }  
    }  
    hashTypeReleaseIterator(hi);  
    zfree(o->ptr);  
    o->encoding = OBJ_ENCODING_HT;  
    o->ptr = dict;  
}  

}
t_hash(after 7.0)：提前进行扩容，所以只有一个dictht

3. 问题验证

(1) 如果514对换成1023对呢？可以看到7.0相比6.2并无优化

3. 写入1万条hash键值对：key为37字节、1023对field(f0..f1022)-value(5字节)

Redis:6.2.15> debug htstats-key hash-aa51a2cd-21d9-4ce1-9440-77b4ef5863c6  

Hash table 0 stats (main hash table):
table size: 1024
number of elements: 1023
different slots: 654
max chain length: 5
avg chain length (counted): 1.56
avg chain length (computed): 1.56
Chain length distribution:
0: 370 (36.13%)
1: 397 (38.77%)
2: 166 (16.21%)
3: 73 (7.13%)
4: 15 (1.46%)
5: 3 (0.29%)

Redis:7.0.12> debug htstats-key hash-ed298442-e907-4736-bf0b-57fb0578b12e
Hash table 0 stats (main hash table):
table size: 1024
number of elements: 1023
different slots: 639
max chain length: 5
avg chain length (counted): 1.60
avg chain length (computed): 1.60
Chain length distribution:
0: 385 (37.60%)
1: 364 (35.55%)
2: 191 (18.65%)
3: 60 (5.86%)
4: 23 (2.25%)
5: 1 (0.10%)
(2) 实验2中，如果我们重启6.0.15、6.2.15版本呢？会发现内存消耗也会减少大约40MB

四、总结：

Redis 7针对hashtable结构的成本优化有两个

• 精简了dict结构，使得每个dict可以减少40字节，在有大量小hash、小zset的场景下有较大优化
• 优化了ziplist转hashtable时候可能产生的rehash，这个优化就一行代码，比较隐蔽，在特殊场景下也能取得不错的优化。