基于Redis5.0
Redis 没有直接使用 C 语言传统的字符串表示（以空字符结尾的字符数组，以下简称 C 字符串）， 而是自己构建了一种名为简单动态字符串（simple dynamic string，SDS）的抽象类型， 并将 SDS 用作 Redis 的默认字符串表示。
SDS定义
//<sds.h>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[];};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[];};//flag低3位保存sds类型，sdshdr5的flag高5位保存buf长度#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//过去指向sdshdr的指针，并赋给sh#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));//获取指向sdshdr结构体的指针#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))//获取sdshdr5的字符串长度，即flag字段中高5位存储的值#define SDS_TYPE_5_LEN(f) ((f)>>SDS_TYPE_BITS)
SDS_HDR --> | len | alloc | flag | buf（sds）|
unsigned char flags = sds[-1]
len：sds的长度，不包括末尾结束符alloc：分配的sds长度，不包括结束符flag：sds类型buf：sds实际存放位置
SDS 遵循 C 字符串以空字符结尾的惯例， 保存空字符的 1 字节空间不计算在 SDS 的 len 属性里面， 并且为空字符分配额外的 1 字节空间，遵循空字符结尾这一惯例的好处是， SDS 可以直接重用一部分 C 字符串函数库里面的函数，末尾空字符的分配在sdsnewlen函数里（sh = s_malloc(hdrlen+initlen+1);），下面有完整函数代码
SDS与C字符串的区别
常数复杂度O(1)获取字符串长度
获取一个 C 字符串的长度， 程序必须遍历整个字符串， 对遇到的每个字符进行计数， 直到遇到代表字符串结尾的空字符为止， 这个操作的复杂度为O(N)
SDS 在len属性中记录了 SDS 本身的长度， 所以获取一个 SDS 长度的复杂度仅为O(1)
杜绝缓冲区溢出
SDS 的空间分配策略完全杜绝了发生缓冲区溢出的可能性： 当 SDS API 需要对 SDS 进行修改时， API 会先检查 SDS 的空间是否满足修改所需的要求， 如果不满足的话， API 会自动将 SDS 的空间扩展至执行修改所需的大小， 然后才执行实际的修改操作， 所以使用 SDS 既不需要手动修改 SDS 的空间大小， 也不会出现缓冲区溢出问题
减少修改字符串时带来的内存重分配次数
C 字符串并不记录自身的长度， 所以对于一个包含了 N 个字符的 C 字符串来说， 这个 C 字符串的底层实现总是一个 N+1 个字符长的数组（额外的一个字符空间用于保存空字符），每次增长或者缩短一个 C 字符串， 程序都总要对保存这个 C 字符串的数组进行一次内存重分配操作，通过未使用空间（alloc - len）， SDS 实现了空间预分配和惰性空间释放两种优化策略
空间预分配
如果对 SDS 进行修改之后， SDS 的长度（也即是len属性的值）将小于 1 MB ， 那么程序分配和len属性同样大小的未使用空间， 这时 SDSalloc属性的值将是和len属性的2倍。 举个例子， 如果进行修改之后， SDS 的len将变成 13 字节， 那么程序也会分配 13 字节的未使用空间， SDS 的buf数组的实际长度将变成 13 + 13 + 1 = 27 字节（额外的一字节用于保存空字符）。
如果对 SDS 进行修改之后， SDS 的长度将大于等于 1 MB ， 那么程序会分配 1 MB 的未使用空间。 举个例子， 如果进行修改之后， SDS 的len将变成 30 MB ， 那么程序会分配 1 MB 的未使用空间， SDS 的 buf 数组的实际长度将为 30 MB + 1 MB + 1 byte 。
通过这种预分配策略， SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。
惰性空间释放
惰性空间释放用于优化 SDS 的字符串缩短操作： 当 SDS 的 API 需要缩短 SDS 保存的字符串时， 程序并不立即使用内存重分配来回收缩短后多出来的字节， 而是使用 free 属性将这些字节的数量记录起来， 并等待将来使用
通过惰性空间释放策略， SDS 避免了缩短字符串时所需的内存重分配操作， 并为将来可能有的增长操作提供了优化
二进制安全
C 字符串中的字符必须符合某种编码（比如 ASCII）， 并且除了字符串的末尾之外， 字符串里面不能包含空字符， 否则最先被程序读入的空字符将被误认为是字符串结尾 —— 这些限制使得 C 字符串只能保存文本数据， 而不能保存像图片、音频、视频、压缩文件这样的二进制数据
使用 SDS 来保存之前提到的特殊数据格式就没有任何问题， 因为 SDS 使用 len 属性的值而不是空字符来判断字符串是否结束，通过使用二进制安全的 SDS ， 而不是 C 字符串， 使得 Redis 不仅可以保存文本数据， 还可以保存任意格式的二进制数据
兼容部分 C 字符串函数
SDS 的 API 都是二进制安全的， 但它们一样遵循 C 字符串以空字符结尾的惯例： 这些 API 总会将 SDS 保存的数据的末尾设置为空字符， 并且总会在为 buf 数组分配空间时多分配一个字节来容纳这个空字符， 这是为了让那些保存文本数据的 SDS 可以重用一部分
SDS API
//<sds.h>//获取sds长度static inline size_t sdslen(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)->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可用的字节数 /* sdsalloc() = sdsavail() + sdslen() */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字符串的核心函数：
/* 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 sdsnewlen(const void *init, size_t initlen) {void *sh;sds s;char type = sdsReqType(initlen);/* Empty strings are usually created in order to append. Use type 8* since type 5 is not good at this. */if (type == SDS_TYPE_5 && initlen == 0) type = SDS_TYPE_8;int hdrlen = sdsHdrSize(type);unsigned char *fp; /* flags pointer. *///为结尾空字符多分配1字节的空间sh = s_malloc(hdrlen+initlen+1);if (init==SDS_NOINIT)init = NULL;else if (!init)memset(sh, 0, hdrlen+initlen+1);if (sh == NULL) return NULL;s = (char*)sh+hdrlen;fp = ((unsigned char*)s)-1;switch(type) {case SDS_TYPE_5: {*fp = type | (initlen << SDS_TYPE_BITS);break;}case SDS_TYPE_8: {SDS_HDR_VAR(8,s);sh->len = initlen;sh->alloc = initlen;*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;}}if (initlen && init)memcpy(s, init, initlen);s[initlen] = '\0';return s;}
扩容的核心函数：
//#define SDS_MAX_PREALLOC (1024*1024)/* 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 sdsMakeRoomFor(sds s, size_t addlen) {void *sh, *newsh;size_t avail = sdsavail(s);size_t len, newlen;char type, oldtype = s[-1] & SDS_TYPE_MASK;int hdrlen;/* Return ASAP if there is enough space left. */if (avail >= addlen) return s;len = sdslen(s);sh = (char*)s-sdsHdrSize(oldtype);newlen = (len+addlen);if (newlen < SDS_MAX_PREALLOC) //SDS_MAX_PREALLOC (1024*1024) = 1Mnewlen *= 2;elsenewlen += 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) {newsh = s_realloc(sh, hdrlen+newlen+1);if (newsh == NULL) return NULL;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;memcpy((char*)newsh+hdrlen, s, len+1);s_free(sh);s = (char*)newsh+hdrlen;s[-1] = type;sdssetlen(s, len);}sdssetalloc(s, newlen);return s;}
对给定字符或字符串进行分割：
/* Split 's' with separator in 'sep'. An array* of sds strings is returned. *count will be set* by reference to the number of tokens returned.** On out of memory, zero length string, zero length* separator, NULL is returned.** Note that 'sep' is able to split a string using* a multi-character separator. For example* sdssplit("foo_-_bar","_-_"); will return two* elements "foo" and "bar".** This version of the function is binary-safe but* requires length arguments. sdssplit() is just the* same function but for zero-terminated strings.*/sds *sdssplitlen(const char *s, ssize_t len, const char *sep, int seplen, int *count) {int elements = 0, slots = 5;long start = 0, j;sds *tokens;if (seplen < 1 || len < 0) return NULL;//tokens相当于是一个二维数组，默认先分配五个指针内存，即可以存5个被分割的字符串tokens = s_malloc(sizeof(sds)*slots);if (tokens == NULL) return NULL;if (len == 0) {*count = 0;return tokens;}for (j = 0; j < (len-(seplen-1)); j++) {/* make sure there is room for the next element and the final one */if (slots < elements+2) {sds *newtokens;slots *= 2;newtokens = s_realloc(tokens,sizeof(sds)*slots);if (newtokens == NULL) goto cleanup;tokens = newtokens;}/* search the separator */if ((seplen == 1 && *(s+j) == sep[0]) || (memcmp(s+j,sep,seplen) == 0)) {tokens[elements] = sdsnewlen(s+start,j-start);if (tokens[elements] == NULL) goto cleanup;elements++;start = j+seplen;j = j+seplen-1; /* skip the separator */}}/* Add the final element. We are sure there is room in the tokens array. */tokens[elements] = sdsnewlen(s+start,len-start);if (tokens[elements] == NULL) goto cleanup;elements++;*count = elements;return tokens;cleanup:{int i;for (i = 0; i < elements; i++) sdsfree(tokens[i]);s_free(tokens);*count = 0;return NULL;}}
返回指定范围内的字符串：
/* Turn the string into a smaller (or equal) string containing only the* substring specified by the 'start' and 'end' indexes.** start and end can be negative, where -1 means the last character of the* string, -2 the penultimate character, and so forth.** The interval is inclusive, so the start and end characters will be part* of the resulting string.** The string is modified in-place.** Example:** s = sdsnew("Hello World");* sdsrange(s,1,-1); => "ello World"*/void sdsrange(sds s, ssize_t start, ssize_t end) {size_t newlen, len = sdslen(s);if (len == 0) return;if (start < 0) {start = len+start;if (start < 0) start = 0;}if (end < 0) {end = len+end;if (end < 0) end = 0;}newlen = (start > end) ? 0 : (end-start)+1;if (newlen != 0) {if (start >= (ssize_t)len) {newlen = 0;} else if (end >= (ssize_t)len) {end = len-1;newlen = (start > end) ? 0 : (end-start)+1;}} else {start = 0;}if (start && newlen) memmove(s, s+start, newlen);s[newlen] = 0;sdssetlen(s,newlen);}
如果觉得《Redis5.0源码解析（一）----------简单动态字符串（SDS）》对你有帮助，请点赞、收藏，并留下你的观点哦！
