深度解析 Redis 存储结构及其高效性背后的机制

1. Redis 存储结构

Redis 是一个高性能的内存数据库，主要通过多种数据结构来实现高效的数据存储和快速的查询操作。这部分将深入探讨 Redis 的不同存储结构及其内部的转换机制。

存储结构

Redis 以键值对（Key-Value）的形式存储数据，但不仅限于简单的字符串类型。它支持多种复杂的数据类型，每种数据类型都有其特定的应用场景和内部实现机制：

• 字符串（String）：最基本的数据类型，可以存储任何类型的数据，如文本、数字等。适用于缓存单一值或简单的计数器。

• 哈希表（Hash）：用于存储对象，例如用户信息。哈希表适合存储多个字段和值的集合，类似于关系数据库中的行。

• 列表（List）：一个双向链表，支持从两端高效地插入和删除元素。常用于实现消息队列、任务列表等。

• 集合（Set）：一个无序的、唯一的元素集合，适用于去重操作、标签系统等。

• 有序集合（Sorted Set, ZSet）：类似于集合，但每个元素都有一个分数（score），元素按照分数有序排列。适用于排行榜、按优先级排序的任务队列等。

• 位图（Bitmap）、HyperLogLog、地理空间索引（Geo） 等其他高级数据结构，提供更多特定场景的优化支持。

存储转换

为了在不同的数据量和访问模式下保持高效，Redis 会根据具体情况动态调整内部存储结构：

• 编码转换：Redis 会根据存储的数据量和访问频率，自动选择最合适的内部表示。例如，较小的哈希表可能使用压缩的 ziplist 编码，以减少内存占用，而当哈希表元素数量超过一定阈值时，会转换为普通的哈希表（dict）以提高访问效率。

• 动态调整：当数据结构的大小或复杂度发生变化时，Redis 会动态调整底层数据结构，以确保性能和内存使用的最优化。例如，列表在元素较少时可能使用压缩列表（ziplist），元素增多后转换为双向链表。

2. 字典实现

Redis 的字典（hash table）是其核心数据结构之一，用于高效地存储和查找键值对。理解字典的内部实现对于优化 Redis 性能至关重要。

数据结构

Redis 字典主要由以下两个结构组成：

• dictEntry：表示字典中的一个节点，包含三个部分：

  • 键（key）：可以是任意支持的数据类型。
  • 值（value）：与键对应的数据。
  • 下一个指针（next）：用于链式解决哈希冲突，指向同一个哈希槽中的下一个 dictEntry。

• dictht：哈希表结构，包含以下字段：

  • 表大小（size）：当前哈希表的大小，即槽（bucket）的数量。
  • 使用数量（used）：当前哈希表中存储的键值对数量。
  • 指针数组（table）：一个指向 dictEntry 链表的指针数组，每个槽对应一个链表的头节点。

冲突处理

哈希冲突在任何哈希表实现中都是不可避免的，Redis 采用链地址法（Separate Chaining）来解决冲突：

• 链地址法：当多个键通过哈希函数映射到同一个槽时，这些键值对会被链接到一个链表中。dictEntry 中的 next 指针用于链接这些冲突的节点。

• 优化链表：为了提高性能，Redis 在处理链表时采用了多种优化策略，如使用更高效的内存分配和缓存友好的数据结构，减少链表遍历的开销。

负载因子

负载因子 = used / size ； used 是数组存储元素的个数， size 是数组的长度；负载因子越小，冲突越小；负载因子越大，冲突越大；redis 的负载因子是 1 ；

负载因子是衡量哈希表使用效率的重要指标：

• 高负载因子：意味着哈希表中每个槽平均存储更多的键值对，增加了冲突发生的概率，导致链表长度增加，从而降低查找效率。

• 负载因子调整：为了维持哈希表的高效性，Redis 会根据负载因子动态调整哈希表的大小。当负载因子超过设定阈值时，进行扩容；当负载因子过低时，进行缩容。

3. 扩容

当字典的负载因子超过阈值（通常是 1）时，Redis 会自动进行扩容操作，以维持哈希表的高效性。

扩容步骤

1. 确定新大小：通常将哈希表的大小翻倍，以减少扩容频率并保持低负载因子。

2. 内存分配：为新的哈希表分配更大的内存空间，确保有足够的槽来存储增加的键值对。

3. 数据迁移：将现有的键值对重新哈希并迁移到新的哈希表中。这个过程涉及将每个键重新计算哈希值，并根据新哈希表的大小将其分配到相应的槽中。

4. 替换旧表：完成数据迁移后，新的哈希表替代旧的哈希表，释放旧表的内存空间。

影响与优化

• 性能影响：扩容是一个耗时的操作，尤其在字典规模较大时，可能导致短暂的性能下降或阻塞。

• 渐进式扩容：为了减少扩容对性能的影响，Redis 使用渐进式 rehash（详见第 5 节），将扩容过程分摊到多个操作中，避免一次性完成所有数据迁移。

4. 缩容

当字典的负载因子低于阈值（通常是 0.1）时，Redis 会进行缩容操作，以释放不必要的内存资源。

缩容步骤

1. 确定新大小：根据当前键值对的数量，计算出一个最小且适合的哈希表大小，避免过度缩小导致频繁的扩缩容操作。

2. 内存释放：将哈希表大小调整为新的尺寸，释放多余的内存空间。

3. 数据迁移：与扩容类似，将现有的键值对重新哈希并迁移到新的哈希表中，以适应缩小后的槽数量。

4. 替换旧表：新的哈希表替代旧的哈希表，释放旧表的内存。

优化策略

• 避免频繁缩容：为防止由于负载因子频繁波动导致的频繁扩缩容，Redis 采用了渐进式调整和阈值保护机制。

• 最小缩容步长：设置最小缩容步长，确保每次缩容都能显著减少内存占用，避免频繁的微调。

5. 渐进式 Rehash

为了避免一次性 rehash 导致的性能问题，Redis 采用了渐进式 rehash 技术，将 rehash 过程分散到多个客户端操作中进行。

渐进式 Rehash 的工作原理

1. 双哈希表：在进行 rehash 时，Redis 同时维护两个哈希表：旧表和新表。新表的大小通常是旧表的两倍或一半，取决于是扩容还是缩容。

2. 分步迁移：每次客户端执行字典操作（如插入、删除、查找）时，Redis 会迁移部分数据从旧表移动到新表。这些迁移步骤是渐进的，逐步完成整个 rehash 过程。

3. 操作兼容：在 rehash 过程中，新的插入操作会直接插入到新表，而查找操作则会同时查询旧表和新表，确保数据的一致性。

4. 完成迁移：当所有数据迁移完成后，旧表被释放，新的哈希表完全接管数据存储。

Rehash 规则

• 元素重新映射：每个键通过哈希函数重新计算其在新表中的位置，根据新表的大小将其分配到相应的槽中。

• 渐进迁移：每次操作迁移一定数量的键值对，确保不会一次性占用过多的 CPU 资源，避免阻塞其他客户端请求。

优势

• 避免阻塞：渐进式 rehash 将 rehash 过程分散到多个小步骤中，避免了长时间的阻塞，提高了 Redis 的响应性。

• 平滑过渡：在 rehash 过程中，Redis 依然可以正常处理客户端请求，确保服务的连续性和稳定性。

6. SCAN 命令

SCAN 命令是 Redis 提供的一种用于遍历数据的迭代器，旨在替代 KEYS 命令，以实现更高效和安全的键遍历操作。

SCAN 的实现原理

• 游标（Cursor）机制：SCAN 使用一个游标来记录遍历的进度。客户端每次调用 SCAN 时，提供上一次返回的游标，服务器根据游标继续遍历剩余的键。

• 非阻塞遍历：与 KEYS 一次性返回所有键不同，SCAN 分批次返回部分键，避免了阻塞服务器和客户端的情况。

遍历顺序

• 伪随机顺序：SCAN 并不保证键的遍历顺序，而是以伪随机的方式返回键。这是因为 Redis 使用哈希槽和渐进式 rehash，遍历顺序可能会因哈希表的动态变化而变化。

• 高位进位加法：为了在不同调用之间有效地管理游标，SCAN 使用一种高位进位加法的方式来确保遍历的连续性和完整性。

避免重复和遗漏

• 一致性保证：Redis 通过特定的算法确保在遍历过程中尽量避免重复和遗漏键，即使在遍历过程中发生了哈希表的变化。

• 极端情况：在某些极端情况下，如 SCAN 过程中发生多次缩容或扩容，可能会导致部分键重复返回或遗漏。这种情况虽然罕见，但需要在应用层进行适当的处理。

使用场景

• 大规模数据遍历：适用于需要遍历大量键但不希望影响服务器性能的场景，如数据导出、统计分析等。

• 实时应用：由于 SCAN 是非阻塞的，适合在实时应用中使用，避免长时间的阻塞操作影响用户体验。

7. 过期（Expire）机制

Redis 提供了键的过期机制，允许在指定时间后自动删除键，以实现数据的自动过期和内存的自动回收。

过期管理方式

Redis 通过两种主要方式来管理过期键：

• 惰性删除（Lazy Deletion）

  • 工作原理：当客户端访问一个键时，Redis 会检查该键是否设置了过期时间。如果过期时间已到，Redis 会立即删除该键，并返回不存在的结果。
  • 优点：节省资源，只在需要时进行检查和删除，适用于不经常访问的键。
  • 缺点：如果过期键长时间不被访问，可能会占用内存，导致内存泄漏。

• 定时删除（Active Deletion）

  • 工作原理：Redis 定期随机扫描一部分设置了过期时间的键，并删除过期的键。这种扫描过程由 Redis 的后台线程自动执行，不依赖于客户端的访问操作。
  • 优点：能够及时回收过期键，避免内存被无效数据占用。
  • 缺点：可能会带来一定的 CPU 开销，特别是在大量键设置了过期时间时。

过期键的存储

• 单独数据结构：Redis 使用专门的数据结构（如一个有序集合）来存储所有设置了过期时间的键及其对应的过期时间。

• 高效查找：通过有序集合的特性，Redis 能够高效地查找和删除过期键，确保过期管理的性能。

过期策略优化

• 最少过期时间的键优先删除：在进行定时删除时，Redis 会优先删除最早过期的键，以最大化内存回收的效率。

• 批量删除：为了减少每次删除操作的开销，Redis 通常会批量删除多个过期键，而不是一次删除一个。

8. 大 Key 处理

在 Redis 中，“大 Key”指的是包含大量数据的键，如包含大量元素的哈希表、有序集合或列表。这些大 Key 在操作时可能会带来显著的性能问题，需要特别注意和优化。

内存分配问题

• 扩容时的内存分配：大 Key 在进行扩容（如哈希表扩容或跳表扩容）时，需要一次性分配大量内存。这可能导致 Redis 出现短暂的卡顿或内存分配失败。

• 删除时的内存回收：一次性删除大 Key 需要释放大量内存，可能会引发内存碎片或 GC（如果使用了内存管理机制）的额外开销。

性能问题

• 高延迟操作：对大 Key 的操作，如大批量插入、删除或查询，可能会导致高延迟，影响 Redis 的整体性能和响应时间。

• 阻塞问题：某些操作如重写 AOF（Append-Only File）或 RDB（Redis Database）快照时，如果包含大 Key，可能会导致 Redis 阻塞时间增加。

性能优化策略

• 分片存储：将大 Key 分片存储为多个较小的 Key，分散存储负载，减少单个 Key 的大小。例如，将一个大型列表分割为多个小列表。

• 批量操作优化：使用流水线（Pipeline）或事务（Transaction）等机制，批量处理大 Key 的操作，减少网络往返和操作延迟。

• 异步处理：对于耗时的操作，可以考虑使用异步处理或后台任务，避免阻塞主线程。

• 内存优化：选择合适的数据结构和编码方式，尽量减少大 Key 的内存占用。例如，使用压缩列表（ziplist）来存储小规模的哈希表或列表。

9. 跳表实现

Redis 使用跳表（Skip List）作为有序集合（Sorted Set, ZSet）的底层实现，以提供高效的有序数据存储和快速的增删查改操作。

跳表的基本概念

跳表是一种基于多层链表的数据结构，通过在多个层级上建立跳跃指针，实现快速的查找和遍历操作。其主要特点包括：

• 多层结构：每个元素在不同层级上都有可能存在跳跃指针，层级越高，跳跃跨度越大。

• 随机化：元素在跳表中的层级通常是随机决定的，这种随机化策略保证了跳表在平均情况下具有良好的性能。

• 时间复杂度：跳表的查找、插入和删除操作的平均时间复杂度为 (O(\log N))，与平衡树相当，但实现更为简单。

理想跳表 vs. Redis 跳表

• 理想跳表

  • 结构：每隔一个节点增加一个层级，形成类似二叉树的结构。
  • 性能：在理想情况下，跳表能够高效地保持有序性和快速的操作性能。

• Redis 跳表

  • 扁平化设计：为了节省内存，Redis 的跳表采用了更扁平化的结构，限制了跳表的最大层级为 32 层。这与理想跳表的多层级结构有所不同，但在实际应用中仍能提供高效的操作性能。

  • 层级生成：Redis 使用概率机制（通常为 1/4 的概率提升到更高层级）生成跳表的层级，确保跳表在大多数情况下具有良好的平衡性和性能。

  • 节点结构：每个跳表节点包含指向下一个节点的指针，以及用于排序的分数（score）和对应的成员（member）。

跳表的操作

• 查找（Search）：从最高层级开始，依次向右移动，直到找到第一个大于或等于目标分数的节点，逐层向下直到最低层级。

• 插入（Insert）：首先确定新节点在每个层级上的位置，然后插入新的跳跃指针，维护跳表的有序性。

• 删除（Delete）：查找到要删除的节点，在所有层级上移除其跳跃指针，维护跳表的结构完整性。

跳表的优势

• 内存效率高：相比于平衡树，跳表的实现更为简单，且内存占用更少。

• 实现简便：跳表的代码实现相对简单，易于维护和优化。

• 性能稳定：在大多数情况下，跳表能够提供与平衡树相当的性能，且由于其随机化的结构，避免了最坏情况的性能下降。

参考

0voice · GitHub