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