001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.util;
019
020import static org.junit.jupiter.api.Assertions.assertEquals;
021import static org.junit.jupiter.api.Assertions.assertFalse;
022import static org.junit.jupiter.api.Assertions.assertTrue;
023
024import java.io.ByteArrayOutputStream;
025import java.io.DataOutputStream;
026import java.nio.ByteBuffer;
027import org.apache.hadoop.hbase.nio.MultiByteBuff;
028import org.apache.hadoop.hbase.testclassification.MiscTests;
029import org.apache.hadoop.hbase.testclassification.SmallTests;
030import org.junit.jupiter.api.Tag;
031import org.junit.jupiter.api.Test;
032
033@Tag(MiscTests.TAG)
034@Tag(SmallTests.TAG)
035public class TestBloomFilterChunk {
036
037  @Test
038  public void testBasicBloom() throws Exception {
039    BloomFilterChunk bf1 = new BloomFilterChunk(1000, (float) 0.01, Hash.MURMUR_HASH, 0);
040    BloomFilterChunk bf2 = new BloomFilterChunk(1000, (float) 0.01, Hash.MURMUR_HASH, 0);
041    bf1.allocBloom();
042    bf2.allocBloom();
043
044    // test 1: verify no fundamental false negatives or positives
045    byte[] key1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
046    byte[] key2 = { 1, 2, 3, 4, 5, 6, 7, 8, 7 };
047
048    bf1.add(key1, 0, key1.length);
049    bf2.add(key2, 0, key2.length);
050
051    assertTrue(BloomFilterUtil.contains(key1, 0, key1.length, new MultiByteBuff(bf1.bloom), 0,
052      (int) bf1.byteSize, bf1.hash, bf1.hashCount));
053    assertFalse(BloomFilterUtil.contains(key2, 0, key2.length, new MultiByteBuff(bf1.bloom), 0,
054      (int) bf1.byteSize, bf1.hash, bf1.hashCount));
055    assertFalse(BloomFilterUtil.contains(key1, 0, key1.length, new MultiByteBuff(bf2.bloom), 0,
056      (int) bf2.byteSize, bf2.hash, bf2.hashCount));
057    assertTrue(BloomFilterUtil.contains(key2, 0, key2.length, new MultiByteBuff(bf2.bloom), 0,
058      (int) bf2.byteSize, bf2.hash, bf2.hashCount));
059
060    byte[] bkey = { 1, 2, 3, 4 };
061    byte[] bval = Bytes.toBytes("this is a much larger byte array");
062
063    bf1.add(bkey, 0, bkey.length);
064    bf1.add(bval, 1, bval.length - 1);
065
066    assertTrue(BloomFilterUtil.contains(bkey, 0, bkey.length, new MultiByteBuff(bf1.bloom), 0,
067      (int) bf1.byteSize, bf1.hash, bf1.hashCount));
068    assertTrue(BloomFilterUtil.contains(bval, 1, bval.length - 1, new MultiByteBuff(bf1.bloom), 0,
069      (int) bf1.byteSize, bf1.hash, bf1.hashCount));
070    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, new MultiByteBuff(bf1.bloom), 0,
071      (int) bf1.byteSize, bf1.hash, bf1.hashCount));
072
073    // test 2: serialization & deserialization.
074    // (convert bloom to byte array & read byte array back in as input)
075    ByteArrayOutputStream bOut = new ByteArrayOutputStream();
076    bf1.writeBloom(new DataOutputStream(bOut));
077    ByteBuffer bb = ByteBuffer.wrap(bOut.toByteArray());
078    BloomFilterChunk newBf1 = new BloomFilterChunk(1000, (float) 0.01, Hash.MURMUR_HASH, 0);
079    assertTrue(BloomFilterUtil.contains(key1, 0, key1.length, new MultiByteBuff(bb), 0,
080      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
081    assertFalse(BloomFilterUtil.contains(key2, 0, key2.length, new MultiByteBuff(bb), 0,
082      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
083    assertTrue(BloomFilterUtil.contains(bkey, 0, bkey.length, new MultiByteBuff(bb), 0,
084      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
085    assertTrue(BloomFilterUtil.contains(bval, 1, bval.length - 1, new MultiByteBuff(bb), 0,
086      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
087    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, new MultiByteBuff(bb), 0,
088      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
089    assertFalse(BloomFilterUtil.contains(bval, 0, bval.length, new MultiByteBuff(bb), 0,
090      (int) newBf1.byteSize, newBf1.hash, newBf1.hashCount));
091
092    System.out.println("Serialized as " + bOut.size() + " bytes");
093    assertTrue(bOut.size() - bf1.byteSize < 10); // ... allow small padding
094  }
095
096  @Test
097  public void testBloomFold() throws Exception {
098    // test: foldFactor < log(max/actual)
099    BloomFilterChunk b = new BloomFilterChunk(1003, (float) 0.01, Hash.MURMUR_HASH, 2);
100    b.allocBloom();
101    long origSize = b.getByteSize();
102    assertEquals(1204, origSize);
103    for (int i = 0; i < 12; ++i) {
104      byte[] ib = Bytes.toBytes(i);
105      b.add(ib, 0, ib.length);
106    }
107    b.compactBloom();
108    assertEquals(origSize >> 2, b.getByteSize());
109    int falsePositives = 0;
110    for (int i = 0; i < 25; ++i) {
111      byte[] bytes = Bytes.toBytes(i);
112      if (
113        BloomFilterUtil.contains(bytes, 0, bytes.length, new MultiByteBuff(b.bloom), 0,
114          (int) b.byteSize, b.hash, b.hashCount)
115      ) {
116        if (i >= 12) falsePositives++;
117      } else {
118        assertFalse(i < 12);
119      }
120    }
121    assertTrue(falsePositives <= 1);
122
123    // test: foldFactor > log(max/actual)
124  }
125
126  @Test
127  public void testBloomPerf() throws Exception {
128    // add
129    float err = (float) 0.01;
130    BloomFilterChunk b = new BloomFilterChunk(10 * 1000 * 1000, (float) err, Hash.MURMUR_HASH, 3);
131    b.allocBloom();
132    long startTime = EnvironmentEdgeManager.currentTime();
133    long origSize = b.getByteSize();
134    for (int i = 0; i < 1 * 1000 * 1000; ++i) {
135      byte[] ib = Bytes.toBytes(i);
136      b.add(ib, 0, ib.length);
137    }
138    long endTime = EnvironmentEdgeManager.currentTime();
139    System.out.println("Total Add time = " + (endTime - startTime) + "ms");
140
141    // fold
142    startTime = EnvironmentEdgeManager.currentTime();
143    b.compactBloom();
144    endTime = EnvironmentEdgeManager.currentTime();
145    System.out.println("Total Fold time = " + (endTime - startTime) + "ms");
146    assertTrue(origSize >= b.getByteSize() << 3);
147
148    // test
149    startTime = EnvironmentEdgeManager.currentTime();
150    int falsePositives = 0;
151    for (int i = 0; i < 2 * 1000 * 1000; ++i) {
152
153      byte[] bytes = Bytes.toBytes(i);
154      if (
155        BloomFilterUtil.contains(bytes, 0, bytes.length, new MultiByteBuff(b.bloom), 0,
156          (int) b.byteSize, b.hash, b.hashCount)
157      ) {
158        if (i >= 1 * 1000 * 1000) falsePositives++;
159      } else {
160        assertFalse(i < 1 * 1000 * 1000);
161      }
162    }
163    endTime = EnvironmentEdgeManager.currentTime();
164    System.out.println("Total Contains time = " + (endTime - startTime) + "ms");
165    System.out.println("False Positive = " + falsePositives);
166    assertTrue(falsePositives <= (1 * 1000 * 1000) * err);
167
168    // test: foldFactor > log(max/actual)
169  }
170
171  @Test
172  public void testSizing() {
173    int bitSize = 8 * 128 * 1024; // 128 KB
174    double errorRate = 0.025; // target false positive rate
175
176    // How many keys can we store in a Bloom filter of this size maintaining
177    // the given false positive rate, not taking into account that the n
178    long maxKeys = BloomFilterUtil.idealMaxKeys(bitSize, errorRate);
179    assertEquals(136570, maxKeys);
180
181    // A reverse operation: how many bits would we need to store this many keys
182    // and keep the same low false positive rate?
183    long bitSize2 = BloomFilterUtil.computeBitSize(maxKeys, errorRate);
184
185    // The bit size comes out a little different due to rounding.
186    assertTrue(Math.abs(bitSize2 - bitSize) * 1.0 / bitSize < 1e-5);
187  }
188
189  @Test
190  public void testFoldableByteSize() {
191    assertEquals(128, BloomFilterUtil.computeFoldableByteSize(1000, 5));
192    assertEquals(640, BloomFilterUtil.computeFoldableByteSize(5001, 4));
193  }
194}