001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.io.hfile;
019
020import java.io.ByteArrayOutputStream;
021import java.io.DataInput;
022import java.io.DataInputStream;
023import java.io.DataOutput;
024import java.io.DataOutputStream;
025import java.io.IOException;
026import java.nio.ByteBuffer;
027import java.util.ArrayList;
028import java.util.Collections;
029import java.util.List;
030import java.util.concurrent.atomic.AtomicReference;
031import org.apache.hadoop.conf.Configuration;
032import org.apache.hadoop.fs.FSDataOutputStream;
033import org.apache.hadoop.hbase.ByteBufferKeyOnlyKeyValue;
034import org.apache.hadoop.hbase.Cell;
035import org.apache.hadoop.hbase.CellComparator;
036import org.apache.hadoop.hbase.CellUtil;
037import org.apache.hadoop.hbase.KeyValue;
038import org.apache.hadoop.hbase.KeyValue.KeyOnlyKeyValue;
039import org.apache.hadoop.hbase.PrivateCellUtil;
040import org.apache.hadoop.hbase.io.HeapSize;
041import org.apache.hadoop.hbase.io.encoding.DataBlockEncoding;
042import org.apache.hadoop.hbase.io.hfile.HFile.CachingBlockReader;
043import org.apache.hadoop.hbase.nio.ByteBuff;
044import org.apache.hadoop.hbase.regionserver.KeyValueScanner;
045import org.apache.hadoop.hbase.util.Bytes;
046import org.apache.hadoop.hbase.util.ClassSize;
047import org.apache.hadoop.hbase.util.ObjectIntPair;
048import org.apache.hadoop.io.WritableUtils;
049import org.apache.hadoop.util.StringUtils;
050import org.apache.yetus.audience.InterfaceAudience;
051import org.slf4j.Logger;
052import org.slf4j.LoggerFactory;
053
054/**
055 * Provides functionality to write ({@link BlockIndexWriter}) and read BlockIndexReader single-level
056 * and multi-level block indexes. Examples of how to use the block index writer can be found in
057 * {@link org.apache.hadoop.hbase.io.hfile.CompoundBloomFilterWriter} and {@link HFileWriterImpl}.
058 * Examples of how to use the reader can be found in {@link HFileReaderImpl} and
059 * org.apache.hadoop.hbase.io.hfile.TestHFileBlockIndex.
060 */
061@InterfaceAudience.Private
062public class HFileBlockIndex {
063
064  private static final Logger LOG = LoggerFactory.getLogger(HFileBlockIndex.class);
065
066  static final int DEFAULT_MAX_CHUNK_SIZE = 128 * 1024;
067
068  /**
069   * The maximum size guideline for index blocks (both leaf, intermediate, and root). If not
070   * specified, <code>DEFAULT_MAX_CHUNK_SIZE</code> is used.
071   */
072  public static final String MAX_CHUNK_SIZE_KEY = "hfile.index.block.max.size";
073
074  /**
075   * Minimum number of entries in a single index block. Even if we are above the
076   * hfile.index.block.max.size we will keep writing to the same block unless we have that many
077   * entries. We should have at least a few entries so that we don't have too many levels in the
078   * multi-level index. This should be at least 2 to make sure there is no infinite recursion.
079   */
080  public static final String MIN_INDEX_NUM_ENTRIES_KEY = "hfile.index.block.min.entries";
081
082  static final int DEFAULT_MIN_INDEX_NUM_ENTRIES = 16;
083
084  /**
085   * The number of bytes stored in each "secondary index" entry in addition to key bytes in the
086   * non-root index block format. The first long is the file offset of the deeper-level block the
087   * entry points to, and the int that follows is that block's on-disk size without including
088   * header.
089   */
090  static final int SECONDARY_INDEX_ENTRY_OVERHEAD = Bytes.SIZEOF_INT + Bytes.SIZEOF_LONG;
091
092  /**
093   * Error message when trying to use inline block API in single-level mode.
094   */
095  private static final String INLINE_BLOCKS_NOT_ALLOWED =
096    "Inline blocks are not allowed in the single-level-only mode";
097
098  /**
099   * The size of a meta-data record used for finding the mid-key in a multi-level index. Consists of
100   * the middle leaf-level index block offset (long), its on-disk size without header included
101   * (int), and the mid-key entry's zero-based index in that leaf index block.
102   */
103  private static final int MID_KEY_METADATA_SIZE = Bytes.SIZEOF_LONG + 2 * Bytes.SIZEOF_INT;
104
105  /**
106   * An implementation of the BlockIndexReader that deals with block keys which are plain byte[]
107   * like MetaBlock or the Bloom Block for ROW bloom. Does not need a comparator. It can work on
108   * Bytes.BYTES_RAWCOMPARATOR
109   */
110  static class ByteArrayKeyBlockIndexReader extends BlockIndexReader {
111
112    private byte[][] blockKeys;
113
114    public ByteArrayKeyBlockIndexReader(final int treeLevel) {
115      // Can be null for METAINDEX block
116      searchTreeLevel = treeLevel;
117    }
118
119    @Override
120    protected long calculateHeapSizeForBlockKeys(long heapSize) {
121      // Calculating the size of blockKeys
122      if (blockKeys != null) {
123        heapSize += ClassSize.REFERENCE;
124        // Adding array + references overhead
125        heapSize += ClassSize.align(ClassSize.ARRAY + blockKeys.length * ClassSize.REFERENCE);
126
127        // Adding bytes
128        for (byte[] key : blockKeys) {
129          heapSize += ClassSize.align(ClassSize.ARRAY + key.length);
130        }
131      }
132      return heapSize;
133    }
134
135    @Override
136    public boolean isEmpty() {
137      return blockKeys.length == 0;
138    }
139
140    /**
141     * n * from 0 to {@link #getRootBlockCount() - 1}
142     */
143    public byte[] getRootBlockKey(int i) {
144      return blockKeys[i];
145    }
146
147    @Override
148    public BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock,
149      boolean cacheBlocks, boolean pread, boolean isCompaction,
150      DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)
151      throws IOException {
152      // this would not be needed
153      return null;
154    }
155
156    @Override
157    public Cell midkey(CachingBlockReader cachingBlockReader) throws IOException {
158      // Not needed here
159      return null;
160    }
161
162    @Override
163    protected void initialize(int numEntries) {
164      blockKeys = new byte[numEntries][];
165    }
166
167    @Override
168    protected void add(final byte[] key, final long offset, final int dataSize) {
169      blockOffsets[rootCount] = offset;
170      blockKeys[rootCount] = key;
171      blockDataSizes[rootCount] = dataSize;
172      rootCount++;
173    }
174
175    @Override
176    public int rootBlockContainingKey(byte[] key, int offset, int length, CellComparator comp) {
177      int pos = Bytes.binarySearch(blockKeys, key, offset, length);
178      // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see
179      // binarySearch's javadoc.
180
181      if (pos >= 0) {
182        // This means this is an exact match with an element of blockKeys.
183        assert pos < blockKeys.length;
184        return pos;
185      }
186
187      // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i],
188      // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that
189      // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if
190      // key < blockKeys[0], meaning the file does not contain the given key.
191
192      int i = -pos - 1;
193      assert 0 <= i && i <= blockKeys.length;
194      return i - 1;
195    }
196
197    @Override
198    public int rootBlockContainingKey(Cell key) {
199      // Should not be called on this because here it deals only with byte[]
200      throw new UnsupportedOperationException(
201        "Cannot search for a key that is of Cell type. Only plain byte array keys "
202          + "can be searched for");
203    }
204
205    @Override
206    public String toString() {
207      StringBuilder sb = new StringBuilder();
208      sb.append("size=" + rootCount).append("\n");
209      for (int i = 0; i < rootCount; i++) {
210        sb.append("key=").append(KeyValue.keyToString(blockKeys[i])).append("\n  offset=")
211          .append(blockOffsets[i]).append(", dataSize=" + blockDataSizes[i]).append("\n");
212      }
213      return sb.toString();
214    }
215  }
216
217  /**
218   * An implementation of the BlockIndexReader that deals with block keys which are the key part of
219   * a cell like the Data block index or the ROW_COL bloom blocks This needs a comparator to work
220   * with the Cells
221   */
222  static class CellBasedKeyBlockIndexReader extends BlockIndexReader {
223
224    private Cell[] blockKeys;
225    /** Pre-computed mid-key */
226    private AtomicReference<Cell> midKey = new AtomicReference<>();
227    /** Needed doing lookup on blocks. */
228    private CellComparator comparator;
229
230    public CellBasedKeyBlockIndexReader(final CellComparator c, final int treeLevel) {
231      // Can be null for METAINDEX block
232      comparator = c;
233      searchTreeLevel = treeLevel;
234    }
235
236    @Override
237    protected long calculateHeapSizeForBlockKeys(long heapSize) {
238      if (blockKeys != null) {
239        heapSize += ClassSize.REFERENCE;
240        // Adding array + references overhead
241        heapSize += ClassSize.align(ClassSize.ARRAY + blockKeys.length * ClassSize.REFERENCE);
242
243        // Adding blockKeys
244        for (Cell key : blockKeys) {
245          heapSize += ClassSize.align(key.heapSize());
246        }
247      }
248      // Add comparator and the midkey atomicreference
249      heapSize += 2 * ClassSize.REFERENCE;
250      return heapSize;
251    }
252
253    @Override
254    public boolean isEmpty() {
255      return blockKeys.length == 0;
256    }
257
258    /**
259     * n * from 0 to {@link #getRootBlockCount() - 1}
260     */
261    public Cell getRootBlockKey(int i) {
262      return blockKeys[i];
263    }
264
265    @Override
266    public BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock,
267      boolean cacheBlocks, boolean pread, boolean isCompaction,
268      DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)
269      throws IOException {
270      int rootLevelIndex = rootBlockContainingKey(key);
271      if (rootLevelIndex < 0 || rootLevelIndex >= blockOffsets.length) {
272        return null;
273      }
274
275      // the next indexed key
276      Cell nextIndexedKey = null;
277
278      // Read the next-level (intermediate or leaf) index block.
279      long currentOffset = blockOffsets[rootLevelIndex];
280      int currentOnDiskSize = blockDataSizes[rootLevelIndex];
281
282      if (rootLevelIndex < blockKeys.length - 1) {
283        nextIndexedKey = blockKeys[rootLevelIndex + 1];
284      } else {
285        nextIndexedKey = KeyValueScanner.NO_NEXT_INDEXED_KEY;
286      }
287
288      int lookupLevel = 1; // How many levels deep we are in our lookup.
289      int index = -1;
290
291      HFileBlock block = null;
292      KeyOnlyKeyValue tmpNextIndexKV = new KeyValue.KeyOnlyKeyValue();
293      while (true) {
294        try {
295          // Must initialize it with null here, because if don't and once an exception happen in
296          // readBlock, then we'll release the previous assigned block twice in the finally block.
297          // (See HBASE-22422)
298          block = null;
299          if (currentBlock != null && currentBlock.getOffset() == currentOffset) {
300            // Avoid reading the same block again, even with caching turned off.
301            // This is crucial for compaction-type workload which might have
302            // caching turned off. This is like a one-block cache inside the
303            // scanner.
304            block = currentBlock;
305          } else {
306            // Call HFile's caching block reader API. We always cache index
307            // blocks, otherwise we might get terrible performance.
308            boolean shouldCache = cacheBlocks || (lookupLevel < searchTreeLevel);
309            BlockType expectedBlockType;
310            if (lookupLevel < searchTreeLevel - 1) {
311              expectedBlockType = BlockType.INTERMEDIATE_INDEX;
312            } else if (lookupLevel == searchTreeLevel - 1) {
313              expectedBlockType = BlockType.LEAF_INDEX;
314            } else {
315              // this also accounts for ENCODED_DATA
316              expectedBlockType = BlockType.DATA;
317            }
318            block = cachingBlockReader.readBlock(currentOffset, currentOnDiskSize, shouldCache,
319              pread, isCompaction, true, expectedBlockType, expectedDataBlockEncoding);
320          }
321
322          if (block == null) {
323            throw new IOException("Failed to read block at offset " + currentOffset
324              + ", onDiskSize=" + currentOnDiskSize);
325          }
326
327          // Found a data block, break the loop and check our level in the tree.
328          if (block.getBlockType().isData()) {
329            break;
330          }
331
332          // Not a data block. This must be a leaf-level or intermediate-level
333          // index block. We don't allow going deeper than searchTreeLevel.
334          if (++lookupLevel > searchTreeLevel) {
335            throw new IOException("Search Tree Level overflow: lookupLevel=" + lookupLevel
336              + ", searchTreeLevel=" + searchTreeLevel);
337          }
338
339          // Locate the entry corresponding to the given key in the non-root
340          // (leaf or intermediate-level) index block.
341          ByteBuff buffer = block.getBufferWithoutHeader();
342          index = locateNonRootIndexEntry(buffer, key, comparator);
343          if (index == -1) {
344            // This has to be changed
345            // For now change this to key value
346            throw new IOException("The key " + CellUtil.getCellKeyAsString(key) + " is before the"
347              + " first key of the non-root index block " + block);
348          }
349
350          currentOffset = buffer.getLong();
351          currentOnDiskSize = buffer.getInt();
352
353          // Only update next indexed key if there is a next indexed key in the current level
354          byte[] nonRootIndexedKey = getNonRootIndexedKey(buffer, index + 1);
355          if (nonRootIndexedKey != null) {
356            tmpNextIndexKV.setKey(nonRootIndexedKey, 0, nonRootIndexedKey.length);
357            nextIndexedKey = tmpNextIndexKV;
358          }
359        } finally {
360          if (block != null && !block.getBlockType().isData()) {
361            // Release the block immediately if it is not the data block
362            block.release();
363          }
364        }
365      }
366
367      if (lookupLevel != searchTreeLevel) {
368        assert block.getBlockType().isData();
369        // Though we have retrieved a data block we have found an issue
370        // in the retrieved data block. Hence returned the block so that
371        // the ref count can be decremented
372        if (block != null) {
373          block.release();
374        }
375        throw new IOException("Reached a data block at level " + lookupLevel
376          + " but the number of levels is " + searchTreeLevel);
377      }
378
379      // set the next indexed key for the current block.
380      return new BlockWithScanInfo(block, nextIndexedKey);
381    }
382
383    @Override
384    public Cell midkey(CachingBlockReader cachingBlockReader) throws IOException {
385      if (rootCount == 0) throw new IOException("HFile empty");
386
387      Cell targetMidKey = this.midKey.get();
388      if (targetMidKey != null) {
389        return targetMidKey;
390      }
391
392      if (midLeafBlockOffset >= 0) {
393        if (cachingBlockReader == null) {
394          throw new IOException(
395            "Have to read the middle leaf block but " + "no block reader available");
396        }
397
398        // Caching, using pread, assuming this is not a compaction.
399        HFileBlock midLeafBlock = cachingBlockReader.readBlock(midLeafBlockOffset,
400          midLeafBlockOnDiskSize, true, true, false, true, BlockType.LEAF_INDEX, null);
401        try {
402          ByteBuff b = midLeafBlock.getBufferWithoutHeader();
403          int numDataBlocks = b.getIntAfterPosition(0);
404          int keyRelOffset = b.getIntAfterPosition(Bytes.SIZEOF_INT * (midKeyEntry + 1));
405          int keyLen = b.getIntAfterPosition(Bytes.SIZEOF_INT * (midKeyEntry + 2)) - keyRelOffset
406            - SECONDARY_INDEX_ENTRY_OVERHEAD;
407          int keyOffset =
408            Bytes.SIZEOF_INT * (numDataBlocks + 2) + keyRelOffset + SECONDARY_INDEX_ENTRY_OVERHEAD;
409          byte[] bytes = b.toBytes(keyOffset, keyLen);
410          targetMidKey = new KeyValue.KeyOnlyKeyValue(bytes, 0, bytes.length);
411        } finally {
412          midLeafBlock.release();
413        }
414      } else {
415        // The middle of the root-level index.
416        targetMidKey = blockKeys[rootCount / 2];
417      }
418
419      this.midKey.set(targetMidKey);
420      return targetMidKey;
421    }
422
423    @Override
424    protected void initialize(int numEntries) {
425      blockKeys = new Cell[numEntries];
426    }
427
428    /**
429     * Adds a new entry in the root block index. Only used when reading.
430     * @param key      Last key in the block
431     * @param offset   file offset where the block is stored
432     * @param dataSize the uncompressed data size
433     */
434    @Override
435    protected void add(final byte[] key, final long offset, final int dataSize) {
436      blockOffsets[rootCount] = offset;
437      // Create the blockKeys as Cells once when the reader is opened
438      blockKeys[rootCount] = new KeyValue.KeyOnlyKeyValue(key, 0, key.length);
439      blockDataSizes[rootCount] = dataSize;
440      rootCount++;
441    }
442
443    @Override
444    public int rootBlockContainingKey(final byte[] key, int offset, int length,
445      CellComparator comp) {
446      // This should always be called with Cell not with a byte[] key
447      throw new UnsupportedOperationException("Cannot find for a key containing plain byte "
448        + "array. Only cell based keys can be searched for");
449    }
450
451    @Override
452    public int rootBlockContainingKey(Cell key) {
453      // Here the comparator should not be null as this happens for the root-level block
454      int pos = Bytes.binarySearch(blockKeys, key, comparator);
455      // pos is between -(blockKeys.length + 1) to blockKeys.length - 1, see
456      // binarySearch's javadoc.
457
458      if (pos >= 0) {
459        // This means this is an exact match with an element of blockKeys.
460        assert pos < blockKeys.length;
461        return pos;
462      }
463
464      // Otherwise, pos = -(i + 1), where blockKeys[i - 1] < key < blockKeys[i],
465      // and i is in [0, blockKeys.length]. We are returning j = i - 1 such that
466      // blockKeys[j] <= key < blockKeys[j + 1]. In particular, j = -1 if
467      // key < blockKeys[0], meaning the file does not contain the given key.
468
469      int i = -pos - 1;
470      assert 0 <= i && i <= blockKeys.length;
471      return i - 1;
472    }
473
474    @Override
475    public String toString() {
476      StringBuilder sb = new StringBuilder();
477      sb.append("size=" + rootCount).append("\n");
478      for (int i = 0; i < rootCount; i++) {
479        sb.append("key=").append((blockKeys[i])).append("\n  offset=").append(blockOffsets[i])
480          .append(", dataSize=" + blockDataSizes[i]).append("\n");
481      }
482      return sb.toString();
483    }
484  }
485
486  /**
487   * The reader will always hold the root level index in the memory. Index blocks at all other
488   * levels will be cached in the LRU cache in practice, although this API does not enforce that.
489   * <p>
490   * All non-root (leaf and intermediate) index blocks contain what we call a "secondary index": an
491   * array of offsets to the entries within the block. This allows us to do binary search for the
492   * entry corresponding to the given key without having to deserialize the block.
493   */
494  static abstract class BlockIndexReader implements HeapSize {
495
496    protected long[] blockOffsets;
497    protected int[] blockDataSizes;
498    protected int rootCount = 0;
499
500    // Mid-key metadata.
501    protected long midLeafBlockOffset = -1;
502    protected int midLeafBlockOnDiskSize = -1;
503    protected int midKeyEntry = -1;
504
505    /**
506     * The number of levels in the block index tree. One if there is only root level, two for root
507     * and leaf levels, etc.
508     */
509    protected int searchTreeLevel;
510
511    /**
512     * @return true if the block index is empty.
513     */
514    public abstract boolean isEmpty();
515
516    /**
517     * Verifies that the block index is non-empty and throws an {@link IllegalStateException}
518     * otherwise.
519     */
520    public void ensureNonEmpty() {
521      if (isEmpty()) {
522        throw new IllegalStateException("Block index is empty or not loaded");
523      }
524    }
525
526    /**
527     * Return the data block which contains this key. This function will only be called when the
528     * HFile version is larger than 1.
529     * @param key          the key we are looking for
530     * @param currentBlock the current block, to avoid re-reading the same block nnn * @param
531     *                     expectedDataBlockEncoding the data block encoding the caller is expecting
532     *                     the data block to be in, or null to not perform this check and return the
533     *                     block irrespective of the encoding
534     * @return reader a basic way to load blocks n
535     */
536    public HFileBlock seekToDataBlock(final Cell key, HFileBlock currentBlock, boolean cacheBlocks,
537      boolean pread, boolean isCompaction, DataBlockEncoding expectedDataBlockEncoding,
538      CachingBlockReader cachingBlockReader) throws IOException {
539      BlockWithScanInfo blockWithScanInfo = loadDataBlockWithScanInfo(key, currentBlock,
540        cacheBlocks, pread, isCompaction, expectedDataBlockEncoding, cachingBlockReader);
541      if (blockWithScanInfo == null) {
542        return null;
543      } else {
544        return blockWithScanInfo.getHFileBlock();
545      }
546    }
547
548    /**
549     * Return the BlockWithScanInfo, a data structure which contains the Data HFileBlock with other
550     * scan info such as the key that starts the next HFileBlock. This function will only be called
551     * when the HFile version is larger than 1.
552     * @param key                       the key we are looking for
553     * @param currentBlock              the current block, to avoid re-reading the same block
554     * @param expectedDataBlockEncoding the data block encoding the caller is expecting the data
555     *                                  block to be in, or null to not perform this check and return
556     *                                  the block irrespective of the encoding.
557     * @return the BlockWithScanInfo which contains the DataBlock with other scan info such as
558     *         nextIndexedKey. n
559     */
560    public abstract BlockWithScanInfo loadDataBlockWithScanInfo(Cell key, HFileBlock currentBlock,
561      boolean cacheBlocks, boolean pread, boolean isCompaction,
562      DataBlockEncoding expectedDataBlockEncoding, CachingBlockReader cachingBlockReader)
563      throws IOException;
564
565    /**
566     * An approximation to the {@link HFile}'s mid-key. Operates on block boundaries, and does not
567     * go inside blocks. In other words, returns the first key of the middle block of the file.
568     * @return the first key of the middle block
569     */
570    public abstract Cell midkey(CachingBlockReader cachingBlockReader) throws IOException;
571
572    /**
573     * @param i from 0 to {@link #getRootBlockCount() - 1}
574     */
575    public long getRootBlockOffset(int i) {
576      return blockOffsets[i];
577    }
578
579    /**
580     * @param i zero-based index of a root-level block
581     * @return the on-disk size of the root-level block for version 2, or the uncompressed size for
582     *         version 1
583     */
584    public int getRootBlockDataSize(int i) {
585      return blockDataSizes[i];
586    }
587
588    /**
589     * @return the number of root-level blocks in this block index
590     */
591    public int getRootBlockCount() {
592      return rootCount;
593    }
594
595    /**
596     * Finds the root-level index block containing the given key. n * Key to find n * the comparator
597     * to be used
598     * @return Offset of block containing <code>key</code> (between 0 and the number of blocks - 1)
599     *         or -1 if this file does not contain the request.
600     */
601    // When we want to find the meta index block or bloom block for ROW bloom
602    // type Bytes.BYTES_RAWCOMPARATOR would be enough. For the ROW_COL bloom case we need the
603    // CellComparator.
604    public abstract int rootBlockContainingKey(final byte[] key, int offset, int length,
605      CellComparator comp);
606
607    /**
608     * Finds the root-level index block containing the given key. n * Key to find
609     * @return Offset of block containing <code>key</code> (between 0 and the number of blocks - 1)
610     *         or -1 if this file does not contain the request.
611     */
612    // When we want to find the meta index block or bloom block for ROW bloom
613    // type
614    // Bytes.BYTES_RAWCOMPARATOR would be enough. For the ROW_COL bloom case we
615    // need the CellComparator.
616    public int rootBlockContainingKey(final byte[] key, int offset, int length) {
617      return rootBlockContainingKey(key, offset, length, null);
618    }
619
620    /**
621     * Finds the root-level index block containing the given key. n * Key to find
622     */
623    public abstract int rootBlockContainingKey(final Cell key);
624
625    /**
626     * The indexed key at the ith position in the nonRootIndex. The position starts at 0. n * @param
627     * i the ith position
628     * @return The indexed key at the ith position in the nonRootIndex.
629     */
630    protected byte[] getNonRootIndexedKey(ByteBuff nonRootIndex, int i) {
631      int numEntries = nonRootIndex.getInt(0);
632      if (i < 0 || i >= numEntries) {
633        return null;
634      }
635
636      // Entries start after the number of entries and the secondary index.
637      // The secondary index takes numEntries + 1 ints.
638      int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);
639      // Targetkey's offset relative to the end of secondary index
640      int targetKeyRelOffset = nonRootIndex.getInt(Bytes.SIZEOF_INT * (i + 1));
641
642      // The offset of the target key in the blockIndex buffer
643      int targetKeyOffset = entriesOffset // Skip secondary index
644        + targetKeyRelOffset // Skip all entries until mid
645        + SECONDARY_INDEX_ENTRY_OVERHEAD; // Skip offset and on-disk-size
646
647      // We subtract the two consecutive secondary index elements, which
648      // gives us the size of the whole (offset, onDiskSize, key) tuple. We
649      // then need to subtract the overhead of offset and onDiskSize.
650      int targetKeyLength = nonRootIndex.getInt(Bytes.SIZEOF_INT * (i + 2)) - targetKeyRelOffset
651        - SECONDARY_INDEX_ENTRY_OVERHEAD;
652
653      // TODO check whether we can make BB backed Cell here? So can avoid bytes copy.
654      return nonRootIndex.toBytes(targetKeyOffset, targetKeyLength);
655    }
656
657    /**
658     * Performs a binary search over a non-root level index block. Utilizes the secondary index,
659     * which records the offsets of (offset, onDiskSize, firstKey) tuples of all entries. n * the
660     * key we are searching for offsets to individual entries in the blockIndex buffer n * the
661     * non-root index block buffer, starting with the secondary index. The position is ignored.
662     * @return the index i in [0, numEntries - 1] such that keys[i] <= key < keys[i + 1], if keys is
663     *         the array of all keys being searched, or -1 otherwise n
664     */
665    static int binarySearchNonRootIndex(Cell key, ByteBuff nonRootIndex,
666      CellComparator comparator) {
667
668      int numEntries = nonRootIndex.getIntAfterPosition(0);
669      int low = 0;
670      int high = numEntries - 1;
671      int mid = 0;
672
673      // Entries start after the number of entries and the secondary index.
674      // The secondary index takes numEntries + 1 ints.
675      int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);
676
677      // If we imagine that keys[-1] = -Infinity and
678      // keys[numEntries] = Infinity, then we are maintaining an invariant that
679      // keys[low - 1] < key < keys[high + 1] while narrowing down the range.
680      ByteBufferKeyOnlyKeyValue nonRootIndexkeyOnlyKV = new ByteBufferKeyOnlyKeyValue();
681      ObjectIntPair<ByteBuffer> pair = new ObjectIntPair<>();
682      while (low <= high) {
683        mid = low + ((high - low) >> 1);
684
685        // Midkey's offset relative to the end of secondary index
686        int midKeyRelOffset = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 1));
687
688        // The offset of the middle key in the blockIndex buffer
689        int midKeyOffset = entriesOffset // Skip secondary index
690          + midKeyRelOffset // Skip all entries until mid
691          + SECONDARY_INDEX_ENTRY_OVERHEAD; // Skip offset and on-disk-size
692
693        // We subtract the two consecutive secondary index elements, which
694        // gives us the size of the whole (offset, onDiskSize, key) tuple. We
695        // then need to subtract the overhead of offset and onDiskSize.
696        int midLength = nonRootIndex.getIntAfterPosition(Bytes.SIZEOF_INT * (mid + 2))
697          - midKeyRelOffset - SECONDARY_INDEX_ENTRY_OVERHEAD;
698
699        // we have to compare in this order, because the comparator order
700        // has special logic when the 'left side' is a special key.
701        // TODO make KeyOnlyKeyValue to be Buffer backed and avoid array() call. This has to be
702        // done after HBASE-12224 & HBASE-12282
703        // TODO avoid array call.
704        nonRootIndex.asSubByteBuffer(midKeyOffset, midLength, pair);
705        nonRootIndexkeyOnlyKV.setKey(pair.getFirst(), pair.getSecond(), midLength);
706        int cmp = PrivateCellUtil.compareKeyIgnoresMvcc(comparator, key, nonRootIndexkeyOnlyKV);
707
708        // key lives above the midpoint
709        if (cmp > 0) low = mid + 1; // Maintain the invariant that keys[low - 1] < key
710        // key lives below the midpoint
711        else if (cmp < 0) high = mid - 1; // Maintain the invariant that key < keys[high + 1]
712        else return mid; // exact match
713      }
714
715      // As per our invariant, keys[low - 1] < key < keys[high + 1], meaning
716      // that low - 1 < high + 1 and (low - high) <= 1. As per the loop break
717      // condition, low >= high + 1. Therefore, low = high + 1.
718
719      if (low != high + 1) {
720        throw new IllegalStateException(
721          "Binary search broken: low=" + low + " " + "instead of " + (high + 1));
722      }
723
724      // OK, our invariant says that keys[low - 1] < key < keys[low]. We need to
725      // return i such that keys[i] <= key < keys[i + 1]. Therefore i = low - 1.
726      int i = low - 1;
727
728      // Some extra validation on the result.
729      if (i < -1 || i >= numEntries) {
730        throw new IllegalStateException("Binary search broken: result is " + i
731          + " but expected to be between -1 and (numEntries - 1) = " + (numEntries - 1));
732      }
733
734      return i;
735    }
736
737    /**
738     * Search for one key using the secondary index in a non-root block. In case of success,
739     * positions the provided buffer at the entry of interest, where the file offset and the
740     * on-disk-size can be read. n * a non-root block without header. Initial position does not
741     * matter. n * the byte array containing the key
742     * @return the index position where the given key was found, otherwise return -1 in the case the
743     *         given key is before the first key.
744     */
745    static int locateNonRootIndexEntry(ByteBuff nonRootBlock, Cell key, CellComparator comparator) {
746      int entryIndex = binarySearchNonRootIndex(key, nonRootBlock, comparator);
747
748      if (entryIndex != -1) {
749        int numEntries = nonRootBlock.getIntAfterPosition(0);
750
751        // The end of secondary index and the beginning of entries themselves.
752        int entriesOffset = Bytes.SIZEOF_INT * (numEntries + 2);
753
754        // The offset of the entry we are interested in relative to the end of
755        // the secondary index.
756        int entryRelOffset = nonRootBlock.getIntAfterPosition(Bytes.SIZEOF_INT * (1 + entryIndex));
757
758        nonRootBlock.position(entriesOffset + entryRelOffset);
759      }
760
761      return entryIndex;
762    }
763
764    /**
765     * Read in the root-level index from the given input stream. Must match what was written into
766     * the root level by {@link BlockIndexWriter#writeIndexBlocks(FSDataOutputStream)} at the offset
767     * that function returned.
768     * @param in         the buffered input stream or wrapped byte input stream
769     * @param numEntries the number of root-level index entries n
770     */
771    public void readRootIndex(DataInput in, final int numEntries) throws IOException {
772      blockOffsets = new long[numEntries];
773      initialize(numEntries);
774      blockDataSizes = new int[numEntries];
775
776      // If index size is zero, no index was written.
777      if (numEntries > 0) {
778        for (int i = 0; i < numEntries; ++i) {
779          long offset = in.readLong();
780          int dataSize = in.readInt();
781          byte[] key = Bytes.readByteArray(in);
782          add(key, offset, dataSize);
783        }
784      }
785    }
786
787    protected abstract void initialize(int numEntries);
788
789    protected abstract void add(final byte[] key, final long offset, final int dataSize);
790
791    /**
792     * Read in the root-level index from the given input stream. Must match what was written into
793     * the root level by {@link BlockIndexWriter#writeIndexBlocks(FSDataOutputStream)} at the offset
794     * that function returned.
795     * @param blk        the HFile block
796     * @param numEntries the number of root-level index entries
797     * @return the buffered input stream or wrapped byte input stream n
798     */
799    public DataInputStream readRootIndex(HFileBlock blk, final int numEntries) throws IOException {
800      DataInputStream in = blk.getByteStream();
801      readRootIndex(in, numEntries);
802      return in;
803    }
804
805    /**
806     * Read the root-level metadata of a multi-level block index. Based on
807     * {@link #readRootIndex(DataInput, int)}, but also reads metadata necessary to compute the
808     * mid-key in a multi-level index.
809     * @param blk        the HFile block
810     * @param numEntries the number of root-level index entries n
811     */
812    public void readMultiLevelIndexRoot(HFileBlock blk, final int numEntries) throws IOException {
813      DataInputStream in = readRootIndex(blk, numEntries);
814      // after reading the root index the checksum bytes have to
815      // be subtracted to know if the mid key exists.
816      int checkSumBytes = blk.totalChecksumBytes();
817      if ((in.available() - checkSumBytes) < MID_KEY_METADATA_SIZE) {
818        // No mid-key metadata available.
819        return;
820      }
821      midLeafBlockOffset = in.readLong();
822      midLeafBlockOnDiskSize = in.readInt();
823      midKeyEntry = in.readInt();
824    }
825
826    @Override
827    public long heapSize() {
828      // The BlockIndexReader does not have the blockKey, comparator and the midkey atomic reference
829      long heapSize =
830        ClassSize.align(3 * ClassSize.REFERENCE + 2 * Bytes.SIZEOF_INT + ClassSize.OBJECT);
831
832      // Mid-key metadata.
833      heapSize += MID_KEY_METADATA_SIZE;
834
835      heapSize = calculateHeapSizeForBlockKeys(heapSize);
836
837      if (blockOffsets != null) {
838        heapSize += ClassSize.align(ClassSize.ARRAY + blockOffsets.length * Bytes.SIZEOF_LONG);
839      }
840
841      if (blockDataSizes != null) {
842        heapSize += ClassSize.align(ClassSize.ARRAY + blockDataSizes.length * Bytes.SIZEOF_INT);
843      }
844
845      return ClassSize.align(heapSize);
846    }
847
848    protected abstract long calculateHeapSizeForBlockKeys(long heapSize);
849  }
850
851  /**
852   * Writes the block index into the output stream. Generate the tree from bottom up. The leaf level
853   * is written to disk as a sequence of inline blocks, if it is larger than a certain number of
854   * bytes. If the leaf level is not large enough, we write all entries to the root level instead.
855   * After all leaf blocks have been written, we end up with an index referencing the resulting leaf
856   * index blocks. If that index is larger than the allowed root index size, the writer will break
857   * it up into reasonable-size intermediate-level index block chunks write those chunks out, and
858   * create another index referencing those chunks. This will be repeated until the remaining index
859   * is small enough to become the root index. However, in most practical cases we will only have
860   * leaf-level blocks and the root index, or just the root index.
861   */
862  public static class BlockIndexWriter implements InlineBlockWriter {
863    /**
864     * While the index is being written, this represents the current block index referencing all
865     * leaf blocks, with one exception. If the file is being closed and there are not enough blocks
866     * to complete even a single leaf block, no leaf blocks get written and this contains the entire
867     * block index. After all levels of the index were written by
868     * {@link #writeIndexBlocks(FSDataOutputStream)}, this contains the final root-level index.
869     */
870    private BlockIndexChunk rootChunk = new BlockIndexChunk();
871
872    /**
873     * Current leaf-level chunk. New entries referencing data blocks get added to this chunk until
874     * it grows large enough to be written to disk.
875     */
876    private BlockIndexChunk curInlineChunk = new BlockIndexChunk();
877
878    /**
879     * The number of block index levels. This is one if there is only root level (even empty), two
880     * if there a leaf level and root level, and is higher if there are intermediate levels. This is
881     * only final after {@link #writeIndexBlocks(FSDataOutputStream)} has been called. The initial
882     * value accounts for the root level, and will be increased to two as soon as we find out there
883     * is a leaf-level in {@link #blockWritten(long, int, int)}.
884     */
885    private int numLevels = 1;
886
887    private HFileBlock.Writer blockWriter;
888    private byte[] firstKey = null;
889
890    /**
891     * The total number of leaf-level entries, i.e. entries referenced by leaf-level blocks. For the
892     * data block index this is equal to the number of data blocks.
893     */
894    private long totalNumEntries;
895
896    /** Total compressed size of all index blocks. */
897    private long totalBlockOnDiskSize;
898
899    /** Total uncompressed size of all index blocks. */
900    private long totalBlockUncompressedSize;
901
902    /** The maximum size guideline of all multi-level index blocks. */
903    private int maxChunkSize;
904
905    /** The maximum level of multi-level index blocks */
906    private int minIndexNumEntries;
907
908    /** Whether we require this block index to always be single-level. */
909    private boolean singleLevelOnly;
910
911    /** CacheConfig, or null if cache-on-write is disabled */
912    private CacheConfig cacheConf;
913
914    /** Name to use for computing cache keys */
915    private String nameForCaching;
916
917    /** Creates a single-level block index writer */
918    public BlockIndexWriter() {
919      this(null, null, null);
920      singleLevelOnly = true;
921    }
922
923    /**
924     * Creates a multi-level block index writer.
925     * @param blockWriter the block writer to use to write index blocks
926     * @param cacheConf   used to determine when and how a block should be cached-on-write.
927     */
928    public BlockIndexWriter(HFileBlock.Writer blockWriter, CacheConfig cacheConf,
929      String nameForCaching) {
930      if ((cacheConf == null) != (nameForCaching == null)) {
931        throw new IllegalArgumentException(
932          "Block cache and file name for " + "caching must be both specified or both null");
933      }
934
935      this.blockWriter = blockWriter;
936      this.cacheConf = cacheConf;
937      this.nameForCaching = nameForCaching;
938      this.maxChunkSize = HFileBlockIndex.DEFAULT_MAX_CHUNK_SIZE;
939      this.minIndexNumEntries = HFileBlockIndex.DEFAULT_MIN_INDEX_NUM_ENTRIES;
940    }
941
942    public void setMaxChunkSize(int maxChunkSize) {
943      if (maxChunkSize <= 0) {
944        throw new IllegalArgumentException("Invalid maximum index block size");
945      }
946      this.maxChunkSize = maxChunkSize;
947    }
948
949    public void setMinIndexNumEntries(int minIndexNumEntries) {
950      if (minIndexNumEntries <= 1) {
951        throw new IllegalArgumentException("Invalid maximum index level, should be >= 2");
952      }
953      this.minIndexNumEntries = minIndexNumEntries;
954    }
955
956    /**
957     * Writes the root level and intermediate levels of the block index into the output stream,
958     * generating the tree from bottom up. Assumes that the leaf level has been inline-written to
959     * the disk if there is enough data for more than one leaf block. We iterate by breaking the
960     * current level of the block index, starting with the index of all leaf-level blocks, into
961     * chunks small enough to be written to disk, and generate its parent level, until we end up
962     * with a level small enough to become the root level. If the leaf level is not large enough,
963     * there is no inline block index anymore, so we only write that level of block index to disk as
964     * the root level.
965     * @param out FSDataOutputStream
966     * @return position at which we entered the root-level index. n
967     */
968    public long writeIndexBlocks(FSDataOutputStream out) throws IOException {
969      if (curInlineChunk != null && curInlineChunk.getNumEntries() != 0) {
970        throw new IOException("Trying to write a multi-level block index, " + "but are "
971          + curInlineChunk.getNumEntries() + " entries in the " + "last inline chunk.");
972      }
973
974      // We need to get mid-key metadata before we create intermediate
975      // indexes and overwrite the root chunk.
976      byte[] midKeyMetadata = numLevels > 1 ? rootChunk.getMidKeyMetadata() : null;
977
978      if (curInlineChunk != null) {
979        while (
980          rootChunk.getRootSize() > maxChunkSize
981            // HBASE-16288: if firstKey is larger than maxChunkSize we will loop indefinitely
982            && rootChunk.getNumEntries() > minIndexNumEntries
983            // Sanity check. We will not hit this (minIndexNumEntries ^ 16) blocks can be addressed
984            && numLevels < 16
985        ) {
986          rootChunk = writeIntermediateLevel(out, rootChunk);
987          numLevels += 1;
988        }
989      }
990
991      // write the root level
992      long rootLevelIndexPos = out.getPos();
993
994      {
995        DataOutput blockStream = blockWriter.startWriting(BlockType.ROOT_INDEX);
996        rootChunk.writeRoot(blockStream);
997        if (midKeyMetadata != null) blockStream.write(midKeyMetadata);
998        blockWriter.writeHeaderAndData(out);
999        if (cacheConf != null) {
1000          cacheConf.getBlockCache().ifPresent(cache -> {
1001            HFileBlock blockForCaching = blockWriter.getBlockForCaching(cacheConf);
1002            cache.cacheBlock(new BlockCacheKey(nameForCaching, rootLevelIndexPos, true,
1003              blockForCaching.getBlockType()), blockForCaching);
1004          });
1005        }
1006      }
1007
1008      // Add root index block size
1009      totalBlockOnDiskSize += blockWriter.getOnDiskSizeWithoutHeader();
1010      totalBlockUncompressedSize += blockWriter.getUncompressedSizeWithoutHeader();
1011
1012      if (LOG.isTraceEnabled()) {
1013        LOG.trace("Wrote a " + numLevels + "-level index with root level at pos "
1014          + rootLevelIndexPos + ", " + rootChunk.getNumEntries() + " root-level entries, "
1015          + totalNumEntries + " total entries, "
1016          + StringUtils.humanReadableInt(this.totalBlockOnDiskSize) + " on-disk size, "
1017          + StringUtils.humanReadableInt(totalBlockUncompressedSize) + " total uncompressed size.");
1018      }
1019      return rootLevelIndexPos;
1020    }
1021
1022    /**
1023     * Writes the block index data as a single level only. Does not do any block framing.
1024     * @param out         the buffered output stream to write the index to. Typically a stream
1025     *                    writing into an {@link HFile} block.
1026     * @param description a short description of the index being written. Used in a log message. n
1027     */
1028    public void writeSingleLevelIndex(DataOutput out, String description) throws IOException {
1029      expectNumLevels(1);
1030
1031      if (!singleLevelOnly) throw new IOException("Single-level mode is turned off");
1032
1033      if (rootChunk.getNumEntries() > 0)
1034        throw new IOException("Root-level entries already added in " + "single-level mode");
1035
1036      rootChunk = curInlineChunk;
1037      curInlineChunk = new BlockIndexChunk();
1038
1039      if (LOG.isTraceEnabled()) {
1040        LOG.trace("Wrote a single-level " + description + " index with " + rootChunk.getNumEntries()
1041          + " entries, " + rootChunk.getRootSize() + " bytes");
1042      }
1043      rootChunk.writeRoot(out);
1044    }
1045
1046    /**
1047     * Split the current level of the block index into intermediate index blocks of permitted size
1048     * and write those blocks to disk. Return the next level of the block index referencing those
1049     * intermediate-level blocks. n * @param currentLevel the current level of the block index, such
1050     * as the a chunk referencing all leaf-level index blocks
1051     * @return the parent level block index, which becomes the root index after a few (usually zero)
1052     *         iterations n
1053     */
1054    private BlockIndexChunk writeIntermediateLevel(FSDataOutputStream out,
1055      BlockIndexChunk currentLevel) throws IOException {
1056      // Entries referencing intermediate-level blocks we are about to create.
1057      BlockIndexChunk parent = new BlockIndexChunk();
1058
1059      // The current intermediate-level block index chunk.
1060      BlockIndexChunk curChunk = new BlockIndexChunk();
1061
1062      for (int i = 0; i < currentLevel.getNumEntries(); ++i) {
1063        curChunk.add(currentLevel.getBlockKey(i), currentLevel.getBlockOffset(i),
1064          currentLevel.getOnDiskDataSize(i));
1065
1066        // HBASE-16288: We have to have at least minIndexNumEntries(16) items in the index so that
1067        // we won't end up with too-many levels for a index with very large rowKeys. Also, if the
1068        // first key is larger than maxChunkSize this will cause infinite recursion.
1069        if (i >= minIndexNumEntries && curChunk.getRootSize() >= maxChunkSize) {
1070          writeIntermediateBlock(out, parent, curChunk);
1071        }
1072      }
1073
1074      if (curChunk.getNumEntries() > 0) {
1075        writeIntermediateBlock(out, parent, curChunk);
1076      }
1077
1078      return parent;
1079    }
1080
1081    private void writeIntermediateBlock(FSDataOutputStream out, BlockIndexChunk parent,
1082      BlockIndexChunk curChunk) throws IOException {
1083      long beginOffset = out.getPos();
1084      DataOutputStream dos = blockWriter.startWriting(BlockType.INTERMEDIATE_INDEX);
1085      curChunk.writeNonRoot(dos);
1086      byte[] curFirstKey = curChunk.getBlockKey(0);
1087      blockWriter.writeHeaderAndData(out);
1088
1089      if (getCacheOnWrite()) {
1090        cacheConf.getBlockCache().ifPresent(cache -> {
1091          HFileBlock blockForCaching = blockWriter.getBlockForCaching(cacheConf);
1092          cache.cacheBlock(
1093            new BlockCacheKey(nameForCaching, beginOffset, true, blockForCaching.getBlockType()),
1094            blockForCaching);
1095        });
1096      }
1097
1098      // Add intermediate index block size
1099      totalBlockOnDiskSize += blockWriter.getOnDiskSizeWithoutHeader();
1100      totalBlockUncompressedSize += blockWriter.getUncompressedSizeWithoutHeader();
1101
1102      // OFFSET is the beginning offset the chunk of block index entries.
1103      // SIZE is the total byte size of the chunk of block index entries
1104      // + the secondary index size
1105      // FIRST_KEY is the first key in the chunk of block index
1106      // entries.
1107      parent.add(curFirstKey, beginOffset, blockWriter.getOnDiskSizeWithHeader());
1108
1109      // clear current block index chunk
1110      curChunk.clear();
1111      curFirstKey = null;
1112    }
1113
1114    /**
1115     * @return how many block index entries there are in the root level
1116     */
1117    public final int getNumRootEntries() {
1118      return rootChunk.getNumEntries();
1119    }
1120
1121    /**
1122     * @return the number of levels in this block index.
1123     */
1124    public int getNumLevels() {
1125      return numLevels;
1126    }
1127
1128    private void expectNumLevels(int expectedNumLevels) {
1129      if (numLevels != expectedNumLevels) {
1130        throw new IllegalStateException("Number of block index levels is " + numLevels
1131          + "but is expected to be " + expectedNumLevels);
1132      }
1133    }
1134
1135    /**
1136     * Whether there is an inline block ready to be written. In general, we write an leaf-level
1137     * index block as an inline block as soon as its size as serialized in the non-root format
1138     * reaches a certain threshold.
1139     */
1140    @Override
1141    public boolean shouldWriteBlock(boolean closing) {
1142      if (singleLevelOnly) {
1143        throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);
1144      }
1145
1146      if (curInlineChunk == null) {
1147        throw new IllegalStateException("curInlineChunk is null; has shouldWriteBlock been "
1148          + "called with closing=true and then called again?");
1149      }
1150
1151      if (curInlineChunk.getNumEntries() == 0) {
1152        return false;
1153      }
1154
1155      // We do have some entries in the current inline chunk.
1156      if (closing) {
1157        if (rootChunk.getNumEntries() == 0) {
1158          // We did not add any leaf-level blocks yet. Instead of creating a
1159          // leaf level with one block, move these entries to the root level.
1160
1161          expectNumLevels(1);
1162          rootChunk = curInlineChunk;
1163          curInlineChunk = null; // Disallow adding any more index entries.
1164          return false;
1165        }
1166
1167        return true;
1168      } else {
1169        return curInlineChunk.getNonRootSize() >= maxChunkSize;
1170      }
1171    }
1172
1173    /**
1174     * Write out the current inline index block. Inline blocks are non-root blocks, so the non-root
1175     * index format is used. n
1176     */
1177    @Override
1178    public void writeInlineBlock(DataOutput out) throws IOException {
1179      if (singleLevelOnly) throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);
1180
1181      // Write the inline block index to the output stream in the non-root
1182      // index block format.
1183      curInlineChunk.writeNonRoot(out);
1184
1185      // Save the first key of the inline block so that we can add it to the
1186      // parent-level index.
1187      firstKey = curInlineChunk.getBlockKey(0);
1188
1189      // Start a new inline index block
1190      curInlineChunk.clear();
1191    }
1192
1193    /**
1194     * Called after an inline block has been written so that we can add an entry referring to that
1195     * block to the parent-level index.
1196     */
1197    @Override
1198    public void blockWritten(long offset, int onDiskSize, int uncompressedSize) {
1199      // Add leaf index block size
1200      totalBlockOnDiskSize += onDiskSize;
1201      totalBlockUncompressedSize += uncompressedSize;
1202
1203      if (singleLevelOnly) throw new UnsupportedOperationException(INLINE_BLOCKS_NOT_ALLOWED);
1204
1205      if (firstKey == null) {
1206        throw new IllegalStateException(
1207          "Trying to add second-level index " + "entry with offset=" + offset + " and onDiskSize="
1208            + onDiskSize + "but the first key was not set in writeInlineBlock");
1209      }
1210
1211      if (rootChunk.getNumEntries() == 0) {
1212        // We are writing the first leaf block, so increase index level.
1213        expectNumLevels(1);
1214        numLevels = 2;
1215      }
1216
1217      // Add another entry to the second-level index. Include the number of
1218      // entries in all previous leaf-level chunks for mid-key calculation.
1219      rootChunk.add(firstKey, offset, onDiskSize, totalNumEntries);
1220      firstKey = null;
1221    }
1222
1223    @Override
1224    public BlockType getInlineBlockType() {
1225      return BlockType.LEAF_INDEX;
1226    }
1227
1228    /**
1229     * Add one index entry to the current leaf-level block. When the leaf-level block gets large
1230     * enough, it will be flushed to disk as an inline block.
1231     * @param firstKey      the first key of the data block
1232     * @param blockOffset   the offset of the data block
1233     * @param blockDataSize the on-disk size of the data block ({@link HFile} format version 2), or
1234     *                      the uncompressed size of the data block ( {@link HFile} format version
1235     *                      1).
1236     */
1237    public void addEntry(byte[] firstKey, long blockOffset, int blockDataSize) {
1238      curInlineChunk.add(firstKey, blockOffset, blockDataSize);
1239      ++totalNumEntries;
1240    }
1241
1242    /**
1243     * @throws IOException if we happened to write a multi-level index.
1244     */
1245    public void ensureSingleLevel() throws IOException {
1246      if (numLevels > 1) {
1247        throw new IOException(
1248          "Wrote a " + numLevels + "-level index with " + rootChunk.getNumEntries()
1249            + " root-level entries, but " + "this is expected to be a single-level block index.");
1250      }
1251    }
1252
1253    /**
1254     * @return true if we are using cache-on-write. This is configured by the caller of the
1255     *         constructor by either passing a valid block cache or null.
1256     */
1257    @Override
1258    public boolean getCacheOnWrite() {
1259      return cacheConf != null && cacheConf.shouldCacheIndexesOnWrite();
1260    }
1261
1262    /**
1263     * The total uncompressed size of the root index block, intermediate-level index blocks, and
1264     * leaf-level index blocks.
1265     * @return the total uncompressed size of all index blocks
1266     */
1267    public long getTotalUncompressedSize() {
1268      return totalBlockUncompressedSize;
1269    }
1270
1271  }
1272
1273  /**
1274   * A single chunk of the block index in the process of writing. The data in this chunk can become
1275   * a leaf-level, intermediate-level, or root index block.
1276   */
1277  static class BlockIndexChunk {
1278
1279    /** First keys of the key range corresponding to each index entry. */
1280    private final List<byte[]> blockKeys = new ArrayList<>();
1281
1282    /** Block offset in backing stream. */
1283    private final List<Long> blockOffsets = new ArrayList<>();
1284
1285    /** On-disk data sizes of lower-level data or index blocks. */
1286    private final List<Integer> onDiskDataSizes = new ArrayList<>();
1287
1288    /**
1289     * The cumulative number of sub-entries, i.e. entries on deeper-level block index entries.
1290     * numSubEntriesAt[i] is the number of sub-entries in the blocks corresponding to this chunk's
1291     * entries #0 through #i inclusively.
1292     */
1293    private final List<Long> numSubEntriesAt = new ArrayList<>();
1294
1295    /**
1296     * The offset of the next entry to be added, relative to the end of the "secondary index" in the
1297     * "non-root" format representation of this index chunk. This is the next value to be added to
1298     * the secondary index.
1299     */
1300    private int curTotalNonRootEntrySize = 0;
1301
1302    /**
1303     * The accumulated size of this chunk if stored in the root index format.
1304     */
1305    private int curTotalRootSize = 0;
1306
1307    /**
1308     * The "secondary index" used for binary search over variable-length records in a "non-root"
1309     * format block. These offsets are relative to the end of this secondary index.
1310     */
1311    private final List<Integer> secondaryIndexOffsetMarks = new ArrayList<>();
1312
1313    /**
1314     * Adds a new entry to this block index chunk.
1315     * @param firstKey              the first key in the block pointed to by this entry
1316     * @param blockOffset           the offset of the next-level block pointed to by this entry
1317     * @param onDiskDataSize        the on-disk data of the block pointed to by this entry,
1318     *                              including header size
1319     * @param curTotalNumSubEntries if this chunk is the root index chunk under construction, this
1320     *                              specifies the current total number of sub-entries in all
1321     *                              leaf-level chunks, including the one corresponding to the
1322     *                              second-level entry being added.
1323     */
1324    void add(byte[] firstKey, long blockOffset, int onDiskDataSize, long curTotalNumSubEntries) {
1325      // Record the offset for the secondary index
1326      secondaryIndexOffsetMarks.add(curTotalNonRootEntrySize);
1327      curTotalNonRootEntrySize += SECONDARY_INDEX_ENTRY_OVERHEAD + firstKey.length;
1328
1329      curTotalRootSize += Bytes.SIZEOF_LONG + Bytes.SIZEOF_INT
1330        + WritableUtils.getVIntSize(firstKey.length) + firstKey.length;
1331
1332      blockKeys.add(firstKey);
1333      blockOffsets.add(blockOffset);
1334      onDiskDataSizes.add(onDiskDataSize);
1335
1336      if (curTotalNumSubEntries != -1) {
1337        numSubEntriesAt.add(curTotalNumSubEntries);
1338
1339        // Make sure the parallel arrays are in sync.
1340        if (numSubEntriesAt.size() != blockKeys.size()) {
1341          throw new IllegalStateException("Only have key/value count " + "stats for "
1342            + numSubEntriesAt.size() + " block index " + "entries out of " + blockKeys.size());
1343        }
1344      }
1345    }
1346
1347    /**
1348     * The same as {@link #add(byte[], long, int, long)} but does not take the key/value into
1349     * account. Used for single-level indexes.
1350     * @see #add(byte[], long, int, long)
1351     */
1352    public void add(byte[] firstKey, long blockOffset, int onDiskDataSize) {
1353      add(firstKey, blockOffset, onDiskDataSize, -1);
1354    }
1355
1356    public void clear() {
1357      blockKeys.clear();
1358      blockOffsets.clear();
1359      onDiskDataSizes.clear();
1360      secondaryIndexOffsetMarks.clear();
1361      numSubEntriesAt.clear();
1362      curTotalNonRootEntrySize = 0;
1363      curTotalRootSize = 0;
1364    }
1365
1366    /**
1367     * Finds the entry corresponding to the deeper-level index block containing the given
1368     * deeper-level entry (a "sub-entry"), assuming a global 0-based ordering of sub-entries.
1369     * <p>
1370     * <i> Implementation note. </i> We are looking for i such that numSubEntriesAt[i - 1] <= k <
1371     * numSubEntriesAt[i], because a deeper-level block #i (0-based) contains sub-entries #
1372     * numSubEntriesAt[i - 1]'th through numSubEntriesAt[i] - 1, assuming a global 0-based ordering
1373     * of sub-entries. i is by definition the insertion point of k in numSubEntriesAt.
1374     * @param k sub-entry index, from 0 to the total number sub-entries - 1
1375     * @return the 0-based index of the entry corresponding to the given sub-entry
1376     */
1377    public int getEntryBySubEntry(long k) {
1378      // We define mid-key as the key corresponding to k'th sub-entry
1379      // (0-based).
1380
1381      int i = Collections.binarySearch(numSubEntriesAt, k);
1382
1383      // Exact match: cumulativeWeight[i] = k. This means chunks #0 through
1384      // #i contain exactly k sub-entries, and the sub-entry #k (0-based)
1385      // is in the (i + 1)'th chunk.
1386      if (i >= 0) return i + 1;
1387
1388      // Inexact match. Return the insertion point.
1389      return -i - 1;
1390    }
1391
1392    /**
1393     * Used when writing the root block index of a multi-level block index. Serializes additional
1394     * information allowing to efficiently identify the mid-key.
1395     * @return a few serialized fields for finding the mid-key
1396     * @throws IOException if could not create metadata for computing mid-key
1397     */
1398    public byte[] getMidKeyMetadata() throws IOException {
1399      ByteArrayOutputStream baos = new ByteArrayOutputStream(MID_KEY_METADATA_SIZE);
1400      DataOutputStream baosDos = new DataOutputStream(baos);
1401      long totalNumSubEntries = numSubEntriesAt.get(blockKeys.size() - 1);
1402      if (totalNumSubEntries == 0) {
1403        throw new IOException("No leaf-level entries, mid-key unavailable");
1404      }
1405      long midKeySubEntry = (totalNumSubEntries - 1) / 2;
1406      int midKeyEntry = getEntryBySubEntry(midKeySubEntry);
1407
1408      baosDos.writeLong(blockOffsets.get(midKeyEntry));
1409      baosDos.writeInt(onDiskDataSizes.get(midKeyEntry));
1410
1411      long numSubEntriesBefore = midKeyEntry > 0 ? numSubEntriesAt.get(midKeyEntry - 1) : 0;
1412      long subEntryWithinEntry = midKeySubEntry - numSubEntriesBefore;
1413      if (subEntryWithinEntry < 0 || subEntryWithinEntry > Integer.MAX_VALUE) {
1414        throw new IOException("Could not identify mid-key index within the "
1415          + "leaf-level block containing mid-key: out of range (" + subEntryWithinEntry
1416          + ", numSubEntriesBefore=" + numSubEntriesBefore + ", midKeySubEntry=" + midKeySubEntry
1417          + ")");
1418      }
1419
1420      baosDos.writeInt((int) subEntryWithinEntry);
1421
1422      if (baosDos.size() != MID_KEY_METADATA_SIZE) {
1423        throw new IOException("Could not write mid-key metadata: size=" + baosDos.size()
1424          + ", correct size: " + MID_KEY_METADATA_SIZE);
1425      }
1426
1427      // Close just to be good citizens, although this has no effect.
1428      baos.close();
1429
1430      return baos.toByteArray();
1431    }
1432
1433    /**
1434     * Writes the block index chunk in the non-root index block format. This format contains the
1435     * number of entries, an index of integer offsets for quick binary search on variable-length
1436     * records, and tuples of block offset, on-disk block size, and the first key for each entry. nn
1437     */
1438    void writeNonRoot(DataOutput out) throws IOException {
1439      // The number of entries in the block.
1440      out.writeInt(blockKeys.size());
1441
1442      if (secondaryIndexOffsetMarks.size() != blockKeys.size()) {
1443        throw new IOException("Corrupted block index chunk writer: " + blockKeys.size()
1444          + " entries but " + secondaryIndexOffsetMarks.size() + " secondary index items");
1445      }
1446
1447      // For each entry, write a "secondary index" of relative offsets to the
1448      // entries from the end of the secondary index. This works, because at
1449      // read time we read the number of entries and know where the secondary
1450      // index ends.
1451      for (int currentSecondaryIndex : secondaryIndexOffsetMarks)
1452        out.writeInt(currentSecondaryIndex);
1453
1454      // We include one other element in the secondary index to calculate the
1455      // size of each entry more easily by subtracting secondary index elements.
1456      out.writeInt(curTotalNonRootEntrySize);
1457
1458      for (int i = 0; i < blockKeys.size(); ++i) {
1459        out.writeLong(blockOffsets.get(i));
1460        out.writeInt(onDiskDataSizes.get(i));
1461        out.write(blockKeys.get(i));
1462      }
1463    }
1464
1465    /**
1466     * @return the size of this chunk if stored in the non-root index block format
1467     */
1468    int getNonRootSize() {
1469      return Bytes.SIZEOF_INT // Number of entries
1470        + Bytes.SIZEOF_INT * (blockKeys.size() + 1) // Secondary index
1471        + curTotalNonRootEntrySize; // All entries
1472    }
1473
1474    /**
1475     * Writes this chunk into the given output stream in the root block index format. This format is
1476     * similar to the {@link HFile} version 1 block index format, except that we store on-disk size
1477     * of the block instead of its uncompressed size.
1478     * @param out the data output stream to write the block index to. Typically a stream writing
1479     *            into an {@link HFile} block. n
1480     */
1481    void writeRoot(DataOutput out) throws IOException {
1482      for (int i = 0; i < blockKeys.size(); ++i) {
1483        out.writeLong(blockOffsets.get(i));
1484        out.writeInt(onDiskDataSizes.get(i));
1485        Bytes.writeByteArray(out, blockKeys.get(i));
1486      }
1487    }
1488
1489    /**
1490     * @return the size of this chunk if stored in the root index block format
1491     */
1492    int getRootSize() {
1493      return curTotalRootSize;
1494    }
1495
1496    /**
1497     * @return the number of entries in this block index chunk
1498     */
1499    public int getNumEntries() {
1500      return blockKeys.size();
1501    }
1502
1503    public byte[] getBlockKey(int i) {
1504      return blockKeys.get(i);
1505    }
1506
1507    public long getBlockOffset(int i) {
1508      return blockOffsets.get(i);
1509    }
1510
1511    public int getOnDiskDataSize(int i) {
1512      return onDiskDataSizes.get(i);
1513    }
1514
1515    public long getCumulativeNumKV(int i) {
1516      if (i < 0) return 0;
1517      return numSubEntriesAt.get(i);
1518    }
1519
1520  }
1521
1522  public static int getMaxChunkSize(Configuration conf) {
1523    return conf.getInt(MAX_CHUNK_SIZE_KEY, DEFAULT_MAX_CHUNK_SIZE);
1524  }
1525
1526  public static int getMinIndexNumEntries(Configuration conf) {
1527    return conf.getInt(MIN_INDEX_NUM_ENTRIES_KEY, DEFAULT_MIN_INDEX_NUM_ENTRIES);
1528  }
1529}