Source code

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.regionserver;
019
020import static org.junit.jupiter.api.Assertions.assertEquals;
021import static org.junit.jupiter.api.Assertions.assertTrue;
022import static org.junit.jupiter.api.Assertions.fail;
023import static org.mockito.Mockito.mock;
024import static org.mockito.Mockito.when;
025
026import java.io.IOException;
027import java.util.ArrayList;
028import java.util.Collections;
029import java.util.List;
030import java.util.Random;
031import org.apache.hadoop.conf.Configuration;
032import org.apache.hadoop.fs.FileSystem;
033import org.apache.hadoop.fs.Path;
034import org.apache.hadoop.hbase.CellComparatorImpl;
035import org.apache.hadoop.hbase.CellUtil;
036import org.apache.hadoop.hbase.HBaseTestingUtil;
037import org.apache.hadoop.hbase.KeyValue;
038import org.apache.hadoop.hbase.KeyValueUtil;
039import org.apache.hadoop.hbase.client.ColumnFamilyDescriptorBuilder;
040import org.apache.hadoop.hbase.client.Scan;
041import org.apache.hadoop.hbase.io.hfile.BlockCache;
042import org.apache.hadoop.hbase.io.hfile.BlockCacheFactory;
043import org.apache.hadoop.hbase.io.hfile.CacheConfig;
044import org.apache.hadoop.hbase.io.hfile.CompoundBloomFilter;
045import org.apache.hadoop.hbase.io.hfile.CompoundBloomFilterWriter;
046import org.apache.hadoop.hbase.io.hfile.HFile;
047import org.apache.hadoop.hbase.io.hfile.HFileContext;
048import org.apache.hadoop.hbase.io.hfile.HFileContextBuilder;
049import org.apache.hadoop.hbase.io.hfile.RandomKeyValueUtil;
050import org.apache.hadoop.hbase.testclassification.LargeTests;
051import org.apache.hadoop.hbase.testclassification.RegionServerTests;
052import org.apache.hadoop.hbase.util.BloomFilterFactory;
053import org.apache.hadoop.hbase.util.BloomFilterUtil;
054import org.apache.hadoop.hbase.util.Bytes;
055import org.junit.jupiter.api.BeforeEach;
056import org.junit.jupiter.api.Tag;
057import org.junit.jupiter.api.Test;
058import org.slf4j.Logger;
059import org.slf4j.LoggerFactory;
060
061/**
062 * Tests writing Bloom filter blocks in the same part of the file as data blocks.
063 */
064@Tag(RegionServerTests.TAG)
065@Tag(LargeTests.TAG)
066public class TestCompoundBloomFilter {
067
068  private static final HBaseTestingUtil TEST_UTIL = new HBaseTestingUtil();
069
070  private static final Logger LOG = LoggerFactory.getLogger(TestCompoundBloomFilter.class);
071
072  private static final int NUM_TESTS = 9;
073  private static final BloomType BLOOM_TYPES[] =
074    { BloomType.ROW, BloomType.ROW, BloomType.ROWCOL, BloomType.ROWCOL, BloomType.ROW,
075      BloomType.ROWCOL, BloomType.ROWCOL, BloomType.ROWCOL, BloomType.ROW };
076
077  private static final int NUM_KV[];
078  static {
079    final int N = 10000; // Only used in initialization.
080    NUM_KV = new int[] { 21870, N, N, N, N, 1000, N, 7500, 7500 };
081    assert NUM_KV.length == NUM_TESTS;
082  }
083
084  private static final int BLOCK_SIZES[];
085  static {
086    final int blkSize = 65536;
087    BLOCK_SIZES = new int[] { 512, 1000, blkSize, blkSize, blkSize, 128, 300, blkSize, blkSize };
088    assert BLOCK_SIZES.length == NUM_TESTS;
089  }
090
091  /**
092   * Be careful not to specify too high a Bloom filter block size, otherwise there will only be one
093   * oversized chunk and the observed false positive rate will be too low.
094   */
095  private static final int BLOOM_BLOCK_SIZES[] =
096    { 1000, 4096, 4096, 4096, 8192, 128, 1024, 600, 600 };
097  static {
098    assert BLOOM_BLOCK_SIZES.length == NUM_TESTS;
099  }
100
101  private static final double TARGET_ERROR_RATES[] =
102    { 0.025, 0.01, 0.015, 0.01, 0.03, 0.01, 0.01, 0.07, 0.07 };
103  static {
104    assert TARGET_ERROR_RATES.length == NUM_TESTS;
105  }
106
107  /** A false positive rate that is obviously too high. */
108  private static final double TOO_HIGH_ERROR_RATE;
109  static {
110    double m = 0;
111    for (double errorRate : TARGET_ERROR_RATES)
112      m = Math.max(m, errorRate);
113    TOO_HIGH_ERROR_RATE = m + 0.03;
114  }
115
116  private static Configuration conf;
117  private static CacheConfig cacheConf;
118  private FileSystem fs;
119
120  /** A message of the form "in test#&lt;number>:" to include in logging. */
121  private String testIdMsg;
122
123  private static final int GENERATION_SEED = 2319;
124  private static final int EVALUATION_SEED = 135;
125
126  private BlockCache blockCache;
127
128  @BeforeEach
129  public void setUp() throws IOException {
130    conf = TEST_UTIL.getConfiguration();
131
132    // This test requires the most recent HFile format (i.e. v2).
133    conf.setInt(HFile.FORMAT_VERSION_KEY, HFile.MAX_FORMAT_VERSION);
134
135    fs = FileSystem.get(conf);
136    blockCache = BlockCacheFactory.createBlockCache(conf);
137    cacheConf = new CacheConfig(conf, blockCache);
138  }
139
140  private List<KeyValue> createSortedKeyValues(Random rand, int n) {
141    List<KeyValue> kvList = new ArrayList<>(n);
142    for (int i = 0; i < n; ++i)
143      kvList.add(RandomKeyValueUtil.randomKeyValue(rand));
144    Collections.sort(kvList, CellComparatorImpl.COMPARATOR);
145    return kvList;
146  }
147
148  @Test
149  public void testCompoundBloomFilter() throws IOException {
150    conf.setBoolean(BloomFilterFactory.IO_STOREFILE_BLOOM_ENABLED, true);
151    for (int t = 0; t < NUM_TESTS; ++t) {
152      conf.setFloat(BloomFilterFactory.IO_STOREFILE_BLOOM_ERROR_RATE,
153        (float) TARGET_ERROR_RATES[t]);
154
155      testIdMsg = "in test #" + t + ":";
156      Random generationRand = new Random(GENERATION_SEED);
157      List<KeyValue> kvs = createSortedKeyValues(generationRand, NUM_KV[t]);
158      BloomType bt = BLOOM_TYPES[t];
159      Path sfPath = writeStoreFile(t, bt, kvs);
160      readStoreFile(t, bt, kvs, sfPath);
161    }
162  }
163
164  /**
165   * Validates the false positive ratio by computing its z-value and comparing it to the provided
166   * threshold.
167   * @param falsePosRate   experimental positive rate
168   * @param nTrials        the number of Bloom filter checks
169   * @param zValueBoundary z-value boundary, positive for an upper bound and negative for a lower
170   *                       bound
171   * @param cbf            the compound Bloom filter we are using
172   * @param additionalMsg  additional message to include in log output and assertion failures
173   */
174  private void validateFalsePosRate(double falsePosRate, int nTrials, double zValueBoundary,
175    CompoundBloomFilter cbf, String additionalMsg) {
176    double p = BloomFilterFactory.getErrorRate(conf);
177    double zValue = (falsePosRate - p) / Math.sqrt(p * (1 - p) / nTrials);
178
179    String assortedStatsStr =
180      " (targetErrorRate=" + p + ", falsePosRate=" + falsePosRate + ", nTrials=" + nTrials + ")";
181    LOG.info("z-value is " + zValue + assortedStatsStr);
182
183    boolean isUpperBound = zValueBoundary > 0;
184
185    if (isUpperBound && zValue > zValueBoundary || !isUpperBound && zValue < zValueBoundary) {
186      String errorMsg = "False positive rate z-value " + zValue + " is "
187        + (isUpperBound ? "higher" : "lower") + " than " + zValueBoundary + assortedStatsStr
188        + ". Per-chunk stats:\n" + cbf.formatTestingStats();
189      fail(errorMsg + additionalMsg);
190    }
191  }
192
193  private void readStoreFile(int t, BloomType bt, List<KeyValue> kvs, Path sfPath)
194    throws IOException {
195    StoreFileInfo storeFileInfo = StoreFileInfo.createStoreFileInfoForHFile(conf, fs, sfPath, true);
196    HStoreFile sf = new HStoreFile(storeFileInfo, bt, cacheConf);
197    sf.initReader();
198    StoreFileReader r = sf.getReader();
199    final boolean pread = true; // does not really matter
200    StoreFileScanner scanner = r.getStoreFileScanner(true, pread, false, 0, 0, false);
201
202    {
203      // Test for false negatives (not allowed).
204      int numChecked = 0;
205      for (KeyValue kv : kvs) {
206        byte[] row = CellUtil.cloneRow(kv);
207        boolean present = isInBloom(scanner, row, CellUtil.cloneQualifier(kv));
208        assertTrue(present, testIdMsg + " Bloom filter false negative on row "
209          + Bytes.toStringBinary(row) + " after " + numChecked + " successful checks");
210        ++numChecked;
211      }
212    }
213
214    // Test for false positives (some percentage allowed). We test in two modes:
215    // "fake lookup" which ignores the key distribution, and production mode.
216    for (boolean fakeLookupEnabled : new boolean[] { true, false }) {
217      if (fakeLookupEnabled) {
218        BloomFilterUtil.setRandomGeneratorForTest(new Random(283742987L));
219      }
220      try {
221        String fakeLookupModeStr =
222          ", fake lookup is " + (fakeLookupEnabled ? "enabled" : "disabled");
223        CompoundBloomFilter cbf = (CompoundBloomFilter) r.getGeneralBloomFilter();
224        cbf.enableTestingStats();
225        int numFalsePos = 0;
226        Random rand = new Random(EVALUATION_SEED);
227        int nTrials = NUM_KV[t] * 10;
228        for (int i = 0; i < nTrials; ++i) {
229          byte[] query = RandomKeyValueUtil.randomRowOrQualifier(rand);
230          if (isInBloom(scanner, query, bt, rand)) {
231            numFalsePos += 1;
232          }
233        }
234        double falsePosRate = numFalsePos * 1.0 / nTrials;
235        LOG.debug(String.format(testIdMsg + " False positives: %d out of %d (%f)", numFalsePos,
236          nTrials, falsePosRate) + fakeLookupModeStr);
237
238        // Check for obvious Bloom filter crashes.
239        assertTrue(falsePosRate < TOO_HIGH_ERROR_RATE, "False positive is too high: " + falsePosRate
240          + " (greater " + "than " + TOO_HIGH_ERROR_RATE + ")" + fakeLookupModeStr);
241
242        // Now a more precise check to see if the false positive rate is not
243        // too high. The reason we use a relaxed restriction for the real-world
244        // case as opposed to the "fake lookup" case is that our hash functions
245        // are not completely independent.
246
247        double maxZValue = fakeLookupEnabled ? 1.96 : 2.5;
248        validateFalsePosRate(falsePosRate, nTrials, maxZValue, cbf, fakeLookupModeStr);
249
250        // For checking the lower bound we need to eliminate the last chunk,
251        // because it is frequently smaller and the false positive rate in it
252        // is too low. This does not help if there is only one under-sized
253        // chunk, though.
254        int nChunks = cbf.getNumChunks();
255        if (nChunks > 1) {
256          numFalsePos -= cbf.getNumPositivesForTesting(nChunks - 1);
257          nTrials -= cbf.getNumQueriesForTesting(nChunks - 1);
258          falsePosRate = numFalsePos * 1.0 / nTrials;
259          LOG.info(testIdMsg + " False positive rate without last chunk is " + falsePosRate
260            + fakeLookupModeStr);
261        }
262
263        validateFalsePosRate(falsePosRate, nTrials, -2.58, cbf, fakeLookupModeStr);
264      } finally {
265        BloomFilterUtil.setRandomGeneratorForTest(null);
266      }
267    }
268
269    r.close(true); // end of test so evictOnClose
270  }
271
272  private boolean isInBloom(StoreFileScanner scanner, byte[] row, BloomType bt, Random rand) {
273    return isInBloom(scanner, row, RandomKeyValueUtil.randomRowOrQualifier(rand));
274  }
275
276  private boolean isInBloom(StoreFileScanner scanner, byte[] row, byte[] qualifier) {
277    Scan scan = new Scan().withStartRow(row).withStopRow(row, true);
278    scan.addColumn(Bytes.toBytes(RandomKeyValueUtil.COLUMN_FAMILY_NAME), qualifier);
279    HStore store = mock(HStore.class);
280    when(store.getColumnFamilyDescriptor())
281      .thenReturn(ColumnFamilyDescriptorBuilder.of(RandomKeyValueUtil.COLUMN_FAMILY_NAME));
282    return scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
283  }
284
285  private Path writeStoreFile(int t, BloomType bt, List<KeyValue> kvs) throws IOException {
286    conf.setInt(BloomFilterFactory.IO_STOREFILE_BLOOM_BLOCK_SIZE, BLOOM_BLOCK_SIZES[t]);
287    conf.setBoolean(CacheConfig.CACHE_BLOCKS_ON_WRITE_KEY, true);
288    cacheConf = new CacheConfig(conf, blockCache);
289    HFileContext meta = new HFileContextBuilder().withBlockSize(BLOCK_SIZES[t]).build();
290    StoreFileWriter w = new StoreFileWriter.Builder(conf, cacheConf, fs)
291      .withOutputDir(TEST_UTIL.getDataTestDir()).withBloomType(bt).withFileContext(meta).build();
292
293    assertTrue(w.hasGeneralBloom());
294    assertTrue(w.getGeneralBloomWriter() instanceof CompoundBloomFilterWriter);
295    CompoundBloomFilterWriter cbbf = (CompoundBloomFilterWriter) w.getGeneralBloomWriter();
296
297    int keyCount = 0;
298    KeyValue prev = null;
299    LOG.debug("Total keys/values to insert: " + kvs.size());
300    for (KeyValue kv : kvs) {
301      w.append(kv);
302
303      // Validate the key count in the Bloom filter.
304      boolean newKey = true;
305      if (prev != null) {
306        newKey = !(bt == BloomType.ROW
307          ? CellUtil.matchingRows(kv, prev)
308          : CellUtil.matchingRowColumn(kv, prev));
309      }
310      if (newKey) ++keyCount;
311      assertEquals(keyCount, cbbf.getKeyCount());
312
313      prev = kv;
314    }
315    w.close();
316
317    return w.getPath();
318  }
319
320  @Test
321  public void testCompoundBloomSizing() {
322    int bloomBlockByteSize = 4096;
323    int bloomBlockBitSize = bloomBlockByteSize * 8;
324    double targetErrorRate = 0.01;
325    long maxKeysPerChunk = BloomFilterUtil.idealMaxKeys(bloomBlockBitSize, targetErrorRate);
326
327    long bloomSize1 = bloomBlockByteSize * 8;
328    long bloomSize2 = BloomFilterUtil.computeBitSize(maxKeysPerChunk, targetErrorRate);
329
330    double bloomSizeRatio = (bloomSize2 * 1.0 / bloomSize1);
331    assertTrue(Math.abs(bloomSizeRatio - 0.9999) < 0.0001);
332  }
333
334  @Test
335  public void testCreateKey() {
336    byte[] row = Bytes.toBytes("myRow");
337    byte[] qualifier = Bytes.toBytes("myQualifier");
338    // Mimic what Storefile.createBloomKeyValue() does
339    byte[] rowKey =
340      KeyValueUtil.createFirstOnRow(row, 0, row.length, new byte[0], 0, 0, row, 0, 0).getKey();
341    byte[] rowColKey = KeyValueUtil
342      .createFirstOnRow(row, 0, row.length, new byte[0], 0, 0, qualifier, 0, qualifier.length)
343      .getKey();
344    KeyValue rowKV = KeyValueUtil.createKeyValueFromKey(rowKey);
345    KeyValue rowColKV = KeyValueUtil.createKeyValueFromKey(rowColKey);
346    assertEquals(rowKV.getTimestamp(), rowColKV.getTimestamp());
347    assertEquals(
348      Bytes.toStringBinary(rowKV.getRowArray(), rowKV.getRowOffset(), rowKV.getRowLength()), Bytes
349        .toStringBinary(rowColKV.getRowArray(), rowColKV.getRowOffset(), rowColKV.getRowLength()));
350    assertEquals(0, rowKV.getQualifierLength());
351  }
352}