1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17 package org.apache.hadoop.hbase.io.encoding;
18
19 import static org.junit.Assert.assertEquals;
20 import static org.junit.Assert.fail;
21
22 import java.io.ByteArrayInputStream;
23 import java.io.DataInputStream;
24 import java.io.DataOutputStream;
25 import java.io.IOException;
26 import java.nio.ByteBuffer;
27 import java.util.ArrayList;
28 import java.util.Collection;
29 import java.util.List;
30 import java.util.Random;
31
32 import org.apache.commons.logging.Log;
33 import org.apache.commons.logging.LogFactory;
34 import org.apache.hadoop.hbase.CategoryBasedTimeout;
35 import org.apache.hadoop.hbase.Cell;
36 import org.apache.hadoop.hbase.HBaseTestingUtility;
37 import org.apache.hadoop.hbase.HConstants;
38 import org.apache.hadoop.hbase.KeyValue;
39 import org.apache.hadoop.hbase.KeyValue.Type;
40 import org.apache.hadoop.hbase.KeyValueUtil;
41 import org.apache.hadoop.hbase.Tag;
42 import org.apache.hadoop.hbase.io.ByteArrayOutputStream;
43 import org.apache.hadoop.hbase.io.compress.Compression;
44 import org.apache.hadoop.hbase.io.compress.Compression.Algorithm;
45 import org.apache.hadoop.hbase.io.hfile.HFileContext;
46 import org.apache.hadoop.hbase.io.hfile.HFileContextBuilder;
47 import org.apache.hadoop.hbase.testclassification.LargeTests;
48 import org.apache.hadoop.hbase.util.Bytes;
49 import org.apache.hadoop.hbase.util.RedundantKVGenerator;
50 import org.junit.Assert;
51 import org.junit.Rule;
52 import org.junit.Test;
53 import org.junit.experimental.categories.Category;
54 import org.junit.rules.TestRule;
55 import org.junit.runner.RunWith;
56 import org.junit.runners.Parameterized;
57 import org.junit.runners.Parameterized.Parameters;
58
59
60
61
62
63 @Category(LargeTests.class)
64 @RunWith(Parameterized.class)
65 public class TestDataBlockEncoders {
66
67 private static final Log LOG = LogFactory.getLog(TestDataBlockEncoders.class);
68
69 @Rule public final TestRule timeout = CategoryBasedTimeout.builder().
70 withTimeout(this.getClass()).withLookingForStuckThread(true).build();
71
72 private static int NUMBER_OF_KV = 10000;
73 private static int NUM_RANDOM_SEEKS = 1000;
74
75 private static int ENCODED_DATA_OFFSET = HConstants.HFILEBLOCK_HEADER_SIZE
76 + DataBlockEncoding.ID_SIZE;
77 static final byte[] HFILEBLOCK_DUMMY_HEADER = new byte[HConstants.HFILEBLOCK_HEADER_SIZE];
78
79 private RedundantKVGenerator generator = new RedundantKVGenerator();
80 private Random randomizer = new Random(42l);
81
82 private final boolean includesMemstoreTS;
83 private final boolean includesTags;
84
85 @Parameters
86 public static Collection<Object[]> parameters() {
87 return HBaseTestingUtility.MEMSTORETS_TAGS_PARAMETRIZED;
88 }
89 public TestDataBlockEncoders(boolean includesMemstoreTS, boolean includesTag) {
90 this.includesMemstoreTS = includesMemstoreTS;
91 this.includesTags = includesTag;
92 }
93
94 private HFileBlockEncodingContext getEncodingContext(Compression.Algorithm algo,
95 DataBlockEncoding encoding) {
96 DataBlockEncoder encoder = encoding.getEncoder();
97 HFileContext meta = new HFileContextBuilder()
98 .withHBaseCheckSum(false)
99 .withIncludesMvcc(includesMemstoreTS)
100 .withIncludesTags(includesTags)
101 .withCompression(algo).build();
102 if (encoder != null) {
103 return encoder.newDataBlockEncodingContext(encoding, HFILEBLOCK_DUMMY_HEADER, meta);
104 } else {
105 return new HFileBlockDefaultEncodingContext(encoding, HFILEBLOCK_DUMMY_HEADER, meta);
106 }
107 }
108
109
110
111
112
113
114
115 @Test
116 public void testEmptyKeyValues() throws IOException {
117 List<KeyValue> kvList = new ArrayList<KeyValue>();
118 byte[] row = new byte[0];
119 byte[] family = new byte[0];
120 byte[] qualifier = new byte[0];
121 byte[] value = new byte[0];
122 if (!includesTags) {
123 kvList.add(new KeyValue(row, family, qualifier, 0l, value));
124 kvList.add(new KeyValue(row, family, qualifier, 0l, value));
125 } else {
126 byte[] metaValue1 = Bytes.toBytes("metaValue1");
127 byte[] metaValue2 = Bytes.toBytes("metaValue2");
128 kvList.add(new KeyValue(row, family, qualifier, 0l, value, new Tag[] { new Tag((byte) 1,
129 metaValue1) }));
130 kvList.add(new KeyValue(row, family, qualifier, 0l, value, new Tag[] { new Tag((byte) 1,
131 metaValue2) }));
132 }
133 testEncodersOnDataset(kvList, includesMemstoreTS, includesTags);
134 }
135
136
137
138
139
140
141
142 @Test
143 public void testNegativeTimestamps() throws IOException {
144 List<KeyValue> kvList = new ArrayList<KeyValue>();
145 byte[] row = new byte[0];
146 byte[] family = new byte[0];
147 byte[] qualifier = new byte[0];
148 byte[] value = new byte[0];
149 if (includesTags) {
150 byte[] metaValue1 = Bytes.toBytes("metaValue1");
151 byte[] metaValue2 = Bytes.toBytes("metaValue2");
152 kvList.add(new KeyValue(row, family, qualifier, 0l, value, new Tag[] { new Tag((byte) 1,
153 metaValue1) }));
154 kvList.add(new KeyValue(row, family, qualifier, 0l, value, new Tag[] { new Tag((byte) 1,
155 metaValue2) }));
156 } else {
157 kvList.add(new KeyValue(row, family, qualifier, -1l, Type.Put, value));
158 kvList.add(new KeyValue(row, family, qualifier, -2l, Type.Put, value));
159 }
160 testEncodersOnDataset(kvList, includesMemstoreTS, includesTags);
161 }
162
163
164
165
166
167
168
169 @Test
170 public void testExecutionOnSample() throws IOException {
171 List<KeyValue> kvList = generator.generateTestKeyValues(NUMBER_OF_KV, includesTags);
172 testEncodersOnDataset(kvList, includesMemstoreTS, includesTags);
173 }
174
175
176
177
178 @Test
179 public void testSeekingOnSample() throws IOException {
180 List<KeyValue> sampleKv = generator.generateTestKeyValues(NUMBER_OF_KV, includesTags);
181
182
183 List<DataBlockEncoder.EncodedSeeker> encodedSeekers =
184 new ArrayList<DataBlockEncoder.EncodedSeeker>();
185 for (DataBlockEncoding encoding : DataBlockEncoding.values()) {
186 LOG.info("Encoding: " + encoding);
187
188
189 if (encoding == DataBlockEncoding.PREFIX_TREE) continue;
190 DataBlockEncoder encoder = encoding.getEncoder();
191 if (encoder == null) {
192 continue;
193 }
194 LOG.info("Encoder: " + encoder);
195 ByteBuffer encodedBuffer = encodeKeyValues(encoding, sampleKv,
196 getEncodingContext(Compression.Algorithm.NONE, encoding));
197 HFileContext meta = new HFileContextBuilder()
198 .withHBaseCheckSum(false)
199 .withIncludesMvcc(includesMemstoreTS)
200 .withIncludesTags(includesTags)
201 .withCompression(Compression.Algorithm.NONE)
202 .build();
203 DataBlockEncoder.EncodedSeeker seeker = encoder.createSeeker(KeyValue.COMPARATOR,
204 encoder.newDataBlockDecodingContext(meta));
205 seeker.setCurrentBuffer(encodedBuffer);
206 encodedSeekers.add(seeker);
207 }
208 LOG.info("Testing it!");
209
210
211 for (boolean seekBefore : new boolean[] { false, true }) {
212 for (int i = 0; i < NUM_RANDOM_SEEKS; ++i) {
213 int keyValueId;
214 if (!seekBefore) {
215 keyValueId = randomizer.nextInt(sampleKv.size());
216 } else {
217 keyValueId = randomizer.nextInt(sampleKv.size() - 1) + 1;
218 }
219
220 KeyValue keyValue = sampleKv.get(keyValueId);
221 checkSeekingConsistency(encodedSeekers, seekBefore, keyValue);
222 }
223 }
224
225
226 LOG.info("Checking edge cases");
227 checkSeekingConsistency(encodedSeekers, false, sampleKv.get(0));
228 for (boolean seekBefore : new boolean[] { false, true }) {
229 checkSeekingConsistency(encodedSeekers, seekBefore, sampleKv.get(sampleKv.size() - 1));
230 KeyValue midKv = sampleKv.get(sampleKv.size() / 2);
231 KeyValue lastMidKv =KeyValueUtil.createLastOnRowCol(midKv);
232 checkSeekingConsistency(encodedSeekers, seekBefore, lastMidKv);
233 }
234 LOG.info("Done");
235 }
236
237 static ByteBuffer encodeKeyValues(DataBlockEncoding encoding, List<KeyValue> kvs,
238 HFileBlockEncodingContext encodingContext) throws IOException {
239 DataBlockEncoder encoder = encoding.getEncoder();
240 ByteArrayOutputStream baos = new ByteArrayOutputStream();
241 baos.write(HFILEBLOCK_DUMMY_HEADER);
242 DataOutputStream dos = new DataOutputStream(baos);
243 encoder.startBlockEncoding(encodingContext, dos);
244 for (KeyValue kv : kvs) {
245 encoder.encode(kv, encodingContext, dos);
246 }
247 encoder.endBlockEncoding(encodingContext, dos, baos.getBuffer());
248 byte[] encodedData = new byte[baos.size() - ENCODED_DATA_OFFSET];
249 System.arraycopy(baos.toByteArray(), ENCODED_DATA_OFFSET, encodedData, 0, encodedData.length);
250 return ByteBuffer.wrap(encodedData);
251 }
252
253 @Test
254 public void testNextOnSample() throws IOException {
255 List<KeyValue> sampleKv = generator.generateTestKeyValues(NUMBER_OF_KV, includesTags);
256
257 for (DataBlockEncoding encoding : DataBlockEncoding.values()) {
258 if (encoding.getEncoder() == null) {
259 continue;
260 }
261 DataBlockEncoder encoder = encoding.getEncoder();
262 ByteBuffer encodedBuffer = encodeKeyValues(encoding, sampleKv,
263 getEncodingContext(Compression.Algorithm.NONE, encoding));
264 HFileContext meta = new HFileContextBuilder()
265 .withHBaseCheckSum(false)
266 .withIncludesMvcc(includesMemstoreTS)
267 .withIncludesTags(includesTags)
268 .withCompression(Compression.Algorithm.NONE)
269 .build();
270 DataBlockEncoder.EncodedSeeker seeker = encoder.createSeeker(KeyValue.COMPARATOR,
271 encoder.newDataBlockDecodingContext(meta));
272 seeker.setCurrentBuffer(encodedBuffer);
273 int i = 0;
274 do {
275 KeyValue expectedKeyValue = sampleKv.get(i);
276 KeyValue keyValue = KeyValueUtil.copyToNewKeyValue(seeker.getKeyValue());
277 if (0 != Bytes.compareTo(keyValue.getBuffer(), keyValue.getOffset(), keyValue.getLength(),
278 expectedKeyValue.getBuffer(), expectedKeyValue.getOffset(),
279 expectedKeyValue.getLength())) {
280
281 int commonPrefix = 0;
282 byte[] left = keyValue.getBuffer();
283 byte[] right = expectedKeyValue.getBuffer();
284 int leftOff = keyValue.getOffset();
285 int rightOff = expectedKeyValue.getOffset();
286 int length = Math.min(keyValue.getLength(), expectedKeyValue.getLength());
287 while (commonPrefix < length
288 && left[commonPrefix + leftOff] == right[commonPrefix + rightOff]) {
289 commonPrefix++;
290 }
291
292 fail(String.format("next() produces wrong results "
293 + "encoder: %s i: %d commonPrefix: %d" + "\n expected %s\n actual %s", encoder
294 .toString(), i, commonPrefix, Bytes.toStringBinary(expectedKeyValue.getBuffer(),
295 expectedKeyValue.getOffset(), expectedKeyValue.getLength()), Bytes
296 .toStringBinary(keyValue.getBuffer())));
297 }
298 i++;
299 } while (seeker.next());
300 }
301 }
302
303
304
305
306
307 @Test
308 public void testFirstKeyInBlockOnSample() throws IOException {
309 List<KeyValue> sampleKv = generator.generateTestKeyValues(NUMBER_OF_KV, includesTags);
310
311 for (DataBlockEncoding encoding : DataBlockEncoding.values()) {
312 if (encoding.getEncoder() == null) {
313 continue;
314 }
315 DataBlockEncoder encoder = encoding.getEncoder();
316 ByteBuffer encodedBuffer = encodeKeyValues(encoding, sampleKv,
317 getEncodingContext(Compression.Algorithm.NONE, encoding));
318 ByteBuffer keyBuffer = encoder.getFirstKeyInBlock(encodedBuffer);
319 KeyValue firstKv = sampleKv.get(0);
320 if (0 != Bytes.compareTo(keyBuffer.array(), keyBuffer.arrayOffset(), keyBuffer.limit(),
321 firstKv.getBuffer(), firstKv.getKeyOffset(), firstKv.getKeyLength())) {
322
323 int commonPrefix = 0;
324 int length = Math.min(keyBuffer.limit(), firstKv.getKeyLength());
325 while (commonPrefix < length
326 && keyBuffer.array()[keyBuffer.arrayOffset() + commonPrefix] == firstKv.getBuffer()[firstKv
327 .getKeyOffset() + commonPrefix]) {
328 commonPrefix++;
329 }
330 fail(String.format("Bug in '%s' commonPrefix %d", encoder.toString(), commonPrefix));
331 }
332 }
333 }
334
335 private void checkSeekingConsistency(List<DataBlockEncoder.EncodedSeeker> encodedSeekers,
336 boolean seekBefore, KeyValue keyValue) {
337 ByteBuffer expectedKeyValue = null;
338 ByteBuffer expectedKey = null;
339 ByteBuffer expectedValue = null;
340 for (DataBlockEncoder.EncodedSeeker seeker : encodedSeekers) {
341 seeker.seekToKeyInBlock(keyValue, seekBefore);
342 seeker.rewind();
343
344 ByteBuffer actualKeyValue = KeyValueUtil.copyKeyToNewByteBuffer(seeker.getKeyValue());
345 ByteBuffer actualKey = seeker.getKeyDeepCopy();
346 ByteBuffer actualValue = seeker.getValueShallowCopy();
347
348 if (expectedKeyValue != null) {
349 assertEquals(expectedKeyValue, actualKeyValue);
350 } else {
351 expectedKeyValue = actualKeyValue;
352 }
353
354 if (expectedKey != null) {
355 assertEquals(expectedKey, actualKey);
356 } else {
357 expectedKey = actualKey;
358 }
359
360 if (expectedValue != null) {
361 assertEquals(expectedValue, actualValue);
362 } else {
363 expectedValue = actualValue;
364 }
365 }
366 }
367
368 private void testEncodersOnDataset(List<KeyValue> kvList, boolean includesMemstoreTS,
369 boolean includesTags) throws IOException {
370 ByteBuffer unencodedDataBuf = RedundantKVGenerator.convertKvToByteBuffer(kvList,
371 includesMemstoreTS);
372 HFileContext fileContext = new HFileContextBuilder().withIncludesMvcc(includesMemstoreTS)
373 .withIncludesTags(includesTags).build();
374 for (DataBlockEncoding encoding : DataBlockEncoding.values()) {
375 DataBlockEncoder encoder = encoding.getEncoder();
376 if (encoder == null) {
377 continue;
378 }
379 HFileBlockEncodingContext encodingContext = new HFileBlockDefaultEncodingContext(encoding,
380 HFILEBLOCK_DUMMY_HEADER, fileContext);
381
382 ByteArrayOutputStream baos = new ByteArrayOutputStream();
383 baos.write(HFILEBLOCK_DUMMY_HEADER);
384 DataOutputStream dos = new DataOutputStream(baos);
385 encoder.startBlockEncoding(encodingContext, dos);
386 for (KeyValue kv : kvList) {
387 encoder.encode(kv, encodingContext, dos);
388 }
389 encoder.endBlockEncoding(encodingContext, dos, baos.getBuffer());
390 byte[] encodedData = baos.toByteArray();
391
392 testAlgorithm(encodedData, unencodedDataBuf, encoder);
393 }
394 }
395
396 @Test
397 public void testZeroByte() throws IOException {
398 List<KeyValue> kvList = new ArrayList<KeyValue>();
399 byte[] row = Bytes.toBytes("abcd");
400 byte[] family = new byte[] { 'f' };
401 byte[] qualifier0 = new byte[] { 'b' };
402 byte[] qualifier1 = new byte[] { 'c' };
403 byte[] value0 = new byte[] { 'd' };
404 byte[] value1 = new byte[] { 0x00 };
405 if (includesTags) {
406 kvList.add(new KeyValue(row, family, qualifier0, 0, value0, new Tag[] { new Tag((byte) 1,
407 "value1") }));
408 kvList.add(new KeyValue(row, family, qualifier1, 0, value1, new Tag[] { new Tag((byte) 1,
409 "value1") }));
410 } else {
411 kvList.add(new KeyValue(row, family, qualifier0, 0, Type.Put, value0));
412 kvList.add(new KeyValue(row, family, qualifier1, 0, Type.Put, value1));
413 }
414 testEncodersOnDataset(kvList, includesMemstoreTS, includesTags);
415 }
416
417 private void testAlgorithm(byte[] encodedData, ByteBuffer unencodedDataBuf,
418 DataBlockEncoder encoder) throws IOException {
419
420 ByteArrayInputStream bais = new ByteArrayInputStream(encodedData, ENCODED_DATA_OFFSET,
421 encodedData.length - ENCODED_DATA_OFFSET);
422 DataInputStream dis = new DataInputStream(bais);
423 ByteBuffer actualDataset;
424 HFileContext meta = new HFileContextBuilder().withHBaseCheckSum(false)
425 .withIncludesMvcc(includesMemstoreTS).withIncludesTags(includesTags)
426 .withCompression(Compression.Algorithm.NONE).build();
427 actualDataset = encoder.decodeKeyValues(dis, encoder.newDataBlockDecodingContext(meta));
428 actualDataset.rewind();
429
430
431
432
433 assertEquals("Encoding -> decoding gives different results for " + encoder,
434 Bytes.toStringBinary(unencodedDataBuf), Bytes.toStringBinary(actualDataset));
435 }
436
437 @Test
438 public void testRowIndexWithTagsButNoTagsInCell() throws IOException {
439 List<KeyValue> kvList = new ArrayList<>();
440 byte[] row = new byte[0];
441 byte[] family = new byte[0];
442 byte[] qualifier = new byte[0];
443 byte[] value = new byte[0];
444 KeyValue expectedKV = new KeyValue(row, family, qualifier, -1L, Type.Put, value);
445 kvList.add(expectedKV);
446 DataBlockEncoding encoding = DataBlockEncoding.ROW_INDEX_V1;
447 DataBlockEncoder encoder = encoding.getEncoder();
448 ByteBuffer encodedBuffer =
449 encodeKeyValues(encoding, kvList, getEncodingContext(Algorithm.NONE, encoding));
450 HFileContext meta =
451 new HFileContextBuilder().withHBaseCheckSum(false).withIncludesMvcc(includesMemstoreTS)
452 .withIncludesTags(includesTags).withCompression(Compression.Algorithm.NONE).build();
453 DataBlockEncoder.EncodedSeeker seeker =
454 encoder.createSeeker(KeyValue.COMPARATOR, encoder.newDataBlockDecodingContext(meta));
455 seeker.setCurrentBuffer(encodedBuffer);
456 Cell cell = seeker.getKeyValue();
457 Assert.assertEquals(expectedKV.getLength(), ((KeyValue) cell).getLength());
458 }
459
460 }