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.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     // This test requires at least HFile format version 2.
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     // This test requires at least HFile format version 2.
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    * A wrapper around a block reader which only caches the results of the last
150    * operation. Not thread-safe.
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); // Ensure no one made this even.
325 
326     // We only add odd-index keys into the array that we will binary-search.
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     // Only odd-index elements of this array are used to keep the secondary
337     // index entries of the corresponding keys.
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       //KeyValue cell = new KeyValue.KeyOnlyKeyValue(k, 0, k.length);
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     // Make sure the keys are increasing.
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       // To make things a bit more interesting, store the key we are looking
399       // for at a non-zero offset in a new array.
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         // This key is in the array we search as the element (i - 1) / 2. Make
415         // sure we find it.
416         expectedResult = (i - 1) / 2;
417         referenceItem = i;
418       } else {
419         // This key is not in the array but between two elements on the array,
420         // in the beginning, or in the end. The result should be the previous
421         // key in the searched array, or -1 for i = 0.
422         expectedResult = i / 2 - 1;
423         referenceItem = i - 1;
424       }
425 
426       assertEquals(lookupFailureMsg, expectedResult, searchResult);
427 
428       // Now test we can get the offset and the on-disk-size using a
429       // higher-level API function.s
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     // Test the ability to look up the entry that contains a particular
473     // deeper-level index block's entry ("sub-entry"), assuming a global
474     // 0-based ordering of sub-entries. This is needed for mid-key calculation.
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   /** Checks if the HeapSize calculator is within reason */
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     // Since the arrays in BlockIndex(byte [][] blockKeys, long [] blockOffsets,
496     // int [] blockDataSizes) are all null they are not going to show up in the
497     // HeapSize calculation, so need to remove those array costs from expected.
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   * to check if looks good when midKey on a leaf index block boundary
508   * @throws IOException
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    // should open hfile.block.index.cacheonwrite
517    conf.setBoolean(CacheConfig.CACHE_INDEX_BLOCKS_ON_WRITE_KEY, true);
518 
519    CacheConfig cacheConf = new CacheConfig(conf);
520    BlockCache blockCache = cacheConf.getBlockCache();
521    // Evict all blocks that were cached-on-write by the previous invocation.
522    blockCache.evictBlocksByHfileName(hfilePath.getName());
523    // Write the HFile
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      // the new generated hfile will contain 2 leaf-index blocks and 16 data blocks,
540      // midkey is just on the boundary of the first leaf-index block
541      for (int i = 0; i < kvNumberToBeWritten; ++i) {
542        byte[] row = TestHFileWriterV2.randomOrderedFixedLengthKey(rand, i, 30);
543 
544        // Key will be interpreted by KeyValue.KEY_COMPARATOR
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    // close hfile.block.index.cacheonwrite
554    conf.setBoolean(CacheConfig.CACHE_INDEX_BLOCKS_ON_WRITE_KEY, false);
555 
556    // Read the HFile
557    HFile.Reader reader = HFile.createReader(fs, hfilePath, cacheConf, conf);
558 
559    boolean hasArrayIndexOutOfBoundsException = false;
560    try {
561      // get the mid-key.
562      reader.midkey();
563    } catch (ArrayIndexOutOfBoundsException e) {
564      hasArrayIndexOutOfBoundsException = true;
565    } finally {
566      reader.close();
567    }
568 
569    // to check if ArrayIndexOutOfBoundsException occured
570    assertFalse(hasArrayIndexOutOfBoundsException);
571  }
572 
573   /**
574    * Testing block index through the HFile writer/reader APIs. Allows to test
575    * setting index block size through configuration, intermediate-level index
576    * blocks, and caching index blocks on write.
577    *
578    * @throws IOException
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       // Evict all blocks that were cached-on-write by the previous invocation.
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       // Write the HFile
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           // Key will be interpreted by KeyValue.KEY_COMPARATOR
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       // Read the HFile
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       // Manually compute the mid-key and validate it.
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         // One int for the number of items, and n + 1 for the secondary index.
673         int entriesOffset = Bytes.SIZEOF_INT * (n + 2);
674 
675         // Get all the keys from the leaf index block. S
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           // If the first key of the block is not among the keys written, we
688           // are not parsing the non-root index block format correctly.
689           assertTrue("Invalid block key from leaf-level block: " + blockKeyStr,
690               keyStrSet.contains(blockKeyStr));
691         }
692       }
693 
694       // Validate the mid-key.
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   /** Check a key/value pair after it was read by the reader */
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     // because of the large rowKeys, we will end up with a 50-level block index without sanity check
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     // This should result in leaf-level indices and a root level index
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     // Scanner doesn't do Cells yet.  Fix.
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