400-002-1024
service@dtsre.com
总部杭州
北京 · 上海 · 贵阳
周一至周五
09:00 - 18:00

玩转云端丨redis的5种对象与8种数据结构之字符串对象(下)

杭州云掣科技有限公司-一家专注于云托管(MSP)服务的公司    产品技术    玩转云端丨redis的5种对象与8种数据结构之字符串对象(下)

引言

本文是对《redis设计与实现(第二版)》中数据结构与对象相关内容的整理与说明。本篇文章只对对象结构,1种对象——字符串对象。以及字符串对象所对应的两种编码——raw和embstr,进行了详细介绍。表达一些本人的想法与看法,也希望更多朋友一起来讨论,分享交流。

 

 

作者:太阳

云掣科技-数据库团队
数据库工程师

 

 

 

字符串对象

 
字符串对象可以存储整数、浮点数、字符串,具体策略是:
 
当存储整数时,用到的编码是int,底层的数据结构可以用来存储long类型的整数;
当存储字符串时,如果字符串的长度小于等于32字节,那么将用编码为embstr的格式来存储;如果字符串的长度大于32字节,将用编码为raw的SDS格式来存储;
当存储浮点数时会先将浮点数转换为字符串,如果转换后的字符串长度小于32字节就用编码为embstr的格式来存储,否则用编码为raw的SDS格式来存储。
 
下图是一个字符串对象的结构图,最左侧是对象结构,中间跟右侧合起来是raw编码的SDS数据结构(sdshdr),示例图:
 

 

 

 

 

raw编码,简单动态字符串(simple dynamic string-SDS)

 

redis用的并不是C语言传统的字符串,而是自己构建了简单动态字符串(simpledynamic string,SDS)。

 

 

当redis打印日志信息或输出报错信息,这些输出的字符串是不会被修改的字符串字面量(sting literal),此时用的是C语言传统的字符串来存储这些信息的。当redis需要存储的是可以被修改的字符串时,就会使用SDS结构。


除了用来保存数据库中的字符串值之外,SDS还被用作缓冲区(buffer):AOF模块中的AOF缓冲区,以及客户端状态中的输入缓冲区,都是由SDS实现的。

 

 

SDS的结构

 

 

SDS结构示意图如下所示:

 

 

 
 

sdshdr是该数据结构的名称即SDS,其中:

 

buf属性,是一个字节数组,用来保存字符串,后面箭头对应的就是实际保存的字符串内容,最后以’\0’空字符串结尾;

 

len属性,记录的是buf数组中实际已使用的字节数量,等于SDS所保存字符串的长度;

 

free属性,记录的是buf数组中未使用字节的数量。

 
 

 

 

SDS优点

 

一、可以用O(1)的复杂度获取到字符串长度

 

 

SDS的len属性记录了字符串的长度,而传统C字符串要想知道长度需要遍历整个字符串。相比于传统C字符串,redis获取字符串长度所需的复杂度从O(N)降低到了O(1)。

 

即使对非常长的字符串反复执行STRLEN命令(获取字符串长度),也不会造成过多的性能消耗。

 

二、杜绝缓冲区溢出

 

在传统的C字符串中,如果要修改字符串的内容,但修改后字符串的长度超过原先的长度就会发生溢出现象。详见下图:

 

 

 

 

在SDS中,当需要对buf字节数组中存储的内容进行修改(增添或删除)时,API会先通过free和len属性检查SDS的空间是否足够,如果不够的话,SDS会自动扩展空间再对内容进行修改。关于自动扩展空间的策略见下方“空间预分配”的内容。
 
三、减少修改字符串长度时所需的内存重分配次数

 

对于传统C字符串:

 

 

如果执行的是增长字符串的操作,如拼接操作(append),那么在执行命令之前,程序需要先通过内存重分配来扩展底层数据的空间大小——否则会产生缓冲区溢出。


如果执行的是缩短字符串的操作,如截断操作(trim),那么在执行这个操作之后,程序需要通过内存重分配来释放字符串不再使用的空间——否则会产生内存泄漏。

 

对于redis中的SDS结构:

 
 
内存重分配设计复杂的算法,是一个比较耗时的操作,redis作为速度要求严苛、数据会被频繁执行的数据库,如果每次修改字符串都需要进行一次内存重分配,会严重影响性能。
 

使用SDS,buf数组里可以包含未使用的字节,这些字节的数量由free属性记录,可以减少修改字符串长度时所需的内存重分配次数。

 

 

 

空间预分配和惰性空间释放

 

 

通过SDS中free属性定义的未使用空间,SDS可以实现间预分配惰性空间释放两种优化策略:

 

1、空间预分配策略——可以降低字符串增长操作引起的内存重分配

 

当需要修改SDS的内容,且需要进行空间扩展的时候,程序不仅会为SDS分配修改所需的必须空间,还会为SDS分配额外的未使用空间。

 

其中,额外分配的未使用空间数量由以下公式决定:

 

如果对SDS进行修改之后,SDS的长度(即len属性的值)将小于1MB,那么程序将分配和len属性同样大小的未使用空间,这时SDS len属性的值将和free属性的值相同。

 

如果对SDS进行修改后,SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。

 
 

说明

 

 

如果对一个字符串的末尾持续追加内容,当字符串整体大小大于1MB时,即使只追加一字节的字符,程序也会额外分配1MB的空间,当再次追加一字节的字符时,程序不会再额外分配1MB的空间,而是使用已有的空闲空间。

 

即在扩展空间之前,会先检查未使用的空间是否足够,如果足够,是不会额外再扩展的。

 

通过空间预分配策略,SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次。

 

2、惰性空间释放策略——可以降低字符串缩短操作引起的内存重分配

 

当SDS中的字符串长度被缩短时,程序并不会立即使用内存重分配来回收缩短后多出来的字节空间,而是使用free属性将这些字节的数量记录起来,以备将来使用。


当然,redis提供了相应的命令来真正释放这些未使用空间,避免不必要的内存浪费。

 

四、二进制安全

 

C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外,字符串里面不能包含空字符,如果字符串除末尾外还有其它空字符,那么最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存图片、音频、视频、压缩文件这样的二进制数据。


为了确保redis可以适用于各种不同的使用场景,SDS的API都是二进制安全的(binary-safe),所有SDS API都会以处理二进制的方式来处理SDS存放buf数组里的数据,程序不会对其中的数据做任何限制、过滤或者假设,数据在写入时是什么样的,它被读取时就是什么样。

这也是RDS的buf属性被称为字节数组的原因——redis不是用这个数组来保存字符,而是用它来保存一系列二进制数据。
 
五、兼容部分C字符串函数
 
SDS遵循空字符串结尾这一惯例,好处是可以直接重用C字符串<string.h>函数库里的函数,从而避免了不必要的代码重复。

 

 

embstr编码

 

如果字符串对象保存的是长度小于等于32字节的字符串,那么将会使用embstr编码,embstr编码是专门用来保存短字符串的一种优化编码方式。embstr编码与raw编码对应的字符串对象,都是由对象结构(redisObject)和数据结构(sdshdr)组成的。

 

 

区别在于用raw编码的字符串对象会调用两次内存分配函数来分别创建redisObject结构和sdshdr结构,而embstr编码则通过调用一次内存分配函数来分配一块连续的空间,空间中一次包含redisObject和sdshr两个结构,embstr编码的字符串对象结构图如下所示:

 

 

 

两者的区别

 

embstr编码的字符串对象在执行命令时,产生的效果和raw编码的字符串对象执行命令时产生的效果是相同的的,但使用embstr编码的字符串对象来保存短字符串值有以下好处:

 

 
 

1、embstr编码将创建字符串对象所需的内存分配次数从raw编码的两次降低为一次;

 

2、释放embstr编码的字符串对象只需要调用一次内存释放函数,而释放raw编码的字符串对象需要调用两次内存释放函数;

 

3、embstr编码的字符串对象的所有数据都保存在一块连续的内存里,结构更加紧凑,而raw编码是分散开的,redisObject对象结构和sdshdr数据结构彼此间是用指针相关联的,embstr编码的对象比raw编码的对象能够更好的利用缓存带来的优势。

 
 

 

 

编码的转换

 

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下,会被转换成raw编码的字符串对象。encoding命令可以查看键对应的值,底层用的是什么编码。

 

 

int转换为raw

 

对于int编码的字符串对象来说,如果我们向对象执行了一些命令,使得这个对象保存的不再是整数值,而是一个字符串值,那么字符串对象的编码将从int变为raw。

 

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
27.0.0.1:6379> set a 100    //设置a=100OK127.0.0.1:6379> object encoding a    //查看键a存储的值用的是什么编码"int"    127.0.0.1:6379> append a 'a'  //向键a的值中追加内容’a’,此时键a存储的值将变为字符串类型(integer) 4127.0.0.1:6379> get a  //查询键a的值"100a"  127.0.0.1:6379> object encoding a    //查看键a存储的值现在对应的编码,发现已经变为raw格式的编码,表示里面现在存储的是字符串"raw"

 

int编码的字符串,存储的是long类型的整数,范围是2^63-1(2的63次方减一) ~ -2^63(2的63次方),当存储的整数在该范围内时,编码为int,当值超过该范围,编码将转换为embstr。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
27.0.0.1:6379> set number1 9223372036854775807  OK127.0.0.1:6379> object encoding number1    "int"127.0.0.1:6379> set number2 9223372036854775808  OK127.0.0.1:6379> object encoding number2"embstr"127.0.0.1:6379> set number3 -9223372036854775808OK127.0.0.1:6379> object encoding number3"int"127.0.0.1:6379> set number4 -9223372036854775809OK127.0.0.1:6379> object encoding number4"embstr"

 

 

embstr转换为raw

 

embstr编码的字符串对象无法被修改(redis没有为embstr编码的字符串对象编写任何响应的修改程序),只有int、raw编码的字符串对象可以被修改,所以embstr编码的字符串实际上是只读的。


当对embstr编码的字符串对象执行任何修改命令时,程序都会先将对象的编码从embstr转换为raw,然后再执行修改命令。所以一旦embstr编码的字符串被修改,它的数据结构就会变成raw编码的格式。

 

  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
127.0.0.1:6379> set a 'ab'OK127.0.0.1:6379> object encoding a"embstr"127.0.0.1:6379> append a 'c'(integer) 3127.0.0.1:6379> get a"abc"127.0.0.1:6379> object encoding a"raw"

 

碎碎念

 

以上就是根据《redis设计与实现(第二版)》中数据结构与对象相关内容进行的部分整理与分享,欢迎各位共同参与讨论一起交流沟通。

 

Redis系列会在未来与大家见面!

2019年8月12日 18:51
浏览量:0
收藏