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.assertFalse;
022import static org.junit.jupiter.api.Assertions.assertTrue;
023import static org.mockito.Mockito.mock;
024import static org.mockito.Mockito.when;
025
026import java.io.IOException;
027import org.apache.hadoop.conf.Configuration;
028import org.apache.hadoop.fs.FileSystem;
029import org.apache.hadoop.fs.Path;
030import org.apache.hadoop.hbase.HBaseTestingUtil;
031import org.apache.hadoop.hbase.KeyValue;
032import org.apache.hadoop.hbase.client.ColumnFamilyDescriptorBuilder;
033import org.apache.hadoop.hbase.client.Get;
034import org.apache.hadoop.hbase.client.Scan;
035import org.apache.hadoop.hbase.io.hfile.CacheConfig;
036import org.apache.hadoop.hbase.io.hfile.HFileContext;
037import org.apache.hadoop.hbase.io.hfile.HFileContextBuilder;
038import org.apache.hadoop.hbase.io.hfile.ReaderContext;
039import org.apache.hadoop.hbase.io.hfile.ReaderContextBuilder;
040import org.apache.hadoop.hbase.log.HBaseMarkers;
041import org.apache.hadoop.hbase.testclassification.RegionServerTests;
042import org.apache.hadoop.hbase.testclassification.SmallTests;
043import org.apache.hadoop.hbase.util.BloomFilterFactory;
044import org.apache.hadoop.hbase.util.BloomFilterUtil;
045import org.apache.hadoop.hbase.util.Bytes;
046import org.apache.hadoop.hbase.util.ChecksumType;
047import org.apache.hadoop.hbase.util.CommonFSUtils;
048import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
049import org.junit.jupiter.api.AfterEach;
050import org.junit.jupiter.api.BeforeEach;
051import org.junit.jupiter.api.Tag;
052import org.junit.jupiter.api.Test;
053import org.slf4j.Logger;
054import org.slf4j.LoggerFactory;
055
056/**
057 * Test TestRowPrefixBloomFilter
058 */
059@Tag(RegionServerTests.TAG)
060@Tag(SmallTests.TAG)
061public class TestRowPrefixBloomFilter {
062
063  private static final Logger LOG = LoggerFactory.getLogger(TestRowPrefixBloomFilter.class);
064  private static final HBaseTestingUtil TEST_UTIL = new HBaseTestingUtil();
065  private CacheConfig cacheConf = new CacheConfig(TEST_UTIL.getConfiguration());
066  private static final ChecksumType CKTYPE = ChecksumType.CRC32C;
067  private static final int CKBYTES = 512;
068  private boolean localfs = false;
069  private static Configuration conf;
070  private static FileSystem fs;
071  private static Path testDir;
072  private static final int BLOCKSIZE_SMALL = 8192;
073  private static final float err = (float) 0.01;
074  private static final int prefixLength = 10;
075  private static final String invalidFormatter = "%08d";
076  private static final String prefixFormatter = "%010d";
077  private static final String suffixFormatter = "%010d";
078  private static final int prefixRowCount = 50;
079  private static final int suffixRowCount = 10;
080  private static final int fixedLengthExpKeys = prefixRowCount;
081  private static final BloomType bt = BloomType.ROWPREFIX_FIXED_LENGTH;
082
083  @BeforeEach
084  public void setUp() throws Exception {
085    conf = TEST_UTIL.getConfiguration();
086    conf.setFloat(BloomFilterFactory.IO_STOREFILE_BLOOM_ERROR_RATE, err);
087    conf.setBoolean(BloomFilterFactory.IO_STOREFILE_BLOOM_ENABLED, true);
088    conf.setInt(BloomFilterUtil.PREFIX_LENGTH_KEY, prefixLength);
089
090    localfs = (conf.get("fs.defaultFS", "file:///").compareTo("file:///") == 0);
091
092    if (fs == null) {
093      fs = FileSystem.get(conf);
094    }
095    try {
096      if (localfs) {
097        testDir = TEST_UTIL.getDataTestDir("TestRowPrefixBloomFilter");
098        if (fs.exists(testDir)) {
099          fs.delete(testDir, true);
100        }
101      } else {
102        testDir = CommonFSUtils.getRootDir(conf);
103      }
104    } catch (Exception e) {
105      LOG.error(HBaseMarkers.FATAL, "error during setup", e);
106      throw e;
107    }
108  }
109
110  @AfterEach
111  public void tearDown() throws Exception {
112    try {
113      if (localfs) {
114        if (fs.exists(testDir)) {
115          fs.delete(testDir, true);
116        }
117      }
118    } catch (Exception e) {
119      LOG.error(HBaseMarkers.FATAL, "error during tear down", e);
120    }
121  }
122
123  private static StoreFileScanner getStoreFileScanner(StoreFileReader reader) {
124    return reader.getStoreFileScanner(false, false, false, 0, 0, false);
125  }
126
127  private void writeStoreFile(final Path f, BloomType bt, int expKeys) throws IOException {
128    HFileContext meta = new HFileContextBuilder().withBlockSize(BLOCKSIZE_SMALL)
129      .withChecksumType(CKTYPE).withBytesPerCheckSum(CKBYTES).build();
130    // Make a store file and write data to it.
131    StoreFileWriter writer = new StoreFileWriter.Builder(conf, cacheConf, fs).withFilePath(f)
132      .withBloomType(bt).withMaxKeyCount(expKeys).withFileContext(meta).build();
133    long now = EnvironmentEdgeManager.currentTime();
134    try {
135      // Put with valid row style
136      for (int i = 0; i < prefixRowCount; i += 2) { // prefix rows
137        String prefixRow = String.format(prefixFormatter, i);
138        for (int j = 0; j < suffixRowCount; j++) { // suffix rows
139          String row = generateRowWithSuffix(prefixRow, j);
140          KeyValue kv = new KeyValue(Bytes.toBytes(row), Bytes.toBytes("family"),
141            Bytes.toBytes("col"), now, Bytes.toBytes("value"));
142          writer.append(kv);
143        }
144      }
145
146      // Put with invalid row style
147      for (int i = prefixRowCount; i < prefixRowCount * 2; i += 2) { // prefix rows
148        String row = String.format(invalidFormatter, i);
149        KeyValue kv = new KeyValue(Bytes.toBytes(row), Bytes.toBytes("family"),
150          Bytes.toBytes("col"), now, Bytes.toBytes("value"));
151        writer.append(kv);
152      }
153    } finally {
154      writer.close();
155    }
156  }
157
158  private String generateRowWithSuffix(String prefixRow, int suffix) {
159    StringBuilder row = new StringBuilder(prefixRow);
160    row.append("#");
161    row.append(String.format(suffixFormatter, suffix));
162    return row.toString();
163  }
164
165  @Test
166  public void testRowPrefixBloomFilter() throws Exception {
167    FileSystem fs = FileSystem.getLocal(conf);
168    float expErr = 2 * prefixRowCount * suffixRowCount * err;
169    int expKeys = fixedLengthExpKeys;
170    // write the file
171    if (!fs.exists(testDir)) {
172      fs.mkdirs(testDir);
173    }
174    Path f = StoreFileWriter.getUniqueFile(fs, testDir);
175    writeStoreFile(f, bt, expKeys);
176
177    // read the file
178    ReaderContext context = new ReaderContextBuilder().withFileSystemAndPath(fs, f).build();
179    StoreFileInfo storeFileInfo = StoreFileInfo.createStoreFileInfoForHFile(conf, fs, f, true);
180    storeFileInfo.initHFileInfo(context);
181    StoreFileReader reader = storeFileInfo.createReader(context, cacheConf);
182    storeFileInfo.getHFileInfo().initMetaAndIndex(reader.getHFileReader());
183    reader.loadFileInfo();
184    reader.loadBloomfilter();
185
186    // check basic param
187    assertEquals(bt, reader.getBloomFilterType());
188    assertEquals(prefixLength, reader.getPrefixLength());
189    assertEquals(expKeys, reader.getGeneralBloomFilter().getKeyCount());
190    StoreFileScanner scanner = getStoreFileScanner(reader);
191    HStore store = mock(HStore.class);
192    when(store.getColumnFamilyDescriptor()).thenReturn(ColumnFamilyDescriptorBuilder.of("family"));
193    // check false positives rate
194    int falsePos = 0;
195    int falseNeg = 0;
196    for (int i = 0; i < prefixRowCount; i++) { // prefix rows
197      String prefixRow = String.format(prefixFormatter, i);
198      for (int j = 0; j < suffixRowCount; j++) { // suffix rows
199        String startRow = generateRowWithSuffix(prefixRow, j);
200        String stopRow = generateRowWithSuffix(prefixRow, j + 1);
201        Scan scan =
202          new Scan().withStartRow(Bytes.toBytes(startRow)).withStopRow(Bytes.toBytes(stopRow));
203        boolean exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
204        boolean shouldPrefixRowExist = i % 2 == 0;
205        if (shouldPrefixRowExist) {
206          if (!exists) {
207            falseNeg++;
208          }
209        } else {
210          if (exists) {
211            falsePos++;
212          }
213        }
214      }
215    }
216
217    for (int i = prefixRowCount; i < prefixRowCount * 2; i++) { // prefix rows
218      String row = String.format(invalidFormatter, i);
219      Scan scan = new Scan(new Get(Bytes.toBytes(row)));
220      boolean exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
221      boolean shouldPrefixRowExist = i % 2 == 0;
222      if (shouldPrefixRowExist) {
223        if (!exists) {
224          falseNeg++;
225        }
226      } else {
227        if (exists) {
228          falsePos++;
229        }
230      }
231    }
232    reader.close(true); // evict because we are about to delete the file
233    fs.delete(f, true);
234    assertEquals(0, falseNeg, "False negatives: " + falseNeg);
235    int maxFalsePos = (int) (2 * expErr);
236    assertTrue(falsePos <= maxFalsePos, "Too many false positives: " + falsePos + " (err=" + err
237      + ", expected no more than " + maxFalsePos + ")");
238  }
239
240  @Test
241  public void testRowPrefixBloomFilterWithGet() throws Exception {
242    FileSystem fs = FileSystem.getLocal(conf);
243    int expKeys = fixedLengthExpKeys;
244    // write the file
245    if (!fs.exists(testDir)) {
246      fs.mkdirs(testDir);
247    }
248    Path f = StoreFileWriter.getUniqueFile(fs, testDir);
249    writeStoreFile(f, bt, expKeys);
250
251    ReaderContext context = new ReaderContextBuilder().withFileSystemAndPath(fs, f).build();
252    StoreFileInfo storeFileInfo = StoreFileInfo.createStoreFileInfoForHFile(conf, fs, f, true);
253    storeFileInfo.initHFileInfo(context);
254    StoreFileReader reader = storeFileInfo.createReader(context, cacheConf);
255    storeFileInfo.getHFileInfo().initMetaAndIndex(reader.getHFileReader());
256    reader.loadFileInfo();
257    reader.loadBloomfilter();
258
259    StoreFileScanner scanner = getStoreFileScanner(reader);
260    HStore store = mock(HStore.class);
261    when(store.getColumnFamilyDescriptor()).thenReturn(ColumnFamilyDescriptorBuilder.of("family"));
262
263    // Get with valid row style
264    // prefix row in bloom
265    String prefixRow = String.format(prefixFormatter, prefixRowCount - 2);
266    String row = generateRowWithSuffix(prefixRow, 0);
267    Scan scan = new Scan(new Get(Bytes.toBytes(row)));
268    boolean exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
269    assertTrue(exists);
270
271    // prefix row not in bloom
272    prefixRow = String.format(prefixFormatter, prefixRowCount - 1);
273    row = generateRowWithSuffix(prefixRow, 0);
274    scan = new Scan(new Get(Bytes.toBytes(row)));
275    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
276    assertFalse(exists);
277
278    // Get with invalid row style
279    // ROWPREFIX: the length of row is less than prefixLength
280    // row in bloom
281    row = String.format(invalidFormatter, prefixRowCount + 2);
282    scan = new Scan(new Get(Bytes.toBytes(row)));
283    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
284    assertTrue(exists);
285
286    // row not in bloom
287    row = String.format(invalidFormatter, prefixRowCount + 1);
288    scan = new Scan(new Get(Bytes.toBytes(row)));
289    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
290    assertFalse(exists);
291
292    reader.close(true); // evict because we are about to delete the file
293    fs.delete(f, true);
294  }
295
296  @Test
297  public void testRowPrefixBloomFilterWithScan() throws Exception {
298    FileSystem fs = FileSystem.getLocal(conf);
299    int expKeys = fixedLengthExpKeys;
300    // write the file
301    if (!fs.exists(testDir)) {
302      fs.mkdirs(testDir);
303    }
304    Path f = StoreFileWriter.getUniqueFile(fs, testDir);
305    writeStoreFile(f, bt, expKeys);
306
307    ReaderContext context = new ReaderContextBuilder().withFileSystemAndPath(fs, f).build();
308    StoreFileInfo storeFileInfo = StoreFileInfo.createStoreFileInfoForHFile(conf, fs, f, true);
309    storeFileInfo.initHFileInfo(context);
310    StoreFileReader reader = storeFileInfo.createReader(context, cacheConf);
311    storeFileInfo.getHFileInfo().initMetaAndIndex(reader.getHFileReader());
312    reader.loadFileInfo();
313    reader.loadBloomfilter();
314
315    StoreFileScanner scanner = getStoreFileScanner(reader);
316    HStore store = mock(HStore.class);
317    when(store.getColumnFamilyDescriptor()).thenReturn(ColumnFamilyDescriptorBuilder.of("family"));
318
319    // Scan with valid row style. startRow and stopRow have a common prefix.
320    // And the length of the common prefix is no less than prefixLength.
321    // prefix row in bloom
322    String prefixRow = String.format(prefixFormatter, prefixRowCount - 2);
323    String startRow = generateRowWithSuffix(prefixRow, 0);
324    String stopRow = generateRowWithSuffix(prefixRow, 1);
325    Scan scan =
326      new Scan().withStartRow(Bytes.toBytes(startRow)).withStopRow(Bytes.toBytes(stopRow));
327    boolean exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
328    assertTrue(exists);
329
330    // prefix row not in bloom
331    prefixRow = String.format(prefixFormatter, prefixRowCount - 1);
332    startRow = generateRowWithSuffix(prefixRow, 0);
333    stopRow = generateRowWithSuffix(prefixRow, 1);
334    scan = new Scan().withStartRow(Bytes.toBytes(startRow)).withStopRow(Bytes.toBytes(stopRow));
335    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
336    assertFalse(exists);
337
338    // There is no common prefix between startRow and stopRow.
339    prefixRow = String.format(prefixFormatter, prefixRowCount - 2);
340    startRow = generateRowWithSuffix(prefixRow, 0);
341    scan = new Scan().withStartRow(Bytes.toBytes(startRow));
342    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
343    assertTrue(exists);
344
345    // startRow and stopRow have a common prefix.
346    // But the length of the common prefix is less than prefixLength.
347    String prefixStartRow = String.format(prefixFormatter, prefixRowCount - 2);
348    String prefixStopRow = String.format(prefixFormatter, prefixRowCount - 1);
349    startRow = generateRowWithSuffix(prefixStartRow, 0);
350    stopRow = generateRowWithSuffix(prefixStopRow, 0);
351    scan = new Scan().withStartRow(Bytes.toBytes(startRow)).withStopRow(Bytes.toBytes(stopRow));
352    exists = scanner.shouldUseScanner(scan, store, Long.MIN_VALUE);
353    assertTrue(exists);
354
355    reader.close(true); // evict because we are about to delete the file
356    fs.delete(f, true);
357  }
358}