Redis 数据结构 ( SDS) 实现
文章目录
Redis没有直接使用 C 语言的字符串,而是自己创建了名为 SDS (simple dynamic string, SDS) 的字符串。
c 语言已经有字符串,为什么redis要重复造轮子1、字符串的长度的处理,c 语言获取字符串需要遍历所有的字符长度 O(n), 而 redis的 sds 可以直接通过 len 来获取 O(1)。
2、内存重新分配,C 语言中涉及到修改字符串的时候会重新分配内存,修改地越频繁,内存分配也就越频繁,而 sds 使用 alloc 预分配,避免了频繁分配内存的问题。
一、二进制安全?
C 语言中,用 “\0” 表示字符串的结束,如果字符串本身就有 “\0” 字符,字符串就会报截断,既非二进制安全,若通过某种机制,保证写字符串时不会受损坏的内容,则是二进制安全。
二、sds 5种 数据结构及类型,代码在 sds.h 和 sds.c中实现。
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; /* used */
uint8_t alloc; /* excluding the header and null terminator */
unsigned char flags; /* 3 lsb of type, 5 unused bits */
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[];
};#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三、加入 attribute ((__packed__)) 和默认对齐的区别 ?
默认对齐
struct sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};

attribute ((__packed__))对齐
struct __attribute__ ((__packed__) ) sdshdr16 {
uint16_t len;
uint16_t alloc;
unsigned char flags;
char buf[];
};

两个好处:
1、可以节省内存(比如 sds16 可以节省 1 个字节)
2、sds返回给上层的,不是结构体首地址,而是指向内容的buf指针,因此此时按1字节对齐,故 sds 创建后,无论是 sdshdr8、sdshr16 还是 sdshdr32,都能通过 (char*)sh+hrlen得到buf的指针。
四、柔性数组
柔性数组只能被放在结构体的末尾,通过 malloc 动态分配内存。这样做的好处是结构体和柔性数组的地址是连续的,提升了一个局部性的访问。
五、flags 作用
struct __attribute__ ((__packed__)) sdshdr5 {
unsigned char flags; /* 低三位存储类型 , 高5位存储 长度 */
char buf[];
};

sds5、sds8、sds16、sds32、sds64 一共5种数据结构,而 2的2此方 为4,不能满足 存储 5种类型,所以需要 3 位(2的3次方 = 8)来存储。
其余的 5 个 bit 用来存储 长度 2的5次方-1 = 31,用来存储长度的、其他的数据结构flags高5位则忽略,因为已经有 len来表示。
可看到redis已经把字符串优化到极致。
六、通过宏 SDS_HDR_VAR 和 SDS_HDR 快速获取 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))))七、gdb 断点创建字符串。
代码
sds sdsnewlen(const void *init, size_t initlen) {
void *sh;
sds s;
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;
int hdrlen = sdsHdrSize(type);
unsigned char *fp; /* flags pointer. */
sh = s_malloc(hdrlen+initlen+1);
if (init==SDS_NOINIT)
init = NULL;
else if (!init)
memset(sh, 0, hdrlen+initlen+1);
if (sh == NULL) return NULL;
s = (char*)sh+hdrlen;
fp = ((unsigned char*)s)-1;
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 = initlen;
*fp = type;
break;
}
case SDS_TYPE_16: {
SDS_HDR_VAR(16,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_32: {
SDS_HDR_VAR(32,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
case SDS_TYPE_64: {
SDS_HDR_VAR(64,s);
sh->len = initlen;
sh->alloc = initlen;
*fp = type;
break;
}
}
if (initlen && init)
memcpy(s, init, initlen);
s[initlen] = '\0';
return s;
}首先查看 sds5,也就是长度小于32位的。
1、在 sdsnewlen 打个断点。

2、在redis客户端 执行 set sds 1

3、在 gdb 执行 c 和 n 、p。

1、init 可以看到正好是set 执行的字符串, sds。
2、initlen 可以看到传入的长度是 3 。
3、type = 0,也就是sds5。

1、s 是指向buf的指针。
2、fp 则是 flags,可以通过 s[-1]很方便的得到。
3、\0 为了=二进制安全。
八、根据不同的长度创建sds类型。
static inline char sdsReqType(size_t string_size) {
if (string_size < 1<<5) //32
return SDS_TYPE_5;
if (string_size < 1<<8) //256
return SDS_TYPE_8;
if (string_size < 1<<16) //65536
return SDS_TYPE_16;
#if (LONG_MAX == LLONG_MAX)
if (string_size < 1ll<<32) //4294967296
return SDS_TYPE_32;
return SDS_TYPE_64;
#else
return SDS_TYPE_32;
#endif
}sds 各种数据结构占用内存的大小:
总结:
1、可以看到当 key 的长度 < 32,会使用sds5,在实际的业务中,小于 32 的很常见,所以我们的key的长度接近32,那么就尽量小于32,这样可以节省内存空间。2、学到了 attribute ((__packed__)) 和 默认对齐的区别。
3、当 sds为5的时候并且值为空的时候会强制转化为sds8。4、sds是如何保证了二进制的安全。
其他接口可自行gdb 查看。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论