Package org.apache.hadoop.hbase.util

Class RegionSplitCalculator<R extends KeyRange>

java.lang.Object
org.apache.hadoop.hbase.util.RegionSplitCalculator<R>
Type Parameters:
R -
@Private public class RegionSplitCalculator<R extends KeyRange> extends Object
This is a generic region split calculator. It requires Ranges that provide start, end, and a comparator. It works in two phases -- the first adds ranges and rejects backwards ranges. Then one calls calcRegions to generate the multimap that has a start split key as a key and possibly multiple Ranges as members. To traverse, one normally would get the split set, and iterate through the calcRegions. Normal regions would have only one entry, holes would have zero, and any overlaps would have multiple entries. The interface is a bit cumbersome currently but is exposed this way so that clients can choose how to iterate through the region splits.

  • Field Summary

    Fields
    Modifier and Type
    Field
    Description
    static final Comparator<byte[]>
    BYTES_COMPARATOR
     
    private static final byte[]
    ENDKEY
    SPECIAL CASE
    private static final org.slf4j.Logger
    LOG
     
    private final Comparator<R>
    rangeCmp
     
    private final TreeSet<byte[]>
    splits
    This contains a sorted set of all the possible split points Invariant: once populated this has 0 entries if empty or at most n+1 values where n == number of added ranges.
    private final org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R>
    starts
    This is a map from start key to regions with the same start key.

  • Constructor Summary

    Constructors
    Constructor
    Description
    RegionSplitCalculator(Comparator<R> cmp)
     

  • Method Summary

    Modifier and Type
    Method
    Description
    boolean
    add(R range)
    Adds an edge to the split calculator
    org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R>
    calcCoverage()
    Generates a coverage multimap from split key to Regions that start with the split key.
    static <R extends KeyRange>
    List<R>
    findBigRanges(Collection<R> bigOverlap, int count)
    Find specified number of top ranges in a big overlap group.
    TreeSet<byte[]>
    getSplits()
     
    org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R>
    getStarts()
     
    private static <R extends KeyRange>
    byte[]
    specialEndKey(R range)
    SPECIAL CASE wrapper for empty end key

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • LOG

      private static final org.slf4j.Logger LOG

    • rangeCmp

      private final Comparator<R extends KeyRange> rangeCmp

    • splits

      private final TreeSet<byte[]> splits
      This contains a sorted set of all the possible split points Invariant: once populated this has 0 entries if empty or at most n+1 values where n == number of added ranges.

    • starts

      private final org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R extends KeyRange> starts
      This is a map from start key to regions with the same start key. Invariant: This always have n values in total

    • ENDKEY

      private static final byte[] ENDKEY
      SPECIAL CASE

    • BYTES_COMPARATOR

      public static final Comparator<byte[]> BYTES_COMPARATOR

  • Constructor Details

  • Method Details

    • specialEndKey

      private static <R extends KeyRange> byte[] specialEndKey(R range)
      SPECIAL CASE wrapper for empty end key
      Returns:
      ENDKEY if end key is empty, else normal endkey.

    • add

      public boolean add(R range)
      Adds an edge to the split calculator
      Returns:
      true if is included, false if backwards/invalid

    • calcCoverage

      public org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R> calcCoverage()
      Generates a coverage multimap from split key to Regions that start with the split key.
      Returns:
      coverage multimap

    • getSplits

      public TreeSet<byte[]> getSplits()

    • getStarts

      public org.apache.hbase.thirdparty.com.google.common.collect.Multimap<byte[],R> getStarts()

    • findBigRanges

      public static <R extends KeyRange> List<R> findBigRanges(Collection<R> bigOverlap, int count)
      Find specified number of top ranges in a big overlap group. It could return less if there are not that many top ranges. Once these top ranges are excluded, the big overlap group will be broken into ranges with no overlapping, or smaller overlapped groups, and most likely some holes.
      Parameters:
      bigOverlap - a list of ranges that overlap with each other
      count - the max number of ranges to find
      Returns:
      a list of ranges that overlap with most others