Redis数据类型——SDS（简单动态字符串）

本文主要是介绍Redis数据类型——SDS（简单动态字符串），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Redis并没有使用C语言传统的字符串，而是构建了一种名为简单动态字符串（Simple dynamic string，SDS），并作为默认字符串使用。

例如：执行如下命令

SET msg "hello world"

Redis数据库中将建立一个键值对，键是一个字符串对象，是一个负责保存"msg"的SDS，而值也是一个SDS，负责保存“hello world”。

注意：SDS还被用于缓冲区，AOF缓冲区以及客户端的输入缓冲区都是SDS实现的

SDS的定义（未包含4.0新特性）

3.0特性

每个sds.h/sdshdr 都代表一个SDS值

struct sdshdr {

int len;//记录SDS保存的数组的长度

int free;//记录SDS中未使用的字节数量

char buf[]; //字节数组，保存字符串

}

buf是一个char型数组，前五个字节保存了 R E D I S 五个字符，最后一个字节保存了空字符 \0;空字符并不算在len里面。额外分配 1 字节空间、把空字符自动加到数组末尾等操作都是SDS自动完成的，完全不用使用者来管理，对用户是完全透明的。

保留空字符的好处就是可以沿用C字符串函数库里的函数。可以直接使用print(“%s”,SDSname->buf);输出。

4.0新特性

#define SDS_TYPE_5 0
#define SDS_TYPE_8 1
#define SDS_TYPE_16 2
#define SDS_TYPE_32 3
#define SDS_TYPE_64 4
#define SDS_TYPE_MASK 7 //类型掩码
#define SDS_TYPE_BITS 3
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); //获取header头指针,其中##是拼接的含义
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T)))) //获取header头指针
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS) //获取sdshdr5的长度

struct __attribute__ ((__packed__)) sdshdr5 { //5种header定义，节省内存使用
uint8_t len; // 字符串实际长度
uint8_t alloc; //字符串已拥有的内存空间容量 sdsalloc() = sdsavail() + sdslen()
unsigned char flags;//表示类型,见宏定义
char buf[];//buf[] : 字符串内容
};

static inline size_t sdslen(const sds s) { //计算sds长度
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return SDS_TYPE_5_LEN(flags);
case SDS_TYPE_8:
return SDS_HDR(8,s)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}

//计算sds可用空间
static inline size_t sdsavail(const sds s) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5: {
return 0;
}
case SDS_TYPE_8: {
SDS_HDR_VAR(8,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
return sh->alloc - sh->len;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
return sh->alloc - sh->len;
}
}
return 0;
}

//设置sds长度
static inline void sdssetlen(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
{
unsigned char *fp = ((unsigned char*)s)-1;
*fp = SDS_TYPE_5 | (newlen << SDS_TYPE_BITS);
}
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->len = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->len = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->len = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->len = newlen;
break;
}
}

SDS与C字符串的区别

1、常数复杂度获取字符串长度

SDS获取字符串数组的时间复杂度是O(1)，因为有len属性记录字符串的长度，而C语言需要遍历一遍才能获得字符串的长度，时间复杂度为O(N)。

2、杜绝缓冲区溢出

<string.h>/strcat 函数可以将src中的内容拼接到 dest 字符串末尾：

char *strcat(char *dest , char *src);

因为c不会记录字符串长度，使用strcat函数的时候，假设已经为 dest 分配了足够多的空间，可以容纳 src 但是，这一假设不成立的时候，就产生了内存溢出。

如图所示，内存中有两个字符串，分别为s1 s2，当执行语句;

strcat(s1 , " world");

但是，没有给s1分配足够多的空间，在执行完语句后会变成下图

这时，s2的内容被意外修改了，而与C语言策略不同，SDS进行修改前，会事先检查SDS的空间是否满足修改所需的要求，如不满足会自动扩展至所需空间。

3、减少修改字符时扩展内存的次数

拿C语言字符串来说，如果需要连续地使用 strcat 函数，为避免内存泄漏，需要连续地扩展空间，为了避免C语言这种缺陷，SDS实现了空间与分配和惰性空间释放两种优化策略

1、空间预分配

SDS大小	分配策略
小于1MB	分配的未使用空间 free = len ,例如：如果修改后的SDSlen长度为5，那么free分配的空间也是5 ，总空间就是 5 + 5 + 1 = 11（额外1字节给空字符）
大于等于1MB	分配的未使用空间为 1MB ,例如：如果修改后的SDSlen长度为5MB，那么free分配的空间就是 1MB ，总空间就是 5MB + 1MB + 1byte（额外1字节给空字符）

这样就降低了内存重分配的次数，连续增长N次的重分配次数从必定N次降低为最多N次。

2、惰性空间释放

此策略用于优化字符串缩短操作，例如：sdstrim函数执行，对于字符串 s 。