温州做美食网站,开网店,网站设计公司哪里好,深圳自助网站建设费用前言 在Redis中有许多数据结构#xff0c;比如#xff1a;简单动态字符串(SDS)#xff0c;双端链表#xff0c;字典#xff0c;压缩列表#xff0c;整数集合等。 Redis并没有直接使用这些数据结构来实现键值对数据库#xff0c;而是基于这些数据结构创建了一个对象系统。…前言 在Redis中有许多数据结构比如简单动态字符串(SDS)双端链表字典压缩列表整数集合等。 Redis并没有直接使用这些数据结构来实现键值对数据库而是基于这些数据结构创建了一个对象系统。这个系统中包含字符串对象列表对象哈希对象集合对象和有序集合对象这物种类型的对象。通过这五种不同类型的对象Redis可以在执行命令前根据对象的类型来判断一个对象是否可以执行给定的命令。使用对象的另一个好处时我们可以针对不同的使用场景为对象设置多种不同的数据结构实现从而优化对象在不同场景下的使用效率。 除此之外Redis对象系统还实现了基于引用计数技术的内存回收机制当程序不再使用某个对象的时候这个对象所占用的内存会被自动释放另外Redis还通过引用计数技术实现了对象共享机制这一机制可以在适当的条件下通过让多个数据库键共享同一个对象来节约内存。 最后Redis对象带有访问时间记录信息该信息可以用于计算数据库键的空转时长在服务器启用了maxmemory功能的情况下空转时间较长的那些键可能会优先被服务器删除。
一. 对象的类型与编码 Redis使用对象来表示数据库的键和值每次当我们在Redis的数据库中新创建一个键值对时我们至少会创建两个对象一个对象用作键值对的键(键对象)另一个对象用作键值对的值(值对象)。 Redis中的每一个对象都由一个redisObject结构表示该结构中和保存数据有关的三个属性分别是type属性encoding属性和ptr属性
typedef struct redisObject {//类型unsigned type:4;//编码unsigned encoding:4;unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or* LFU data (least significant 8 bits frequency* and most significant 16 bits access time). */int refcount;//指向底层实现数据结构指针void *ptr;
} robj; 1.1 类型 对象type属性记录了对象的类型这个属性的值可以是下图中的一个。 对于Redis数据库保存的键值对来说键总是一个字符串对象而值则可以是字符串对象列表对象哈希对象集合对象或有序集合对象的其中一种。
当我们称呼一个数据库键为字符串键时我们指的是这个数据库键所对应的值为字符串对象 当我们称呼一个数据库键为列表键时我们指的是这个数据库键所对应的值为列表对象 TYPE命令的实现方式也与此类似当我们对一个数据库执行TYPE命令时命令返回的结果为数据库键对应的值对象的类型而不是键对象的类型。 下图列出了TYPE命令在面对不同类型的值对象时所产生的输出 1.2 编码和底层实现 对象的ptr指针指向对象的底层实现数据结构而这些数据结构由对象encoding属性决定。 encoding属性记录了对象所使用的编码也就是说这个对象使用了什么数据结构作为对象的底层实现。 每种类型的对象都至少使用两种不同的编码下图列出了每种类型的对象可以使用的编码 使用OBJECT ENCODING命令可以查看一个数据库键的值对象的编码 下图列出了不同编码的对象所对应的OBJECT ENCODING 命令输出 通过encoding属性来设定对象所使用的编码而不是为特定类型的对象关联一种固定的编码极大的提升了Redis的灵活性和效率因为Redis可以通过不同的使用场景来为一个对象设置不同的编码从而优化对象在某一场景下的效率。 举个例子在列表包含的元素比较少时Redis使用压缩列表作为列表对象的底层实现
因为压缩列表比双端链表更节省内存并且元素比较少时在内存中以连续块方式保存压缩列表比双端链表可以更快被加载到内存中。随着列表对象包含的元素越来越多使用压缩列表来保存元素的优势逐渐消失时对象就会将底层实现从压缩列表转向功能更强也更加适合保存大量元素的双端链表上面。 其他类型得得对象也通过使用多种不同的编码来进行类似的优化。 下面介绍Redis中的五种不同类型的对象说明这些对象底层所使用的编码方式列出对象从一种编码转化成另外一种编码所需的条件以及同一个命令在不同编码上的实现方式。
二. 字符串对象 字符串对象的编码可以是intraw或者emstr。 如果一个字符串对象保存的是整数值并且这个整数值可以使用long类型来表示那么字符串字符串对象会将整数值保存到字符串对象的ptr属性里(将void*转换成long)并将字符串对象的编码设置成int。 如果字符串对象保存的是一个字符串值并且这个字符串的长度大于32字节那么字符串对象将使用一个简单的动态字符串(SDS)来保存这个字符串值并将对象的编码设置为raw。 如果字符串对象保存的是一个字符串值并且这个字符串值的长度小于等于32字节那么字符对象将使用embstr编码的方式来保存这个字符串值。 2.1 embstr编码方式 embstr编码是专门用来保存短字符串的一种优化编码方式。这种编码方式和raw编码一样都使用redisObject结构和sdshdr结构来表示字符串对象。但是raw编码会调用两次内存分配来分别创建redisObject结构和sdshdr结构。而embstr编码则通过调用一次内存分配函数来分配一块连续的空间空间依次包含redisObject和sdshdr两个结构。 embstr编码的字符串对象在执行命令时产生的效果和raw编码的字符串对象执行命令时产生的效果相同但使用embstr编码的字符串对象来保存短字符串值有以下好处
embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次。释放embstr编码字符串对象只需要调用一次内存释放函数而释放raw编码的字符串对象需要调用两次内存释放函数。因为embstr编码的字符串对象所有数据都保存在一块连续的内存里所以这种编码的字符串比起raw编码的字符串对象能够更好地利用缓存带来地优势。 最后可以用long double类型表示地浮点数在Redis中也是作为字符串值来保存地。如果我们要保存一个浮点数到字符串对象里面那么程序会先将这个浮点数转换成字符串值然后再保存转换所得地字符串值。 举个例子执行以下代码将创建一个包含3.14的字符串表示3.14的字符串对象在有需要的时候程序会将保存的字符串对象里面的字符串值转换回浮点数值执行某些操作然后再将执行操作所得的浮点数转换回字符串值并继续保存子字符串对象里。 下图总结并列出字符串对象保存各种不同类型的值所使用的编码方式 2.2 编码转换 int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下会被转换为raw编码的字符串对象。 对于int编码的字符串对象来说如果我们向对象执行了一些命令使得这个对象保存的不再是整数值而是一个字符串值那么字符串对象的编码从int变为raw。 在下面的示例中我们通过APPEND命令向一个保存整数值的字符串对象追加了一个字符串值因为追加操作只能对字符串值执行所以程序会先将之前保存的整数值10086转换为字符串值10086然后再执行追加操作操作的执行结果就是一个raw编码的保存了字符串值的字符串对象 因为Redis没有为embstr编码的字符串对象编写任何相应的修改程序(只有int编码的字符串对象和raw编码的字符串对象有这些程序)。所以embstr编码的字符串对象实际上是只读的。当我们对embstr编码的字符串对象执行任何修改命令时程序会先将对象的编码从embstr编码转换成raw编码然后再执行修改命令。 因为这个原因embstr编码的字符串对象在执行修改命令之后总会变成一个raw编码的字符串对象。 2.3 字符串命令的实现 因为字符串键的值为字符串对象所以用于字符串键的所有命令都是针对字符串对象来构建的下图列举了其中一部分字符串命令以及命令在不同编码的字符串对象下的实现方法 三. 列表对象 在redis3.2版本之前的列表对象的编码可以是ziplist(压缩列表)或者linkedlist(双端链表)。 在redis3.2版本之后已经不使用ziplist和linkedlist作为底层实现取而代之的是quicklist。 3.1 redis3.2版本前的ziplist和linkedlist ziplist编码的列表对象使用压缩列表作为底层实现每一个压缩列表节点(entry)保存了一个列表元素。 举个例子如果我们执行RPUSH命令那么服务器创建一个列表对象作为number键的值
127.0.0.1:6379 RPUSH NUMBERS 1 THREE 5
(integer) 3 如果numbers键的值对象使用的是ziplist编码这个值对象将会是下图所展示的样子 另一方面linkedlist编码的列表对象使用双端链表作为底层实现每一个双端链表的节点都保存了一个字符串对象而每一个字符串对象都保存了一个列表元素。 举个例子如果上面的列表使用的linkedlist编码那么numbers键的值对象将是下图所示 注意
linkedlist编码的列表对象在底层的双端链表结构中包含多个字符串对象在之后介绍的哈希对象集合对象和有序集合对象中都会出现字符串对象是Redis五种类型的对象中唯一一个会被其他四种类型对象嵌套的对象。为了简化字符串对象我们在途中使用的是StringObject字样的格子表示一个字符串对象而实际保存的值比如一个包含three字符串值的字符串对象如下图 3.1.1 编码转换 当列表对象可以同时满足以下两个条件时列表对象使用ziplist编码
列表对象保存的所有字符串元素长度都小于64字节列表对象保存的元素数量小于512个不能满足这两个条件的列表对象需要使用linkedlist编码。 注意以上两个条件的上限值是可以修改的具体请看配置文件中关于list-max-ziplist-value选项和list-max-ziplist-entries选项的说明。 对于使用ziplist编码的列表来说使用ziplist编码所需的两个条件的任意一个不能被满足时对象的编码转换操作就会被执行原本保存在压缩列表里的所有列表元素都会被转移并保持到双端链表里面对象的编码也会从ziplist变为linkedlist。 例子 1. 列表对象因为保存长度太大的元素而进行编码转换的情况
127.0.0.1:6379 rpush blah hello world again
(integer) 3
127.0.0.1:6379 object encoding blah
ziplist
127.0.0.1:6379 rpush blah wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
(integer) 4
127.0.0.1:6379 object encoding blah
liskedlist
127.0.0.1:6379 2. 因为保存元素数量过多而进行编码转换
127.0.0.1:6379 EVAL for i1, 512 do redis.call(RPUSH, KEYS[1], i)end 1 integers
(nil)
127.0.0.1:6379 llen integers
(integer) 512
127.0.0.1:6379 object encoding integers
ziplist
127.0.0.1:6379 rpush integers 513
(integer) 513
127.0.0.1:6379 object encoding integers
linkedlist
127.0.0.1:6379 3.1.2 列表命令的实现 3.2 redis3.2版本之后的quicklist 3.2.1 为什么引入quicklist
ziplist优缺点 优点存储在连续的内存上不容易产生内存碎片内存利用率高。 缺点插入和删除操作需要频繁的申请和释放内存同时会发生内存拷贝数据量大时内存拷贝开销大。
linkedlist优缺点 优点插入和删除节点复杂度低。 缺点除了报存数据外还需要保存prev和next指针内存利用率低。并且双向链表各个节点时单独的内存块不连续容易造成内存碎片。 基于上述问题quicklist的设计是时间和空间的折中quicklist结合了ziplist和linkedlist的优点核心思想是使用ziplist的特性并使用linkedlist结构来减少ziplist的长度。 3.2.2 quicklist内部结构 quicklist每一个节点都是一个quicklistNode对象数据结构如下
typedef struct quicklistNode {//前一个节点struct quicklistNode *prev;//后一个节点struct quicklistNode *next;//当前指向的ziplist或者quicklistLZFunsigned char *zl;//当前ziplist占用字节unsigned int sz; /* ziplist size in bytes *///ziplist中存储元素个数16字节(最大65535个)unsigned int count : 16; /* count of items in ziplist *///是否采用LZF压缩算法压缩节点 1RAW 2: LZFunsigned int encoding : 2; /* RAW1 or LZF2 *///存储结构unsigned int container : 2; /* NONE1 or ZIPLIST2 *///当前ziplist是否需要再次被压缩(如果前面被解压过则为true表示需要被再次压缩)unsigned int recompress : 1; /* was this node previous compressed? *///unsigned int attempted_compress : 1; /* node cant compress; too small */unsigned int extra : 10; /* more bits to steal for future usage */
} quicklistNode; Redis使用quicklist来管理所有的quicklistNode结构如下
typedef struct quicklist {//列表头节点quicklistNode *head;//列表尾节点quicklistNode *tail;//ziplist一共存储了多少元素即所有quicklistNode节点count和unsigned long count; /* total count of all entries in all ziplists *///双向链表的长度即quicklistNode节点数unsigned long len; /* number of quicklistNodes *///填充因子int fill : QL_FILL_BITS; /* fill factor for individual nodes *///压缩深度0不压缩unsigned int compress : QL_COMP_BITS; /* depth of end nodes not to compress;0off */unsigned int bookmark_count: QL_BM_BITS;quicklistBookmark bookmarks[];
} quicklist; quicklist结构实际是一个双向链表链表中保存的元素是ziplist。这样当ziplist达到某一长度时会新建一个quicklistNode节点。这样做的优点有
使用到ziplist相比较于linkedlist减少内存碎片。使用到双向链表减少单个ziplist的长度减少内存拷贝的开销。 3.2.3 ziplist大小 虽然说quicklist结合了ziplist和双向链表的优点但是现在的问题是ziplist大小的选择。
ziplist太小内存碎片越多ziplist太大分配大块连续内存空间的难度越大内存拷贝消耗越大。 如何保持ziplist的长度取决于具体应用场景。 我们可以通过配置list-max-ziplist-size参数来控制ziplist的大小。基于两种原则元素个数或元素大小。
当list-max-ziplist-size取正值的时候表示按照数据项个数来限定每一个quicklist中ziplist的长度。比如当list-max-ziplist-size等于5时表示quciklist的ziplist节点最多包含5个数据项。当list-max-ziplist-size取负值的时候表示按照占用字节数来限定每一个quicklist中ziplist的长度。这时它只能取-5到-1这五个值。表示的含义如下 -5: 每个quicklist节点上的ziplist大小不能超过64 Kb。注1kb 1024 bytes -4: 每个quicklist节点上的ziplist大小不能超过32 Kb。 -3: 每个quicklist节点上的ziplist大小不能超过16 Kb。 -2: 每个quicklist节点上的ziplist大小不能超过8 Kb。-2是Redis给出的默认值 -1: 每个quicklist节点上的ziplist大小不能超过4 Kb。 3.2.4 quicklist的compress属性 列表设计最容易访问的是列表两端的数据中间的访问频率很低如果符合这个场景redis中还有一个配置可以对列表的中将节点进行压缩(采用的LZF——无痕压缩算法)进一步节省内存。
list-compress-depth 0 compress属性表示压缩深度这个属性表示quicklist两端不被压缩的节点数 注意这里压缩的节点是quicklist的节点quicklistNode而不是ziplist里的数据。实际上压缩quicklist节点包含的整个ziplist都会被压缩。 compress属性表示压缩深度可以通过配置list-compress-depth来控制
0不压缩(默认值)1首尾第1个元素不压缩2首位前2个元素不压缩3首尾前3个元素不压缩以此类推 3.2.5 quicklistNode的zl指针 zl指针默认指向ziplistsz属性记录了当前ziplist占用的字节数。 但是当ziplist被压缩(LZF算法)后zl指针指向另外一个对象quicklistLZFquicklistLZF结构是一个4N字节的结构。
typedef struct quicklistLZF {//LZF的大小unsigned int sz; /* LZF size in bytes*///被压缩的内容char compressed[];
} quicklistLZF;
参考【Redis】列表对象底层原理之quicklist_quicklist原理_云川之下的博客-CSDN博客
