NA-TRANSFER
NA-TRANSFER

Bitcask存储引擎

geroge geroge 收录于 数据库
 约 300 字 预计阅读 2 分钟 

背景介绍

为了解决分布式数据库Riak高性能、低延迟的本地存储需求，Riak设计了Bitcask存储引擎，能够快速读写、处理大数据集、具备容灾能力且易于备份和恢复。Bitcask存储引擎的特点有:

  1. 高性能读写：
    • 提供低读写延迟和高随机写吞吐率。
    • 在重访问负载下保持可预测的行为。
  2. 大规模数据处理：
    • 处理远超内存的数据集而不降低性能。
    • 确保在大数据量下的高效运行和稳定性。
  3. 崩溃恢复与数据完整性：
    • 系统崩溃友好，支持快速恢复且不丢失数据。
    • 提供简便的备份和恢复机制，确保数据安全。
  4. 简洁性与易维护性：
    • 代码格式和数据结构设计简洁易懂，便于维护和扩展。

存储结构

Bitcask架构简单，主要由：内存中键目录（keydir）和数据文件（data file）组成，其中数据文件包括活跃数据文件（active data file）和旧数据文件（older data file）。

图1 bitcask存储结构
图1 bitcask存储结构

数据文件

数据文件存在于磁盘上，组成了一个Bitcask实例目录，同一时刻只允许一个操作系统进程对其进行写操作。任何时刻，目录中只有一个文件是“活动”的，用于写入新数据，并且只通过追加方式写入。当现有活跃文件达到一定大小阈值时，会被关闭并创建一个新的活跃文件。一旦文件被关闭，它就成为不可变的，永远不会再被打开进行写操作。

每个数据文件都由若干个键值对条目组成。每个键值对条目格式简单，包括时间戳、键长度、值长度、键和值。

图2 键值对条目结构
图2 键值对条目结构

每次写入时，根据待插入的键值对数据生成一个新的条目，将条目追加到活动文件中，所以数据文件其实是这些条目的线性序列。

图3 数据文件内部逻辑结构
图3 数据文件内部逻辑结构

键目录

键目录是位于内存中的一张哈希表，存着所有数据文件每个键的位置信息，包括该键最近写入的文件id、值大小、偏移量和时间戳。

图4 键目录逻辑结构
图4 键目录逻辑结构

机制设计

Bitcask常见操作有打开数据实例、读写数据、合并旧数据文件以及备份恢复数据。

打开数据实例

Bitcask打开数据实例的流程如下。

图5 bitcask打开数据实例
图5 bitcask打开数据实例

  1. 初始化 BitCask 实例：

    • 检查要打开的数据目录是否存在，不存在则创建新的数据目录，否则打开当前数据目录。

  2. 加载键目录（Keydir）：

    • 初始化内存中的必要组件-键目录（keydir），用于快速查找键值对
    • 提示文件是 Bitcask 用于加速重启时键目录加载的辅助文件,存储了键的元数据，如果有提示文件存在，则会优先从提示文件中加载键目录，这样可以大大减少重启时的加载时间

  3. 打开数据文件：

    • 打开所有需要的数据文件，包括当前的活动文件和历史文件。对于每个文件，Bitcask 会检查文件的完整性，确保没有损坏。

  4. 启动后台任务：

    • 启动必要的后台任务，如定期合并（merge）旧的数据文件，以减少磁盘空间的使用。

  5. 准备写入：

    • 初始化写入缓冲区，准备接受新的写入请求。如果需要，创建一个新的数据文件，作为当前的活动写入文件。

  6. 完成打开：

    • 完成所有初始化步骤后，Bitcask 实例进入正常工作状态，可以接受读写请求。

读写流程

Bitcask读写流程如下图所示。

图6 bitcask读写流程
图6 bitcask读写流程

读操作

Bitcask读操作的流程如下：

  1. 查找键值：首先，Bitcask 会在内存中的 keydir 中查找给定的键；
  2. 读取数据：根据 keydir 中查找到的信息（文件 ID、位置和大小），直接从磁盘上的数据文件中读取数据。由于 keydir 中已经包含了数据的准确位置，因此读取操作只需要一次磁盘寻道；
  3. 利用操作系统缓存：在许多情况下，操作系统的文件系统读取缓存会使得这一操作比预期的更快。

所以Bitcask的读取操作非常高效，只需要一次磁盘寻道，并且可以利用操作系统的缓存来加速读取过程。

写操作

Bitcask写操作的流程如下：

  1. 打开 Bitcask 实例：调用 bitcask:open(DirectoryName, Opts) 打开或创建一个 Bitcask 数据存储。如果目录已有实例被打开，新进程将共享该实例的 keydir；
  2. 写入数据：通过 bitcask:put(BitCaskHandle, Key, Value) 将键值对追加写入当前的“活跃文件”中；
  3. 更新 keydir：写入完成后，内存中的 keydir 被更新，以记录最新数据的位置和大小；
  4. 同步数据（可选）：如果设置了 sync_on_put 选项，写入后会同步数据到磁盘，确保持久化；
  5. 关闭实例（可选）：完成所有写入操作后，可以调用 bitcask:close(BitCaskHandle) 关闭数据存储，并确保数据被完全写入磁盘。

删除是一种特殊的写操作。删除操作流程如下：

  1. 用户请求删除

    • 用户发起删除某个键的请求。

  2. 写入删除标记

    • 在日志中追加一条记录，表示要删除该键。
    • 更新 key-directory（键目录），标记该键为已删除。

  3. 完成删除请求

    • 对用户返回删除成功的响应。

  4. 等待合并过程

    • 定期或在合适的时机，执行后台的合并与清理过程。
    • 在合并过程中，扫描旧的日志文件。

  5. 合并操作

    • 将未被删除的键值对与新的键值对写入新的合并文件。
    • 忽略已标记为删除的键。

  6. 更新数据文件

    • 更新存储路径，替换旧的日志文件为新的合并文件。

  7. 清理旧文件

    • 删除旧的日志文件，释放磁盘空间。

图6 bitcask删除流程
图6 bitcask删除流程

合并过程

在合并过程中，Bitcask 通过以下步骤生成一组新的数据文件，并丢弃旧的、过时的数据条目：

  1. 读取非活跃文件 ：Bitcask 首先会读取所有非活跃文件（即旧文件）。这些文件包含了所有历史写入的数据条目。
  2. 构建键的最新版本映射 ：Bitcask 会遍历每个非活跃文件中的所有数据条目，并构建一个映射（map），该映射记录了每个键的最新版本。这个映射会覆盖旧版本的数据条目。
  3. 写入新数据文件 ：在构建了键的最新版本映射后，Bitcask 会打开一个新的数据文件（通常称为“合并文件”或“新文件”），并将映射中的所有最新版本的数据条目写入这个新文件。
  4. 丢弃旧数据条目 ：由于新文件中已经包含了所有键的最新版本，旧的、过时的数据条目在写入新文件后就不再需要了。因此，这些旧数据条目会被丢弃。
  5. 更新 keydir ：在合并过程中，Bitcask 会更新内存中的 keydir，使其指向新文件中的最新数据条目。
  6. 删除旧文件 ：合并完成后，Bitcask 会删除旧的非活跃文件，因为这些文件中的数据已经被合并到新文件中。
  7. 创建提示文件 ：为了加速未来的启动时间，Bitcask 会为新文件创建提示文件。提示文件记录了每个键在新文件中的位置和大小，但不包含实际的值。

图7 合并流程
图7 合并流程

总结来说，合并过程通过读取所有非活跃文件，构建键的最新版本映射，并将这些最新版本的数据条目写入新文件，从而丢弃旧的、过时的数据条目。这个过程有效地减少了存储空间的占用，并通过生成的提示文件加速了 Bitcask 的启动时间。

备份与恢复过程

完善中

与lsm-tree对比

Bitcask 和 LSM-Tree（Log-Structured Merge-Tree）是两种常见的键值存储引擎，它们各自有不同的优缺点，适用于不同的应用场景。以下是它们的主要优缺点对比：

Bitcask

优点：

  1. 简单高效 ：Bitcask 模型非常简单，易于理解和实现。它基于日志结构，数据写入速度非常快，因为写操作是顺序的，减少了磁盘寻道时间。
  2. 快速读取 ：由于 Bitcask 维护了一个内存中的哈希表（称为“键目录”），读取操作非常快，通常只需要一次内存查找。
  3. 低延迟写入 ：写入操作是直接追加到日志文件中，不需要复杂的合并操作，因此写入延迟较低。
  4. 易于备份和恢复 ：Bitcask 的数据文件是顺序的，易于备份和恢复。

缺点：

  1. 内存占用 ：Bitcask 需要维护一个内存中的哈希表来存储键和数据文件的偏移量，这会占用大量内存，尤其是在键数量巨大的情况下。
  2. 磁盘空间利用率 ：Bitcask 不支持原地更新，旧数据不会被覆盖，因此随着时间的推移，磁盘空间利用率会逐渐降低。
  3. 不支持范围查询 ：Bitcask 是基于键值对的存储，不支持高效的范围查询。

LSM-Tree

优点：

  1. 高写入吞吐量 ：LSM-Tree 通过将写操作先写入内存中的 MemTable，然后定期刷新到磁盘上的 SSTable（Sorted String Table），实现了高写入吞吐量。
  2. 高效的磁盘空间利用 ：LSM-Tree 通过合并和压缩操作，可以有效地回收旧数据占用的磁盘空间，提高磁盘利用率。
  3. 支持范围查询 ：由于数据是按顺序存储在 SSTable 中，LSM-Tree 支持高效的范围查询。
  4. 可扩展性 ：LSM-Tree 设计支持水平扩展，适合大规模数据存储和高并发写入场景。

缺点：

  1. 写放大问题 ：LSM-Tree 的写入操作可能会导致写放大问题，即一次写操作可能会触发多次磁盘写入（例如，合并和压缩操作）。
  2. 读取延迟较高 ：读取操作可能需要合并多个 SSTable 中的数据，尤其是在数据量较大时，读取延迟较高。
  3. 复杂性较高 ：LSM-Tree 的实现和管理相对复杂，涉及到多个组件（如 MemTable、SSTable、Bloom Filter 等）的协调和管理。

总结

  • Bitcask 适合于写入频繁、读取频繁但不需要范围查询的场景，尤其是在内存充足的情况下。
  • LSM-Tree 适合于需要高写入吞吐量、支持范围查询、并且可以容忍一定读取延迟的场景。

参考文献

  1. https://riak.com/assets/bitcask-intro.pdf
更新于 2024-10-29 
存储引擎
返回 | 主页
0%