数据结构与对象

简单动态字符串(SDS)

Redis并没有使用C语言传统的字符串表示(以空字符串节为的字符数组)，而是自己构建了一种名为简单动态字符串(SDS)

例如客户端执行命令

redis: SET msg "hello world"

  • Redis将在数据库中创建一个新的键值对
  • 键值对的键是一个字符串对象，对象的底层实现是一个保存着字符串"msg"的SDS
  • 键值对的值也是一个字符串对象，对象的底层实现是一个保存着字符串"hello world"的SDS

SDS除了用来保存数据库中的字符串值以外，还可以用作缓冲区，AOF模块中的AOF缓冲区，以及客户端状态中的输入缓冲区，都是由SDS实现的

The Design of SDS

每个sds.h/sdshdr结构表示一个SDS值

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

与C的字符串一样，SDS为空字符分配额外的1字节空间，以及添加空字符到字符串末尾等操作由SDS函数自动完成，由于SDS末尾也有额外空字符，SDS也可以使用部分string.h函数，例如print("%s",s->buf)

why SDS?

1. 常数复杂度获取字符串长度

  • C字符串本身不记录自身的长度信息，如果要获取一个C字符串的长度，必须遍历整个字符串，时间复杂度O(n)
  • 而SDS是结构体结构，有元素len记录SDS本身长度，因此获取长度时间复杂度O(1)
  • 设置和更新SDS长度的工作是由SDS的API在执行时自动完成，使用SDS无需任何手动修改长度的工作

2. 杜绝缓冲区溢出

  • C字符串不记录自身长度会带来另外一个问题：容易造成缓冲区溢出
    • 如果使用<string.h>/strcat函数，将两个字符串进行拼接，如果事先没有声明足够长的数组，会导致出现缓冲区溢出的情况
  • 对于SDS来说，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性
    • 当SDS API 需要对SDS进行修改时，API会先检查SDS的空间是否满足修改所需的要求，如果不满足，API自动将SDS的空间扩展到执行修改所需的大小
    • 所以使用SDS不需要手动修改空间大小，也不会出现缓冲区溢出问题

3. 减少修改字符串时带来的内存重分配次数

  • 由于C字符串不记录自身长度，对于一个包含了N个字符串的C字符串来说，C字符串底层是一个N+1字符长的数组，因此每次增长或缩短一个字符串，程序需要对保存这个C字符串的数组进行一次内存重分配操作
    • 如果增长字符串，例如append，执行操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小，否则会导致缓冲区溢出
    • 如果缩短字符串，例如trim，执行操作之后，程序需要通过内存重分配来释放字符串不再使用的那部分空间，否则会导致内存泄漏
    • 内存重分配涉及的算法较为复杂，是一个比较耗时的操作
  • SDS通过未使用空间(free)，解决了字符串长度和底层数组长度的关联，在SDS中，buf数组的长度不一定是字符数量加一，数组里面可以包含未使用的字节，长度用free指定
    • 空间预分配
      • 当SDS的一个API需要对SDS进行修改，并且需要对SDS进行扩展，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间
        • 如果对SDS进行修改之后，SDS长度小于1MB，那么程序分配和len属性同样大小的未使用空间
        • 如果对SDS进行修改之后，SDS长度大于等于1MB，那么程序会分配1MB的未使用空间
      • 这样，SDS将连续增长N此字符串所需的内存重分配次数从必定N次降低为最多N次
    • 惰性空间释放
      • 惰性空间释放用于优化SDS的字符串缩短操作
      • 当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是用free来将这些字节的数量记录起来
      • 如果在进行缩短后，马上进行拼接，就可以不用进行内存重分配，直接将free的长度分配给需要拼接的字符串即可，提升了效率

4. 二进制安全

C字符串中的字符必须符合某种编码(ASCII)，因此字符串里面不能包含空字符，自然无法保存音频，视频，图片等二进制数据

对于Redis，允许中间出现空字符，所以程序不会对SDS中的数据做任何的限制，过滤等情况

因此，Redis可以用SDS来保存一系列二进制数据

5. 兼容部分C字符串函数

​ 前面提过，SDS同样以空字符作为结尾标志，因此它也可以使用部分<string.h>中的函数

总结

C字符串 SDS
获取字符串长度的复杂度为O(n) 获取字符串长度的复杂度为O(1)
API是不安全的，可能造成缓冲区溢出 API安全，不会造成缓冲区溢出
修改字符串N次必定执行N次内存重分配 修改字符串N次最多执行N次内存重分配
只能保存文本数据 可以保存文本或二进制数据(图像，视频，音频…)
可以使用<string.h>库中所有函数 可以使用部分<string.h>库中的函数

对象

对象的类型与编码

Redis中的每个对象都由一个redisObject结构表示，该结构中和保存数据有关的三个属性分别是type,encoding,ptr

typedef struct redisObject{
    //类型
    unsigned type:4;
    //编码
    unsigned encoding:4;
    //指向底层实现数据结构的指针
    void *ptr;
    //...
    
}robj;

类型

对象的type属性记录了对象的类型，对于Redis数据库保存的键值对来说，键总是一个字符串对象，而值可以是字符串对象，列表对象，哈希对象，集合对象或有序集合对象中的其中一个

  • 我们称呼一个数据库键为”字符串键”时，我们指的是”这个数据库键所对应的值为字符串对象”

编码与底层实现

  • 可以使用OBJECT ENCODING ...来查看一个数据库键的值对象的编码

字符串对象

字符串对象的编码可以是row,raw,embstr

如果字符串对象保存的是一个字符串值，且字符串值的长度小于等于39字节，那么字符串对象将使用embstr编码的方法保存这个字符串的值

embstr编码是专门用于保存短字符串的一种优化编码方式

编码可转换

int编码的字符串对象和embstr编码的字符串对象在条件满足的情况下，会被转换成raw编码的字符串对象

  • 例如，对于int类型的字符串对象来说，如果我们执行命令使得这个对象保存的不再是整数值，而是一个字符串值，那么字符串对象编码会变为raw

列表对象

底层多为ziplist,linkedlist

ziplist编码的列表对象使用压缩列表作为底层实现，每个压缩列表节点保存了一个列表元素

linkedlist编码的列表对象使用双端链表作为底层实现，每个双端链表节点都保存了一个字符串对象，每个字符串对象都保存了一个列表元素

类型检查与命令多态

类型检查的实现

在执行一个类型特定的命令之前，Redis会先检查输入键的类型是否正确，然后再决定是否执行给定的命令

  • 在执行一个类型特定命令之前，服务器会先检查输入数据库键的值对象是否是执行命令所需的类型，如果是，服务器对键执行指定的命令

  • 否则服务器拒绝执行命令，向客户端返回一个类型错误

多态命令的实现

Redis除了会根据值对象的类型判断键是否能够执行指定命令之外，还会根据值对象的编码方式，选择正确的命令实现代码来执行命令

如果对一个键执行LLEN命令，那么服务器除了要确保执行命令的是列表键之外，还需要根据键的值对象所使用的编码来选择正确的LLEN命令

  • 如果列表对象的编码是ziplist，那么说明列表对象的实现为压缩列表，程序将使用ziplistLen函数返回列表长度
  • 如果列表对象的编码是linkedlist，那么说明列表对象的实现为双端链表，程序将使用listLength函数返回双端列表长度

内存回收

C语言不具备自动内存回收功能，Redis在自己的对象系统中构建了这样的机制

​ Redis在自己的对象系统中，构建了一个引用计数技术实现的内存回收机制，通过这一机制，程序可以通过跟踪对象给的引用计数信息，在适当的时候自动释放对象并回收内存

对象共享

对象的引用计数属性还带有对象共享的作用

如果键A已经创建了一个包含整数值100的字符串作为值对象，键B也要创建一个同样保存整数值100的字符串

  • 那么服务器直接让键A和键B共享同一个字符串对象即可
    • 步骤:
      1. 将数据库键的值指针指向一个现有的值对象
      1. 将被共享的值对象引用计数增1

当服务器需要用到值0-9999的字符串对象时，服务器就会使用这些共享对象，而不是新创建对象

对象的空转时长

对象redisObject结构中包含的最后一个属性是unsigned: lru:22，该属性记录了对象最后一次被命令程序访问的时间

可以通过它，得到对象的空转时间

重点回顾

  • Redis数据库中的每个键值对的键和值都是一个对象
  • Redis有字符串，列表，哈希，集合，有序集合五种类型的对象，每种类型的对象至少都有两种或以上的编码方式，适用于不同场景
  • 服务器在执行某些命令前，会先检查给定键的类型能否执行指定的命令，以及命令多态
  • Redis的对象系统带有引用计数实现的内存回收机制，当一个对象不再被使用时，对象所占用的内存就会被自动释放
  • Redis会共享值为0-9999的字符串对象
  • 对象会记录自己最后一次被访问的时间，这个时间可以用于计算对象的空转时间
Redis
数据结构与对象

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！

redis:单机数据库 Previous
教育平台开发所遇问题 Next