深入Redis之内存模型1

阿里 阅读:201 2022-03-12 15:54:33 评论:0
1、前言
 
在客户端通过redis-cli连接服务器后(后面如无特殊说明,客户端一律使用redis-cli),通过info命令可以查看内存使用情况,如图:
其中,info命令可以显示redis服务器的许多信息,包括服务器基本信息、CPU、内存、持久化、客户端连接信息等等;memory是参数,表示只显示内存相关的信息。
 
返回结果中比较重要的几个说明如下:
 
(1)used_memory:Redis分配器分配的内存总量(单位是字节),包括使用的虚拟内存(即swap);注意used_memory_human只是显示更友好。
 
(2)used_memory_rss:Redis进程占据操作系统的内存(单位是字节),与top及ps命令看到的值是一致的;除了分配器分配的内存之外,used_memory_rss还包括进程运行本身需要的内存、内存碎片等,但是不包括虚拟内存。
 
因此,used_memory和used_memory_rss,前者是从Redis角度得到的量,后者是从操作系统角度得到的量。二者之所以有所不同,一方面是因为内存碎片和Redis进程运行需要占用内存,使得前者可能比后者小,另一方面虚拟内存的存在,使得前者可能比后者大。由于在实际应用中,Redis的数据量会比较大,此时进程运行占用的内存与Redis数据量和内存碎片相比,都会小得多;因此used_memory_rss和used_memory的比例,便成了衡量Redis内存碎片率的参数;这个参数就是mem_fragmentation_ratio。
 
(3)mem_fragmentation_ratio:内存碎片比率,该值是used_memory_rss / used_memory的比值。(>1时,说明多出的部分内存并没有用于数据存储,而是被内存碎片所消耗;<1时 ,说明可能是操作系统把Redis内存swap到磁盘导致。)
 
mem_fragmentation_ratio一般大于1,且该值越大,内存碎片比例越大。mem_fragmentation_ratio<1,说明Redis使用了虚拟内存,由于虚拟内存的媒介是磁盘,比内存速度要慢很多,当这种情况出现时,应该及时排查,如果内存不足应该及时处理,如增加Redis节点、增加Redis服务器的内存、优化应用等。
 
一般来说,mem_fragmentation_ratio在1.03左右是比较健康的状态(对于jemalloc来说);上面截图中的mem_fragmentation_ratio值很大,是因为还没有向Redis中存入数据,Redis进程本身运行的内存使得used_memory_rss 比used_memory大得多。
 
(4)mem_allocator:Redis使用的内存分配器,在编译时指定;可以是 libc 、jemalloc或者tcmalloc,默认是jemalloc;截图中使用的便是默认的jemalloc。
 
2、Redis内存划分
 
Redis作为内存数据库,在内存中存储的内容主要是键值对型数据;但是,除了数据以外,Redis的其他部分也会占用内存。Redis的内存占用主要可以划分为以下几个部分:
 
2.1、数据
作为数据库,数据是最主要的部分;这部分占用的内存会统计在used_memory中。
 
Redis使用键值对存储数据,其中的值(对象)包括5种类型,即字符串、哈希、列表、集合、有序集合。这5种类型是Redis对外提供的,实际上,在Redis内部,每种类型可能有2种或更多的内部编码实现;此外,Redis在存储对象时,并不是直接将数据扔进内存,而是会对对象进行各种包装:如redisObject、SDS等;
 
2.2、进程本身运行需要的内存
Redis主进程本身运行肯定需要占用内存,如代码、常量池等等;这部分内存大约几兆,在大多数生产环境中与Redis数据占用的内存相比可以忽略。这部分内存不是由jemalloc分配,因此不会统计在used_memory中。
 
补充说明:除了主进程外,Redis创建的子进程运行也会占用内存,如Redis执行AOF、RDB重写时创建的子进程。Redis执行 fork操作产生的子进程,内存占用量与父进程相同,理论上需要一倍的物理内存来完成重写操作。
 
当然,这部分内存不属于Redis进程,也不会统计在used_memory和used_memory_rss中。
 
2.3、缓冲内存
缓冲内存包括客户端缓冲区、复制积压缓冲区、AOF缓冲区等;其中:
  1. 客户端缓冲:存储客户端连接的输入输出缓冲;复制积压缓冲用于部分复制功能;
  2. 复制积压缓冲区:Redis在2.8版本之后提供了一个可重用的固定大小缓冲区,用于实现部分复制功能,根据 repl-backlog-size参数控制,默认1MB。对于复制积压缓冲区,只有Master节点存在,所有Slave节点共享此缓冲区。
  3. AOF缓冲区用于在进行AOF重写时,保存最近的写入命令,其消耗的内存取决于AOF重写时间和写入量,这部分空间占用通常很小。
 
这部分内存由jemalloc分配,因此会统计在used_memory中。
 
2.4、内存碎片
内存碎片是Redis在分配、回收物理内存过程中产生的。例如,如果对数据的更改频繁,而且数据之间的大小相差很大,可能导致redis释放的空间在物理内存中并没有释放,但redis又无法有效利用,这就形成了内存碎片。内存碎片不会统计在used_memory中。
 
内存碎片的产生与对数据进行的操作、数据的特点等都有关;此外,与使用的内存分配器也有关系:如果内存分配器设计合理,可以尽可能的减少内存碎片的产生。jemalloc便在控制内存碎片方面做的很好。
 
如果Redis服务器中的内存碎片已经很大,可以通过安全重启的方式减小内存碎片:因为重启之后,Redis重新从备份文件中读取数据,在内存中进行重排,为每个数据重新选择合适的内存单元,减小内存碎片。
 
3、Redis数据存储
 
3.1、概要
关于Redis数据存储的细节,涉及到内存分配器(如jemalloc)、简单动态字符串(SDS)、5种对象类型及内部编码、redisObject。在讲述具体内容之前,先说明一下这几个概念之间的关系。
下图是执行set hello world时,所涉及到的数据模型。
1、dictEntry:Redis是Key-Value数据库,因此对每个键值对都会有一个dictEntry,里面存储了指向Key和Value的指针;next指向下一个dictEntry,与本Key-Value无关。
 
2、Key:图中右上角可见,Key("hello")并不是直接以字符串存储,而是存储在SDS结构中(key)。
 
3、redisObject:Value("world")既不是直接以字符串存储,也不是像Key一样直接存储在SDS中,而是存储在redisObject中(value)。实际上,不论Value是5种类型的哪一种,都是通过redisObject来存储的;而redisObject中的type字段指明了Value对象的类型,ptr字段则指向对象所在的地址。不过可以看出,字符串对象虽然经过了redisObject的包装,但仍然需要通过SDS存储。实际上,redisObject除了type和ptr字段以外,还有其他字段图中没有给出,如用于指定对象内部编码的字段;后面会详细介绍。
 
4、jemalloc:无论是DictEntry对象,还是redisObject、SDS对象,都需要内存分配器(如jemalloc)分配内存进行存储。以DictEntry对象为例,有3个指针组成,在64位机器下占24个字节,jemalloc会为它分配32字节大小的内存单元。
 
3.2、内存分配器jemalloc
Redis在编译时便会指定内存分配器;内存分配器可以是 libc 、jemalloc或者tcmalloc,默认是jemalloc。jemalloc作为Redis的默认内存分配器,在减小内存碎片方面做的相对比较好。jemalloc在64位系统中,将内存空间划分为小、大、巨大三个范围;每个范围内又划分了许多小的内存块单位;当Redis存储数据时,会选择大小最合适的内存块进行存储。
 
jemalloc划分的内存单元如下图所示:
例如,如果需要存储大小为130字节的对象,jemalloc会将其放入160字节的内存单元中。
 
3.3、redisObject
前面说到,Redis对象有5种类型;无论是哪种类型,Redis都不会直接存储,而是通过redisObject对象进行存储。
 
redisObject对象非常重要,Redis对象的类型、内部编码、内存回收、共享对象等功能,都需要redisObject支持,下面将通过redisObject的结构来说明它是如何起作用的。
 
redisObject的定义如下(不同版本的Redis可能稍稍有所不同):
typedef struct redisObject { 
  unsigned type:4; 
  unsigned encoding:4; 
  unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */ 
  int refcount; 
  void *ptr; 
} robj; 

redisObject的每个字段的含义和作用如下:

 
3.3.1、type:对象的类型,占4个比特;目前包括REDIS_STRING(字符串)、REDIS_LIST (列表)、REDIS_HASH(哈希)、REDIS_SET(集合)、REDIS_ZSET(有序集合)。
当我们执行type命令时,便是通过读取RedisObject的type字段获得对象的类型;如下图所示:
 
3.3.2、encoding:对象的内部编码,占4个比特。对于Redis支持的每种类型,都有至少两种内部编码,例如对于字符串,有int、embstr、raw三种编码。通过encoding属性,Redis可以根据不同的使用场景来为对象设置不同的编码,大大提高了Redis的灵活性和效率。以列表对象为例,有压缩列表和双端链表两种编码方式;如果列表中的元素较少,Redis倾向于使用压缩列表进行存储,因为压缩列表占用内存更少,而且比双端链表可以更快载入;当列表对象元素较多时,压缩列表就会转化为更适合存储大量元素的双端链表。通过object encoding命令,可以查看对象采用的编码方式,如下图所示:
 
3.3.3、lru:lru记录的是对象最后一次被命令程序访问的时间,占据的比特数不同的版本有所不同(如4.0版本占24比特,2.6版本占22比特)。通过对比lru时间与当前时间,可以计算某个对象的空转时间;object idletime命令可以显示该空转时间(单位是秒)。object idletime命令的一个特殊之处在于它不改变对象的lru值。
lru值除了通过object idletime命令打印之外,还与Redis的内存回收有关系:如果Redis打开了maxmemory选项,且内存回收算法选择的是volatile-lru或allkeys—lru,那么当Redis内存占用超过maxmemory指定的值时,Redis会优先选择空转时间最长的对象进行释放内存空间。
 
3.3.4、refcount引用计数
 
refcount与共享对象:
 
refcount记录的是该对象被引用的次数,类型为整型。refcount的作用,主要在于对象的引用计数和内存回收。当创建新对象时,refcount初始化为1;当有新程序使用该对象时,refcount加1;当对象不再被一个新程序使用时,refcount减1;当refcount变为0时,对象占用的内存会被释放。
 
Redis中被多次使用的对象(refcount>1),称为共享对象。Redis为了节省内存,当有一些对象重复出现时,新的程序不会创建新的对象,而是仍然使用原来的对象。这个被重复使用的对象,就是共享对象。目前共享对象仅支持整数值的字符串对象。
 
共享对象的具体实现:
 
Redis的共享对象目前只支持整数值的字符串对象。之所以如此,实际上是对内存和CPU(时间)的平衡:共享对象虽然会降低内存消耗,但是判断两个对象是否相等却需要消耗额外的时间。对于整数值,判断操作复杂度为O(1);对于普通字符串,判断复杂度为O(n);而对于哈希、列表、集合和有序集合,判断的复杂度为O(n^2)。
 
虽然共享对象只能是整数值的字符串对象,但是5种类型都可能使用共享对象(如哈希、列表等的元素可以使用)。就目前的实现来说,Redis服务器在初始化时,会创建10000个字符串对象,值分别是0~9999的整数值;当Redis需要使用值为0~9999的字符串对象时,可以直接使用这些共享对象。10000这个数字可以通过调整参数REDIS_SHARED_INTEGERS(4.0中是OBJ_SHARED_INTEGERS)的值进行改变。
 
共享对象的引用次数可以通过object refcount命令查看,如下图所示。命令执行的结果页佐证了只有0~9999之间的整数会作为共享对象。
 
3.3.5、ptr:指向具体的数据,如前面的例子中,set hello world,ptr指向包含字符串world的SDS。
 
总结
综上所述,redisObject的结构与对象类型、编码、内存回收、共享对象都有关系;一个redisObject对象的大小为16字节:4bit+4bit+24bit+4Byte+8Byte=16Byte。
 
3.4、简单动态字符串SDS
 
Redis没有直接使用C字符串(即以空字符’\0’结尾的字符数组)作为默认的字符串表示,而是使用了SDS。SDS是简单动态字符串(Simple Dynamic String)的缩写。
 
1、SDS结构
sds的结构如下:
struct sdshdr { 
    int len;//已用长度 
    int free;//未使用长度 
    char buf[]; 
};
buf表示字节数组,用来存储字符串;len表示buf已使用的长度,free表示buf未使用的长度。下面是两个例子:
通过SDS的结构可以看出,buf数组的长度=free+len+1(其中1表示字符串结尾的空字符)。
所以,一个SDS结构占据的空间为:free所占长度+len所占长度+ buf数组的长度=4+4+free+len+1=free+len+9(字节)。
 
2、SDS与C字符串的比较
 
SDS在C字符串的基础上加入了free和len字段,带来了很多好处:
  • 获取字符串长度时间复杂度降低:SDS是O(1),C字符串是O(n)
  • 杜绝缓冲区溢出:使用C字符串的API时,如果字符串长度增加(如strcat操作)而忘记重新分配内存,很容易造成缓冲区的溢出;而SDS由于记录了长度,相应的API在可能造成缓冲区溢出时会自动重新分配内存,杜绝了缓冲区溢出。
  • 修改字符串时内存的重分配概率降低:对于C字符串,如果要修改字符串,必须要重新分配内存(先释放再申请),因为如果没有重新分配,字符串长度增大时会造成内存缓冲区溢出,字符串长度减小时会造成内存泄露。而对于SDS,由于可以记录len和free,因此解除了字符串长度和空间数组长度之间的关联,可以在此基础上进行优化:空间预分配策略(即分配内存时比实际需要的多)使得字符串长度增大时重新分配内存的概率大大减小;惰性空间释放策略使得字符串长度减小时重新分配内存的概率大大减小。
  • SD可以存取二进制数据:SDS可以,C字符串不可以。因为C字符串以空字符作为字符串结束的标识,而对于一些二进制文件(如图片等),内容可能包括空字符串,因此C字符串无法正确存取;而SDS以字符串长度len来作为字符串结束标识,因此没有这个问题。
此外,由于SDS中的buf仍然使用了C字符串(即以’\0’结尾),因此SDS可以使用C字符串库中的部分函数;但是需要注意的是,只有当SDS用来存储文本数据时才可以这样使用,在存储二进制数据时则不行(’\0’不一定是结尾)。
 
3、SDS与C字符串的应用
Redis在存储对象时,一律使用SDS代替C字符串。例如set hello world命令,hello和world都是以SDS的形式存储的。而sadd myset member1 member2 member3命令,不论是键("myset"),还是集合中的元素("member1"、 "member2"和"member3"),都是以SDS的形式存储。除了存储对象,SDS还用于存储各种缓冲区。只有在字符串不会改变的情况下,如打印日志时,才会使用C字符串。
 
4、Redis的对象类型与内部编码
前面已经说过,Redis支持5种对象类型,而每种结构都有至少两种编码;这样做的好处在于:一方面接口与实现分离,当需要增加或改变内部编码时,用户使用不受影响,另一方面可以根据不同的应用场景切换内部编码,提高效率。
 
Redis各种对象类型支持的内部编码如下图所示(图中版本是Redis3.0,Redis后面版本中又增加了内部编码):
关于Redis内部编码的转换,都符合以下规律:编码转换在Redis写入数据时完成,且转换过程不可逆,只能从小内存编码向大内存编码转换。
 
4.1、字符串
(1)概况
字符串是最基础的类型,因为所有的键都是字符串类型,且字符串之外的其他几种复杂类型的元素也是字符串。注意字符串长度不能超过512MB。
 
(2)内部编码
字符串类型的内部编码有3种,它们的应用场景如下:
  • int:8个字节的长整型。字符串值是整型时,这个值使用long整型表示。
  • embstr:长度<=39字节的字符串。embstr与raw都使用redisObject和sds保存数据,区别在于,embstr的使用只分配一次内存空间(因此redisObject和sds是连续的),而raw需要分配两次内存空间(分别为redisObject和sds分配空间)。因此与raw相比,embstr的好处在于创建时少分配一次空间,删除时少释放一次空间,以及对象的所有数据连在一起,寻找方便。而embstr的坏处也很明显,如果字符串的长度增加需要重新分配内存时,整个redisObject和sds都需要重新分配空间,因此redis中的embstr实现为只读。
  • raw:长度大于39个字节的字符串,字符串对象将使用一个简单动态字符串SDS来保存这个字符串值,并将对象的编码设置为raw。
示例如下图所示:
embstr和raw进行区分的长度,是39;是因为redisObject的长度是16字节,sds的长度是9+字符串长度;因此当字符串长度是39时,embstr的长度正好是16+9+39=64,jemalloc正好可以分配64字节的内存单元。
 
(3)编码转换
当int数据不再是整数,或大小超过了long的范围时,自动转化为raw。而对于embstr,由于其实现是只读的,因此在对embstr对象进行修改时,都会先转化为raw再进行修改,因此,只要是修改embstr对象,修改后的对象一定是raw的,无论是否达到了39个字节。示例如下图所示:
embstr与raw区别:
embstr编码和raw编码一样都使用redisObject结构和sdshdr结构来表示字符串对象,但是raw编码会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构,而embstr编码则通过调用一次内存分配函数来分配一块连续的空间,embstr编码的字符串对象在执行命令时产生的效果和raw编码相同,使用embstr编码的字符串对象来保存短字符串有以下好处:
embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。
释放embstr编码的字符串对象只需要调用一次内存释放函数,而释放raw编码的字符串对象需要调用两次内存释放函数。
因为embstr编码的字符串对象的所有数据都保存在一块连续的内存里面,所以这种编码的字符串对象比起raw编码的字符串对象能够更好地利用缓存带来的优势。
embstr编码的字符串对象实际上是只读的,当我们对 embstr 编码的字符串对象执行任何修改命令时, 程序会先将对象的编码从 embstr 转换成 raw ,然后再执行修改命令。因为这个原因,embstr 编码的字符串对象在执行修改命令之后, 总会变成一个 raw 编码的字符串对象。
 
4.2、列表    
(1)概况
列表(list)用来存储多个有序的字符串,每个字符串称为元素;一个列表可以存储2^32-1个元素。Redis中的列表支持两端插入和弹出,并可以获得指定位置(或范围)的元素,可以充当数组、队列、栈等。
 
(2)内部编码
列表的内部编码可以是压缩列表(ziplist)或双端链表(linkedlist)。
双端链表:由一个list结构和多个listNode结构组成;典型结构如下图所示:
通过图中可以看出,双端链表同时保存了表头指针和表尾指针,并且每个节点都有指向前和指向后的指针;链表中保存了列表的长度;dup、free和match为节点值设置类型特定函数,所以链表可以用于保存各种不同类型的值。而链表中每个节点指向的是type为字符串的redisObject。
 
压缩列表ziplist:压缩列表是Redis为了节约内存而开发的,是由一系列特殊编码的连续内存块(而不是像双端链表一样每个节点是指针)组成的顺序型数据结构;具体结构相对比较复杂。与双端链表相比,压缩列表可以节省内存空间,但是进行修改或增删操作时,复杂度较高;因此当节点数量较少时,可以使用压缩列表;但是节点数量多时,还是使用双端链表划算。压缩列表不仅用于实现列表,也用于实现哈希、有序列表;使用非常广泛。
 
使用压缩列表作为底层实现,每个压缩列表节点保存了一个列表元素,例如执行rpush命令插入三个元素
rpush numbers 1 "three" 5
 
 
考虑到链表的附加空间相对太高,prev 和 next 指针就要占去 16 个字节 (64bit 系统的指针是 8 个字节),另外每个节点的内存都是单独分配,会加剧内存的碎片化,影响内存管理效率。Redis 3.2 之后对列表数据结构进行了改造,使用 quicklist 代替了 ziplist 和 linkedlist。quickList 是 zipList 和 linkedList 的混合体,它将 linkedList 按段切分,每一段使用 zipList 来紧凑存储,多个 zipList 之间使用双向指针串接起来。
// 快速列表 
struct quicklist { 
    quicklistNode* head; 
    quicklistNode* tail; 
    long count; // 元素总数 
    int nodes; // ziplist 节点的个数 
    int compressDepth; // LZF 算法压缩深度 
    ... 
} 
// 快速列表节点 
struct quicklistNode { 
    quicklistNode* prev; 
    quicklistNode* next; 
    ziplist* zl; // 指向压缩列表 
    int32 size; // ziplist 的字节总数 
    int16 count; // ziplist 中的元素数量 
    int2 encoding; //存储形式 2bit,原生字节数组还是LZF压缩存储 
    ... 
} 
struct ziplist_compressed { 
    int32 size; 
    byte[] compressed_data; 
} 
struct ziplist { 
    ... 
}
上述代码简单地表示了 quicklist 的大致结构。为了进一步节约空间,Redis 还会对 ziplist 进行压缩存储,使用 LZF 算法压缩,可以选择压缩深度。
  • quicklist 默认的压缩深度是 0,也就是不压缩。压缩的实际深度由配置参数list-compress-depth决定。
  • 为了支持快速的 push/pop 操作,quicklist 的首尾两个 ziplist 不压缩,此时深度就是 1。
  • 如果深度为 2,就表示 quicklist 的首尾第一个 ziplist 以及首尾第二个 ziplist 都不压缩。
  • quicklist 内部默认单个 ziplist 长度为 8k 字节,超出了这个字节数,就会新起一个 ziplist。
  • ziplist 的长度由配置参数 list-max-ziplist-size 决定。
(3)编码转换
下图展示了列表编码转换的特点:
其中,单个字符串不能超过64字节,是为了便于统一分配每个节点的长度;这里的64字节是指字符串的长度,不包括SDS结构,因为压缩列表使用连续、定长内存块存储字符串,不需要SDS结构指明长度。后面提到压缩列表,也会强调长度不超过64字节,原理与这里类似。
 
4.3、哈希
 
哈希应用于对象缓存,例如每个人的购物车,以用户id为key,商品id为field,商品数量为value,其他信息可以通过商品id到数据库中获取详细信息。
 
(1)概况
哈希(作为一种数据结构),不仅是redis对外提供的5种对象类型的一种(与字符串、列表、集合、有序结合并列),也是Redis作为Key-Value数据库所使用的数据结构。为了说明的方便,下面当使用“内层的哈希”时,代表的是redis对外提供的5种对象类型的一种;使用“外层的哈希”代指Redis作为Key-Value数据库所使用的数据结构。
 
(1)内部编码
内层的哈希使用的内部编码可以是压缩列表(ziplist)和哈希表(hashtable)两种;Redis的外层的哈希则只使用了hashtable。
 
压缩列表前面已介绍。与哈希表相比,压缩列表用于元素个数少、元素长度小的场景;其优势在于集中存储,节省空间;同时,虽然对于元素的操作复杂度也由O(1)变为了O(n),但由于哈希中元素数量较少,因此操作的时间并没有明显劣势。
 
ziplist:每当有新的键值对要加入到哈希对象时,程序会先将保存了键的压缩列表节点推入到压缩列表表尾,然后再将保存了值的压缩列表节点推入到压缩列表表尾。因此:
  • 保存了同一键值对的两个节点总是紧挨在一起,保存键的节点在前,保存值的节点在后
  • 先添加到哈希对象中的键值对会被放在压缩列表的表头方向,而后来添加到哈希对象中的键值对会被放在压缩列表的表尾方向。
 
hashtable:一个hashtable由1个dict结构、2个dictht结构、1个dictEntry指针数组(称为bucket)和多个dictEntry结构组成。
 
正常情况下(即hashtable没有进行rehash时)各部分关系如下图所示:
 
下面从底层向上依次介绍各个部分:
 
dictEntry:结构用于保存键值对,结构定义如下:
typedef struct dictEntry{ 
    void *key; 
    union{ 
        void *val; 
        uint64_tu64; 
        int64_ts64; 
    }v; 
    struct dictEntry *next; 
}dictEntry; 

其中,各个属性的功能如下:

key:键值对中的键;
val:键值对中的值,使用union(即共用体)实现,存储的内容既可能是一个指向值的指针,也可能是64位整型,或无符号64位整型;
next:指向下一个dictEntry,用于解决哈希冲突问题
在64位系统中,一个dictEntry对象占24字节(key/val/next各占8字节)。
 
bucket:是一个数组,数组的每个元素都是指向dictEntry结构的指针。redis中bucket数组的大小计算规则如下:大于dictEntry的、最小的2^n;例如,如果有1000个dictEntry,那么bucket大小为1024;如果有1500个dictEntry,则bucket大小为2048。
 
dictht:结构如下:
typedef struct dictht{ 
    dictEntry **table; 
    unsigned long size; 
    unsigned long sizemask; 
    unsigned long used; 
}dictht;
其中,各个属性的功能说明如下:
  • table属性是一个指针,指向bucket;
  • size属性记录了哈希表的大小,即bucket的大小;
  • used记录了已使用的dictEntry的数量;
  • sizemask属性的值总是为size-1,这个属性和哈希值一起决定一个键在table中存储的位置。
 
dict:
 
一般来说,通过使用dictht和dictEntry结构,便可以实现普通哈希表的功能;但是Redis的实现中,在dictht结构的上层,还有一个dict结构。下面说明dict结构的定义及作用。
 
dict结构如下:
typedef struct dict{ 
    dictType *type; 
    void *privdata; 
    dictht ht[2]; 
    int trehashidx; 
} dict;
其中,type属性和privdata属性是为了适应不同类型的键值对,用于创建多态字典。
 
ht属性和trehashidx属性则用于rehash,即当哈希表需要扩展或收缩时使用。ht是一个包含两个项的数组,每项都指向一个dictht结构,这也是Redis的哈希会有1个dict、2个dictht结构的原因。通常情况下,所有的数据都是存在放dict的ht[0]中,ht[1]只在rehash的时候使用。dict进行rehash操作的时候,将ht[0]中的所有数据rehash到ht[1]中。然后将ht[1]赋值给ht[0],并清空ht[1]。
 
因此,Redis中的哈希之所以在dictht和dictEntry结构之外还有一个dict结构,一方面是为了适应不同类型的键值对,另一方面是为了rehash。
 
(3)编码转换
如前所述,Redis中内层的哈希既可能使用哈希表,也可能使用压缩列表。
 
只有同时满足下面两个条件时,才会使用压缩列表:哈希中元素数量小于512个;哈希中所有键值对的键和值字符串长度都小于64字节。如果有一个条件不满足,则使用哈希表;且编码只可能由压缩列表转化为哈希表hashtable,反方向则不可能。
 
下图展示了Redis内层的哈希编码转换的特点:
 
4.4、集合
(1)概况
集合(set)与列表类似,都是用来保存多个字符串,一个集合中同样最多可以存储2^32-1个元素,但集合与列表有两点不同:集合中的元素是无序的,因此不能通过索引来操作元素;集合中的元素不能有重复。除了支持常规的增删改查,Redis还支持多个集合取交集、并集、差集。
 
(2)内部编码
集合的内部编码可以是整数集合(intset)或哈希表(hashtable)。哈希表前面已经讲过,这里略过不提;需要注意的是,集合在使用哈希表时,值全部被置为null。
整数集合intest的结构定义如下:
typedef struct intset{ 
    uint32_t encoding; 
    uint32_t length; 
    int8_t contents[]; 
} intset;
  • enconding:虽然intset结构将contents属性声明为int8_t类型的数组,但contents的真正类型取决于enconding属性的值。int16_t(最小值-32768,最大32767),int32_t(最小值-2147483648,最大值2147483647),int64_t(最小值-9223372036854775808,最大值9223372036854775807)。
  • length:记录了整数集合包含的元素数量,也就是contents数组的长度。
  • contents:数组是整数集合的底层实现,整数集合的每个元素都是contents数组的一个数组项,各个项在数组中按值的大小从小到大有序地排列,并且不包含重复项。
 
整数集合适用于集合所有元素都是整数且集合元素数量较小的时候,与哈希表相比,整数集合的优势在于集中存储,节省空间;同时,虽然对于元素的操作复杂度也由O(1)变为了O(n),但由于集合数量较少,因此操作的时间并没有明显劣势。
 
(3)编码转换
只有同时满足下面两个条件时,集合才会使用整数集合:集合中元素数量小于512个;集合中所有元素都是整数值。如果有一个条件不满足,则使用哈希表;且编码只可能由整数集合转化为哈希表,反方向则不可能。
下图展示了集合编码转换的特点:
 
4.5、有序集合
(1)概况
有序集合与集合一样,元素都不能重复;但与集合不同的是,有序集合中的元素是有顺序的。与列表使用索引下标作为排序依据不同,有序集合为每个元素设置一个分数(score)作为排序依据。
 
(2)内部编码
有序集合的内部编码可以是压缩列表(ziplist)或跳跃表(skiplist)。ziplist在列表和哈希中都有使用,前面已经讲过,这里略过不提。
 
跳跃表是一种有序数据结构,通过在每个节点中维持多个指向其他节点的指针,从而达到快速访问节点的目的。除了跳跃表,实现有序数据结构的另一种典型实现是平衡树;大多数情况下,跳跃表的效率可以和平衡树媲美,且跳跃表实现比平衡树简单很多,因此redis中选用跳跃表代替平衡树。跳跃表支持平均O(logN)、最坏O(N)的复杂点进行节点查找,并支持顺序操作。Redis的跳跃表实现由zskiplist和zskiplistNode两个结构组成:前者用于保存跳跃表信息(如头结点、尾节点、长度等),后者用于表示跳跃表节点。
skiplist编码的有序集合对象使用zset结构作为底层实现,一个zset结构同时包含一个字典和一个跳跃表:
typedef struct zset { 
    zskiplist *zsl; 
    dict *dict; 
} zset;
  • zsl 跳跃表按分值从小到大保存了所有集合元素, 每个跳跃表节点都保存了一个集合元素:跳跃表节点的 object 属性保存了元素的成员,score 属性则保存了元素的分值。 通过这个跳跃表,程序可以对有序集合进行范围型操作,比如 ZRANK 、 ZRANGE 等命令。
  • dict 字典为有序集合创建了一个从成员到分值的映射,字典中的每个键值对都保存了一个集合元素:字典的键保存了元素的成员,字典的值则保存了元素的分值。通过这个字典,程序可以用 O(1) 复杂度查找给定成员的分值,如 ZSCORE 命令。
  • 有序集合每个元素的成员都是一个字符串对象, 而每个元素的分值都是一个 double 类型的浮点数。
 
(3)编码转换
只有同时满足下面两个条件时,才会使用压缩列表:有序集合中元素数量小于128个;有序集合中所有成员长度都不足64字节。如果有一个条件不满足,则使用跳跃表;且编码只可能由压缩列表转化为跳跃表,反方向则不可能。
 
(4) 为什么有序集合需要同时使用跳跃表和字典来实现?
 
  • 如果只使用字典来实现有序集合, 那么虽然以 O(1) 复杂度查找成员的分值这一特性会被保留, 但是,因为字典以无序的方式来保存集合元素,所以每次在执行范围型操作 —— 比如 ZRANK 、 ZRANGE 等命令时, 程序都需要对字典保存的所有元素进行排序,完成这种排序需要至少 O(N log N) 时间复杂度,以及额外的 O(N) 内存空间(因为要创建一个数组来保存排序后的元素)。
  • 如果只使用跳跃表来实现有序集合,那么跳跃表执行范围型操作的所有优点都会被保留,但因为没有了字典,所以根据成员查找分值这一操作的复杂度将从 O(1) 上升为 O(log N) 。
  • 值得一提的是,虽然 zset 结构同时使用跳跃表和字典来保存有序集合元素, 但这两种数据结构都会通过指针来共享相同元素的成员和分值,所以同时使用跳跃表和字典来保存集合元素不会产生任何重复成员或者分值,也不会因此而浪费额外的内存。
 
5、应用举例
 
5.1、估算Redis内存使用量
要估算redis中的数据占据的内存大小,需要对redis的内存模型有比较全面的了解,包括前面介绍的hashtable、sds、redisobject、各种对象类型的编码方式等。
 
下面以最简单的字符串类型来进行说明。
 
假设有90000个键值对,每个key的长度是7个字节,每个value的长度也是7个字节(且key和value都不是整数);下面来估算这90000个键值对所占用的空间。在估算占据空间之前,首先可以判定字符串类型使用的编码方式:embstr。
 
90000个键值对占据的内存空间主要可以分为两部分:一部分是90000个dictEntry占据的空间;一部分是键值对所需要的bucket空间。
 
每个dictEntry占据的空间包括:
 
  • 一个dictEntry,24字节,jemalloc会分配32字节的内存块
  • 一个key,7字节,所以SDS(key)需要7+9=16个字节,jemalloc会分配16字节的内存块
  • 一个redisObject,16字节,jemalloc会分配16字节的内存块
  • 一个value,7字节,所以SDS(value)需要7+9=16个字节,jemalloc会分配16字节的内存块
 
综上,一个dictEntry需要32+16+16+16=80个字节。
 
bucket空间:bucket数组的大小为大于90000的最小的2^n,是131072;每个bucket元素为8字节(因为64位系统中指针大小为8字节)。
 
因此,可以估算出这90000个键值对占据的内存大小为:90000*80 + 131072*8 = 8248576个字节。
 
下面写个程序在redis中验证一下:
public class RedisTest { 
  public static Jedis jedis = new Jedis("localhost", 6379); 
  public static void main(String[] args) throws Exception{ 
    Long m1 = Long.valueOf(getMemory()); 
    insertData(); 
    Long m2 = Long.valueOf(getMemory()); 
    System.out.println(m2 - m1); 
  } 
  public static void insertData(){ 
    for(int i = 10000; i < 100000; i++){ 
      jedis.set("aa" + i, "aa" + i); //key和value长度都是7字节,且不是整数 
    } 
  } 
  public static String getMemory(){ 
    String memoryAllLine = jedis.info("memory"); 
    String usedMemoryLine = memoryAllLine.split("\r\n")[1]; 
    String memory = usedMemoryLine.substring(usedMemoryLine.indexOf(':') + 1); 
    return memory; 
  } 
} 
运行结果:8247552 

理论值与结果值误差在万分之1.2,对于计算需要多少内存来说,这个精度已经足够了。之所以会存在误差,是因为在我们插入90000条数据之前redis已分配了一定的bucket空间,而这些bucket空间尚未使用。

作为对比将key和value的长度由7字节增加到8字节,则对应的SDS变为17个字节,jemalloc会分配32个字节,因此每个dictEntry占用的字节数也由80字节变为112字节。此时估算这90000个键值对占据内存大小为:90000*112 + 131072*8 = 11128576。
 
在redis中验证代码如下(只修改插入数据的代码):
public static void insertData(){ 
  for(int i = 10000; i < 100000; i++){ 
    jedis.set("aaa" + i, "aaa" + i); //key和value长度都是8字节,且不是整数 
  } 
} 
运行结果:11128576;估算准确。
对于字符串类型之外的其他类型,对内存占用的估算方法是类似的,需要结合具体类型的编码方式来确定。
 
5.2、优化占用内存
了解redis的内存模型,对优化redis内存占用有很大帮助。下面介绍几种优化场景。
 
(1)利用jemalloc特性进行优化
上一小节所讲述的90000个键值便是一个例子。由于jemalloc分配内存时数值是不连续的,因此key/value字符串变化一个字节,可能会引起占用内存很大的变动;在设计时可以利用这一点。
例如,如果key的长度如果是8个字节,则SDS为17字节,jemalloc分配32字节;此时将key长度缩减为7个字节,则SDS为16字节,jemalloc分配16字节;则每个key所占用的空间都可以缩小一半。
 
(2)使用整型/长整型
如果是整型/长整型,Redis会使用int类型(8字节)存储来代替字符串,可以节省更多空间。因此在可以使用长整型/整型代替字符串的场景下,尽量使用长整型/整型。
 
(3)共享对象
利用共享对象,可以减少对象的创建(同时减少了redisObject的创建),节省内存空间。目前redis中的共享对象只包括10000个整数(0-9999);可以通过调整REDIS_SHARED_INTEGERS参数提高共享对象的个数;例如将REDIS_SHARED_INTEGERS调整到20000,则0-19999之间的对象都可以共享。
考虑这样一种场景:论坛网站在redis中存储了每个帖子的浏览数,而这些浏览数绝大多数分布在0-20000之间,这时候通过适当增大REDIS_SHARED_INTEGERS参数,便可以利用共享对象节省内存空间。
 
(4)避免过度设计
然而需要注意的是,不论是哪种优化场景,都要考虑内存空间与设计复杂度的权衡;而设计复杂度会影响到代码的复杂度、可维护性。
如果数据量较小,那么为了节省内存而使得代码的开发、维护变得更加困难并不划算;还是以前面讲到的90000个键值对为例,实际上节省的内存空间只有几MB。但是如果数据量有几千万甚至上亿,考虑内存的优化就比较必要了。
 
5.3、关注内存使用碎片率
 
内存碎片率是一个重要的参数,对redis 内存的优化有重要意义。
如果内存碎片率过高(jemalloc在1.03左右比较正常),说明内存碎片多,内存浪费严重;这时便可以考虑重启redis服务,在内存中对数据进行重排,减少内存碎片。
如果内存碎片率小于1,说明redis内存不足,部分数据使用了虚拟内存(即swap);由于虚拟内存的存取速度比物理内存差很多(2-3个数量级),此时redis的访问速度可能会变得很慢。因此必须设法增大物理内存(可以增加服务器节点数量,或提高单机内存),或减少redis中的数据。
要减少redis中的数据,除了选用合适的数据类型、利用共享对象等,还有一点是要设置合理的数据回收策略(maxmemory-policy),当内存达到一定量后,根据不同的优先级对内存进行回收。
 
 

标签:Redis
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

搜索
排行榜
关注我们

一个IT知识分享的公众号