当初在高铁上, 赶着春节回家过年, 无座站票, 电脑只能放行李架上, 面对着行李架撸键盘--看过<Redis的设计与实现>这本书, 忽然想起, 便整顿下SDS的内容, 绝对前面的章节, 算是比较简单的~

大多数状况下, Redis应用SDS(Simple Dynamic String, 简略动静字符串)作为字符串示意, 比起C字符串, SDS具备以下长处:

  1. 常数复杂度获取字符串长度;
  2. 杜绝缓冲区溢出;
  3. 缩小批改字符串时带来的内存重调配次数;
  4. 二进制平安;
  5. 兼容局部C字符串函数.

以上列举的长处, 也算是这篇文章的次要内容. 先从定义说起吧:

1. SDS的定义

SDS构造定义如下(sds.h/sdshdr):

struct sdshdr {    // 记录buf数组中已应用字节的数量, 等于SDS所保留字符串的长度    int len;    // 记录buf数组中未应用字节的数量    int free;    // 字节数组, 用于保留字符串    char buf[];}
  1. len属性记录了已应用的字节数量(字符串长度);
  2. free属性的值为0, 示意这个SDS没有未应用的空间;
  3. free属性的值为5, 示意这个SDS保留了一个5字节长的字符串;
  4. buf属性是一个char类型的数组, 数组的最初一个字节保留了空字符\0.

SDS遵循C字符串以空字符串结尾的常规, 空字符不计入SDS的len属性, 即额定为空字符调配了1字节的空间, 并且增加空字符到字符串开端均由SDS函数主动实现, 对使用者齐全通明. 该个性带来的益处是, SDS能够间接复用C字符串函数库的局部函数.

2. SDS与C字符串的区别

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

  1. 因为C字符串不记录本身长度, 所以获取长度时须要遍历整个字符串, 直到遇到空字符\0为止, 该操作的复杂度为O(N);
  2. 因为SDS在len属性中记录了SDS自身的长度, 所以获取一个SDS的长度的复杂度为O(1).

Redis应用SDS, 将获取字符串长度所需的复杂度从O(N)升高到O(1), 确保获取字符串长度的工作不会成为Redis的性能瓶颈.

2.2 杜绝缓冲区溢出

因为C字符串不记录本身长度, 以函数strcat来说, 当执行该函数时, 都是认为曾经为dest调配了足够的内存包容src字符串, 但如果该假如不成立, 就会产生缓冲区溢出.

然而, SDS的字符串空间调配策略, 从根本上杜绝了缓冲区溢出的可能性: 当SDS-API须要对SDS进行批改时, API会先查看SDS的空间是否满足批改所需的需要, 如果不满足的话, API会主动扩容至所需大小, 再执行批改操作. 所以, SDS无需手工保护SDS的空间大小, 也不会产生缓冲区溢出的问题.

2.3 缩小批改字符串时带来的内存重调配次数

因为C字符串不记录本身长度, 所以每次增长或缩减字符串, 须要对保留这个C字符串的数组进行一次内存重调配操作:

1.如果程序执行的是增长字符串的操作, 比方拼接操作append, 须要进行内存重调配操作, 扩大底层数组至适合大小, 否则将会产生缓冲区溢出;
2.如果程序执行的是缩短字符串的操作, 比方截断操作trim, 须要进行内存开释操作, 否则将会产生内存泄露.

Redis作为数据库, 常常用于速度要求严苛, 数据被频繁批改的场合, 缩小内存的重调配次数能进步性能. SDS通过未应用空间解除了字符串长度和底层数组长度之间的关联: 在SDS中, buf数组的长度不肯定就是字符数加一, 数组外面能够蕴含未应用的字节, 而这些字节的数量就由SDS的free属性记录.

通过未应用空间, SDS实现了空间预调配和惰性空间开释两种优化策略.

1.空间预调配

当SDS-API对SDS进行批改, 并且须要对SDS进行空间扩大的时候, 程序不仅会为SDS调配批改所需的空间, 还会为SDS调配额定的未应用空间.

额定调配的未应用空间数量, 由以下公式决定:

  1. 如果对SDS进行批改之后, SDS的长度(即len属性)将小于1MB, 那么程序调配和len属性同样大小的未应用空间, 这时SDS的len属性的值将和free属性的值雷同: 比方批改之后, SDS的len将变成13字节, 那么程序也会调配13字节的未应用空间, buf长度将变成 13Byte + 13Byte + 1Byte = 27Byte;
  2. 如果对SDS进行批改之后, SDS的长度将大于等于1MB, 那么程序会调配1MB的未应用空间: 比方批改之后, SDS的len将变成30MB, 那么程序会调配1MB的未应用空间, buf长度将变成 30MB + 1MB + 1Byte.

通过空间预调配策略, Redis能够缩小间断执行字符串增长操作所需的内存重调配次数.

2.惰性空间开释

惰性空间开释用于优化SDS的字符串缩短操作: 当SDS-API须要缩短SDS字符串时, 程序并不会立刻回收内存, 而是应用free属性将这些字节的数量记录起来, 并期待未来应用.

当然, SDS也提供了相应的API真正地开释SDS的未应用空间, 无需放心该策略带来的内存节约问题.

2.4 二进制平安

C字符串除了开端, 不能蕴含空字符, 否则最先被程序读入的空字符将被误认为是字符串结尾, 所以C字符串只能保留文本数据, 而不能保留像图片, 音频, 视频, 压缩文件这样的二进制数据.

Redis为了能够实用于各种不同的场景, SDS-API都是二进制平安的(binary-safe), 所有SDS-API都会以二进制的形式解决buf数组外面的数据, 不限度, 不过滤, 不假如, 写入什么就读到什么.

2.5 兼容局部C字符串函数

尽管SDS-API是二进制平安的, 但它们一样遵循C字符串以空字符结尾的常规: 这些API总是将SDS保留的数据开端数组为空字符, 并且总会在为buf调配空间时多调配一个字节来包容这个空字符, 以复用<string.h>库定义的函数.

3. SDS的API

函数作用复杂度
sdsnew创立一个蕴含给定C字符串的SDSO(N), N为给定C字符串的长度
sdsempty创立一个不蕴含任何内容的空SDSO(1)
sdsfree开释给定的SDSO(N), N为被开释SDS的长度
sdslen返回SDS的已应用空间字节数这个值能够通过读取SDS的len属性来间接取得, 复杂度为O(1)
sdsavail返回SDS的未应用空间字节数这个值能够通过读取SDS的free属性来间接取得, 复杂度为O(1)
sdsdup创立一个给定SDS的正本(copy)O(N), N为给定C字符串的长度
sdsclear清空SDS保留的字符串内容因为惰性空间开释策略, 复杂度为O(1)
sdscat将给定C字符串拼接到另一个SDS字符串的开端O(N), N为被拼接C字符串的长度
sdscatsds将给定SDS字符串拼接到另一个SDS字符串的开端O(N), N为被拼接SDS字符串的长度
sdscpy将给定的C字符串复制到SDS外面, 笼罩SDS原有的字符串O(N), N为被复制SDS字符串的长度
sdsgrowzero用空字符将SDS扩大至给定长度O(N), N为扩大新增的字节数
sdsrange保留SDS给定区间内的数据, 不在区间内的数据会被笼罩或革除O(N), N为被保留数据的字节数
sdstrim承受一个SDS和一个C字符串作为参数, 从SDS中移除所有在C字符串中呈现过的字符O(N^2), N为给定C字符串的长度
sdscmp比照两个SDS字符串是否雷同O(N), N为两个SDS钟较短的那个SDS的长度

4. 总结

  • Redis在大多数状况下应用SDS作为字符串的示意;
  • 相比C字符串, SDS具备以下长处:
  1. 常熟复杂度获取字符串长度;
  2. 杜绝缓冲区溢出;
  3. 缩小批改字符串长度时所需的内存重调配次数;
  4. 二进制平安;
  5. 兼容局部C字符串函数.
  • C字符串和SDS之间的区别:
C字符串SDS
获取字符串长度的复杂度为O(N)获取字符串长度的复杂度为O(1)
API是不平安的，可能造成缓冲区溢出API是平安的，不会造成缓冲区溢出
批改字符串长度N次必然须要执行N次内存重调配批改字符串长度N次最多需啊哟执行N次内存重调配
能够应用所有<string.h>库中的函数能够应用一部分<string.h>库中的函数

以上笔记都是整顿自<Redis的设计与实现>, 真的很感激作者, 也心愿本人能保持写下去^_^.

文章来源于自己博客，公布于 2018-02-15，原文链接：https://imlht.com/archives/106/