Redis核心数据结构之SDS(二)

SDS与C字符串的区别

杜绝缓冲区溢出

除了获取字符串长度的复杂度高之外，C字符串不记录自身长度带来的另一个问题是
容易造成缓冲区溢出(buffer overflow).例如/strcat函数可以将src字符串
中的内容拼接到dest字符串的末尾:

char *strcat(char *dest,const char *src);
1

因为C字符串不记录自身的长度，所以strcat假定用户在执行这个函数时，已经为dest
分配了足够多的内存，可以容纳src字符串中的所有内容，而一旦这个假定不成立时，
就会产生缓冲区溢出。
与C字符串不同，SDS的空间分配策略完全杜绝了发生缓冲区溢出的可能性:当SDS API
需要对SDS进行修改时，API会先检查SDS的空间是否满足所需的要求，如果不满足的
话，API会自动将SDS的空间扩展至执行修改所需的大小，然后才执行实际的修改操作，
所以使用SDS既不需要手动修改SDS的空间大小，也不会出现前面所说的缓冲区溢出问题

例子

例如，假设程序里有两个在内存中紧邻着的C字符串s1和s2,
其中s1保存了字符串"Redis"，而s2则保存了字符串"MongoDB"，如图所示

如果一个程序决定通过执行:

strcat(s1, " Cluster");
1

将S1的内容修改为"Redis Cluster"，但粗心地却忘了在执行strcat之前为s1
分配足够的空间，那么在strcat函数执行之后，S1的数据将溢出到了S2所在
的空间中，导致S2保存的内容被意外地修改，如图所示

举个例子，SDS的API里面也有一个用于执行拼接操作的sdscat函数，它可以
将一个C字符串拼接到给定SDS所保存的字符串的后面，但是在执行拼接操作之前，
sdscat会先检查给定SDS的空间是否足够，如果不够的话，sdscat就会先扩展SDS的
空间，然后才执行拼接操作，例如执行，sdscat(s, " Cluster"),SDS值如图所示，
那么sdscat将在执行拼接操作之前检查s的长度是否足够，在发现s目前的空间不足以
拼接" Cluster"之后，sdscat就会先扩展s的空间，然后再执行拼接" Cluster"的操作，

拼接之后的SDS结构如图.
注意,sdscat不仅对这个SDS进行了拼接操作，它还为SDS分配了13字节的未使用空间，
并且拼接之后的字符串也正好是13字节长，这种现象既不是bug也不是巧合,它和SDS的
空间分配策略有关

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

因为C字符串并不记录自身的长度，所以对于一个包含了N个字符的C字符串来说，这个C字符串的底层实现总是一个N+1个字符长的数组(额外的一个字符空间用于保存空字符)。因为C字符串的长度和底层数组的长度之间存在着这种关联性，所以每次增长或者缩短一个C字符串，程序都总要对保存这个C字符串的数组进行一次内存重分配操作:

• 1.如果程序执行的是增长字符串的操作，比如拼接操作(append)，那么再执行这个操作之前，程序需要先通过内存重分配来扩展底层数组的空间大小——如果忘了这一步就会产生缓冲区溢出
• 2.如果程序执行的是缩短字符串的操作，比如截断操作(trim)，那么在执行这个操作之后,程序需要通过内存重分配来释放字符串不再使用的那部分空间——如果忘了这一步就会产生内存泄漏

例子

• 例如，如果我们持有一个值为"Redis"的C字符串s,那么为了将s的值改为"Redis Cluster",在执行:

strcat(s," Cluster");
1

之前，我们需要先使用内存重分配操作，扩展s的空间，之后，
如果我们又打算将s的值从"Redis Cluster"改为"Redis Cluster Tutorial"，那么再执行:

strcat(s, " Tutorial");
1

之前，我们需要再次使用内存重分配扩展s的空间，注入此类。
因为内存重分配设计复杂的算法，并且可能需要执行系统调用，所以它通常是一个比较耗时的操作:

• 1.在一般程序中，如果修改字符串长度的情况不太常出现，那么每次修改都执行一次内存重分配也是可以接受的
• 2.但是Redis作为数据库，经常被用于速度要求严苛、数据被频繁修改的场合，如果每次修改字符串的长度都需要执行一次内存重分配的话，那么光是执行内存重分配的时间就会占去修改字符串所用时间的一大部分，如果这种修改频繁地发生的话，可能还会对性能造成影响

空间预分配和惰性空间释放

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

空间预分配

空间预分配用于优化SDS的字符串增长操作:当SDS的API对一个SDS进行修改，并且需要对SDS进行空间扩展的时候，程序不仅会为SDS分配修改所必须要的空间，还会为SDS分配额外的未使用空间。其中，额外分配的未使用空间数量由以下公式决定:

• 1.如果对SDS进行修改之后，SDS的长度(也即是len属性的长度)将小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDSlen属性的值将和free属性的值相同。
• 2.如果对SDS进行修改之后，SDS的长度将大于等于1MB,那么程序会分配1MB的未使用空间。

通过空间预分配策略，Redis可以减少连续执行字符串增长操作所需的内存重分配次数。

例子

• 例如，如果进行修改之后，SDS的len将变成13字节，那么程序也会分配13字节的未使用空间，SDS的buf数组的实际长度将变成13+13+1=27字节(额外的一字节用于保存空字符)

• 例如，入宫进行修改之后，SDS的len将变成30MB，那么程序会分配1MB的未使用空间，SDS的buf数组的实际长度将为30MB+1MB+1byte

• 例如，对于如图所示的SDS值s来说，如果执行sdscat(s, " Cluster"),
  那么sdscat将执行一次内存重分配操作，将SDS的长度修改为13字节，
  并将SDS的未使用空间同样修改为13字节
  

• 如果这时，我们再对s执行:sdscat(s, " Tutorial");那么这次sdscat将不需要执行内存重分配，因为未使用空间里面的13字节足以保存9字节的" Tutorial"，执行sdscat之后的SDS，如下图所示
  

• 在扩展SDS空间之前，SDS API会先检查未使用空间是否足够，如果足够的话，API就会直接使用未使用空间，而无须执行内存重分配。
  通过这种预分配策略，SDS将连续增长N次字符串所需的内存重分配次数从必定N次降低为最多N次
  

惰性空间释放

惰性空间释放用于优化SDS的字符串缩短操作:当SDS的API需要缩短SDS保存的字符串时，程序并不立即使用内存重分配来回收缩短后多出来的字节，而是使用free属性将这些字节的数量记录起来，并等待将来使用

例子

• 例如，sdstrim函数接受一个SDS和一个C字符串作为参数，从SDS左右两端分别移除所有在C字符串中出现过的字符.比如，对如图所示的SDS值s来说,执行

sdstrim(s,"XY")//移除SDS字符串中的所有"X"和"Y"
1

会将SDS修改成如下图

• 注意执行sdstrim之后的SDS并没有释放多出来的8字节空间，而是将这些8字节空间作为未使用空间保留在了SDS里面，如果将来要对SDS进行增长操作的话，这些未使用空间就可能派上用场。
  
• 例如，现在对s执行sdscat(s，" Redis");那么完成这次sdscat操作将不需要执行内存重分配:因为SDS里面预留的8字节空间已经足以拼接6个字节常的" Redis".通过惰性空间释放策略，SDS避免了缩短字符串所需的内存重分配操作，并为将来可能有的增长操作提供了优化，与此同时，SDS也提供了相应的API，让我们可以在有需要时真正地释放SDS的未使用空间，所以不用担心惰性空间释放策略会造成内存浪费