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