文章系转载，便于整理和分类，原文地址：https://blog.csdn.net/qq_33361976/article/details/109014012前言
本篇文章会讲到redis里面用到的最基础的数据类型sds，它相比较于普通string有什么不同了
废话不多说，下面正式进入主题
一、sds的结构
1. sds的定义
sds.h
//定义了一个char 指针
typedef char *sds;
/* 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[];
};
//lsb 代表有效位的意思，
//__attribute__ ((__packed__)) 代表structure 采用手动对齐的方式。
struct __attribute__ ((__packed__)) sdshdr8 {
//buf 已经使用的长度
uint8_t len; /* used */
//buf 分配的长度，等于buf[]的总长度-1，因为buf有包括一个/0的结束符
uint8_t alloc; /* excluding the header and null terminator */
//只有3位有效位，因为类型的表示就是0到4，所有这个8位的flags 有5位没有被用到
unsigned char flags; /* 3 lsb of type, 5 unused bits */
//实际的字符串存在这里
char buf[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};
// 与上面的变化只有len和alloc， 就是长度不同而已
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[];
};可以看到sds 这种结构在不同长度下，大体的结构是相同，唯一不同的 sdshdr5也没用到过。
2. sds的初始化
/* Create a new sds string with the content specified by the 'init' pointer
* and 'initlen'.
* If NULL is used for 'init' the string is initialized with zero bytes.
* If SDS_NOINIT is used, the buffer is left uninitialized;
*
* The string is always null-termined (all the sds strings are, always) so
* even if you create an sds string with:
*
* mystring = sdsnewlen("abc",3);
*
* You can print the string with printf() as there is an implicit \0 at the
* end of the string. However the string is binary safe and can contain
* \0 characters in the middle, as the length is stored in the sds header. */
// 因为sds 在最前面指定了整个字符的长度，即使中间出现\0结束符，也能正常编译， 而不至于担心因为出现了结束符/0，而导致解码失败。
sds sdsnewlen(const void *init, size_t initlen) {
// 这个指针会指向整个sds开始的地方
void *sh;
// sds 实际上也是一个指针，
// 但是s指向整个struct buf开始的位置
sds s;
//根据不同的长度返回不同的类型的sds
char type = sdsReqType(initlen);
/* Empty strings are usually created in order to append. Use type 8
* since type 5 is not good at this. */
// 空string 往往用于append ， 在这里可以看到sds type 5 类型会被怒sds type 8 替换掉
if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;
//获取struct的长度
int hdrlen = sdsHdrSize(type);
// flag 指针，这个指针就是用来表示sds 是哪个类型的
unsigned char *fp; /* flags pointer. */
//分配空间 这里+1 为的是分配一个结束符号
sh = s_malloc(hdrlen+initlen+1);
// sh在这里指向了这个刚刚分配的内存地址
if (sh == NULL) return NULL;
// 判断是否是init阶段
if (init==SDS_NOINIT)
init = NULL;
// 如果不是init阶段则清0
else if (!init)
//init 不为空的话
// 将sh这块内存全部设置为0
memset(sh, 0, hdrlen+initlen+1);
//s 指向了字符串开始的地址，hdrlen 可以看错sds head
s = (char*)sh+hdrlen;
//因为可以看到地址的顺序是 len,alloc,flag,buf,目前s是指向buf，
//那么后退1位,fp 正好指向了flag对应的地址。
fp = ((unsigned char*)s)-1;
//下面就是根据
switch(type) {
case SDS_TYPE_5: {
*fp = type | (initlen << SDS_TYPE_BITS);
break;
}
case SDS_TYPE_8: {
//这里使用了内连方法，让sh这个变量赋值了struct sdshdr
SDS_HDR_VAR(8,s);
//下面就是初始化长度，这里就没啥好说的了
sh->len = initlen;
sh->alloc = initlen;
//fp 对应的地址赋值了对应的type，type 的取值是1-4
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
//如果两者都不为空，则init 这个对应的字符串，赋值给s
if (initlen && init)
//这里是给buf赋值初始化
memcpy(s, init, initlen);
// 分配一个结束符
s[initlen] = '\0';
return s;
}
// 下面的方法，为上面的init 里面用到的工具方法
// 根据不同的string size 返回不同sds类型
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5)
return SDS_TYPE_5;
if (string_size < 1<<8)
return SDS_TYPE_8;
if (string_size < 1<<16)
return SDS_TYPE_16;
//这里应该是考虑到32位系统的原因
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32)
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}
// 根据不同的类型返回struct的长度
static inline int sdsHdrSize(char type) {
//SDS_TYPE_MASK的作用是清除不必要的位数 SDS_TYPE_MASK 为00000111
switch(type&SDS_TYPE_MASK) {
case SDS_TYPE_5:
return sizeof(struct sdshdr5);
case SDS_TYPE_8:
return sizeof(struct sdshdr8);
case SDS_TYPE_16:
return sizeof(struct sdshdr16);
case SDS_TYPE_32:
return sizeof(struct sdshdr32);
case SDS_TYPE_64:
return sizeof(struct sdshdr64);
}
return 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
// 可以看到s本来是指向buf的位置，减去struct的长度正好就是开始的位置
// 然后sh就指向了整个sds开始的位置
// T就是占位符，返回不同类型的struct
#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));
//下面这个就是直接返回对应的struct
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
//这个类型的可以不关注因为没有被用到
#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)3. sds 图解
4. sds 扩容
/* Enlarge the free space at the end of the sds string so that the caller
* is sure that after calling this function can overwrite up to addlen
* bytes after the end of the string, plus one more byte for nul term.
*
* Note: this does not change the *length* of the sds string as returned
* by sdslen(), but only the free buffer space we have. */
// 扩容sds， 这里有一点，如果sds本身还有剩余空间，那么多分配的空间等于 addlen-leftlen
sds sdsMakeRoomFor(sds s, size_t addlen) {
void *sh, *newsh;
//获取剩余可用的空间
size_t avail = sdsavail(s);
size_t len, newlen;
//在上面图解里面s的指针是这段空间的中间 ,那么-1就正好指向了flag
char type,oldtype = s[-1] & SDS_TYPE_MASK;
int hdrlen;
/* Return ASAP if there is enough space left. */
//如果可用空间大于需要增加的长度，那么直接返回
if (avail >= addlen) return s;
//len 已使用长度
len = sdslen(s);
//sh 回到指向了这个sds的起始位置。
sh = (char*)s-sdsHdrSize(oldtype);
// newlen 代表最小需要的长度
newlen = (len+addlen);
if (newlen < SDS_MAX_PREALLOC)
//但是实际会分配2倍的长度，如果空间小于最大阈值
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;
//获取新长度的类型
type = sdsReqType(newlen);
/* Don't use type 5: the user is appending to the string and type 5 is
* not able to remember empty space, so sdsMakeRoomFor() must be called
* at every appending operation. */
if (type == SDS_TYPE_5) type = SDS_TYPE_8;
hdrlen = sdsHdrSize(type);
if (oldtype==type) {
//sh是开始地址，在开始地址的基础上，分配更多的空间，
// 逻辑如同初始化部分，hdrlen 是head的长度，即struct本身大小
// 后面newlen 是buf 大小， +1 是为了结束符号
// sds 通常情况下是可以直接打印的
newsh = s_realloc(sh, hdrlen+newlen+1);
if (newsh == NULL) return NULL;
//s继续指向中间位置
s = (char*)newsh+hdrlen;
} else {
/* Since the header size changes, need to move the string forward,
* and can't use realloc */
//如果类型发生变化，地址内容不可复用，所以找新的空间。
newsh = s_malloc(hdrlen+newlen+1);
if (newsh == NULL) return NULL;
//复制原来的str到新的sds 上面,
//newsh+hdrlen 等于sds buf 地址开始的位置
//s 原buf的位置
//len+1 把结束符号也复制进来
memcpy((char*)newsh+hdrlen, s, len+1);
//释放前面的内存空间
s_free(sh);
//调整s开始的位置，即地址空间指向新的buf开始的位置
s = (char*)newsh+hdrlen;
//-1 正好到了flag的位置
s[-1] = type;
//分配len的值
sdssetlen(s, len);
}
//分配alloc的值
sdssetalloc(s, newlen);
//返回新的sds
return s;
}
// 给len 设值
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,可用的长度。
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;
}
/* sdsalloc() = sdsavail() + sdslen() */
// 获取alloc的长度
static inline size_t sdsalloc(const sds s) {
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)->alloc;
case SDS_TYPE_16:
return SDS_HDR(16,s)->alloc;
case SDS_TYPE_32:
return SDS_HDR(32,s)->alloc;
case SDS_TYPE_64:
return SDS_HDR(64,s)->alloc;
}
return 0;
}
// 给 alloc 设值
static inline void sdssetalloc(sds s, size_t newlen) {
unsigned char flags = s[-1];
switch(flags&SDS_TYPE_MASK) {
case SDS_TYPE_5:
/* Nothing to do, this type has no total allocation info. */
break;
case SDS_TYPE_8:
SDS_HDR(8,s)->alloc = newlen;
break;
case SDS_TYPE_16:
SDS_HDR(16,s)->alloc = newlen;
break;
case SDS_TYPE_32:
SDS_HDR(32,s)->alloc = newlen;
break;
case SDS_TYPE_64:
SDS_HDR(64,s)->alloc = newlen;
break;
}
}上面主要讲了sds是如何扩容的，可以看到sds的最大特点是可以预分配内存，在扩容方面也非常的高效。不用复制来复制去
5. 为什么要使用内存不对齐（非常重要，全网讲sds唯一讲到这点就在这里）
在看下面之前首先要对内存对齐有个基本概念，为什么要内存对齐了，这里就设计到cpu的工作原理相关了，可以百度cpu工作原理，主要是跟内存地址和寄存器的映射关系有关，但是有两条定理可以在这里了解。
一个32位的cpu， 每一个周期从内存里面能读到32位的数据。
基于这个原因和寄存器的原因，cpu的每次读的地址开始是4的倍数，打个比方我们要读地址2上面长度为4的数据，那么就需要两个周期， cpu首先得从0-3地址上面读数据，然后再从3-7的地址上面的数据， 在这里我们可以看到内存对齐的作用。 那么问题来了，对于redis 作者一个对内存和cpu 用到极致的作者，为什么还要用非对齐的sds了，原因在于sds的本身结构注定只能非对齐状态。 请看下图，在对齐状态我们的结构体在内存里面表现形势是如何的。
可以看到不同类型的sds 下面，pad 的位数也是不同的，那么我们要从sds 指针位置访问到flag，在不知道类型的情况下是不可能了，那么有同学又要发问了，去掉sdshdr8的结构不就行了吗，从理论来说这样牺牲的内存也不会太多，也保证了性能，但是这仅仅是在32位系统下面的结构，如果在64位系统，那可能又是另外一个结构了。 好的那么有同学又要说了 我们能不能把指针放到flag开始的位置。答案也是不能，但是：
这样我们就没办法完美兼容string，
这样我们也会引入各种类型判断调整，所以redis 最后还是用到内存不对齐这个方案。
总结
- 可以看到sds相较于普通c语言string 来说，是二进制安全的，因为string 没有长度标示当一段地址里面存在多个结束符号，string是没有办法访问到第一个/0后面的内容的，而正好sds的结构弥补了这一缺点。
- sds 对于动态扩容也是string 无法比拟的，如sds的结构让sds可以预分配内存，甚至在原有长度类型不变的基础上，可以在原来内存使用基础上。实现动态扩容，上文代码也讲解得非常清晰。那么这样的好处又是啥了，如果一个string 非常长的情况下，如果要在原来的String基础上做append 操作，那么需要把内容复制到新的地址上面，而这件事情是一件非常耗费性能的一件事，而sds正好解决这件事，尤其在将网络io数据转化为具体命令操作的时候，要经常对字符串做append操作。所以sds结构非常适合redis。
- 且sds也可以直接当做string来使用，巧妙的指针使用也是让sds完美兼容string。 至于为什么要讲sds，因为在redis 最基础的数据除了字典就是sds，所以再我们讲redis如何从网络报文转化为具体执行的命令前，我们得先熟悉下sds这个结构。