struct sdshdr { int len; // 记录buf数组中已使用字节的数量 int free; // 记录buf数组中未使用字节的数量 char buf[]; // 字节数组，用于保存实际字符串 }

typedef struct listNode { struct listNode *prev; // 前置节点 struct listNode *next; // 后置节点 void *value; // 节点的值 } listNode;

typedef struct list {
    listNode *head; // 表头节点 listNode *tail; // 表尾结点 void *(*dup)(void *ptr); // 节点值复制函数 void (*free)(void *ptr); // 节点值释放函数 int (*match)(void *ptr, void *key); // 节点值对比函数 unsigned int len; // 链表所包含的节点数量 } list;

typedef struct zskiplistNode {
    robj *obj; // 成员对象 double score; // 成员对象分值 struct zskiplistNode *backward; // 后退指针 struct zskiplistLevel // 节点层 { struct zskiplistNode *forward; // 前进指针 unsigned int span; // 跨度 } level[];
} zskiplistNode;

typedef struct zskiplist { struct zskiplistNode *header, *tail; // 表头节点和表尾结点 unsigned long length; // 表中节点的数量 int level; // 表中层数最大的节点的层数 } zskiplist;

typedef struct dict {
    dictType *type; // 字典类型 void *privdata; // 私有数据 dictht ht[2]; // 哈希表数组 int rehashidx; // rehash索引，当不进行rehash时，值为-1 int iterators; // 当前该字典迭代器个数 } dict;

typedef struct dictht {
    dictEntry **table; // 哈希表节点数组 unsigned long size; // 哈希表大小 unsigned long sizemask; // 哈希表大小掩码，用于计算索引值，总是等于size-1 unsigned long used; // 该哈希表已有节点的数量 } dictht;

typedef struct dictEntry { void *key; void *val; struct dictEntry *next;
} dictEntry;

redis的哈希表采用链地址法来解决哈希冲突问题，多个哈希值相同的键值对通过链表连接在一起。dictEntry结构占用的总字节数为24。

字典的整体结构关系如下图3所示：

图3. 字典整体结构关系图

随着哈希表保存的键值对逐渐增多，哈希表中每个桶的冲突链会越来越长，为了让哈希表的负载因子维持在一个合理范围，redis会自动通过rehash的方式扩展哈希表。rehash的过程大概就是先为ht[1]分配对应的空间，然后将ht[0]中的所有节点转移到ht[1]中，最后再释放ht[0]所占用的空间。rehash后新生成的dictEntry节点数组大小等于超过当前key个数向上求整的2的n次方，比如当前key个数为100，则新生成的节点数组大小就是128。

5、对象

前面介绍了redis的常用数据结构，但redis大多数情况下并没有直接使用这些数据结构来实现键值对数据库，而是基于这些数据结构创建了一个对象系统，每个对象都包含了一种具体数据结构。比如，当redis数据库新创建一个键值对时，就需要创建一个值对象，值对象的*ptr属性指向具体的SDS字符串。

每个对象都由一个redisObject结构表示，具体定义如下（redis.h/redisObject）：

typedef struct redisObject { unsigned type: 4; // 对象类型 unsigned storage: 2; // REDIS_VM_MEMORY or REDIS_VM_SWAPPING unsigned encoding: 4; // 对象所使用的编码 unsigned lru: 22; // lru time (relative to server.lruclock) int refcount; // 对象的引用计数 void *ptr; // 指向对象的底层实现数据结构 } robj;

 具体属性此处不再详细描述，只需知道redisObject结构占用的总字节数为16。

二、jemalloc内存分配规则

jemalloc是一种通用的内存管理方法，着重于减少内存碎片和支持可伸缩的并发性，我们部门的redis版本中就引入了jemalloc，做redis容量评估前必须对jemalloc的内存分配规则有一定了解。

jemalloc基于申请内存的大小把内存分配分为三个等级：small，large，huge：

• Small Object的size以8字节，16字节，32字节等分隔开，小于页大小；
• Large Object的size以分页为单位，等差间隔排列，小于chunk的大小；
• Huge Object的大小是chunk大小的整数倍。

对于64位系统，一般chunk大小为4M，页大小为4K，内存分配的具体规则如下：

三、redis容量评估

redis容量评估模型根据key类型而有所不同。

1、string

一个简单的set命令最终会产生4个消耗内存的结构，中间free掉的不考虑：

• 1个dictEntry结构，24字节，负责保存具体的键值对；
• 1个redisObject结构，16字节，用作val对象；
• 1个SDS结构，（key长度 9）字节，用作key字符串；
• 1个SDS结构，（val长度 9）字节，用作val字符串；

当key个数逐渐增多，redis还会以rehash的方式扩展哈希表节点数组，即增大哈希表的bucket个数，每个bucket元素都是个指针（dictEntry*），占8字节，bucket个数是超过key个数向上求整的2的n次方。

真实情况下，每个结构最终真正占用的内存还要考虑jemalloc的内存分配规则，综上所述，string类型的容量评估模型为：

总内存消耗 = （dictEntry大小 redisObject大小 key_SDS大小 val_SDS大小）* key个数 bucket个数 * 指针大小

string类型容量评估测试脚本如下：

#!/bin/sh  old_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "before test, memory used: $old_memory" for((i=1000; i<3000; i  )) do ./redis-cli -h 0 -p 10009 set test_key_$i test_value_$i > /dev/null sleep 0.2 done new_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "after test, memory used: $new_memory" let difference=new_memory-old_memory echo "difference is: $difference"

测试用例中，key长度为 13，value长度为15，key个数为2000，根据上面总结的容量评估模型，容量预估值为2000 * （32 16 32 32） 2048 * 8 = 240384

运行测试脚本，得到结果如下：

结果都是240384，说明模型预估的十分精确。

2、hash

哈希对象的底层实现数据结构可能是zipmap或者hashtable，当同时满足下面这两个条件时，哈希对象使用zipmap这种结构（此处列出的条件都是redis默认配置，可以更改）：

• 哈希对象保存的所有键值对的键和值的字符串长度都小于64字节；
• 哈希对象保存的键值对的数量都小于512个；

可以看出，业务侧真实使用场景基本都不能满足这两个条件，所以哈希类型大部分都是hashtable结构，因此本篇文章只讲hashtable，对zipmap结构感兴趣的同学可以私下咨询我。

与string类型不同的是，hash类型的值对象并不是指向一个SDS结构，而是指向又一个dict结构，dict结构保存了哈希对象具体的键值对，hash类型结构关系如图4所示：

 图4. hash类型结构关系图

一个hmset命令最终会产生以下几个消耗内存的结构：

• 1个dictEntry结构，24字节，负责保存当前的哈希对象；
• 1个SDS结构，（key长度 9）字节，用作key字符串；
• 1个redisObject结构，16字节，指向当前key下属的dict结构；
• 1个dict结构，88字节，负责保存哈希对象的键值对；
• n个dictEntry结构，24*n字节，负责保存具体的field和value，n等于field个数；
• n个redisObject结构，16*n字节，用作field对象；
• n个redisObject结构，16*n字节，用作value对象；
• n个SDS结构，（field长度 9）*n字节，用作field字符串；
• n个SDS结构，（value长度 9）*n字节，用作value字符串；

因为hash类型内部有两个dict结构，所以最终会有产生两种rehash，一种rehash基准是field个数，另一种rehash基准是key个数，结合jemalloc内存分配规则，hash类型的容量评估模型为：

总内存消耗 = [（redisObject大小 * 2 field_SDS大小  val_SDS大小  dictEntry大小）* field个数 field_bucket个数 * 指针大小 dict大小 redisObject大小 key_SDS大小 dictEntry大小 ] * key个数 key_bucket个数 * 指针大小

测试验证

#!/bin/sh  value_prefix="test_value_123456789012345678901234567890123456789012345678901234567890_" old_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "before test, memory used: $old_memory" for((i=100; i<300; i  )) do for((j=100; j<300; j  )) do ./redis-cli -h 0 -p 10009 hset test_key_$i test_field_$j $value_prefix$j > /dev/null done sleep 0.5 done new_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "after test, memory used: $new_memory" let difference=new_memory-old_memory echo "difference is: $difference"

结果相差40，说明模型预测比较准确。

3、zset

同哈希对象类似，有序集合对象的底层实现数据结构也分两种：ziplist或者skiplist，当同时满足下面这两个条件时，有序集合对象使用ziplist这种结构（此处列出的条件都是redis默认配置，可以更改）：

• 有序集合对象保存的元素数量小于128个；
• 有序集合保存的所有元素成员的长度都小于64字节；

业务侧真实使用时基本都不能同时满足这两个条件，因此这里只讲skiplist结构的情况。skiplist类型的值对象指向一个zset结构，zset结构同时包含一个字典和一个跳跃表，占用的总字节数为16，具体定义如下（redis.h/zset）：

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

跳跃表按分值从小到大保存了所有集合元素，每个跳跃表节点都保存了一个集合元素，dict字典为有序集合创建了一个从成员到分值的映射，字典中的每个键值对都保存了一个集合元素，这两种数据结构会通过指针来共享相同元素的成员和分值，没有浪费额外的内存。zset类型的结构关系如图5所示：

图5. zset类型结构关系图

一个zadd命令最终会产生以下几个消耗内存的结构：

• 1个dictEntry结构，24字节，负责保存当前的有序集合对象；
• 1个SDS结构，（key长度 9）字节，用作key字符串；
• 1个redisObject结构，16字节，指向当前key下属的zset结构；
• 1个zset结构，16字节，负责保存下属的dict和zskiplist结构；
• 1个dict结构，88字节，负责保存集合元素中成员到分值的映射；
• n个dictEntry结构，24*n字节，负责保存具体的成员和分值，n等于集合成员个数；
• 1个zskiplist结构，32字节，负责保存跳跃表的相关信息；
• 1个32层的zskiplistNode结构，24 16*32=536字节，用作跳跃表头结点；
• n个zskiplistNode结构，（24 16*m）*n字节，用作跳跃表节点，m等于节点层数；
• n个redisObject结构，16*n字节，用作集合中的成员对象；
• n个SDS结构，（value长度 9）*n字节，用作成员字符串；

因为每个zskiplistNode节点的层数都是根据幂次定律随机生成的，而容量评估需要确切值，因此这里采用概率中的期望值来代替单个节点的大小，结合jemalloc内存分配规则，经计算，单个zskiplistNode节点大小的期望值为53.336。

zset类型内部同样包含两个dict结构，所以最终会有产生两种rehash，一种rehash基准是成员个数，另一种rehash基准是key个数，zset类型的容量评估模型为：

总内存消耗 = [（val_SDS大小  redisObject大小  zskiplistNode大小  dictEntry大小）* value个数 value_bucket个数 * 指针大小 32层zskiplistNode大小  zskiplist大小  dict大小 zset大小 redisObject大小 key_SDS大小 dictEntry大小 ] * key个数 key_bucket个数 * 指针大小

测试验证

#!/bin/sh  value_prefix="test_value_123456789012345678901234567890123456789012345678901234567890_" old_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "before test, memory used: $old_memory" for((i=100; i<300; i  )) do for((j=100; j<300; j  )) do ./redis-cli -h 0 -p 10009 zadd test_key_$i $j $value_prefix$j > /dev/null done sleep 0.5 done new_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "after test, memory used: $new_memory" let difference=new_memory-old_memory echo "difference is: $difference"

结果相差672，说明模型预测比较准确。

4、list

列表对象的底层实现数据结构同样分两种：ziplist或者linkedlist，当同时满足下面这两个条件时，列表对象使用ziplist这种结构（此处列出的条件都是redis默认配置，可以更改）：

• 列表对象保存的所有字符串元素的长度都小于64字节；
• 列表对象保存的元素数量小于512个；

因为实际使用情况，这里同样只讲linkedlist结构。linkedlist类型的值对象指向一个list结构，具体结构关系如图6所示：

图6. linkedlist类型结构关系图

一个rpush或者lpush命令最终会产生以下几个消耗内存的结构：

• 1个dictEntry结构，24字节，负责保存当前的列表对象；
• 1个SDS结构，（key长度 9）字节，用作key字符串；
• 1个redisObject结构，16字节，指向当前key下属的list结构；
• 1个list结构，48字节，负责管理链表节点；
• n个listNode结构，24*n字节，n等于value个数；
• n个redisObject结构，16*n字节，用作链表中的值对象；
• n个SDS结构，（value长度 9）*n字节，用作值对象指向的字符串；

list类型内部只有一个dict结构，rehash基准为key个数，综上，list类型的容量评估模型为：

总内存消耗 = [（val_SDS大小  redisObject大小  listNode大小）* value个数   list大小    redisObject大小 key_SDS大小 dictEntry大小 ] * key个数 key_bucket个数 * 指针大小

测试验证

#!/bin/sh  value_prefix="test_value_123456789012345678901234567890123456789012345678901234567890_" old_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "before test, memory used: $old_memory" for((i=100; i<300; i  )) do for((j=100; j<300; j  )) do ./redis-cli -h 0 -p 10009 rpush test_key_$i $value_prefix$j > /dev/null done sleep 0.5 done new_memory=`./redis-cli -h 0 -p 10009 info|grep used_memory:|awk -F: '{printf "%d", $2}'` echo "after test, memory used: $new_memory" let difference=new_memory-old_memory echo "difference is: $difference"

运行测试脚本，得到结果如下：

结果都是5787648，说明模型预估的十分精确。