风向晚。maplefan

引言

为何redis中大量使用的是SDS，而不是传统的C语言字符串表示法存储字符串？到底什么是SDS？为什么要使用SDS？其相对于传统的C语言字符串有何优点？本文会针对以上几点做一个详细的分析，帮助大家以及自己更好的理解redis中的简单动态字符串。

介绍SDS之前先简单介绍一下C语言中的传统字符串表示法

C语言字符串（C字符串）

始终以空字符结尾的字符数组，c语言为其封装了大量的函数库操作API

C字符串特点

• 字符数组存储
• 以空字符结尾，除了末尾之外，字符串里面不可以包含空字符
• 由于采用字符数组，导致所存储的字符必须符合某种编码（如ASCII）
• 获取C字符串长度必须遍历整个字符串，并对遇到的每个字符计数，直到遇到空字符为止，时间复杂度为O(N)

那么基于以上特点，C字符串是否能够满足我们Redis高效，安全的需求呢？显然是不能的，单是一个获取字符串长度就需要遍历整个字符串数组了，必须重新定义一种新的结构以支持Redis中对于频繁高效操作字符串的要求。

SDS 简单动态字符串

基于以上C字符串的缺陷，Redis自己构建了一种名为简单动态字符串的抽象类型，简称SDS。

SDS结构

struct sdshdr {

    // buf数组已经使用字节数量，即SDS字符串长度
    int len;

    // 记录buf数组中未使用字节的数量
    int free;

    // 字节数组，用于保存二进制数据
    char buf[];
}

可以看出，SDS定义的结构中，增加了一个int类型的len属性用于记录SDS所保存的字符串长度，一个free属性用于记录数组中未使用的字节数量。

SDS特点

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

Redis中利用SDS字符串的len属性可以直接获取到所保存的字符串的长
度，直接将获取字符串长度所需的复杂度从C字符串的O(N)降低到了O(1)。

• 减少修改字符串时导致的内存重新分配次数

基于前面介绍的C字符串的特性，我们知道对于一个包含了N个字符的C字符串来说，其底层实现总是N+1个字符长的数组（额外一个空字符结尾），那么如果这个时候需要对字符串进行修改，程序就需要提前对这个C字符串数组进行一次内存重分配（可能是扩展或者释放），而内存重分配就意味着是一个耗时的操作。

Redis巧妙的使用了SDS避免了C字符串的缺陷，在SDS中，buf数组的长度不一定就是字符串的字符数量加一，buf数组里面可以包含未使用的字节，而这些未使用的字节由free属性记录。

SDS采用了空间预分配策略避免C字符串每一次修改时都需要进行内存重分配的耗时操作，将内存重分配从原来的每修改N次就分配N次降低到了修改N次最多分配N次。

字符串扩展：

首先检查SDS未使用空间即free属性是否够用，如果够用，则会直接使用未使用空间，而无须进行内存重分配。

空间预分配

所谓预分配就是额外多分配一部分空间给SDS，并不是仅仅只分配刚好够字符串扩展修改后的空间。

分配策略：

1. 若SDS修改后，其长度（len的属性）小于1MB，那么程序会分配和修改后的len属性同样大小的未使用空间
2. 若修改后，其长度大于1MB，那么程序只会分配固定1MB的未使用空间，不会再多分配了，考虑内存的成本因素

字符串缩短：

针对SDS字符串的缩短场景，SDS并不会立即释放多余出来的内存空间，而是将这部分内存空间记录再其free属性中，当SDS字符串进行扩展时，这部分未使用的内存空间就能直接用，而不需要进行内存重分配，这就是SDS的惰性空间释放。

• 杜绝缓冲区溢出

在C字符串的拼接操作过程中，例如某程序员操作S1拼接S2，由于程序员忘记了给需要拼接的字符串S1分配足够的内存空间（到底需要分配多少内存呢？哈哈，当然需要遍历S2的字符数组才能知道S2的长度是多少，因为C字符串不记录自身的长度），那么拼接的时候就会导致缓冲区溢出的可能性。

针对以上情况，SDS的空间分配策略可以完全杜绝这种情况，因为当SDS 的API对SDS进行修改时，API会首先检查SDS的未使用空间是否足够，不够的化会进行内存重分配以扩展空间至足够修改所需的大小，然后再执行实际的修改操作，这样就可以达到杜绝缓冲区溢出的可能。

• 让Redis保存更多类型的数据成为可能

由于C字符串中保存的字符必须符合某种编码格式（如ASCII），这就限制了C字符串只能保存文本数据，而不能保存箱视频，音频，压缩文件这种的二进制数据。

另一个限制是C字符串中间不能包含空字符，否则中间的空字符会被认为是整个字符串的结尾，而导致后面的部分字符被忽略掉。

SDS的API被设计成了二进制安全的，以处理二进制的方式来处理SDS中存放再buf数组中的数据，原样存取，这就是为什么在SDS的结构中采用的是字节数组，而不是C字符串中的字符数组。

这样的二进制安全的SDS，使得Redis不仅可以保存文本，还可以保存任意格式的二进制数据。

• 兼容部分C字符串API

由于C字符串本身具有大量操作API，SDS如果可以利用一部分C字符串的API那样就不用重复发明轮子了，所以Redis中的SDS遵循C字符串以空字符结尾的惯例，在SDS的API中，总会将SDS保存的数据末尾设置未空字符，在分配buf数组时也总会多分配一个字节来保存这个空字符，这样SDS就可以重用一部分C字符串库的API。

C字符串与SDS对比

总结

Redis中采用SDS替代C语言中传统字符串表示法，提升了获取字符串长度的效率，扩大了能够保存数据的类型范围，以及降低了每次修改字符串时候的内存重分配次数，甚至规避了在操作C字符串中可能出现的缓冲区内存溢出的可能性，从而为Redis中字符串操作的安全，高效提供了保障。

编译环境：VS2019 + Win10 + cmake-gui-3.8.0 + cef_binary_3.2623.1401.gb90a3be_windows32

最后一个兼容Windows XP的CEF（2623）的下载地址：https://pan.baidu.com/s/1UoWt8Ffs_YPBCmYlHbipLg

提取码:x7ym

1、解压 cef_binary_3.2623.1401.gb90a3be_windows32 后，目录如下:

2、下载cmake-gui

下载地址：https://pan.baidu.com/s/1KdOaZXWX9gy7yVKVbJdpgA

提取码:ptnu

下载好cmake-gui并安装好之后打开cmake-gui.exe，设置如下：

Where is the source code : cef_binary_3.2623.1401.gb90a3be_windows32解压后的路径

where to build the binaries : cef_binary_3.2623.1401.gb90a3be_windows32解压后的路径

Configure: 选择你电脑上装有的VS的编译器的版本，如果选择了电脑本地并没有的VS编译器版本，会遇到如下情况：

用cmake生成编译工程时候报这样的错误，原因是配置错误导致cmake找不到对应的编译器，于是通过File->Delete cache清理配置，重新通过Configure更换你电脑上装有的VS的编译器的版本即可。

当出现Configuring done的时候点击Generate按钮即可生成对应版本的VS sln解决方案，使用VS打开生成解决方案即可。

VS2015打开cef.sln然后直接编译即可生成libcef_dll_wrapper.lib文件了，如下图项目cefsimple项目和cefclient项目会失败，这个并不影响生成我需要的libcef_dll_wrapper.lib，我就不解决了。

在这里还有一个坑就是这个工具最多只支持到VS2017，由于我的电脑上装了VS2013和VS2019，于是我选择了VS2013的配置并成功编译出了libcef_dll_warpper.lib，但在导入CEF浏览器实际项目调用的时候报了如下错误：error LNK2038: 检测到“_MSC_VER”的不匹配项问题。

_MSC_VER这个相当于做了宏的检测  _MSC_VER 定义编译器的版本。下面是一些编译器版本的_MSC_VER值：
MS VC++ 14.0 _MSC_VER = 1900 vs2015
MS VC++ 12.0 _MSC_VER = 1800 vs2013的编译器他的平台是v120
MS VC++ 11.0 _MSC_VER = 1700 vs2012的编译器他的平台是v110
MS VC++ 10.0 _MSC_VER = 1600 Visual C++ 2010
MS VC++ 9.0 _MSC_VER = 1500 Visual C++ 2008
MS VC++ 8.0 _MSC_VER = 1400 Visual C++ 2005
MS VC++ 7.1 _MSC_VER = 1310
MS VC++ 7.0 _MSC_VER = 1300
MS VC++ 6.0 _MSC_VER = 1200
MS VC++ 5.0 _MSC_VER = 1100

error LNK2038: 检测到“_MSC_VER”的不匹配项: 值“1800”不匹配值“1700”(main.obj 中)
原因：由于你使用了vs2012，工作集选择了更高的1800也就是vs2013的，致使msvc不兼容！
方法：在项目（解决方案资源管理器或者属性管理器里都行）右键属性-配置属性-常规中，平台工具集选用为合适平台即可，比如上面的就是要选择成2012的 v11版本，注意光选了还没有用，还要应用。
注意一个工程里面会有几个解决方案的时候，需要给每个解决方案都更改一遍，最后重新编译即可。

最近在通过OpenHardWareMonitorLib来获得一些CPU和GPU的信息，采用了c++调用c#dll的方法，由于只能传递基本数据类型，所以动态数组考虑到使用String来传递回C++并进行字符串分割，在.net中string是需要用gcnew进行初始化，先来看看gcnew和普通的new的区别：

C++/CLI中使用gcnew关键字表示在托管堆上分配内存，并且为了与以前的指针区分，用^来替换* ，就语义上来说他们的区别大致如下:

1.     gcnew返回的是一个句柄(Handle)，而new返回的是实际的内存地址. 
2.     gcnew创建的对象由虚拟机托管，而new创建的对象必须自己来管理和释放.
暂时没有很深入的去理解这些区别。因为需要在c++的控制代码中对c#产生的String^变量进行写出，而默认的文件写出是string类型的，因此需要进行转换。查阅资料发现有人总结了一下较为简单的转换方式：

1：std::string转String^:std::string stdstr=””;
String^ str = marshal_as<String^>(stdstr);

2：String^转std::string:
String^ str= gcnew String();
std::string stdstr = marshal_as(str->ToString());

3：CString转Sting^:
CString cstr=””;
String^ str = marshal_as(cstr.GetBuffer());
cstr.ReleaseBuffer();

4：String^转CString:
String^ str;
CString cstr(str);