Flower

This is an implementation of Bloom Filters for Elixir. It uses NIFs written in Rust for better performance, since Bloom Filters rely highly on mutability.

What are Bloom Filter?

TL;DR: Huge amount of data ➜ small Bloom Filter : Was X not in Huge amount of data?

For more about this topic consider checking out:

• Bloom Filters by Jason Davis
• Bloom Filters, Mining of Massive Datasets, Stanford University on Youtube

Installation

The package can be installed by adding flower to your list of dependencies in mix.exs:

def deps do
  [
    {:flower, "~> 0.1.1"},
  ]
end

Also, you need to have Rust installed, since this uses NIFs.

Docs can be found at https://hexdocs.pm/flower.

Documentation can be generated with ExDoc.

Usage

There is also a small walk through in the Example Section

alias Flower.Bloom, as: Bloom

Create new Bloom Filter

expected_number_of_unique_elements = 1000
# With an size atom
iex> filter = Bloom.new(:"8 KB", expected_number_of_unique_elements)
...
# Or by a maximum byte size:
iex> filter = Bloom.new_by_byte_size(8 * 1024, expected_number_of_unique_elements)
...
# Or by a bit address length:
iex> filter = Bloom.new(16, expected_number_of_unique_elements)
...

Insert Elements

iex> Bloom.insert(filter, 42)
:ok
iex> Bloom.insert(filter, [1,2,{:atom, <<1,2,3,4>>}])
:ok
iex> Bloom.insert(filter, "Hello!")
:ok

Check for Elements

iex> Bloom.has_not?(filter, "Hello!")
false
iex> Bloom.has_maybe?(filter, [1,2,{:atom, <<1,2,3,4>>}])
true
iex> Bloom.has_maybe?(filter, :atom)
false
# `has_maybe?` is allways the opposite of `has_not?`.
iex> Bloom.has_maybe?(filter, 42) != Bloom.has_not?(filter, 42)
true

Funky Stuff

iex> Bloom.estimate_count(filter)
3
iex> Bloom.false_positive_probability(filter)
3.2348227494719115e-28
# This number is only that small, because we have just 3 elements in 8 KBs.

Example

Prime Numbers

Checking if a number is not a prime and below 100_000.

# helper module
defmodule Step do
    def throught(from, to, step, func) when from < to do
        func.(from)
        throught(from+step, to, step, func)
    end
    def throught(_,_,_,_), do: :ok
end && :ok

# alias so we need to write less
alias Flower.Bloom, as: Bloom


# Select apropriate size.
# We will put about 100_000 elements in.
# 64 KB = 512 KBit
# 512 KBit / 100_000 ~= 5.25 Bits per element.
# Meeh. Lets see...
non_primes = Bloom.new(:"64 KB", 100_000)
# We can also write
non_primes = Bloom.new(19, 100_000)
# or (it will choose the next smaller size)
non_primes = Bloom.new_by_byte_size(64 * 1024, 100_000)

# Lets inspect the size.
byte_size(Bloom.serialize(non_primes))

# lets two non primes in:
Bloom.insert(non_primes, 42)
Bloom.insert(non_primes, "one hundred")
Bloom.insert(non_primes, [:ok, {Anything, 1.0e9}])

# Let's double check:
Bloom.has_maybe?(non_primes, 42)
Bloom.has_maybe?(non_primes, "one hundred")
Bloom.has_maybe?(non_primes, 7)
Bloom.has_maybe?(non_primes, [:ok, {Anything, 1.0e9}])
Bloom.has_maybe?(non_primes, 52)
# Works!


# Now we can get a estimate of
# the number of items we
# put in.
Bloom.estimate_count(non_primes)


# Apply Sieve of Eratosthenes
# This may take a few seconds.
# At least we can do it with
# constant memory.
for x <- 2..50_000 do
  # Skip multiples of previous numbers.
  # this is actually not safe to do
  # with a bloom filter since they are
  # aproximations. But let's don't care for now.
  if(Bloom.has_not?(non_primes, x)) do
    Step.throught(x*2, 100_000, x, fn non_prime ->
        # Much of the time is used to calculate
        # hashes.
        Bloom.insert(non_primes, non_prime)
    end)
 end
end && :ok

non_primes |> Bloom.has_not?(12) # not a prime
non_primes |> Bloom.has_not?(11) # prime
non_primes |> Bloom.has_not?(6719) # no prime
non_primes |> Bloom.has_not?(4245) # prime
non_primes |> Bloom.has_not?(9973) # no prime
non_primes |> Bloom.has_not?(3549) # prime
non_primes |> Bloom.has_not?(89591) # prime
non_primes |> Bloom.has_not?(84949) # no prime

# Maybe a bit high, 64 KB for 100_000 Numbers
# is not that much.
Bloom.false_positive_probability(non_primes)

# Let's reestimate .
# There are 9_592 primes below 100_000, so this
# should yield about 100_000 - 9_592 = 90_408
Bloom.estimate_count(non_primes)

Side note: If you want to check primes, google search for Miller–Rabin primality test.

Note

Please try avoiding calling the following functions often:

• Bloom.false_positive_probability
• Bloom.estimate_count
• Bloom.serialize
• Bloom.deserialize

They are expensive for larger sizes, and therefore run on the Dirty CPU Scheduler.

Bloom.serialize(Bloom.new(:"512 MB", 100)) can hang for 45 seconds! The data has to be copied since Elixir data types are immutable.