Redis设计与实现-1.数据结构(1)

凌风郎少 2020-04-23

简单动态字符串SDS

SDS属性

  • free:表示SDS分配空间中没有使用的数量
  • len:表示SDS保存的字符串的长度
  • buf:char类型的数组,存储具体字符,最后一个字节保存了空字符‘\0‘。

SDS的字符串以空字符结尾,保存空字符的1字节空间空间不计算在SDS的len属性中。在分配字符串SDS空间的时候,会把1字节的空间算进去。

SDS特性

  1.获取时间复杂度O(1)

SDS字符串中len保存了字符串的长度,所以获取SDS的时间复杂度是O(1)。如果不知道长度,那么获取字符串就要找到字符串的结尾,来获取字符串数据。

  2.杜绝缓冲区溢出

SDS在修改前,先会判断字符串空间是否满足修改所需要的要求,如果不满足的话,会先将空间拓展至执行修改所需要的大小,然后进行修改操作。

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

1)空间预分配:优化SDS字符串增长操作,不光对SDS修改内容进行内存分配,也会给SDS额外的内存空间。

  • 如果SDS修改后,SDS长度将小于1MB,那么程序会分配和len属性同样大小的未使用空间,这时候SDS的len属性和free属性的值相同。SDS修改后的空间大小为 len+free+1。(free=len)
  • 如果SDS修改之后,SDS长度大于等于1MB,那么程序会直接分配1MB的未使用空间。举例当SDS修改后的len为20MB,那么程序分配后的长度为 20MB+1MB+1byte。

通过空间预分配策略,Redis可以减少连续执行字符串增长操作所需要的内存重分配次数。

2)惰性空间释放:优化SDS字符串缩短操作,当SDS需要缩短SDS保存的字符串时候,程序并不会立即使用内存重新分配来回收缩短后的字节,而是使用free属性将这些字节数量记录下来。与此同时,SDS提供了相应API,让我们在需要的时候,真正的释放未使用空间,所以不需要担心惰性空间释放策略会造成内存浪费。

  4.二进制安全

SDS的API都是以处理二进制的方式来处理SDS存放在buf数组里面的数据,不会对数据进行限制和过滤。二进制安全的SDS,使Redis不仅可以保存文本数据,还可以保存任意二进制数据。

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

链表

每个链表节点都是一个listNode结构,多个ListNode节点通过前后指针组成了双端链表。listNode结构如下:

  • listNode prev:前指针
  • listNode next:后指针
  • value:节点的值

字典

字典是一种保存键值对的抽象数据结构。Redis的字典使用哈希表作为底层实现,一个哈希表里面有多个哈希表节点,而每个哈希表节点就保存了字段中的一个键值对。

哈希表

Redis设计与实现-1.数据结构(1)

  • dictht代表一个字典,
  • table属性是一个数组,
  • size为属性记录了哈希表大小(table数组大小),
  • used记录了目前已有节点的数量,s
  • izemask属性的值总是为size-1。

sizemask和哈希值一起决定一个键应该被放到table数组的那个索引上面。

哈希表节点

Redis设计与实现-1.数据结构(1)

  • key属性保存着键值对中的键
  • v属性保存这键值对中的值,值可以是一个指针,或者是一个uint64_t的整数,或者是一个int64_t的整数。
  • next属性是指向另一个哈希表节点的指针,这个指针可以将多个哈希值相同的简直对连接在一起,以此来解决键冲突的问题。

字典

Redis设计与实现-1.数据结构(1) 

  • type属性是一个指向dictType结构的指针
  • privdata属性保存了需要传给那些类型特定函数的可选参数
  • ht属性是一个包含两个项的数组,数组的每个项都是一个dictht哈希表,一般只使用ht[0],ht[1]是在对ht[0]进行rehash的时候使用。
  • rehashidx属性记录了rehash目前的进度,没有进行rehash的时候值为-1。

解决键冲突

Redis的哈希表使用链地址法解决键冲突。

Rehash

随着操作不断执行,哈希表保存的键值对会慢慢增多或者减少,为了让哈希表的负载因子维持在一个合理的范围内,当哈希表的键值对数量太多或者太少时,程序会对哈希表的大小进行相应的扩展和收缩。扩展和收缩哈希表的工作可以通过rehash操作完成。步骤如下:

  1. 为字典ht[1]分配空间,分配空间大小取决于扩展操作还是收缩操作。扩展操作ht[1]大小为第一个大于等于ht[0].userd*2的2的n次幂。收缩操作ht[1]的大小为第一个大于等于ht[0].used的2的n次幂。
  2. 将保存在ht[0]中的所有键值对rehash到ht[1]上。rehash指的是重新计算键的哈希值和索引值,然后将键值对放在ht[1]哈希表的指定位置上。
  3. 当ht[0]包含的所有值都迁移之后,释放ht[0],将ht[1]设置为ht[0],并在ht[1]新创建一个空白哈希表,为下一次rehash作准备。

渐进式rehash

 rehash动作不是一次性、集中式地完成,而是分多次、渐进式地完成的。具体过程如下:

  1. 为ht[1]分配空间,让字典同时持有ht[0]和ht[1]两个哈希表。
  2. 在字典中维持一个索引计数器变量rehashidx,并将他的值设置为0,表示rehash工作正式开始。
  3. 在rehash期间,每次对字典进行添加、删除、查询或者更新操作时,程序除了执行指定操作外,还会顺带将ht[0]哈希表在rehashidx索引上的所有键值对rehash到ht[1],当rehash工作完成后,程序会将rehashidx属性的值增1。
  4. 随着不断执行操作,在某一个时间,ht[0]的所有键值对都会被rehash到ht[1],这是程序将rehashidx属性的值设为-1,表示rehash操作完成。

渐进式rehash执行期间的哈希表操作

字典里面查询一个键,先从ht[0]里面进行查询,如果没有,就会继续到ht[1]进行查询。

字典里面添加一个键值对一律会保存到ht[1]里面,而ht[0]则不再进行任何添加操作。保证了ht[0]包含的键值对数量会只减不增,并随着rehash操作的执行而最终变成空表。

相关推荐