C++从零开始实现LSM-Tree-KV存储-14-布隆过滤器

ToniXWD

2025-03-15

项目

C++, KV存储

这节课针对之前实现的LSM-Tree设计布隆过滤器来减少无效的磁盘IO

代码仓库：ToniXWD/toni-lsm: A KV storage engine based on LSM Tree, supporting Redis RESP

欢迎点个Star

1 布隆过滤器简介

1.1 原理介绍

布隆过滤器是一种 probabilistic 数据结构，用于判断一个元素是否在集合中。它通过一个概率的方式来判断，即使集合中存在一个元素，但是布隆过滤器也依然可以判断出来。

布隆过滤器的核心思想是使用一个位数组和多个哈希函数来表示一个集合。它的特点是可以高效地判断某个元素是否“可能存在”或“确定不存在”，但它有一定的误判率，即可能会误判某个不存在的元素为“可能存在”。其实现方式如下:

初始化位数组：布隆过滤器使用一个固定大小的位数组（如长度为 m），所有位初始化为 0。
插入元素时在位数组记录：当插入一个元素时，使用 k 个独立的哈希函数对该元素进行哈希运算，得到 k 个哈希值（每个值对应位数组的索引）。将这些索引位置的位设置为 1。
查询元素时在位数组校验：当查询一个元素是否存在时，同样使用 k 个哈希函数对该元素进行哈希运算，得到 k 个哈希值。如果这些哈希值对应的位数组中的所有位都为 1，则判断该元素“可能存在”；如果有任意一位为 0，则判断该元素“确定不存在”。

特点

优点：布隆过滤器的空间效率和查询效率非常高，适合处理大规模数据。
缺点：存在一定的误判率（即可能会误判不存在的元素为“可能存在”），并且无法删除元素（删除可能会影响其他元素的判断）。

1.2 案例介绍

下面我们通过一个案例来看看布隆过滤器的运行机制:

bloom-example

案例图片来源自 https://blog.csdn.net/Zyw907155124/article/details/135556557, 侵删

在新增一个记录时(put/insert等), 通过预定义数量(案例图片中是2个)的哈希函数对key进行哈希, 将哈希值对位数组的长度取模, 将结果作为索引, 将索引位置的位设置为1
在查询时(get), 通过预定义数量(案例图片中是2个)的哈希函数对key进行哈希, 将哈希值对位数组的长度取模, 将结果作为索引, 如果索引位置的位为1, 则认为该key可能存在, 否则认为该key不存在

2 LSM-Tree中的布隆过滤器

尽管我们之前为整个LSM-Tree设计了bock cache, 但面对大量不存在于LSM-Tree中的key时, bock cache会频繁的进行磁盘IO, 这将导致LSM-Tree的性能降低。

这里的原理类似后端八股文中Redis常问的缓存击穿、缓存穿透、缓存雪崩，而设置布隆过滤器就是一个景点的解决方案，背过八股的同学们应该会很熟悉。

因此，我们可以在编码SST文件时，为每个SST文件都设计一个bloom filter, 在其中记录整个SST中的所有key, 并将其持久化到文件系统中, 在读取文件时, 相应的布隆过滤器部分也需要被解码并加载到内存中。这样当查询时, 我们只需要判断key是否存在于bloom filter中, 如果不存在, 则认为该key不存在于LSM-Tree, 否则, 我们需要继续在LSM-Tree中查找。这样以来, 我们就可以避免大量的无效访问。

3 布隆过滤器代码实现

3.1 设计思路

现在我们就可以为我们的LSM-Tree设计一个布隆过滤器了，我们需要完成如下的功能：

能够在初始化时通过假阳性率和键的数量来确定哈希函数的数量和位数组的长度
支持编码与解码

对于通过假阳性率和键的数量来确定哈希函数的数量和位数组的长度, 我们可以按照指定的公式求取, 但问题在于我们是不知道哈希函数的数量的, 难道我们要手动写很多个哈希函数吗?

我们可以采用这样的方案: 只写2个哈希函数, 通过对这两个哈希函数的线性组合构造新的哈希函数

3.2 代码实现

3.2.1 头文件

class BloomFilter {
public:
  // 构造函数，初始化布隆过滤器
  // expected_elements: 预期插入的元素数量
  // false_positive_rate: 允许的假阳性率
  BloomFilter();
  BloomFilter(size_t expected_elements, double false_positive_rate);

  BloomFilter(size_t expected_elements, double false_positive_rate,
              size_t num_bits);

  void add(const std::string &key);

  // 如果key可能存在于布隆过滤器中，返回true；否则返回false
  bool possibly_contains(const std::string &key) const;

  // 清空布隆过滤器
  void clear();

  std::vector<uint8_t> encode();
  static BloomFilter decode(const std::vector<uint8_t> &data);

private:
  // 布隆过滤器的位数组大小
  size_t expected_elements_;
  // 允许的假阳性率
  double false_positive_rate_;
  size_t num_bits_;
  // 哈希函数的数量
  size_t num_hashes_;
  // 布隆过滤器的位数组
  std::vector<bool> bits_;

private:
  // 第一个哈希函数
  // 返回值: 哈希值
  size_t hash1(const std::string &key) const;

  // 第二个哈希函数
  // 返回值: 哈希值
  size_t hash2(const std::string &key) const;

  size_t hash(const std::string &key, size_t idx) const;
};

3.2.2 构造函数

构造函数就是计算需要的哈希函数数量和位数组大小:

BloomFilter::BloomFilter(){};

// 构造函数，初始化布隆过滤器
// expected_elements: 预期插入的元素数量
// false_positive_rate: 允许的假阳性率
BloomFilter::BloomFilter(size_t expected_elements, double false_positive_rate)
    : expected_elements_(expected_elements),
      false_positive_rate_(false_positive_rate) {
  // 计算布隆过滤器的位数组大小
  double m = -static_cast<double>(expected_elements) *
             std::log(false_positive_rate) / std::pow(std::log(2), 2);

  num_bits_ = static_cast<size_t>(std::ceil(m));

  // 计算哈希函数的数量
  num_hashes_ =
      static_cast<size_t>(std::ceil(m / expected_elements * std::log(2)));

  // 初始化位数组
  bits_.resize(num_bits_, false);
}

构造函数中, 假阳性率、键值对数量、哈希函数数量、位数组数量间的关系可以通过下面的公式计算：

1 2	double m = -static_cast<double>(expected_elements) * std::log(false_positive_rate) / std::pow(std::log(2), 2);

也就是:

bloom-compute

这里的公式推导不介绍了, 就是个数学问题

3.2.3 添加记录

添加记录时, 我们根据哈希函数的序号, 使用2个不同的哈希函数的线性组合来构造一个新的哈希函数计算位数组的索引:

void BloomFilter::add(const std::string &key) {
  // 对每个哈希函数计算哈希值，并将对应位置的位设置为true
  for (size_t i = 0; i < num_hashes_; ++i) {
    bits_[hash(key, i)] = true;
  }
}

size_t BloomFilter::hash1(const std::string &key) const {
  std::hash<std::string> hasher;
  return hasher(key);
}

size_t BloomFilter::hash2(const std::string &key) const {
  std::hash<std::string> hasher;
  return hasher(key + "salt");
}

size_t BloomFilter::hash(const std::string &key, size_t idx) const {
  auto h1 = hash1(key);
  auto h2 = hash2(key);
  return (h1 + idx * h2) % num_bits_;
}

3.2.4 判断key否存在

布隆过滤器检查key是否存在时, 我们只需要判断哈希函数的线性组合的计算结果对应的位数组中的位是否都为true即可:

//  如果key可能存在于布隆过滤器中，返回true；否则返回false
bool BloomFilter::possibly_contains(const std::string &key) const {
  // 对每个哈希函数计算哈希值，检查对应位置的位是否都为true
  for (size_t i = 0; i < num_hashes_; ++i) {
    auto bit_idx = hash(key, i);
    if (!bits_[bit_idx]) {
      return false;
    }
  }
  return true;
}

3.2.5 编解码

这里编解码在逻辑上也非常简单, 但在C++语法上有一个坑需要注意:

CPP的std::vector<bool>是以bit为基础操作的, 也就是说假设有下面的代码:

1 2	std::vector<bool> bits(8, false); bits[0] = true;

这里的[0]表示对第一个bit进行操作, 而不是对第一个byte进行操作!!!

因此, 这里编解码时, 需要额外确保字节的对其:

// 编码布隆过滤器为 std::vector<uint8_t>
std::vector<uint8_t> BloomFilter::encode() {
  std::vector<uint8_t> data;

  // 编码 expected_elements_
  data.insert(data.end(),
              reinterpret_cast<const uint8_t *>(&expected_elements_),
              reinterpret_cast<const uint8_t *>(&expected_elements_) +
                  sizeof(expected_elements_));

  // 编码 false_positive_rate_
  data.insert(data.end(),
              reinterpret_cast<const uint8_t *>(&false_positive_rate_),
              reinterpret_cast<const uint8_t *>(&false_positive_rate_) +
                  sizeof(false_positive_rate_));

  // 编码 num_bits_
  data.insert(data.end(), reinterpret_cast<const uint8_t *>(&num_bits_),
              reinterpret_cast<const uint8_t *>(&num_bits_) +
                  sizeof(num_bits_));

  // 编码 num_hashes_
  data.insert(data.end(), reinterpret_cast<const uint8_t *>(&num_hashes_),
              reinterpret_cast<const uint8_t *>(&num_hashes_) +
                  sizeof(num_hashes_));

  // 编码 bits_
  size_t num_bytes = (num_bits_ + 7) / 8; // 向上取整以对齐字节
  for (size_t i = 0; i < num_bytes; ++i) {
    uint8_t byte = 0;
    for (size_t j = 0; j < 8; ++j) {
      if (i * 8 + j < num_bits_) {
        byte |= (bits_[i * 8 + j] << j);
      }
    }
    data.push_back(byte);
  }

  return data;
}

// 从 std::vector<uint8_t> 解码布隆过滤器
BloomFilter BloomFilter::decode(const std::vector<uint8_t> &data) {
  size_t index = 0;

  // 解码 expected_elements_
  size_t expected_elements;
  std::memcpy(&expected_elements, &data[index], sizeof(expected_elements));
  index += sizeof(expected_elements);

  // 解码 false_positive_rate_
  double false_positive_rate;
  std::memcpy(&false_positive_rate, &data[index], sizeof(false_positive_rate));
  index += sizeof(false_positive_rate);

  // 解码 num_bits_
  size_t num_bits;
  std::memcpy(&num_bits, &data[index], sizeof(num_bits));
  index += sizeof(num_bits);

  // 解码 num_hashes_
  size_t num_hashes;
  std::memcpy(&num_hashes, &data[index], sizeof(num_hashes));
  index += sizeof(num_hashes);

  // 解码 bits_
  std::vector<bool> bits(num_bits, false);
  size_t num_bytes = (num_bits + 7) / 8;
  for (size_t i = 0; i < num_bytes; ++i) {
    uint8_t byte = data[index++];
    for (size_t j = 0; j < 8; ++j) {
      if (i * 8 + j < num_bits) {
        bits[i * 8 + j] = (byte >> j) & 1;
      }
    }
  }

  BloomFilter bf;
  bf.expected_elements_ = expected_elements;
  bf.false_positive_rate_ = false_positive_rate;
  bf.num_bits_ = num_bits;
  bf.num_hashes_ = num_hashes;
  bf.bits_ = bits;

  return bf;
}

4 LSM-Tree引入布隆过滤器

4.1 布隆过滤器的编码

布隆过滤器是编码到sst文件中的, 我们需要更新sst的编码格式如下:

sst-with-bloom

我们在Block的元数据块后面加入了布隆过滤器的编码部分, 同时将其偏移量也记录在了Extra Information中。

编解码格式变化了, 相应的函数也需要更新, 但这里就不展开了, 毕竟流程类似的, 可以看仓库源码

我们只需要在编码sst时, 每次add时, 添加对这个key的记录就可以了:

void SSTBuilder::add(const std::string &key, const std::string &value) {
  // 记录第一个key
  if (first_key.empty()) {
    first_key = key;
  }

  // 在 布隆过滤器 中添加key
  if (bloom_filter != nullptr) {
    bloom_filter->add(key);
  }

  if (block.add_entry(key, value)) {
    // block 满足容量限制, 插入成功
    last_key = key;
    return;
  }

  finish_block(); // 将当前 block 写入

  block.add_entry(key, value);
  first_key = key;
  last_key = key; // 更新最后一个key
}

4.2 布隆过滤器的解码

在open一个sst时, 将布隆过滤器的部分解码并初始化:

std::shared_ptr<SST> SST::open(size_t sst_id, FileObj file,
                               std::shared_ptr<BlockCache> block_cache) {
  ...

  // 2. 读取 bloom filter
  if (sst->bloom_offset + 2 * sizeof(uint32_t) < file_size) {
    // 布隆过滤器偏移量 + 2*uint32_t 的大小小于文件大小
    // 表示存在布隆过滤器
    uint32_t bloom_size = file_size - sst->bloom_offset - sizeof(uint32_t) * 2;
    auto bloom_bytes = sst->file.read_to_slice(sst->bloom_offset, bloom_size);

    auto bloom = BloomFilter::decode(bloom_bytes);
    sst->bloom_filter = std::make_shared<BloomFilter>(std::move(bloom));
  }

 ...

  return sst;
}

4.3 布隆过滤器的使用

同时, 在查询时需要用布隆过滤器过滤无效请求:

size_t SST::find_block_idx(const std::string &key) {
  // 先在布隆过滤器判断key是否存在
  if (bloom_filter != nullptr && !bloom_filter->possibly_contains(key)) {
    return -1;
  }

  // 二分查找
  ...
}