数据结构
redis 为了节省内存，针对不同的长度数据采用不同的数据结构。
sds.h 中定义了如下共五种，通常 SDS_TYPE_5 并不使用，因为该类型不会存放数据长度，每次都需要进行分配和释放。
#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
以 type = 1 为例
typedef char *sds; /* __attribute__ ((__packed__)) 的所用就是告诉编译器取消结构在编译过程中的优化对齐，按照实际占用 */ struct __attribute__ ((__packed__)) sdshdr8 { uint8_t len; /* 数据长度 */ uint8_t alloc; /* 去掉头和 null 结束符，有效长度+数据长度 */ unsigned char flags; /* 3 lsb of type, 5 unused bits */ // 变长数据 char buf[]; };
展示一个数据例子：
- free 属性的值为 0 表示这个 sds 没有分配任何未使用空间。
- len 属性的值为 5 ， 表示这个 sds 保存了一个 5 个长度的字符串。
- buf 属性是一个 char 类型的数组，数组保存了前面5个字节的字符串 'R'、'e'、'd' 、'i'、's' 。最后一个字符则保存了空字符 '\0'。
对于数据压缩的演示：
空间拓容
- 当前有效长度 >= 新增长度，直接返回；
- 更新之后，判断新旧类型是否一致；
- 一致使用 remailc, 否则使用 malloc + free
- a. 当前有效长度 >= 新增长度，直接返回
- 增加步长
- 新增长度小于预分配长度（1024 * 1204），扩大一倍
- 新增长度大于等于预分配的长度，每次加预分配长度（减少不必要的内存）
文件位置： sds.c/_sdsMakeRoomFor
#define SDS_MAX_PREALLOC (1024*1024) sds _sdsMakeRoomFor(sds s, size_t addlen, int greedy) { void *sh, *newsh; size_t avail = sdsavail(s); size_t len, newlen, reqlen; 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; len = sdslen(s); sh = (char*)s-sdsHdrSize(oldtype); reqlen = newlen = (len+addlen); assert(newlen > len); /* Catch size_t overflow */ if (greedy == 1) { //新增后长度小于预分配长度（1024 * 1024，扩大一倍: SDS_MAX_PREALLOC = 1024 * 1024） if (newlen < SDS_MAX_PREALLOC) 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; // 新老类型一致使用 remalloc, 否则使用 malloc + freea , 当前有效长度 >= 新增长度，直接返回 hdrlen = sdsHdrSize(type); assert(hdrlen + newlen + 1 > reqlen); /* Catch size_t overflow */ 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); s_free(sh); s = (char*)newsh+hdrlen; s[-1] = type; sdssetlen(s, len); } usable = usable-hdrlen-1; if (usable > sdsTypeMaxSize(type)) usable = sdsTypeMaxSize(type); sdssetalloc(s, usable); return s; }
空间缩容
在 trim 操作时，采用的是惰性释放即：不会立即使用内存重新分配来回收缩短的字节，只是移动和标记，并修改数据。
文件位置 sds.c/sdstrim
sds sdstrim(sds s, const char *cset) { char *end, *sp, *ep; size_t len; sp = s; ep = end = s+sdslen(s)-1; while(sp <= end && strchr(cset, *sp)) sp++; while(ep > sp && strchr(cset, *ep)) ep--; len = (ep-sp)+1; if (s != sp) memmove(s, sp, len); s[len] = '\0'; sdssetlen(s,len); return s; }
真正的删除操作是在后续操作中见 tryObjectEncoding
文件位置 server.c/tryObjectEncoding
void trimStringObjectIfNeeded(robj *o) { if (o->encoding == OBJ_ENCODING_RAW && sdsavail(o->ptr) > sdslen(o->ptr)/10) { o->ptr = sdsRemoveFreeSpace(o->ptr); } }
优点
- 常量获取字符串长度（len）
- 避免缓冲区溢出
- 减少字符串修改带来的内存频繁重分配次数
- 二进制操作安全：可以保持文本数据，也可以保持任意格式的二机制数据（如视频流等）
- 以 '\0' 结尾，使其兼容部分 C 字符串函数
其他
- sds 是 char* 的别名，可以理解为分配的是一块连续的内存（表头 + 数据），根据局部性原理可以提高访问速度。
- 数据存储不使用 SDS_TYPE_5， 因为该类型每次新数据时，都需要进行拓充。
- 利用 C 语言内存布局，在 SDS 结构体中使用了一个 0 长度的数组，既可以达到变长，又能保证内存也是连续的，因此在 SDS 一系列操作中，看到使用 s[-1] 这样的操作搞的很惊讶，当然这里 s 指向的是 buf 位置。
文件位置：sds.c/sdsalloc
/* sdsalloc() = sdsavail() + sdslen() */ 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; }
参考资料
- 《Redis 设计与实现》 黄健宏
