文章图片



文章图片



文章图片



文章图片


本文导读Redis的性能为什么如此优异 ， 席卷各大互联网公司 ， 其一 ， 它是内存数据库 ， 内存的访问速度本身就快 。 其二 ， 优雅高效的底层数据结构 。
数据存储方式Redis采用全局哈希表以键值对的形式来存储所有数据 ， 每一个哈希桶中仅保存具体值的指针 ， 这样就可以在节省空间的情况以O(1)的效率进行查找 。

全局哈希表
当数据量不断增大时 ， redeis采用链式哈希解决hash冲突问题 ， 即同一哈希桶中的多个元素采用链表存储 ， 这样查询时间复杂度就退化为了O(n) 。


哈希冲突
为了解决hash冲突问题 ， redis会采用rehash操作 ， 即增加hash桶数量 ， 将冲突的数据打散保存 。 为了使rehash操作更高效 ， Redis默认使用了两个全局哈希表A和B 。

一开始 ， 当你刚插入数据时 ， 默认使用哈希表A ， 此时的哈希表B并没有被分配空间 。 随着数据逐步增多 ， Redis开始执行rehash：
首先 ， 给哈希表B分配更大的空间 ， 一般为表A的两倍；
其次 ， 把哈希表A中的数据重新映射并拷贝到哈希表B中；
最后 ， 释放哈希表A的空间 。
第二步看似简单 ， 但是当数据量巨大的时候进行拷贝会阻塞redis线程 ， 导致正常的业务请求无法被处理 。 为了解决该问题 ， redis采用了渐进式rehash ， 将一次性大量拷贝的开销分摊到每一次业务请求当中 。 如图所示 ， 每处理一个请求时 ， 从哈希表1中的第一个索引位置开始 ， 顺带着将这个索引位置上的所有entries拷贝到哈希表2中；等处理下一个请求时 ， 再顺带拷贝哈希表1中的下一个索引位置的entries 。

【网络安全|Redis的高效数据结构】
渐进式哈希
基础数据结构
Redis键值对中值的数据类型一共包含五种：String(字符串)、List(列表)、Hash(哈希)、Set(集合)和Sorted Set(有序集合) ， 这些是数据的保存形式 。 对应的底层实现数据结构一共有6种 ， 分别是简单动态字符串、双向链表、压缩列表、哈希表、跳表和整数数组 。 具体对应关系如下：

数据结构对应关系
可以看到 ， String类型的底层实现主要有简单动态字符串一种数据结构 。 List、Hash、Set和Sorted Set底层都有两种实现结构 ， 四种类型称为集合类型 ， 它们的特点是一个键对应了一个集合的数据 。 在这6中数据结构中 ， 双向链表、哈希表、整数数组是释放常见的就不再过多解释 ， 我们下面重点介绍下简单动态字符串、压缩列表和跳表三种数据结构 。

简单动态字符串（Simple Dynamic String - SDS）Redis没有直接使用C语言传统的字符串 ， 而自己构建了一种简单动态字符串的抽象类型 ， 并将此作为默认字符串表示 。 SDS由三个字段构成 ， len记录buf数组已使用的字节数量 ， 即sds保存的字符串的长度 ， 不含'\\0'；free 记录buf数组中未使用字节的数量；buf[
记录字节数组 ， 用于保存字符串 。 这样具有明显优势 ， 其一 ， 获取字符串的长度的时间复杂度为O(1)；其二 ， 字符串进行拼接时可以快速检查剩余空间避免缓存区溢出；其三 ， 空间预分配减少修改字符串带来的内存重分配次数 。


压缩列表压缩列表实际上类似于一个数组 ， 数组中的每一个元素都对应保存一个数据 。 和数组不同的是 ， 压缩列表在表头有三个字段 zlbytes、zltail 和 zllen ， 分别表示列表长度、列表尾的偏移量和列表中的 entry个数；压缩列表在表尾还有一个zlend ， 表示列表结束 。 在压缩列表中 ， 如果我们要查找定位第一个元素和最后一个元素 ， 可以通过表头三个字段的长度直接定位 ， 复杂度是O(1) 。 而查找其他元素时 ， 就没有这么高效了 ， 只能逐个查找 ， 此时的复杂度就是 O(N) 了 。

跳表有序链表只能逐一查找元素 ， 导致操作起来非常缓慢 ， 于是就出现了跳表 。 具体来说 ， 跳表在链表的基础上 ， 增加了多级索引 ， 通过索引位置的几个跳转 ， 实现数据的快速定位 ， 如下图所示：分页标题#e#
如果我们要在链表中查找 33 这个元素 ， 只能从头开始遍历链表 ， 查找 6 次 ， 直到找到 33 为止 。 此时 ， 复杂度是 O(N) ， 查找效率很低 。 为了提高查找速度 ， 我们来增加一级索引：从第一个元素开始 ， 每两个元素选一个出来作为索引 。 这些索引再通过指针指向原始的链表 。 例如 ， 从前两个元素中抽取元素 1 作为一级索引 ， 从第三、四个元素中抽取元素 11 作为一级索引 。 此时 ， 我们只需要 4 次查找就能定位到元素 33 了 。 如果我们还想再快 ， 可以再增加二级索引：从一级索引中 ， 再抽取部分元素作为二级索引 。 例如 ， 从一级索引中抽取 1、27、100 作为二级索引 ， 二级索引指向一级索引 。 这样 ， 我们只需要 3 次查找 ， 就能定位到元素 33 了 。 可以看到 ， 这个查找过程就是在多级索引上跳来跳去 ， 最后定位到元素 。 这也正好符合“跳”表的叫法 。 当数据量很大时 ， 跳表的查找复杂度就是 O(logN) 。

来源：(帝都小梁)

【】网址：/a/2021/0205/kd682512.html

标题：网络安全|Redis的高效数据结构