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.io.hfile;
21
22 import static org.junit.Assert.assertEquals;
23 import static org.junit.Assert.assertFalse;
24 import static org.junit.Assert.assertTrue;
25
26 import java.io.ByteArrayOutputStream;
27 import java.io.DataOutputStream;
28 import java.io.IOException;
29 import java.nio.ByteBuffer;
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.Collection;
33 import java.util.HashSet;
34 import java.util.List;
35 import java.util.Random;
36 import java.util.Set;
37
38 import org.apache.commons.logging.Log;
39 import org.apache.commons.logging.LogFactory;
40 import org.apache.hadoop.conf.Configuration;
41 import org.apache.hadoop.fs.FSDataInputStream;
42 import org.apache.hadoop.fs.FSDataOutputStream;
43 import org.apache.hadoop.fs.FileSystem;
44 import org.apache.hadoop.fs.Path;
45 import org.apache.hadoop.hbase.CellUtil;
46 import org.apache.hadoop.hbase.HBaseTestingUtility;
47 import org.apache.hadoop.hbase.KeyValue;
48 import org.apache.hadoop.hbase.fs.HFileSystem;
49 import org.apache.hadoop.hbase.io.compress.Compression;
50 import org.apache.hadoop.hbase.io.compress.Compression.Algorithm;
51 import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding;
52 import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexChunk;
53 import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexReader;
54 import org.apache.hadoop.hbase.testclassification.MediumTests;
55 import org.apache.hadoop.hbase.util.Bytes;
56 import org.apache.hadoop.hbase.util.ClassSize;
57 import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
58 import org.junit.Before;
59 import org.junit.Test;
60 import org.junit.experimental.categories.Category;
61 import org.junit.runner.RunWith;
62 import org.junit.runners.Parameterized;
63 import org.junit.runners.Parameterized.Parameters;
64
65 @RunWith(Parameterized.class)
66 @Category(MediumTests.class)
67 public class TestHFileBlockIndex {
68
69 @Parameters
70 public static Collection<Object[]> compressionAlgorithms() {
71 return HBaseTestingUtility.COMPRESSION_ALGORITHMS_PARAMETERIZED;
72 }
73
74 public TestHFileBlockIndex(Compression.Algorithm compr) {
75 this.compr = compr;
76 }
77
78 private static final Log LOG = LogFactory.getLog(TestHFileBlockIndex.class);
79
80 private static final int NUM_DATA_BLOCKS = 1000;
81 private static final HBaseTestingUtility TEST_UTIL =
82 new HBaseTestingUtility();
83
84 private static final int SMALL_BLOCK_SIZE = 4096;
85 private static final int NUM_KV = 10000;
86
87 private static FileSystem fs;
88 private Path path;
89 private Random rand;
90 private long rootIndexOffset;
91 private int numRootEntries;
92 private int numLevels;
93 private static final List<byte[]> keys = new ArrayList<byte[]>();
94 private final Compression.Algorithm compr;
95 private byte[] firstKeyInFile;
96 private Configuration conf;
97
98 private static final int[] INDEX_CHUNK_SIZES = { 4096, 512, 384 };
99 private static final int[] EXPECTED_NUM_LEVELS = { 2, 3, 4 };
100 private static final int[] UNCOMPRESSED_INDEX_SIZES =
101 { 19187, 21813, 23086 };
102
103 private static final boolean includesMemstoreTS = true;
104
105 static {
106 assert INDEX_CHUNK_SIZES.length == EXPECTED_NUM_LEVELS.length;
107 assert INDEX_CHUNK_SIZES.length == UNCOMPRESSED_INDEX_SIZES.length;
108 }
109
110 @Before
111 public void setUp() throws IOException {
112 keys.clear();
113 rand = new Random(2389757);
114 firstKeyInFile = null;
115 conf = TEST_UTIL.getConfiguration();
116
117
118 conf.setInt(HFile.FORMAT_VERSION_KEY, HFile.MAX_FORMAT_VERSION);
119
120 fs = HFileSystem.get(conf);
121 }
122
123 @Test
124 public void testBlockIndex() throws IOException {
125 testBlockIndexInternals(false);
126 clear();
127 testBlockIndexInternals(true);
128 }
129
130 private void clear() throws IOException {
131 keys.clear();
132 rand = new Random(2389757);
133 firstKeyInFile = null;
134 conf = TEST_UTIL.getConfiguration();
135
136
137 conf.setInt(HFile.FORMAT_VERSION_KEY, 3);
138
139 fs = HFileSystem.get(conf);
140 }
141
142 private void testBlockIndexInternals(boolean useTags) throws IOException {
143 path = new Path(TEST_UTIL.getDataTestDir(), "block_index_" + compr + useTags);
144 writeWholeIndex(useTags);
145 readIndex(useTags);
146 }
147
148
149
150
151
152 private static class BlockReaderWrapper implements HFile.CachingBlockReader {
153
154 private HFileBlock.FSReader realReader;
155 private long prevOffset;
156 private long prevOnDiskSize;
157 private boolean prevPread;
158 private HFileBlock prevBlock;
159
160 public int hitCount = 0;
161 public int missCount = 0;
162
163 public BlockReaderWrapper(HFileBlock.FSReader realReader) {
164 this.realReader = realReader;
165 }
166
167 @Override
168 public HFileBlock readBlock(long offset, long onDiskSize,
169 boolean cacheBlock, boolean pread, boolean isCompaction,
170 boolean updateCacheMetrics, BlockType expectedBlockType,
171 DataBlockEncoding expectedDataBlockEncoding)
172 throws IOException {
173 if (offset == prevOffset && onDiskSize == prevOnDiskSize &&
174 pread == prevPread) {
175 hitCount += 1;
176 return prevBlock;
177 }
178
179 missCount += 1;
180 prevBlock = realReader.readBlockData(offset, onDiskSize,
181 -1, pread, false);
182 prevOffset = offset;
183 prevOnDiskSize = onDiskSize;
184 prevPread = pread;
185
186 return prevBlock;
187 }
188 }
189
190 private void readIndex(boolean useTags) throws IOException {
191 long fileSize = fs.getFileStatus(path).getLen();
192 LOG.info("Size of " + path + ": " + fileSize);
193
194 FSDataInputStream istream = fs.open(path);
195 HFileContext meta = new HFileContextBuilder()
196 .withHBaseCheckSum(true)
197 .withIncludesMvcc(includesMemstoreTS)
198 .withIncludesTags(useTags)
199 .withCompression(compr)
200 .build();
201 HFileBlock.FSReader blockReader = new HFileBlock.FSReaderImpl(istream, fs.getFileStatus(path)
202 .getLen(), meta);
203
204 BlockReaderWrapper brw = new BlockReaderWrapper(blockReader);
205 HFileBlockIndex.BlockIndexReader indexReader =
206 new HFileBlockIndex.BlockIndexReader(
207 KeyValue.RAW_COMPARATOR, numLevels, brw);
208
209 indexReader.readRootIndex(blockReader.blockRange(rootIndexOffset,
210 fileSize).nextBlockWithBlockType(BlockType.ROOT_INDEX), numRootEntries);
211
212 long prevOffset = -1;
213 int i = 0;
214 int expectedHitCount = 0;
215 int expectedMissCount = 0;
216 LOG.info("Total number of keys: " + keys.size());
217 for (byte[] key : keys) {
218 assertTrue(key != null);
219 assertTrue(indexReader != null);
220 HFileBlock b =
221 indexReader.seekToDataBlock(new KeyValue.KeyOnlyKeyValue(key, 0, key.length), null, true,
222 true, false, null);
223 if (KeyValue.COMPARATOR.compareFlatKey(key, firstKeyInFile) < 0) {
224 assertTrue(b == null);
225 ++i;
226 continue;
227 }
228
229 String keyStr = "key #" + i + ", " + Bytes.toStringBinary(key);
230
231 assertTrue("seekToDataBlock failed for " + keyStr, b != null);
232
233 if (prevOffset == b.getOffset()) {
234 assertEquals(++expectedHitCount, brw.hitCount);
235 } else {
236 LOG.info("First key in a new block: " + keyStr + ", block offset: "
237 + b.getOffset() + ")");
238 assertTrue(b.getOffset() > prevOffset);
239 assertEquals(++expectedMissCount, brw.missCount);
240 prevOffset = b.getOffset();
241 }
242 ++i;
243 }
244
245 istream.close();
246 }
247
248 private void writeWholeIndex(boolean useTags) throws IOException {
249 assertEquals(0, keys.size());
250 HFileContext meta = new HFileContextBuilder()
251 .withHBaseCheckSum(true)
252 .withIncludesMvcc(includesMemstoreTS)
253 .withIncludesTags(useTags)
254 .withCompression(compr)
255 .withBytesPerCheckSum(HFile.DEFAULT_BYTES_PER_CHECKSUM)
256 .build();
257 HFileBlock.Writer hbw = new HFileBlock.Writer(null,
258 meta);
259 FSDataOutputStream outputStream = fs.create(path);
260 HFileBlockIndex.BlockIndexWriter biw =
261 new HFileBlockIndex.BlockIndexWriter(hbw, null, null);
262
263 for (int i = 0; i < NUM_DATA_BLOCKS; ++i) {
264 hbw.startWriting(BlockType.DATA).write(String.valueOf(rand.nextInt(1000)).getBytes());
265 long blockOffset = outputStream.getPos();
266 hbw.writeHeaderAndData(outputStream);
267
268 byte[] firstKey = null;
269 byte[] family = Bytes.toBytes("f");
270 byte[] qualifier = Bytes.toBytes("q");
271 for (int j = 0; j < 16; ++j) {
272 byte[] k =
273 new KeyValue(TestHFileWriterV2.randomOrderedKey(rand, i * 16 + j), family, qualifier,
274 EnvironmentEdgeManager.currentTime(), KeyValue.Type.Put).getKey();
275 keys.add(k);
276 if (j == 8) {
277 firstKey = k;
278 }
279 }
280 assertTrue(firstKey != null);
281 if (firstKeyInFile == null) {
282 firstKeyInFile = firstKey;
283 }
284 biw.addEntry(firstKey, blockOffset, hbw.getOnDiskSizeWithHeader());
285
286 writeInlineBlocks(hbw, outputStream, biw, false);
287 }
288 writeInlineBlocks(hbw, outputStream, biw, true);
289 rootIndexOffset = biw.writeIndexBlocks(outputStream);
290 outputStream.close();
291
292 numLevels = biw.getNumLevels();
293 numRootEntries = biw.getNumRootEntries();
294
295 LOG.info("Index written: numLevels=" + numLevels + ", numRootEntries=" +
296 numRootEntries + ", rootIndexOffset=" + rootIndexOffset);
297 }
298
299 private void writeInlineBlocks(HFileBlock.Writer hbw,
300 FSDataOutputStream outputStream, HFileBlockIndex.BlockIndexWriter biw,
301 boolean isClosing) throws IOException {
302 while (biw.shouldWriteBlock(isClosing)) {
303 long offset = outputStream.getPos();
304 biw.writeInlineBlock(hbw.startWriting(biw.getInlineBlockType()));
305 hbw.writeHeaderAndData(outputStream);
306 biw.blockWritten(offset, hbw.getOnDiskSizeWithHeader(),
307 hbw.getUncompressedSizeWithoutHeader());
308 LOG.info("Wrote an inline index block at " + offset + ", size " +
309 hbw.getOnDiskSizeWithHeader());
310 }
311 }
312
313 private static final long getDummyFileOffset(int i) {
314 return i * 185 + 379;
315 }
316
317 private static final int getDummyOnDiskSize(int i) {
318 return i * i * 37 + i * 19 + 13;
319 }
320
321 @Test
322 public void testSecondaryIndexBinarySearch() throws IOException {
323 int numTotalKeys = 99;
324 assertTrue(numTotalKeys % 2 == 1);
325
326
327 int numSearchedKeys = (numTotalKeys - 1) / 2;
328
329 ByteArrayOutputStream baos = new ByteArrayOutputStream();
330 DataOutputStream dos = new DataOutputStream(baos);
331
332 dos.writeInt(numSearchedKeys);
333 int curAllEntriesSize = 0;
334 int numEntriesAdded = 0;
335
336
337
338 int secondaryIndexEntries[] = new int[numTotalKeys];
339
340 for (int i = 0; i < numTotalKeys; ++i) {
341 byte[] k = TestHFileWriterV2.randomOrderedKey(rand, i * 2);
342 KeyValue cell = new KeyValue(k, Bytes.toBytes("f"), Bytes.toBytes("q"),
343 Bytes.toBytes("val"));
344
345 keys.add(cell.getKey());
346 String msgPrefix = "Key #" + i + " (" + Bytes.toStringBinary(k) + "): ";
347 StringBuilder padding = new StringBuilder();
348 while (msgPrefix.length() + padding.length() < 70)
349 padding.append(' ');
350 msgPrefix += padding;
351 if (i % 2 == 1) {
352 dos.writeInt(curAllEntriesSize);
353 secondaryIndexEntries[i] = curAllEntriesSize;
354 LOG.info(msgPrefix + "secondary index entry #" + ((i - 1) / 2) +
355 ", offset " + curAllEntriesSize);
356 curAllEntriesSize += cell.getKey().length
357 + HFileBlockIndex.SECONDARY_INDEX_ENTRY_OVERHEAD;
358 ++numEntriesAdded;
359 } else {
360 secondaryIndexEntries[i] = -1;
361 LOG.info(msgPrefix + "not in the searched array");
362 }
363 }
364
365
366 for (int i = 0; i < keys.size() - 1; ++i)
367 assertTrue(KeyValue.COMPARATOR.compare(
368 new KeyValue.KeyOnlyKeyValue(keys.get(i), 0, keys.get(i).length),
369 new KeyValue.KeyOnlyKeyValue(keys.get(i + 1), 0, keys.get(i + 1).length)) < 0);
370
371 dos.writeInt(curAllEntriesSize);
372 assertEquals(numSearchedKeys, numEntriesAdded);
373 int secondaryIndexOffset = dos.size();
374 assertEquals(Bytes.SIZEOF_INT * (numSearchedKeys + 2),
375 secondaryIndexOffset);
376
377 for (int i = 1; i <= numTotalKeys - 1; i += 2) {
378 assertEquals(dos.size(),
379 secondaryIndexOffset + secondaryIndexEntries[i]);
380 long dummyFileOffset = getDummyFileOffset(i);
381 int dummyOnDiskSize = getDummyOnDiskSize(i);
382 LOG.debug("Storing file offset=" + dummyFileOffset + " and onDiskSize=" +
383 dummyOnDiskSize + " at offset " + dos.size());
384 dos.writeLong(dummyFileOffset);
385 dos.writeInt(dummyOnDiskSize);
386 LOG.debug("Stored key " + ((i - 1) / 2) +" at offset " + dos.size());
387 dos.write(keys.get(i));
388 }
389
390 dos.writeInt(curAllEntriesSize);
391
392 ByteBuffer nonRootIndex = ByteBuffer.wrap(baos.toByteArray());
393 for (int i = 0; i < numTotalKeys; ++i) {
394 byte[] searchKey = keys.get(i);
395 byte[] arrayHoldingKey = new byte[searchKey.length +
396 searchKey.length / 2];
397
398
399
400 System.arraycopy(searchKey, 0, arrayHoldingKey, searchKey.length / 2,
401 searchKey.length);
402
403 KeyValue.KeyOnlyKeyValue cell = new KeyValue.KeyOnlyKeyValue(
404 arrayHoldingKey, searchKey.length / 2, searchKey.length);
405 int searchResult = BlockIndexReader.binarySearchNonRootIndex(cell,
406 nonRootIndex, KeyValue.COMPARATOR);
407 String lookupFailureMsg = "Failed to look up key #" + i + " ("
408 + Bytes.toStringBinary(searchKey) + ")";
409
410 int expectedResult;
411 int referenceItem;
412
413 if (i % 2 == 1) {
414
415
416 expectedResult = (i - 1) / 2;
417 referenceItem = i;
418 } else {
419
420
421
422 expectedResult = i / 2 - 1;
423 referenceItem = i - 1;
424 }
425
426 assertEquals(lookupFailureMsg, expectedResult, searchResult);
427
428
429
430 boolean locateBlockResult =
431 (BlockIndexReader.locateNonRootIndexEntry(nonRootIndex, cell,
432 KeyValue.COMPARATOR) != -1);
433
434 if (i == 0) {
435 assertFalse(locateBlockResult);
436 } else {
437 assertTrue(locateBlockResult);
438 String errorMsg = "i=" + i + ", position=" + nonRootIndex.position();
439 assertEquals(errorMsg, getDummyFileOffset(referenceItem),
440 nonRootIndex.getLong());
441 assertEquals(errorMsg, getDummyOnDiskSize(referenceItem),
442 nonRootIndex.getInt());
443 }
444 }
445
446 }
447
448 @Test
449 public void testBlockIndexChunk() throws IOException {
450 BlockIndexChunk c = new BlockIndexChunk();
451 ByteArrayOutputStream baos = new ByteArrayOutputStream();
452 int N = 1000;
453 int[] numSubEntriesAt = new int[N];
454 int numSubEntries = 0;
455 for (int i = 0; i < N; ++i) {
456 baos.reset();
457 DataOutputStream dos = new DataOutputStream(baos);
458 c.writeNonRoot(dos);
459 assertEquals(c.getNonRootSize(), dos.size());
460
461 baos.reset();
462 dos = new DataOutputStream(baos);
463 c.writeRoot(dos);
464 assertEquals(c.getRootSize(), dos.size());
465
466 byte[] k = TestHFileWriterV2.randomOrderedKey(rand, i);
467 numSubEntries += rand.nextInt(5) + 1;
468 keys.add(k);
469 c.add(k, getDummyFileOffset(i), getDummyOnDiskSize(i), numSubEntries);
470 }
471
472
473
474
475 for (int i = 0; i < N; ++i) {
476 for (int j = i == 0 ? 0 : numSubEntriesAt[i - 1];
477 j < numSubEntriesAt[i];
478 ++j) {
479 assertEquals(i, c.getEntryBySubEntry(j));
480 }
481 }
482 }
483
484
485 @Test
486 public void testHeapSizeForBlockIndex() throws IOException {
487 Class<HFileBlockIndex.BlockIndexReader> cl =
488 HFileBlockIndex.BlockIndexReader.class;
489 long expected = ClassSize.estimateBase(cl, false);
490
491 HFileBlockIndex.BlockIndexReader bi =
492 new HFileBlockIndex.BlockIndexReader(KeyValue.RAW_COMPARATOR, 1);
493 long actual = bi.heapSize();
494
495
496
497
498 expected -= ClassSize.align(3 * ClassSize.ARRAY);
499
500 if (expected != actual) {
501 ClassSize.estimateBase(cl, true);
502 assertEquals(expected, actual);
503 }
504 }
505
506
507
508
509
510 @Test
511 public void testMidKeyOnLeafIndexBlockBoundary() throws IOException {
512 Path hfilePath = new Path(TEST_UTIL.getDataTestDir(),
513 "hfile_for_midkey");
514 int maxChunkSize = 512;
515 conf.setInt(HFileBlockIndex.MAX_CHUNK_SIZE_KEY, maxChunkSize);
516
517 conf.setBoolean(CacheConfig.CACHE_INDEX_BLOCKS_ON_WRITE_KEY, true);
518
519 CacheConfig cacheConf = new CacheConfig(conf);
520 BlockCache blockCache = cacheConf.getBlockCache();
521
522 blockCache.evictBlocksByHfileName(hfilePath.getName());
523
524 {
525 HFileContext meta = new HFileContextBuilder()
526 .withBlockSize(SMALL_BLOCK_SIZE)
527 .withCompression(Algorithm.NONE)
528 .withDataBlockEncoding(DataBlockEncoding.NONE)
529 .build();
530 HFile.Writer writer =
531 HFile.getWriterFactory(conf, cacheConf)
532 .withPath(fs, hfilePath)
533 .withFileContext(meta)
534 .create();
535 Random rand = new Random(19231737);
536 byte[] family = Bytes.toBytes("f");
537 byte[] qualifier = Bytes.toBytes("q");
538 int kvNumberToBeWritten = 16;
539
540
541 for (int i = 0; i < kvNumberToBeWritten; ++i) {
542 byte[] row = TestHFileWriterV2.randomOrderedFixedLengthKey(rand, i, 30);
543
544
545 KeyValue kv =
546 new KeyValue(row, family, qualifier, EnvironmentEdgeManager.currentTime(),
547 TestHFileWriterV2.randomFixedLengthValue(rand, SMALL_BLOCK_SIZE));
548 writer.append(kv);
549 }
550 writer.close();
551 }
552
553
554 conf.setBoolean(CacheConfig.CACHE_INDEX_BLOCKS_ON_WRITE_KEY, false);
555
556
557 HFile.Reader reader = HFile.createReader(fs, hfilePath, cacheConf, conf);
558
559 boolean hasArrayIndexOutOfBoundsException = false;
560 try {
561
562 reader.midkey();
563 } catch (ArrayIndexOutOfBoundsException e) {
564 hasArrayIndexOutOfBoundsException = true;
565 } finally {
566 reader.close();
567 }
568
569
570 assertFalse(hasArrayIndexOutOfBoundsException);
571 }
572
573
574
575
576
577
578
579
580 @Test
581 public void testHFileWriterAndReader() throws IOException {
582 Path hfilePath = new Path(TEST_UTIL.getDataTestDir(),
583 "hfile_for_block_index");
584 CacheConfig cacheConf = new CacheConfig(conf);
585 BlockCache blockCache = cacheConf.getBlockCache();
586
587 for (int testI = 0; testI < INDEX_CHUNK_SIZES.length; ++testI) {
588 int indexBlockSize = INDEX_CHUNK_SIZES[testI];
589 int expectedNumLevels = EXPECTED_NUM_LEVELS[testI];
590 LOG.info("Index block size: " + indexBlockSize + ", compression: "
591 + compr);
592
593 blockCache.evictBlocksByHfileName(hfilePath.getName());
594
595 conf.setInt(HFileBlockIndex.MAX_CHUNK_SIZE_KEY, indexBlockSize);
596 Set<String> keyStrSet = new HashSet<String>();
597 byte[][] keys = new byte[NUM_KV][];
598 byte[][] values = new byte[NUM_KV][];
599
600
601 {
602 HFileContext meta = new HFileContextBuilder()
603 .withBlockSize(SMALL_BLOCK_SIZE)
604 .withCompression(compr)
605 .build();
606 HFile.Writer writer =
607 HFile.getWriterFactory(conf, cacheConf)
608 .withPath(fs, hfilePath)
609 .withFileContext(meta)
610 .create();
611 Random rand = new Random(19231737);
612 byte[] family = Bytes.toBytes("f");
613 byte[] qualifier = Bytes.toBytes("q");
614 for (int i = 0; i < NUM_KV; ++i) {
615 byte[] row = TestHFileWriterV2.randomOrderedKey(rand, i);
616
617
618 KeyValue kv =
619 new KeyValue(row, family, qualifier, EnvironmentEdgeManager.currentTime(),
620 TestHFileWriterV2.randomValue(rand));
621 byte[] k = kv.getKey();
622 writer.append(kv);
623 keys[i] = k;
624 values[i] = CellUtil.cloneValue(kv);
625 keyStrSet.add(Bytes.toStringBinary(k));
626 if (i > 0) {
627 assertTrue(KeyValue.COMPARATOR.compareFlatKey(keys[i - 1],
628 keys[i]) < 0);
629 }
630 }
631
632 writer.close();
633 }
634
635
636 HFile.Reader reader = HFile.createReader(fs, hfilePath, cacheConf, conf);
637 assertEquals(expectedNumLevels,
638 reader.getTrailer().getNumDataIndexLevels());
639
640 assertTrue(Bytes.equals(keys[0], reader.getFirstKey()));
641 assertTrue(Bytes.equals(keys[NUM_KV - 1], reader.getLastKey()));
642 LOG.info("Last key: " + Bytes.toStringBinary(keys[NUM_KV - 1]));
643
644 for (boolean pread : new boolean[] { false, true }) {
645 HFileScanner scanner = reader.getScanner(true, pread);
646 for (int i = 0; i < NUM_KV; ++i) {
647 checkSeekTo(keys, scanner, i);
648 checkKeyValue("i=" + i, keys[i], values[i], scanner.getKey(),
649 scanner.getValue());
650 }
651 assertTrue(scanner.seekTo());
652 for (int i = NUM_KV - 1; i >= 0; --i) {
653 checkSeekTo(keys, scanner, i);
654 checkKeyValue("i=" + i, keys[i], values[i], scanner.getKey(),
655 scanner.getValue());
656 }
657 }
658
659
660 HFileReaderV2 reader2 = (HFileReaderV2) reader;
661 HFileBlock.FSReader fsReader = reader2.getUncachedBlockReader();
662
663 HFileBlock.BlockIterator iter = fsReader.blockRange(0,
664 reader.getTrailer().getLoadOnOpenDataOffset());
665 HFileBlock block;
666 List<byte[]> blockKeys = new ArrayList<byte[]>();
667 while ((block = iter.nextBlock()) != null) {
668 if (block.getBlockType() != BlockType.LEAF_INDEX)
669 return;
670 ByteBuffer b = block.getBufferReadOnly();
671 int n = b.getInt();
672
673 int entriesOffset = Bytes.SIZEOF_INT * (n + 2);
674
675
676 for (int i = 0; i < n; ++i) {
677 int keyRelOffset = b.getInt(Bytes.SIZEOF_INT * (i + 1));
678 int nextKeyRelOffset = b.getInt(Bytes.SIZEOF_INT * (i + 2));
679 int keyLen = nextKeyRelOffset - keyRelOffset;
680 int keyOffset = b.arrayOffset() + entriesOffset + keyRelOffset +
681 HFileBlockIndex.SECONDARY_INDEX_ENTRY_OVERHEAD;
682 byte[] blockKey = Arrays.copyOfRange(b.array(), keyOffset, keyOffset
683 + keyLen);
684 String blockKeyStr = Bytes.toString(blockKey);
685 blockKeys.add(blockKey);
686
687
688
689 assertTrue("Invalid block key from leaf-level block: " + blockKeyStr,
690 keyStrSet.contains(blockKeyStr));
691 }
692 }
693
694
695 assertEquals(
696 Bytes.toStringBinary(blockKeys.get((blockKeys.size() - 1) / 2)),
697 Bytes.toStringBinary(reader.midkey()));
698
699 assertEquals(UNCOMPRESSED_INDEX_SIZES[testI],
700 reader.getTrailer().getUncompressedDataIndexSize());
701
702 reader.close();
703 reader2.close();
704 }
705 }
706
707 private void checkSeekTo(byte[][] keys, HFileScanner scanner, int i)
708 throws IOException {
709 assertEquals("Failed to seek to key #" + i + " (" + Bytes.toStringBinary(keys[i]) + ")", 0,
710 scanner.seekTo(KeyValue.createKeyValueFromKey(keys[i])));
711 }
712
713 private void assertArrayEqualsBuffer(String msgPrefix, byte[] arr,
714 ByteBuffer buf) {
715 assertEquals(msgPrefix + ": expected " + Bytes.toStringBinary(arr)
716 + ", actual " + Bytes.toStringBinary(buf), 0, Bytes.compareTo(arr, 0,
717 arr.length, buf.array(), buf.arrayOffset(), buf.limit()));
718 }
719
720
721 private void checkKeyValue(String msgPrefix, byte[] expectedKey,
722 byte[] expectedValue, ByteBuffer keyRead, ByteBuffer valueRead) {
723 if (!msgPrefix.isEmpty())
724 msgPrefix += ". ";
725
726 assertArrayEqualsBuffer(msgPrefix + "Invalid key", expectedKey, keyRead);
727 assertArrayEqualsBuffer(msgPrefix + "Invalid value", expectedValue,
728 valueRead);
729 }
730
731 @Test(timeout=10000)
732 public void testIntermediateLevelIndicesWithLargeKeys() throws IOException {
733 testIntermediateLevelIndicesWithLargeKeys(16);
734 }
735
736 @Test(timeout=10000)
737 public void testIntermediateLevelIndicesWithLargeKeysWithMinNumEntries() throws IOException {
738
739 testIntermediateLevelIndicesWithLargeKeys(2);
740 }
741
742 public void testIntermediateLevelIndicesWithLargeKeys(int minNumEntries) throws IOException {
743 Path hfPath = new Path(TEST_UTIL.getDataTestDir(),
744 "testIntermediateLevelIndicesWithLargeKeys.hfile");
745 int maxChunkSize = 1024;
746 FileSystem fs = FileSystem.get(conf);
747 CacheConfig cacheConf = new CacheConfig(conf);
748 conf.setInt(HFileBlockIndex.MAX_CHUNK_SIZE_KEY, maxChunkSize);
749 conf.setInt(HFileBlockIndex.MIN_INDEX_NUM_ENTRIES_KEY, minNumEntries);
750 HFileContext context = new HFileContextBuilder().withBlockSize(16).build();
751 HFileWriterV2 hfw =
752 (HFileWriterV2) new HFileWriterV2.WriterFactoryV2(conf, cacheConf)
753 .withFileContext(context)
754 .withPath(fs, hfPath).create();
755 List<byte[]> keys = new ArrayList<byte[]>();
756
757
758 for (int i=0; i < 100; i++) {
759 byte[] rowkey = new byte[maxChunkSize + 1];
760 byte[] b = Bytes.toBytes(i);
761 System.arraycopy(b, 0, rowkey, rowkey.length - b.length, b.length);
762 keys.add(rowkey);
763 hfw.append(CellUtil.createCell(rowkey));
764 }
765 hfw.close();
766
767 HFile.Reader reader = HFile.createReader(fs, hfPath, cacheConf, conf);
768
769 HFileScanner scanner = reader.getScanner(true, true);
770 for (int i = 0; i < keys.size(); ++i) {
771 scanner.seekTo(CellUtil.createCell(keys.get(i)));
772 }
773 reader.close();
774 }
775 }
776