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