SDS从1.0到2.0

Redis中的字符串使用的是自己的实现,解决了使用原生字符串的一些弊端
在源码中定义为sds.h

1.0

1.0 的定义是这样的

1
2
3
4
5
struct sdshdr {
unsigned int len;
unsigned int free;
char buf[];
};

通过两个字段标记buf中空闲的大小和已经有的字符串的长度
获得了以下的好处

  • 使得strlen的时间复杂度变成了O(1)
  • 避免缓冲区溢出问题,使用自定义的strcat等函数
  • 空间预分配,当需要对SDS进行扩展的时候,如果空间不足,再分配时会依据一些策略预分配一些空间
    • 如果对SDS修改后len < 1MB,那么将预分配len大小的空间,就是free = len
    • 如果对SDS修改后len >= 1MB, 那么将预分配1MB大小的空间, 就是free = 1MB

有分配就有收回
关于收回有两个函数sdstrimsdsRemoveFreeSpace
第一个并没有回收buf数组,而是把多余的空间的大小写到了free中
第二个是进行了回收buf数组的操作
我再去看sdsRemoveFreeSpace的调用,发现其实调用的并不多
可能是Redis的场景中,直接delete的较多,进行remove并不多
而且Redis提供的操作中也只有append操作可以对字符串进行增加
具体哪些会调用remove,TODO一下,等后面看到了再说

我在看书的时候顺便去翻了下源码
发现3.2之后进行了一番的升级

变得略复杂

为什么要进行了升级呢,其实SDS的定义也不是毫无缺点
看这个issue就知道了
https://github.com/antirez/redis/issues/757
问题就在len和free的使用类型上,使用的是unsigned int

  • unsigned int,也就是32位,最多只能记录4GB大小,超过4G的大小将无法使用
  • 内存损耗,如果字符串都非常短,可能16位就能记录,那么32位就损耗了2位

(其实如果我倒觉得这两个不是什么问题,果然大佬的思想就是不一样)

但是既然问题提出来了就需要解决

简单的换len和free的类型吗
这个不行,因为你仔细观察上面两个缺点,发现他们其实是有点互斥的成分在里面
一个嫌弃是unsigned int过小,一个是嫌弃unsigned int过大

然后这个PR就提出了自适应的sdshdr
https://github.com/antirez/redis/pull/2509
也就是SDS2.0的实现

2.0

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

这是2.0的struct定义
根据长度分为了5种,分别是8位,16位,32位,64位
每个定义中使用了一个char类型的flags标记当前的struct是什么类型

再注意看还有一个__attribute__ ((__packed__))的定义
这个我也不知道是啥,所以特地去查了一下
结果是GCC的编译器的一个标记选项,使用紧凑结构编译
正常情况下的struct会使用内存对齐的
比如这个

1
2
3
4
5
6
7
8
struct stu {
char ch;
int v;
};
int main() {
printf("%d\n", (int) sizeof(struct stu));
return 0;
}

结果在我的64位机器上输出的是8
虽然char是1位,int是4位,但是因为对齐的原因,ch和v之间有三位是不用的,属于padding位
所以整个struct的占用大小是8

但是如果加上__attribute__ ((__packed__))选项呢

1
2
3
4
5
6
7
8
struct __attribute__ ((packed)) stu {
char ch;
int v;
};
int main() {
printf("%d\n", (int) sizeof(struct stu));
return 0;
}

你会发现输出的是5

这个关键词看起来是极好的,但是其实也有弊端
既然节约了空间,那么在时间上肯定是有损耗的
正常我们读取v数据在32位的数据总线上,读取一次就够了,因为地址总线按照32位进行寻址的
但是如果是上面这种,因为v分布在两个32位的地址中,数据总线可能需要进行两个读取才能把v的值拿到

说回SDS,既然分为了五种类型,那么在进行一些操作的时候就要分情况讨论了
因为在操作SDS的时候,统一的全部换成了地址进行操作

1
typedef char *sds;

之前的定义,len肯定是在前4位的,但是现在不知道了,所以要先找出type,看是哪一种类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static inline size_t sdslen(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)->len;
case SDS_TYPE_16:
return SDS_HDR(16,s)->len;
case SDS_TYPE_32:
return SDS_HDR(32,s)->len;
case SDS_TYPE_64:
return SDS_HDR(64,s)->len;
}
return 0;
}

比如计算长度这个,得先拿出flags,判断下属于哪个类型的SDS,然后再对长度所在的地址进行取值