View Javadoc

1   /**
2    *
3    * Licensed to the Apache Software Foundation (ASF) under one
4    * or more contributor license agreements.  See the NOTICE file
5    * distributed with this work for additional information
6    * regarding copyright ownership.  The ASF licenses this file
7    * to you under the Apache License, Version 2.0 (the
8    * "License"); you may not use this file except in compliance
9    * with the License.  You may obtain a copy of the License at
10   *
11   *     http://www.apache.org/licenses/LICENSE-2.0
12   *
13   * Unless required by applicable law or agreed to in writing, software
14   * distributed under the License is distributed on an "AS IS" BASIS,
15   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
16   * See the License for the specific language governing permissions and
17   * limitations under the License.
18   */
19  package org.apache.hadoop.hbase.util;
20  
21  import static org.junit.Assert.assertEquals;
22  import static org.junit.Assert.assertTrue;
23  
24  import java.util.ArrayList;
25  import java.util.Collection;
26  import java.util.Comparator;
27  import java.util.List;
28  import java.util.SortedSet;
29  import java.util.UUID;
30  
31  import org.apache.commons.logging.Log;
32  import org.apache.commons.logging.LogFactory;
33  import org.apache.hadoop.hbase.SmallTests;
34  import org.junit.Test;
35  
36  import com.google.common.collect.ComparisonChain;
37  import com.google.common.collect.Multimap;
38  
39  import org.junit.experimental.categories.Category;
40  
41  @Category(SmallTests.class)
42  public class TestRegionSplitCalculator {
43    private static final Log LOG = LogFactory.getLog(TestRegionSplitCalculator.class);
44  
45    /**
46     * This is range uses a user specified start and end keys. It also has an
47     * extra tiebreaker so that different ranges with the same start/end key pair
48     * count as different regions.
49     */
50    static class SimpleRange implements KeyRange {
51      byte[] start, end;
52      UUID tiebreaker;
53  
54      SimpleRange(byte[] start, byte[] end) {
55        this.start = start;
56        this.end = end;
57        this.tiebreaker = UUID.randomUUID();
58      }
59  
60      @Override
61      public byte[] getStartKey() {
62        return start;
63      }
64  
65      @Override
66      public byte[] getEndKey() {
67        return end;
68      }
69  
70      public String toString() {
71        return "[" + Bytes.toString(start) + ", " + Bytes.toString(end) + "]";
72      }
73    }
74  
75    Comparator<SimpleRange> cmp = new Comparator<SimpleRange>() {
76      @Override
77      public int compare(SimpleRange sr1, SimpleRange sr2) {
78        ComparisonChain cc = ComparisonChain.start();
79        cc = cc.compare(sr1.getStartKey(), sr2.getStartKey(),
80            Bytes.BYTES_COMPARATOR);
81        cc = cc.compare(sr1.getEndKey(), sr2.getEndKey(),
82            RegionSplitCalculator.BYTES_COMPARATOR);
83        cc = cc.compare(sr1.tiebreaker, sr2.tiebreaker);
84        return cc.result();
85      }
86    };
87  
88    /**
89     * Check the "depth" (number of regions included at a split) of a generated
90     * split calculation
91     */
92    void checkDepths(SortedSet<byte[]> splits,
93        Multimap<byte[], SimpleRange> regions, Integer... depths) {
94      assertEquals(splits.size(), depths.length);
95      int i = 0;
96      for (byte[] k : splits) {
97        Collection<SimpleRange> rs = regions.get(k);
98        int sz = rs == null ? 0 : rs.size();
99        assertEquals((int) depths[i], sz);
100       i++;
101     }
102   }
103 
104   /**
105    * This dumps data in a visually reasonable way for visual debugging. It has
106    * the basic iteration structure.
107    */
108   String dump(SortedSet<byte[]> splits, Multimap<byte[], SimpleRange> regions) {
109     // we display this way because the last end key should be displayed as well.
110     StringBuilder sb = new StringBuilder();
111     for (byte[] k : splits) {
112       sb.append(Bytes.toString(k)).append(":\t");
113       for (SimpleRange r : regions.get(k)) {
114         sb.append(r.toString()).append("\t");
115       }
116       sb.append("\n");
117     }
118     String s = sb.toString();
119     LOG.info("\n" + s);
120     return s;
121   }
122 
123   @Test
124   public void testSplitCalculator() {
125     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
126     SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
127     SimpleRange c = new SimpleRange(Bytes.toBytes("C"), Bytes.toBytes("D"));
128     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
129         cmp);
130     sc.add(a);
131     sc.add(b);
132     sc.add(c);
133 
134     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
135     LOG.info("Standard");
136     String res = dump(sc.getSplits(), regions);
137     checkDepths(sc.getSplits(), regions, 1, 1, 1, 0);
138     assertEquals(res, "A:\t[A, B]\t\n" + "B:\t[B, C]\t\n" + "C:\t[C, D]\t\n"
139         + "D:\t\n");
140   }
141 
142   @Test
143   public void testSplitCalculatorNoEdge() {
144     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
145         cmp);
146 
147     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
148     LOG.info("Empty");
149     String res = dump(sc.getSplits(), regions);
150     checkDepths(sc.getSplits(), regions);
151     assertEquals("", res);
152   }
153 
154   @Test
155   public void testSplitCalculatorSingleEdge() {
156     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
157     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
158         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<SimpleRange>(
172         cmp);
173     sc.add(a);
174 
175     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
176     LOG.info("Single empty edge");
177     String res = dump(sc.getSplits(), regions);
178     checkDepths(sc.getSplits(), regions, 1);
179     assertEquals("A:\t[A, A]\t\n", res);
180   }
181 
182   @Test
183   public void testSplitCalculatorCoverSplit() {
184     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
185     SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
186     SimpleRange c = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
187     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
188         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<SimpleRange>(
207         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<SimpleRange>(
226         cmp);
227     sc.add(a);
228     sc.add(b);
229     sc.add(c);
230 
231     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
232     LOG.info("Hole between C and E");
233     String res = dump(sc.getSplits(), regions);
234     checkDepths(sc.getSplits(), regions, 1, 1, 0, 1, 0);
235     assertEquals("A:\t[A, B]\t\n" + "B:\t[B, C]\t\n" + "C:\t\n"
236         + "E:\t[E, F]\t\n" + "F:\t\n", res);
237   }
238 
239   @Test
240   public void testSplitCalculatorOverreach() {
241     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
242     SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("D"));
243     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
244         cmp);
245     sc.add(a);
246     sc.add(b);
247 
248     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
249     LOG.info("AC and BD overlap but share no start/end keys");
250     String res = dump(sc.getSplits(), regions);
251     checkDepths(sc.getSplits(), regions, 1, 2, 1, 0);
252     assertEquals("A:\t[A, C]\t\n" + "B:\t[A, C]\t[B, D]\t\n"
253         + "C:\t[B, D]\t\n" + "D:\t\n", res);
254   }
255 
256   @Test
257   public void testSplitCalculatorFloor() {
258     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
259     SimpleRange b = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B"));
260     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
261         cmp);
262     sc.add(a);
263     sc.add(b);
264 
265     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
266     LOG.info("AC and AB overlap in the beginning");
267     String res = dump(sc.getSplits(), regions);
268     checkDepths(sc.getSplits(), regions, 2, 1, 0);
269     assertEquals("A:\t[A, B]\t[A, C]\t\n" + "B:\t[A, C]\t\n" + "C:\t\n", res);
270   }
271 
272   @Test
273   public void testSplitCalculatorCeil() {
274     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
275     SimpleRange b = new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C"));
276     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
277         cmp);
278     sc.add(a);
279     sc.add(b);
280 
281     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
282     LOG.info("AC and BC overlap in the end");
283     String res = dump(sc.getSplits(), regions);
284     checkDepths(sc.getSplits(), regions, 1, 2, 0);
285     assertEquals("A:\t[A, C]\t\n" + "B:\t[A, C]\t[B, C]\t\n" + "C:\t\n", res);
286   }
287 
288   @Test
289   public void testSplitCalculatorEq() {
290     SimpleRange a = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
291     SimpleRange b = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
292 
293     LOG.info(a.tiebreaker + " - " + b.tiebreaker);
294     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
295         cmp);
296     sc.add(a);
297     sc.add(b);
298 
299     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
300     LOG.info("AC and AC overlap completely");
301     String res = dump(sc.getSplits(), regions);
302     checkDepths(sc.getSplits(), regions, 2, 0);
303     assertEquals("A:\t[A, C]\t[A, C]\t\n" + "C:\t\n", res);
304   }
305 
306   @Test
307   public void testSplitCalculatorBackwards() {
308     SimpleRange a = new SimpleRange(Bytes.toBytes("C"), Bytes.toBytes("A"));
309     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
310         cmp);
311     sc.add(a);
312 
313     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
314     LOG.info("CA is backwards");
315     String res = dump(sc.getSplits(), regions);
316     checkDepths(sc.getSplits(), regions); // expect nothing
317     assertEquals("", res);
318   }
319 
320   @Test
321   public void testComplex() {
322     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
323         cmp);
324     sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("Am")));
325     sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C")));
326     sc.add(new SimpleRange(Bytes.toBytes("Am"), Bytes.toBytes("C")));
327     sc.add(new SimpleRange(Bytes.toBytes("D"), Bytes.toBytes("E")));
328     sc.add(new SimpleRange(Bytes.toBytes("F"), Bytes.toBytes("G")));
329     sc.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("E")));
330     sc.add(new SimpleRange(Bytes.toBytes("H"), Bytes.toBytes("I")));
331     sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
332 
333     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
334     LOG.info("Something fairly complex");
335     String res = dump(sc.getSplits(), regions);
336     checkDepths(sc.getSplits(), regions, 3, 3, 3, 1, 2, 0, 1, 0, 1, 0);
337     assertEquals("A:\t[A, Am]\t[A, B]\t[A, C]\t\n"
338         + "Am:\t[A, B]\t[A, C]\t[Am, C]\t\n"
339         + "B:\t[A, C]\t[Am, C]\t[B, E]\t\n" + "C:\t[B, E]\t\n"
340         + "D:\t[B, E]\t[D, E]\t\n" + "E:\t\n" + "F:\t[F, G]\t\n" + "G:\t\n"
341         + "H:\t[H, I]\t\n" + "I:\t\n", res);
342   }
343 
344   @Test
345   public void testBeginEndMarker() {
346     RegionSplitCalculator<SimpleRange> sc = new RegionSplitCalculator<SimpleRange>(
347         cmp);
348     sc.add(new SimpleRange(Bytes.toBytes(""), Bytes.toBytes("A")));
349     sc.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
350     sc.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("")));
351 
352     Multimap<byte[], SimpleRange> regions = sc.calcCoverage();
353     LOG.info("Special cases -- empty");
354     String res = dump(sc.getSplits(), regions);
355     checkDepths(sc.getSplits(), regions, 1, 1, 1, 0);
356     assertEquals(":\t[, A]\t\n" + "A:\t[A, B]\t\n" + "B:\t[B, ]\t\n"
357         + "null:\t\n", res);
358   }
359 
360   @Test
361   public void testBigRanges() {
362     SimpleRange ai = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("I"));
363     SimpleRange ae = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("E"));
364     SimpleRange ac = new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C"));
365 
366     Collection<SimpleRange> bigOverlap = new ArrayList<SimpleRange>();
367     bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("E")));
368     bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("C")));
369     bigOverlap.add(new SimpleRange(Bytes.toBytes("A"), Bytes.toBytes("B")));
370     bigOverlap.add(new SimpleRange(Bytes.toBytes("B"), Bytes.toBytes("C")));
371     bigOverlap.add(new SimpleRange(Bytes.toBytes("E"), Bytes.toBytes("H")));
372     bigOverlap.add(ai);
373     bigOverlap.add(ae);
374     bigOverlap.add(ac);
375 
376     // Expect 1 range to be returned: ai
377     List<SimpleRange> bigRanges = RegionSplitCalculator.findBigRanges(bigOverlap, 1);
378     assertEquals(1, bigRanges.size());
379     assertEquals(ai, bigRanges.get(0));
380 
381     // Expect 3 ranges to be returned: ai, ae and ac
382     bigRanges = RegionSplitCalculator.findBigRanges(bigOverlap, 3);
383     assertEquals(3, bigRanges.size());
384     assertEquals(ai, bigRanges.get(0));
385 
386     SimpleRange r1 = bigRanges.get(1);
387     SimpleRange r2 = bigRanges.get(2);
388     assertEquals("A", Bytes.toString(r1.start));
389     assertEquals("A", Bytes.toString(r2.start));
390     String r1e = Bytes.toString(r1.end);
391     String r2e = Bytes.toString(r2.end);
392     assertTrue((r1e.equals("C") && r2e.equals("E"))
393       || (r1e.equals("E") && r2e.equals("C")));
394   }
395 
396 }
397