0%

SDS实现从1.0到2.0

Posted on Edited on In

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

有分配就有收回
关于收回有两个函数sdstrim和sdsRemoveFreeSpace
第一个并没有回收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，然后再对长度所在的地址进行取值