。

另一方面则是因为高效的数据结构#xff0c;使得操作键值效率较高。

总体来说#xff0c;Redis使用了一个用来保存每个Key/Value的全…数据结构

Redis之所以“快”一方面因为它是内存数据库所有操作都在内存上完成内存的访问速度本来就快。

另一方面则是因为高效的数据结构使得操作键值效率较高。

总体来说Redis使用了一个用来保存每个Key/Value的全局哈希表结构其中Value类型又包括了支持集合类型的双向链表、压缩列表、跳表等五大底层结构。

简单来说底层数据结构一共有

种分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组。

它们和数据类型的对应关系如下图所示

Redis使用了一个全局维度的哈希表来保存所有的Key/Value每个哈希表本质上都是一个数组这个数组的每个元素称为一个哈希桶。

哈希桶中的元素保存的并不是Value本身而是指向Value的指针如下图所示

由数据结构的知识可以知道哈希表的时间复杂度为O(1)因此它非常适合快速查找的场景。

当往哈希表中写入的数据变的很多时哈希冲突问题就会出现。

Redis采用了链式哈希来解决哈希冲突。

但是如果哈希表里写入的数据越来越多哈希冲突链也会进而变得很长从而导致这个链条上得元素查找耗时长效率降低。

因此Redis还会对哈希表做rehash操作。

所谓rehash就是增加现有的哈希桶的数量让逐渐增多的entry元素能够在更多的桶之间分散保存减少单个桶中的元素数量从而减少单个桶中的冲突。

在具体操作中Redis会开辟一个新的哈希表比如大小为之前的两倍然后把之前哈希表的数据重新映射到新的哈希表最后释放之前的哈希表。

在拷贝之前哈希表数据到新哈希表时涉及到数据量过大有可能会造成Redis的线程阻塞从而无法服务其他的请求。

因此Redis采用了渐进式哈希的解决方案。

简单来说所谓渐进式哈希就是不一次性把老哈希表中的数据迁移完而是在每次处理一个请求时从老哈希表中的第一个索引位置开始顺带着将这个索引位置上的所有entries拷贝到新哈希表中等下一个请求时再顺带拷贝下一个索引位置的entries。

如此便将一次性的大量拷贝的开销分摊到多次处理请求的过程中避免了耗时的操作和服务的中断。

此外渐进式rehash执行时除了根据键值对的操作来进行数据迁移Redis本身还会有一个定时任务在执行rehash如果没有键值对操作时这个定时任务会周期性地例如每100ms一次搬移一些数据到新的哈希表中这样可以缩短整个rehash的过程。

I/O

键值对读写之外的其他功能大多都是由额外的线程执行的。

比如持久化、异步删除、集群数据同步等操作。

NoteRedis

6.0之后对网络I/O改为使用多线程但是仍然使用单线程处理键值对的读写操作。

Redis

多线程系统中通常会有共享资源需要被多个线程访问和修改。

为了保证这些共享资源的正确性需要额外的机制如锁来进行控制。

这些机制会带来额外的开销。

多线程开发中并发访问控制是一个难点。

如果没有精细设计只是简单使用粗粒度的互斥锁会导致大部分线程在等待锁导致并行变成串行系统吞吐率不升反降。

我们都知道Redis公开出来的数据Redis使用单线程也可以达到每秒10万级的处理能力前提条件在一定的服务器配置下才能达到。

为什么这么高效核心原因有两个

2Redis采用了多路复用机制使其在网络I/O操作中能够并发处理大量的客户端请求从而实现高吞吐率。

其中原因2是Redis单线程高效率的重点它避免了accept()

send()/recv()

Redis在设计中基于Linux的I/O多路复用机制实现了自己的I/O模型如下图所示

上图中的多个FD就是多个套接字SocketRedis的网络框架通过调用epoll让内核监听这些套接字。

此时Redis线程不会阻塞在某一个特定的监听

已连接的套接字上。

因此Redis可以同时和多个客户端连接并处理请求从而提升并发性。