Redis SDS

sds(simple dynamic string) 简单动态字符串,是redis内部存储字符串类型的数据结构,是对原生c语言中char[]的扩展和封装.

sdshdr数据结构(v3.0及以前)

sds数据结构:

struct sdshdr {
unsigned int len;  // buf中已经使用的长度
unsigned int free;  // buf中未使用的长度
char buf[];  // 存储字符串的char数组
};

针对sdshdr数据结构本身,我们看下在执行命令时sds是如何使用的.

set命令

在执行set key redis命令时,sds存储字符串的过程

1. 计算存储字符串”redis”长度,长度为5

2. buf 数组会使用空间预分配的方式申请空间

初始分配的buf空间分为3部分,字符串存储空间,预分配空间,字符串结尾标识符'\0'.

预分配空间,有2个要求:

2.1 当存储字符串长度小于1M时,会额外增加一倍长度的冗余空间

2.2 当存储字符串长度大于1M时,会额外增加1M长度的冗余空间

buf数组分配的空间长度=5+5+1=11

3. len字符串长度,值为5

free未使用长度,也就是这里的预分配空间长度,同样为5

sds存储字符串redis后的数据结构

strlen命令

在计算存的字符串值的长度key时,返回sdshdr->len即可,时间复杂度为o(1).

append,setrange与setbit命令

1. 在执行append key abc命令时,会判断追加的字符串长度,是否判断是否大于sds的未使用空间,如果未使用空间能够存储追加字符串,调整len,free值,不会做申请空间等操作.

2. setrange命令,在未超过预分配空间时,也只会更新buf数组值,不会做申请空间操作.

3. setbit虽然进行位操作,但也是按字节存储,本质是一样的.可以参考位域.

综上所述,sds有如下优点:

1. 可动态扩展内存,sds字符串其内容可以修改,追加.

2. 惰性删除,预分配空间不会被释放,除非该字符串所对应的键被删除,或者redis启动时重新载入的字符串不会预分配空间.

3. 二进制安全,sds能存储任意二进制数据,而不仅仅是可打印字符.

4. 与传统的c语言字符串类型兼容.

sds的缺点及优化

缺点:

1. redis的key也使用sds作为存储数据结构,但key是不会有更改操作的,这就造成了空间的浪费.

2. sds中的len,free的类型是unsigned int,是占用4字节,在存放小字符串时也会造成空间的浪费.

优化:

针对这些缺点redis在v3.2之后,对数据格式做了调整优化.

1. 数据结构拆分

根据存储数据的大小,记录长度的len,buf空间,将原有的数据结构细分为5种情况,分别为sdshdr5, sdshdr8, sdshdr16, sdshdr32, sdshdr64.对应存储字符串长度分别为2^5, 2^8, 2^16, 2^32, 2^64.

2. 取消字节对齐

采用__attribute__ ((__packed__)) 让编译器取消结构体在编译过程中的优化对齐,按照实际占用字节数进行对齐,减少空间占用.

3. 优化key存储数据格式

针对key存储的情况,优化采用sdshdr5 的数据结构,不在存储len,free值,减少空间占用.

这也意味着key值长度不要超过32位,否则还是会采用更大存储空间的sdshdr数据结构,造成空间浪费.

struct __attribute__ ((__packed__)) sdshdr5 {  // 对应的字符串长度小于 1<<5
    unsigned char flags; // flag用3bit来标明sds类型,其余5bit未使用
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr8 { // 对应的字符串长度小于 1<<8
    uint8_t len;  // 字符串使用的长度
    uint8_t alloc;  // 分配的总长度
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr16 { // 对应的字符串长度小于 1<<16
uint16_t len;
    uint16_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr32 { // 对应的字符串长度小于 1<<32
    uint32_t len;
    uint32_t alloc;
    unsigned char flags;
    char buf[];
};
struct __attribute__ ((__packed__)) sdshdr64 { // 对应的字符串长度小于 1<<64
    uint64_t len;
    uint64_t alloc;
    unsigned char flags;
    char buf[];
};