《Redis设计和实现》读书笔记1-简单动态字符串

 临近过年,我离开了实习了4个多月的扇贝。临走前,导师赠送给我一本《Redis设计和实现》,于是心血来潮,想读一读这本书,然后仿照书中介绍的原理实现一个小型的数据库。这是redis系列的第一篇博文,希望我可以坚持下去,不要虎头蛇尾。

简单动态字符串

 我们都知道Redis是由纯c代码编写而成的,而c语言中的原生字符串有很多的缺陷,不利于大型工程的使用。于是Redis的作者便自己实现一套字符串数据结构,就是sds.h/sdshdr结构。

SDS的定义

struct sdshdr {
  // 记录sdshdr中数组已经使用的数量
  int len;
  // 记录sdshdr中数组未使用的数量
  int free;
  char buf[];
};

sdshdr的定义如代码所示,其中buf属性为一个char类型的数组,数组的前五个字节分别保存着’R’,’e’,’d’,’i’,’s’五个字符,最后一个字符则保存则空字符串’\0’。之所以在数组尾部保存空字符,是为了可以使用一些c语言的字符串函数库中的函数。

SDS与c字符串的区别

常数时间内获得字符串长度

 我们都知道,在c中,字符串就是一个末尾有一个’\0’的一维数组,它并不记录本身的长度。所以,每次想要获取其长度时,都需要遍历整个数组,时间复杂度就为O(n);而SDS因为本身就有len这个字段,并且在SDS被修改时,会自动改变len字段,所以获得字符串长度的时间复杂度为O(1).

杜绝缓冲区溢出

 因为c的字符串没有任何安全保证,当我们使用strcat函数来拼接字符串时,如果目标字符串没有被分配足够空间的话,就会造成缓冲区溢出。而在SDS中,当然是每次修改都会进行缓冲区溢出检测,所以不会出现类似问题。

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

 这一条应该是使用SDS最大的优势所在啦。因为c语言中的字符串都是无法修改的,所以每次拼接或者裁剪字符串都会导致新的字符串数据结构的生成,从而需要新的内存分配或者释放部分内存。由于内存分配很消耗时间,所以使用c语言的字符串会导致数据库性能低下。
 而SDS会通过空间预分配和惰性空间释放来减少内存分配或者释放的次数。
 内存预分配是指每次需要对SDS进行空间扩展时,程序不仅分配SDS所必须要的空间,还会额外分配一些空间,将其大小赋值给’free’属性。如果需要分配的大小为n,额外分配的空间为e,总共分配空间为t,那么(默认单位为字节)

  e = n < 1MB ? n:1MB
  t = n < 1MB ? n + n + 1 ? n + 1MB + 1

 这样的话,下次再进行字符串拼接时,额外的空间就会被使用上,从而避免额外的一次内存分配。
 而惰性内存回收则是指裁剪字符串时,释放出来的额外空间并不会立刻被回收,而是继续保存,只是修改len和’free’属性,等到字符串再次被修改时使用。

二进制安全

 由于c语言字符串以’\0’来判断字符串的结束,所以无法保存一些图片,音频,视频这些可能写入’\0’的二进制数据。

后续

 书里的内容很简单,希望自己也可以实现一个简单的string类型吧,不过不清楚java中String对象的实现欧,以后可以了解一下。

关于图片和转载

知识共享许可协议
本作品采用知识共享署名 4.0 国际许可协议进行许可。 转载时请注明原文链接,图片在使用时请保留图片中的全部内容,可适当缩放并在引用处附上图片所在的文章链接。

关于评论和留言

如果对本文 《Redis设计和实现》读书笔记1-简单动态字符串 的内容有疑问,请在下面的评论系统中留言,谢谢。

原文链接:《Redis设计和实现》读书笔记1-简单动态字符串

Follow: Ztelur · GitHub

历小冰

君子不器