redis字符串实现

redis 内部的字符串实现,并不是c所定义的字符串, 而是一个sds对象, 这个特性也是redis如此高效,并且能够存储二进制数据类型的原因。

struct sdshdr {
    int len;
    int free;
    char buf[];
};

这样设计的优点:

  1. 当我们获取字符串长度的时候, 如果是c字符串, 必须遍历整个字节数组, 复杂度是O(n), 通过这个属性, 把这个操作降低成O(1)

  2. 底层语言很容易导致缓冲区溢出(缓存区溢出是指, 假如有连续的a, b 两个变量, a的长度是4, b的是5, 如果我们把a的长度直接增加到6, 那么b变量的内容就会被覆写一部分),而sds的free属性很容易判断添加字符串操作能否顺利进行, 如果长度不够, 就会进行内容的重新分配

  3. redis的内存分配采用预分配与懒释放, 预分配是指, 如果free的长度不满足添加的操作,如果原本长度小于1Mb, 重新分配的len与free长度相同(原本len为 4, 添加长度为3, 那么修改之后就是len = 7, free = 7 ,总空间 7+7+1 = 15), 如果长度大于1Mb, 每次预分配的内存默认1Mb。 懒释放指,当我们对字符串裁剪的时候, redis并不会进行内存重新分配, 而是将释放的空间记录到free中。

  4. 二进制安全, redis的字符串可以存放二进制数据的原因就是len属性并非根据’\0’来判断一个字符串的结尾。

  5. 虽然SDS的API都是二进制安全的,但它们一样遵循C字符串以空字符结尾的惯例:这些API总会将SDS保存的数据的末尾设置为空字符,并且总会在为buf数组分配空间时多分配一个字节来容纳这个空字符,这是为了让那些保存文本数据的SDS可以重用一部分库定义的函数。

通过上述的几个特性, redis减少了大量不必要的循环与内存的重新分配, 这是redis如此高效的原因之一。

一个sds对象是一个完整的字符串, 共有三个属性, 分别是

  • len 记录了字符串的长度, 并不包括末尾的’\0’
  • free 记录了这个对象的剩余长度
  • buf 记录了存储的字符串内容

一个sds对象所占用的空间是 len + free + 1byte , 原因是len属性, 并不计算末尾的’\0’