Source code

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.util;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertTrue;
022
023import java.util.ArrayList;
024import java.util.Collection;
025import java.util.Comparator;
026import java.util.List;
027import java.util.SortedSet;
028import java.util.UUID;
029import org.apache.hadoop.hbase.HBaseClassTestRule;
030import org.apache.hadoop.hbase.HBaseTestingUtility;
031import org.apache.hadoop.hbase.testclassification.MiscTests;
032import org.apache.hadoop.hbase.testclassification.SmallTests;
033import org.junit.ClassRule;
034import org.junit.Test;
035import org.junit.experimental.categories.Category;
036import org.slf4j.Logger;
037import org.slf4j.LoggerFactory;
038
039import org.apache.hbase.thirdparty.com.google.common.collect.ComparisonChain;
040import org.apache.hbase.thirdparty.com.google.common.collect.Multimap;
041
042@Category({MiscTests.class, SmallTests.class})
043public class TestRegionSplitCalculator {
044
045  @ClassRule
046  public static final HBaseClassTestRule CLASS_RULE =
047      HBaseClassTestRule.forClass(TestRegionSplitCalculator.class);
048
049  private static final Logger LOG = LoggerFactory.getLogger(TestRegionSplitCalculator.class);
050  public static final HBaseTestingUtility TEST_UTIL = new HBaseTestingUtility();
051  /**
052   * This is range uses a user specified start and end keys. It also has an
053   * extra tiebreaker so that different ranges with the same start/end key pair
054   * count as different regions.
055   */
056  static class SimpleRange implements KeyRange {
057    byte[] start, end;
058    UUID tiebreaker;
059
060    SimpleRange(byte[] start, byte[] end) {
061      this.start = start;
062      this.end = end;
063      this.tiebreaker = TEST_UTIL.getRandomUUID();
064    }
065
066    @Override
067    public byte[] getStartKey() {
068      return start;
069    }
070
071    @Override
072    public byte[] getEndKey() {
073      return end;
074    }
075
076    @Override
077    public String toString() {
078      return "[" + Bytes.toString(start) + ", " + Bytes.toString(end) + "]";
079    }
080  }
081
082  Comparator<SimpleRange> cmp = new Comparator<SimpleRange>() {
083    @Override
084    public int compare(SimpleRange sr1, SimpleRange sr2) {
085      ComparisonChain cc = ComparisonChain.start();
086      cc = cc.compare(sr1.getStartKey(), sr2.getStartKey(),
087          Bytes.BYTES_COMPARATOR);
088      cc = cc.compare(sr1.getEndKey(), sr2.getEndKey(),
089          RegionSplitCalculator.BYTES_COMPARATOR);
090      cc = cc.compare(sr1.tiebreaker, sr2.tiebreaker);
091      return cc.result();
092    }
093  };
094
095  /**
096   * Check the "depth" (number of regions included at a split) of a generated
097   * split calculation
098   */
099  void checkDepths(SortedSet<byte[]> splits,
100      Multimap<byte[], SimpleRange> regions, Integer... depths) {
101    assertEquals(splits.size(), depths.length);
102    int i = 0;
103    for (byte[] k : splits) {
104      Collection<SimpleRange> rs = regions.get(k);
105      int sz = rs == null ? 0 : rs.size();
106      assertEquals((int) depths[i], sz);
107      i++;
108    }
109  }
110
111  /**
112   * This dumps data in a visually reasonable way for visual debugging. It has
113   * the basic iteration structure.
114   */
115  String dump(SortedSet<byte[]> splits, Multimap<byte[], SimpleRange> regions) {
116    // we display this way because the last end key should be displayed as well.
117    StringBuilder sb = new StringBuilder();
118    for (byte[] k : splits) {
119      sb.append(Bytes.toString(k)).append(":\t");
120      for (SimpleRange r : regions.get(k)) {
121        sb.append(r.toString()).append("\t");
122      }
123      sb.append("\n");
124    }
125    String s = sb.toString();
126    LOG.info("\n" + s);
127    return s;
128  }
129
130  @Test
131  public void testSplitCalculator() {
132    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
133    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
134    SimpleRange c = new SimpleRange(Bytes.toBytes("C"), Bytes.toBytes("D"));
135    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
136    sc.add(a);
137    sc.add(b);
138    sc.add(c);
139
140    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
141    LOG.info("Standard");
142    String res = dump(sc.getSplits(), regions);
143    checkDepths(sc.getSplits(), regions, 1, 1, 1, 0);
144    assertEquals("A:\t[A, B]\t\n" + "B:\t[B, C]\t\n" + "C:\t[C, D]\t\nD:\t\n", res);
145  }
146
147  @Test
148  public void testSplitCalculatorNoEdge() {
149    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
150
151    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
152    LOG.info("Empty");
153    String res = dump(sc.getSplits(), regions);
154    checkDepths(sc.getSplits(), regions);
155    assertEquals("", res);
156  }
157
158  @Test
159  public void testSplitCalculatorSingleEdge() {
160    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
161    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
162    sc.add(a);
163
164    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
165    LOG.info("Single edge");
166    String res = dump(sc.getSplits(), regions);
167    checkDepths(sc.getSplits(), regions, 1, 0);
168    assertEquals("A:\t[A, B]\t\n" + "B:\t\n", res);
169  }
170
171  @Test
172  public void testSplitCalculatorDegenerateEdge() {
173    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("A"));
174    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
175    sc.add(a);
176
177    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
178    LOG.info("Single empty edge");
179    String res = dump(sc.getSplits(), regions);
180    checkDepths(sc.getSplits(), regions, 1);
181    assertEquals("A:\t[A, A]\t\n", res);
182  }
183
184  @Test
185  public void testSplitCalculatorCoverSplit() {
186    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
187    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
188    SimpleRange c = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
189    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
190    sc.add(a);
191    sc.add(b);
192    sc.add(c);
193
194    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
195    LOG.info("AC covers AB, BC");
196    String res = dump(sc.getSplits(), regions);
197    checkDepths(sc.getSplits(), regions, 2, 2, 0);
198    assertEquals("A:\t[A, B]\t[A, C]\t\n" + "B:\t[A, C]\t[B, C]\t\n"
199        + "C:\t\n", res);
200  }
201
202  @Test
203  public void testSplitCalculatorOverEndpoint() {
204    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
205    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
206    SimpleRange c = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("D"));
207    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
208    sc.add(a);
209    sc.add(b);
210    sc.add(c);
211
212    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
213    LOG.info("AB, BD covers BC");
214    String res = dump(sc.getSplits(), regions);
215    checkDepths(sc.getSplits(), regions, 1, 2, 1, 0);
216    assertEquals("A:\t[A, B]\t\n" + "B:\t[B, C]\t[B, D]\t\n"
217        + "C:\t[B, D]\t\n" + "D:\t\n", res);
218  }
219
220  @Test
221  public void testSplitCalculatorHoles() {
222    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
223    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
224    SimpleRange c = new SimpleRange(Bytes.toBytes("E"), Bytes.toBytes("F"));
225    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
226    sc.add(a);
227    sc.add(b);
228    sc.add(c);
229
230    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
231    LOG.info("Hole between C and E");
232    String res = dump(sc.getSplits(), regions);
233    checkDepths(sc.getSplits(), regions, 1, 1, 0, 1, 0);
234    assertEquals("A:\t[A, B]\t\n" + "B:\t[B, C]\t\n" + "C:\t\n"
235        + "E:\t[E, F]\t\n" + "F:\t\n", res);
236  }
237
238  @Test
239  public void testSplitCalculatorOverreach() {
240    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
241    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("D"));
242    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
243    sc.add(a);
244    sc.add(b);
245
246    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
247    LOG.info("AC and BD overlap but share no start/end keys");
248    String res = dump(sc.getSplits(), regions);
249    checkDepths(sc.getSplits(), regions, 1, 2, 1, 0);
250    assertEquals("A:\t[A, C]\t\n" + "B:\t[A, C]\t[B, D]\t\n"
251        + "C:\t[B, D]\t\n" + "D:\t\n", res);
252  }
253
254  @Test
255  public void testSplitCalculatorFloor() {
256    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
257    SimpleRange b = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
258    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
259    sc.add(a);
260    sc.add(b);
261
262    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
263    LOG.info("AC and AB overlap in the beginning");
264    String res = dump(sc.getSplits(), regions);
265    checkDepths(sc.getSplits(), regions, 2, 1, 0);
266    assertEquals("A:\t[A, B]\t[A, C]\t\n" + "B:\t[A, C]\t\n" + "C:\t\n", res);
267  }
268
269  @Test
270  public void testSplitCalculatorCeil() {
271    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
272    SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
273    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
274    sc.add(a);
275    sc.add(b);
276
277    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
278    LOG.info("AC and BC overlap in the end");
279    String res = dump(sc.getSplits(), regions);
280    checkDepths(sc.getSplits(), regions, 1, 2, 0);
281    assertEquals("A:\t[A, C]\t\n" + "B:\t[A, C]\t[B, C]\t\n" + "C:\t\n", res);
282  }
283
284  @Test
285  public void testSplitCalculatorEq() {
286    SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
287    SimpleRange b = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
288
289    LOG.info(a.tiebreaker + " - " + b.tiebreaker);
290    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
291    sc.add(a);
292    sc.add(b);
293
294    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
295    LOG.info("AC and AC overlap completely");
296    String res = dump(sc.getSplits(), regions);
297    checkDepths(sc.getSplits(), regions, 2, 0);
298    assertEquals("A:\t[A, C]\t[A, C]\t\n" + "C:\t\n", res);
299  }
300
301  @Test
302  public void testSplitCalculatorBackwards() {
303    SimpleRange a = new SimpleRange(Bytes.toBytes("C"), Bytes.toBytes("A"));
304    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
305    sc.add(a);
306
307    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
308    LOG.info("CA is backwards");
309    String res = dump(sc.getSplits(), regions);
310    checkDepths(sc.getSplits(), regions); // expect nothing
311    assertEquals("", res);
312  }
313
314  @Test
315  public void testComplex() {
316    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
317    sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("Am")));
318    sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C")));
319    sc.add(new SimpleRange(Bytes.toBytes("Am"), Bytes.toBytes("C")));
320    sc.add(new SimpleRange(Bytes.toBytes("D"), Bytes.toBytes("E")));
321    sc.add(new SimpleRange(Bytes.toBytes("F"), Bytes.toBytes("G")));
322    sc.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("E")));
323    sc.add(new SimpleRange(Bytes.toBytes("H"), Bytes.toBytes("I")));
324    sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
325
326    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
327    LOG.info("Something fairly complex");
328    String res = dump(sc.getSplits(), regions);
329    checkDepths(sc.getSplits(), regions, 3, 3, 3, 1, 2, 0, 1, 0, 1, 0);
330    assertEquals("A:\t[A, Am]\t[A, B]\t[A, C]\t\n"
331        + "Am:\t[A, B]\t[A, C]\t[Am, C]\t\n"
332        + "B:\t[A, C]\t[Am, C]\t[B, E]\t\n" + "C:\t[B, E]\t\n"
333        + "D:\t[B, E]\t[D, E]\t\n" + "E:\t\n" + "F:\t[F, G]\t\n" + "G:\t\n"
334        + "H:\t[H, I]\t\n" + "I:\t\n", res);
335  }
336
337  @Test
338  public void testBeginEndMarker() {
339    RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<>(cmp);
340    sc.add(new SimpleRange(Bytes.toBytes(""), Bytes.toBytes("A")));
341    sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
342    sc.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("")));
343
344    Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
345    LOG.info("Special cases -- empty");
346    String res = dump(sc.getSplits(), regions);
347    checkDepths(sc.getSplits(), regions, 1, 1, 1, 0);
348    assertEquals(":\t[, A]\t\n" + "A:\t[A, B]\t\n" + "B:\t[B, ]\t\n"
349        + "null:\t\n", res);
350  }
351
352  @Test
353  public void testBigRanges() {
354    SimpleRange ai = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("I"));
355    SimpleRange ae = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("E"));
356    SimpleRange ac = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
357
358    Collection<SimpleRange> bigOverlap = new ArrayList<>(8);
359    bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("E")));
360    bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C")));
361    bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
362    bigOverlap.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C")));
363    bigOverlap.add(new SimpleRange(Bytes.toBytes("E"), Bytes.toBytes("H")));
364    bigOverlap.add(ai);
365    bigOverlap.add(ae);
366    bigOverlap.add(ac);
367
368    // Expect 1 range to be returned: ai
369    List<SimpleRange> bigRanges = RegionSplitCalculator.findBigRanges(bigOverlap, 1);
370    assertEquals(1, bigRanges.size());
371    assertEquals(ai, bigRanges.get(0));
372
373    // Expect 3 ranges to be returned: ai, ae and ac
374    bigRanges = RegionSplitCalculator.findBigRanges(bigOverlap, 3);
375    assertEquals(3, bigRanges.size());
376    assertEquals(ai, bigRanges.get(0));
377
378    SimpleRange r1 = bigRanges.get(1);
379    SimpleRange r2 = bigRanges.get(2);
380    assertEquals("A", Bytes.toString(r1.start));
381    assertEquals("A", Bytes.toString(r2.start));
382    String r1e = Bytes.toString(r1.end);
383    String r2e = Bytes.toString(r2.end);
384    assertTrue((r1e.equals("C") && r2e.equals("E"))
385      || (r1e.equals("E") && r2e.equals("C")));
386  }
387
388}
389