You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@spark.apache.org by "ASF GitHub Bot (Jira)" <ji...@apache.org> on 2024/05/03 21:01:00 UTC
[jira] [Updated] (SPARK-47547) observed false positive rate in bloom filter is greater than expected for large n
[ https://issues.apache.org/jira/browse/SPARK-47547?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
ASF GitHub Bot updated SPARK-47547:
-----------------------------------
Labels: pull-request-available (was: )
> observed false positive rate in bloom filter is greater than expected for large n
> ---------------------------------------------------------------------------------
>
> Key: SPARK-47547
> URL: https://issues.apache.org/jira/browse/SPARK-47547
> Project: Spark
> Issue Type: Bug
> Components: Spark Core
> Affects Versions: 3.5.0
> Reporter: Nathan Conroy
> Priority: Minor
> Labels: pull-request-available
>
> When creating a bloom filter out of a large number of elements (>400 million or so) with an fpp (false positive rate) of 1% in Spark, the observed false positive rate appears to be much higher, as much as 20%.
> This is demonstrated below in this spark shell:
> {noformat}
> ____ __
> / __/__ ___ _____/ /__
> _\ \/ _ \/ _ `/ __/ '_/
> /___/ .__/\_,_/_/ /_/\_\ version 3.5.0-amzn-0
> /_/
>
> Using Scala version 2.12.17 (OpenJDK 64-Bit Server VM, Java 17.0.10)
> Type in expressions to have them evaluated.
> Type :help for more information.
> scala> import java.security.MessageDigest
> import java.security.MessageDigest
> scala> import scala.util.Random
> import scala.util.Random
> scala> import org.apache.spark.util.sketch.BloomFilter
> import org.apache.spark.util.sketch.BloomFilter
> scala>
> scala> // Function to generate a random SHA1 hash
> scala> def generateRandomSha1(): String = {
> | val randomString = Random.alphanumeric.take(20).mkString
> | val sha1 = MessageDigest.getInstance("SHA-1")
> | sha1.update(randomString.getBytes("UTF-8"))
> | val digest = sha1.digest
> | digest.map("%02x".format(_)).mkString
> | }
> generateRandomSha1: ()String
> scala>
> scala> // Generate a DataFrame with 500 million rows of random SHA1 hashes
> scala> val df = spark.range(500000000).map(_ => generateRandomSha1()).toDF("Hash")
> df: org.apache.spark.sql.DataFrame = [Hash: string]
> scala> // Create a bloom filter out of this collection of strings.
> scala> val bloom_filter = df.stat.bloomFilter("Hash", 500000000, 0.01)
> bloom_filter: org.apache.spark.util.sketch.BloomFilter = org.apache.spark.util.sketch.BloomFilterImpl@a14c0ba9
> scala> // Generate another 10,000 random hashes
> scala> val random_sha1s = List.fill(10000)(generateRandomSha1())
> random_sha1s: List[String] = List(f3cbfd9bd836ea917ebc0dfc5330135cfde322a3, 4bff8d58799e517a1ba78236db9b52353dd39b56, 775bdd9d138a79eeae7308617f5c0d1d0e1c1697, abbd761b7768f3cbadbffc0c7947185856c4943d, 343692fe61c552f73ad6bc2d2d3072cc456da1db, faf4430055c528c9a00a46e9fae7dc25047ffaf3, 255b5d56c39bfba861647fff67704e6bc758d683, dae8e0910a368f034958ae232aa5f5285486a8ac, 3680dbd34437ca661592a7e4d39782c9c77fb4ba, f5b43f7a77c9d9ea28101a1848d8b1a1c0a65b82, 5bda825102026bc0da731dc84d56a499ccff0fe1, 158d7b3ce949422de421d5e110e3f6903af4f8e1, 2efcae5cb10273a0f5e89ae34fa3156238ab0555, 8d241012d42097f80f30e8ead227d75ab77086d2, 307495c98ae5f25026b91e60cf51d4f9f1ad7f4b, 8fc2f55563ab67d4ec87ff7b04a4a01e821814a3, b413572d14ee16c6c575ca3472adff62a8cbfa3d, 9219233b0e8afe57d7d5cb6...
> scala> // Check how many of these random hashes return a positive result when passed into mightContain
> scala> random_sha1s.map(c => bloom_filter.mightContain(c)).count(_ == true)
> res0: Int = 2153 {noformat}
> I believe this is the result of the bloom filter implementation using 32bit hashes. Since the maximum value that can be returned by the k hash functions is ~2.14 billion (max integer value in Java), bloom filters with m > ~2.14 billion have degraded performance resulting from not using any bits at indices greater than ~2.14 billion.
> This was a known bug in Guava that was fixed several years ago, but it looks like the fix was never ported to Spark. See [https://github.com/google/guava/issues/1119]
> Of course, using a different hash function strategy would break existing uses of this code, so we should tread with caution here.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org