Skip to content

Latest commit

 

History

History
50 lines (48 loc) · 3.69 KB

redis字符串sds设计.md

File metadata and controls

50 lines (48 loc) · 3.69 KB
Raw

redis字符串sds设计

redis数据库底层没有直接使用c的字符串表示，而是自己使用名为简单动态字符串(simple dynamic string,SDS)

SDS定义

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

示例
sds.png

  • free属性值为0，表示sds没有分配任何为使用空间
  • len属性为5，表示这个sds保存了一个5个字节长的字符串
  • buf属性表示一个char类型的数组，前五个字节保存"Redis"，而最后一个字节保存空字符'\0' 注：SDS遵循空字符结尾的好处是：SDS可以直接重用一部分c字符串函数库的函数，比如直接打印字符串printf

SDS与C字符串的区别

1. 获取字符串长度时间复杂度不同(提高获取字符串长度性能)
  • 普通C字符串获取长度需要遍历整个字符串，因此复杂度为O(N)。
  • SDS的len属性直接保存字符串的长度，复杂度为O(1)
2. SDS杜绝缓冲区溢出
  • C:比如说，拼接字符串函数char *strcat(char *dest,const char *sec)，当dest不足够存放src所有内容时，就会产生缓冲区溢出
  • SDS:SDS有自己的空间分配策略，当SDS的API对字符串操作时，API会先检查SDS的空间是否满足操作，不满足的话API会自动将SDS的空间扩展至所需大小，然后才执行操作
3. 减少修改字符串带来的内存重分配次数
  • 当C需要修改字符串长度时，我们需要再次对使用内存重新分配，由于内存重新分配设计复杂的算法，并且可能执行系统调用，所以通常是比较耗时的操作
  • SDS的空间预分配跟惰性空间释放会对字符串的内存分配次数进行优化

1.空间预分配

  • 如果对SDS修改后，SDS的长度(len)<1MB，则程序将分配和len属性同样大小的free空间
  • 如果对SDS修改后，SDS的长度(len)>1MB，则程序将分配1MB的free空间

2.惰性空间释放

  • 惰性空间释放用于优化SDS缩短的操作，当SDS缩短时，程序不会立即进行内存重新分配，而是用free保存多余出来的字节，方便未来使用
4.二进制安全
  • C字符串中的字符除了末尾外，不能包含空字符，否则会被识别成字符串结尾
  • SDS可以用来保存二进制数据，所以SDS的API都是二进制安全(binary-safe)的，所有的SDS API 会以处理二进制方式来处理buf的数据。因此数据写入是什么样的，读取出来就是什么样的。
5.兼容部分C字符串函数
  • 虽然SDS的API是二进制安全的，但其也遵循C字符串以空字符结尾的惯例：这些API总会将SDS保存的末尾设置为空字符，并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符，为了让保存文本数据的SDS可以重用<string.h>定义的函数
总结
C字符串 SDS
获取字符串长度复杂度为O(N) 获取字符串长度复杂度为O(1)
API是不安全的，可能造成缓冲区溢出 API是安全的，不会成缓冲区溢出
修改字符串长度N次必然需要执行N次内存重新分配 修改字符串长度N次最多需要执行N次内存重新分配
只能保存文本数据 可以保存文本数据和二进制数据
可以使用所有<string.h>库中的函数 可以使用部分<string.h>库中的函数