Redis为什么快

22
四月
2021

基于内存实现

此处不展开

高效的数据结构

redis提供了5种数据类型,其应用场景如下

Stringlisthashsetzset
缓存、计数器、分布式锁等链表、队列hash表,用户信息去重、共同好友等访问量排行榜

为了追求速度,不同的数据类型使用不同的数据结构速度才得以提升,rediss提供6中低层数据结构
在这里插入图片描述

Redis hash 字段

Redis整体就是一个哈希表保存所有的键值对,哈希表本质就是一个数组,每个元素都被叫做哈希桶,无论是什么数据类型,每个桶里面的entry保存着实际具体值的指针,哈希表查找的时间复杂度为O(1),这也是Redis快的原因之一。

在这里插入图片描述
使用Hash无法避免的问题就是hash冲突,Redis通过链式哈希解决此问题,也就是同一个桶里面的元素使用链表保存,但是当链表过长一定会导致查询变慢,所以redis使用两个哈希表,用rehash操作增加现有的哈希桶数量,进而减少冲突。

一开始默认使用hash1存储键值对,此时并没有给hash2分配空间,当数据越来越多触发rehash时会进行如下操作
1.给hash2分配更大空间
2.将hash1的数据重新计算哈希映射到hash2中
3.释放hash1的空间
但是步骤二的数据映射并不是一次性的,因为一次性映射会造成阻塞影响使用。Redis才用渐进式rehash,而是将rehash的过程分散到每次客户端的请求中。

SDS简单动态字符

比起C语言中的字符串结构,SDS有更多的优势
在这里插入图片描述
1.O(1)的时间复杂度获取字符串长度
c语言中字符串如果想获取长度需要遍历整个字符串,知道遇到’\0’结束,而SDS中保存字符串长度
2.空间预分配
SDS被修改后,不仅会为SDS分配所需要的必须空间,还会分配未使用空间,当len长度小于1M时,将分配和len相同长度的未使用空间,当len长度>1M时,将分配1M的未使用空间
3.惰性空间释放
当对SDS缩短时,程序并不会回收多余的内存空间,进而减少了后续append操作的内存分配步骤。
4.二进制安全
因为SDS有len标识,所以哪怕遇到’\0’也不会认为到了字符串末尾

zipList 压缩列表

当一个列表只有少量数据并且每个列表项要么是小整数值要么是长度比较短的字符串时,Redis就会使用压缩链表来做列表建的底层实现。

zipList是由连续内存块组成的顺序性的数据结构,其中包括多个entry节点,其表头有三个字段zlbytes(占用字节数)、zltail(列表尾的偏移量)和zllen(节点个数),在ziplist尾部还有一个zlend标识结束位
在这里插入图片描述

linkedList双端列表

特点
1.每个节点都有prev和next指针,获取前直节点和后直节点比较方便
2.带表头指针和表尾指针,获取链表头结点和尾节点的复杂度为O(1)
3.带链表长度计数器
4.节点使用指针来保存节点值,所以链表可以用于保存各种不同类型的值。

目前已经使用quicklist代替了ziplist和linkedlist.quick是两者的结合体,它将linkedlist分段,每一段都使用ziplist储存,多个ziplist之间使用双向指针连接
在这里插入图片描述

整数数组intset

当集合中值包含证书并且元素数量不多时,Redis就使用该集合作为set的底层实现

encodinglengthcontents
编码方式元素数量元素数组

skipList跳表

zset的排序功能就是通过跳表实现的,跳表是一种有序的数据结构,它通过每个节点中维护多个指向其他节点的指针从而达到快速访问节点的目的。
在这里插入图片描述
如上图所示,查找key为40的节点只需要遍历三次(1->28->40)

合理的数据编码

stringListHashSetZset
存储数字使用int,否则使用row字符串长度<64字节切元素个数<512使用ziplist,否则使用LinkedList(高版本都使用quickList) 这两个条件是可配置的所有的键值对的key和value字符串均<64字节并且键值对数量<512使用ziplist,否则使用hashtable元素全部为证书且个数小于一定范围使用intSet否则使用hashtable成员长度都小于64字节切个数小于128使用ziplist否则使用跳表

单线程模式

Redis单线程指的是Redis的网络IO以及键值对指令的读写是单线程的,但是对于Redis的持久化、集群数据同步等都是由不同线程执行的

单线程有点:
1.不会因为创建线程导致性能损耗
2.避免上下文切换带来的cpu消耗,不存在线程切换的开销
3.避免线程之间的竞争关系,无需考虑锁

问题:Redis使用单线程是否没有充分利用cpu资源呢?
回答:因为redis是基于内存操作的,CPU并不是redis的瓶颈,而是机器内存大小或者网络带宽,所以多线程也就没有必要了。

IO多路复用

Redis才用epoll+自己实现的简单事件框架处理。epoll中的读、写、连接、关闭都转化为了事件,利用epoll多路复用的特性减少IO时间
在这里插入图片描述

基本IO模型

在这里插入图片描述
0.监听某个端口
1.和客户端建立accpt (如果redis监听到一个客户端有连接请求但是一直未能建立连接会阻塞在此,进而导致其他客户端无法建立连接
2.从socket中读取recv (当Redis通过recv()从客户端读取数据,但是数据迟迟没有到达,Redis也会一直阻塞在这
3.解析客户端发送的请求parse
4.执行get、set指令
5.返回客户端数据

这也是基本IO模型最大的弊端

IO多路复用

多路指的是多个socket连接,复用指的是复用一个线程。多路复用主要有三种技术,分别是select、poll、epoll(优选)

Redis在单线程下,内核会一直监听socket上的连接请求或者数据请求,一旦有请求到达就交给Redis线程处理,这就实现了一个Redis线程处理多个IO流的效果。这样Redis线程不会阻塞在某一个特定的监听或者已连接的socket上,从而提高并发

总结

1.基于内存操作,一般都是存取操作,时间的花费主要集中在IO上,所以速度较快
2.整个redis就是一个全局hash表,所以查找较快,为解决hash冲突导致链表过程问题,使用两个哈希表托冲哈希桶数量从而减少哈希冲突,并且采用渐进式rehash避免阻塞问题
3.高效的低层数据结构,比如压缩表对短数据进行压缩存储、跳表加快访问速度。并且根据不同的数据类型选择合适的编码进行存储。
4.采用单线程模式,减少线程间切换,无需考虑锁机制。
5.非阻塞IO,IO多路复用技术提高并发能力

如有侵权请及时联系删除谢谢!

TAG

网友评论

共有访客发表了评论
请登录后再发布评论,和谐社会,请文明发言,谢谢合作! 立即登录 注册会员