RocksDB中Cuckoo Table技术内幕解析

Cuckoo-Table作为RocksDB里的一种SST文件格式，具有高吞吐量的随机点查找 (point lookups)能力，本文详细介绍了Cuckoo-Table的实现细节。

一、 Cuckoo Table 概述：一种为点查找优化的 SST 文件格式

在深入代码细节之前，我们首先需要理解 Cuckoo Table 在 RocksDB 生态系统中的位置和它的设计目标。

1.1 RocksDB 的可插拔表格式 (Pluggable Table Format) 架构

RocksDB 的一个强大特性是其高度模块化和可插拔的架构。SST (Sorted String Table) 文件的物理布局并非一成不变，而是由一个称为 TableFactory 的抽象工厂来定义的。这意味着开发者可以根据不同的工作负载，选择甚至开发不同的表格式实现，以达到最优的性能。

RocksDB 允许在数据库级别，甚至是列族 (Column Family) 级别指定不同的 TableFactory。这为精细化的性能调优提供了极大的灵活性。Cuckoo Table 正是 RocksDB 提供的、一种高度特化的表格式实现。

1.2 Cuckoo Table 的定位与适用场景

Cuckoo Table 的设计目标非常明确：为高吞吐量的随机点查找 (point lookups) 提供极致的性能。它基于布谷鸟哈希算法，能够以近乎 O(1) 的时间复杂度完成键查找。

为了达到这个目标，它建立在一些严格的假设和约束之上：

  • **键和值必须是定长的 (Fixed Length)**：这是其数据布局的基础。
  • 不支持 Merge 操作：它的结构不适合处理需要合并的写操作。
  • **不支持前缀布隆过滤器 (Prefix Bloom Filter)**：它的哈希基于完整的用户键 (user_key)。
  • 范围扫描性能较差：由于键是按哈希值散乱分布的，范围扫描的效率远低于默认的 BlockBasedTable。

因此，Cuckoo Table 的理想使用场景是：当你的业务主要是通过 Get() API 进行大量、快速的随机键查询，且很少或几乎没有范围扫描 (Iterator) 需求时，例如用作某些索引或元数据的存储。

1.3 Cuckoo Table 与默认 Block-Based Table 的核心区别

为了更清晰地理解其定位，我们可以将它与 RocksDB 默认的 BlockBasedTable 格式进行对比。

特性Cuckoo TableBlock-Based Table (默认)
核心数据结构哈希表 (Hash Table)B-Tree (通过索引块和数据块模拟)
点查找机制直接哈希计算内存地址，近 O(1)查找索引块 (1-2次 I/O)，再读取数据块 (1次 I/O)
范围扫描机制昂贵 (首次需全量读取并排序)高效 (按序迭代数据块)
键/值长度必须是定长可变长
适用场景专用于高速点查找通用场景，点查找和范围扫描性能均衡

二、 CuckooTableFactory：配置中心与构造工厂

CuckooTableFactory 是使用 Cuckoo Table 的入口。它遵循工厂设计模式，作为连接 RocksDB 内核与 Cuckoo Table 具体实现的桥梁。

2.1 Factory 的核心职责与设计模式

CuckooTableFactory 继承自 rocksdb::TableFactory，其核心职责有二：

  1. 持有配置：保存用户为 Cuckoo Table 指定的所有配置项 (CuckooTableOptions)。
  2. 创建实例：当 RocksDB 需要创建或读取 SST 文件时，调用工厂的 NewTableBuilder 或 NewTableReader 方法，来生产出配置正确的具体实例。

2.2 CuckooTableOptions：定制你的 Cuckoo Table

用户通过 CuckooTableOptions 结构体来定制 Cuckoo Table 的行为。

代码 (rocksdb/table.h):

struct CuckooTableOptions {
  // Determines the space utilization of the hash table.
  // Smaller values result in more space being used but fewer collisions.
  double hash_table_ratio = 0.9;

  // Maximum number of Cuckoo hash functions.
  uint32_t max_search_depth = 100;

  // In case of collision, Cuckoo hash will attempt to kick out an element
  // to other locations. This defines the block size that will be searched
  // within Cuckoo hash.
  uint32_t cuckoo_block_size = 5;

  // If this option is enabled, user key is treated as uint64_t and its value
  // is used as hash value. This option is valid only when user key is 8 bytes.
  bool identity_as_first_hash = false;

  // If this option is set to true, module hashing will be used to calculate
  // hash values. Otherwise, bit-masking will be used.
  bool use_module_hash = true;
};
  • hash_table_ratio: 哈希表空间利用率。值越小，哈希表越大，冲突越少，但空间浪费越多。
  • max_search_depth: 解决哈希冲突时，”踢出”路径的最大搜索深度，防止无限循环。
  • cuckoo_block_size: Cuckoo 块大小。这是一个优化，当哈希到一个位置时，会线性探测一个大小为 cuckoo_block_size 的区域，可以有效减少冲突。
  • identity_as_first_hash: 一个性能优化。当键本身就是 8 字节的整数时，可以直接将其值作为第一个哈希值，避免计算开销。

2.3 核心算法：CuckooHash 函数深度解析

CuckooHash 函数是整个 Cuckoo Table 功能的数学基础，它负责为同一个键生成多个不同的哈希位置。

代码 (table/cuckoo/cuckoo_table_factory.h):

static inline uint64_t CuckooHash(
    const Slice& user_key, uint32_t hash_cnt, bool use_module_hash,
    uint64_t table_size_, bool identity_as_first_hash,
    uint64_t (*get_slice_hash)(const Slice&, uint32_t, uint64_t)) {
#if !defined NDEBUG || defined OS_WIN
  if (get_slice_hash != nullptr) {
    return get_slice_hash(user_key, hash_cnt, table_size_);
  }
#else
  (void)get_slice_hash;
#endif

  uint64_t value = 0;
  if (hash_cnt == 0 && identity_as_first_hash) {
    value = (*reinterpret_cast<const int64_t*>(user_key.data()));
  } else {
    value = MurmurHash(user_key.data(), static_cast<int>(user_key.size()),
                       kCuckooMurmurSeedMultiplier * hash_cnt);
  }
  if (use_module_hash) {
    return value % table_size_;
  } else {
    return value & (table_size_ - 1);
  }
}

2.3.1 多哈希函数与种子

布谷鸟哈希需要为同一个键计算多个哈希值。这里的实现非常巧妙：它使用同一个 MurmurHash 算法，但通过传入不同的种子 (seed) 来达到目的。种子是由 kCuckooMurmurSeedMultiplier * hash_cnt 计算得来的。hash_cnt 从 0 开始递增，从而为同一个 user_key 生成一个哈希值序列。

2.3.2 Identity-as-first-hash 优化

if (hash_cnt == 0 && ...) 这段代码是一个性能捷径。当此选项开启，且键的长度为 8 字节时，第一个哈希函数 (hash_cnt == 0) 不会执行 MurmurHash，而是直接将键的 8 个字节内容重新解释 (reinterpret_cast) 为一个 int64_t 作为哈希值。对于本身就是数字类型的键，这极大地提升了哈希计算的速度。

2.3.3 范围映射：位运算与取模

if (use_module_hash) 分支决定了如何将 64 位的哈希值映射到 [0, table_size_ - 1] 的桶索引范围。

  • value % table_size_: 取模运算，通用但性能稍慢。
  • value & (table_size_ - 1): 按位与运算。当 table_size_ 是 2 的整数次幂时，这个操作与取模等价，但速度快得多。CuckooTableBuilder 在 use_module_hash 为 false 时会确保 table_size_ 满足此条件。

2.4 创建 Builder 和 Reader 实例

这两个方法是 TableFactory 接口的核心实现，负责“生产”具体的读写工具。

代码 (table/cuckoo/cuckoo_table_factory.cc):

TableBuilder* CuckooTableFactory::NewTableBuilder(
    const TableBuilderOptions& table_builder_options,
    WritableFileWriter* file) const {
  return new CuckooTableBuilder(
      file, table_options_.hash_table_ratio, 64,
      table_options_.max_search_depth,
      table_builder_options.internal_comparator.user_comparator(),
      table_options_.cuckoo_block_size, table_options_.use_module_hash,
      table_options_.identity_as_first_hash, nullptr /* get_slice_hash */,
      table_builder_options.column_family_id,
      table_builder_options.column_family_name, table_builder_options.db_id,
      table_builder_options.db_session_id, table_builder_options.cur_file_num);
}

Status CuckooTableFactory::NewTableReader(
    const ReadOptions& /*ro*/, const TableReaderOptions& table_reader_options,
    std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
    std::unique_ptr<TableReader>* table,
    bool /*prefetch_index_and_filter_in_cache*/) const {
  std::unique_ptr<CuckooTableReader> new_reader(new CuckooTableReader(
      table_reader_options.ioptions, std::move(file), file_size,
      table_reader_options.internal_comparator.user_comparator(), nullptr));
  Status s = new_reader->status();
  if (s.ok()) {
    *table = std::move(new_reader);
  }
  return s;
}
  • NewTableBuilder: 当 RocksDB 需要创建 Cuckoo Table 格式的 SST 文件时调用此方法。它会实例化一个 CuckooTableBuilder，并将工厂自身存储的 table_options_ 配置以及 RocksDB 核心传入的通用参数（如文件句柄、比较器等）一并传给 Builder 的构造函数。
  • NewTableReader: 当 RocksDB 需要读取一个 Cuckoo Table 格式的 SST 文件时调用此方法。它会实例化一个 CuckooTableReader，并将文件句柄、文件大小等信息传递给 Reader 的构造函数，以便 Reader 进行初始化。

三、 CuckooTableBuilder：从零到一构建哈希表

CuckooTableBuilder 负责将无序的键值对集合转换成一个结构紧凑、查询高效的 Cuckoo Table SST 文件。其过程可以概括为“收集 -> 构建 -> 写入”。

3.1 Builder 的核心流程：收集 -> 构建 -> 写入

  1. 收集 (Collect): 在 Add() 方法被调用时，Builder 并不立即构建哈希表。它首先进行约束验证（如键值是否定长），然后将所有键值对线性地追加到内存中的 kvs_ 和 deleted_keys_ 两个字符串缓冲区内。
  2. 构建 (Build): 当 Finish() 方法被调用时，真正的构建工作开始。Builder 会在内存中创建一个 std::vector<CuckooBucket> 来代表哈希表。它会遍历所有收集到的键，通过 MakeHashTable() 方法将它们逐一安置到 CuckooBucket 向量中，并在此过程中解决所有哈希冲突。
  3. 写入 (Write): 内存中的哈希表布局一旦确定，Finish() 方法就会遍历 CuckooBucket 向量，将每个桶的内容（真实的键值对或空桶占位符）按顺序写入文件。最后，附上包含所有元数据的属性块和文件尾部，完成 SST 文件的创建。

3.2 关键数据结构：CuckooBucket 的巧妙设计

CuckooBucket 是构建过程中哈希桶在内存中的临时表达，其设计的核心是效率。

代码 (table/cuckoo/cuckoo_table_builder.h):

private:
  struct CuckooBucket {
    CuckooBucket() : vector_idx(kMaxVectorIdx), make_space_for_key_call_id(0) {}
    uint32_t vector_idx;
    uint32_t make_space_for_key_call_id;
  };
  static const uint32_t kMaxVectorIdx = std::numeric_limits<int32_t>::max();

3.2.1 vector_idx：轻量级数据指针

该字段是一个 uint32_t 索引，指向键值对在 kvs_ 或 deleted_keys_ 字符串缓冲区中的位置。这种“指针”而非“实体”的设计极大地节省了内存。一个特殊值 kMaxVectorIdx 被用来标记这是一个空桶。

3.2.2 make_space_for_key_call_id：无重置的“已访问”标记

在 MakeSpaceForKey 的 BFS 搜索中，需要标记已访问的节点以防循环。常规的 bool visited 标志需要在每次搜索前重置整个哈希表，代价高昂。此字段通过一个不断递增的“调用ID”来解决这个问题。每次搜索都有一个唯一的ID，一个桶只有其 make_space_for_key_call_id 与当前搜索的ID相同时，才被认为是“已访问”。这巧妙地避免了重置操作，是重要的性能优化。具体的：

  • CuckooTableBuilder 内部维护一个从 0 开始的计数器 make_space_for_key_call_id。

  • 每次调用 MakeSpaceForKey 时, 这个计数器会 ++, 得到一个本次调用独一无二的 ID.

    // in cuckoo_table_builder.cc
// 在 MakeHashTable 的循环中
while (!bucket_found &&
    !MakeSpaceForKey(hash_vals, ++make_space_for_key_call_id, buckets,
     &bucket_id)) {
    // ...
}

  • 在 MakeSpaceForKey 的 BFS 搜索中, 当访问一个桶时, 它会把这个桶的 make_space_for_key_call_id 字段设置为当前调用的ID.

    // in cuckoo_table_builder.cc:
// 在 MakeSpaceForKey 的 BFS 探索中
(*buckets)[static_cast<size_t>(child_bucket_id)]
  .make_space_for_key_call_id = make_space_for_key_call_id;

  • 在检查一个桶是否”已访问”时, 它不再检查 bool 值, 而是比较桶的 make_space_for_key_call_id 是否等于当前调用的ID.

    // in cuckoo_table_builder.cc`):
if ((*buckets)[static_cast<size_t>(child_bucket_id)]
        .make_space_for_key_call_id == make_space_for_key_call_id) {
    // 已在本次搜索中访问过, 跳过
  continue;
}

3.3 Add() 方法：数据收集与约束验证

Add() 方法是数据流入 Builder 的入口，负责验证和暂存。

代码 (table/cuckoo/cuckoo_table_builder.cc):

void CuckooTableBuilder::Add(const Slice& key, const Slice& value) {
  // ...
  if (!has_seen_first_key_) {
    is_last_level_file_ = ikey.sequence == 0;
    has_seen_first_key_ = true;
    // ...
    key_size_ = is_last_level_file_ ? ikey.user_key.size() : key.size();
  }
  if (key_size_ != (is_last_level_file_ ? ikey.user_key.size() : key.size())) {
    status_ = Status::NotSupported("all keys have to be the same size");
    return;
  }
  // ... (similar check for value_size_)

  if (ikey.type == kTypeValue) {
    kvs_.append(is_last_level_file_ ? ikey.user_key.data() : key.data(),
                is_last_level_file_ ? ikey.user_key.size() : key.size());
    kvs_.append(value.data(), value.size());
    // ...
  }
  // ...
}

3.3.1 键值定长：Cuckoo Table 的硬性要求

代码中的 if (!has_seen_first_key_) 块会在添加第一个键时执行，捕获其键长和值长。后续所有 Add() 调用都会检查新的键值是否与第一次的长度严格相等。这是因为最终的 SST 文件是一个由定长桶组成的连续数组，Reader 需要依赖这个定长来计算偏移量。

3.3.2 LSM-Tree Level 判断与序列号剥离优化

is_last_level_file_ = ikey.sequence == 0; 这一行代码是一个关键优化。在 RocksDB 中，只有当一个键在整个数据库中是最新版本时（即所有旧版本已被合并，且上层没有新版本），其序列号才可能在Compaction到最底层时被“剥离”为0。因此，sequence == 0 是一个强烈的信号，表明这个文件将被放在 LSM-Tree 的最底层。在这种情况下，user_key 在该层是唯一的，Builder 便可以只存储 user_key 而非完整的 InternalKey，为每个键节省8字节。

为什么sequence == 0能表明这个文件在LSM-Tree的最底层？为什么user_key 在该层是唯一的

  1. 基础: Sequence Number (序列号) 的作用

    首先, 我们要理解 Sequence Number (后文简称 seq) 是什么.
    在 RocksDB 中, 每一次写入操作 (Put, Delete, Merge) 都会被分配一个全局唯一、单调递增的 seq. 它就像这次操作的”时间戳”或”版本号”. seq 的核心作用是实现多版本并发控制 (MVCC),也就是让不同时间的读请求能看到不同版本的数据快照.

    例如:

  2. Put(“mykey”, “v1”) -> 分配 seq=100

  3. Put(“mykey”, “v2”) -> 分配 seq=101

  4. Delete(“mykey”) -> 分配 seq=102

    在 RocksDB 内部, 这三个操作对应三个不同的 InternalKey: mykey@100, mykey@101, mykey@102. 即使它们的 user_key (“mykey”) 相同, 但因为 seq 不同, 它们是三个独立的条目.

  5. 解答: 为什么最底层的 user_key 是唯一的?

    这归功于 Compaction (合并) 机制.

    LSM-Tree 的数据是从高层 (Level 0, L0) 向底层 (Level 1, L2, …, Lmax) 不断合并的. Compaction 的一个核心任务就是清理冗余数据.

  • 在高层 (如 L0, L1): 一个 user_key 可能存在多个版本. 比如 L0 中可能同时存在 mykey@100 和 mykey@101. 这是因为 L0 的文件是 MemTable 直接 Flush 下来的,可能包含重叠的键范围和多个版本.

  • 合并过程中的版本选择: 当 RocksDB 将 L_N 层的文件和 L_{N+1} 层的文件进行合并时, 对于任何一个相同的 user_key, 它只会保留seq 最高 (也就是最新) 的那一个版本,而所有旧版本都会被丢弃.

  • 到达最底层 (Last Level): “最底层” (我们称之为 Lmax) 是数据的最终归宿. 当数据经过一层又一层的 Compaction 到达 Lmax 时, 所有关于同一个 user_key的历史版本都已经被处理掉了. 因此, 在 Lmax 这一层的所有 SST 文件中, 任意一个 user_key 最多只会存在一个条目. 如果这个 user_key 有一个更新的版本,那么这个新版本必然存在于比 Lmax 更高的层级 (L0 到 L_{max-1}).

    结论: Compaction 机制保证了在最底层的数据集合中, user_key 是唯一的.

  1. 为什么 ikey.sequence == 0 能假定在最底层?

    这是基于上述结论的一个非常重要的优化.

    既然我们知道了在最底层, user_key 是唯一的, 那么版本号 (seq) 对于区分 user_key 的多个版本来说, 就失去了意义. 它的存在只是为了和上层可能存在的新版本进行比较.

    RocksDB 在执行到最底层的 Compaction 时, 会进行一个特殊的检查:

    对于一个即将被写入最底层 Lmax 的键 user_key (假设其版本为 seq=S), RocksDB 会检查所有上层 (L0 到 L_{max-1}) 是否存在任何版本比 S 更新的 user_key.

  • 情况A: 存在更新的版本. 如果上层有一个 mykey@S_newer (其中 S_newer > S), 那么写入 Lmax 的这个键必须保留它原始的 seq=S, 以便未来的读请求能正确地选择上层的最新版本.

  • 情况B: 不存在任何更新的版本. 如果检查发现所有上层都没有 mykey 的踪影, 这意味着当前要写入 Lmax 的这个版本就是整个数据库中最新的、最权威的版本. 在这种情况下, seq
    对于版本控制来说是多余的. 为了节省空间 (每个 seq 占用 7 个字节), RocksDB 会执行一个”序列号剥离” (Sequence Number Stripping) 的优化: 直接将 seq 设置为 0.

    所以, 逻辑链是这样的:

  1. 只有在 Compaction 到最底层时, 才有可能触发 “序列号剥离” 优化.

  2. 只有当一个键在整个数据库中没有更老的版本(已被清理)也没有更新的版本(不存在于上层)时, 它的 seq 才会被置为 0.

  3. 因此, 当 CuckooTableBuilder 在 Add() 方法中看到一个键的 ikey.sequence == 0 时, 它可以做出一个非常可靠的推断: 这个键是经过了上述优化处理的.产生这种键的唯一途径就是一次到最底层的 Compaction (或者用户通过特殊接口直接Ingest文件到最底层).

  4. 既然文件中的一个键来自最底层, 那么可以合理地假定整个 SST 文件都是为最底层构建的.

    这就是为什么一行简单的 is_last_level_file_ = ikey.sequence == 0; 背后蕴含了对整个 LSM-Tree Compaction 和版本管理机制的深刻理解. 这个判断使得 Cuckoo Table可以为最底层文件进行特殊优化, 即直接存储 user_key (因为唯一), 而不是存储完整的 InternalKey, 从而节省了 8 字节/每条记录 的空间.

3.4 Finish() 方法：将内存布局写入文件

Finish() 是将内存中的理想布局物化为物理文件的过程。

代码 (table/cuckoo/cuckoo_table_builder.cc):

Status CuckooTableBuilder::Finish() {
  // ...
  status_ = MakeHashTable(&buckets);
  // ...
  // Determine unused_user_key to fill empty buckets.
  // ...

  // Write the table.
  for (auto& bucket : buckets) {
    if (bucket.vector_idx == kMaxVectorIdx) {
      io_status_ = file_->Append(opts, Slice(unused_bucket));
    } else {
      io_status_ = file_->Append(opts, GetKey(bucket.vector_idx));
      if (io_status_.ok() && value_size_ > 0) {
          io_status_ = file_->Append(opts, GetValue(bucket.vector_idx));
      }
    }
    // ...
  }

  // Write meta blocks.
  // ...
  return status_;
}

该方法首先调用 MakeHashTable() 完成内存布局。然后，它会生成一个保证不存在的 unused_bucket 作为空位占位符。接着，它遍历 buckets 向量，如果桶是空的 (vector_idx == kMaxVectorIdx)，就写入占位符；否则，就通过 GetKey() 和 GetValue() 从缓冲区取出真实的键值对写入文件。最后，写入包含所有布局参数的属性块和文件尾部。

3.5 MakeHashTable()：哈希放置调度

此函数是放置所有键的调度中心，它为 Add() 收集的每个键寻找一个“家”。

代码 (table/cuckoo/cuckoo_table_builder.cc):

Status CuckooTableBuilder::MakeHashTable(std::vector<CuckooBucket>* buckets) {
  // ...
  for (uint32_t vector_idx = 0; vector_idx < num_entries_; vector_idx++) {
    // ...
    // 1. 尝试直接放置
    for (uint32_t hash_cnt = 0; hash_cnt < num_hash_func_ && !bucket_found; ++hash_cnt) {
      // ... 遍历 Cuckoo Block 寻找空位
    }

    // 2. 处理冲突
    while (!bucket_found &&
           !MakeSpaceForKey(hash_vals, ++make_space_for_key_call_id, buckets,
                            &bucket_id)) {
      // 3. 增加哈希函数作为最后手段
      // ...
    }

    // 4. 最终放置
    (*buckets)[static_cast<size_t>(bucket_id)].vector_idx = vector_idx;
  }
  return Status::OK();
}

它的策略是：对每个键，首先尝试最廉价的操作——直接在它的所有哈希位置（包括Cuckoo Block）中寻找空位。如果失败，则进入 while 循环，调用昂贵的 MakeSpaceForKey() 尝试“踢出”其他键。如果连“踢出”都失败了，它会采取最后的手段：为当前键增加一个新的哈希函数，赋予它一个全新的位置选择，然后再次尝试。一旦找到位置，就将键的索引 vector_idx 记录到目标桶中。

3.6 MakeSpaceForKey()：布谷鸟“踢出”算法的精髓

这是 Cuckoo Hash 最核心、最有趣的算法，用于在没有空位时，通过移动现有元素来创造空间。

代码 (table/cuckoo/cuckoo_table_builder.cc):

bool CuckooTableBuilder::MakeSpaceForKey(
    /* ... */) {
  struct CuckooNode { /* ... */ };
  std::vector<CuckooNode> tree;
  // ... BFS 搜索逻辑 ...
  while (!null_found && curr_pos < tree.size()) {
    // ... 扩展节点，寻找空位 ...
  }

  if (null_found) {
    // 路径找到，反向遍历 tree 进行“踢出”
    uint32_t bucket_to_replace_pos = static_cast<uint32_t>(tree.size()) - 1;
    while (bucket_to_replace_pos >= num_hash_func_) {
      CuckooNode& curr_node = tree[bucket_to_replace_pos];
      (*buckets)[static_cast<size_t>(curr_node.bucket_id)] =
          (*buckets)[static_cast<size_t>(tree[curr_node.parent_pos].bucket_id)];
      bucket_to_replace_pos = curr_node.parent_pos;
    }
    *bucket_id = tree[bucket_to_replace_pos].bucket_id;
  }
  return null_found;
}

3.6.1 BFS 搜索树的构建与可视化

该函数通过广度优先搜索（BFS）寻找一条从某个被占用的桶到某个空桶的路径。它使用一个 std::vector<CuckooNode> tree 来模拟搜索树。树的根节点是当前要插入的键的所有候选位置。然后，它逐层扩展：对于树中的一个节点（代表一个被占用的桶），它会查找桶中那个键的备用位置，并将这些备用位置作为子节点加入树中，直到找到一个空桶为止。

3.6.2 “踢出”路径的查找与替换逻辑

一旦 BFS 找到一个空桶，if (null_found) 块内的逻辑就会被触发。这里的 while 循环是实现“踢出”操作的关键。它从找到的空桶节点开始，沿着 parent_pos 指针反向回溯到根节点。在回溯的每一步，它都执行 (*buckets)[child_bucket] = (*buckets)[parent_bucket]; 操作，即将父节点桶中的内容（键）移动到子节点桶的位置。这个连锁反应最终会使路径的起点（即最初要插入的键的某个候选位置）变为空，从而为新键腾出空间。

假设我们有一个大小为 8 的哈希表 (hash_table_size_ = 8), 并且已经存放了一些键. 我们用 K1, K2 等来代表不同的键.

  • 哈希表当前状态:

    Bucket Index:01234567
    Content:K1K2K3

  • 键的哈希位置: 假设我们有2个哈希函数 h1 和 h2.

    • h1(K1)=1, h2(K1)=5 (K1 占用了它的主位置 1)
    • h1(K2)=2, h2(K2)=1 (K2 占用了它的主位置 2, 它的备用位置 1 已被 K1 占用)
    • h1(K3)=5, h2(K3)=7 (K3 占用了它的主位置 5, 它的备用位置 7 是空的)

  • 当前任务: 我们现在要插入一个新键 K_new, 不幸的是, 它的哈希位置是 h1(K_new)=2 和 h2(K_new)=5. 这两个位置都已经被占用了.

    此时, MakeHashTable 发现无法直接放置 K_new, 于是调用 MakeSpaceForKey.

  1. BFS 的 tree 是什么样的?

    tree 是一个用 std::vector 实现的扁平化的树, 节点之间通过 parent_pos (父节点在 vector 中的索引) 关联.

    CuckooNode 结构:

    struct CuckooNode {
  uint64_t bucket_id; // 桶的 ID, 即在哈希表中的索引
  uint32_t depth;     // 在 BFS 树中的深度
  uint32_t parent_pos;// 父节点在 tree 向量中的索引
  // ...
};

    MakeSpaceForKey 开始执行:

  2. Level 0 (根节点):
    MakeSpaceForKey 首先将 K_new 的所有候选位置 (2 和 5) 作为根节点放入 tree.

    // tree 向量的内容:
[
  // index 0
  { bucket_id: 2, depth: 0, parent_pos: 0 },
 // index 1
  { bucket_id: 5, depth: 0, parent_pos: 0 }
]

  3. Level 1 (扩展子节点):
    BFS 从 tree 的头部 (index 0) 开始处理.

    • 处理 tree[0] (bucket 2):

      • 桶 2 中存放的是 K2.

      • K2 的备用位置是 h2(K2)=1.

      • 将备用位置 1 作为一个新的 CuckooNode 加入 tree, 它的父节点是 tree[0].

        // tree 向量的内容:
[
  { bucket_id: 2, depth: 0, parent_pos: 0 }, // index 0
  { bucket_id: 5, depth: 0, parent_pos: 0 }, // index 1
  // 新增节点, 父节点索引为 0
  { bucket_id: 1, depth: 1, parent_pos: 0 }  // index 2
]
    • 处理 tree[1] (bucket 5):

      • 桶 5 中存放的是 K3.

      • K3 的备用位置是 h2(K3)=7.

      • 将备用位置 7 作为一个新的 CuckooNode 加入 tree, 它的父节点是 tree[1].

        // tree 向量的内容:
[
  { bucket_id: 2, depth: 0, parent_pos: 0 }, // index 0
  { bucket_id: 5, depth: 0, parent_pos: 0 }, // index 1
  { bucket_id: 1, depth: 1, parent_pos: 0 }, // index 2
  // 新增节点, 父节点索引为 1
  { bucket_id: 7, depth: 1, parent_pos: 1 }  // index 3
]
    • 发现空位! 当把 bucket_id: 7 这个节点加入 tree 时, 代码会检查哈希表中 buckets[7] 的状态. 它发现 buckets[7] 是空的 (vector_idx == kMaxVectorIdx). BFS 搜索成功!

    BFS tree 的最终形态:
    这个 tree 向量在逻辑上代表了这样一棵搜索树:

        (K_new)
       /       \
(Level 0)  Bucket 2 (K2)   Bucket 5 (K3)
             |               |
(Level 1)  Bucket 1 (K1)   Bucket 7 (EMPTY)  <-- 成功找到路径!

我们找到了一条可行的”踢出路径”: 将 K3 从桶 5 移动到桶 7, 就能空出桶 5 给 K_new.

四、 CuckooTableReader：快如闪电的点查找

与 Builder 的复杂性形成鲜明对比，Reader 的设计极其简洁高效。所有复杂的布局工作都已在写入时完成，Reader 的任务就是以最快的方式利用这个预设好的布局。

4.1 Reader 的核心思想：mmap 与直接地址计算

CuckooTableReader 的高性能秘诀主要有两点：

  1. 内存映射 (mmap): Reader 通过 mmap 系统调用将整个 SST 文件映射到进程的虚拟地址空间。这避免了传统的 read() 系统调用带来的内核态/用户态切换和数据拷贝开销。后续的所有文件访问都变成了直接的内存访问，速度极快（仅在首次访问时会触发缺页中断）。
  2. 直接地址计算: 它不依赖于任何索引块。对于一个给定的键，它能通过哈希函数直接计算出键在文件（即内存）中的几个潜在位置。查找过程就是几次哈希计算和内存访问，时间复杂度接近 O(1)。

4.2 构造函数：加载元数据与内存映射

Reader 的构造函数负责读取 Builder 留下的“地图”，并完成内存映射。

代码 (table/cuckoo/cuckoo_table_reader.cc):

CuckooTableReader::CuckooTableReader(
    const ImmutableOptions& ioptions,
    std::unique_ptr<RandomAccessFileReader>&& file, uint64_t file_size,
    /* ... */) {
  if (!ioptions.allow_mmap_reads) {
    status_ = Status::InvalidArgument("File is not mmaped");
    return;
  }
  
  // 读取并解析 Table Properties
  status_ =
      ReadTableProperties(file_.get(), file_size, kCuckooTableMagicNumber,
                          ioptions, read_options, &props);
  // ...

  // 从 Properties 中恢复所有布局参数
  // ... find and assign num_hash_func_, unused_key_, key_length_, etc. ...
  bucket_length_ = key_length_ + value_length_;

  // 将整个文件映射到内存
  status_ = file_->Read(IOOptions(), 0, static_cast<size_t>(file_size),
                        &file_data_, nullptr, nullptr);
}

构造函数首先检查 mmap 是否被允许。然后，它通过 ReadTableProperties 从文件尾部读取元数据，恢复 Builder 保存的所有布局参数，如哈希函数数量、键值长度、空桶占位符 unused_key_ 等。最后，它调用 file_->Read()（在 mmap 模式下）将整个文件内容映射到 file_data_ 这个 Slice 中，为后续的查找做好了准备。

4.3 Get() 方法：从哈希到内存地址的直接转换

Get() 方法是 Reader 的精髓所在，完美体现了其设计思想。

代码 (table/cuckoo/cuckoo_table_reader.cc):

Status CuckooTableReader::Get(const ReadOptions&, const Slice& key, GetContext* get_context, ... ) {
  Slice user_key = ExtractUserKey(key);
  for (uint32_t hash_cnt = 0; hash_cnt < num_hash_func_; ++hash_cnt) {
    uint64_t offset =
        bucket_length_ * CuckooHash(user_key, hash_cnt, ...);
    const char* bucket = &file_data_.data()[offset];

    for (uint32_t block_idx = 0; block_idx < cuckoo_block_size_; ++block_idx, bucket += bucket_length_) {
      if (ucomp_->Equal(Slice(unused_key_.data(), user_key.size()),
                        Slice(bucket, user_key.size()))) {
        return Status::OK();
      }
      if (ucomp_->Equal(user_key, Slice(bucket, user_key.size()))) {
        Slice value(bucket + key_length_, value_length_);
        // ... 保存 value 到 get_context ...
        return Status::OK();
      }
    }
  }
  return Status::OK();
}

查找过程非常直接：

  1. 对给定的 user_key，遍历所有哈希函数。
  2. 对于每个哈希函数，通过 CuckooHash(...) 计算出哈希值，再乘以 bucket_length_，得到在 file_data_ 中的**精确字节偏移量 offset**。
  3. 从该 offset 开始，在线性探测 cuckoo_block_size_ 个桶。
  4. 在每个桶中，首先与 unused_key_ 比较，如果是空桶，则说明键不在此处。然后与 user_key 比较，如果匹配，则从 bucket + key_length_ 处提取值并返回。
  5. 如果所有哈希函数对应的所有 Cuckoo Block 都检查完毕仍未找到，则键不存在。

4.4 Prepare() 方法：利用 CPU 缓存预取

这是一个可选的性能优化，用于在 Get() 之前“预热”CPU缓存。

代码 (table/cuckoo/cuckoo_table_reader.cc):

void CuckooTableReader::Prepare(const Slice& key) {
  // ...
  uint64_t addr = /* ... calculate address of first hash location ... */;
  uint64_t end_addr = addr + cuckoo_block_bytes_minus_one_;
  for (addr &= CACHE_LINE_MASK; addr < end_addr; addr += CACHE_LINE_SIZE) {
    PREFETCH(reinterpret_cast<const char*>(addr), 0, 3);
  }
}

该方法会计算出键的第一个哈希位置对应的内存地址，然后通过 PREFETCH 宏（通常是编译器的 __builtin_prefetch）指示 CPU 提前将这块内存区域加载到高速缓存中，从而降低后续 Get() 时的内存访问延迟。

五、 CuckooTableIterator：范围扫描的代价

Cuckoo Table 为了极致的点查找性能，牺牲了范围扫描的能力。其迭代器的实现方式清晰地反映了这一点。

5.1 迭代器的核心机制：一次性全量排序

由于 SST 文件中的键是按哈希值散乱分布的，为了提供 Iterator 所要求的有序遍历功能，CuckooTableIterator 不得不采取一种直接但代价高昂的策略：在首次使用时，读取所有键并进行一次完整的排序。

5.2 InitIfNeeded()：昂贵的初始化

迭代器的所有魔法都发生在 InitIfNeeded() 中，该方法在 Seek 或 SeekToFirst 等导航方法首次被调用时执行。

代码 (table/cuckoo/cuckoo_table_reader.cc):

void CuckooTableIterator::InitIfNeeded() {
  if (initialized_) {
    return;
  }
  // ...
  const char* bucket = reader_->file_data_.data();
  // 1. 遍历所有桶, 收集所有非空桶的 ID
  for (uint32_t bucket_id = 0; bucket_id < num_buckets; ++bucket_id) {
    if (Slice(bucket, reader_->key_length_) != Slice(reader_->unused_key_)) {
      sorted_bucket_ids_.push_back(bucket_id);
    }
    bucket += reader_->bucket_length_;
  }
  
  // 2. 对所有非空桶的 ID, 按照其对应的 Key 进行排序
  std::sort(sorted_bucket_ids_.begin(), sorted_bucket_ids_.end(),
            bucket_comparator_);
  // ...
}
  1. 收集: 代码首先遍历整个 mmap 的文件内容，检查每一个桶。如果桶的内容不是 unused_key_，就将其 bucket_id 添加到一个 std::vector<uint32_t> sorted_bucket_ids_ 中。
  2. 排序: 这是最昂贵的操作。它调用 std::sort，并传入一个自定义的 BucketComparator，对 sorted_bucket_ids_ 向量进行排序。排序的依据不是桶ID的数值，而是ID对应桶中的键。

5.3 BucketComparator：如何比较“桶ID”

这个自定义比较器是实现排序的关键。

代码 (table/cuckoo/cuckoo_table_reader.cc):

struct BucketComparator {
    // ...
    bool operator()(const uint32_t first, const uint32_t second) const {
      const char* first_bucket = /* ... get key address from first id ... */;
      const char* second_bucket = /* ... get key address from second id ... */;
      return ucomp_->Compare(Slice(first_bucket, user_key_len_),
                             Slice(second_bucket, user_key_len_)) < 0;
    }
    // ...
  };

它的 operator() 接收两个桶ID，然后根据ID从 file_data_ 中找到对应的键，最后使用用户提供的 Comparator (ucomp_) 来比较这两个键，从而决定桶ID的顺序。

5.4 Seek/Next/Prev：基于已排序索引的快速导航

一旦 InitIfNeeded() 完成了昂贵的排序，迭代器的所有导航操作就变得非常轻快。

代码 (table/cuckoo/cuckoo_table_reader.cc):

void CuckooTableIterator::Seek(const Slice& target) {
  InitIfNeeded();
  // ...
  auto seek_it =
      std::lower_bound(sorted_bucket_ids_.begin(), sorted_bucket_ids_.end(),
                       kInvalidIndex, seek_comparator);
  // ...
}

void CuckooTableIterator::Next() { ++curr_key_idx_; /* ... */ }
void CuckooTableIterator::Prev() { --curr_key_idx_; /* ... */ }
  • Next() 和 Prev() 只是简单地移动 sorted_bucket_ids_ 向量的下标 curr_key_idx_。
  • Seek() 则是在这个已排序的ID向量上执行高效的二分查找 (std::lower_bound)。
  • 这些操作都只涉及整数向量的操作，因此一旦初始化完成，迭代本身的速度非常快。

六、 总结：Cuckoo Table 的设计哲学与权衡

通过对 Factory、Builder 和 Reader 的深入分析，我们可以清晰地看到 Cuckoo Table 的设计哲学：通过在写入时承担更多的复杂性，并施加更严格的约束，来换取读取时极致的性能。

  • 优点:

    • 无与伦比的点查找性能，这得益于其 mmap 友好的扁平文件结构和 O(1) 复杂度的直接哈希地址计算。

  • 代价与权衡:

    • 严格的约束: 必须使用定长的键和值。
    • 复杂的写入路径: Builder 需要处理复杂的哈希冲突和“踢出”逻辑，构建过程可能比 BlockBasedTable 更慢，CPU消耗也更高。
    • 昂贵的范围扫描: Iterator 的首次使用需要进行全量扫描和排序，对于范围查询的场景是完全不适合的。

总而言之，Cuckoo Table 是 RocksDB 工具箱中一件锋利的“专科武器”，而非“万金油”。它完美地诠释了在高性能存储系统设计中，“没有最好的，只有最合适的”这一黄金法则。当你的业务场景与它的设计目标高度契合时，它能带来惊人的性能提升。