C语言中的字符串

在C语言里面使用长度为N+1的字符数组来表示长度为N的字符串，并且字符数组的最后一个元素总是空字符'\0'。

C字符串

为验证C字符串结构，以下demo打印了字节数组中的元素的ASCII码和字符堆栈，再通过ASCII码对照表，可以得知C字符串最后一个字节总为0，对应的就是'\0'。

打印字符数组元素

Redis中的字符串

      redis并不采用C语言中传统的字符表示方式，redis采用了一种叫SDS（简单动态字符串）的数据结构来标识字符串。

      每个SDS值由一个sdshdr结构表示，以下为sdshdr数据结构定义：

sdshdr结构

      SDS保持了C语言字符串以空字符结尾的惯例，保持空字符的1个字节空间是不记录在len属性中的，并且空字符空间分配、添加空字符操作都是SDS内部自动完成的。对使用SDS的用户来说都是透明的，并且正因为SDS保持了C语言字符串的这个特性，使得SDS可以直接使用C字符串函数库的部分函数。

      以下示例展示了一个分配了10字节空间的SDS对象，其中使用5个字节保存了字符串hello，  5个空格代表5个字节的未使用空间，额外一个字节空间保存空字符'\0'。

SDS示例

为什么redis选择SDS来表示字符串，而不使用C字符串呢？

主要有以下几点原因：

获取字符串长度的时间复杂度差异

      C字符串本身并不记录字符串长度，也就是每次获取字符串，都必须要遍历整个字符串，直到遇到字符串末尾的空字符为止，该操作的时间复杂度为O（n）。

      SDS结构本身通过len属性保存字符串长度，每次获取长度直接读取len属性值即可，该操作的时间复杂度为O（1）。

缓冲区溢出问题

      C字符串在使用时，假定用户已经为字符串分配了足够的内存空间，当所分配空间不足以容纳字符串内容，就会产生缓冲区溢出问题。

内存中紧邻的两个C字符串

      假设用户对s1进行修改（如strcat操作），在“hello”后拼接了“ world”，但在修改前未分配足够的内存空间，那就容易会导致修复后的s1的内容将s2的内容覆盖。

s2被意外修改

      SDS则可以避免这种缓冲区溢出的问题，SDS在对字符串内容修改前会先检查SDS的空间是否足够，如空间不满足修改后的内容存储，SDS会先对buf字符数组进行扩容，以确保有足够的空间，同时也避免了缓冲区溢出的问题，并且拓容机制是由SDS自动完成的，对用户而言是透明的。

字符串修改引起多次的内存重分配问题

      C语言中总是以N+1个字节来保存长度为N的字符串，也就意味着每次对字符进行修改（增长/缩短）都会引起内存分配操作。每次增长字符串都必须先对字节数组进行拓容，否则会引起缓冲区溢出问题，每次对字符缩短，需要释放不再使用的空间，否则会导致内存溢出。

      redis为了避免每次修改字符串每次都触发需要内存分配，SDS结构中通过len和free属性将字符串底层数组的长度和字符串长度的关系进行了解耦，并且引入了优化策略，以减少内存重分配开销。

      在buf数组的长度不一定就是字符数+1，数组中可以包含未使用字节。通过引入free属性来保存未使用空间，redis提供了两种优化策略：

1)空间预分配

      当对SDS进行修改，并且SDS需要进行拓容时，SDS不仅仅只是分配足够的空间保存字符，同时会额外分配未使用空间。

      当SDS修改后的len属性值小于1MB，那么程序会分配和len属性值同样大小的未使用空间，如SDS修改拓容后，len的值为10，那么程序也会为SDS分配10的未使用空间，也就是free也会是10，那么SDS的总占用空间为10+10+1=21字节。

      当SDS修改后的len属性值大于1MB，那么程序会分配1MB的未使用空间，如SDS修改拓容后，len的值为20MB，那么程序也会为SDS分配1MB的未使用空间，也就是free是1MB，那么SDS的总占用空间为20MB+1MB+1byte。

      通过空间分配策略，可以减少每次对SDS长度增长时内存重分配的开销。

2)惰性空间释放

      当对SDS进行修改，并且SDS的字符串长度需要缩短时，redis并不是立刻重新分配内存以来回收缩短后多出来的字节空间，而是先使用free属性将这些多出来的字节进行记录，以备后续使用。另外SDS提供了API以让用户可以在有需要的时候再真正的去释放未使用空间。

二进制安全

    C语言的字符串中的字符必须要符合某些编码(如ASCII)，并且不能包含空字符，否则字符未到末尾就会因为存在空字符而被认为结束了，因此C字符串只能保存文本，不能保存图片、影音等二进制数据。

      redis中SDS的buf数组不是用来专门保存字符的，而是用来保存一系列的二进制数据的。因为SDS中len属性的存在，所以并不需要通过空字符判定是否字符串结束，从而使SDS避免了C字符串的弊端并且可以安全的保存各种二进制数据。

SDS对C字符函数的部分兼容

      SDS除了是二进制安全外，还保留了C字符以空字符结尾的约定，从而使SDS->buf可以作为部分C字符函数的参数，实现了对这部分函数的复用。