Redis教程

redis的底层原理

本文主要是介绍redis的底层原理,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

1. String:

  C语言字符串的缺陷:在c语言中,对字符串操作时,char* 指针只是指向字符数组的起始位置,而字符数组的结尾位置就用\0表示,意思是指字符串的结束

  1. 获取长度需要 O(n)         (SDS 是O(1)解决的)

  2. 除了字符串的末尾之外,字符串里面不能有”\0“字符,不能保存像图片、音频、视频这样的二进制数据      (SDS除了最后末尾为\0,中间也可以有\0,因此是可以存储二进制的)

  3. C语言标准库中字符串的操作函数是很不安全的,会导致缓冲区溢出: 怎么理解呢?

    c语言的字符串是不会记录自身的缓冲区大小的,例如在执行strcat(dest,src)函数时假定程序员在执行这个函数时,假设已经为dest分配了足够多的内存,可以容纳被拼接的字符串中的所有内容,一旦这个假定不成立,就会发生缓冲区溢出。   (预分配机制解决的)

 

  redis通过SDS来表示String字符串:  

  Redis的字符串对象: 一般包含两各对象,第一个对象是redisObject, 第二个对象是存放地址的对象

    1. embstr:

    

    2. raw: 原生格式

    

 

     3. INT类型:

    

 

2. List:

  原本的数据结构为:双向链表

  redis的双向链表是在其基础上添加了 头节点、尾节点以及节点数。  缺点也很明显(空间不连续,无法很好利用CPU缓存,能很好利用CPU缓存的数据结构就是数组。因此需要压缩列表来搞定)

  ziplist:它被设计成一种内存紧凑型的数据结构,占用一块连续的内存空间,不仅可以利用CPU缓存,而且会针对不同长度的数据,进行相应的编码,这种方法可以有效节省开销。  

  压缩列表的缺陷:

    1. 不能保存过多的元素,否则查询效率降低

    2. 新增或修改某个元素时,压缩列表占用的内存空间需要重新分配,甚至可能引发连锁更新的问题。

    因此,Redis对象(List 对象,Hash对象,Zset对象)包含元素较少时,或者元素值不大情况才会使用压缩列表作为底层数据结构。

  ziplist有一大缺陷: 连锁更新

    一个Entry 分为三段  previous_entry_length (前面元素的长度)、 encoding(编码)、content(”内容“)  

    长度是可变的,如果前面的长度为254的话,那么用一个字节来表示,如果大于254就用5个字节来表示,这就有可能造成连锁更新。

  Redis针对压缩列表在设计上的不足,在后来的版本中,新增设计了两种数据结构: quicklist和listpack。这两种数据结构的设计目标,就是尽可能地保持压缩列表节省内存的优势,同时解决压缩列表的连锁更新的问题。

 

3. hash数据类型:

  随着数据逐步增多,触发了rehash操作,这个过程分为三步:

    1. 给哈希表2 分配空间,会比哈希表1 大两倍

    2. 将哈希表1的数据迁移到哈希表2

    3. 迁移完成后,哈希表1的空间会被释放,并把哈希表2设置为哈希表1,然后在哈希表2新创建一个空白的哈希表,为下次rehash做准备。

    

 

    第二步有问题,如果哈希表1的数据量非常大,那么在迁移至哈希表2的时候,因为会涉及到大量的数据拷贝,此时可能会对redis造成阻塞,无法服务其他请求。

   渐进式rehash

   为了避免rehash在数据迁移过程中,因拷贝数据的耗时,影响Redis性能的情况,所以Redis采用了渐进式rehash,也就是将数据的工作不再是一次性迁移完成,而是多次迁移。

   渐进式rehash步骤:

    1. 给哈希表2分配空间

    2. 在rehash进行期间,每次哈希表进行新增、删除、查找或者更新操作时,Redis除了会执行对应的操作之外,还会顺序将哈希表1中索引位置上的所有key-value迁移到哈希表2上。  

    随着处理客户端发起的哈希表请求数量越多,最终在某个时间点,会把哈希表1的所有key -value 迁移到哈希表2,从而完成rehash操作。

    在进行渐进式rehash的过程中,会有两个哈希表,所以在渐进式rehash进行期间,哈希表元素的删、查、更新都会在这两个哈希表进行。

    比如,查找一个key的值的话,先会在哈希表1里面进行查找,如果没找到,就会继续到哈希表2里面进行查找。

    

    在渐进式rehash进行期间,新增一个k-v时,会被保存到哈希表2里面,而哈希表1不再进行任何添加操作,这样保证了哈希表1的k-v只会减少,随着rehash操作完成,最终哈希表会变成空表。

    

    rehash触发条件:

    rehash的触发条件跟负载因子有关系。

    

 

     触发rehash操作的条件,主要有两个:

     1. 当负载因子大于等于1,并且Redis没有在执行bgsave命令或者 bgrewriteof命令,也就是没有执行RDB快照或者AOF重写的时候,就会进行rehash操作

     2. 当负载因子大于等于5时,此时冲突非常严重了,不管有没有在执行RDB快照或者AOF重写,都会强制进行rehahs操作。

 

整数集合:

    整数集合是set对象的底层实现之一。

    

 

     特点:1. 元素不重复

        2. 元素有序

     只支持升级,不支持降级

 

跳跃表:

  首先跳跃表是一个链表,链表最大的缺陷就是在查找元素的时候,需要顺序遍历,而跳跃表可以通过近似于二分查找的方式来解决这个问题。

  跳表是在链表基础上改进过来的,实现了一种多层的有序链表,这样的好处是能快速读定位数据。

 

Zset 对象是唯一要给同时使用了两个数据结构来实现的Redis对象,这两个数据结构一个是跳表,一个是哈希表。这样的好处是既能进行高效的范围查询,也能进行高效的单点查询:

  

 

   其中 dict是哈希表,zskiplist 是跳跃表。

  能支持范围查询,因为它的数据结构设计采用了跳表

  常数复杂度获取元素权重,这时因为它同时采用了哈希表进行索引。

 

  跳表的Entry元素: 这个node就是 一个元素对象,一个分数,一个level数组。

  这个node指的是

  

 

   跳表在创建节点的时候,随机生成每个节点的层数,并没有严格维持相邻两层的节点数量比例为2:1 的情况。

  具体做法是: 跳表在创建节点的时候,会生成范围[0,1]的一个随机数,如果这个随机数小于0.25,那么层数就增加一层,然后继续生成下一个随机数,直到随机数的结果大于0.25结束。   这样的做法,相当于每增加一层的概率不超过25%,层数越高,概率越低。

 

接下来讲一讲quicklist:

  quicklistNode结构体里包含了前一个节点和下一个节点指针,这样每个quicklistNode形成了一个双向链表。但是链表节点的元素不再是单纯保存元素值,而是保存了一个压缩列表,所以quicklistNode结构有个压缩列表的指针。

  在向quicklist添加一个元素的时候,不会像普通链表那样,直接新建一个链表节点,而是会检查插入位置的压缩列表是否能容纳该元素,如果能容纳就直接保存到quicklistNode结构里的压缩列表,不能容纳才新建一个新的quicklistNode结构。

  quicklist会控制quicklistNode结构里的压缩列表的大小或者元素个数,来规避潜在连锁更新风险,但并没有完全解决连锁更新的问题。

  

 

 

listpack

  quicklist虽然通过quicklistNode 结构里的压缩列表的大小或者元素个数,来减少连锁更新带来的性能影响,但是并没有完全解决连锁更新的问题。

  因为quicklistNode 还是用了压缩列表来保存元素,压缩列表连锁更新问题,来源于其结构设计,所以要想彻底解决这个问题,需要设计一个新的数据结构。

  于是,Redis在5.0 新设计一个数据结构叫listpack,目的是替代压缩列表,最大的特点是listpack中每个节点不在包含前一个节点的长度了,压缩列表每个节点正因为需要保存前一个节点的长度字段,就会有连锁更新的隐患。

  

  listpark头包含两个属性,分别记录了listpack总字节数和元素数量,然后listpack末尾也有个结尾标识。

   图中的listpack entry就是listpack的节点了。

  其中listpack entry:

  

 

   主要包含三个方面内容:

   encoding,定义该元素的编码类型,会对不同长度的整数和字符串进行编码;

   data,实际存放的数据;

   len,encoding + data的总长度; 

   可以看到,listpack没有压缩列表中记录前一个节点长度的字段了,lsitpack只记录当前节点的长度,当我们像listpack加入一个新元素,不会影响其他节点的长度字段的变化,从而避免了压缩列表的连锁更新问题。

 

Redis对象:

  hash数据类型:

  1. ziplist

  2. hashtable

  两个情况,哈希对象所有键值对字符串长度小于64个字节;

  键值对的数据量小于512个

  否则就会使用hashtable作为数据存储方式

 

2. zset有序集合:

  1. skiplist: 通过分数查元素

  2. dict          通过元素查分数

  3. ziplist   当数量比较少的时候使用ziplist

      

  

 

 

  

  

  

  

 

 

  

这篇关于redis的底层原理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!