# 算法
## 算法描述
- https://en.wikipedia.org/wiki/Bloom_filter
- 数据结构：bit array（m 个 bits），初始为 0
- 
- Set a key：
- 使用 k 个 hash 函数，对 key 计算 hash 值
- 针对每个 hash 值 h ，设置 bit array 的 h % m 位置为 1
- $bit\_array[h\mod m]=1$
- Probe a key：
- 使用同样的 k 个 hash 函数，查看 bit array 的 k 个对应位置是否全部为 1
## 公式
- 最优 hash 函数个数 k
- $k=\frac{m}{n} \ln 2$
- **m**: bit array的位数
- **n**: key的个数
- 即只取决于 bits_per_key 参数，约等于 $bits\_per\_key \times0.69$
- false postitives 的概率
- 
---------
# Rocksdb 实现
- 术语与算法的对应：
- num_probes: k （hash 函数的个数）
- hash 函数：32-bit hash，k 个 hash 值的计算
- 第一个hash 值：完整 key 经过 XXPH3 计算出 64位 hash 值
- 后续 k - 1 hash 值的计算：上一个 hash 值乘以黄金比例
- bits_per_key：m / n
## FilterPolicy
- include/rocksdb/filter_policy.h
- 入口类，表示不同的 filter 策略，内置 `BloomFilterPolcy` 和 `RibbonFilterPolicy`
- 核心方法：
- GetBuilderWithContext：返回 `FilterBitsBuilder` ，用于写入时构建 filter blocks
- GetFilterBitsReader：返回 `FilterBitsReader`，用于读取 filter blocks
## Bloom filter
- filter block 的格式
```
0 +-----------------------------------+
| Raw Bloom filter data |
| ... |
len +-----------------------------------+
| char{-1} byte -> new Bloom filter |
len+1 +-----------------------------------+
| byte for subimplementation |
| 0: FastLocalBloom |
| other: reserved |
len+2 +-----------------------------------+
| byte for block_and_probes |
| 0 in top 3 bits -> 6 -> 64-byte |
| reserved: |
| 1 in top 3 bits -> 7 -> 128-byte|
| 2 in top 3 bits -> 8 -> 256-byte|
| ... |
| num_probes in bottom 5 bits, |
| except 0 and 31 reserved |
len+3 +-----------------------------------+
| two bytes reserved |
| possibly for hash seed |
len_with_meta +-----------------------------------+
```
- 末尾为元数据（5字节）
- 包含 filter 的类型、num_probes 参数
## FastLocalBloomImpl
- 基础实现，方法类（无数据成员）
- util/bloom_impl.h
- **基本结构**：
- 整个 filter data 由多个 cacheline 组成，一个 cacheline 一个 bloom 结构
- 先计算 key 的 hash 值（64位），使用 hash 来构建
- key 的 64位 hash 值拆分为==两个==部分：
- 低 32 位 h1 用于定位 cacheline
- 高32 位 h2 作为 bloom filter hash 函数的输入
- **EstimatedFpRate**：估算 false postive rate
- 算法：[http://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf](http://www.ccs.neu.edu/home/pete/pub/bloom-filters-verification.pdf)
- 相比朴素算法，需要考虑 cacheline 冲突
- **ChooseNumProbes**: 根据 millibits_per_key 挑选 hash 函数个数
- **AddHash**：添加 key（ 的 hash 值）到 bloom filter
- 该函数只作演示，实际的添加分为两步：
- **PrepareHash**:
- prefetch bit_array 的目标 cacheline
- 使用了 [FastRange](https://github.com/lemire/fastrange)来快速定位 cacheline
- **AddHashPrepared**：
- 使用 num_probes 个 hash 函数设置 cacheline 的 bit 位
- **HashMayMatch** / **HashMayMatchPrepared**
- 检测 key 是否存在
- 计算 num_probes 个 hash 函数，依次查看对应 bit 是否为 0 ，为 0 返回 false
## FastLocalBloomBitsBuilder
^34417e
- builder 类，写入时用于构建 bloom filter 数据
- table/block_based/filter_policy.cc
- 关键数据成员：
- **`hash_entries_info_`**: `HashEntriesInfo`，
- 主要是 `std::deque<uint64_t> entries`, 保存 key 的 hash 值
- 关键方法：
- **AddKey**：参数 `Slice& key`，添加一个 Key 到 bloom filter
- 继承自 `XXPH3FilterBitsBuilder`
- 实际上是将 key 的 hash值先缓存到 `hash_entries_info_`
- 每次 Add 的 key 是递增的，并且对 hash 进行去除
- 只记录跟 last hash 不同的
- 尤其是使用 prefix bloom filter 后，重复概率会很高
- **Finish**: 分配内存，使用 FastLocalBloomImpl 构建 filter data
- 优化
- ROCKSDB_MALLOC_USABLE_SIZE
- malloc 会分配比请求更多的内存，使用实际分配到的，来减少内碎片节省空间。
## FastLocalBloomBitsReader
- reader 类，读取如 Get 时会调用到。
- 核心成员：
- **`data_`**：`data_`，filter data
- **`num_probes_`**：`num_probes_`
- **MayMatch**：
- 调用 FastLocalBloomImpl 检测 key 是否可能存在
------
# TODO
- [ ] 阅读引用论文，理解 IndependentProbabilitySum 的算法
- [ ] cache_res_mgr_