BlockedBloomFilter Class

A Bloom filter that stores the bits of each value in a single 64-byte block (one cache line).

public closed class BlockedBloomFilter

Remarks

A BloomFilter spreads the bits of a value over the whole filter, so adding or finding a value in a filter larger than the CPU caches reads HashCount unrelated cache lines. A blocked filter chooses one block from the hash and sets every bit of the value inside it: one cache line per operation. Blocks do not fill evenly, so a blocked filter needs a little more memory for the same false positive probability; size it with BlockedBloomFilterSize.

Methods

NameDescription
CreateAdler32(BlockedBloomFilterSize)
CreateCrc32(BlockedBloomFilterSize)
CreateCrc64(BlockedBloomFilterSize)
CreateXXHash128(BlockedBloomFilterSize)
CreateXXHash3(BlockedBloomFilterSize)
CreateXXHash32(BlockedBloomFilterSize)
CreateXXHash64(BlockedBloomFilterSize)
GetEstimateCount()
Load(Stream)Creates a filter from a snapshot written by BlockedBloomFilter.Save.
Load<TFilter>(Stream)Creates a filter of a given type from a snapshot written by BlockedBloomFilter.Save.
LoadAsync(Stream, CancellationToken)Creates a filter from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.
LoadAsync<TFilter>(Stream, CancellationToken)Creates a filter of a given type from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.
Save(Stream)Writes a snapshot of the filter to a stream: its hash algorithm, its size and its bits.
SaveAsync(Stream, CancellationToken)Writes a snapshot of the filter to a stream: its hash algorithm, its size and its bits.
UnionWith(BlockedBloomFilter)Adds to this filter every value represented by other, by combining their bits with a bitwise OR.

CreateAdler32(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterAdler32 CreateAdler32(BlockedBloomFilterSize size)

No documentation is available.

CreateCrc32(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterCrc32 CreateCrc32(BlockedBloomFilterSize size)

No documentation is available.

CreateCrc64(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterCrc64 CreateCrc64(BlockedBloomFilterSize size)

No documentation is available.

CreateXXHash128(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterXXHash128 CreateXXHash128(BlockedBloomFilterSize size)

No documentation is available.

CreateXXHash3(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterXXHash3 CreateXXHash3(BlockedBloomFilterSize size)

No documentation is available.

CreateXXHash32(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterXXHash32 CreateXXHash32(BlockedBloomFilterSize size)

No documentation is available.

CreateXXHash64(BlockedBloomFilterSize)

BloomFilter.g.cs
public static BlockedBloomFilterXXHash64 CreateXXHash64(BlockedBloomFilterSize size)

No documentation is available.

GetEstimateCount()

BlockedBloomFilter.cs
public double GetEstimateCount()

Returns

double

No documentation is available.

Load overloads

Creates a filter from a snapshot written by BlockedBloomFilter.Save.

public static BlockedBloomFilter Load(Stream stream)
Parameters
stream Stream
The stream to read the snapshot from. It is left positioned after the snapshot.
Returns

BlockedBloomFilter A new filter of the hash algorithm, size and content of the snapshot, such as a BlockedBloomFilterXXHash128.

Exceptions
InvalidDataException
The data is not a blocked Bloom filter snapshot, is truncated or corrupted, uses an unsupported version, or was written on a machine with another byte order.
Remarks

The header is validated before the filter is allocated. When the stream is seekable, its length is also checked against the size of the filter first. The snapshot ends with a checksum, verified once it is read.

Load<TFilter>(Stream)

BlockedBloomFilter.Snapshot.cs

Creates a filter of a given type from a snapshot written by BlockedBloomFilter.Save.

public static TFilter Load<TFilter>(Stream stream) where TFilter : BlockedBloomFilter
Type parameters
TFilter
The type of the filter, such as BlockedBloomFilterXXHash128.
Parameters
stream Stream
The stream to read the snapshot from. It is left positioned after the snapshot.
Returns

TFilter A new filter of the size and content of the snapshot.

Exceptions
InvalidDataException
The snapshot contains a filter of another type, or is not valid (see BlockedBloomFilter.Load).

LoadAsync overloads

LoadAsync(Stream, CancellationToken)

BlockedBloomFilter.Snapshot.cs

Creates a filter from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.

public static Task<BlockedBloomFilter> LoadAsync(Stream stream, CancellationToken cancellationToken = default)
Parameters
stream Stream
The stream to read the snapshot from. It is left positioned after the snapshot.
cancellationToken CancellationToken
A token to cancel the operation.
Returns

Task<BlockedBloomFilter> A new filter of the hash algorithm, size and content of the snapshot.

Exceptions
InvalidDataException
The snapshot is not valid (see BlockedBloomFilter.Load).

LoadAsync<TFilter>(Stream, CancellationToken)

BlockedBloomFilter.Snapshot.cs

Creates a filter of a given type from a snapshot written by BlockedBloomFilter.Save or BlockedBloomFilter.SaveAsync.

public static Task<TFilter> LoadAsync<TFilter>(Stream stream, CancellationToken cancellationToken = default) where TFilter : BlockedBloomFilter
Type parameters
TFilter
The type of the filter, such as BlockedBloomFilterXXHash128.
Parameters
stream Stream
The stream to read the snapshot from. It is left positioned after the snapshot.
cancellationToken CancellationToken
A token to cancel the operation.
Returns

Task<TFilter> A new filter of the size and content of the snapshot.

Exceptions
InvalidDataException
The snapshot contains a filter of another type, or is not valid (see BlockedBloomFilter.Load).

Writes a snapshot of the filter to a stream: its hash algorithm, its size and its bits.

public void Save(Stream stream)

Parameters

stream Stream
The stream to write the snapshot to.

Remarks

The bits are copied through a small buffer, so saving a large filter does not allocate a second copy of it.

Stop adding values while the snapshot is written. Each bit is read atomically, but values added during the write may be partially saved: some of their bits are in the snapshot, others are not, so the restored filter may report them as absent.

Keys are hashed from their in-memory bytes, so the snapshot records the byte order of the machine, and BlockedBloomFilter.Load rejects a snapshot written on a machine with another byte order.

Example

var filter = BlockedBloomFilter.CreateXXHash128(BlockedBloomFilterSize.CreateOptimalSize(expectedItemCount: 1000, falsePositiveProbability: 0.01));
filter.Add("alice@example.com");

using var stream = new MemoryStream();
filter.Save(stream);

stream.Position = 0;
var restored = BlockedBloomFilter.Load<BlockedBloomFilterXXHash128>(stream);

Assert.True(restored.MayContain("alice@example.com"));
Assert.False(restored.MayContain("bob@example.com"));

SaveAsync(Stream, CancellationToken)

BlockedBloomFilter.Snapshot.cs

Writes a snapshot of the filter to a stream: its hash algorithm, its size and its bits.

public Task SaveAsync(Stream stream, CancellationToken cancellationToken = default)

Parameters

stream Stream
The stream to write the snapshot to.
cancellationToken CancellationToken
A token to cancel the operation.

Returns

Task A task that completes when the snapshot is written.

Remarks

See BlockedBloomFilter.Save. Stop adding values until the task completes.

UnionWith(BlockedBloomFilter)

BlockedBloomFilter.cs

Adds to this filter every value represented by other, by combining their bits with a bitwise OR.

public void UnionWith(BlockedBloomFilter other)

Parameters

other BlockedBloomFilter
The filter whose values are added. It must use the same hash algorithm (the same concrete type), the same number of blocks and the same number of hash functions as this filter. It is not modified.

Exceptions

ArgumentNullException
other is null.
ArgumentException
other uses another hash algorithm, number of blocks or number of hash functions.

Remarks

After the call, MayContain returns true for every value added to this filter or to other before the call: the union never introduces a false negative. Calling the method with the filter itself does nothing.

The result holds the values of both filters in the same number of bits. Its false positive probability is higher than the one the filters were sized for when the total number of values exceeds the expected item count. Size each filter for the total number of values when you plan to merge them.

The compatibility checks happen before any bit is written: when they fail, this filter is left unchanged.

The method can run while other threads call Add or MayContain on either filter. The bits of this filter are set with atomic operations, so no value added concurrently to this filter is lost. The source is read one 64-bit word at a time, not as a snapshot: a value added to other during the call may or may not be included. Once the method has returned, every value that was in other when it was called is included.