背景

在大数据分析领域,很多优化都是围绕一句话来做:”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