欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Redis源码阅读:Redis字符串SDS详解

程序员文章站 2022-06-26 11:35:47
sds 基本概念简单动态字符串(simple dynamic string)sds,用作redis 的默认字符串。c语言中的字符串:以空字符结尾的字符数组sds实现举例redis > set m...

sds 基本概念

简单动态字符串(simple dynamic string)sds,用作redis 的默认字符串。

c语言中的字符串:以空字符结尾的字符数组

sds实现举例

redis > set msg "hello world"
ok

我们通过 set 在 redis 数据库中创建了一个数据键对象为 "msg" 和 数据值对象为 "hello world" 的键值对,其中数据键和数据值对象底层的字符串实现都是 sds 。同时, sds 还被用于 aof 缓冲区。

sds 定义

struct sdshdr {
    # 记录 buf 数组中已使用字节的数量,即当前字符串长度值  
    # 等于 sds 所保存字符串的字节长度
    int len;
    # 记录 buf 数组中未使用字节的数量,buf空余可用的长度,append时使用  
    int free;
    # 字节char数组,用于保存字符串,实际保存字符串数据,最后一个字节保存了空字符 '\0'
    char buf[];
};

buf 属性的字节数组中的字符串长度等于 len 属性值加上1,因为 redis遵循 c语言的规范,在sds数据类型字符串的结尾加上了 空字符串,额外占用 1 个字节空间,这1个字节空间不计算在 sds 的 len属性里面。

由于sds将字符串的结尾加上了 空字符串符合c语言字符串规范,redis 字符串操作可以兼容c语言中一部分字符串库中的函数,redis 无需专门为 sds在编写一套函数。

sds的优点

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

  1. c字符串需要遍历整个字符串,计数,直到碰到空字符,停止计数,复杂度为o(n)
  2. sds获取 len 属性值即可,复杂度为 o(1) 。所以 strlen 的复杂度也为 o(1)

api安全,杜绝缓冲区溢出

  1. c字符串在进行字符串拼接 strcat 时,需要预先分配足够的空间,来容纳拼接的字符串,否则会造成缓冲区溢出的问题,比如临近的空间有另外一个字符串。
  2. sds 在进行字符串拼接时,会先检查 len 的长度是否足够,如果不够,会先扩展 len,再进行字符串拼接。

减少修改字符串长度时所需的内存重分配次数

  • 空间预分配
  • 当对 sds 进行空间扩展时,计算扩展之后的 len值如果小于 1mb,那么久会分配 扩展之后的 len 值给 free 属性作为,为下次扩展时预分配的未使用空间,如果下次扩展所需字节空间小于 free 的值,那么就无需进行空间扩展,直接使用未使用空间。
  • 惰性空间释放
  • 同样,默认情况下,对 sds 进行缩减时,缩减的空间不会立刻被这个sds释放,而是分配给 free ,如果之后再进行扩展时,有可能会用到。
  • redis 的 sds 类型通过这两种空间分配策略,减少了字符串增长缩减时所需的内存重分配操作,为内存分配提供了优化。

二进制安全

redis 通过 len属性的值来判断是否结束,而不是c字符串的 \0 作为结束。

兼容部分c字符串函数

上面已经提到sds在末尾添加了 \0 ,这样可以兼容部分c字符串函数,可以直接使用 <string.h> 函数库。

redis 字符串源码原理

1、redis的字符串结构被设计成一个[sds]结构

字符串实际内容是被存放在一个数组中,如下表

struct sds<t> {
  t capacity; // 数组容量
  t len; // 数组实际长度
  byte flags; // 特殊标识位,不理睬它
  byte[] content; // 数组内容
}

当字符串的大小超出当前分配的capacity大小时,数组将扩容,分配更大的数组,将旧的数组拷贝到新数组中,再将增加到字符串添加进去。

2、embstr 与raw

1)redis的字符串的储存方式分为2种,当长度特别短时,使用emb形式存储,当长度超出44时,使用raw存储。

2)俩者的区别:

redis的对象头结构如下:

struct redisobject {
    int4 type; // 4bits
    int4 encoding; // 4bits
    int24 lru; // 24bits
    int32 refcount; // 4bytes
    void *ptr; // 8bytes,64-bit system
} robj;

解析:不同的对象具有不同类型的type;同一个类型的type会有不同的存储形式encoding;使用lru来记录对象的lru信息,每个对象都有一个引用计数,当计数为0的时候,对象就会被销毁,内存被回收;pre指针用来指示对象内容具体存储位置;上诉对象有结构内容加起来需要占用16字节的存储空间。

sds对象头大小:实际内容的大小(capacity) + 3byte,3是用来存储capacity + len + flags内容加起来的长度,而content数组初始值是16,所有sds最小的大小是19 (16+3 );

存储形式如下图:

Redis源码阅读:Redis字符串SDS详解

解析:embstr将redisobject对象头和sds对象连续存在一起,使用malloc方法一次分配;而raw需要俩次malloc,俩个对象头砸死内存地址上一般是不连续的。embstr最大能容纳的字符串长度是44字节

3、扩容策略

字符串在长度小于1m之前,扩容空间采用加倍策略,即保留100%冗余空间。当长度大于1m,没次扩容只会多分配1m的冗余空间。

以上为个人经验,希望能给大家一个参考,也希望大家多多支持。