Redis数据库执行命令速度快的原因是什么?

Redis数据库执行命令速度快的原因是什么?作为服务端工程师工作中Redis用到的比较多。很多人知道Redis 快仅仅因为它是基于内存实现的,对于其它原因倒是模棱两可。

Redis数据库执行命令速度快如下:

图片[1]-Redis数据库执行命令速度快的原因是什么?-时光博客网

一、基于内存实现

Redis基于内存的数据库,与磁盘数据库做对比,对于磁盘数据库来说需要将数据读取到内存里,这个过程会受到磁盘I/O的限制。而对于内存数据库来说,本身数据就存在于内存里没有了这方面的开销。

二、高效的数据结构

Redis中有多种数据类型,每种数据类型的底层都由一种或多种数据结构来支持。正是因为有了这些数据结构,Redis在存储与读取上的速度才不受阻碍。

Redis数据结构:

图片[2]-Redis数据库执行命令速度快的原因是什么?-时光博客网

1、简单动态字符串

即SDS,用来处理字符串。了解C语言的都知道它是有处理字符串方法的,而Redis就是C语言实现的:

(1)字符串长度处理

图片[3]-Redis数据库执行命令速度快的原因是什么?-时光博客网

字符串在C语言中的存储方式,想要获取「Redis」的长度,需要从头开始遍历直到遇到'\0'为止。

图片[4]-Redis数据库执行命令速度快的原因是什么?-时光博客网

Redis中怎么操作呢?用一个len字段记录当前字符串的长度。想要获取长度只需要获取len字段即可。

你看,差距不言自明。前者遍历的时间复杂度为O(n),Redis中O(1) 就能拿到速度明显提升。

在描述算法复杂度时,经常用到o(1), o(n), o(logn), o(nlogn)来表示对应算法的时间复杂度, 这里进行归纳一下它们代表的含义: 
这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度,也用于表示空间复杂度。 
O后面的括号中有一个函数,指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。 
比如时间复杂度为O(n),就代表数据量增大几倍,耗时也增大几倍。比如常见的遍历算法。 
再比如时间复杂度O(n^2),就代表数据量增大n倍时,耗时增大n的平方倍,这是比线性更高的时间复杂度。比如冒泡排序,就是典型的O(n^2)的算法,对n个数排序,需要扫描n×n次。 
再比如O(logn),当数据增大n倍时,耗时增大logn倍(这里的log是以2为底的,比如,当数据增大256倍时,耗时只增大8倍,是比线性还要低的时间复杂度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256个数据中查找只要找8次就可以找到目标。 
O(nlogn)同理,就是n乘以logn,当数据增大256倍时,耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。 
O(1)就是最低的时空复杂度了,也就是耗时/耗空间与输入数据大小无关,无论输入数据增大多少倍,耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度,无论数据规模多大,都可以在一次计算后找到目标(不考虑冲突的话)

(2)内存重新分配

C语言中涉及到修改字符串的时候会重新分配内存。修改地越频繁,内存分配也就越频繁。而内存分配是会消耗性能的,那么性能下降在所难免。而Redis中会涉及到字符串频繁的修改操作,这种内存分配方式显然就不适合了。

于是SDS实现了两种优化策略:

1>空间预分配

对SDS修改及空间扩充时,除了分配所必须的空间外,还会额外分配未使用的空间。
具体分配规则是这样的:SDS修改后,len长度小于1M,那么将会额外分配与len相同长度的未使用空间。如果修改后长度大于1M,那么将分配1M的使用空间。

2>惰性空间释放

有空间分配对应的就有空间释放。SDS缩短时,并不会回收多余的内存空间,而是使用free字段将多出来的空间记录下来。如果后续有变更操作,直接使用free中记录的空间,减少了内存的分配。

(3)二进制安全

已经知道了Redis可以存储各种数据类型,那么二进制数据肯定也不例外。但二进制数据并不是规则的字符串格式,可能会包含一些特殊的字符,比如'\0'等。前面我们提到过,C中字符串遇到 '\0' 会结束,那'\0' 之后的数据就读取不上了。但在SDS中,是根据len长度来判断字符串结束的。

2、双端链表

列表List更多是被当作队列或栈来使用的。队列和栈的特性一个先进先出,一个先进后出。双端链表很好的支持了这些特性。

图片[5]-Redis数据库执行命令速度快的原因是什么?-时光博客网

(1)前后节点

图片[6]-Redis数据库执行命令速度快的原因是什么?-时光博客网

链表里每个节点都带有两个指针,prev指向前节点,next指向后节点。这样在时间复杂度为O(1) 内就能获取到前后节点。

(2)头尾节点

图片[7]-Redis数据库执行命令速度快的原因是什么?-时光博客网

你可能注意到了,头节点里有head和tail两个参数,分别指向头节点和尾节点。这样的设计能够对双端节点的处理时间复杂度降至O(1) ,对于队列和栈来说再适合不过。同时链表迭代时从两端都可以进行。

(3)链表长度

头节点里同时还有一个参数len,和上边提到的SDS里类似,这里是用来记录链表长度的。因此获取链表长度时不用再遍历整个链表,直接拿到len值就可以了,这个时间复杂度是O(1)。

这些特性都降低了List使用时的时间开销。

3、压缩列表

双端链表我们已经熟悉了。不知道你有没有注意到一个问题:如果在一个链表节点中存储一个小数据,比如一个字节。那么对应的就要保存头节点,前后指针等额外的数据。这样就浪费了空间,同时由于反复申请与释放也容易导致内存碎片化。这样内存的使用效率就太低了。

图片[8]-Redis数据库执行命令速度快的原因是什么?-时光博客网

它是经过特殊编码,专门为了提升内存使用效率设计的。所有的操作都是通过指针与解码出来的偏移量进行的。并且压缩列表的内存是连续分配的,遍历的速度很快。

4、字典Redis

作为K-V型数据库,所有的键值都是用字典来存储的。日常学习中使用的字典你应该不会陌生,想查找某个词通过某个字就可以直接定位到,速度非常快。这里所说的字典原理上是一样的,通过某个key可以直接获取到对应的value。字典又称为哈希表,这点没什么可说的。哈希表的特性大家都很清楚,能够在O(1) 时间复杂度内取出和插入关联的值。

5、跳跃表

作为Redis中特有的数据结构-跳跃表,其在链表的基础上增加了多级索引来提升查找效率。

图片[9]-Redis数据库执行命令速度快的原因是什么?-时光博客网

这是跳跃表的简单原理图,每一层都有一条有序的链表,最底层的链表包含了所有的元素。这样跳跃表就可以支持在O(logN) 的时间复杂度里查找到对应的节点。

下面这张是跳表真实的存储结构,与其它数据结构一样都在头节点里记录了相应的信息减少了一些不必要的系统开销。

图片[10]-Redis数据库执行命令速度快的原因是什么?-时光博客网

三、合理的数据编码

对于每一种数据类型来说,底层的支持可能是多种数据结构,什么时候使用哪种数据结构,这就涉及到了编码转化的问题。不同的数据类型是如何进行编码转化的:

String:存储数字的话,采用int类型的编码,如果是非数字的话,采用raw编码;

List:字符串长度及元素个数小于一定范围使用ziplist编码,任意条件不满足,则转化为linkedlist编码;

Hash:hash对象保存的键值对内的键和值字符串长度小于一定值及键值对;

Set:保存元素为整数及元素个数小于一定范围使用intset编码,任意条件不满足,则使用hashtable编码;

Zset:zset对象中保存的元素个数小于及成员长度小于一定值使用ziplist编码,任意条件不满足,则使用skiplist编码。

四、合适的线程模型

图片[11]-Redis数据库执行命令速度快的原因是什么?-时光博客网

Redis快的原因还有一个是因为使用了合适的线程模型:

1、I/O多路复用模型

I/O:网络I/O

多路:多个TCP连接

复用:共用一个线程或进程

生产环境中的使用,通常是多个客户端连接Redis,然后各自发送命令至Redis服务器,最后服务端处理这些请求返回结果。

图片[12]-Redis数据库执行命令速度快的原因是什么?-时光博客网

应对大量的请求,Redis中使用I/O多路复用程序同时监听多个套接字,并将这些事件推送到一个队列里,然后逐个被执行。最终将结果返回给客户端。

2、避免上下文切换

Redis是单线程的。单线程的Redis为什么会快?因为多线程在执行过程中需要进行CPU的上下文切换,这个操作比较耗时。Redis又是基于内存实现的,对于内存来说,没有上下文切换效率就是最高的。多次读写都在一个CPU上,对于内存来说就是最佳方案。

3、单线程模型

Redis中使用了Reactor单线程模型,你可能对它并不熟悉。没关系,只需要大概了解一下即可。

图片[13]-Redis数据库执行命令速度快的原因是什么?-时光博客网

这张图里接收到用户的请求后,全部推送到一个队列里,然后交给文件事件分派器,而它是单线程的工作方式。Redis又是基于它工作的,所以说Redis是单线程的。

总结:

  • 基于内存实现数据都存储在内存里,减少了一些不必要的I/O操作,操作速率很快;
  • 高效的数据结构,底层多种数据结构支持不同的数据类型,支持Redis存储不同的数据;
  • 不同数据结构的设计,使得数据存储时间复杂度降到最低;
  • 合理的数据编码:根据字符串的长度及元素的个数适配不同的编码格式;
  • 合适的线程模型,I/O多路复用模型同时监听客户端连接;
  • 单线程在执行过程中不需要进行上下文切换减少了耗时。
© 版权声明
THE END
喜欢就支持一下吧
点赞6赞赏
分享
评论 抢沙发

请登录后发表评论