0%

redis底层之简单动态字符串SDS

字符串是redis最基本的数据类型,其它几种数据类型构成也包含字符串对象,其长度不能超过512M。字符串对象的编码可以是int,raw或者embstr。

一、概念

  1. Redis没有直接使用C语言传统的字符串表示(以空字符结尾的字符数组,以下简称C字符串), 而是自己构建了一种名为简单动态字符串(simple dynamic string,SDS)的抽象类型,并将SDS用作Redis的默认字符串表示。

  2. 比如说SET name kobe这个命令,redis将在数据库中创建一个键值对。

    • 键值对的键是一个字符串对象,对象的底层实现是一个保存着字符串name的SDS
    • 键值对的值是一个字符串对象,对象的底层实现是一个保存着字符串kobe的SDS
  3. SDS定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
# <3.2版本
struct sdshdr {
int len; // 记录buf数组中已使用字节的数量,不包括'\0'的长度,等于SDS所保存字符串的长度
int free; // 记录buf数组中未使用字节的数量
char buf[]; // 字节数组,用于保存字符串:不是用这个数组来保存字符,而是用它来保存一系列二进制数据。
};

# >=3.2版本
/* Note: sdshdr5 is never used, we just access the flags byte directly.
* However is here to document the layout of type 5 SDS strings. */
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 3 lsb of type, and 5 msb of string length */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 {
uint16_t len; /* used */
uint16_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 {
uint32_t len; /* used */
uint32_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 {
uint64_t len; /* used */
uint64_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
char buf[];
};
  1. 逻辑结构

    • <3.2版本 string

      • free属性的值为0,表示这个SDS没有分配任何未使用空间。
      • len属性的值为5,表示这个SDS保存了一个五字节长的字符串。
      • buf属性是一个char类型的数组,数组的前五个字节分别保存了’R’、’e’、’d’、’i’、’s’五个字符,而最后一个字节则保存了空字符’\0’
        • buf[]除了保存字符串的字符外,还会在末尾保存一个空字符’\0’,空字符不计算在len属性之中,遵循空字符结尾的好处是可以重用一部分C字符串的函数
    • >3.2版本

      • len表示sds当前sds的长度,单位是字节,不包括’\0’终止符
      • alloc表示当前为sds分配的大小,单位是字节(3.2以前的版本用的free是表示剩余可用空间)
      • flags表示当前sdshdr的类型,声明为char 一共有1个字节(8位),用低三位就可以表示所有5种sdshdr类型
        • 要判断一个sds属于什么类型的sdshdr,只需flags&SDS_TYPE_MASKSDS_TYPE_n比较即可
      • buf同3.2之前的版本一样

二、和C字符串对比

  1. 获取字符串长度的时间复杂度为O(1):

    • C字符串不记录自身的长度信息,获取字符串长度时会遍历字节数组,直到遇到空字符为止,复杂度为 O(N)
    • SDS直接通过struct sdshdr结构体len属性获取字符串长度,复杂度为O(1)
  2. 可以避免缓冲区溢出:

    • C字符串不记录自身长度,修改字符串时不会判断本身是否拥有足够的内存空间,当内存空间不足时则会造成缓冲区的溢出.
    • 当SDS API需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需的要求。如果不满足API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作,所以使用SDS既不需要手动修改SDS的空间大小,也不会出现前面所说的缓冲区溢出问题。
  3. 减少修改字符串长度时所需的内存重分配次数

    • 空间预分配:用于优化SDS的字符串增长操作,当SDS API对一个SDS进行修改并且需要对SDS进行空间扩展的时候,程序不仅会为SDS分配修改所必须要的空间,还会为SDS分配额外的未使用空间。
      • 如果对SDS进行修改之后,SDS的长度(即len属性的值)小于1MB,那么程序分配和len属性同样大小的未使用空间,即free=len
      • 如果对SDS进行修改之后,SDS的长度大于等于1MB,那么程序会分配1MB的未使用空间,即free=1MB
    • 惰性空间释放:用于优化SDS的字符串缩短操作,当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。
  4. 二进制安全

    • C字符串中的字符必须符合某种编码(比如ASCII),并且除了字符串的末尾之外不能包含空字符,否则最先被程序读入的空字符将被误认为是字符串结尾,这些限制使得C字符串只能保存文本数据,而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
    • SDS的API都是二进制安全的,所有SDS API都会以处理二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中的数据做任何限制、过滤、或者假设,数据在写入时是什么样的,它被读取时就是什么样。
  5. 编码:字符串对应的编码类型有int、embstr和raw三种,根据值的不同Redis会采用不同的编码

    • 当所设置的值是一个long范围内的整数时,会使用int编码
    • 当设置的值是一个长度小于等于44的字符串时,会使用embstr编码
    • 当设置的值是一个长度大于44的字符串时,会使用raw编码

embstr和raw按44字节为分界是在Redis3.2开始的,之前是以39字节为分界的。

三、参考

  1. 参考一