redis容量评估模型

发表于2017-07-11
评论0 414浏览

想免费获取内部独家PPT资料库?观看行业大牛直播?点击加入腾讯游戏学院游戏美术行业精英群

167422913
业务侧申请redis服务器资源时,需要事先对redis容量做一个大致评估,之前的容量评估公式基本只是简单的(key长度 value长度)* key个数,误差较大,后期经常需要进行缩扩容调整,因此提出一个较精确的redis容量评估模型就显得很有必要。 Ps:本文所用的redis版本为2.4.8,不同版本的redis所用底层数据结构可能会有所不同,请知悉。


一、redis常用数据结构

做容量评估之前,有必要对redis常用数据结构有大概了解。

1、SDS

redis没有直接使用c语言传统的字符串(以空字符为结尾的字符数组),而是自己创建了一种名为SDS(简单动态字符串)的抽象类型,用作redis默认的字符串。

SDS的定义如下(sds.h/sdshdr):

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

 下图1展示了一个SDS实例:

图1. SDS示例图

 图1的SDS实例中存储了字符串“Redis”, sdshdr中对应的free长度为5len长度5 SDS占用的总字节数为sizeof(int) * 2 5 5 1 = 19。

2、链表

链表在redis中的应用非常广泛,列表键的底层实现之一就是链表。每个链表节点使用一个listNode结构来表示,具体定义如下(adlist.h/listNode):

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

 redis另外还使用了list结构来管理链表,以方便操作,具体定义如下(adlist.h/list):

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;

 listNode结构占用的总字节数为24,list结构占用的总字节数为48。

3、跳跃表

redis采用跳跃表(skiplist)作为有序集合键的底层实现之一,跳跃表是一种有序数据结构,它通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。

跳跃表由redis.h/zskiplistNode和redis.h/zskiplist两个结构定义,zskiplistNode结构具体定义如下:

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

跳跃表可以理解为多层的有序双向链表,zskiplistNode结构用于表示跳跃表节点,obj属性和score属性分别表示具体的值对象和对应的排序分值,backward属性和forward属性分别表示后退和前进指针,和普通链表不同,前进指针可以直接指向后续第n个节点,两个节点之间的距离用span属性表示。每个跳跃表节点的level数组大小不定,当节点新生成时,程序都会根据幂次定律(power low,越大的数出现的概率越小)随机生成一个介于1和32之间的值作为level数组的大小。zskiplistNode结构占用的总字节数为(24 16*n),n为level数组的大小。

zskiplist结构具体定义如下:

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

 zskiplist结构则用于保存跳跃表节点的相关信息,header和tail分别指向跳跃表的表头和表尾节点,length记录节点总数量,level记录跳跃表中层高最大的那个节点的层数量。zskiplist结构占用的总字节数为32。

下图2展示了一个跳跃表示例:

图2. 跳跃表示例图

位于图片最左边的是zskiplist结构,位于zskiplist结构右边的是四个zskiplistNode结构,header指向跳跃表的表头节点,表头节点和其他节点的构造是一样的,但后退指针、分值、成员对象这些属性都不会被用到,所以被省略,只显示其各个层。

4、字典

字典在redis中的应用很广泛,redis的数据库就是使用字典作为底层实现的,具体数据结构定义如下(dict.h/dict):

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

 type属性和privdata属性是为了针对不同类型的键值对而设置的,此处了解即可。dict中还保存了一个长度为2dictht哈希表数组,哈希表负责保存具体的键值对,一般情况下字典只使用ht[0]哈希表,只有在rehash时才使用ht[1]。dict结构占用的总节数为88。

字典所使用的哈希表dictht结构定义如下(dict.h/dictht):

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

 table属性是一个数组,数组中每个元素都是一个指向dictEntry结构的指针,每个dictEntry结构就是一个哈希表节点,保存一个具体的键值对。size记录了哈希表总大小,used记录了哈希表已有节点的数量,sizemark值总是等于size -1,它和哈希值一起决定每个键的索引。dictht结构占用的总节数为32。

哈希节点使用dictEntry结构表示,具体定义如下(dict.h/dictEntry):

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个数 * 指针大小

测试验证

hash类型容量评估测试脚本如下:

#!/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"

测试用例中,key长度为 12,field长度为14,value长度为75,key个数为200,field个数为200,根据上面总结的容量评估模型,容量预估值为[(16 16 32 96 32)* 200 256 * 8 96 16 32 32 ] * 200 256 * 8 = 8126848

运行测试脚本,得到结果如下:

结果相差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个数 * 指针大小

测试验证

zset类型容量评估测试脚本如下:

#!/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"

测试用例中,key长度为 12,value长度为75,key个数为200,value个数为200,根据上面总结的容量评估模型,容量预估值为[(96 16 53.336 32)* 200 256 * 8 640 32 96 16 16 32 32 ] * 200 256 * 8 = 8477888

运行测试脚本,得到结果如下:

结果相差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个数 * 指针大小

测试验证

list类型容量评估测试脚本如下:

#!/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"

测试用例中,key长度为 12,value长度为75,key个数为200,value个数为200,根据上面总结的容量评估模型,容量预估值为[(96 16 32)* 200 48 16 32 32 ] * 200 256 * 8 = 5787648

运行测试脚本,得到结果如下:

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

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引

游戏学院公众号二维码
腾讯游戏学院
微信公众号

提供更专业的游戏知识学习平台