一、Redis-简单动态字符串(SDS)

[toc]

前言

复习一下之前看的东西，有些遗忘

SDS概述

Redis它是一个使用C语言写的内存K-V数据库，但是Redis没有直接使用C语言传统的字符串表示，它构建了属于Redis自己的一种简单动态字符串，结构体定义如下：

struct sdshdr{
    //记录buf数组中已使用字节的数量
    //等于SDS所保存字符串的长度
    int len;
    
    //记录buf数组中未使用字节的数量
    int free;
    
    //字节数组，用于保存字符串
    char buf[];
}

SDS和C字符串一样，都用 ‘\0’(空字符)来表示最后一位，不过保存空字符的1字节不计算在 SDS 的 len 属性里面。

SDS为什么比C字符串更适用于Redis

常数复杂度获取字符串长度

因为C字符串并不记录自身的长度信息，所以为了获取一个C字符串的长度，程序必须遍历整个字符串，对遇到的每个字符串计数，这个操作的时间复杂度为O(N)。

SDS它在len属性中记录了SDS本身的长度，所以获取一个SDS长度的时间复杂度为O(1)。

通过使用SDS而不是C字符串，Redis将获取字符串长度所需的复杂度从O(N)降到了O(1),确保获取字符串长度的工作不会成为Redis的性能瓶颈。

杜绝缓冲区溢出

因为C字符串不记录自身长度，所以在执行strcat函数拼接字符串时，如果事先分配了足够的内存空间则不会产生溢出，但若是没有分配足够的内存空间，则会产生内存溢出，溢出到相邻的空间中。

而当SDS的API需要对SDS进行修改时，API会先检查SDS的空间是否满足修改的所需的要求，如果不能满足的话，API会自动将SDS的空间扩展至所需的大小，然后才执行实际的修改操作。(SDS有它自己的空间分配策略，下面会讲)

减少修改字符串时带来的内存重分配次数

C字符串不记录自身的长度，所以我们每次增长或者缩短一个C字符串时，有可能会造成系统调用，从而给系统增加负担。

如果程序增长字符串，在操作之前程序会先通过内存重分配来扩展底层数组的空间大小（如果忘了这一步则会产生缓冲区溢出）
如果程序缩短字符串，在操作之前程序会先通过内存重分配来释放字符串不再使用的那部分空间（如果忘了这一步则会产生内存泄漏）

一般程序中，如果修改的字符串长度的情况不太常出现，那么每次修改执行一次内存重分配还是可以接受的，但是当我们频繁修改的时候，因为内存重分配是一个很耗时的操作，对于像Redis这种追求速度的数据库，显然不能每次修改都去执行一次内存重分配。

在Redis中，SDS通过未使用空间解除了字符串长度和底层数组长度之间的关联，SDS中buf数组的长度不一定就是字符串数量加一，数组里面可以包含未使用的字节，而这些字节的数量就由SDS的free属性记录。通过未使用空间，SDS实现了空间预分配和惰性空间释放两种优化策略。

空间预分配：当对SDS修改后，如果SDS长度小于1MB，那么程序分配和len属性同样大小的未使用空间，这时len属性的值将和free属性的值相同。如果对SDS修改后，SDS长度将大于1MB，那么程序会分配1MB的未使用空间。
通过这种方式，每次SDS的API都会检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间而不会重新分配内存
惰性空间释放：当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用。通过惰性空间释放，SDS避免了缩短字符串时所需的内存重分配操作。

二进制安全

C字符串的字符必须符合某种编码（ASCII），并且除了字符串的末尾外，字符串里不能包含空字符，否则最先被程序读入的空字符将被误认为是字符串结尾，这些限制使得C字符只能保存文本数据，不能保存像图片、音频、视频、压缩文件这样的二进制数据。但是SDS的API都是二进制安全的，所有的SDS的API都会以处理二进制的方式来处理SDS存放的buf数组里的数据，程序不会对其中的数据做任何限制、过滤、或者假设，这正是我们将SDS的buf属性称为字节数组的原因——Redis不是用这个数组来保存字符，而是用它来保存一系列二进制数据。
SDS使用len属性的值而不是空字符来判断字符串是否结束。

兼容部分C字符串函数

虽然SDS的API都是二进制安全的，但是它们一样遵循C字符串以空字符结尾的惯例，这都是为了让SDS能够共用C字符串函数。