Redis源码学习(2)-Redis中的动态字符串实现（上）
码农天地 -
在src/sds.h中定义了Redis中的动态String类型，这意味着，使用者仅仅需要调用接口API就可以向String加入数据，而不需要关心扩容的问题。Redis使用 typedef char *sds; 来描述这个动态String，其在内存中的分布格式为一个StringHeader以及在StringHeader后面一段连续的动态内存，而sds则是指向StringHeader后面的连续内存的第一个字节。其在内存中问分布情况可以入下图所示：
sds的头部信息主要包含了sds被分配的缓存大小以及已经使用的缓存的大小，根据所需要的分配缓存的大小，在Redis中定义了五种sds的头部信息：
sdshdr5，定义了类型SDS_TYPE_5sdshdr8，定义了类型SDS_TYPE_8sdshdr16，定义了类型SDS_TYPE_16sdshdr32，定义了类型SDS_TYPE_32sdshdr64，定义了类型SDS_TYPE_64上述的五种sdshdr分别表示最大可以分配缓存的大小，其中sdshdr5表示最大可以分配1 << 5大小的缓存，而sdshdr8表示最大可以分配1 << 8大小的缓存。除了sdshdr5之外，其余的头部信息都是按照如下格式（以sdshdr32为例）进行定义的：
struct __attribute__ ((__packed__)) sdshdr32
{
uint32_t len; //已经使用缓存的长度
uint32_t alloc; //包含header以及结尾null结束符在内分配的缓存的总长度
unsigned char flags; //低三位保存header类型信息，SDS_TYPE_32
char buf[]; //动态分配的缓存
};而sdshdr5头部的格式则是按照如下的方式进行定义的：
struct __attribute__ ((__packed__)) sdshdr5
{
unsigned char flags; //低三位保存header类型信息，高五位用于表示已经使用缓存的长度
char buf[]; //动态分配的缓存
};基于我们需要的String的长度，选择不同的sdshdr，这样可以达到节约空间的目的。通过Redis之中关于sdshdr数据类型的定义，我们可以发现，无论是哪种sdshdr,sdshdr.buf缓存字段之前，都是sdshdr.flags标记字段，在Redis之中，我们实际使用的sds变量，其实是指向sdshdr.buf的指针，而整个SDS是一段连续分配的内存，那么，如果我们通过sds向前偏移一个字节长度的话sds[-1]，一定是这个SDS数据的sdshdr.flags字段。通过位运算，我们便可以知道该SDS数据所使用sdshdr的类型，进而通过指针偏移，便可以获取到整个SDS的头部信息，后续很对对于SDS的基础操作都是通过该方式实现的。
在头文件之中定义了若干个宏以及静态函数用于实现对于sds的基础操作。
#define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))给定一个sds数据，使用SDS_HDR来获取其对应的sdshdr的头指针。其使用方法是通过SDS数据获取到对应的sdshdr.flags，进而得到HeaderType，通过调用SDS_HDR来获取
整个头部信息，例如：
unsigned char flags = s[-1];
switch (flags * SDS_TYPE_MASK)
{
...
case SDS_TYPE_8:
SDS_HDR(8, s)->len = new_len;
break;
...
}#define SDS_HDR_VAR(T,s) struct sdshdr##T *sh = (void*)((s)-(sizeof(struct sdshdr##T)));给定一个sds数据，声明一个sdshdr指针变量sh，并将这个sds对应的sdshdr头指正赋值给这个sh变量。
static inline size_t sdslen(const sds s);给定一个sds数据，获取其已使用缓存的长度，具体的实现方式为：
sdshdr的定义，以及sds在内存中的分布结构，通过s[-1]来获取StringHeader中的flags数据。根据flags计算出其对应的是什么类型的shshdr。调用宏SDS_HDR获取到对应的StringHeader的指针，进而获得len字段数据。static inline size_t sdsalloc(const sds s);给定一个sds数据，获取其分配缓存sdshdr.buf的总长度。
static inline size_t sdsavail(const sds s);给定一个sds数据，获取其缓存可用的长度，可以理解为sdsavail(s) == sdsalloc(s) - sdslen(s)。
static inline void sdssetlen(sds s, size_t newlen);给定一个sds数据，以及一个新的长度newlen，将sds的header中的len字段设置为newlen。
static inline void sdsinclen(sds s, size_t inc);给定一个sds数据，以及一个需要增加的长度inc，将sds的header中的len字段增加inc。需要注意的是，在sdsinclen中，并不会检查增加的长度inc是否是合法的，仅仅是将inc累加到sdshdr.len之中。这就需要调用者在调用sdsinclen接口之前，自己检查长度是否合法。
static inline void sdssetalloc(const sds s, size_t newlen);给定一个sds数据，以及一个新的长度newlen，将sds的header中的alloc字段设置为newlen。通过源码，我们可以发现，SDS_TYPE_5类型的sds数据与其他类型的sds数据不论在sdshdr结构，还是基础操作接口的处理，均有很大的差异。Redis在2015年7月15日的提交中引入了这个新的sds类型，作者自己给出的提交信息是：
结合后续其他操作接口对于SDS_TYPE_5类型的处理，我们可以认为，这个类型的sds数据，主要用于存储长度不超过32个字节，并且不会重新分配缓存的数据。对此，Redis的作者也给出了建议：
static inline int sdsHdrSzie(char type);
static inline char sdsReqType(size_t string_size);上述两个在src/sds.c头文件中定义的两个静态函数，分别用于返回一个特定HeaderType的头部结构体长度，以及根据一个string_size的长度，返回合适的HeaderType。
sds sdsnewlen(const void *init, size_t initlen);
sds sdsempty(void);
sds sdsnew(const char* init);
sds sdsdup(const sds s);
void sdsfree(sds s);其中sdsnewlen函数，是这一系列函数的基础，其作用是，给定一段初始化内存的头指针init，以及初始长度initlen，构建一个sds数据。这个函数会根据你需要初始化数据的长度initlen通过sdsReqType接口来选择所使用的HeaderType，8位，16位，32位还是64位，使用s_malloc调用，为其分配长度为headerSize + initlen + 1的缓存，之所以需要多分配出一个字节的缓存，是因为在Redis中的sds总是以0作为结束标记的，因为需要为这个结束标记多分配出一个字节的缓存。同时由于sds本质上是二进制安全的，这也就意味着在数据的中间也有可能会出现0，故此这也是我们为什么在头部信息结构体中需要sdshdr.len字段的原因。同时初始话Header中的type,len,alloc字段，并将init所指向的数据调用memcpy拷贝到sds的缓冲区中，同时以0作为结束标记(null-termined)。后续的三个接口都是通过调用sdsnewlen来完成相关功能的：
sdsempty函数用来创建一个空的sds数据。sdsnew函数可以从一个null-terminated的C风格字符串中创建一个sds数据。注意这个接口不是二进制安全的，因为其内部是使用strlen来计算传入数据长度的。sdsdup函数可以通过一个给定的sds数据，复制出一个新的sds数据并返回最后一个接口sdsfree函数通过调用s_free接口来释放一个给定的sds数据，需要注意的是，所释放的内容包括sds头指针，以及其前面的Header数据的整个缓存。
void sdsupdatelen(sds s);通过对内部数据调用strlen来更新sds的长度，这个接口在sds缓存被手动改写的情况下很有用。通常来说，这个接口用于缩短sds的sdshdr.len字段，但是这个接口不会对sdshdr.buf中的数据进行修改。
void sdsclear(sds s);用于清空一个sds数据的内容，与sdsupdatelen接口类似，这个函数不会释放或者修改已经存在的缓存。仅仅是将sdshdr.len长度字段清零，但是空间还在。
sds sdsMakeRoomFor(sds s, size_t addlen);sdsMakeRoomFor这个接口用于扩大一个给定sds数据的可用缓存空间，可以确保用户在调用这个接口之后，可以向缓存之中续写addlen个字节的内容，但是这个操作不会改变已经使用的缓存的大小，也就是不会改变sdslen调用的结果。
其中几个细节点：
如果当前sds的可用空间也就是sdsavail的大小大于addlen，那么该函数什么操作也不会执行。同时为了减少重复分配缓存所带来的系统开销，sdsMakeRoomFor接口总是会多分配出一些预留（最多1MB字节）的缓存：newlen = (len+addlen)
if (newlen < SDS_MAX_PREALLOC)
newlen *= 2;
else
newlen += SDS_MAX_PREALLOC;s_realloc接口为其增加缓存容量。扩容操作永远不会使用SDS_TYPE_5类型的Header，因为该类型的Header无法保存可用缓存的大小，这也就意味着，如果使用SDS_TYPE_5类型的sds，那么每次进行append操作的时候，都会调用sdsMakeRoomFor来重新分配缓存。那么对于一个SDS_TYPE_5类型的sds，在调用过一次sdsMakeRoomFor之后，至少会被升级的SDS_TYPE_8类型的sds。如果引发了Header的升级，那么会调用s_malloc接口来分配一个新的sds，将原始数据拷贝进去，返回新的sds指针,这也就意味着，调用者无法保证作为参数传入的sds指针在调用结束后是否依然有效，因此比如使用函数的返回值来执行后续操作s = sdsMakeRoomFor(s, newlen);。对于接口sdsMakeRoomFor，Redis的作者给出的建议是：
也就是说，当我们能确保sds中有足够的多余缓存时，那么就不要调用该接口。
sds sdsRemoveFreeSpace(sds s);sdsRemoveFreeSpace这个接口的用途是收缩sds的缓存大小，通过释放多余的可用空间，使之刚好保存sdslen大小的数据。
其中的细节点：
如果收缩导致Header的降级，那么调用s_malloc接口重新分配一个新的sds，拷贝数据后，返回新的sds。如果收缩没有导致Header的降级，那么直接调用s_realloc接口调整缓存大小，实现缓存释放。size_t sdsAllocSize(sds s);sdsAllocSize这个接口用与返回分配给指定sds数据的内存的总大小。
其中包含:
sds指针前的Header的大小缓存中已使用数据的大小可用空间的大小结束符0的大小这个接口与sdsalloc的区别是，sdsalloc返回的是sdshdr.buf分配的缓存的大小。
void* sdsAllocPtr(sds s);sdsAllocPtr这个接口返回一个sds数据直接被分配的头指针，也就是Header的指针。
void sdsIncrLen(sds s, ssize_t incr);可以理解为可以给指定的sds的sdshdr.len增加incr的长度，同时会导致sdsavail的可用空间减少，该接口只负责处理sds数据的长度，而不会改动其内容。基本应用场景:
sdsMakeRoomFor函数为sds扩容向sds的缓存之中写入数据调用sdsIncrLen函数，调整写入数据之后的sdslen长度oldlen = sdslen(s);
s = sdsMakeRoomFor(s, BUFFER_SIZE);
nread = read(fd, s+oldlen, BUFFER_SIZE);
/* ... check for nread <= 0 and handle it ... */
sdsIncrLen(s, nread);这个接口与sdsinclen类似，但是该接口更多的是提供给用户调用，其内部增加了长度校验机制，这就需要我们在调用前通过sdsMakeRoomFor接口来确保可用缓存空间，或者手动检查incr的大小，不能超过sdsavail的大小，否则会触发断言机制。
喜欢的同学可以扫描二维码，关注我的微信公众号，马基雅维利incoding
Tags 标签
加个好友，技术交流
