View Javadoc

1   /**
2    * Copyright 2011 The Apache Software Foundation
3    *
4    * Licensed to the Apache Software Foundation (ASF) under one
5    * or more contributor license agreements.  See the NOTICE file
6    * distributed with this work for additional information
7    * regarding copyright ownership.  The ASF licenses this file
8    * to you under the Apache License, Version 2.0 (the
9    * "License"); you may not use this file except in compliance
10   * with the License.  You may obtain a copy of the License at
11   *
12   *     http://www.apache.org/licenses/LICENSE-2.0
13   *
14   * Unless required by applicable law or agreed to in writing, software
15   * distributed under the License is distributed on an "AS IS" BASIS,
16   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17   * See the License for the specific language governing permissions and
18   * limitations under the License.
19   */
20  package org.apache.hadoop.hbase.util;
21  
22  import java.util.ArrayList;
23  import java.util.Collection;
24  import java.util.Comparator;
25  import java.util.List;
26  import java.util.Map.Entry;
27  import java.util.TreeMap;
28  import java.util.TreeSet;
29  
30  import org.apache.commons.logging.Log;
31  import org.apache.commons.logging.LogFactory;
32  import org.apache.hadoop.hbase.util.Bytes.ByteArrayComparator;
33  
34  import com.google.common.collect.ArrayListMultimap;
35  import com.google.common.collect.Multimap;
36  import com.google.common.collect.TreeMultimap;
37  
38  /**
39   * This is a generic region split calculator. It requires Ranges that provide
40   * start, end, and a comparator. It works in two phases -- the first adds ranges
41   * and rejects backwards ranges. Then one calls calcRegions to generate the
42   * multimap that has a start split key as a key and possibly multiple Ranges as
43   * members.
44   * 
45   * To traverse, one normally would get the split set, and iterate through the
46   * calcRegions. Normal regions would have only one entry, holes would have zero,
47   * and any overlaps would have multiple entries.
48   * 
49   * The interface is a bit cumbersome currently but is exposed this way so that
50   * clients can choose how to iterate through the region splits.
51   * 
52   * @param <R>
53   */
54  public class RegionSplitCalculator<R extends KeyRange> {
55    final static Log LOG = LogFactory.getLog(RegionSplitCalculator.class);
56  
57    private final Comparator<R> rangeCmp;
58    /**
59     * This contains a sorted set of all the possible split points
60     * 
61     * Invariant: once populated this has 0 entries if empty or at most n+1 values
62     * where n == number of added ranges.
63     */
64    private final TreeSet<byte[]> splits = new TreeSet<byte[]>(BYTES_COMPARATOR);
65  
66    /**
67     * This is a map from start key to regions with the same start key.
68     * 
69     * Invariant: This always have n values in total
70     */
71    private final Multimap<byte[], R> starts = ArrayListMultimap.create();
72  
73    /**
74     * SPECIAL CASE
75     */
76    private final static byte[] ENDKEY = null;
77  
78    public RegionSplitCalculator(Comparator<R> cmp) {
79      rangeCmp = cmp;
80    }
81  
82    public final static Comparator<byte[]> BYTES_COMPARATOR = new ByteArrayComparator() {
83      @Override
84      public int compare(byte[] l, byte[] r) {
85        if (l == null && r == null)
86          return 0;
87        if (l == null)
88          return 1;
89        if (r == null)
90          return -1;
91        return super.compare(l, r);
92      }
93    };
94  
95    /**
96     * SPECIAL CASE wrapper for empty end key
97     * 
98     * @return ENDKEY if end key is empty, else normal endkey.
99     */
100   private static <R extends KeyRange> byte[] specialEndKey(R range) {
101     byte[] end = range.getEndKey();
102     if (end.length == 0) {
103       return ENDKEY;
104     }
105     return end;
106   }
107 
108   /**
109    * Adds an edge to the split calculator
110    * 
111    * @return true if is included, false if backwards/invalid
112    */
113   public boolean add(R range) {
114     byte[] start = range.getStartKey();
115     byte[] end = specialEndKey(range);
116 
117     if (end != ENDKEY && Bytes.compareTo(start, end) > 0) {
118       // don't allow backwards edges
119       LOG.debug("attempted to add backwards edge: " + Bytes.toString(start)
120           + " " + Bytes.toString(end));
121       return false;
122     }
123 
124     splits.add(start);
125     splits.add(end);
126     starts.put(start, range);
127     return true;
128   }
129 
130   /**
131    * Generates a coverage multimap from split key to Regions that start with the
132    * split key.
133    * 
134    * @return coverage multimap
135    */
136   public Multimap<byte[], R> calcCoverage() {
137     // This needs to be sorted to force the use of the comparator on the values,
138     // otherwise byte array comparison isn't used
139     Multimap<byte[], R> regions = TreeMultimap.create(BYTES_COMPARATOR,
140         rangeCmp);
141 
142     // march through all splits from the start points
143     for (Entry<byte[], Collection<R>> start : starts.asMap().entrySet()) {
144       byte[] key = start.getKey();
145       for (R r : start.getValue()) {
146         regions.put(key, r);
147 
148         for (byte[] coveredSplit : splits.subSet(r.getStartKey(),
149             specialEndKey(r))) {
150           regions.put(coveredSplit, r);
151         }
152       }
153     }
154     return regions;
155   }
156 
157   public TreeSet<byte[]> getSplits() {
158     return splits;
159   }
160 
161   public Multimap<byte[], R> getStarts() {
162     return starts;
163   }
164 
165   /**
166    * Find specified number of top ranges in a big overlap group.
167    * It could return less if there are not that many top ranges.
168    * Once these top ranges are excluded, the big overlap group will
169    * be broken into ranges with no overlapping, or smaller overlapped
170    * groups, and most likely some holes.
171    *
172    * @param bigOverlap a list of ranges that overlap with each other
173    * @param count the max number of ranges to find
174    * @return a list of ranges that overlap with most others
175    */
176   public static <R extends KeyRange> List<R>
177       findBigRanges(Collection<R> bigOverlap, int count) {
178     List<R> bigRanges = new ArrayList<R>();
179 
180     // The key is the count of overlaps,
181     // The value is a list of ranges that have that many overlaps
182     TreeMap<Integer, List<R>> overlapRangeMap = new TreeMap<Integer, List<R>>();
183     for (R r: bigOverlap) {
184       // Calculates the # of overlaps for each region
185       // and populates rangeOverlapMap
186       byte[] startKey = r.getStartKey();
187       byte[] endKey = specialEndKey(r);
188 
189       int overlappedRegions = 0;
190       for (R rr: bigOverlap) {
191         byte[] start = rr.getStartKey();
192         byte[] end = specialEndKey(rr);
193 
194         if (BYTES_COMPARATOR.compare(startKey, end) < 0
195             && BYTES_COMPARATOR.compare(endKey, start) > 0) {
196           overlappedRegions++;
197         }
198       }
199 
200       // One region always overlaps with itself,
201       // so overlappedRegions should be more than 1
202       // for actual overlaps.
203       if (overlappedRegions > 1) {
204         Integer key = Integer.valueOf(overlappedRegions);
205         List<R> ranges = overlapRangeMap.get(key);
206         if (ranges == null) {
207           ranges = new ArrayList<R>();
208           overlapRangeMap.put(key, ranges);
209         }
210         ranges.add(r);
211       }
212     }
213     int toBeAdded = count;
214     for (Integer key: overlapRangeMap.descendingKeySet()) {
215       List<R> chunk = overlapRangeMap.get(key);
216       int chunkSize = chunk.size();
217       if (chunkSize <= toBeAdded) {
218         bigRanges.addAll(chunk);
219         toBeAdded -= chunkSize;
220         if (toBeAdded > 0) continue;
221       } else {
222         // Try to use the middle chunk in case the overlapping is
223         // chained, for example: [a, c), [b, e), [d, g), [f h)...
224         // In such a case, sideline the middle chunk will break
225         // the group efficiently.
226         int start = (chunkSize - toBeAdded)/2;
227         int end = start + toBeAdded;
228         for (int i = start; i < end; i++) {
229           bigRanges.add(chunk.get(i));
230         }
231       }
232       break;
233     }
234     return bigRanges;
235   }
236 }