redis核心数据结构
Redis是一个存储在磁盘上的内存数据库。数据模型是key-value，但支持许多不同类
型的值:字符串、列表、集合、排序集合、哈希、流、HyperLogLogs、位图。
redis的特性:
基于内存，c语言编写、单线程架构
基于键值对的结构服务器: 支持string，hash，list,set,zset
内置丰富功能：键的过期策略，具有发布订阅功能，支持lua脚本(可创建新redis命令)，pipeline(批量命令)。
持久化 rdb和aof
主从，哨兵，分布式集群
redis的功能使用
1-缓存
2-排行榜
3-计数器
4-消息队列系统
5-。。。
本文分析redis的核心数据结构：动态字符串sds
如何实现一个扩容方便且2进制安全的字符串呢？
即在c中字符串结尾用'\0'表示结束，不能把本身就含有'\0'的字符截断，而且还能还原原2进制含义。
sds.h 3.0版本
struct sdshdr {
//buf中已经使用的字节的数量
int len;
//buf中未使用的字节的数量
int free;
//保存字符串的字节数组
char buf[];
};
sds-API使用如下
总结sds设计优点优点
- 数组的地址是连续的
- 获取长度时间复杂度为O(1)（sdslen）
- 空间分配策略防止有缓存溢出。(sdscatlen)
- 通过 空间预分配和 惰性空间 减少 内存 扩展的次数。(sdscatlen,sdstrim)
- 二进制安全，可以保存任何二进制的数据（sdsnewlen）。
- 兼容C字符串。
sds5.0版本
好家伙redis3.0这样设计确实比c好处大大滴，来看看5.0版本。
c语言中，有char、bool、short、int、float、double、long、这几种基本类型，1、2、4、8.小于1(使用位运算将一个数当成2个数使用)，有五种类型区分开来需要3bit(2^3=8)才能表达。
-
长度在32之内的字符串
struct __attribute__ ((__packed__))sdshdr5 { unsigned char flags; /* 低3位存储类型, 高5位存储长度 */ char buf[];/*数组，存放实际内容*/ }; -
长度>32的字符串
typedef unsigned char uint8_t;//1 字节 typedef unsigned short int uint16_t;//2 个字节 typedef unsigned int uint32_t;//4 个字节 typedef unsigned long int uint64_t;//8 个字节 struct __attribute__ ((__packed__)) sdshdr5 { unsigned char flags; /* 3 lsb of type, and 5 msb of string length */ 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[]; };
len ：buf中已占用字节数. alloc : buf 分配的总长度。 flags中3bit用来记录字符串类型，5bit未使用。 buf ：真正存储字符串的数据空间。
1-一般情况下，结构体会按其所有变量大小的最小公倍数做字节对齐。attribute((packed))修饰后，结构体则变为按1字节对齐。所以对于sdshdr32类型-使用packed前是4字节对齐，修饰后按照1字节对齐，节约3字节。
2-c语言中struct中的属性的编写顺序是lags在buf之前，sds返回的是buf指针，buf[-1]则是flags。
动态扩容-在sds调用sdscatsds拼接的时候
sds sdscatsds(sds s, const sds t) { return sdscatlen(s, t, sdslen(t)); }
sds sdscatlen(sds s, const void *t, size_t len)
sds sdscat(sds s, const char *t) {
return sdscatlen(s, t, strlen(t));
}
sds sdscatlen(sds s, const void *t, size_t len) {
size_t curlen = sdslen(s);
s = sdsMakeRoomFor(s,len);
if (s == NULL) return NULL;
memcpy(s+curlen, t, len);//直接拼接，保证了二进制安全
sdssetlen(s, curlen+len);//加上结束符
s[curlen+len] = '\0';
return s;
}
1）若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在数组buf末尾追加即可，无须扩容，直接返回s。
2)若需要扩容，则返 回扩容好的新字符串s。函数中的len、curlen等长度值是不含结束符的，而拼接时用memcpy将两个字符串拼接在一起，指定了相关长 度，故该过程保证了二进制安全，最后需要加上结束符。
3）最后根据新长度重新选取存储类型，并分配空间。此处若无 须更改类型，通过realloc扩大柔性数组即可；否则需要重新开辟内 存，并将原字符串的buf内容移动到新位置。
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. */
//若sds中剩余空闲长度avail大于新增内容的长度addlen，直接在数组buf末尾追加即可，无须扩容。直接返回s。
if (avail >= addlen) return s;
//若sds中剩余空闲长度avail小于或等于新增内容的长度 addlen.
len = sdslen(s);
sh = (char*)s-sdsHdrSize(oldtype);
newlen = (len+addlen); //1024*1024
if (newlen < SDS_MAX_PREALLOC)//新增后总长度len+addlen<1MB的
newlen *= 2;//扩容2倍
else
newlen += SDS_MAX_PREALLOC;//加上1MB
//最后根据新长度重新选取存储类型
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) {
//扩大buf长度
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;
//将原buf内容移动到新位置
memcpy((char*)newsh+hdrlen, s, len+1);
s_free(sh);//释放旧指针
s = (char*)newsh+hdrlen;//偏移sds结构的起始地址，得到字符串起始地址
s[-1] = type;//为falgs赋值
sdssetlen(s, len);//长度赋值
}
sdssetalloc(s, newlen);//为len属性赋值
return s;
}
小结:
注意:malloc、calloc、realloc之间的区别
区别在于是否会对申请的内存空间进行初始化
函数malloc不能初始化所分配的内存空间，函数calloc() 会将所分配的内存空间中的每一位都初始化为零。
功能上的区别
malloc与calloc用来动态分配内存空间，而realloc则是对给定的指针所指向的内存空间进行扩大或者缩小。
