写在前面
以下内容是基于Redis 6.2.6 版本整理总结
Redis数据结构
Redis是以k-v形式存储的内存数据库，其中key和value都是以对象（object）的形式进行存储。对象分为：string、list、hash、set和zet五种对象，这五种对象的底层实现依赖于自己实现的一些数据结构，如：sds、quicklist、ziplist、hashtable、skiplist等。注意：key只能是string对象。
今天我们就来学习，Redis的sds（简单动态字符串）。
一、SDS（Simple Dynamic String，简单动态字符串）
Redis没有使用C语言传统的字符串表示方式（以’\0’结尾的字符数组），而是自己实现了sds的抽象类型，Redis默认使用sds作为字符串的表示。
set msg "hello, world"
其中，key为保存字符串“msg”的sds，value为保存字符串“hello，world”的sds。
除了用来保存字符串的值外，sds还被用作buffer（缓冲区），比如：AOF持久化模块中的AOF缓冲区，及客户端的输入缓冲区等。
1.1 SDS的定义
每个src/sds.h/sdshdr结构表示一个sds对象。sdshdrxx会根据字符串的实际长度，选取合适的结构，最大化节省内存空间。获取字符串长度时间复杂度O(1)。
attribute ((packed)) : 告诉编译器，不要因为内存对齐而在结构体中填充字节，以保证内存的紧凑，这样sds - 1就可以得到flags字段，进而能够得到其头部类型。如果填充了字节，则就不能得到flags字段。
/* 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; // 已经使用的字节数 uint8_t alloc; // 实际可以存储的字节最大长度，不包括SDS头部和结尾的空字符 unsigned char flags; // flags中的低3个bit决定使用哪种结构存储字符串，高5bit未使用 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[]; };
1.2 空间预分配
用来优化SDS的字符串增长操作：当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。
1.3 惰性空间释放
用来优化SDS字符串缩短操作：当SDS的API对一个SDS进行缩短时，程序并不立即回收多出来的字节，而是通过alloc和len的差值，将这些字节数量保存起来，等待将来使用。
1.4 二进制安全
C语言的字符串中的字符必须符合某种编码（如：ASCII），并且除了字符串末尾的空字符，其他位置不能包含空字符，否则，会出现数据被截断的情况，比如：
如果使用C字符串所用的函数来识别，只能读取到“hello”，后面的“world”会被忽略，这个限制使得C字符串只能保存文本数据，而不能保存图片、视频、压缩文件等二进制数据。
SDS的API都会以二进制的方式来处理SDS存放在buf数组里的数据，Redis使用这个数组保存的是一系列二进制数据，而不是保存字符。SDS使用len属性的值判断字符串是否结束，而不是空字符，即SDS是二进制安全的。
二、SDS 源码分析
2.1 头部信息
Redis 使用以下宏定义来标识SDS的头部
#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 // 通过字符串的大小返回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; #if (LONG_MAX == LLONG_MAX) if (string_size < 1ll<<32) return SDS_TYPE_32; return SDS_TYPE_64; #else return SDS_TYPE_32; #endif }
2.2 SDS 操作
SDS的头部和buf是一段连续的内存空间，所以，当我们得到一个SDS的对象s时，可以通过s[-1]得到flags字段，再减去sdshdr的大小就能找到该对象的起始地址。
2.2.1 一些宏定义
// 返回sds对象的起始地址 #define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T))); #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))
2.2.2 获取当前sds对象buf中存储的字符串长度
说明，s[-1]往后偏移一个字节，拿到flags的值，再通过和SDS_TYPE_MASK掩码“与”操作，得到头部的类型，再通过对应类型宏定义返回的头部指针的len属性获取字符串的长度。
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; }
2.2.3 获取当前sds对象剩余可用空间大小
同上，通过头的指针的alloc-len 得到可用空间的大小。
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; }
2.2.4 使用一个字符串初始化SDS对象
Redis 6.2.6 新增了 sdstrynewlen() 函数，和 sdsnewlen() 函数的区别在于 调用_sdsnewlen()函数的第三个参数，是否开启 trymalloc。如果开始了trymalloc，若分配函数返回NULL，不会走系统设置的zmalloc_default_oom异常处理函数，该函数直接会使程序退出。
// src/sds.c // sds mystring = sdsnewlen("abc",3); sds sdsnewlen(const void *init, size_t initlen) { return _sdsnewlen(init, initlen, 0); } sds sdstrynewlen(const void *init, size_t initlen) { return _sdsnewlen(init, initlen, 1); } sds _sdsnewlen(const void *init, size_t initlen, int trymalloc) { void *sh; sds s; // 根据字符串的长度选择合适的sdshdr头部 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; // 根据type获取头部大小 int hdrlen = sdsHdrSize(type); unsigned char *fp; /* flags pointer. */ size_t usable; assert(initlen + hdrlen + 1 > initlen); /* Catch size_t overflow */ // 是否开启trymalloc，usable 会保存实际分配的字节数 sh = trymalloc? s_trymalloc_usable(hdrlen+initlen+1, &usable) : s_malloc_usable(hdrlen+initlen+1, &usable); if (sh == NULL) return NULL; if (init==SDS_NOINIT) init = NULL; else if (!init) memset(sh, 0, hdrlen+initlen+1); // s从sds起始地址偏移hdrlen大小，指向buf的首地址 s = (char*)sh+hdrlen; // s往后偏移一个字节，指向flags fp = ((unsigned char*)s)-1; // usable: 实际分配的长度 // hdrlen: 头部大小 // 1: 结尾要保存'\0'的一个字节 usable = usable-hdrlen-1; // 计算实际buf可用的空间 // 如果 usable 大于该 type 对应的最大长度，修正 usable if (usable > sdsTypeMaxSize(type)) usable = sdsTypeMaxSize(type); // 填充头部各个属性字段，如：len alloc flags 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 = usable; *fp = type; break; } case SDS_TYPE_16: { SDS_HDR_VAR(16,s); sh->len = initlen; sh->alloc = usable; *fp = type; break; } case SDS_TYPE_32: { SDS_HDR_VAR(32,s); sh->len = initlen; sh->alloc = usable; *fp = type; break; } case SDS_TYPE_64: { SDS_HDR_VAR(64,s); sh->len = initlen; sh->alloc = usable; *fp = type; break; } } // 将要保存的字符串拷贝到sds对象对应的buf中 if (initlen && init) memcpy(s, init, initlen); // 结尾添加 '\0' s[initlen] = '\0'; // 将该sds对象返回出去 return s; }
2.2.5 空间预分配
Redis使用sdsMakeRoomFor(s, addlen)函数来为sds对象预分配addlen大小的空间。
sds sdsMakeRoomFor(sds s, size_t addlen) { void *sh, *newsh; // 获取该sds对象当前可用空间大小 size_t avail = sdsavail(s); size_t len, newlen, reqlen; // oldtype 保存该sds预分配前的type char type, oldtype = s[-1] & SDS_TYPE_MASK; int hdrlen; size_t usable; /* Return ASAP if there is enough space left. */ // 如果剩余空间足够，直接返回原对象 if (avail >= addlen) return s; // 获取该sds对象已使用字节数 len = sdslen(s); // 获取指向该sds对象起始地址的指针 sh = (char*)s-sdsHdrSize(oldtype); // 空间不够：则新分配的字节数 = old字节数 + 预分配的字节数 reqlen = newlen = (len+addlen); assert(newlen > len); /* Catch size_t overflow */ // 如果预分配的字节数在1M以内，每次翻倍newlen*2 ；如果大于等于1M，每次空间新增加1M if (newlen < SDS_MAX_PREALLOC) newlen *= 2; else newlen += SDS_MAX_PREALLOC; // 根据新的字节长度计算此时的type 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); assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */ // 如果扩展后的type和之前一样 if (oldtype==type) { newsh = s_realloc_usable(sh, hdrlen+newlen+1, &usable); 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_usable(hdrlen+newlen+1, &usable); if (newsh == NULL) return NULL; // 拷贝目标字符串 memcpy((char*)newsh+hdrlen, s, len+1); // 释放旧的sds对象 s_free(sh); // s 指向 buf s = (char*)newsh+hdrlen; s[-1] = type; // type赋值 sdssetlen(s, len); // 设置新sds对象的len属性，len还是原来字符串的长度，只是预分配了空间 } usable = usable-hdrlen-1; if (usable > sdsTypeMaxSize(type)) usable = sdsTypeMaxSize(type); sdssetalloc(s, usable); // 设置新sds对象的alloc属性 return s; }
