redis sds

结构

sds主要由lenallocbuf构成。其中buf是柔性数组,分配sds的时候,这个结构体会作为header。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
typedef char *sds;

/* 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; /* 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[];
};

// 如果没有packed,那么sizeof(sdshdr32) =
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[];
};

为sds分配空间,initlen是字符串的长度,1是末尾的'\0'。

1
sh = s_malloc(hdrlen+initlen+1);

sdsnewlen、sdslen,sdsavail

sdsnewlen返回的是char buf[]首元素的地址,这个值作为sds指针的值。这是sds中巧妙的地方。但是如何获取header地址,以及访问成员?毕竟相关字段是在柔性数组的前面。

  • sds - 1就是flag,由flag可以得知header类型,也就知道header的长度,减去header的长度得到header的地址,访问len成员即可得知buf长度。

    1
    #define SDS_HDR(T,s) ((struct sdshdr##T *)((s)-(sizeof(struct sdshdr##T))))

  • sdshdr5是一个特别的类型,长度和类型都隐藏在了flag里面。SDS_TYPE_5存储的是长度小于1 << 5的字符数组,也就是可以用5 bit来表示。这样加上3 bit的类型,合起来刚好8 bit,就是一个flag

    1
    *fp = type | (initlen << SDS_TYPE_BITS);

    因此flag的3 lsb作为类型,5 msb作为长度。但sdshdr5无法记录空闲的空间,因此无法扩容。

sdsgrowzero

  • 新长度小于1MB,则buf大小翻倍
  • 新长度大于等于1MB,则buf加1MB

sdstrim

trim后并未释放buf的空间。

提供了sdsRemoveFreeSpace函数,可以完成在尾部没有空闲的空间。

sds与c字符串的区别

  • 参数时间获取字符串长度
  • 记录长度,避免buffer overflow
  • 空间预分配、惰性释放,减少重分配次数
  • 二进制安全
  • 兼容部分c字符串函数

问题

  1. sds的定义使用了pack,内存没有对齐的情况下,会影响cpu访问内存的性能,这个是如何解决的?

References

  1. Redis源码阅读计划
  2. Redis源码从哪里读起?
  3. Redis 深度历险:核心原理与应用实践