1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.apache.hadoop.hbase.util;
21
22 import java.io.DataInput;
23 import java.io.IOException;
24 import java.nio.ByteBuffer;
25
26 import org.apache.hadoop.hbase.classification.InterfaceAudience;
27 import org.apache.hadoop.hbase.KeyValue.KVComparator;
28 import org.apache.hadoop.hbase.io.hfile.BlockType;
29 import org.apache.hadoop.hbase.io.hfile.FixedFileTrailer;
30 import org.apache.hadoop.hbase.io.hfile.HFile;
31 import org.apache.hadoop.hbase.io.hfile.HFileBlock;
32 import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex;
33
34
35
36
37
38
39
40
41 @InterfaceAudience.Private
42 public class CompoundBloomFilter extends CompoundBloomFilterBase
43 implements BloomFilter {
44
45
46 private HFile.Reader reader;
47
48 private HFileBlockIndex.BlockIndexReader index;
49
50 private int hashCount;
51 private Hash hash;
52
53 private long[] numQueriesPerChunk;
54 private long[] numPositivesPerChunk;
55
56
57
58
59
60
61
62
63 public CompoundBloomFilter(DataInput meta, HFile.Reader reader)
64 throws IOException {
65 this.reader = reader;
66
67 totalByteSize = meta.readLong();
68 hashCount = meta.readInt();
69 hashType = meta.readInt();
70 totalKeyCount = meta.readLong();
71 totalMaxKeys = meta.readLong();
72 numChunks = meta.readInt();
73 comparator = FixedFileTrailer.createComparator(
74 Bytes.toString(Bytes.readByteArray(meta)));
75
76 hash = Hash.getInstance(hashType);
77 if (hash == null) {
78 throw new IllegalArgumentException("Invalid hash type: " + hashType);
79 }
80
81 index = new HFileBlockIndex.BlockIndexReader(comparator, 1);
82 index.readRootIndex(meta, numChunks);
83 }
84
85 @Override
86 public boolean contains(byte[] key, int keyOffset, int keyLength,
87 ByteBuffer bloom) {
88
89
90 boolean result;
91
92 int block = index.rootBlockContainingKey(key, keyOffset,
93 keyLength);
94 if (block < 0) {
95 result = false;
96 } else {
97 HFileBlock bloomBlock;
98 try {
99
100 bloomBlock = reader.readBlock(index.getRootBlockOffset(block),
101 index.getRootBlockDataSize(block), true, true, false, true,
102 BlockType.BLOOM_CHUNK, null);
103 } catch (IOException ex) {
104
105 throw new IllegalArgumentException(
106 "Failed to load Bloom block for key "
107 + Bytes.toStringBinary(key, keyOffset, keyLength), ex);
108 }
109
110 ByteBuffer bloomBuf = bloomBlock.getBufferReadOnly();
111 result = ByteBloomFilter.contains(key, keyOffset, keyLength,
112 bloomBuf, bloomBlock.headerSize(),
113 bloomBlock.getUncompressedSizeWithoutHeader(), hash, hashCount);
114 }
115
116 if (numQueriesPerChunk != null && block >= 0) {
117
118 ++numQueriesPerChunk[block];
119 if (result)
120 ++numPositivesPerChunk[block];
121 }
122
123 return result;
124 }
125
126 public boolean supportsAutoLoading() {
127 return true;
128 }
129
130 public int getNumChunks() {
131 return numChunks;
132 }
133
134 @Override
135 public KVComparator getComparator() {
136 return comparator;
137 }
138
139 public void enableTestingStats() {
140 numQueriesPerChunk = new long[numChunks];
141 numPositivesPerChunk = new long[numChunks];
142 }
143
144 public String formatTestingStats() {
145 StringBuilder sb = new StringBuilder();
146 for (int i = 0; i < numChunks; ++i) {
147 sb.append("chunk #");
148 sb.append(i);
149 sb.append(": queries=");
150 sb.append(numQueriesPerChunk[i]);
151 sb.append(", positives=");
152 sb.append(numPositivesPerChunk[i]);
153 sb.append(", positiveRatio=");
154 sb.append(numPositivesPerChunk[i] * 1.0 / numQueriesPerChunk[i]);
155 sb.append(";\n");
156 }
157 return sb.toString();
158 }
159
160 public long getNumQueriesForTesting(int chunk) {
161 return numQueriesPerChunk[chunk];
162 }
163
164 public long getNumPositivesForTesting(int chunk) {
165 return numPositivesPerChunk[chunk];
166 }
167
168 @Override
169 public String toString() {
170 StringBuilder sb = new StringBuilder();
171 sb.append(ByteBloomFilter.formatStats(this));
172 sb.append(ByteBloomFilter.STATS_RECORD_SEP +
173 "Number of chunks: " + numChunks);
174 sb.append(ByteBloomFilter.STATS_RECORD_SEP +
175 "Comparator: " + comparator.getClass().getSimpleName());
176 return sb.toString();
177 }
178
179 }