Redis高性能的原因及说明

一、基于内存实现 Redis 是基于内存的数据库,那不可避免的就要与磁盘数据库做对比。 对于磁盘数据库来说,是需要将数据读取到内存里的,这个过程会受到磁盘 I

一、基于内存实现

Redis 是基于内存的数据库,那不可避免的就要与磁盘数据库做对比。

对于磁盘数据库来说,是需要将数据读取到内存里的,这个过程会受到磁盘 I/O 的限制。

而对于内存数据库来说,本身数据就存在于内存里,也就没有了这方面的开销。

二、高效的数据结构

Redis 中有多种数据类型,每种数据类型的底层都由一种或多种数据结构来支持。

正是因为有了这些数据结构,Redis 在存储与读取上的速度才不受阻碍。

1. 简单动态字符串(SDS)

(1)字符串长度处理

用一个 len 字段记录当前字符串的长度。想要获取长度只需要获取 len 字段即可,时间复杂度为 O(1)。

(2)内存重新分配

修改字符串的时候会重新分配内存。修改地越频繁,内存分配也就越频繁。而内存分配是会消耗性能的,那么性能下降在所难免。而 Redis 中会涉及到字符串频繁的修改操作,于是 SDS 实现了两种优化策略:

  • - 空间预分配

对 SDS 修改及空间扩充时,除了分配所必须的空间外,还会额外分配未使用的空间。

具体分配规则是这样的:SDS 修改后,len 长度小于 1M,那么将会额外分配与 len 相同长度的未使用空间。如果修改后长度大于 1M,那么将分配1M的使用空间。

  • - 惰性空间释放

当然,有空间分配对应的就有空间释放。

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

(3)二进制安全

读取字符串遇到 ‘\0’ 会结束,那 ‘\0’ 之后的数据就读取不上了。但在 SDS 中,是根据 len 长度来判断字符串结束的,二进制安全的问题就解决了。

2. 双端链表

  • - 头尾节点

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

  • - 链表长度

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

  • - 每个节点

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

  • - 链表结构

3. 压缩列表

如果在一个链表节点中存储一个小数据,比如一个字节。那么对应的就要保存头节点,前后指针等额外的数据。

这样就浪费了空间,同时由于反复申请与释放也容易导致内存碎片化。这样内存的使用效率就太低了。Redis为了节约内存开发了压缩列表。

压缩列表结构

参数说明:

  • zlbytes:记录整个压缩列表占用的内存字节数。
  • zltail:记录压缩列表表尾节点距离压缩列表起始地址有多少字节。
  • zllen:记录了压缩列表包含的节点数量。
  • entryN:压缩列表的节点,节点长度由节点保存的内容决定。
  • zlend:特殊值0xFF(十进制255),用于标记压缩列表的末端。

4. 字典

dict结构体是字典中最顶层的结构体,用于指向两个哈希表,两个哈希表是为了在扩容时使用

hash扩容:

  • 1 创建ht[1],长度= len(ht[0]) * 2
  • 2 将ht[0]上的数据rehash到ht[1]上,即重新计算哈希地址
  • 3 释放ht[0],将ht[1]设置为ht[0],然后创建新的ht[1]

5. 跳跃表

调表的结构:

由多层链表构成,每层之间部分节点相连,且每层链表的数据都是有序的

最底层的链表是双向的,且包含所有元素,可实现类似二分查找,

在调表中的查找次数接近层数,时间复杂度为O(logn)

用随机化来决定哪些节点需要上浮

跳表中的查找:

类似二分查找,从最顶层开始查找,大数向右查找,小数向左查找

如查找17,查找路径为 13 -> 46 -> 22 -> 17

因为17>13(L3),就在L3中往后走,发现17<46(L3),

就通过13(L3)到达了13(L2),然后往后走发现17<22(L2),

就通过13(L2)往下达到了13(L1),然后往后走就遇到了17

查找35 13 -> 46 -> 22 -> 46 -> 35

查找 54 13 -> 46 -> 54

跳表中的插入:

1 先在最底层链表中找到合适的位置,并插入

2 然后用抛硬币的方式决定它是需要上浮的次数

假如此时链表共3层,需要抛两次硬币,来决定它上浮几次

跳表与平衡树、哈希表的比较

1 skiplist和各种平衡树(如AVL、红黑树等)的元素是有序排列的,而哈希表不是有序的。

因此,在哈希表上只能做单个key的查找,不适宜做范围查找。所谓范围查找,指的是查找那些大小在指定的两个值之间的所有节点。

2 在做范围查找的时候,平衡树比skiplist操作要复杂。

在平衡树上,我们找到指定范围的小值之后,还需要以中序遍历的顺序继续寻找其它不超过大值的节点。

如果不对平衡树进行一定的改造,这里的中序遍历并不容易实现。

而在skiplist上进行范围查找就非常简单,只需要在找到小值之后,对第1层链表进行若干步的遍历就可以实现。

3 平衡树的插入和删除操作可能引发子树的调整,逻辑复杂,

而skiplist的插入和删除只需要修改相邻节点的指针,操作简单又快速。

4 从内存占用上来说,skiplist比平衡树更灵活一些。

一般来说,平衡树每个节点包含2个指针(分别指向左右子树),而skiplist每个节点包含的指针数目平均为1/(1-p),具体取决于参数p的大小。如果像Redis里的实现一样,取p=1/4,那么平均每个节点包含1.33个指针,比平衡树更有优势。

5 查找单个key,skiplist和平衡树的时间复杂度都为O(log n),大体相当;

而哈希表在保持较低的哈希值冲突概率的前提下,查找时间复杂度接近O(1),性能更高一些。

所以我们平常使用的各种Map或dictionary结构,大都是基于哈希表实现的。

从算法实现难度上来比较,skiplist比平衡树要简单得多。

四、合理的数据编码

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

那我们就来看看,不同的数据类型是如何进行编码转化的:

  • String:存储数字的话,采用int类型的编码,如果是非数字的话,采用 raw 编码;
  • List:字符串长度及元素个数小于一定范围使用 ziplist 编码,任意条件不满足,则转化为 linkedlist 编码;
  • Hash:hash 对象保存的键值对内的键和值字符串长度小于一定值及键值对;
  • Set:保存元素为整数及元素个数小于一定范围使用 intset 编码,任意条件不满足,则使用 hashtable 编码;
  • Zset:zset 对象中保存的元素个数小于及成员长度小于一定值使用 ziplist 编码,任意条件不满足,则使用 skiplist 编码。

五、合适的线程模型

1. I/O多路复用模型

2. 避免上下文切换

3. 单线程模型

总结

以上为个人经验,希望能给大家一个参考,也希望大家多多支持好代码网。

标签: Redis 高性能