Redis成本优化-版本升级-3.hashtable优化

字数 8553阅读 556评论 0赞 3

内容摘要：

Redis7.0.12优化hashtable结构，精简dict结构，优化ziplist转hashtable时的rehash，实现性能和内存的提升。

当前摘要为AI生成

本文是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.8.24 | 3.0.7 | 3.2.13 | 4.0.14 | 5.0.14 | 6.0.20 | 6.2.15 | 7.0.12 |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| 容量MB | 603.15 | 603.15 | 549.75 | 488.77 | 488.77 | 488.77 | 488.77 | 450.71 |
##### 2. 写入1万条hash键值对：key为37字节(hash-32字节uuid)、514对field(f0..f513)-value(5字节)
| 版本 | 2.8.24 | 3.0.7 | 3.2.13 | 4.0.14 | 5.0.14 | 6.0.15 | 6.2.15 | 7.0.12 |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| 容量MB | 589.94 | 589.94 | 511.29 | 315.27 | 315.27 | 315.27 | 315.27 | 275.90 |
##### 3. 写入1万条hash键值对：key为37字节(hash-32字节uuid)、514对field(f0..f513)-value(100字节)
| 版本 | 2.8.24 | 3.0.7 | 3.2.13 | 4.0.14 | 5.0.14 | 6.0.15 | 6.2.15 | 7.0.12 |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| 容量MB | 1060.52 | 1060.52 | 981.87 | 825.07 | 825.07 | 825.07 | 825.07 | 824.76 |
#### 初步结论：
* 2.8到3.0：hashtable容量无变化
* 3.0到3.2：优化来源于sdshdr拆分，详见[[Redis成本优化-版本升级-1.SDS优化历史](https://www.talkwithtrend.com/Article/268453 "[Redis成本优化-版本升级-1.SDS优化历史")]

* 3.2到4.0：优化来源于复杂数据架构中的元素去掉robj，详见[[Redis成本优化-版本升级-2.复杂数据结构robj优化](https://www.talkwithtrend.com/Article/268455 "[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
![](/home/attachment/202311/06/923323_169925488889723.png)

相关代码：
    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中。
![](/home/attachment/202311/06/923323_169925490568439.png)

相关代码变为：
    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. 问题分析
![](/home/attachment/202311/06/923323_169925496988134.png)

按照上一节分析，我们可以计算下相关实验
* 实验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
![](/home/attachment/202311/06/923323_169925502282481.png)

每次对hash类型(当前是ziplist实现)进行添加元素时，会进行元素个数的检测，当ziplist的长度 > hash-max-ziplist-entries时，会将其转成一个hashtable
t_hash(before 7.0)：具体方法是创建一个空的dict然后逐个遍历ziplist执行dictAdd，在这个过程中会触发到rehash(512这个元素这个点，有关rehash可以参考[Redis开发规范解析(三)--一个Redis最好存多少key](https://mp.weixin.qq.com/s?__biz=Mzg2NTEyNzE0OA==&mid=2247483696&idx=1&sn=e4eb640cc657e55e35e89660bde59d99&scene=21#wechat_redirect))，所以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
![](/home/attachment/202311/06/923323_169925503820902.png)

#### 3. 问题验证
(1) 如果514对换成1023对呢？可以看到7.0相比6.2并无优化
##### 3. 写入1万条hash键值对：key为37字节、1023对field(f0..f1022)-value(5字节)
|     | 2.8.24 | 3.0.7 | 3.2.13 | 4.0.14 | 5.0.14 | 6.0.15 | 6.2.15 | 7.0.12 |
| ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ | ------------ |
| 容量MB | 1016.85 | 1016.85 | 862.32 | 470.38 | 470.38 | 470.38 | 470.38 | 470.04 |
    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，这个优化就一行代码，比较隐蔽，在特殊场景下也能取得不错的优化。

Redis

著作权归作者所有

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

添加新评论0 条评论

Ctrl+Enter 发表

匿名评论

Redis成本优化-版本升级-3.hashtable优化

添加新评论0 条评论

文章目录展开目录

作者其他文章

相关文章

相关问题

相关资料