Redis字符串底层数据结构？
作者：程序员马丁
热门项目实战社群，收获国内众多知名公司面试青睐，近千名同学面试成功！助力你在校招或社招上拿个offer。
答题思路
回答话术
在 Redis 中，没有使用 C 标准库提供的字符串，而是实现了一种名为简单动态字符串（SDS, Simple Dynamic String）的数据结构来表示字符串。
SDS 由长度（len）、内存空间大小（alloc）、字符串类型（flags）和存储的字节数组（buf）四个部分组成。相较于 C 标准库的字符串，它具备以下优点：
- 高效的长度计算：SDS 记录了字符串长度，因此获取字符串长度时可直接返回，无需遍历每个字符。
- 二进制安全：SDS 不需要根据
\0特色字符判断字符串是否已经结束，因此可存储任何二进制数据，无需担心因为特殊字符引发异常。 - 高效修改的操作：SDS 记录了内存空间大小，因此写入时可计算剩余空间并决定是否自动扩容，结合追加字符串时的空间预分配和截取字符串时的惰性删除策略，最大程度的减少了修改时的内存重新分配次数。
- 节省内存：Redis 设计了五种不同类型的 SDS，每种对应某一大小范围的字符串，因此可以根据字符串的大小选择占用空间最少的 SDS 类型，并且不使用编译器的内存对齐，而是按实际大小分配内存。最大程度节省了内存。
问题详解
1. 高效的长度计算
对于 C 标准库 string.h 的字符串使用 char* 字符串数值记录字符，由于没有一个具体的长度，因此使用时需要遍历每一个字符，直到特殊字符 \0 为止。
Redis 使用一个额外的 len 属性来记录字符串的具体长度，所以当获取字符串长度时不必每次都要遍历数组。
2. 二进制安全
由于 C 标准库中的字符串使用 \0 作为结束符号，因此当把其他数据转而二进制存储时，就可能有可能因为在字符串中出现 \0 导致读取数据时提前结束。
而 Redis 不需要根据 \0 去判断字符串是否结束，因此它可以将任何数据转为二进制存储。
不过，为了兼容 C 标准库的一些操作，Redis 仍然为数组末尾的 \0 预留了内存空间。
3. 高效修改的操作
对于在 C 标准库的字符串，当我们进行修改操作的时候，可能需要频繁的重新分配内存大小。
Redis 的 SDS 除了使用 len 来记录字符串长度外，还使用 alloc 变量来记录字符串的分配到的内存大小，当修改字符串时，使用两值计算即可得知当前空间是否足够，并确认是否需要/不需要扩容。
当对字符串进行修改时，Redis 会根据修改后使用的空间大小，对 SDS 预分配额外的内存空间，一般来说，当其操作后的字符串大小 < 1MB，那么将 会额外分配一倍的未使用内存，若 > 1MB，那么将会额外分配 1MB 内存。
并且，当截取字符串时，Redis 不会立即释放字符串的内存空间，而是等到相关操作结束后再进行释放。
上述措施最大化的保证当频繁操作字符串时，不会因为额外的内存分配操作而影响性能。
在 3.2 及更早版本，Redis 使用 free 来记录未使用的内存大小，后面改为使用 alloc 记录已分配的总内存大小。
4. 节省内存
在 Redis 中， SDS 共有 sdshdr5、sdshdr8、sdshdr16、sdshdr32 与 sdshdr64 五种字符串，它们分别对应存储长度小于等于 2 的 5/8/16/32/64 次方字节的字符串。flags 属性则用于区分它们的属于哪种 SDS。
不同的 SDS 的 len 和 alloc 长度不同，比如 sdshdr32 中两者的长度类型为 uint32，而 sdshdr5 甚至直接使用 flags 的高 5 位存储长度，低 3 位存储类型。
此外，默认情况下编译器会使用内存对齐的方式分配内存，也就是说，编译器在为同一个结构体中的变量分配内存时，不会按实际大小分配内存，而是会为其分配额外的内存，保证最终每个成员变量分配的内存大小都为最大变量的整倍数，从而保证所有成员尽可能在内存中相邻。Redis 使用 __attribute__ ((__packed__)) 让编译器取消内存对齐，从而保证按实际大小分配内存，从而节约内存。
关于内存对齐，具体可以参见：掘金内存对齐 sourl.cn/kFeph7