redis string sds（【Redis】关于Redis数据结构简单动态字符串(SDS)的一些杂记）

【Redis】关于Redis数据结构“简单动态字符串(SDS)
  
  
  
  
  
  
 ”的一些杂记

推荐几篇关于SDS数据结构讲解较为详细的文章：

一
  
  
  
  
  
  
 、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

二 
  
  
  
  
  
 、深入理解Redis之简单动态字符串 - itbsl - 博客园 (cnblogs.com)

三 


 


 


 


 


 


 
、Redis内部数据结构详解(2)——sds - 铁蕾的个人博客 (zhangtielei.com)

四
 
 
 
 
 
 
、简单动态字符串 — Redis 设计与实现 (redisbook.readthedocs.io)

一  
   
   
   
   
   
  、SDS的结构与实现

在前面的内容中
  
  
  
  
  
  
 ， 我们一直将 sds 作为一种抽象数据结构来说明 
  
  
  
  
  
 ， 实际上 


 


 


 


 


 


 
， 它的实现由以下两部分组成：

typedef char *sds; struct sdshdr { // buf 已占用长度 int len; // buf 剩余可用长度 int free; // 实际保存字符串数据的地方 char buf[]; };

其中
 
 
 
 
 
 
，类型 sds 是 char * 的别名（alias）  
   
   
   
   
   
  ，而结构 sdshdr 则保存了 len  

 

 

 

 

 

 
、 free 和 buf 三个属性            。

作为例子 

 

 

 

 

 

 
，以下是新创建的

 

 

 

 

 

 
，同样保存 hello world 字符串的 sdshdr 结构：

struct sdshdr { len = 11; free = 0; buf = "hello world\0"; // buf 的实际长度为 len + 1 };

通过 len 属性             ， sdshdr 可以实现复杂度为 θ(1)的长度计算操作  
 
  
 
  
 
  
 
  
 
  
 
  。

另一方面 
 

 
 

 
 

 
 

 
 

 
 

 
， 通过对 buf 分配一些额外的空间












， 并使用 free 记录未使用空间的大小                   ， sdshdr 可以让执行追加操作所需的内存重分配次数大大减少 
 
 
 
 
 
 
 
 
 
 
 
 
， 下一节我们就会来详细讨论这一点












。

当然


















， sds 也对操作的正确实现提出了要求 —— 所有处理 sdshdr 的函数             ，都必须正确地更新 len 和 free 属性 
 
  
 
  
 
  
 
  
 
  
 
  
，否则就会造成 bug 
  
  
  
  
  
  
。

二

 

 

 

 

 

 
、字符串对象

Redis 是一个键值对数据库（key-value DB）











， 数据库的值可以是字符串             、集合 
 

 
 

 
 

 
 

 
 

 
 

 
、列表等多种类型的对象
  
  
  
  
  
  
 ， 而数据库的键则总是字符串对象  
  
  
  
  
  
 。对于那些包含字符串值的字符串对象来说 
  
  
  
  
  
 ， 每个字符串对象都包含一个 sds 值
 


 


 


 


 


 


 。

注意：

“包含字符串值的字符串对象 
  
  
  
  
  
 ” 


 


 


 


 


 


 
，这种说法初听上去可能会有点奇怪
 
 
 
 
 
 
， 但是在 Redis 中  
   
   
   
   
   
  ， 一个字符串对象除了可以保存字符串值之外 

 

 

 

 

 

 
， 还可以保存 long 类型的值

 

 

 

 

 

 
， 所以为了严谨起见             ， 这里需要强调一下： 当字符串对象保存的是字符串时 
 

 
 

 
 

 
 

 
 

 
 

 
， 它包含的才是 sds 值












， 否则的话                   ， 它就是一个 long 类型的值
 
 
 
 
 
 
。

例如 
 
 
 
 
 
 
 
 
 
 
 
 
，以下命令创建了一个新的键值对


















，该键值对的键和值都是字符串对象             ，他们都包含一个sds值：

127.0.0.1:6379> set school "HeFeiUniversity" OK 127.0.0.1:6379> get school "HeFeiUniversity" 127.0.0.1:6379>

下面的命令也创建了一个键值对 
 
  
 
  
 
  
 
  
 
  
 
  
，但是它的键是字符串对象











，而值则是一个集合对象：

127.0.0.1:6379> sadd nosql "MongoDB" "Redis" "Neo4j" (integer) 3 127.0.0.1:6379> smembers nosql 1) "Neo4j" 2) "Redis" 3) "MongoDB" 127.0.0.1:6379>

三












、Redis字符串与C字符串的区别

在 C 语言中
  
  
  
  
  
  
 ，字符串可以用一个 \0 结尾的 char 数组来表示   
   
   
   
   
   
 。

比如说 
  
  
  
  
  
 ， hello world 在 C 语言中就可以表示为 "hello world\0" 
 

 

 

 

 

 

 。

这种简单的字符串表示 


 


 


 


 


 


 
，在大多数情况下都能满足要求
 
 
 
 
 
 
，但是  
   
   
   
   
   
  ，它并不能高效地支持长度计算和追加（append）这两种操作：

每次计算字符串长度（strlen(s)）的复杂度为 θ(N)

 

 

 

 

 

 
。 对字符串进行 N 次追加 

 

 

 

 

 

 
，必定需要对字符串进行 N 次内存重分配（realloc）             。

在 Redis 内部

 

 

 

 

 

 
， 字符串的追加和长度计算很常见             ， 而 APPEND 和 STRLEN 更是这两种操作 
 

 
 

 
 

 
 

 
 

 
 

 
，在 Redis 命令中的直接映射












， 这两个简单的操作不应该成为性能的瓶颈
 
 

 
 

 
 

 
 

 
 

 
 

 。

另外                   ， Redis 除了处理 C 字符串之外 
 
 
 
 
 
 
 
 
 
 
 
 
， 还需要处理单纯的字节数组


















， 以及服务器协议等内容             ， 所以为了方便起见 
 
  
 
  
 
  
 
  
 
  
 
  
， Redis 的字符串表示还应该是二进制安全的： 程序不应对字符串里面保存的数据做任何假设











， 数据可以是以 \0 结尾的 C 字符串
  
  
  
  
  
  
 ， 也可以是单纯的字节数组 
  
  
  
  
  
 ， 或者其他格式的数据












。

考虑到这两个原因 


 


 


 


 


 


 
， Redis 使用 sds 类型替换了 C 语言的默认字符串表示： sds 既可高效地实现追加和长度计算
 
 
 
 
 
 
， 同时是二进制安全的                   。

和C字符串不  
   
   
   
   
   
  ，因为SDS在len属性中记录了SDS本身的长度 

 

 

 

 

 

 
，所以获取一个SDS长度的复杂度为O(1) 
 
 
 
 
 
 
 
 
 
 
 
 。

通过使用SDS而不是C字符串

 

 

 

 

 

 
，Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1)             ，这确保了获取字符串长度的工作不会成为Redis的性能瓶颈



















。所以 
 

 
 

 
 

 
 

 
 

 
 

 
，即使我们对一个非常长的字符串反复执行STRLEN命令












，也不会对系统性能造成任何影响                   ，因为STRLEN命令的复杂度仅为O(1)            。

SDS相对于传统C字符串的优点☆☆☆： C字符串 SDS 获取字符串长度的复杂度为 O(N) 获取字符串长度的复杂度为 O(1) 操作字符串函数不安全 
 
 
 
 
 
 
 
 
 
 
 
 
，可能造成缓冲区溢出 安全的操作字符串API


















，避免缓冲区溢出 修改字符串长度 N 次必然需要执行 N 次内存重分配 修改字符串长度 N 次最多需要执行 N 次内存重分配 只能保存文本数据 可以保存文本以及图片                   、音频 
 
 
 
 
 
 
 
 
 
 
 
 
、视频


















、压缩文件这样的二进制数据  
 
  
 
  
 
  
 
  
 
  
 
  。

四             、SDS对内存的优化策略

SDS采用了空间预分配策略与惰性空间释放策略来避免内存分配问题












。

空间预分配策略是指             ，每次 SDS 进行空间扩展时 
 
  
 
  
 
  
 
  
 
  
 
  
，程序不但为其分配所需的空间











，还会为其分配额外的未使用空间
  
  
  
  
  
  
 ，以减少内存再分配次数
  
  
  
  
  
  
。而额外分配的未使用空间大小取决于空间扩展后SDS 的 len 属性值  
  
  
  
  
  
 。

如果 len 属性值小于 1M 
  
  
  
  
  
 ，那么分配的未使用空间 free 的大小与 len 属性值相同
 


 


 


 


 


 


 。 如果 len 属性值大于等于 1M 


 


 


 


 


 


 
，那么分配的未使用空间 free 的大小固定是 1M
 
 
 
 
 
 
。

SDS 对于空间释放采用的是惰性空间释放策略   
   
   
   
   
   
 。该策略是指
 
 
 
 
 
 
，SDS 字符串长度如果缩短  
   
   
   
   
   
  ，那么多出的未使用空间将暂时不释放 

 

 

 

 

 

 
，而是增加到 free 中
 

 

 

 

 

 

 。以使后期扩展 SDS 时减少内存 再分配次数

 

 

 

 

 

 
。如果要释放 SDS 的未使用空间

 

 

 

 

 

 
，则可通过 sdsRemoveFreeSpace()函数来释放             。

五 
 
  
 
  
 
  
 
  
 
  
 
  
、SDS模块的API

sds 模块基于 sds 类型和 sdshdr 结构提供了以下 API ：

函数 作用 算法复杂度 sdsnewlen 创建一个指定长度的 sds              ，接受一个 C 字符串作为初始化值 O(N) sdsempty 创建一个只包含空白字符串 "" 的 sds O(1) sdsnew 根据给定 C 字符串 
 

 
 

 
 

 
 

 
 

 
 

 
，创建一个相应的 sds O(N) sdsdup 复制给定 sds O(N) sdsfree 释放给定 sds O(N) sdsupdatelen 更新给定 sds 所对应 sdshdr 结构的 free 和 len O(N) sdsclear 清除给定 sds 的内容












，将它初始化为 "" O(1) sdsMakeRoomFor 对 sds 所对应 sdshdr 结构的 buf 进行扩展 O(N) sdsRemoveFreeSpace 在不改动 buf 的情况下                   ，将 buf 内多余的空间释放出去 O(N) sdsAllocSize 计算给定 sds 的 buf 所占用的内存总数 O(1) sdsIncrLen 对 sds 的 buf 的右端进行扩展（expand）或修剪（trim） O(1) sdsgrowzero 将给定 sds 的 buf 扩展至指定长度 
 
 
 
 
 
 
 
 
 
 
 
 
，无内容的部分用 \0 来填充 O(N) sdscatlen 按给定长度对 sds 进行扩展


















，并将一个 C 字符串追加到 sds 的末尾 O(N) sdscat 将一个 C 字符串追加到 sds 末尾 O(N) sdscatsds 将一个 sds 追加到另一个 sds 末尾 O(N) sdscpylen 将一个 C 字符串的部分内容复制到另一个 sds 中             ，需要时对 sds 进行扩展 O(N) sdscpy 将一个 C 字符串复制到 sds O(N)

本文仅供学习参考！