网站建设哪家稳妥正规的教育培训机构有哪些
这是我2021年的第4篇原创文章，原汁原味的技术之路尽在Jerrycodes
底层数据结构
SDS底层构建
SDS优化了什么
空间预分配
惰性空间释放
常数级获取字符串长度
杜绝缓存区溢出
二进制安全
总结
尾语
Redis中有五种数据类型：
String: 字符串
Hash: 散列
List: 列表
Set: 集合
Sorted Set: 有序集合
字符串类型 是 Redis 最基础的数据结构。其值实际可以是 字符串（简单 和 复杂 的字符串，例如 JSON、XML）、数字（整数、浮点数），甚至是 二进制（图片、音频、视频），但是值最大不能超过 512MB
底层数据结构
它不是普通字符串，而是 SDS字符串，这个 SDS的意思是「Simple Dynamic String」。
Redis是由C语言编写的，C语言里面的字符串是以0x\0结尾，通常我们就说以 NULL 结尾。它不包含长度信息，当我们需要获取字符串长度时，需要调用 strlen(s) 来获取长度，它的时间复杂度是O(n)，如果一个字符串太长，这个函数就太浪费 CPU了。
所以如果线上有个数据需要知道key对应的value的值的长度，那这个请求的处理速度可是一只行走的乌龟。所以对C语言的做法重新设计。
SDS底层构建
来看一下SDS的结构
/** 类型别名，用于指向 sdshdr 的 buf 属性*/
typedef char *sds;struct sdshdr { // buf 中已占用空间的长度int len;// buf 中剩余可用空间的长度int free;// 数据空间 实际上不占用内存空间sizeof(struct sdshdr) = 8char buf[];
};
如图展示了一个SDS的示例：
free属性的值为0，表示这个SDS没有任何剩余的可使用字节数。
len为5，表示这个SDS保存了一个长度为5的字符串
buf属性是一个char类型的数组，数组的前五个字节分别保存了'R'、'e'、'd'、'i'、's'五个字符，而最后一个字节则保存空字符'\0'，代表字符串结束
SDS优化了什么
一句话，SDS就是为了解决C语言中字符串的弊端。
C语言中字符串存在什么问题？
缓存区溢出
字符长度计算复杂
接下来介绍以下SDS是如何解决这些问题并优化的
空间预分配
空间预分配用于优化SDS的字符串增长操作。
我们都知道当SDS除了分配给本身所需的字节空间，还会再额外分配一些备用空间。备用空间怎么决定，有以下两种方式：
1.（len属性<1MB) 总长度len<1MB: 总空间为2*len+1
如果对SDS进行修改后，SDS的长度（即len属性的值）小于1MB，那么程序分配和len属性同样大小的未使用空间，这时SDS的free属性的值将于len属性的值相同。
比如经过修改之后，SDS的len将变为13个字节，那么程序也会分配13个字节的备用空间，外加一个字节用于存储空字符串标识字符串结束，所以SDS的buf数组实际长度为13+13+1=27字节
2.（len属性>1MB) 修改之后总长度len>=1MB: 总空间为len+1MB+1
如果对SDS进行修改之后，SDS的长度大于等于1MB，那么程序会多分配1MB的未使用时间。
比如经修改后，SDS的len为30MB，那么程序会多分配1MB的未使用空间，SDS的buf数组的实际长度为30MB+10MB+1字节
惰性空间释放
惰性空间用于优化SDS字符串的缩短操作。
当SDS的API需要缩短SDS保存的字符串时,程序并不立即使用内存重分配来回收缩短后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。
例如操作前字符串s1=”aabbcc“等价于
SDS struct{
free=0,
len=6，
buf="aabbcc"。
}
执行截断操作，只保留前三位，那么根据SDS的特性，操作后s2="aab",等价于
SDS struct{
free=3,
len=3，
buf="aab"。
}
SDS并没有释放多出来的3字节空间，而是将这3字节空间作为未使用的空间存在了SDS中，如果以后还有扩充操作的话可以派上用场。
常数级获取字符串长度
不同于C语言中strlen获取字符串长度为O（N）的复杂度，SDS中直接读取len的值，当然len属性是在字符串更新的时候也随之更新，复杂度为O（1），相当于是一个空间换时间的操作了。
杜绝缓存区溢出
我们知道在C语言中不记录自身长度带来的一个后果就是容易造成缓存溢出。如使用strcat函数进行拼接时，若原有字符串的空间不足时，会发生截断现象。
如str1 = "aabbcc",str2 ="ddeeff"; 如果str1中至多只能存放10个字符，那么经过strcat(str1,str2)函数后的输出结果为"aabbccddee",这就是缓存区溢出现象。
而SDS对象恰好可以解决这个问题的存在。如果buf的长度小于新字符串的长度，则声明一个新的数组存放新字符串，反之，无需再声明一个新的数组来容纳新字符串，节省开支。
二进制安全
二进制安全是指，在传输数据时，保证二进制数据的信息安全，也就是不被篡改、破译等，如果被攻击，能够及时检测出来。
c中的strlen函数依赖于特殊的字符 '\0' 来判断字符串是否结束，所以对于字符串str = "1234\0123"来说，strlen(str)=4，但实际上str的长度为9.
使用SDS就不需要依赖控制符，而是用len来指定存储数据的大小，所有的SDS API都会以处理二进制的方式来处理SDS的buf的数据。程序不会对buf的数据做任何限制、过滤或假设，数据写入的时候是什么，读取的时候依然不变。
所以使用SDS，可以放心的存储二进制数据
总结
| C字符串 | SDS |
|---|---|
| 获取字符串长度复杂度为O（N） | 获取字符串长度复杂度为O（1） |
| 会导致缓存区溢出 | 不会导致缓存区溢出 |
| 修改N次字符串必定导致N次字符串的新建 | 修改N次字符串最多导致N次字符串的新建 |
| 二进制下不安全 | 二进制安全 |
尾语
Jerry哥建立了一个优质的技术微信群，主要用于2022秋招/实习交流群，正在准备2021春招的人也可以加入。群内嘉宾有前美团技术人索隆，微软工程师C哥和已经成功上岸的J哥。欢迎大家扫码加我，备注学校+姓名+岗位，我会拉大家进群。
码到这里，何不来个在看？