You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by re...@apache.org on 2025/08/06 10:14:58 UTC
(jackrabbit-oak) 01/01: OAK-11842: Copy Bloom Filter implementation from oak-run-commons to oak-commons for re-use
This is an automated email from the ASF dual-hosted git repository.
reschke pushed a commit to branch OAK-11842
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git
commit e2e16c1a826561dcd37c6b8bc8fee7d942bf4303
Author: Julian Reschke <ju...@gmx.de>
AuthorDate: Wed Aug 6 11:14:36 2025 +0100
OAK-11842: Copy Bloom Filter implementation from oak-run-commons to oak-commons for re-use
---
.../jackrabbit/oak/spi/blob/split/BlobIdSet.java | 16 +-
oak-commons/pom.xml | 4 +
.../oak/commons/collections/BloomFilter.java | 188 +++++++++++++++++++
.../oak/commons/collections/HashUtils.java | 86 +++++++++
.../oak/commons/collections/HyperLogLog.java | 95 ++++++++++
.../oak/commons/collections/package-info.java | 2 +-
.../oak/commons/collections/BloomFilterTest.java | 200 +++++++++++++++++++++
.../oak/commons/collections/HyperLogLogTest.java | 161 +++++++++++++++++
oak-run-commons/pom.xml | 5 +
.../flatfile/analysis/modules/BinaryId.java | 8 +-
.../analysis/modules/DistinctBinarySize.java | 4 +-
.../modules/DistinctBinarySizeHistogram.java | 2 +-
.../flatfile/analysis/modules/PropertyStats.java | 4 +-
.../flatfile/analysis/utils/TopKValues.java | 3 +-
.../index/indexer/document/tree/Prefetcher.java | 6 +-
.../analysis/modules/PropertyStatsTest.java | 2 +-
.../analysis/utils/CountMinSketchTest.java | 5 +-
.../flatfile/analysis/utils/TopKValuesTest.java | 10 +-
.../document/cache/CacheChangesTracker.java | 44 ++---
19 files changed, 789 insertions(+), 56 deletions(-)
diff --git a/oak-blob/src/main/java/org/apache/jackrabbit/oak/spi/blob/split/BlobIdSet.java b/oak-blob/src/main/java/org/apache/jackrabbit/oak/spi/blob/split/BlobIdSet.java
index e62084fcfe..49acb59232 100644
--- a/oak-blob/src/main/java/org/apache/jackrabbit/oak/spi/blob/split/BlobIdSet.java
+++ b/oak-blob/src/main/java/org/apache/jackrabbit/oak/spi/blob/split/BlobIdSet.java
@@ -25,7 +25,6 @@ import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
-import java.nio.charset.StandardCharsets;
import org.apache.commons.io.IOUtils;
import org.slf4j.Logger;
@@ -33,8 +32,7 @@ import org.slf4j.LoggerFactory;
import org.apache.jackrabbit.guava.common.cache.Cache;
import org.apache.jackrabbit.guava.common.cache.CacheBuilder;
-import org.apache.jackrabbit.guava.common.hash.BloomFilter;
-import org.apache.jackrabbit.guava.common.hash.Funnels;
+import org.apache.jackrabbit.oak.commons.collections.BloomFilter;
class BlobIdSet {
@@ -42,19 +40,19 @@ class BlobIdSet {
private final File store;
- private final BloomFilter<CharSequence> bloomFilter;
+ private final BloomFilter bloomFilter;
private final Cache<String, Boolean> cache;
BlobIdSet(String repositoryDir, String filename) {
store = new File(new File(repositoryDir), filename);
- bloomFilter = BloomFilter.create(Funnels.stringFunnel(StandardCharsets.UTF_8), 9000000); // about 8MB
+ bloomFilter = BloomFilter.construct(9000000, 0.03); // 9M entries, 3% false positive rate
cache = CacheBuilder.newBuilder().maximumSize(1000).build();
fillBloomFilter();
}
synchronized boolean contains(String blobId) throws IOException {
- if (!bloomFilter.apply(blobId)) {
+ if (!bloomFilter.mayContain(blobId)) {
return false;
}
Boolean cached = cache.getIfPresent(blobId);
@@ -64,7 +62,7 @@ class BlobIdSet {
if (isPresentInStore(blobId)) {
cache.put(blobId, Boolean.TRUE);
- bloomFilter.put(blobId);
+ bloomFilter.add(blobId);
return true;
} else {
cache.put(blobId, Boolean.FALSE);
@@ -74,7 +72,7 @@ class BlobIdSet {
synchronized void add(String blobId) throws IOException {
addToStore(blobId);
- bloomFilter.put(blobId);
+ bloomFilter.add(blobId);
cache.put(blobId, Boolean.TRUE);
}
@@ -114,7 +112,7 @@ class BlobIdSet {
reader = new BufferedReader(new FileReader(store));
String line;
while ((line = reader.readLine()) != null) {
- bloomFilter.put(line);
+ bloomFilter.add(line);
}
} catch (IOException e) {
log.error("Can't fill bloom filter", e);
diff --git a/oak-commons/pom.xml b/oak-commons/pom.xml
index 5e8396cd65..8b774a03dc 100644
--- a/oak-commons/pom.xml
+++ b/oak-commons/pom.xml
@@ -102,6 +102,10 @@
<groupId>org.apache.commons</groupId>
<artifactId>commons-collections4</artifactId>
</dependency>
+ <dependency>
+ <groupId>commons-codec</groupId>
+ <artifactId>commons-codec</artifactId>
+ </dependency>
<dependency>
<groupId>org.apache.jackrabbit</groupId>
<artifactId>jackrabbit-jcr-commons</artifactId>
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/BloomFilter.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/BloomFilter.java
new file mode 100644
index 0000000000..3c266ea1bb
--- /dev/null
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/BloomFilter.java
@@ -0,0 +1,188 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.commons.collections;
+
+/**
+ * A Bloom filter implementation.
+ */
+public class BloomFilter {
+
+ private final int k;
+ private final int arraySize;
+ private final long[] data;
+
+ private BloomFilter(long[] data, int k) {
+ this.data = data;
+ this.k = k;
+ this.arraySize = data.length;
+ }
+
+ /**
+ * Construct a Bloom filter. With a fpp of 0.01, the memory usage is roughly 1
+ * byte per entry.
+ *
+ * @param bytes the size in number of bytes (eg. 64_000_000 for 64 MB memory
+ * usage)
+ * @param fpp the false-positive probability (eg. 0.01 for a 1% false-positive
+ * probability)
+ * @return the Bloom filter
+ */
+ public static BloomFilter construct(long n, double fpp) {
+ if (n <= 0) {
+ throw new IllegalArgumentException("n must be greater than 0");
+ }
+ if (fpp <= 0 || fpp >= 1) {
+ throw new IllegalArgumentException("fpp must be between 0 and 1");
+ }
+ long m = calculateBits(n, fpp);
+ int k = calculateK((double) m / n);
+ return new BloomFilter(new long[(int) ((m + 63) / 64)], k);
+ }
+
+ // See also https://hur.st/bloomfilter
+
+ /**
+ * Calculate the best k parameter for a Bloom filter.
+ *
+ * @param bitsPerKey the number of bits per key (eg. 10)
+ * @return the k parameter
+ */
+ public static int calculateK(double bitsPerKey) {
+ return Math.max(1, (int) Math.round(bitsPerKey * Math.log(2)));
+ }
+
+ /**
+ * Calculate the number of bits needed for a Bloom filter, given a number of entries and the k parameter.
+ *
+ * @param n the number of entries (eg. 1_000_000)
+ * @param fpp the false positive probability (eg. 0.01)
+ * @return the bits needed
+ */
+ public static long calculateBits(long n, double fpp) {
+ return (long) Math.ceil((n * Math.log(fpp)) / Math.log(1 / Math.pow(2, Math.log(2))));
+ }
+
+ /**
+ * Calculate the maximum number of entries in the set, given the the memory size
+ * in bits, and a target false positive probability.
+ *
+ * @param bits the number of bits (eg. 10_000_000)
+ * @param fpp the false positive probability (eg. 0.01)
+ * @return the maximum number of entries to be added
+ */
+ public static long calculateN(long bits, double fpp) {
+ return (long) Math.ceil((bits * Math.log(Math.pow(0.5, Math.log(2))) / Math.log(fpp)));
+ }
+
+ /**
+ * Calculate the false positive probability.
+ *
+ * @param bits the number of bits (eg. 10_000_000)
+ * @param fpp the false positive probability (eg. 0.01)
+ * @return the maximum number of entries to be added
+ */
+ public static double calculateFpp(long n, long bits, int k) {
+ // p = pow(1 - exp(-k / (m / n)), k)
+ return Math.pow(1 - Math.exp(-k / ((double) bits / n)), k);
+ }
+
+ /**
+ * Add an entry, using an int hash code.
+ *
+ * @param value the value to check
+ */
+ public void add(String value) {
+ add(HashUtils.hash64(value));
+ }
+
+ /**
+ * Add an entry.
+ *
+ * @param hash the hash value (need to be a high quality hash code, with all
+ * bits having high entropy)
+ */
+ public void add(long hash) {
+ long a = (hash >>> 32) | (hash << 32);
+ long b = hash;
+ for (int i = 0; i < k; i++) {
+ data[HashUtils.reduce((int) (a >>> 32), arraySize)] |= 1L << a;
+ a += b;
+ }
+ }
+
+ /**
+ * Whether the entry may be in the set.
+ *
+ * @param value the value to check
+ * @return true if the entry was added, or, with a certain false positive
+ * probability, even if it was not added
+ */
+ public boolean mayContain(String value) {
+ return mayContain(HashUtils.hash64(value));
+ }
+
+ /**
+ * Whether the entry may be in the set.
+ *
+ * @param hash the hash value (need to be a high quality hash code, with all
+ * bits having high entropy)
+ * @return true if the entry was added, or, with a certain false positive
+ * probability, even if it was not added
+ */
+ public boolean mayContain(long hash) {
+ long a = (hash >>> 32) | (hash << 32);
+ long b = hash;
+ for (int i = 0; i < k; i++) {
+ if ((data[HashUtils.reduce((int) (a >>> 32), arraySize)] & 1L << a) == 0) {
+ return false;
+ }
+ a += b;
+ }
+ return true;
+ }
+
+ /**
+ * Get the number of bits needed for the array.
+ *
+ * @return the number of bits
+ */
+ public long getBitCount() {
+ return data.length * 64L;
+ }
+
+ public int getK() {
+ return k;
+ }
+
+ /**
+ * Get the estimated entry count (number of distinct items added). This
+ * operation is relatively slow, as it loops over all the entries.
+ *
+ * @return the estimated entry count, or Long.MAX_VALUE if the number can not be estimated.
+ */
+ public long getEstimatedEntryCount() {
+ long x = 0;
+ for (long d : data) {
+ x += Long.bitCount(d);
+ }
+ double m = getBitCount();
+ return (long) (-(m / k) * Math.log(1 - (x / m)));
+ }
+
+}
\ No newline at end of file
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HashUtils.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HashUtils.java
new file mode 100644
index 0000000000..90d998664c
--- /dev/null
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HashUtils.java
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.commons.collections;
+
+import java.nio.charset.StandardCharsets;
+import org.apache.commons.codec.digest.MurmurHash3;
+
+/**
+ * A hash function utility class.
+ */
+public class HashUtils {
+
+ private HashUtils() {
+ // utility class
+ }
+
+ /**
+ * Calculate a 64-bit hash value from a string.
+ *
+ * @param s the string
+ * @return the hash value
+ */
+ public static long hash64(String s) {
+ return MurmurHash3.hash128(s.getBytes(StandardCharsets.UTF_8))[0];
+ }
+
+ /**
+ * Calculate a 64-bit hash value from a value, using a seed.
+ *
+ * The current algorithm used the finalizer of the MurmurHash3 hash function,
+ * but callers shouldn't rely on that.
+ *
+ * @param x the value
+ * @param seed the seed
+ * @return the hash value
+ */
+ public static long hash64(long x, long seed) {
+ x += seed;
+ x = (x ^ (x >>> 33)) * 0xff51afd7ed558ccdL;
+ x = (x ^ (x >>> 33)) * 0xc4ceb9fe1a85ec53L;
+ x = x ^ (x >>> 33);
+ return x;
+ }
+
+ /**
+ * Calculate a 64-bit hash value from a value. The input is a 64-bit value and
+ * the output is a 64-bit values. Two different inputs are never mapped to the
+ * same output. The operation is reversible.
+ *
+ * @param x the value
+ * @return the hash value
+ */
+ public static long hash64(long x) {
+ return hash64(x, 100);
+ }
+
+ /**
+ * Shrink the hash to a value 0..n. Kind of like modulo, but using
+ * multiplication and shift, which are faster to compute.
+ *
+ * @param hash the hash
+ * @param n the maximum of the result
+ * @return the reduced value
+ */
+ public static int reduce(int hash, int n) {
+ // http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
+ return (int) (((hash & 0xffffffffL) * (n & 0xffffffffL)) >>> 32);
+ }
+
+}
\ No newline at end of file
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLog.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLog.java
new file mode 100644
index 0000000000..2054decff0
--- /dev/null
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLog.java
@@ -0,0 +1,95 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.commons.collections;
+
+import java.util.HashSet;
+
+/**
+ * A HyperLogLog implementation.
+ */
+public class HyperLogLog {
+
+ private final double amm2;
+ private final int m;
+ private final byte[] counters;
+ private final int maxSmallSetSize;
+ private HashSet<Long> smallSet;
+
+ public HyperLogLog(int m, int maxSmallSetSize) {
+ this.maxSmallSetSize = maxSmallSetSize;
+ if (maxSmallSetSize > 0) {
+ smallSet = new HashSet<>();
+ } else {
+ smallSet = null;
+ }
+ if (m < 16) {
+ throw new IllegalArgumentException("Must be >= 16, is " + m);
+ }
+ if (Integer.bitCount(m) != 1) {
+ throw new IllegalArgumentException("Must be a power of 2, is " + m);
+ }
+ this.m = m;
+ double am;
+ switch (m) {
+ case 32:
+ am = 0.697;
+ break;
+ case 64:
+ am = 0.709;
+ break;
+ default:
+ am = 0.7213 / (1.0 + 1.079 / m);
+ }
+ amm2 = am * m * m;
+ this.counters = new byte[m];
+ }
+
+ public void add(long hash) {
+ if (smallSet != null) {
+ smallSet.add(hash);
+ if (smallSet.size() > maxSmallSetSize) {
+ smallSet = null;
+ }
+ }
+ int i = (int) (hash & (m - 1));
+ counters[i] = (byte) Math.max(counters[i], 1 + Long.numberOfLeadingZeros(hash));
+ }
+
+ public long estimate() {
+ if (smallSet != null) {
+ return smallSet.size();
+ }
+ double sum = 0;
+ int countZero = 0;
+ for(int c : counters) {
+ countZero += c == 0 ? 1 : 0;
+ sum += 1. / (1L << (c & 0xff));
+ }
+ if (sum == 0) {
+ sum = 1;
+ }
+ long est = (long) (1. / sum * amm2);
+ if (est <= 5 * m && countZero > 0) {
+ // linear counting
+ est = (long) (m * Math.log((double) m / countZero));
+ }
+ return est;
+ }
+
+}
\ No newline at end of file
diff --git a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/package-info.java b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/package-info.java
index 81c20db5ca..5d1490f210 100644
--- a/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/package-info.java
+++ b/oak-commons/src/main/java/org/apache/jackrabbit/oak/commons/collections/package-info.java
@@ -21,7 +21,7 @@
* Utilities for Java collections and streams.
*/
@Internal(since = "1.0.0")
-@Version("2.2.0")
+@Version("2.3.0")
package org.apache.jackrabbit.oak.commons.collections;
import org.apache.jackrabbit.oak.commons.annotations.Internal;
import org.osgi.annotation.versioning.Version;
diff --git a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/BloomFilterTest.java b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/BloomFilterTest.java
new file mode 100644
index 0000000000..464de8c4ef
--- /dev/null
+++ b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/BloomFilterTest.java
@@ -0,0 +1,200 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.commons.collections;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertTrue;
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertThrows;
+
+import org.junit.Test;
+
+/**
+ * Tests the Bloom filter implementation.
+ */
+public class BloomFilterTest {
+
+ @Test
+ public void calculateBits() {
+ assertEquals(9_585_059, BloomFilter.calculateBits(1_000_000, 0.01));
+ // test some extreme values
+ assertEquals(0, BloomFilter.calculateBits(1, 1.0));
+ assertEquals(1, BloomFilter.calculateBits(1, 0.99));
+ assertEquals(0, BloomFilter.calculateBits(0, 0.0));
+ assertTrue(BloomFilter.calculateBits(Integer.MAX_VALUE, 0.0) > Integer.MAX_VALUE);
+ }
+
+ @Test
+ public void calculateK() {
+ assertEquals(7, BloomFilter.calculateK(10));
+ // test some extreme values
+ assertEquals(1, BloomFilter.calculateK(1));
+ assertEquals(1, BloomFilter.calculateK(0));
+ assertEquals(69, BloomFilter.calculateK(100));
+ }
+
+ @Test
+ public void calculateN() {
+ assertEquals(11, BloomFilter.calculateN(100, 0.01));
+ // test some extreme values
+ assertEquals(1, BloomFilter.calculateN(1, 0.01));
+ assertEquals(1, BloomFilter.calculateN(1, 0.1));
+ assertEquals(0, BloomFilter.calculateN(0, 0.01));
+ }
+
+ @Test
+ public void construct() {
+ BloomFilter f = BloomFilter.construct(100, 0.01);
+ assertEquals(960, f.getBitCount());
+ assertEquals(7, f.getK());
+ }
+
+ @Test
+ public void fpp() {
+ for (double fpp = 0.001; fpp < 1; fpp *= 2) {
+ int size = 500_000;
+ BloomFilter f = BloomFilter.construct(size, fpp);
+ for (int i = 0; i < size; i++) {
+ f.add(HashUtils.hash64(i));
+ }
+ for (int i = 0; i < size; i++) {
+ assertTrue(f.mayContain(HashUtils.hash64(i)));
+ }
+ int falsePositives = 0;
+ for (int i = 0; i < size; i++) {
+ if (f.mayContain(HashUtils.hash64(i + size))) {
+ falsePositives++;
+ }
+ }
+ double realFpp = (double) falsePositives / size;
+ // expected to be within 10%
+ assertTrue("expected fpp: " + fpp + " got: " + realFpp, realFpp >= fpp * 0.9 && realFpp <= fpp * 1.1);
+ long est = f.getEstimatedEntryCount();
+ assertTrue("expected n: " + size + " got: " + est, size >= est * 0.9 && size <= est * 1.1);
+
+ double fpp2 = BloomFilter.calculateFpp(size, f.getBitCount(), f.getK());
+ assertTrue("expected fpp: " + fpp + " got: " + fpp2, fpp2 >= fpp * 0.9 && fpp2 <= fpp * 1.1);
+ }
+ }
+
+ @Test
+ public void estimatedEntryCount() {
+ // let's assume we have a 1 KB Bloom filter with a false positive rate of 1%:
+ double fpp = 0.01;
+ long bits = 1000 * 8;
+ long n = BloomFilter.calculateN(bits, fpp);
+ BloomFilter bloom = BloomFilter.construct(n, fpp);
+ // and a HyperLogLog of 1 KB:
+ HyperLogLog hll = new HyperLogLog(1024, 0);
+ // now we calculate estimations with both the Bloom filter and HyperLogLog
+ for(int i = 0; i < 20_000; i++) {
+ long x = HashUtils.hash64(i);
+ bloom.add(x);
+ hll.add(x);
+ if (i > 0 && i % 1000 == 0) {
+ long estBloom = bloom.getEstimatedEntryCount();
+ long estHll = hll.estimate();
+ int errBloom = (int) (Math.abs((double) i / estBloom - 1) * 10000);
+ int errHll = (int) (Math.abs((double) i / estHll - 1) * 10000);
+ if (i < 10_000) {
+ assertTrue(errBloom < 1000);
+ } else {
+ assertEquals(Long.MAX_VALUE, estBloom);
+ }
+ assertTrue(errHll < 1000);
+ }
+ }
+ }
+
+ @Test
+ public void filterFunctionality() {
+ BloomFilter filter = BloomFilter.construct(100, 0.01);
+ String testValue = "test-value";
+
+ // Initially should not contain anything
+ assertFalse(filter.mayContain(testValue));
+
+ // Add the item and verify it's found
+ filter.add(testValue);
+ assertTrue(filter.mayContain(testValue));
+
+ // Verify another value is not found
+ assertFalse(filter.mayContain("different-value"));
+ }
+
+ @Test
+ public void filterWithMultipleEntries() {
+ BloomFilter filter = BloomFilter.construct(100, 0.01);
+
+ // Add multiple entries
+ for (int i = 0; i < 100; i++) {
+ filter.add("value-" + i);
+ }
+
+ // Verify all entries are found
+ for (int i = 0; i < 100; i++) {
+ assertTrue(filter.mayContain("value-" + i));
+ }
+ }
+
+ @Test
+ public void falsePositiveProbability() {
+ // Create a filter with high false positive probability for testing
+ double fpp = 0.3;
+ BloomFilter filter = BloomFilter.construct(100, fpp);
+
+ // Fill the filter to capacity
+ for (int i = 0; i < 100; i++) {
+ filter.add("existing-" + i);
+ }
+
+ // Test with values not in the filter
+ int falsePositives = 0;
+ int trials = 1000;
+
+ for (int i = 0; i < trials; i++) {
+ if (filter.mayContain("nonexistent-" + i)) {
+ falsePositives++;
+ }
+ }
+
+ // The false positive rate should be approximately fpp
+ double actualFpp = (double) falsePositives / trials;
+ assertTrue("False positive rate should be close to expected, got " + actualFpp + " expected " + fpp, Math.abs(actualFpp - fpp) < 0.15);
+ }
+
+ @Test
+ public void invalidEntries() {
+ // Should throw exception for entries < 1
+ assertThrows(IllegalArgumentException.class,() -> BloomFilter.construct(0, 0.01));
+ }
+
+ @Test
+ public void invalidFppZero() {
+ // Should throw exception for fpp <= 0
+ assertThrows(IllegalArgumentException.class,() -> BloomFilter.construct(100, 0.0));
+ }
+
+ @Test
+ public void invalidFppOne() {
+ // Should throw exception for fpp >= 1
+ assertThrows(IllegalArgumentException.class,() -> BloomFilter.construct(100, 1.0));
+ }
+
+}
\ No newline at end of file
diff --git a/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLogTest.java b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLogTest.java
new file mode 100644
index 0000000000..fd3fb39bff
--- /dev/null
+++ b/oak-commons/src/test/java/org/apache/jackrabbit/oak/commons/collections/HyperLogLogTest.java
@@ -0,0 +1,161 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.jackrabbit.oak.commons.collections;
+
+import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
+
+import org.junit.Test;
+
+public class HyperLogLogTest {
+
+ @Test(expected = IllegalArgumentException.class)
+ public void illegalHyperLogLogTooSmall() {
+ new HyperLogLog(8, 0);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void illegalHyperLogLogNotPowerOfTwo() {
+ new HyperLogLog(30, 0);
+ }
+
+ @Test
+ public void smallSet() {
+ HyperLogLog hll100 = new HyperLogLog(16, 100);
+ assertEquals(0, hll100.estimate());
+ HyperLogLog hll0 = new HyperLogLog(16, 0);
+ assertEquals(0, hll0.estimate());
+ for (int i = 0; i < 10_000; i++) {
+ hll100.add(i % 100);
+ hll0.add(i % 100);
+ }
+ assertEquals(100, hll100.estimate());
+ assertNotEquals(100, hll0.estimate());
+ }
+
+ @Test
+ public void test() {
+ int testCount = 50;
+ for (int m = 16; m <= 128; m *= 2) {
+ double avg = Math.sqrt(averageOverRange(m, 30_000, testCount, false, 2));
+ int min, max;
+ switch (m) {
+ case 16:
+ min = 22;
+ max = 23;
+ break;
+ case 32:
+ min = 15;
+ max = 16;
+ break;
+ case 64:
+ min = 10;
+ max = 11;
+ break;
+ case 128:
+ min = 7;
+ max = 8;
+ break;
+ default:
+ min = 0;
+ max = 0;
+ break;
+ }
+ assertTrue("m " + m + " expected " + min + ".." + max + " got " + avg, min < avg && avg < max);
+ }
+ }
+
+ private static double averageOverRange(int m, long maxSize, int testCount, boolean debug, double exponent) {
+ double sum = 0;
+ int count = 0;
+ for (long size = 1; size <= 20; size++) {
+ sum += test(m, size, testCount, debug, exponent);
+ count++;
+ }
+ for (long size = 22; size <= 300; size += size / 5) {
+ sum += test(m, size, testCount, debug, exponent);
+ count++;
+ }
+ for (long size = 400; size <= maxSize; size *= 2) {
+ sum += test(m, size, testCount, debug, exponent);
+ count++;
+ }
+ return sum / count;
+ }
+
+ private static double test(int m, long size, int testCount, boolean debug, double exponent) {
+ long x = 0;
+ long min = Long.MAX_VALUE, max = Long.MIN_VALUE;
+ long ns = System.nanoTime();
+ double sumSquareError = 0;
+ double sum = 0;
+ double sumFirst = 0;
+ int repeat = 10;
+ int runs = 2;
+ for (int test = 0; test < testCount; test++) {
+ HyperLogLog hll;
+ hll = new HyperLogLog(m, 0);
+ long baseX = x;
+ for (int i = 0; i < size; i++) {
+ hll.add(HashUtils.hash64(x));
+ x++;
+ }
+ long e = hll.estimate();
+ sum += e;
+ min = Math.min(min, e);
+ max = Math.max(max, e);
+ long error = e - size;
+ sumSquareError += error * error;
+ sumFirst += e;
+ for (int add = 0; add < repeat; add++) {
+ long x2 = baseX;
+ for (int i = 0; i < size; i++) {
+ hll.add(HashUtils.hash64(x2));
+ x2++;
+ }
+ }
+ e = hll.estimate();
+ sum += e;
+ min = Math.min(min, e);
+ max = Math.max(max, e);
+ error = e - size;
+ sumSquareError += error * error;
+ }
+ ns = System.nanoTime() - ns;
+ long nsPerItem = ns / testCount / runs / (1 + repeat) / size;
+ double stdDev = Math.sqrt(sumSquareError / testCount / runs);
+ double relStdDevP = stdDev / size * 100;
+ int biasFirstP = (int) (100 * (sumFirst / testCount / size) - 100);
+ int biasP = (int) (100 * (sum / testCount / runs / size) - 100);
+ if (debug) {
+ System.out.println("m " + m + " size " + size + " relStdDev% " + (int) relStdDevP +
+ " range " + min + ".." + max +
+ " biasFirst% " + biasFirstP +
+ " bias% " + biasP +
+ " avg " + (sum / testCount / runs) +
+ " time " + nsPerItem);
+ }
+ // we try to reduce the relStdDevP, make sure there are no large values
+ // (trying to reduce sumSquareError directly
+ // would mean we care more about larger sets, but we don't)
+ return Math.pow(relStdDevP, exponent);
+ }
+
+}
\ No newline at end of file
diff --git a/oak-run-commons/pom.xml b/oak-run-commons/pom.xml
index e1288dccc2..efd3657e51 100644
--- a/oak-run-commons/pom.xml
+++ b/oak-run-commons/pom.xml
@@ -110,6 +110,11 @@
<artifactId>oak-jcr</artifactId>
<version>${project.version}</version>
</dependency>
+ <dependency>
+ <groupId>org.apache.jackrabbit</groupId>
+ <artifactId>oak-commons</artifactId>
+ <version>${project.version}</version>
+ </dependency>
<dependency>
<groupId>org.jetbrains</groupId>
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinaryId.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinaryId.java
index 3ec93f175d..741c1cceae 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinaryId.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/BinaryId.java
@@ -20,7 +20,7 @@ package org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.modul
import java.util.Objects;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.Hash;
+import org.apache.jackrabbit.oak.commons.collections.HashUtils;
/**
* A binary id.
@@ -51,9 +51,9 @@ public class BinaryId {
// we need to hash again because some of the bits are fixed
// in case of UUIDs: always a "4" here: xxxxxxxx-xxxx-4xxx
// (the hash64 is a reversible mapping, so there is no risk of conflicts)
- this.v0 = Hash.hash64(Long.parseUnsignedLong(buff.substring(0, 16), 16));
- this.v1 = Hash.hash64(Long.parseUnsignedLong(buff.substring(16, 32), 16));
- this.v2 = Hash.hash64(Long.parseUnsignedLong(buff.substring(32, Math.min(48, buff.length())), 16));
+ this.v0 = HashUtils.hash64(Long.parseUnsignedLong(buff.substring(0, 16), 16));
+ this.v1 = HashUtils.hash64(Long.parseUnsignedLong(buff.substring(16, 32), 16));
+ this.v2 = HashUtils.hash64(Long.parseUnsignedLong(buff.substring(32, Math.min(48, buff.length())), 16));
}
@Override
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySize.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySize.java
index 272c7f357b..878375f1f8 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySize.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySize.java
@@ -28,8 +28,8 @@ import java.util.stream.Collectors;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeData;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeProperty;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeProperty.ValueType;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.BloomFilter;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.HyperLogLog;
+import org.apache.jackrabbit.oak.commons.collections.BloomFilter;
+import org.apache.jackrabbit.oak.commons.collections.HyperLogLog;
/**
* Collects the number and size of distinct binaries.
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySizeHistogram.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySizeHistogram.java
index 349a3fe35b..061aa39d52 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySizeHistogram.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/DistinctBinarySizeHistogram.java
@@ -27,7 +27,7 @@ import java.util.stream.Collectors;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeData;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeProperty;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeProperty.ValueType;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.HyperLogLog;
+import org.apache.jackrabbit.oak.commons.collections.HyperLogLog;
/**
* A histogram of distinct binaries. For each size range, we calculate the
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java
index 80227f5744..c749a1ab59 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStats.java
@@ -31,7 +31,7 @@ import java.util.stream.Collectors;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeData;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.stream.NodeProperty;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.Hash;
+import org.apache.jackrabbit.oak.commons.collections.HashUtils;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.HyperLogLog3Linear64;
import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.TopKValues;
@@ -123,7 +123,7 @@ public class PropertyStats implements StatsCollector {
stats.values += p.getValues().length;
if (stats.count > MIN_PROPERTY_COUNT) {
for (String v : p.getValues()) {
- long hash = Hash.hash64(v.hashCode(), seed);
+ long hash = HashUtils.hash64(v.hashCode(), seed);
stats.hll = HyperLogLog3Linear64.add(stats.hll, hash);
stats.size += v.length();
stats.maxSize = Math.max(stats.maxSize, v.length());
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValues.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValues.java
index 2c235f2197..48b4a63b0b 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValues.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValues.java
@@ -21,6 +21,7 @@ package org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils
import java.util.ArrayList;
import java.util.HashMap;
+import org.apache.jackrabbit.oak.commons.collections.HashUtils;
import org.apache.jackrabbit.oak.commons.json.JsopBuilder;
/**
@@ -91,7 +92,7 @@ public class TopKValues {
if (countedCount > 1000) {
skipRemaining = SKIP;
}
- long hash = Hash.hash64(value.hashCode());
+ long hash = HashUtils.hash64(value);
long est = sketch.addAndEstimate(hash);
if (est < min) {
return;
diff --git a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/tree/Prefetcher.java b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/tree/Prefetcher.java
index 10992f5c06..8f4e6d2cac 100644
--- a/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/tree/Prefetcher.java
+++ b/oak-run-commons/src/main/java/org/apache/jackrabbit/oak/index/indexer/document/tree/Prefetcher.java
@@ -34,8 +34,8 @@ import org.apache.jackrabbit.oak.api.Blob;
import org.apache.jackrabbit.oak.api.PropertyState;
import org.apache.jackrabbit.oak.api.Type;
import org.apache.jackrabbit.oak.index.indexer.document.NodeStateEntry;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.Hash;
-import org.apache.jackrabbit.oak.index.indexer.document.flatfile.analysis.utils.HyperLogLog;
+import org.apache.jackrabbit.oak.commons.collections.HashUtils;
+import org.apache.jackrabbit.oak.commons.collections.HyperLogLog;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
@@ -240,7 +240,7 @@ public class Prefetcher {
// and then we use a secondary hash
// otherwise the estimation is way off
int h = blob.getContentIdentity().hashCode();
- return Hash.hash64(h | (blob.length() << 32));
+ return HashUtils.hash64(h | (blob.length() << 32));
}
static enum PrefetchType {
diff --git a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStatsTest.java b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStatsTest.java
index 7803a54400..5fe819335d 100644
--- a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStatsTest.java
+++ b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/modules/PropertyStatsTest.java
@@ -67,7 +67,7 @@ public class PropertyStatsTest {
pc.add(n);
}
assertEquals("PropertyStats\n"
- + "skewed weight 3 count 1000000 distinct 394382 avgSize 7 maxSize 11 top {\"skipped\":899091,\"counted\":90910,\"false\":25583,\"true\":25518,\"-411461567\":1,\"1483286044\":1,\"1310925467\":1,\"-1752252714\":1,\"-1433290908\":1,\"-1209544007\":1}\n"
+ + "skewed weight 3 count 1000000 distinct 394382 avgSize 7 maxSize 11 top {\"skipped\":899091,\"counted\":90910,\"false\":25618,\"true\":25543,\"-411461567\":1,\"1483286044\":1,\"1310925467\":1,\"-1752252714\":1,\"-1433290908\":1,\"-1209544007\":1}\n"
+ "", pc.toString());
}
diff --git a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/CountMinSketchTest.java b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/CountMinSketchTest.java
index 92935ca286..212c0fba22 100644
--- a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/CountMinSketchTest.java
+++ b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/CountMinSketchTest.java
@@ -24,6 +24,7 @@ import static org.junit.Assert.assertTrue;
import java.util.Arrays;
import java.util.Random;
+import org.apache.jackrabbit.oak.commons.collections.HashUtils;
import org.junit.Test;
public class CountMinSketchTest {
@@ -83,11 +84,11 @@ public class CountMinSketchTest {
}
CountMinSketch est = new CountMinSketch(5, 16);
for (int i = 0; i < size; i++) {
- est.add(Hash.hash64(x + data[i]));
+ est.add(HashUtils.hash64(x + data[i]));
}
int[] counts = getCounts(data);
for (int i = 0; i < 10; i++) {
- long e = est.estimate(Hash.hash64(x + i));
+ long e = est.estimate(HashUtils.hash64(x + i));
long expectedPercent = (int) (100. * counts[i] / size);
long estPercent = (int) (100. * e / size);
if (debug) {
diff --git a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValuesTest.java b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValuesTest.java
index 696e2e724f..dfd36a6eba 100644
--- a/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValuesTest.java
+++ b/oak-run-commons/src/test/java/org/apache/jackrabbit/oak/index/indexer/document/flatfile/analysis/utils/TopKValuesTest.java
@@ -30,17 +30,17 @@ public class TopKValuesTest {
public void test() {
TopKValues v = new TopKValues(3);
Random r = new Random(1);
- for(int i=0; i<1000000; i++) {
- if(r.nextBoolean()) {
+ for (int i = 0; i < 1000000; i++) {
+ if (r.nextBoolean()) {
v.add("common" + r.nextInt(2));
} else {
v.add("rare" + r.nextInt(100));
}
}
- assertEquals("{\"notSkewed\":5,\"skipped\":908191,\"counted\":91809,\"common1\":24849,\"common0\":24652,\"rare13\":2374}", v.toString());
+ assertEquals("{\"notSkewed\":5,\"skipped\":908191,\"counted\":91809,\"common0\":24231,\"common1\":23844,\"rare13\":2722}", v.toString());
assertEquals(91809, v.getCount());
- assertEquals(24849, v.getTopCount());
- assertEquals(24652, v.getSecondCount());
+ assertEquals(24231, v.getTopCount());
+ assertEquals(23844, v.getSecondCount());
}
}
diff --git a/oak-store-document/src/main/java/org/apache/jackrabbit/oak/plugins/document/cache/CacheChangesTracker.java b/oak-store-document/src/main/java/org/apache/jackrabbit/oak/plugins/document/cache/CacheChangesTracker.java
index 14e30cd673..196f6188d4 100644
--- a/oak-store-document/src/main/java/org/apache/jackrabbit/oak/plugins/document/cache/CacheChangesTracker.java
+++ b/oak-store-document/src/main/java/org/apache/jackrabbit/oak/plugins/document/cache/CacheChangesTracker.java
@@ -16,14 +16,13 @@
*/
package org.apache.jackrabbit.oak.plugins.document.cache;
-import org.apache.jackrabbit.guava.common.hash.BloomFilter;
-import org.apache.jackrabbit.guava.common.hash.Funnel;
-import org.apache.jackrabbit.guava.common.hash.PrimitiveSink;
+import org.apache.jackrabbit.oak.commons.collections.BloomFilter;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.io.Closeable;
import java.util.List;
+import java.util.concurrent.atomic.AtomicReference;
import java.util.function.Predicate;
public class CacheChangesTracker implements Closeable {
@@ -62,10 +61,10 @@ public class CacheChangesTracker implements Closeable {
changeTrackers.remove(this);
if (LOG.isDebugEnabled()) {
- if (lazyBloomFilter.filter == null) {
+ if (lazyBloomFilter.filterRef.get() == null) {
LOG.debug("Disposing CacheChangesTracker for {}, no filter was needed", keyFilter);
} else {
- LOG.debug("Disposing CacheChangesTracker for {}, filter fpp was: {}", keyFilter, lazyBloomFilter.filter.expectedFpp());
+ LOG.debug("Disposing CacheChangesTracker for {}, filter fpp was: {}", keyFilter, LazyBloomFilter.FPP);
}
}
}
@@ -76,38 +75,33 @@ public class CacheChangesTracker implements Closeable {
private final int entries;
- private volatile BloomFilter<String> filter;
+ private final AtomicReference<BloomFilter> filterRef;
public LazyBloomFilter(int entries) {
this.entries = entries;
+ this.filterRef = new AtomicReference<>();
}
public synchronized void put(String entry) {
- getFilter().put(entry);
+ getFilter().add(entry);
}
public boolean mightContain(String entry) {
- if (filter == null) {
- return false;
- } else {
- synchronized (this) {
- return filter.mightContain(entry);
- }
- }
+ BloomFilter f = filterRef.get();
+ return f != null && f.mayContain(entry);
}
- private BloomFilter<String> getFilter() {
- if (filter == null) {
- filter = BloomFilter.create(new Funnel<String>() {
- private static final long serialVersionUID = -7114267990225941161L;
-
- @Override
- public void funnel(String from, PrimitiveSink into) {
- into.putUnencodedChars(from);
- }
- }, entries, FPP);
+ private BloomFilter getFilter() {
+ BloomFilter result = filterRef.get();
+ if (result == null) {
+ BloomFilter newFilter = BloomFilter.construct(entries, FPP);
+ if (filterRef.compareAndSet(null, newFilter)) {
+ result = newFilter;
+ } else {
+ result = filterRef.get();
+ }
}
- return filter;
+ return result;
}
}
}