bloommask

datatrove stores its deduplication Bloom filter as m_bytes bytes and reports a false-positive rate computed over the m_bytes * 8 bits that allocation holds. The line that maps a hash to a bit index reduces it with a bitwise AND against m_bytes, the byte count, instead of the bit count. That AND can only return submasks of the set bits of m_bytes, so the filter reaches exactly 2 ** popcount(m_bytes) bit positions regardless of how many bits it allocated. For a power-of-two size it reaches two. The filter saturates after a couple of insertions, and a stream of genuinely unique documents is dropped as duplicates while the logged false-positive rate stays near zero.

The line

SingleBloomFilter.get_indexes, src/datatrove/pipeline/dedup/bloom_filter.py line 147, commit 5987417f95605cce581454fcff22305b3165bb3e (current main):

phv = np.bitwise_and((shingles * a + b) % _mersenne_prime, self.config.m_bytes)

Every other part of the file works in the m_bytes * 8 bit space this contradicts:

• the m property returns self.m_bytes * 8;
• get_optimal_k and get_false_positive_prob compute with m = size_in_bytes * 8;
• the bit vector is bytearray([0] * m_bytes), that is m_bytes * 8 bits;
• update_bf and query turn an index into a bit address with divmod(index, 8), so a valid index runs over [0, m_bytes * 8).

The correct reduction is % self.config.m, or & (self.config.m - 1) when m is a power of two. The shipped & self.config.m_bytes is off by the factor of eight between bytes and bits, and worse, it is an AND rather than a modulo, so it does not even cover the smaller range uniformly.

The reachable-index law

hash & m_bytes returns a submask of the set bits of m_bytes. Every submask is attainable, so the set of reachable indices has exactly

reachable = 2 ** popcount(m_bytes)

elements, against the m_bytes * 8 bits allocated. The reachable fraction is 2 ** popcount(m_bytes) / (m_bytes * 8), which is minute for any realistic size and worst for the power-of-two sizes an operator is most likely to choose.

m_bytes	popcount	reachable bits	allocated bits	fraction
2^20	1	2	8388608	2.4e-07
2^16	1	2	524288	3.8e-06
1000	6	64	8000	8.0e-03
2^10 - 1	10	1024	8184	1.3e-01

The reported rate is not the delivered rate

datatrove logs get_false_positive_prob(m_bytes, n, k), the standard Bloom expression over m = m_bytes * 8 bits. The filter delivers the same expression with the reachable count in place of m. At m_bytes = 2^20, k = 7, and only one hundred inserted shingles the logged rate is 2.8e-29 and the delivered rate is 1.0. The two disagree by twenty-nine orders of magnitude, and the gap is not a bound or an approximation, it is the difference between m_bytes * 8 and two in the denominator.

What it does to a corpus

impact.py runs datatrove's insert-and-query path on fifty documents whose shingles are all distinct random hashes, changing only the reduction on line 147. With the correct reduction none of the fifty are dropped. With the shipped mask, at m_bytes = 2^20 and k = 7, the two reachable bits are set almost at once, every later shingle reads as already seen, and 49 of the 50 unique documents are dropped as duplicates.

Why it survived the test suite

tests/pipeline/dedup/test_bloom_filter.py builds the filter with m_bytes = 2**10 - 1. That is 1023, an all-ones mask, and for an all-ones mask hash & 1023 equals hash % 1024. The AND accidentally becomes a clean modulo over 1024 buckets, enough to keep the small test input collision-free, so the assertions pass. The one size the suite exercises is the single arithmetic case in which the bug is invisible. Any non-(2^p - 1) size shrinks the reachable set, and every power-of-two size collapses it to two.

Layout

• mask.py: the committed and correct reductions, and the exact reachable-index law 2 ** popcount(m_bytes) against the m_bytes * 8 allocated bits.
• fprate.py: the logged false-positive rate over m_bytes * 8 bits versus the delivered rate over 2 ** popcount(m_bytes) bits, and their ratio.
• impact.py: datatrove's get_indexes, update_bf, query, and step reproduced exactly, and the unique-document drop count under each reduction.
• test_bloommask.py: the reachable-count law, the power-of-two collapse to two bits, the submask-only range of the committed mask, the logged-versus-delivered divergence, the unique-document drops, and the all-ones size that hides the bug.

Reproduce

python mask.py
python fprate.py
python impact.py
python test_bloommask.py

Fix

Replace the byte-count mask with a reduction into the bit space the rest of the file already uses:

phv = (shingles * a + b) % _mersenne_prime % self.config.m

or & (self.config.m - 1) when m is a power of two. That restores the m_bytes * 8 addressable bits and the false-positive rate the filter reports.