Redis源码sds学习十二-sds面试题

Redis(Remote Dictionary Server) 是一个使用 C 语言编写的，开源的（BSD许可）高性能非关系型（NoSQL）的键值对数据库，被广泛用于缓存方向， 所以在很多公司招聘时，都会问到Redis的相关内容，本文简单总结一下sds面试中经常碰到的知识点，以供参考。

sdshdr结构

说起sds，就必须提到sds的基本数据结构，sdshdr结构如下：

struct sdshdr {    
    // buf 中已占用空间的长度
    int len;

    // buf 中剩余可用空间的长度
    int free;

    // 数据空间
    char buf[];
};

比起c字符串，SDS有以下优点：

1. 常数复杂度获取字符串长度。

   和C字符串不同，因为SDS在len属性中记录了SDS本身的长度len，所以获取一个SDS长度的复杂度仅为O(1)。

   而c字符串中，需要调用strlen函数来计算得出长度。通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O(N)降低到了O(1)，这确保了获取字符串长度的工作不会成为Redis的性能瓶颈。这样即使我们队一个非常长的字符串键反复执行StrLen命令，也不会对系统性能造成任何影响。

2. 杜绝缓冲区溢出

   C字符串不记录自身长度带来的另一个问题是容易造成缓冲区溢出（buffer overflow），而SDS中不存在这个问题，因为可以读取len判断是否溢出。

   在 Redis 中，当 SDS API 需要对 SDS 进行修改时，API 会先检查 SDS 的空间是否满足修改所需的要求，如果不满足的话，API 会自动将 SDS 的空间扩展至执行修改所需的大小，然后才执行实际的修改操作。所以，使用 SDS 既不需要手动修改 SDS 的空间大小，也不会出现前面所说的缓冲区溢出问题。

3. 二进制安全

   c字符串中以'\0'表示结尾，这使得c无法正确存储包含'\0'的数据。因为没有提供额外的信息来区分'\0'是结尾还是数据的一部分。虽然可以使用base64等算法对数据进行编码来解决该问题，但这通常会降低代码的效率。

   SDS中，即使数据中出现了 '\0'，我们也可以通过 sdshdr::len 字段高效准确的获取长度。这样就避免了二进制的安全问题。

4. 减少修改字符串长度时所需的内存重分配次数

   Redis 的 SDS 实现了空间预分配优化策略。当 SDS 的 API 对一个 SDS 进行修改时，程序不仅会为 SDS 分配必须要的空间，还会为 SDS 分配额外的未使用空间。

   额外分配未使用空间数量的规则：

   当 SDS 的 len 属性值小于 1MB，程序分配和 len 属性同样大小的未使用空间。当 SDS 的 len 属性值大于 1MB，程序将多分配 1M 的未使用空间。通过这种预分配策略，SDS 将连续增长 N 次字符串所需的内存重分配次数从必定 N 次降低为最多 N 次。

   具体可见本公众号文章:Redis sds动态字符串学习二

5. 尾部 '\0' 使得SDS兼容部分C字符串函数

   sds分配存储区时，也会多分配一个空间，用于在字符串末尾添加'\0'，这就使得SDS也能复用c库中的一部分函数。

在Redis的sds部分中，只要将上面相关知识点弄懂，举一反三，但基本上在面试官问到sds这一块的知识点就没啥问题了，当然如果涉及到有些细节还需要看源码才能有更深的理解。

参考：

Redis设计与实现

https://ld246.com/article/1447315370203

http://www.shouhuola.com/q-21559.html

https://blog.csdn.net/Time_Limit/article/details/106583461

本人才疏学浅，理解水平有限，只是一家之言，如果有错误及不当之处，请批评指正。

如果对您有一点帮助，我就十分高兴，希望共同进步，也会继续学习并分享，请关注工作号hongmaolinux，点赞,在看和转发，十分感谢！