CheckBloomFilterScalaThreadsafety.scala

import java.util.concurrent.ConcurrentHashMap
import java.util.{Set => JSet}

import scala.jdk.CollectionConverters._
import scala.util.Random
import scala.concurrent.{ExecutionContext, Future}

// https://github.com/alexandrnikitin/bloom-filter-scala
import bloomfilter.mutable.BloomFilter

/* Program to try to find incorrect results from `BloomFilter` due to not being thread-safe.
 * 
 *   - in a whole bunch of futures that are mostly executed in parallel, write values into
 *     the bloom filter and into a concurrent set 
 *
 *   - then, list out all of the values in the set and make sure that `mightContain` from
 *     the bloom filter always returns `true`
 */
object Main extends App {

  val expectedElements = 100000
  val falsePositiveRate = 0.4

  val authoritative: JSet[String] = ConcurrentHashMap.newKeySet[String]()
  val bloom: BloomFilter[String] = BloomFilter[String](expectedElements, falsePositiveRate)

  implicit val ec: ExecutionContext = ExecutionContext.global
  Future
    .traverse(Vector.tabulate(expectedElements / 100)(new Random(_))) { (random: Random) =>
      Future {
        for (i <- 0 until 100) {
          val nextS = random.nextString(10)
          authoritative.add(nextS)
          bloom.add(nextS)
        }
      }
    }
    .map { _ =>
      for (definitelyIn <- authoritative.iterator.asScala) {
        if (!bloom.mightContain(definitelyIn)) {
          println(s"`bloom.mightContain($definitelyIn) = false` is wrong!")
        }
      }
    }
}

sample-output.txt

$ sbt run
[info] welcome to sbt 1.5.5 (AdoptOpenJDK Java 16)
[info] loading settings for project global-plugins from metals.sbt ...
[info] loading global plugins from /Users/atheriault/.sbt/1.0/plugins
[info] loading project definition from /Users/atheriault/Scratch/is-bloom-filter-scala-threadsafe/project
[info] loading settings for project root from build.sbt ...
[info] set current project to is-bloom-filter-scala-threadsafe (in build file:/Users/atheriault/Scratch/is-bloom-filter-scala-threadsafe/)
[info] running example.Main
`bloom.mightContain(冃锁楎㊐碘뱧싖屔䅬삆) = false` is wrong!
`bloom.mightContain(ӧ僣ぽ紹퇝텿䰭ꎼ㟔廋) = false` is wrong!
`bloom.mightContain(厅⍣鼿寑긃꩔뫜腥ꔘ괒) = false` is wrong!
`bloom.mightContain(樣☧鹇㷩䓸预먠숧㋨乛) = false` is wrong!
`bloom.mightContain(과⦝ƍ萍 false` is wrong!
[success] Total time: 1 s, completed Jul 15, 2021, 3:47:06 PM