HBase-Compaction-(2)ExploringCompactionPolicy以及RatioBasedCompactionPol

  /**
    * -- Default minor compaction selection algorithm:
    * choose CompactSelection from candidates --
    * First exclude bulk-load files if indicated in configuration.
    * Start at the oldest file and stop when you find the first file that
    * meets compaction criteria:
    * (1) a recently-flushed, small file (i.e. <= minCompactSize)
    * OR
    * (2) within the compactRatio of sum(newer_files)
    * Given normal skew, any newer files will also meet this criteria
    * <p/>
    * Additional Note:
    * If fileSizes.size() >> maxFilesToCompact, we will recurse on
    * compact().  Consider the oldest files first to avoid a
    * situation where we always compact [end-threshold,end).  Then, the
    * last file becomes an aggregate of the previous compactions.
    *
    * normal skew:
    *
    *         older ----> newer (increasing seqID)
    *     _
    *    | |   _
    *    | |  | |   _
    *  --|-|- |-|- |-|---_-------_-------  minCompactSize
    *    | |  | |  | |  | |  _  | |
    *    | |  | |  | |  | | | | | |
    *    | |  | |  | |  | | | | | |
    * @param candidates pre-filtrate
    * @return filtered subset
    */
  protected ArrayList<HStoreFile> applyCompactionPolicy(ArrayList<HStoreFile> candidates,
    boolean mayUseOffPeak, boolean mayBeStuck) throws IOException {
    if (candidates.isEmpty()) {
      return candidates;
    }

    // we're doing a minor compaction, let's see what files are applicable
    int start = 0;
    double ratio = comConf.getCompactionRatio();
    if (mayUseOffPeak) {
      ratio = comConf.getCompactionRatioOffPeak();
      LOG.info("Running an off-peak compaction, selection ratio = " + ratio);
    }

    // get store file sizes for incremental compacting selection.
    final int countOfFiles = candidates.size();
    long[] fileSizes = new long[countOfFiles];
    long[] sumSize = new long[countOfFiles];
    for (int i = countOfFiles - 1; i >= 0; --i) {
      HStoreFile file = candidates.get(i);
      fileSizes[i] = file.getReader().length();
      // calculate the sum of fileSizes[i,i+maxFilesToCompact-1) for algo
      int tooFar = i + comConf.getMaxFilesToCompact() - 1;
      sumSize[i] = fileSizes[i]
        + ((i + 1 < countOfFiles) ? sumSize[i + 1] : 0)
        - ((tooFar < countOfFiles) ? fileSizes[tooFar] : 0);
    }


    while (countOfFiles - start >= comConf.getMinFilesToCompact() &&
      fileSizes[start] > Math.max(comConf.getMinCompactSize(),
          (long) (sumSize[start + 1] * ratio))) {
      ++start;
    }
    if (start < countOfFiles) {
      LOG.info("Default compaction algorithm has selected " + (countOfFiles - start)
        + " files from " + countOfFiles + " candidates");
    } else if (mayBeStuck) {
      // We may be stuck. Compact the latest files if we can.
      int filesToLeave = candidates.size() - comConf.getMinFilesToCompact();
      if (filesToLeave >= 0) {
        start = filesToLeave;
      }
    }
    candidates.subList(0, start).clear();
    return candidates;
  }

    final int countOfFiles = candidates.size();
    long[] fileSizes = new long[countOfFiles];
    long[] sumSize = new long[countOfFiles];
    for (int i = countOfFiles - 1; i >= 0; --i) {
      HStoreFile file = candidates.get(i);
      fileSizes[i] = file.getReader().length();
      // calculate the sum of fileSizes[i,i+maxFilesToCompact-1) for algo
      int tooFar = i + comConf.getMaxFilesToCompact() - 1;
      sumSize[i] = fileSizes[i]
        + ((i + 1 < countOfFiles) ? sumSize[i + 1] : 0)
        - ((tooFar < countOfFiles) ? fileSizes[tooFar] : 0);
    }

package org.apache.hadoop.hbase.regionserver.compactions;

import org.apache.hadoop.conf.Configuration;
import org.apache.hadoop.hbase.regionserver.EmptyStoreConfigInformation;
import org.apache.hadoop.hbase.regionserver.HStoreFile;
import org.apache.hadoop.hbase.regionserver.StoreConfigInformation;
import org.junit.Before;
import org.junit.Test;

import java.io.IOException;
import java.util.ArrayList;

/**
 *
 * @see "http://hbase.apache.org/0.94/book/regions.arch.html"
 * to get more information
 *
 * */
public class TestRatioBasedCompactionPolicy {

    /**
     *
     * Suppose the order is from old to new.
     *
     * */
    ArrayList<HStoreFile> storeFiles = new ArrayList<>();
    MockStoreFileGenerator mockStoreFileGenerator = new MockStoreFileGenerator(TestRatioBasedCompactionPolicy.class);
    RatioBasedCompactionPolicy compactionPolicy = null;

    private void prepareCompactionPolicy() {
        Configuration configuration = new Configuration();
        configuration.set("hbase.hstore.compaction.ratio", "1.0");
        configuration.set("hbase.hstore.compaction.min", "3");
        configuration.set("hbase.hstore.compaction.max", "5");
        configuration.set("hbase.hstore.compaction.min.size", "10");
        configuration.set("hbase.hstore.compaction.max.size", "1000");

        StoreConfigInformation storeConfigInformation = new EmptyStoreConfigInformation();
        compactionPolicy = new RatioBasedCompactionPolicy(configuration, storeConfigInformation);
    }

    private void prepareCandidateStoreFilesForExamplean zhao1() {
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(100));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(50));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(23));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(12));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(12));
    }

    private void prepareCandidateStoreFilesForExample2() {
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(100));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(25));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(12));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(12));
    }

    private void prepareCandidateStoreFilesForExample3() {
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(7));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(6));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(5));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(4));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(3));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(2));
        storeFiles.add(mockStoreFileGenerator.createMockStoreFileBytes(1));
    }

    @Test
    public void testApplyCompactionPolicyForExample1() throws IOException {
        prepareCandidateStoreFilesForExample1();
        prepareCompactionPolicy();
        ArrayList<HStoreFile> toCompact = compactionPolicy.applyCompactionPolicy(storeFiles, false, false);
        for (HStoreFile hsf : toCompact) {
            System.out.println(hsf.getReader().length());
        }
    }

    @Test
    public void testApplyCompactionPolicyForExample2() throws IOException {
        prepareCandidateStoreFilesForExample2();
        prepareCompactionPolicy();
        ArrayList<HStoreFile> toCompact = compactionPolicy.applyCompactionPolicy(storeFiles, false, false);
        for (HStoreFile hsf : toCompact) {
            System.out.println(hsf.getReader().length());
        }
    }

    @Test
    public void testApplyCompactionPolicyForExample3() throws IOException {
        prepareCandidateStoreFilesForExample3();
        prepareCompactionPolicy();
        ArrayList<HStoreFile> toCompact = compactionPolicy.applyCompactionPolicy(storeFiles, false, false);
        for (HStoreFile hsf : toCompact) {
            System.out.println(hsf.getReader().length());
        }
    }
}

  /**
   *
   * Reading:
   *    Like `RatioBasedCompactionPolicy`, but select files by range, not one by one.
   *    Find out the longest (must large than min_compact_file and less than max_compact_size) file sequence
   *        and the smallest total file size
   *        to compact
   *
   * */
  public List<HStoreFile> applyCompactionPolicy(List<HStoreFile> candidates, boolean mightBeStuck,
      boolean mayUseOffPeak, int minFiles, int maxFiles) {
    final double currentRatio = mayUseOffPeak
        ? comConf.getCompactionRatioOffPeak() : comConf.getCompactionRatio();

    // Start off choosing nothing.
    List<HStoreFile> bestSelection = new ArrayList<>(0);
    List<HStoreFile> smallest = mightBeStuck ? new ArrayList<>(0) : null;
    long bestSize = 0;
    long smallestSize = Long.MAX_VALUE;

    int opts = 0, optsInRatio = 0, bestStart = -1; // for debug logging
    // Consider every starting place.
    for (int start = 0; start < candidates.size(); start++) {
      // Consider every different sub list permutation in between start and end with min files.
      for (int currentEnd = start + minFiles - 1;
          currentEnd < candidates.size(); currentEnd++) {
        List<HStoreFile> potentialMatchFiles = candidates.subList(start, currentEnd + 1);

        // Sanity checks
        if (potentialMatchFiles.size() < minFiles) {
          continue;
        }
        if (potentialMatchFiles.size() > maxFiles) {
          continue;
        }

        // Compute the total size of files that will
        // have to be read if this set of files is compacted.
        long size = getTotalStoreSize(potentialMatchFiles);

        // Store the smallest set of files.  This stored set of files will be used
        // if it looks like the algorithm is stuck.
        if (mightBeStuck && size < smallestSize) {
          smallest = potentialMatchFiles;
          smallestSize = size;
        }

        if (size > comConf.getMaxCompactSize(mayUseOffPeak)) {
          continue;
        }

        ++opts;
        if (size >= comConf.getMinCompactSize()
            && !filesInRatio(potentialMatchFiles, currentRatio)) {
          continue;
        }

        ++optsInRatio;
        if (isBetterSelection(bestSelection, bestSize, potentialMatchFiles, size, mightBeStuck)) {
          bestSelection = potentialMatchFiles;
          bestSize = size;
          bestStart = start;
        }
      }
    }
    if (bestSelection.isEmpty() && mightBeStuck) {
      LOG.debug("Exploring compaction algorithm has selected " + smallest.size()
          + " files of size "+ smallestSize + " because the store might be stuck");
      return new ArrayList<>(smallest);
    }
    LOG.debug("Exploring compaction algorithm has selected {}  files of size {} starting at " +
      "candidate #{} after considering {} permutations with {} in ratio", bestSelection.size(),
      bestSize, bestSize, opts, optsInRatio);
    return new ArrayList<>(bestSelection);
  }