Redis原理再学习：动态字符串sds

Redis原理再学习：动态字符串sds

字符

字符就是英文里的一个一个英文字母，比如：a。中文里的单个汉字，比如：好。

字符串就是多个字母或多个汉字组成，比如字符串：redis，中文字符串：你好吗。

英文字符，如果按照 ASCII 码计算，一个字符占用 1 个字节。

中文字符的编码就比较复杂点，一个字符占用空间一般是 2 个字节，有的也用 3-4 个字节。

它有很多格式编码，有 gb2312，gbk， utf8 等等。

具体可以看看这篇文章：常见的中文字符编码。

动态字符串sds定义

看看 redis3.0 中的字符数据结构定义，sds.h/sdshdr

// https://github.com/redis/redis/blob/3.0/src/sds.h#L41
// redis3.0 低版本容易理解
typedef char *sds;
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};


• len：记录 buf 数组中字符的长度

  
  



• free：记录 buf 中未使用的字节的数量

  
  



• buf：字节数组，保存字符串

  
  

sdshdr为什么要这样设计

C 语言中的字符数组难道不够用吗？

对于普通的字符串操作，C 语言中的字符数组是够用的。但是，redis 定位是高性能 kv 数据库，所以对于 redis 是不够用的。

从哪些方面优化才能扣出一点点性能呢？

1. 空间换时间：一次多分配一些空间，下次增加字符串时不需要在进行分配空间的操作了。这个叫预分配。

   ​ 还有，截断字符串时，也不需要归还空间，而是用 free 属性记录，下次可以在复用空间，这个叫惰性分配。

   
   



2. 获取字符串长度复杂度 O(1)：sdshdr 里面定义了一个属性 len，操作字符串时会自动计算字符串的长度并赋值给这个 len 属性。所以在 redis 的一些命令中，不需要在计算一次字符串长度，而计算这个长度复杂度是 O(N)。比如 strlen 命令。

   
   

除了上面的 2 点，还有哪些好处？

1. 避免缓存区溢出：因为 SDS 的空间分配策略杜绝了发生缓冲区溢出的可能性。因为 SDS 的 API 会先检查空间是否满足修改所需的要求，不满足的话会自动扩展修改所需的空间大小。


2. 二进制安全：得益于 sds api 的设计，所有 sds api 都会以处理二进制的方式处理 sds 存放在 buf 数组里的数据。因为 sdshdr 里有一个 len 属性。

sdshdr存储字符串示例

比如 sdshdr 存储一个字符串 Redis，如下图：

​ （《Redis设计与实现》）

存储 Redis 字符串时 sdshdr 各属性解释：

• free：值为 0，表示 sdshdr 中没有未使用的空间

  
  



• len：值为 5，表示 sdshdr 保存了一个 5 字节长度的字符串

  
  



• buf：char 类型的数组，数组前 5 个字节保存了 R, e, d, i, s 五个字符，结尾保存了空字符 '\0'。这个遵循了 c 语言中空字符串结尾惯例。保存这个空字符串的 1 字节长度不计算在 sdshdr 的 len 属性里。

  
  

参考

• 《redis设计与实现》 作者：黄健宏


• redis.io

== just do it ==