背景

在大数据分析领域，很多优化都是围绕一句话来做：”reduce distance to the data.“

Bloom Filter Index 的作用是访问 Storage 之前使用布隆索引做下探测，然后决定是否需要从后端读取真正的数据块。

有问题的 Bloom Filter

大家所熟悉的数据库，大部分都在使用 Bloom Filter 解决等值查询的问题，避免做一些无用的数据读取。

Databend 第一版( databend#6639) 使用的也是 Bloom Filter 经典算法，经过测试发现了一些问题：
Bloom Filter Index 的索引空间占用过大，Bloom Filter Index 大小甚至超过了原始数据大小（为了让用户简单易用，Databend 会自动为某些数据类型创建 Bloom 索引），这样做 Bloom 检测跟直接读取后端数据区别不大，所以并没有太大的性能提升。

原因是 Bloom Filter 生成时并不知道数据的基数，比如 Boolean 类型，它也会根据数目分配空间，并不会关注基数问题（基数为 2，True or False）。

于是 Databend 社区开始了新方案的探索之路，初步确定一个可行方案是通过 HyperLoglog 检测出数据唯一度，然后做空间分配。

9 月份某个周六的 TiDB 用户大会上，Databend 有个展台，跟 xp(@drmingdrmer) 见面（Databend 团队是 Remote 办公，大家线下见面不太容易 😭）重新讨论起这个问题，他想用 Trie 思想来解决，思路挺好，但复杂度较高。

xp 是 Trie 领域的高手，工程实现来对他来说不是问题，但隐约感觉一些现有技术可以很好的解决这个问题。

高性价比的 Xor Filter

周日进行了一番探索，发现了 Daniel Lemire 团队在 2019 年提出的 Xor Filter 算法: Xor Filters: Faster and Smaller Than Bloom Filters，从介绍看效果非常不错。

抱着试试看的心理，基于 Rust 版（xorfilter）做了一个测试 （Xor Filter Bench，发现疗效非常不错：

1
2
3
4
5
6
7
8
9
10
11
u64: 
xor bitmap encode:1230069 bytes, raw:8000000 bytes, ratio:0.15375863

bool:
xor bitmap encode:61 bytes, raw:1000000 bytes, ratio:0.000061

string:
xor bitmap encode:123067 bytes, raw:3000000 bytes, ratio:0.041022334

100000 records of the same key:
xor bitmap encode: 61 bytes, raw:3000000 bytes, ratio:0.000020333333

于是，在 databend#7860 实现了 Bloom Filter 到 Xor Filter 的切换，让我们做一些测试来看看效果。

测试环境

Databend: v0.8.122-nightly，单节点
VM: 32 vCPU, 32 GiB (Cloud VM)
Object Store: S3
数据集: 100 亿记录，350G Raw Data，Xor Filter Index 700MB，索引和数据全部持久化到对象存储
表结构:

1
2
3
4
5
6
7
mysql> desc t10b;
+-------+-----------------+------+---------+-------+
| Field | Type            | Null | Default | Extra |
+-------+-----------------+------+---------+-------+
| c1    | BIGINT UNSIGNED | NO   | 0       |       |
| c2    | VARCHAR         | NO   |         |       |
+-------+-----------------+------+---------+-------+

部署 Databend

Step1：下载安装包

1
2
wget https://github.com/datafuselabs/databend/releases/download/v0.8.122-nightly/databend-v0.8.122-nightly-x86_64-unknown-linux-musl.tar.gz .
tar zxvf databend-v0.8.122-nightly-x86_64-unknown-linux-musl.tar.gz

解压后目录结构：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
tree
.
├── bin
│   ├── databend-meta
│   ├── databend-metabench
│   ├── databend-metactl
│   └── databend-query
├── configs
│   ├── databend-meta.toml
│   └── databend-query.toml
├── readme.txt
└── scripts
    ├── start.sh
    └── stop.sh

Step2：启动 Databend Meta

1
./bin/databend-meta -c configs/databend-meta.toml

Step3：配置 Databend Query

1
vim configs/databend-query.toml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
... ...

[meta]
endpoints = ["127.0.0.1:9191"]
username = "root"
password = "root"
client_timeout_in_second = 60
auto_sync_interval = 60

# Storage config.
[storage]
# fs | s3 | azblob | obs
type = "s3"

# To use S3-compatible object storage, uncomment this block and set your values.
 [storage.s3]
bucket = "<your-bucket-name>"
endpoint_url = "<your-s3-endpoint>"
access_key_id = "<your-key>"
secret_access_key = "<your-access-key>"

详细部署文档请参考： https://databend.rs/doc/deploy/deploying-databend

Step4： 启动 Databend Query

1
./bin/databend-query -c configs/databend-query.toml

Step5： 构造测试数据集

1
mysql -uroot -h127.0.0.1 -P3307

构造 100 亿条测试数据(耗时 16 min 0.41 sec):

1
create table t10b as select number as c1, cast(rand() as string) as c2 from numbers(10000000000)

查询（无任何缓存，数据和索引全部在对象存储）：

1
2
3
4
5
6
7
8
mysql> select * from t10b where  c2='0.6622377673133426';
+-----------+--------------------+
| c1        | c2                 |
+-----------+--------------------+
| 937500090 | 0.6622377673133426 |
+-----------+--------------------+
1 row in set (20.57 sec)
Read 40000000 rows, 1009.75 MiB in 20.567 sec., 1.94 million rows/sec., 49.10 MiB/sec.

单节点 Databend 利用 filter 下推，然后使用 Xor Filter 索引做过滤，在 100 亿规模的随机数据上做点式查询，可以在 20s 左右。
也可以利用 Databend 的分布式能力来加速点查，Databend 的设计理念是一份数据计算弹性扩展，从单节点扩展到集群模式也非常简单：Expanding a Standalone Databend。

References

[1] Arxiv: Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters
[2] Daniel Lemire’s blog: Xor Filters: Faster and Smaller Than Bloom Filters
[3] Databend, Cloud Lakehouse: https://github.com/datafuselabs/databend