阅读 26

《Redis设计与实现》读书笔记(一)简单动态字符串与链表

  翻这本书已经不止一次了,但是总是学完就忘,借着这次部门组织兴趣小组再重新系统的学习一遍。但当我和同事讨论这本书学来有什么用的时候,大家都有点两眼一抹黑,我自问自己也有点迷茫。“是啊,我看过了,然后我也不知道这个有什么用“。所以我就google了一下”SDS的好处“。

  像我们平时用的都是从使用者的角度。比如:string、list、hash、set、sorted set。

  从内部实现的角度。比如:dict、sds、ziplist、quicklist、skiplist

  我恍然大悟,我明白了redis是如何用内部的数据结构去实现常用的数据结构。这样我就能明白这本书所表达的含义了。

  在讨论任何一个系统的内部实现的时候,我们都要先明确它的设计原则,这样我们才能更深刻地理解它为什么会进行如此设计的真正意图。在本文接下来的讨论中,我们主要关注以下几点:

  • 存储效率。压缩数据、减少内存碎片。
  • 快速响应时间。
  • 单线程。不在于CPU资源,而在于内存访问和网络IO。

一、简单动态字符串

Redis自己构建了一个数据结构 命名为 简单动态字符串(simple dynamic string,SDS)

struct sdshdr {
  //记录buf数组中已使用字节的数量 等于SDS所保存字符串的长度
  int len;
  //记录buf数组中未使用字节的数量
  int free;
  //字节数组,用户保存字符串
  char buf[];
}复制代码

SDS遵循C字符串以空字符串结尾的惯例,好处是可以直接重用一部分C字符串函数库里面的函数。但是C字符串不满足Redis对字符串在安全性、效率以及功能方面的要求。

  1. 常数复杂度获取字符串的长度

C字符串本身不记录自身的长度信息,获取长度信息时,需要遍历整个字符串进行计数,直到遇到字符串结尾的空字符串为止。操作的复杂度为O(N)。

而SDS中len属性中记录了SDS的长度,所以获取一个SDS的长度复杂度为O(1)。

   2.杜绝缓冲区溢出

C字符串本身不记录自身的长度,执行拼接字符串时,没有预先扩容,则可能会出现内存其他内容被意外修改

而SDSAPI需要对SDS进行修改时,API会先检查SDS的空间是否满足修改所需要的要求,如果不满足的话,API会自动将SDS的空间扩展至执行修改所需的大小,然后才执行实际的修改操作

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

内存重分配

(1)空间预分配

优化SDS的字符串增长操作。

基于修改后的长度是否大于1MB,小于则将free属性的值设置为len的值;大于则将free属性的值设为1MB。

基于以上策略,当连续增长N次字符串所需要的内存重分配次数从必定N次降低为最多N次。

(2)惰性空间释放

优化SDS的字符串缩减操作。

当SDS的API需要缩短SDS保存的字符时,程序并不立即使用内存重新分配来回收缩短出来后多出来的字节,而是使用free属性将这些字节的数量记录起来,并等待将来使用。

以空间换时间

  4.二进制安全

C字符串中的字符必须符合某种编码,并且除了字符串的末尾之外,字符里不能包含空字符,否则最先程序读入的空字符串将被误认为是字符串结尾,导致C字符串只能保存文本数据。

所以SDS的API都是二进制安全的,所有SDS API都会以二进制的方式来处理SDS存放在buf数组里的数据,程序不会对其中数据做任何限制、过滤、或者假设,数据在写入时啥样,读取就是啥样。

  5.兼容部分C字符串函数

二、链表

typedef struct listNode {
  //前置节点
  struct listNode *prev;
  //后置节点
  struct listNode *next;
}复制代码

参考链接:zhangtielei.com/posts/blog-… 

 


关注下面的标签,发现更多相似文章
评论