Redis5 设计与源码分析 阅读笔记 02

第4章 压缩列表

  ziplist本质为一个字节数组，redis为了节约内存而设计的一种线性数据结构，可以包含多个元素，每个元素可以是一个字节数组或一个整数。

  有序集合Zset或者散列表 的元素个数比较少，且元素都是短字符串，redis便使用压缩列表作为其底层存储结构，列表使用快速链表quicklist结构存储，这个就是双向链表和压缩列表的组合。

下面是插入方法

插入元素步骤

1.对插入元素内容进行编码

   编码先尝试将数据内容解析为整数，如果解析成功，按照压缩列表整数类型编码存储；如果解析失败，按照压缩列表字节数组类型编码存储。

2.重新分配空间

     添加元素entryNew，元素长度1024；entryX + 1 元素的previous_entry_length字段需要占5个字节，即压缩列表的长度不仅增加了1024个字节，还要加上entryX + 1元素扩展的4个字节

3.数据复制

   重新分配空间之后，需要将位置p后的元素移动到指定位置，把新元素插入到位置P

 

删除元素步骤

1.计算待删除元素的总长度

2.数据复制

3.重新分配空间

 

第5章 字典

  hash结构的特征

 1.可以存储海量数据，键值对为映射关系，获取或者插入数据复杂度为o(1)

 2.键值对 键的类型可以是字符串，整型，浮点型等，且键是唯一的

 3.键值对中 值的类型可为String,Hash ,List ， Set, ZSet

增加元素到散列表hash

1.字典中已存在键，就返回NULL，否则添加键至Hash表中，并返回新加的hash节点

2.给返回的新节点设置值，更新其val字段

 

字典扩容

1.申请一块新内存，初次申请默认容量大小为4个dictEntry；非初次申请，申请内存大小为当前hash表容量的一倍

2.把新申请的内存地址赋值给ht[1], 并把字典的rehashidx 由 -1 改成0, 表示之后需要进行rehash操作

 

rehash

1.计算ht[0]每个键的hash值和索引值，依次添加到新的Hash表ht[1], 并且删除老Hash表中的键值对

2.rehash 操作后，清空ht[0], 把ht[1] 和ht[0] 对调， 然后把字典中rehashidx的字段标识改为-1

渐进式rehash

1.依次插入，删除，查找，修改前，都先判断当前字典rehash操作是否在进行中，进行中则调用dictRehashStep 函数进行rehash。除这些操作之外，服务空闲时，也调用incrementallyRehash函数进行批量rehash操作。 历经N次rehash后，整个ht[0]的数据都会迁移到ht[1], 这样就拆分成上百万，千万，亿次操作中，所以时间可以忽略不计。

 

第6章  整数集合

  当Redis的集合类型元素都是整数并且都在64位有符号整数范围之内时，使用intset存储

  可以存储int16_t, int32_t, int64_t 类型的整型数据，并且可以保证集合中的数据不重复

  数据查询： intset是从小到大有序排列的，通过防御性判断之后使用二分法进行元素的查找

6.2.2 元素添加

  1.判断插入值需要什么编码格式

  2.调用intsetSearch函数进行查重，即插入的值是否在当前集合中，如果找到了就不能再次插入，直接返回。

  3.调用intsetResize 扩充当前的intset，即给新插入的值申请好存储空间

  4 插入新值，并且把intset长度length+1