Highly optimized Bloom filter that mimics the Python set API, written in Rust
Project description
rBloom
A fast, simple and lightweight
Bloom filter library for
Python, implemented in Rust. It's designed to be as pythonic as
possible, mimicking the built-in set
type where it can, and works with
any hashable object. While it's a new
kid on the block (this project was started in 2023), it's also currently
the fastest kid on the block by a long shot (see the section
Benchmarks). Releases are published on
PyPI.
Quickstart
This library defines only one class, which can be used as follows:
>>> from rbloom import Bloom
>>> bf = Bloom(200, 0.01) # 200 items max, false positive rate of 1%
>>> bf.add("hello")
>>> "hello" in bf
True
>>> "world" in bf
False
>>> bf.update(["hello", "world"]) # "hello" and "world" now in bf
>>> other_bf = Bloom(200, 0.01)
### add some items to other_bf
>>> third_bf = bf | other_bf # third_bf now contains all items in
# bf and other_bf
>>> third_bf = bf.copy()
... third_bf.update(other_bf) # same as above
>>> bf.issubset(third_bf) # bf <= third_bf also works
True
Unlike BF's in real life, you can have as many of these as you want, and they all work well together!
For the full API, see the section Documentation.
Installation
On almost all platforms, simply run:
pip install rbloom
If you're on an uncommon platform, this may cause pip to build the library
from source, which requires the Rust
toolchain. You can also build
rbloom
by cloning this repository and running
maturin:
maturin build --release
This will create a wheel in the target/wheels/
directory, which can
subsequently also be passed to pip.
Why rBloom?
Why should you use this library instead of one of the other Bloom filter libraries on PyPI?
- Simple: Almost all important methods work exactly like their
counterparts in the built-in
set
type. - Fast:
rbloom
is implemented in Rust, which makes it blazingly fast. See section Benchmarks for more information. - Lightweight:
rbloom
has no dependencies of its own. - Maintainable: This library is very concise, and it's written
in idiomatic Rust. Even if I were to stop maintaining
rbloom
(which I don't intend to), it would be trivially easy for you to fork it and keep it working for you.
I started rbloom
because I was looking for a simple Bloom filter
dependency for a project, but the pure Python implementations were too
slow. The only fast alternative I could find, pybloomfiltermmap3
(written
in C), showed undefined behavior on recent versions of Python (see below),
so I made rbloom
instead. It ended up being twice as fast and has grown to
encompass a more complete API (e.g. with set comparisons like issubset
).
Do note that while rbloom
only supports reading and writing its Bloom filter
files in one sweep, pybloomfiltermmap3
supports modifying them in-place with
mmap. This is of limited utility in most cases due to the random-access-heavy
nature of Bloom filters, which causes the entire file to be in memory after
only a few operations in spite of mmap, but does more elegantly utilize the
disk cache on most operating systems. As a rule of thumb, if you need filters
larger than your system memory (one gigabyte stores around a billion items
depending on the false positive rate), you should use pybloomfiltermmap3
.
Benchmarks
I implemented the following simple benchmark in the respective API of each library:
bf = Bloom(10_000_000, 0.01)
for i in range(10_000_000):
bf.add(i + 0.5) # floats because ints are hashed as themselves
for i in range(10_000_000):
assert i + 0.5 in bf
This resulted in the following runtimes:
Library | Time | Notes |
---|---|---|
rBloom | 5.956s | works out-of-the-box |
pybloomfiltermmap3 | 11.280s | surprisingly hard to get working [1] |
pybloom3 | 75.871s | works out-of-the-box |
Flor | 128.837s | doesn't work on arbitrary objects [2] |
bloom-filter2 | 325.044s | doesn't work on arbitrary objects [2] |
[1] It refused to install on Python 3.11 and kept segfaulting on 3.10 (on Linux
as of January 2023), so I installed 3.7 on my machine for this benchmark.
[2] I tested both converting to bytes and pickling, and chose the faster time.
The benchmark was run on a 2019 Dell XPS 15 7590 with an Intel Core i5-9300H. It was run 5 times for each library, and the average time was used.
Also note that rbloom
is compiled against a stable ABI for
portability, and that you can get a small but measurable speedup by
removing the "abi3-py37"
flag from Cargo.toml
and building
it yourself.
Documentation
This library defines only one class, the signature of which should be
thought of as follows. Note that only the first few methods differ from
the built-in set
type:
class Bloom:
# expected_items: max number of items to be added to the filter
# false_positive_rate: max false positive rate of the filter
# hash_func: optional argument, see section "Cryptographic security"
def __init__(self, expected_items: int, false_positive_rate: float,
hash_func=__builtins__.hash)
@property
def size_in_bits(self) -> int # number of buckets in the filter
@property
def hash_func(self) -> Callable[[Any], int] # retrieve the hash_func
# given to __init__
@property
def approx_items(self) -> float # estimated number of items in
# the filter
@classmethod
def load(cls, filepath: str, hash_func) -> Bloom # see "Persistence"
def save(self, filepath: str) # see section "Persistence"
#####################################################################
# ALL SUBSEQUENT METHODS ARE #
# EQUIVALENT TO THE CORRESPONDING METHODS #
# OF THE BUILT-IN SET TYPE #
#####################################################################
def add(self, obj) # add obj to self
def __contains__(self, obj) -> bool # check if obj in self
def __bool__(self) -> bool # False if empty
def __repr__(self) -> str # basic info
def __or__(self, other: Bloom) -> Bloom # self | other
def __ior__(self, other: Bloom) # self |= other
def __and__(self, other: Bloom) -> Bloom # self & other
def __iand__(self, other: Bloom) # self &= other
# these extend the functionality of __or__, __ior__, __and__, __iand__
def union(self, *others: Union[Iterable, Bloom]) -> Bloom # __or__
def update(self, *others: Union[Iterable, Bloom]) # __ior__
def intersection(self, *others: Union[Iterable, Bloom]) -> Bloom # __and__
def intersection_update(self, *others: Union[Iterable, Bloom]) # __iand__
# these implement <, >, <=, >=, ==, !=
def __lt__, __gt__, __le__, __ge__, __eq__, __ne__(self,
other: Bloom) -> bool
def issubset(self, other: Bloom) -> bool # self <= other
def issuperset(self, other: Bloom) -> bool # self >= other
def clear(self) # remove all items
def copy(self) -> Bloom # duplicate self
To prevent death and destruction, the bitwise set operations only work on
filters where all parameters are equal (including the hash functions being
the exact same object). Because this is a Bloom filter, the __contains__
and approx_items
methods are probabilistic, as are all the methods that
compare two filters (such as __le__
and __issubset__
).
Cryptographic security
Python's built-in hash function is designed to be fast, not maximally collision-resistant, so if your program depends on the false positive rate being perfectly correct, you may want to supply your own hash function. This is especially the case when working with very large filters (more than a few tens of millions of items) or when false positives are very costly and could be exploited by an adversary. Just make sure that your hash function returns an integer between -2^127 and 2^127 - 1. Feel free to use the following example in your own code:
from rbloom import Bloom
from hashlib import sha256
from pickle import dumps
def hash_func(obj):
h = sha256(dumps(obj)).digest()
return int.from_bytes(h[:16], "big") - 2**127
bf = Bloom(100_000_000, 0.01, hash_func=hash_func)
When you throw away Python's built-in hash function and start hashing serialized representations of objects, however, you open up a breach into the scary realm of the unpythonic:
- Numbers like
2
,2.0
and2 + 0j
will suddenly no longer be equal. - Instances of classes with custom hashing logic (e.g. to stop caches inside instances from affecting their hashes) will suddenly display undefined behavior.
- Objects that can't be serialized simply won't be hashable at all.
Making you supply your own hash function in this case is a deliberate design decision intended to show you what you're doing and prevent you from shooting yourself in the foot.
Also note that using a custom hash will incur a performance penalty over using the built-in hash.
Persistence
The save
and load
methods allow you to save and load filters to and
from disk. However, as the built-in hash function's salt changes between
invocations of Python, they only work on filters with custom hash
functions. Note that it is your responsibility to ensure that the hash
function you supply to load
is the same as the one originally used by
the filter you're loading!
bf = Bloom(10_000, 0.01, some_hash_func)
bf.add("hello")
bf.add("world")
bf.save("bf.bloom")
loaded_bf = Bloom.load("bf.bloom", some_hash_func)
assert loaded_bf == bf
The size of the file is bf.size_in_bits // 8 + 8
bytes.
Statement of attribution: Bloom filters were originally proposed in (Bloom, 1970). Furthermore, this implementation makes use of a constant recommended by (L'Ecuyer, 1999) for redistributing the entropy of a single hash over multiple integers using a linear congruential generator.
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for rbloom-1.4.4-cp37-abi3-win_amd64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 8218e10daf2d8e8b037b21591698891d5884df67d44abbfc3c13ee286a1c2fd4 |
|
MD5 | 4d5c48bf9f3d707c7272fa2c79b162a6 |
|
BLAKE2b-256 | a852cefa2538840d61a0c744dfc885a7fd0d112c6f36ea32abdc3ee5ff5d1f65 |
Hashes for rbloom-1.4.4-cp37-abi3-manylinux_2_17_x86_64.manylinux2014_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | d9b17db3ef642b027a37cc78e16909b32aafd93033a23423b7d23ca2bd02a875 |
|
MD5 | d77620c08df7faafe962f50d7694be61 |
|
BLAKE2b-256 | c433df2f5c3b32c6893ecbce14b9022e7cf4b46a4fa3abfa92596f979977cc78 |
Hashes for rbloom-1.4.4-cp37-abi3-manylinux_2_17_aarch64.manylinux2014_aarch64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 67b126490a7425de6ec0d8843cefdcf7b2bdcf3700ec0de7098b5141cf82367b |
|
MD5 | c6ca84e8cc91f501e7fe0b0e2fdb53ab |
|
BLAKE2b-256 | 5677ec06d152fd635fab3338e471d1fc04fbabd36a62eaf290dda945048f415e |
Hashes for rbloom-1.4.4-cp37-abi3-manylinux_2_5_i686.manylinux1_i686.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 98af67939c814856c2261965412ba2bf2491e527496ee4b26238a3a49572fe1f |
|
MD5 | 7d5378c5441053fd929e76d02ac83fac |
|
BLAKE2b-256 | 117672fcb2ec7abe154930d4713e9337a1b00501b28bc00e6be78f6d37853381 |
Hashes for rbloom-1.4.4-cp37-abi3-macosx_10_9_x86_64.macosx_11_0_arm64.macosx_10_9_universal2.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 1b038b7851fd09c610aca4f56b4552458c1a94e49195bf78c70983f9b9f195cc |
|
MD5 | a70144c165e86b88edbfa8a5f22b3069 |
|
BLAKE2b-256 | 31dcd393c26b0be991f37a158d0f59b4d002deee7759507ce1f982de25cd497f |