View Javadoc

1   /*
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
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.encoding.DataBlockEncoding;
51  import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexChunk;
52  import org.apache.hadoop.hbase.io.hfile.HFileBlockIndex.BlockIndexReader;
53  import org.apache.hadoop.hbase.testclassification.MediumTests;
54  import org.apache.hadoop.hbase.util.Bytes;
55  import org.apache.hadoop.hbase.util.ClassSize;
56  import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
57  import org.junit.Before;
58  import org.junit.Test;
59  import org.junit.experimental.categories.Category;
60  import org.junit.runner.RunWith;
61  import org.junit.runners.Parameterized;
62  import org.junit.runners.Parameterized.Parameters;
63  
64  @RunWith(Parameterized.class)
65  @Category(MediumTests.class)
66  public class TestHFileBlockIndex {
67  
68    @Parameters
69    public static Collection<Object[]> compressionAlgorithms() {
70      return HBaseTestingUtility.COMPRESSION_ALGORITHMS_PARAMETERIZED;
71    }
72  
73    public TestHFileBlockIndex(Compression.Algorithm compr) {
74      this.compr = compr;
75    }
76  
77    private static final Log LOG = LogFactory.getLog(TestHFileBlockIndex.class);
78  
79    private static final int NUM_DATA_BLOCKS = 1000;
80    private static final HBaseTestingUtility TEST_UTIL =
81        new HBaseTestingUtility();
82  
83    private static final int SMALL_BLOCK_SIZE = 4096;
84    private static final int NUM_KV = 10000;
85  
86    private static FileSystem fs;
87    private Path path;
88    private Random rand;
89    private long rootIndexOffset;
90    private int numRootEntries;
91    private int numLevels;
92    private static final List<byte[]> keys = new ArrayList<byte[]>();
93    private final Compression.Algorithm compr;
94    private byte[] firstKeyInFile;
95    private Configuration conf;
96  
97    private static final int[] INDEX_CHUNK_SIZES = { 4096, 512, 384 };
98    private static final int[] EXPECTED_NUM_LEVELS = { 2, 3, 4 };
99    private static final int[] UNCOMPRESSED_INDEX_SIZES =
100       { 19187, 21813, 23086 };
101 
102   private static final boolean includesMemstoreTS = true;
103 
104   static {
105     assert INDEX_CHUNK_SIZES.length == EXPECTED_NUM_LEVELS.length;
106     assert INDEX_CHUNK_SIZES.length == UNCOMPRESSED_INDEX_SIZES.length;
107   }
108 
109   @Before
110   public void setUp() throws IOException {
111     keys.clear();
112     rand = new Random(2389757);
113     firstKeyInFile = null;
114     conf = TEST_UTIL.getConfiguration();
115 
116     // This test requires at least HFile format version 2.
117     conf.setInt(HFile.FORMAT_VERSION_KEY, HFile.MAX_FORMAT_VERSION);
118 
119     fs = HFileSystem.get(conf);
120   }
121 
122   @Test
123   public void testBlockIndex() throws IOException {
124     testBlockIndexInternals(false);
125     clear();
126     testBlockIndexInternals(true);
127   }
128 
129   private void clear() throws IOException {
130     keys.clear();
131     rand = new Random(2389757);
132     firstKeyInFile = null;
133     conf = TEST_UTIL.getConfiguration();
134 
135     // This test requires at least HFile format version 2.
136     conf.setInt(HFile.FORMAT_VERSION_KEY, 3);
137 
138     fs = HFileSystem.get(conf);
139   }
140 
141   private void testBlockIndexInternals(boolean useTags) throws IOException {
142     path = new Path(TEST_UTIL.getDataTestDir(), "block_index_" + compr + useTags);
143     writeWholeIndex(useTags);
144     readIndex(useTags);
145   }
146 
147   /**
148    * A wrapper around a block reader which only caches the results of the last
149    * operation. Not thread-safe.
150    */
151   private static class BlockReaderWrapper implements HFile.CachingBlockReader {
152 
153     private HFileBlock.FSReader realReader;
154     private long prevOffset;
155     private long prevOnDiskSize;
156     private boolean prevPread;
157     private HFileBlock prevBlock;
158 
159     public int hitCount = 0;
160     public int missCount = 0;
161 
162     public BlockReaderWrapper(HFileBlock.FSReader realReader) {
163       this.realReader = realReader;
164     }
165 
166     @Override
167     public HFileBlock readBlock(long offset, long onDiskSize,
168         boolean cacheBlock, boolean pread, boolean isCompaction,
169         boolean updateCacheMetrics, BlockType expectedBlockType,
170         DataBlockEncoding expectedDataBlockEncoding)
171         throws IOException {
172       if (offset == prevOffset && onDiskSize == prevOnDiskSize &&
173           pread == prevPread) {
174         hitCount += 1;
175         return prevBlock;
176       }
177 
178       missCount += 1;
179       prevBlock = realReader.readBlockData(offset, onDiskSize,
180           -1, pread);
181       prevOffset = offset;
182       prevOnDiskSize = onDiskSize;
183       prevPread = pread;
184 
185       return prevBlock;
186     }
187   }
188 
189   private void readIndex(boolean useTags) throws IOException {
190     long fileSize = fs.getFileStatus(path).getLen();
191     LOG.info("Size of " + path + ": " + fileSize);
192 
193     FSDataInputStream istream = fs.open(path);
194     HFileContext meta = new HFileContextBuilder()
195                         .withHBaseCheckSum(true)
196                         .withIncludesMvcc(includesMemstoreTS)
197                         .withIncludesTags(useTags)
198                         .withCompression(compr)
199                         .build();
200     HFileBlock.FSReader blockReader = new HFileBlock.FSReaderImpl(istream, fs.getFileStatus(path)
201         .getLen(), meta);
202 
203     BlockReaderWrapper brw = new BlockReaderWrapper(blockReader);
204     HFileBlockIndex.BlockIndexReader indexReader =
205         new HFileBlockIndex.BlockIndexReader(
206             KeyValue.RAW_COMPARATOR, numLevels, brw);
207 
208     indexReader.readRootIndex(blockReader.blockRange(rootIndexOffset,
209         fileSize).nextBlockWithBlockType(BlockType.ROOT_INDEX), numRootEntries);
210 
211     long prevOffset = -1;
212     int i = 0;
213     int expectedHitCount = 0;
214     int expectedMissCount = 0;
215     LOG.info("Total number of keys: " + keys.size());
216     for (byte[] key : keys) {
217       assertTrue(key != null);
218       assertTrue(indexReader != null);
219       HFileBlock b =
220           indexReader.seekToDataBlock(new KeyValue.KeyOnlyKeyValue(key, 0, key.length), null, true,
221             true, false, null);
222       if (KeyValue.COMPARATOR.compareFlatKey(key, firstKeyInFile) < 0) {
223         assertTrue(b == null);
224         ++i;
225         continue;
226       }
227 
228       String keyStr = "key #" + i + ", " + Bytes.toStringBinary(key);
229 
230       assertTrue("seekToDataBlock failed for " + keyStr, b != null);
231 
232       if (prevOffset == b.getOffset()) {
233         assertEquals(++expectedHitCount, brw.hitCount);
234       } else {
235         LOG.info("First key in a new block: " + keyStr + ", block offset: "
236             + b.getOffset() + ")");
237         assertTrue(b.getOffset() > prevOffset);
238         assertEquals(++expectedMissCount, brw.missCount);
239         prevOffset = b.getOffset();
240       }
241       ++i;
242     }
243 
244     istream.close();
245   }
246 
247   private void writeWholeIndex(boolean useTags) throws IOException {
248     assertEquals(0, keys.size());
249     HFileContext meta = new HFileContextBuilder()
250                         .withHBaseCheckSum(true)
251                         .withIncludesMvcc(includesMemstoreTS)
252                         .withIncludesTags(useTags)
253                         .withCompression(compr)
254                         .withBytesPerCheckSum(HFile.DEFAULT_BYTES_PER_CHECKSUM)
255                         .build();
256     HFileBlock.Writer hbw = new HFileBlock.Writer(null,
257         meta);
258     FSDataOutputStream outputStream = fs.create(path);
259     HFileBlockIndex.BlockIndexWriter biw =
260         new HFileBlockIndex.BlockIndexWriter(hbw, null, null);
261 
262     for (int i = 0; i < NUM_DATA_BLOCKS; ++i) {
263       hbw.startWriting(BlockType.DATA).write(String.valueOf(rand.nextInt(1000)).getBytes());
264       long blockOffset = outputStream.getPos();
265       hbw.writeHeaderAndData(outputStream);
266 
267       byte[] firstKey = null;
268       byte[] family = Bytes.toBytes("f");
269       byte[] qualifier = Bytes.toBytes("q");
270       for (int j = 0; j < 16; ++j) {
271         byte[] k =
272             new KeyValue(TestHFileWriterV2.randomOrderedKey(rand, i * 16 + j), family, qualifier,
273                 EnvironmentEdgeManager.currentTime(), KeyValue.Type.Put).getKey();
274         keys.add(k);
275         if (j == 8) {
276           firstKey = k;
277         }
278       }
279       assertTrue(firstKey != null);
280       if (firstKeyInFile == null) {
281         firstKeyInFile = firstKey;
282       }
283       biw.addEntry(firstKey, blockOffset, hbw.getOnDiskSizeWithHeader());
284 
285       writeInlineBlocks(hbw, outputStream, biw, false);
286     }
287     writeInlineBlocks(hbw, outputStream, biw, true);
288     rootIndexOffset = biw.writeIndexBlocks(outputStream);
289     outputStream.close();
290 
291     numLevels = biw.getNumLevels();
292     numRootEntries = biw.getNumRootEntries();
293 
294     LOG.info("Index written: numLevels=" + numLevels + ", numRootEntries=" +
295         numRootEntries + ", rootIndexOffset=" + rootIndexOffset);
296   }
297 
298   private void writeInlineBlocks(HFileBlock.Writer hbw,
299       FSDataOutputStream outputStream, HFileBlockIndex.BlockIndexWriter biw,
300       boolean isClosing) throws IOException {
301     while (biw.shouldWriteBlock(isClosing)) {
302       long offset = outputStream.getPos();
303       biw.writeInlineBlock(hbw.startWriting(biw.getInlineBlockType()));
304       hbw.writeHeaderAndData(outputStream);
305       biw.blockWritten(offset, hbw.getOnDiskSizeWithHeader(),
306           hbw.getUncompressedSizeWithoutHeader());
307       LOG.info("Wrote an inline index block at " + offset + ", size " +
308           hbw.getOnDiskSizeWithHeader());
309     }
310   }
311 
312   private static final long getDummyFileOffset(int i) {
313     return i * 185 + 379;
314   }
315 
316   private static final int getDummyOnDiskSize(int i) {
317     return i * i * 37 + i * 19 + 13;
318   }
319 
320   @Test
321   public void testSecondaryIndexBinarySearch() throws IOException {
322     int numTotalKeys = 99;
323     assertTrue(numTotalKeys % 2 == 1); // Ensure no one made this even.
324 
325     // We only add odd-index keys into the array that we will binary-search.
326     int numSearchedKeys = (numTotalKeys - 1) / 2;
327 
328     ByteArrayOutputStream baos = new ByteArrayOutputStream();
329     DataOutputStream dos = new DataOutputStream(baos);
330 
331     dos.writeInt(numSearchedKeys);
332     int curAllEntriesSize = 0;
333     int numEntriesAdded = 0;
334 
335     // Only odd-index elements of this array are used to keep the secondary
336     // index entries of the corresponding keys.
337     int secondaryIndexEntries[] = new int[numTotalKeys];
338 
339     for (int i = 0; i < numTotalKeys; ++i) {
340       byte[] k = TestHFileWriterV2.randomOrderedKey(rand, i * 2);
341       KeyValue cell = new KeyValue(k, Bytes.toBytes("f"), Bytes.toBytes("q"), 
342           Bytes.toBytes("val"));
343       //KeyValue cell = new KeyValue.KeyOnlyKeyValue(k, 0, k.length);
344       keys.add(cell.getKey());
345       String msgPrefix = "Key #" + i + " (" + Bytes.toStringBinary(k) + "): ";
346       StringBuilder padding = new StringBuilder();
347       while (msgPrefix.length() + padding.length() < 70)
348         padding.append(' ');
349       msgPrefix += padding;
350       if (i % 2 == 1) {
351         dos.writeInt(curAllEntriesSize);
352         secondaryIndexEntries[i] = curAllEntriesSize;
353         LOG.info(msgPrefix + "secondary index entry #" + ((i - 1) / 2) +
354             ", offset " + curAllEntriesSize);
355         curAllEntriesSize += cell.getKey().length
356             + HFileBlockIndex.SECONDARY_INDEX_ENTRY_OVERHEAD;
357         ++numEntriesAdded;
358       } else {
359         secondaryIndexEntries[i] = -1;
360         LOG.info(msgPrefix + "not in the searched array");
361       }
362     }
363 
364     // Make sure the keys are increasing.
365     for (int i = 0; i < keys.size() - 1; ++i)
366       assertTrue(KeyValue.COMPARATOR.compare(
367           new KeyValue.KeyOnlyKeyValue(keys.get(i), 0, keys.get(i).length),
368           new KeyValue.KeyOnlyKeyValue(keys.get(i + 1), 0, keys.get(i + 1).length)) < 0);
369 
370     dos.writeInt(curAllEntriesSize);
371     assertEquals(numSearchedKeys, numEntriesAdded);
372     int secondaryIndexOffset = dos.size();
373     assertEquals(Bytes.SIZEOF_INT * (numSearchedKeys + 2),
374         secondaryIndexOffset);
375 
376     for (int i = 1; i <= numTotalKeys - 1; i += 2) {
377       assertEquals(dos.size(),
378           secondaryIndexOffset + secondaryIndexEntries[i]);
379       long dummyFileOffset = getDummyFileOffset(i);
380       int dummyOnDiskSize = getDummyOnDiskSize(i);
381       LOG.debug("Storing file offset=" + dummyFileOffset + " and onDiskSize=" +
382           dummyOnDiskSize + " at offset " + dos.size());
383       dos.writeLong(dummyFileOffset);
384       dos.writeInt(dummyOnDiskSize);
385       LOG.debug("Stored key " + ((i - 1) / 2) +" at offset " + dos.size());
386       dos.write(keys.get(i));
387     }
388 
389     dos.writeInt(curAllEntriesSize);
390 
391     ByteBuffer nonRootIndex = ByteBuffer.wrap(baos.toByteArray());
392     for (int i = 0; i < numTotalKeys; ++i) {
393       byte[] searchKey = keys.get(i);
394       byte[] arrayHoldingKey = new byte[searchKey.length +
395                                         searchKey.length / 2];
396 
397       // To make things a bit more interesting, store the key we are looking
398       // for at a non-zero offset in a new array.
399       System.arraycopy(searchKey, 0, arrayHoldingKey, searchKey.length / 2,
400             searchKey.length);
401 
402       KeyValue.KeyOnlyKeyValue cell = new KeyValue.KeyOnlyKeyValue(
403           arrayHoldingKey, searchKey.length / 2, searchKey.length);
404       int searchResult = BlockIndexReader.binarySearchNonRootIndex(cell,
405           nonRootIndex, KeyValue.COMPARATOR);
406       String lookupFailureMsg = "Failed to look up key #" + i + " ("
407           + Bytes.toStringBinary(searchKey) + ")";
408 
409       int expectedResult;
410       int referenceItem;
411 
412       if (i % 2 == 1) {
413         // This key is in the array we search as the element (i - 1) / 2. Make
414         // sure we find it.
415         expectedResult = (i - 1) / 2;
416         referenceItem = i;
417       } else {
418         // This key is not in the array but between two elements on the array,
419         // in the beginning, or in the end. The result should be the previous
420         // key in the searched array, or -1 for i = 0.
421         expectedResult = i / 2 - 1;
422         referenceItem = i - 1;
423       }
424 
425       assertEquals(lookupFailureMsg, expectedResult, searchResult);
426 
427       // Now test we can get the offset and the on-disk-size using a
428       // higher-level API function.s
429       boolean locateBlockResult =
430           (BlockIndexReader.locateNonRootIndexEntry(nonRootIndex, cell,
431           KeyValue.COMPARATOR) != -1);
432 
433       if (i == 0) {
434         assertFalse(locateBlockResult);
435       } else {
436         assertTrue(locateBlockResult);
437         String errorMsg = "i=" + i + ", position=" + nonRootIndex.position();
438         assertEquals(errorMsg, getDummyFileOffset(referenceItem),
439             nonRootIndex.getLong());
440         assertEquals(errorMsg, getDummyOnDiskSize(referenceItem),
441             nonRootIndex.getInt());
442       }
443     }
444 
445   }
446 
447   @Test
448   public void testBlockIndexChunk() throws IOException {
449     BlockIndexChunk c = new BlockIndexChunk();
450     ByteArrayOutputStream baos = new ByteArrayOutputStream();
451     int N = 1000;
452     int[] numSubEntriesAt = new int[N];
453     int numSubEntries = 0;
454     for (int i = 0; i < N; ++i) {
455       baos.reset();
456       DataOutputStream dos = new DataOutputStream(baos);
457       c.writeNonRoot(dos);
458       assertEquals(c.getNonRootSize(), dos.size());
459 
460       baos.reset();
461       dos = new DataOutputStream(baos);
462       c.writeRoot(dos);
463       assertEquals(c.getRootSize(), dos.size());
464 
465       byte[] k = TestHFileWriterV2.randomOrderedKey(rand, i);
466       numSubEntries += rand.nextInt(5) + 1;
467       keys.add(k);
468       c.add(k, getDummyFileOffset(i), getDummyOnDiskSize(i), numSubEntries);
469     }
470 
471     // Test the ability to look up the entry that contains a particular
472     // deeper-level index block's entry ("sub-entry"), assuming a global
473     // 0-based ordering of sub-entries. This is needed for mid-key calculation.
474     for (int i = 0; i < N; ++i) {
475       for (int j = i == 0 ? 0 : numSubEntriesAt[i - 1];
476            j < numSubEntriesAt[i];
477            ++j) {
478         assertEquals(i, c.getEntryBySubEntry(j));
479       }
480     }
481   }
482 
483   /** Checks if the HeapSize calculator is within reason */
484   @Test
485   public void testHeapSizeForBlockIndex() throws IOException {
486     Class<HFileBlockIndex.BlockIndexReader> cl =
487         HFileBlockIndex.BlockIndexReader.class;
488     long expected = ClassSize.estimateBase(cl, false);
489 
490     HFileBlockIndex.BlockIndexReader bi =
491         new HFileBlockIndex.BlockIndexReader(KeyValue.RAW_COMPARATOR, 1);
492     long actual = bi.heapSize();
493 
494     // Since the arrays in BlockIndex(byte [][] blockKeys, long [] blockOffsets,
495     // int [] blockDataSizes) are all null they are not going to show up in the
496     // HeapSize calculation, so need to remove those array costs from expected.
497     expected -= ClassSize.align(3 * ClassSize.ARRAY);
498 
499     if (expected != actual) {
500       ClassSize.estimateBase(cl, true);
501       assertEquals(expected, actual);
502     }
503   }
504 
505   /**
506    * Testing block index through the HFile writer/reader APIs. Allows to test
507    * setting index block size through configuration, intermediate-level index
508    * blocks, and caching index blocks on write.
509    *
510    * @throws IOException
511    */
512   @Test
513   public void testHFileWriterAndReader() throws IOException {
514     Path hfilePath = new Path(TEST_UTIL.getDataTestDir(),
515         "hfile_for_block_index");
516     CacheConfig cacheConf = new CacheConfig(conf);
517     BlockCache blockCache = cacheConf.getBlockCache();
518 
519     for (int testI = 0; testI < INDEX_CHUNK_SIZES.length; ++testI) {
520       int indexBlockSize = INDEX_CHUNK_SIZES[testI];
521       int expectedNumLevels = EXPECTED_NUM_LEVELS[testI];
522       LOG.info("Index block size: " + indexBlockSize + ", compression: "
523           + compr);
524       // Evict all blocks that were cached-on-write by the previous invocation.
525       blockCache.evictBlocksByHfileName(hfilePath.getName());
526 
527       conf.setInt(HFileBlockIndex.MAX_CHUNK_SIZE_KEY, indexBlockSize);
528       Set<String> keyStrSet = new HashSet<String>();
529       byte[][] keys = new byte[NUM_KV][];
530       byte[][] values = new byte[NUM_KV][];
531 
532       // Write the HFile
533       {
534         HFileContext meta = new HFileContextBuilder()
535                             .withBlockSize(SMALL_BLOCK_SIZE)
536                             .withCompression(compr)
537                             .build();
538         HFile.Writer writer =
539             HFile.getWriterFactory(conf, cacheConf)
540                 .withPath(fs, hfilePath)
541                 .withFileContext(meta)
542                 .create();
543         Random rand = new Random(19231737);
544         byte[] family = Bytes.toBytes("f");
545         byte[] qualifier = Bytes.toBytes("q");
546         for (int i = 0; i < NUM_KV; ++i) {
547           byte[] row = TestHFileWriterV2.randomOrderedKey(rand, i);
548 
549           // Key will be interpreted by KeyValue.KEY_COMPARATOR
550           KeyValue kv =
551               new KeyValue(row, family, qualifier, EnvironmentEdgeManager.currentTime(),
552                   TestHFileWriterV2.randomValue(rand));
553           byte[] k = kv.getKey();
554           writer.append(kv);
555           keys[i] = k;
556           values[i] = CellUtil.cloneValue(kv);
557           keyStrSet.add(Bytes.toStringBinary(k));
558           if (i > 0) {
559             assertTrue(KeyValue.COMPARATOR.compareFlatKey(keys[i - 1],
560                 keys[i]) < 0);
561           }
562         }
563 
564         writer.close();
565       }
566 
567       // Read the HFile
568       HFile.Reader reader = HFile.createReader(fs, hfilePath, cacheConf, conf);
569       assertEquals(expectedNumLevels,
570           reader.getTrailer().getNumDataIndexLevels());
571 
572       assertTrue(Bytes.equals(keys[0], reader.getFirstKey()));
573       assertTrue(Bytes.equals(keys[NUM_KV - 1], reader.getLastKey()));
574       LOG.info("Last key: " + Bytes.toStringBinary(keys[NUM_KV - 1]));
575 
576       for (boolean pread : new boolean[] { false, true }) {
577         HFileScanner scanner = reader.getScanner(true, pread);
578         for (int i = 0; i < NUM_KV; ++i) {
579           checkSeekTo(keys, scanner, i);
580           checkKeyValue("i=" + i, keys[i], values[i], scanner.getKey(),
581               scanner.getValue());
582         }
583         assertTrue(scanner.seekTo());
584         for (int i = NUM_KV - 1; i >= 0; --i) {
585           checkSeekTo(keys, scanner, i);
586           checkKeyValue("i=" + i, keys[i], values[i], scanner.getKey(),
587               scanner.getValue());
588         }
589       }
590 
591       // Manually compute the mid-key and validate it.
592       HFileReaderV2 reader2 = (HFileReaderV2) reader;
593       HFileBlock.FSReader fsReader = reader2.getUncachedBlockReader();
594 
595       HFileBlock.BlockIterator iter = fsReader.blockRange(0,
596           reader.getTrailer().getLoadOnOpenDataOffset());
597       HFileBlock block;
598       List<byte[]> blockKeys = new ArrayList<byte[]>();
599       while ((block = iter.nextBlock()) != null) {
600         if (block.getBlockType() != BlockType.LEAF_INDEX)
601           return;
602         ByteBuffer b = block.getBufferReadOnly();
603         int n = b.getInt();
604         // One int for the number of items, and n + 1 for the secondary index.
605         int entriesOffset = Bytes.SIZEOF_INT * (n + 2);
606 
607         // Get all the keys from the leaf index block. S
608         for (int i = 0; i < n; ++i) {
609           int keyRelOffset = b.getInt(Bytes.SIZEOF_INT * (i + 1));
610           int nextKeyRelOffset = b.getInt(Bytes.SIZEOF_INT * (i + 2));
611           int keyLen = nextKeyRelOffset - keyRelOffset;
612           int keyOffset = b.arrayOffset() + entriesOffset + keyRelOffset +
613               HFileBlockIndex.SECONDARY_INDEX_ENTRY_OVERHEAD;
614           byte[] blockKey = Arrays.copyOfRange(b.array(), keyOffset, keyOffset
615               + keyLen);
616           String blockKeyStr = Bytes.toString(blockKey);
617           blockKeys.add(blockKey);
618 
619           // If the first key of the block is not among the keys written, we
620           // are not parsing the non-root index block format correctly.
621           assertTrue("Invalid block key from leaf-level block: " + blockKeyStr,
622               keyStrSet.contains(blockKeyStr));
623         }
624       }
625 
626       // Validate the mid-key.
627       assertEquals(
628           Bytes.toStringBinary(blockKeys.get((blockKeys.size() - 1) / 2)),
629           Bytes.toStringBinary(reader.midkey()));
630 
631       assertEquals(UNCOMPRESSED_INDEX_SIZES[testI],
632           reader.getTrailer().getUncompressedDataIndexSize());
633 
634       reader.close();
635       reader2.close();
636     }
637   }
638 
639   private void checkSeekTo(byte[][] keys, HFileScanner scanner, int i)
640       throws IOException {
641     assertEquals("Failed to seek to key #" + i + " (" + Bytes.toStringBinary(keys[i]) + ")", 0,
642         scanner.seekTo(KeyValue.createKeyValueFromKey(keys[i])));
643   }
644 
645   private void assertArrayEqualsBuffer(String msgPrefix, byte[] arr,
646       ByteBuffer buf) {
647     assertEquals(msgPrefix + ": expected " + Bytes.toStringBinary(arr)
648         + ", actual " + Bytes.toStringBinary(buf), 0, Bytes.compareTo(arr, 0,
649         arr.length, buf.array(), buf.arrayOffset(), buf.limit()));
650   }
651 
652   /** Check a key/value pair after it was read by the reader */
653   private void checkKeyValue(String msgPrefix, byte[] expectedKey,
654       byte[] expectedValue, ByteBuffer keyRead, ByteBuffer valueRead) {
655     if (!msgPrefix.isEmpty())
656       msgPrefix += ". ";
657 
658     assertArrayEqualsBuffer(msgPrefix + "Invalid key", expectedKey, keyRead);
659     assertArrayEqualsBuffer(msgPrefix + "Invalid value", expectedValue,
660         valueRead);
661   }
662 
663 
664 }
665