Redis源码阅读--SDS nosqlredis

简单动态字符串 SDS Redis没有直接用C的字符串 (以空字符结尾的字符数组)，而自己构建了一种字符串(simple dynamic string,SDS)的抽象类型。
包含字符串值得键值对再底层都是SDS实现的

127.0.0.1:6379> set msg "hello wordl" OK键是一个字符对象底层就是一个保存字符串"msg"的SDS 值也是一个字符串对象，底层就是一个保存字符串"hello world"的SDS127.0.0.1:6379> rpush fruits "apple" "banana" "cherry" (integer) 3 这里的值就是一个列表对象列表里有三个SDS对象

SDS除了被用作存储字符串，还被用作缓冲区(buffer)：AOF的缓冲区，客户端状态的输入缓冲区都是SDS实现的
SDS的定义

/* * 类型别名，用于指向 sdshdr 的 buf 属性 */ typedef char *sds; /* * 保存字符串对象的结构 */ struct sdshdr {// buf 中已占用空间的长度 int len; // buf 中剩余可用空间的长度 int free; // 数据空间 char buf[]; }; 这里的buf是char数组所以最后一个字节还是保存了结束符'\0' 如果要出入字符串Redis五个字符 buf中实际存储的是 'R'、'e'、'd'、'i'、's'、'\0' 六个字符但实际这多出来的len里面这么做个好处是SDS可以只有重用C字符串的一部分函数。比如可以直接用printf打印

C字符串因为用N+1表示N的字符串不满足Redis对字符串再安全性和效率方面不满足。
常数复杂度获取字符串长度 C的字符串是不记录本身长度信息的，所以SDS获取查本身长度是O(1).
所以非常长的字符串执行 strlen就可以直接获得长度不会对系统性能造成影响

127.0.0.1:6379> strlen msg (integer) 11

杜绝缓冲区溢出 C的字符串容易造成缓冲区溢出(buffer overflow)

/strcat可以将src字符串中的内容拼接到dest字符串末尾 char *strcat(char *dest,const char *src)因为C字符串不记录自己的长度，所以strcat假定用户再执行这个函数时，已经为dest分配了足够多的内存，可以继续容纳src字符串中的内容，如果实际不满足就会产生缓冲区溢出。(C语言一向认为自己的程序员时最聪明的，任何做法都是有意义且正确的)SDS的API需要对SDS进行修改时，会先检查SDS空间是否满足修改所需要求，如果不满足API就会自动将SDS空间扩展到所需的大小。

SDS初始化

sds sdsnewlen(const void *init, size_t initlen) {struct sdshdr *sh; // 根据是否有初始化内容，选择适当的内存分配方式 // T = O(N) if (init) { // zmalloc 不初始化所分配的内存 sh = zmalloc(sizeof(struct sdshdr)+initlen+1); } else { // zcalloc 将分配的内存全部初始化为 0 sh = zcalloc(sizeof(struct sdshdr)+initlen+1); }// 内存分配失败，返回 if (sh == NULL) return NULL; // 设置初始化长度 sh->len = initlen; // 新 sds 不预留任何空间 sh->free = 0; // 如果有指定初始化内容，将它们复制到 sdshdr 的 buf 中 // T = O(N) if (initlen && init) memcpy(sh->buf, init, initlen); // 以 \0 结尾 sh->buf[initlen] = '\0'; // 返回 buf 部分，而不是整个 sdshdr return (char*)sh->buf; }

sds sdscat(sds s, const char *t) { return sdscatlen(s, t, strlen(t)); }//对接函数 sds sdscatlen(sds s, const void *t, size_t len) {struct sdshdr *sh; // 原有字符串长度 size_t curlen = sdslen(s); // 扩展 sds 空间 // T = O(N) s = sdsMakeRoomFor(s,len); // 内存不足？直接返回 if (s == NULL) return NULL; // 复制 t 中的内容到字符串后部 // T = O(N) sh = (void*) (s-(sizeof(struct sdshdr))); memcpy(s+curlen, t, len); // 更新属性 sh->len = curlen+len; sh->free = sh->free-len; // 添加新结尾符号 s[curlen+len] = '\0'; // 返回新 sds return s; }//扩容函数 sds sdsMakeRoomFor(sds s, size_t addlen) {struct sdshdr *sh, *newsh; // 获取 s 目前的空余空间长度 size_t free = sdsavail(s); size_t len, newlen; // s 目前的空余空间已经足够，无须再进行扩展，直接返回 if (free >= addlen) return s; // 获取 s 目前已占用空间的长度 len = sdslen(s); sh = (void*) (s-(sizeof(struct sdshdr))); // s 最少需要的长度 newlen = (len+addlen); // 根据新长度，为 s 分配新空间所需的大小 if (newlen < SDS_MAX_PREALLOC) // 如果新长度小于 SDS_MAX_PREALLOC // 那么为它分配两倍于所需长度的空间 newlen *= 2; else // 否则，分配长度为目前长度加上 SDS_MAX_PREALLOC newlen += SDS_MAX_PREALLOC; // T = O(N) newsh = zrealloc(sh, sizeof(struct sdshdr)+newlen+1); // 内存不足，分配失败，返回 if (newsh == NULL) return NULL; // 更新 sds 的空余长度 newsh->free = newlen - len; // 返回 sds return newsh->buf; }void* __cdecl memcpy( _Out_writes_bytes_all_(_Size) void* _Dst, _In_reads_bytes_(_Size)void const* _Src, _In_size_t_Size ); //获得sds的可用空间 static inline size_t sdsavail(const sds s) { struct sdshdr *sh = (void*)(s-(sizeof(struct sdshdr))); return sh->free; }//使用的内存字节数 static size_t used_memory = 0; //是否线程安全 0=安全 1=不安全 static int zmalloc_thread_safe = 0; //更新used_memory时用到的互斥锁 pthread_mutex_t used_memory_mutex = PTHREAD_MUTEX_INITIALIZER; void *zrealloc(void *ptr, size_t size) { #ifndef HAVE_MALLOC_SIZE void *realptr; #endif size_t oldsize; void *newptr; if (ptr == NULL) return zmalloc(size); #ifdef HAVE_MALLOC_SIZE oldsize = zmalloc_size(ptr); newptr = realloc(ptr,size); if (!newptr) zmalloc_oom_handler(size); update_zmalloc_stat_free(oldsize); update_zmalloc_stat_alloc(zmalloc_size(newptr)); return newptr; #else realptr = (char*)ptr-PREFIX_SIZE; oldsize = *((size_t*)realptr); newptr = realloc(realptr,size+PREFIX_SIZE); if (!newptr) zmalloc_oom_handler(size); *((size_t*)newptr) = size; update_zmalloc_stat_free(oldsize); update_zmalloc_stat_alloc(size); return (char*)newptr+PREFIX_SIZE; #endif }

//非线程安全调教下zmalloc分配内存时更新使用内存字节数 #define update_zmalloc_stat_add(__n) do { \ pthread_mutex_lock(&used_memory_mutex); \ used_memory += (__n); \ pthread_mutex_unlock(&used_memory_mutex); \ } while(0)#define update_zmalloc_stat_sub(__n) do { \ pthread_mutex_lock(&used_memory_mutex); \ used_memory -= (__n); \ pthread_mutex_unlock(&used_memory_mutex); \ } while(0)#endif//zmalloc和zcalloc分配内存以后更新使用内存字节数 #define update_zmalloc_stat_alloc(__n) do { \ size_t _n = (__n); \ if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \ if (zmalloc_thread_safe) { \ update_zmalloc_stat_add(_n); \ } else { \ used_memory += _n; \ } \ } while(0)#define update_zmalloc_stat_free(__n) do { \ size_t _n = (__n); \ if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \ if (zmalloc_thread_safe) { \ update_zmalloc_stat_sub(_n); \ } else { \ used_memory -= _n; \ } \ } while(0)可以看到update_zmalloc_stat_alloc负责在分配内存后增加used_memory的值，update_zmalloc_stat_free负责在释放内存后减少used_memory的值，输入参数_n即为新增或者减少的内存。在这两个宏定义内部，又分为了线程安全和不安全两种情况，不安全时需要通过线程锁进行互斥访问。对于 if (_n&(sizeof(long)-1)) _n += sizeof(long)-(_n&(sizeof(long)-1)); \它的主要作用是如果分配或者释放的内存_n不是long类型字节数的整数倍，则将它向上调整为sizeof(long)的整数倍，最终保证used_memory是sizeof(long)的整数倍。#define PREFIX_SIZE (sizeof(size_t)) //zmalloc:分配内存，分配时多分配PREFIX_SIZE用于记录当前分配的内存所占字节数 void *zmalloc(size_t size) { void *ptr = malloc(size+PREFIX_SIZE); if (!ptr) zmalloc_oom_handler(size); #ifdef HAVE_MALLOC_SIZE update_zmalloc_stat_alloc(zmalloc_size(ptr)); return ptr; #else *((size_t*)ptr) = size; update_zmalloc_stat_alloc(size+PREFIX_SIZE); return (char*)ptr+PREFIX_SIZE; #endif }//是否malloc分配的空间，更新内存使用字节数 void zfree(void *ptr) { #ifndef HAVE_MALLOC_SIZE void *realptr; size_t oldsize; #endifif (ptr == NULL) return; #ifdef HAVE_MALLOC_SIZE update_zmalloc_stat_free(zmalloc_size(ptr)); free(ptr); #else realptr = (char*)ptr-PREFIX_SIZE; oldsize = *((size_t*)realptr); update_zmalloc_stat_free(oldsize+PREFIX_SIZE); free(realptr); #endif }为了在释放内存时可以知道这块内存的大小以更新used_memory，在分配内存时额外分配了sizeof(size_t)大小的空间，并用它来记录分配的内存大小

减少修改字符串时带来的内存重分配次数对于C来说每次增长或者缩短一个字符串，程序都要对字符串
数字进行一次内存重分配。这一步时需要程序员自己去卸载程序里的
一般情况下如果修改字符串长度的情况不常出现，那么每次修改都执行溢出内存分配时可以接收的。
但Redis注重速度，如果每次修改字符串长度都要重新分配溢出内存那时不能接受的。
那个SDS通过未使用空间 int free 来解除了字符串长度与底层数组长度之间的关联。所以再SDS中buf数组的长度不一定时字符数加一，数组里面还可以包含未使用的字节，而这些字节的数量就是由SDS的free属性记录。
通过未使用空间SDS实现了空间预分配和惰性空间释放两种优化策略。
空间预分配用于优化SDS字符串增长操作，当SDS的API对SDS进行修改并且需要对SDS进行空间扩展时，程序不仅会为SDS分配必须的空间，还会为SDS分配额外的未使用空间也就时free。
分配算法
1、如果对SDS进行修改之后，SDS的长度（也就是len属性的值）将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS len属性的值将和free属性的值相同。

如果修改之后，SDS的len将变成13字节那么程序会分配13字节的未使用空间， SDS的buf数组的实际长度将变成13+13+1=27字节。

2、如果对SDS进行修改后SDS的长度大于等于1MB，那么程序会分配1MB的未使用空间

如果进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间 SDS的buf数组实际长度将变为30MB+1MB + 1byte

惰性空间释放用于优化SDS的字符串缩短操作：当SDS的API需要缩短SDS保存的字符串时，程序并不立刻使用内存重分配来回收缩后多出来的字节，二是使用free属性将这些字节数量记录起来，并等待使用。
二进制安全 C字符串中的字符必须符合某种编码(比如ASCII)，并且除了字符串末尾之外，字符串里面不能包含空字符,否则最先被程序读入的空字符将会被误认为是字符串结尾，这些限制使得C字符串只能保存文本数据，而不能保存像图片、音频、视频、压缩文件这样的二进制数据。
为了确保Redis可以适用各种不同的是哟个场景，SDS的API都是二进制安全的，所以SDS API都会以处理二进制的方式处理SDS存放再buf数组里的数据，车光绪不会对数据做任何内容上的处理。
所以SDS的属性称为字节数据，buf存不是字符，存档是二进制数据。
SDS使用len属性的值而不是空字符来判断结束，所以就不会出现不能保存 '\0'的问题。
兼容部分C字符串函数之所以保存以空字符 '\0'结尾就是为了让那些保存文本数据的SDS可以重用一部分库定义的函数。