布隆过滤器( Bloom filters)
数据块索引提供了一个有效的方法,在访问一个特定的行时用来查找应该读取的HFile的数据块。但是它的效用是有限的。HFile数据块的默认大小是64KB,这个大小不能调整太多。
如果你要查找一个短行,只在整个数据块的起始行键上建立索引无法给你细粒度的索引信息。例如,如果你的行占用100字节存储空间,一个64KB的数据块包含(64 * 1024)/100 = 655.53 = ~700行,而你只能把起始行放在索引位上。你要查找的行可能落在特定数据块上的行区间里,但也不是肯定存放在那个数据块上。这有多种情况的可能,或者该行在表里不存在,或者存放在另一个HFile里,甚至在MemStore里。这些情况下,从硬盘读取数据块会带来IO开销,也会滥用数据块缓存。这会影响性能,尤其是当你面对一个巨大的数据集并且有很多并发读用户时。
布隆过滤器允许你对存储在每个数据块的数据做一个反向测试。当某行被请求时,先检查布隆过滤器看看该行是否不在这个数据块。布隆过滤器要么确定回答该行不在,要么回答它不知道。这就是为什么我们称它是反向测试。布隆过滤器也可以应用到行里的单元上。当访问某列标识符时先使用同样的反向测试。
布隆过滤器也不是没有代价。存储这个额外的索引层次占用额外的空间。布隆过滤器随着它们的索引对象数据增长而增长,所以行级布隆过滤器比列标识符级布隆过滤器占用空间要少。当空间不是问题时,它们可以帮助你榨干系统的性能潜力。
你可以在列族上打开布隆过滤器,如下所示:
hbase(main)> create 'mytable',{NAME=>'colfam1',BLOOMFILTER=>'ROWCOL'}
BLOOMFILTER参数的默认值是NONE。一个行级布隆过滤器用ROW打开,列标识符级布隆过滤器用ROWCOL打开。行级布隆过滤器在数据块里检查特定行键是否不存在,列标识符级布隆过滤器检查行和列标识符联合体是否不存在。ROWCOL布隆过滤器的开销高于ROW布隆过滤器。
- if (memOnly == false
- && ((StoreFileScanner) kvs).shouldSeek(scan, columns)) {
- scanners.add(kvs);
- }
- if (!scan.isGetScan()) {
- return true;
- }
- byte[] row = scan.getStartRow();
- switch (this.bloomFilterType) {
- case ROW:
- return passesBloomFilter(row, 0, row.length, null, 0, 0);
- case ROWCOL:
- if (columns != null && columns.size() == 1) {
- byte[] column = columns.first();
- return passesBloomFilter(row, 0, row.length, column, 0, column.length);
- }
- // For multi-column queries the Bloom filter is checked from the
- // seekExact operation.
- return true;
- default:
- return true;
- }
- // Seek all scanners to the start of the Row (or if the exact matching row
- // key does not exist, then to the start of the next matching Row).
- if (matcher.isExactColumnQuery()) {
- for (KeyValueScanner scanner : scanners)
- scanner.seekExactly(matcher.getStartKey(), false);
- } else {
- for (KeyValueScanner scanner : scanners)
- scanner.seek(matcher.getStartKey());
- }
- public boolean seekExactly(KeyValue kv, boolean forward)
- throws IOException {
- if (reader.getBloomFilterType() != StoreFile.BloomType.ROWCOL ||
- kv.getRowLength() == 0 || kv.getQualifierLength() == 0) {
- return forward ? reseek(kv) : seek(kv);
- }
- boolean isInBloom = reader.passesBloomFilter(kv.getBuffer(),
- kv.getRowOffset(), kv.getRowLength(), kv.getBuffer(),
- kv.getQualifierOffset(), kv.getQualifierLength());
- if (isInBloom) {
- // This row/column might be in this store file. Do a normal seek.
- return forward ? reseek(kv) : seek(kv);
- }
- // Create a fake key/value, so that this scanner only bubbles up to the top
- // of the KeyValueHeap in StoreScanner after we scanned this row/column in
- // all other store files. The query matcher will then just skip this fake
- // key/value and the store scanner will progress to the next column.
- cur = kv.createLastOnRowCol();
- return true;
- }