Unified probabilistic filter API

[nevillelyh]

This is inspired by the discussion about Algebird BloomFilter, mutable BloomFilter from #1806, and CuckooFilter (paper).

cc @anish749 @clairemcginty

Background:

• There're multiple probabilistic implementations with different properties and performance.
• This discussion is limited to using Bloom/Cuckoo Filter for probabilistic set membership.
• Not all of them can be expressed as Algebird Semigroup or Aggregator.
• A common use case is to convert an SCollection[T] (where T can be String, Array[Byte], etc.) as a singleton SCollection[ProbFilter], which can then be used as a side input or store on disk.

For this specific case we want to abstract over the existing mutable BloomFilter & Java CuckooFilter (also mutable) and a few use cases. A few points about the 2 filter algorithsm:

• Filter construction
  • BF can be constructed in parallel and expressed as a Semigroup or Aggregator, since BF ++ BF is just bitwise OR.
  • CF cannot be constructed in parallel since insertion is non-deterministic (random entry in a bucket) and may involve eviction. So it requires a .groupBy(_ => ()) followed by sequential insertion of all elements. OTOH we can do a .map() into (index1: Long, fingerprint: Int) per element to reduce shuffle IO, since each entry is represented by index1, index2, fingerprint alone and we can compute index2 from index1 XOR fingerprint and vice versa.
• Insertion
  • BF insertions are idempotent, so we don't have to do SCollection#unique before building the filter. BF insertions will also never fail since it's just flipping bits to 1.
  • CF insertions are not idempotent, and cannot insert the same item more than 2b times where b is bucket size (usually 2, 4, or 8). In our case of set membership, we should do SCollection#unique before building the filter. CF insertions can fail when it's close to full capacity.
• Probabilistic interpretations
  • Both BF and CF has well defined false positive probability, which is usually set at filter construction.
  • BF can have false positives but no false negatives, i.e. either maybe contains or definitely does not contain.
  • CF can have false negatives if we ignore failed insertions. The false negative probability = # of insertion failure / # of insertions.
  • To make a CF that behaves like BF, i.e. no false negatives, we can either A retry with bigger capacity until no failures occur (more time) or B memorize failed items and build a second CF, and chain maybeContains lookup.

Proposal:

I sketched something like this:

import com.spotify.scio.values.SCollection
import com.twitter.algebird

// immutable, read only filter interface
trait ProbFilter[T] {
  val capacity: Long // maximum number of items allowed
  val fpp: Double // false positive prob
  val fnp: Double // false negative prob
  def hasFalsePos: Boolean = fpp > 0.0
  def hasFalseNeg: Boolean = fnp > 0.0

  // may return both false positive and negative depending on `fpp` and `fnp`
  def contains(item: T): Boolean
}

// builder
trait ProbFilterBuilder[PF[_]] {
  def build[T](data: Seq[T])(implicit hash: algebird.Hash128[T]): PF[T]
  def build[T](data: SCollection[T])(implicit hash: algebird.Hash128[T]): SCollection[PF[T]]

  // probably methods for ser/de too
}

// naive BF impl with immutable Algebird BF
case class BloomFilter[T] private (capacity: Long, fpp: Double, internal: algebird.BF[T])
    extends ProbFilter[T] {
  override val fnp: Double = 0.0

  override def contains(item: T): Boolean = internal.maybeContains(item)
}

case class BloomFilterBuilder(capacity: Long, fpp: Double)
  extends ProbFilterBuilder[BloomFilter] {
  override def build[T](data: Seq[T])(implicit hash: algebird.Hash128[T]): BloomFilter[T] = {
    require(capacity <= Int.MaxValue)
    val bfm = algebird.BloomFilter(capacity.toInt, fpp)
    val bfa = algebird.BloomFilterAggregator(bfm)
    val bf = bfa.appendAll(data)
    BloomFilter(capacity, fpp, bf)
  }

  override def build[T](data: SCollection[T])(
    implicit hash: algebird.Hash128[T]
  ): SCollection[BloomFilter[T]] = ???
}

We can implement this for the following and hide all impl details, including aggregator/groupBy/pre-hash and Algebird vs our mutable instances away.

• mutable BF
• one-sided CF with no false negative
• two-sided CF with both false positive & negative

On the Scio side, we can add the following API to make it more user friendly:

• SCollection[T]#toProbFilter[PF[_]](builder: ProbFilter[PF]): SCollection[PF[T]]
• Methods to save/load SCollection[PF[_]] to/from disk

[nevillelyh]

Also another good alternative: Quotient Filter
https://en.wikipedia.org/wiki/Quotient_filter
https://www.usenix.org/legacy/event/hotstorage11/tech/final_files/Bender.pdf
https://www3.cs.stonybrook.edu/~ppandey/files/p775-pandey.pdf

[clairemcginty]

👍 What's the reasoning behind the def build[T](data: Seq[T])(implicit hash: algebird.Hash128[T]): PF[T] signature in ProbFilterBuilder ? How would the caller know which build implementation to use?

Also, maybe we could use some kind of ADT to represent the conditional results of def contains(item: T) instead of a plain boolean? something similar to algebird's ApproximateBoolean ?

[nevillelyh]

The Seq[T] version of build is for in-memory builds so we can easily benchmark insert/lookup performance and fpp/fnp rate.

Yeah contains is the most naive but probably the fastest impl. For BF/CF fpp depends on current load factor and quiet expensive.

Note on Algebird, we'll probably use our own mutable BF and some pure Java CF/QF impl. In that case it's probably better to not depend on any Algebird types in case of 2.13 migration.

[anish749]

For the contains(item: T) we don't want to calculate the approxProb in the ApproximateBoolean every time we are checking for membership. It would be nice to have two separate functions like algebird, contains(item: T): ApproximateBoolean and mayBeContains(item: T): Boolean

[nevillelyh]

Or even just contains(item: T): Boolean and actual{Fpp,Fnp}: Double. Since we only expose the final read-only filter, fpp/fnp should be constant (given final load) and independent from items queried.
A minor benefit is one fewer temp object creation.

[nevillelyh]

I pushed a WIP brach to https://github.com/spotify/scio/tree/neville/filter

[cesarcolle]

hi guys,
Seems like you're interested in CuckooFilter .
I start implement this one, highly inspired of the Algebird's Bloomfilter here => Cuckoo-filter

If you're interested I can optimize / finalize it to your WIP branch.

Thanks

[nevillelyh]

@cesarcolle I've seen that PR and will comment there.

[nevillelyh]

Fixed in #2651