阿里云能做网站么,wap文字游戏搭建教程,深圳网站建设黄浦网络-技术差,怎么做虚拟网站定义
众所周知#xff0c;Redis是由C语言写的。 对于字符串类型的数据存储#xff0c;Redis并没有直接使用C语言中的字符串。 而是自己构建了一个结构体#xff0c;叫做“简单动态字符串”#xff0c;简称SDS#xff0c;比C语言中的字符串更加灵活。
SDS的结构体是这样的…定义
众所周知Redis是由C语言写的。 对于字符串类型的数据存储Redis并没有直接使用C语言中的字符串。 而是自己构建了一个结构体叫做“简单动态字符串”简称SDS比C语言中的字符串更加灵活。
SDS的结构体是这样的
struct{int len; // 数组中已使用的字节的数量即真实的内容长度 int free; // 数组中未使用的字节的数量即还可以继续存储的内容的长度 char buff[]; // 字节数组用来保存字符串
};在C语言中总是使用长度是N1的字符数组来保存长度为N的字符串并且字符数组的最后一个是’\0’结束符在SDS中一次申请的字符串的长度比真实的长所以才会有free这个属性
SDS与C语言字符串相比优点是
O(1)复杂度获取字符串长度防止了内存溢出减少内存分配的次数二进制安全
获取字符串长度
对于C字符串来说获取一个字符串的真实长度需要遍历字符串这就是O(N)的时间复杂度。 而在SDS中用一个len属性保存字符串的真实长度每次对字符串的修改都会维护这个len属性 因此对于SDS来说获取字符串的真实长度的时间复杂度是O(1)这确保了获取字符串长度的操作不会成为Redis字符串的性能瓶颈
内存溢出问题
在C字符串中如果要对字符串进行修改操作如果忘记了给字符串重新分配足够的空间就会导致内存溢出问题。在C语言中并没有内存溢出相关的检查机制因此可能会导致不可预测的问题产生。
通过SDS的API来操作字符串时会先检查SDS的空间是否满足修改的要求如果不满足的话会自动将SDS的空间扩展至要求的大小然后执行字符串操作所以使用SDS来操作字符串不用担心内存溢出问题。
减少内存分配的次数
对于C语言字符串因为总是有一个长度为N1的字符数组来保存一个长度为N的字符串。 所以如果对C字符串进行操作
如果进行字符串的长度增长的操作比如追加字符append那么在执行这个操作前需要先为字符串分配新的内存空间然后才能执行操作。如果忘记了重新分配内存会导致内存溢出问题。如果进行字符串长度的减少操作比如删除某个字符那么在执行这个操作之后需要释放掉不再使用的内存空间。如果忘记了释放内存会导致内存泄漏问题。
而对于SDS来说不存在这些问题通过两个机制来解决以上问题
空间预分配惰性空间释放
1. 空间预分配
空间预分配机制用来优化SDS字符串的增长操作。 我们认为初始化赋值和拼接操作都是对于SDS的扩容操作。 当SDS来扩容一个字符串时系统不仅会为SDS分配所需的内存空间大小还会分配额外的未使用空间即系统分配给SDS的空间大小比真实的字符串长度要大。 至于额外的空间有多大有以下规则
当扩容后的SDS的长度小于1MB那么程序分配的额外空间就是len的大小即与真实的字符串的空间大小相同。例如扩容后SDS的len的长度是20那么额外的空间也是20总共的SDS的空间是40字节。如果扩容后的SDS的长度大于等于1MB那么程序会分配1MB的额外空间。
通过空间预分配策略可以减少字符串增长操作的内存分配次数。 当进行字符串增长操作时会先检查free的空间大小是否够增加的长度如果够那么直接在真实的数组上操作无需再进行内存分配操作并维护free和len的值。 如果不够那么就会进行扩容操作扩容机制上面说过了。
2. 惰性空间释放
惰性空间释放用来优化字符串的缩短操作。 当SDS缩短一个字符串时还是直接在原始的数组上操作并维护len和free的值。 缩短完成后程序并不会立即回收释放后的内存而是使用free属性记录下来方便下次的字符串长度增加时使用。
二进制安全
C字符串中的字符必须符号某种编码例如当编码格式是ASCII时除了末尾的空字符’\0’外字符串内容中不可以出现空字符否则程序在读取字符串时会误以为这是字符串的结尾。 这样的限制使得C字符串只能保存文本数据而不能保存图片、音频等二进制数据。 而SDS会以二进制的方式来处理存放到buff数组中的数据程序不会对其中的数据进行限制、过滤等额外操作 这就是我们称SDS是字节数组的原因——Redis不是用buff数组来保存字符而是保存一系列的二进制数据
SDS不是使用空字符’\0’来判断字符串的结尾而是使用len属性来判断字符串是否结尾 如Redis\0StringC字符串的函数会把’\0’当做结束符来处理而忽略到后面的String。而SDS的buf字节数组不是在保存字符而是一系列二进制数组SDS API都会以二进制的方式来处理buf数组里的数据使用len属性的值而不是空字符来判断字符串是否结束。
参考文章
Redis数据结构——简单动态字符串SDS - 随心所于 - 博客园 《Redis设计与实现》
