跳转至

Parquet 布隆过滤器 (Bloom Filter)

问题描述

在当前格式下，列统计信息和字典可以用于谓词下推（Predicate Pushdown）。统计信息包含最小值和最大值，可用于筛选出不在范围内的值。字典更具体，读取器可以筛选出介于最小值和最大值之间但不在字典中的值。然而，当数据的不同值过多时，写入器有时会选择不使用字典，因为字典会占用额外的存储空间。这使得某些高基数（high cardinality）的列，虽然其最小值和最大值相距甚远，但无法受益于谓词下推。

布隆过滤器（Bloom Filter） 是一种紧凑的数据结构，用于近似存储一个集合。它可以回答成员查询，返回 "绝对不存在" 或 "可能存在" 的结果，其中假阳性（false positive）的概率可以在初始化过滤器时配置。布隆过滤器不会产生假阴性（false negatives）。

由于布隆过滤器比字典小得多，因此即使在高基数列中，或者存储空间受限的情况下，也可以用于谓词下推。

目标

  • 在高基数列上启用谓词下推，同时使用比字典更少的空间。
  • 当查询未附加布隆过滤器的列或执行非选择性查询时，不引入额外的 I/O 开销。

技术实现

本节介绍 分块布隆过滤器（Split Block Bloom Filters），这是 Parquet 目前支持的唯一布隆过滤器实现。

基本概念

一个 "块（block）" 是分块布隆过滤器的基本组成部分。每个块包含 256 比特，分为 8 个连续的 32 比特字（word）。每个字被视为一个位数组，每个位可以是 "已设置（set）" 或 "未设置（not set）"。

  • 初始化：当一个块初始化时，所有 8 个字的所有位都未设置。
  • 操作：
    • block_insert(x): 插入值 x，修改块。
    • block_check(x): 检查值 x 是否已插入，返回布尔值。

block_check(x) 的逻辑是：如果 block_insert(x) 之前被调用过，则返回 true，否则以高概率返回 false。

位设置逻辑

每个块的 block_insert 和 block_check 依赖两个重要组件： 1. salt 数组（8 个奇数常量）： c unsigned int32 salt[8] = {0x47b6137bU, 0x44974d91U, 0x8824ad5bU, 0xa2b7289dU, 0x705495c7U, 0x2df1424bU, 0x9efc4947U, 0x5c6bfb31U}; 2. mask 方法：将 x 计算为一个块，其中每个字的某个位被设置。 c block mask(unsigned int32 x) { block result; for (i in [0..7]) { unsigned int32 y = x * salt[i]; result.getWord(i).setBit(y >> 27); } return result; } - mask 计算 x * salt[i] 并右移 27 位（>> 27），得到 0 到 31 之间的整数，然后在相应字的该位上设置 1。

插入和检查

  • 插入（block_insert） c void block_insert(block b, unsigned int32 x) { block masked = mask(x); for (i in [0..7]) { for (j in [0..31]) { if (masked.getWord(i).isSet(j)) { b.getWord(i).setBit(j); } } } }
  • 检查（block_check） c boolean block_check(block b, unsigned int32 x) { block masked = mask(x); for (i in [0..7]) { for (j in [0..31]) { if (masked.getWord(i).isSet(j) && !b.getWord(i).isSet(j)) { return false; } } } return true; }

分块布隆过滤器（SBBF）

  • 结构：由 z 个块组成，其中 z ≥ 1 且 z < 2^31。
  • 初始化：每个块都初始化为全零（所有位未设置）。
  • 操作：
    • filter_insert(x): 选择一个块并调用 block_insert(x)。
    • filter_check(x): 选择一个块并调用 block_check(x)。

块选择策略

为了避免使用慢速的 取模运算（modulo），采用以下方法选择块：

unsigned int64 i = ((x >> 32) * z) >> 32;
  • x >> 32 取 x 的高 32 位作为索引来源。
  • 乘以 z 并右移 32 位，从而映射到 [0, z-1] 之间的整数。

布隆过滤器大小计算

布隆过滤器的 check 操作可能产生 假阳性（false positive），即 返回 true 但实际上该值未被插入。假阳性的概率受以下因素影响： - 比特位数量 / 插入哈希值数量 比例： - 1024 个块，26214 个哈希值，假阳性率 ≈ 1.26%。 - 1024 个块，52428 个哈希值，假阳性率 ≈ 18%。 - 1024 个块，13107 个哈希值，假阳性率 ≈ 0.04%。

比特位 / 插入值比率 假阳性概率
6.0 10%
10.5 1%
16.9 0.1%
26.4 0.01%
41.0 0.001%

文件格式

布隆过滤器仅适用于单个列块（Column Chunk），其数据包括： - 布隆过滤器头部（Header）：存储位集大小（字节数）。 - 布隆过滤器位集（Bitset）。

在 Thrift 结构 中定义如下：

struct BloomFilterPageHeader {
  1: required i32 numBytes;
  2: required BloomFilterAlgorithm algorithm;
  3: required BloomFilterHash hash;
  4: required BloomFilterCompression compression;
}

struct ColumnMetaData {
  ...
  14: optional i64 bloom_filter_offset;
}

布隆过滤器可以存储在：

  1. 所有行组（Row Group）之后
  2. 行组之间

加密

对于敏感数据列，布隆过滤器可能暴露部分信息（如某值是否存在）。因此，敏感列的布隆过滤器应使用 列密钥（Column Key） 进行加密，非敏感列无需加密。

加密使用 AES-GCM 算法，并且： - 布隆过滤器头部 使用 "BloomFilter Header"（8） 作为 AAD。 - 布隆过滤器位集 使用 "BloomFilter Bitset"（9） 作为 AAD。

最佳实践

  1. 高基数列优先使用布隆过滤器，而非字典，以节省存储空间。
  2. 确保合理设置比特位与插入值比率，控制假阳性率。
  3. 对于敏感列，启用加密，以避免数据泄露。