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.assertArrayEquals;
021import static org.junit.Assert.assertEquals;
022import static org.junit.Assert.assertFalse;
023import static org.junit.Assert.assertNotSame;
024import static org.junit.Assert.assertTrue;
025
026import java.util.ArrayList;
027import java.util.Arrays;
028import java.util.List;
029import org.apache.commons.lang3.ArrayUtils;
030import org.apache.hadoop.conf.Configuration;
031import org.apache.hadoop.hbase.HBaseClassTestRule;
032import org.apache.hadoop.hbase.HBaseTestingUtil;
033import org.apache.hadoop.hbase.HRegionLocation;
034import org.apache.hadoop.hbase.TableName;
035import org.apache.hadoop.hbase.client.RegionInfo;
036import org.apache.hadoop.hbase.client.RegionLocator;
037import org.apache.hadoop.hbase.client.Table;
038import org.apache.hadoop.hbase.testclassification.MediumTests;
039import org.apache.hadoop.hbase.testclassification.MiscTests;
040import org.apache.hadoop.hbase.util.RegionSplitter.DecimalStringSplit;
041import org.apache.hadoop.hbase.util.RegionSplitter.HexStringSplit;
042import org.apache.hadoop.hbase.util.RegionSplitter.SplitAlgorithm;
043import org.apache.hadoop.hbase.util.RegionSplitter.UniformSplit;
044import org.junit.AfterClass;
045import org.junit.BeforeClass;
046import org.junit.ClassRule;
047import org.junit.Rule;
048import org.junit.Test;
049import org.junit.experimental.categories.Category;
050import org.junit.rules.TestName;
051import org.slf4j.Logger;
052import org.slf4j.LoggerFactory;
053
054/**
055 * Tests for {@link RegionSplitter}, which can create a pre-split table or do a rolling split of an
056 * existing table.
057 */
058@Category({ MiscTests.class, MediumTests.class })
059public class TestRegionSplitter {
060
061  @ClassRule
062  public static final HBaseClassTestRule CLASS_RULE =
063    HBaseClassTestRule.forClass(TestRegionSplitter.class);
064
065  private final static Logger LOG = LoggerFactory.getLogger(TestRegionSplitter.class);
066  private final static HBaseTestingUtil UTIL = new HBaseTestingUtil();
067  private final static String CF_NAME = "SPLIT_TEST_CF";
068  private final static byte xFF = (byte) 0xff;
069
070  @Rule
071  public TestName name = new TestName();
072
073  @BeforeClass
074  public static void setup() throws Exception {
075    UTIL.startMiniCluster(2);
076  }
077
078  @AfterClass
079  public static void teardown() throws Exception {
080    UTIL.shutdownMiniCluster();
081  }
082
083  /**
084   * Test creating a pre-split table using the HexStringSplit algorithm.
085   */
086  @Test
087  public void testCreatePresplitTableHex() throws Exception {
088    final List<byte[]> expectedBounds = new ArrayList<>(17);
089    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
090    expectedBounds.add(Bytes.toBytes("10000000"));
091    expectedBounds.add(Bytes.toBytes("20000000"));
092    expectedBounds.add(Bytes.toBytes("30000000"));
093    expectedBounds.add(Bytes.toBytes("40000000"));
094    expectedBounds.add(Bytes.toBytes("50000000"));
095    expectedBounds.add(Bytes.toBytes("60000000"));
096    expectedBounds.add(Bytes.toBytes("70000000"));
097    expectedBounds.add(Bytes.toBytes("80000000"));
098    expectedBounds.add(Bytes.toBytes("90000000"));
099    expectedBounds.add(Bytes.toBytes("a0000000"));
100    expectedBounds.add(Bytes.toBytes("b0000000"));
101    expectedBounds.add(Bytes.toBytes("c0000000"));
102    expectedBounds.add(Bytes.toBytes("d0000000"));
103    expectedBounds.add(Bytes.toBytes("e0000000"));
104    expectedBounds.add(Bytes.toBytes("f0000000"));
105    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
106
107    // Do table creation/pre-splitting and verification of region boundaries
108    preSplitTableAndVerify(expectedBounds, HexStringSplit.class.getSimpleName(),
109      TableName.valueOf(name.getMethodName()));
110  }
111
112  /**
113   * Test creating a pre-split table and splitting it again using the HexStringSplit and
114   * DecimalStringSplit algorithms.
115   */
116  @Test
117  public void testSplitPresplitTable() throws Exception {
118    testSplitPresplitTable(new HexStringSplit());
119    testSplitPresplitTable(new DecimalStringSplit());
120  }
121
122  private void testSplitPresplitTable(RegionSplitter.NumberStringSplit splitter) throws Exception {
123    final List<byte[]> initialBounds = new ArrayList<>();
124    initialBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
125    initialBounds.addAll(Arrays.asList(splitter.split(8)));
126    initialBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
127
128    // Do table creation/pre-splitting and verification of region boundaries
129    final String className = splitter.getClass().getSimpleName();
130    final TableName tableName = TableName.valueOf(className);
131    preSplitTableAndVerify(initialBounds, className, tableName);
132
133    // Split the table again and verify the new region boundaries
134    final List<byte[]> expectedBounds = new ArrayList<>();
135    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
136    expectedBounds.addAll(Arrays.asList(splitter.split(16)));
137    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
138    rollingSplitAndVerify(tableName, className, expectedBounds);
139  }
140
141  /**
142   * Test creating a pre-split table using the UniformSplit algorithm.
143   */
144  @Test
145  public void testCreatePresplitTableUniform() throws Exception {
146    List<byte[]> expectedBounds = new ArrayList<>(17);
147    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
148    expectedBounds.add(new byte[] { 0x10, 0, 0, 0, 0, 0, 0, 0 });
149    expectedBounds.add(new byte[] { 0x20, 0, 0, 0, 0, 0, 0, 0 });
150    expectedBounds.add(new byte[] { 0x30, 0, 0, 0, 0, 0, 0, 0 });
151    expectedBounds.add(new byte[] { 0x40, 0, 0, 0, 0, 0, 0, 0 });
152    expectedBounds.add(new byte[] { 0x50, 0, 0, 0, 0, 0, 0, 0 });
153    expectedBounds.add(new byte[] { 0x60, 0, 0, 0, 0, 0, 0, 0 });
154    expectedBounds.add(new byte[] { 0x70, 0, 0, 0, 0, 0, 0, 0 });
155    expectedBounds.add(new byte[] { (byte) 0x80, 0, 0, 0, 0, 0, 0, 0 });
156    expectedBounds.add(new byte[] { (byte) 0x90, 0, 0, 0, 0, 0, 0, 0 });
157    expectedBounds.add(new byte[] { (byte) 0xa0, 0, 0, 0, 0, 0, 0, 0 });
158    expectedBounds.add(new byte[] { (byte) 0xb0, 0, 0, 0, 0, 0, 0, 0 });
159    expectedBounds.add(new byte[] { (byte) 0xc0, 0, 0, 0, 0, 0, 0, 0 });
160    expectedBounds.add(new byte[] { (byte) 0xd0, 0, 0, 0, 0, 0, 0, 0 });
161    expectedBounds.add(new byte[] { (byte) 0xe0, 0, 0, 0, 0, 0, 0, 0 });
162    expectedBounds.add(new byte[] { (byte) 0xf0, 0, 0, 0, 0, 0, 0, 0 });
163    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
164
165    // Do table creation/pre-splitting and verification of region boundaries
166    preSplitTableAndVerify(expectedBounds, UniformSplit.class.getSimpleName(),
167      TableName.valueOf(name.getMethodName()));
168  }
169
170  /**
171   * Unit tests for the HexStringSplit algorithm. Makes sure it divides up the space of keys in the
172   * way that we expect.
173   */
174  @Test
175  public void unitTestHexStringSplit() {
176    HexStringSplit splitter = new HexStringSplit();
177    // Check splitting while starting from scratch
178
179    byte[][] twoRegionsSplits = splitter.split(2);
180    assertEquals(1, twoRegionsSplits.length);
181    assertArrayEquals(Bytes.toBytes("80000000"), twoRegionsSplits[0]);
182
183    byte[][] threeRegionsSplits = splitter.split(3);
184    assertEquals(2, threeRegionsSplits.length);
185    byte[] expectedSplit0 = Bytes.toBytes("55555555");
186    assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
187    byte[] expectedSplit1 = Bytes.toBytes("aaaaaaaa");
188    assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
189
190    // Check splitting existing regions that have start and end points
191    byte[] splitPoint = splitter.split(Bytes.toBytes("10000000"), Bytes.toBytes("30000000"));
192    assertArrayEquals(Bytes.toBytes("20000000"), splitPoint);
193
194    byte[] lastRow = Bytes.toBytes("ffffffff");
195    assertArrayEquals(lastRow, splitter.lastRow());
196    byte[] firstRow = Bytes.toBytes("00000000");
197    assertArrayEquals(firstRow, splitter.firstRow());
198
199    // Halfway between 00... and 20... should be 10...
200    splitPoint = splitter.split(firstRow, Bytes.toBytes("20000000"));
201    assertArrayEquals(Bytes.toBytes("10000000"), splitPoint);
202
203    // Halfway between df... and ff... should be ef....
204    splitPoint = splitter.split(Bytes.toBytes("dfffffff"), lastRow);
205    assertArrayEquals(Bytes.toBytes("efffffff"), splitPoint);
206
207    // Check splitting region with multiple mappers per region
208    byte[][] splits =
209      splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("30000000"), 3, false);
210    assertEquals(2, splits.length);
211    assertArrayEquals(Bytes.toBytes("10000000"), splits[0]);
212    assertArrayEquals(Bytes.toBytes("20000000"), splits[1]);
213
214    splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("20000000"), 2, true);
215    assertEquals(3, splits.length);
216    assertArrayEquals(Bytes.toBytes("10000000"), splits[1]);
217  }
218
219  /**
220   * Unit tests for the DecimalStringSplit algorithm. Makes sure it divides up the space of keys in
221   * the way that we expect.
222   */
223  @Test
224  public void unitTestDecimalStringSplit() {
225    DecimalStringSplit splitter = new DecimalStringSplit();
226    // Check splitting while starting from scratch
227
228    byte[][] twoRegionsSplits = splitter.split(2);
229    assertEquals(1, twoRegionsSplits.length);
230    assertArrayEquals(Bytes.toBytes("50000000"), twoRegionsSplits[0]);
231
232    byte[][] threeRegionsSplits = splitter.split(3);
233    assertEquals(2, threeRegionsSplits.length);
234    byte[] expectedSplit0 = Bytes.toBytes("33333333");
235    assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
236    byte[] expectedSplit1 = Bytes.toBytes("66666666");
237    assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
238
239    // Check splitting existing regions that have start and end points
240    byte[] splitPoint = splitter.split(Bytes.toBytes("10000000"), Bytes.toBytes("30000000"));
241    assertArrayEquals(Bytes.toBytes("20000000"), splitPoint);
242
243    byte[] lastRow = Bytes.toBytes("99999999");
244    assertArrayEquals(lastRow, splitter.lastRow());
245    byte[] firstRow = Bytes.toBytes("00000000");
246    assertArrayEquals(firstRow, splitter.firstRow());
247
248    // Halfway between 00... and 20... should be 10...
249    splitPoint = splitter.split(firstRow, Bytes.toBytes("20000000"));
250    assertArrayEquals(Bytes.toBytes("10000000"), splitPoint);
251
252    // Halfway between 00... and 19... should be 09...
253    splitPoint = splitter.split(firstRow, Bytes.toBytes("19999999"));
254    assertArrayEquals(Bytes.toBytes("09999999"), splitPoint);
255
256    // Halfway between 79... and 99... should be 89....
257    splitPoint = splitter.split(Bytes.toBytes("79999999"), lastRow);
258    assertArrayEquals(Bytes.toBytes("89999999"), splitPoint);
259
260    // Check splitting region with multiple mappers per region
261    byte[][] splits =
262      splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("30000000"), 3, false);
263    assertEquals(2, splits.length);
264    assertArrayEquals(Bytes.toBytes("10000000"), splits[0]);
265    assertArrayEquals(Bytes.toBytes("20000000"), splits[1]);
266
267    splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("20000000"), 2, true);
268    assertEquals(3, splits.length);
269    assertArrayEquals(Bytes.toBytes("10000000"), splits[1]);
270  }
271
272  /**
273   * Unit tests for the UniformSplit algorithm. Makes sure it divides up the space of keys in the
274   * way that we expect.
275   */
276  @Test
277  public void unitTestUniformSplit() {
278    UniformSplit splitter = new UniformSplit();
279
280    // Check splitting while starting from scratch
281    try {
282      splitter.split(1);
283      throw new AssertionError("Splitting into <2 regions should have thrown exception");
284    } catch (IllegalArgumentException e) {
285    }
286
287    byte[][] twoRegionsSplits = splitter.split(2);
288    assertEquals(1, twoRegionsSplits.length);
289    assertArrayEquals(twoRegionsSplits[0], new byte[] { (byte) 0x80, 0, 0, 0, 0, 0, 0, 0 });
290
291    byte[][] threeRegionsSplits = splitter.split(3);
292    assertEquals(2, threeRegionsSplits.length);
293    byte[] expectedSplit0 = new byte[] { 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55 };
294    assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
295    byte[] expectedSplit1 = new byte[] { (byte) 0xAA, (byte) 0xAA, (byte) 0xAA, (byte) 0xAA,
296      (byte) 0xAA, (byte) 0xAA, (byte) 0xAA, (byte) 0xAA };
297    assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
298
299    // Check splitting existing regions that have start and end points
300    byte[] splitPoint = splitter.split(new byte[] { 0x10 }, new byte[] { 0x30 });
301    assertArrayEquals(new byte[] { 0x20 }, splitPoint);
302
303    byte[] lastRow = new byte[] { xFF, xFF, xFF, xFF, xFF, xFF, xFF, xFF };
304    assertArrayEquals(lastRow, splitter.lastRow());
305    byte[] firstRow = ArrayUtils.EMPTY_BYTE_ARRAY;
306    assertArrayEquals(firstRow, splitter.firstRow());
307
308    splitPoint = splitter.split(firstRow, new byte[] { 0x20 });
309    assertArrayEquals(splitPoint, new byte[] { 0x10 });
310
311    splitPoint =
312      splitter.split(new byte[] { (byte) 0xdf, xFF, xFF, xFF, xFF, xFF, xFF, xFF }, lastRow);
313    assertArrayEquals(splitPoint, new byte[] { (byte) 0xef, xFF, xFF, xFF, xFF, xFF, xFF, xFF });
314
315    splitPoint = splitter.split(new byte[] { 'a', 'a', 'a' }, new byte[] { 'a', 'a', 'b' });
316    assertArrayEquals(splitPoint, new byte[] { 'a', 'a', 'a', (byte) 0x80 });
317
318    // Check splitting region with multiple mappers per region
319    byte[][] splits =
320      splitter.split(new byte[] { 'a', 'a', 'a' }, new byte[] { 'a', 'a', 'd' }, 3, false);
321    assertEquals(2, splits.length);
322    assertArrayEquals(splits[0], new byte[] { 'a', 'a', 'b' });
323    assertArrayEquals(splits[1], new byte[] { 'a', 'a', 'c' });
324
325    splits = splitter.split(new byte[] { 'a', 'a', 'a' }, new byte[] { 'a', 'a', 'e' }, 2, true);
326    assertEquals(3, splits.length);
327    assertArrayEquals(splits[1], new byte[] { 'a', 'a', 'c' });
328  }
329
330  @Test
331  public void testUserInput() {
332    SplitAlgorithm algo = new HexStringSplit();
333    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
334    assertFalse(splitFailsPrecondition(algo, "00", "AA")); // custom is fine
335    assertTrue(splitFailsPrecondition(algo, "AA", "00")); // range error
336    assertTrue(splitFailsPrecondition(algo, "AA", "AA")); // range error
337    assertFalse(splitFailsPrecondition(algo, "0", "2", 3)); // should be fine
338    assertFalse(splitFailsPrecondition(algo, "0", "A", 11)); // should be fine
339    assertTrue(splitFailsPrecondition(algo, "0", "A", 12)); // too granular
340
341    algo = new DecimalStringSplit();
342    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
343    assertFalse(splitFailsPrecondition(algo, "00", "99")); // custom is fine
344    assertTrue(splitFailsPrecondition(algo, "99", "00")); // range error
345    assertTrue(splitFailsPrecondition(algo, "99", "99")); // range error
346    assertFalse(splitFailsPrecondition(algo, "0", "2", 3)); // should be fine
347    assertFalse(splitFailsPrecondition(algo, "0", "9", 10)); // should be fine
348    assertTrue(splitFailsPrecondition(algo, "0", "9", 11)); // too granular
349
350    algo = new UniformSplit();
351    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
352    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\xAA")); // custom is fine
353    assertTrue(splitFailsPrecondition(algo, "\\xAA", "\\x00")); // range error
354    assertTrue(splitFailsPrecondition(algo, "\\xAA", "\\xAA")); // range error
355    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x02", 3)); // should be fine
356    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x0A", 11)); // should be fine
357    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x0A", 12)); // should be fine
358  }
359
360  private boolean splitFailsPrecondition(SplitAlgorithm algo) {
361    return splitFailsPrecondition(algo, 100);
362  }
363
364  private boolean splitFailsPrecondition(SplitAlgorithm algo, String firstRow, String lastRow) {
365    return splitFailsPrecondition(algo, firstRow, lastRow, 100);
366  }
367
368  private boolean splitFailsPrecondition(SplitAlgorithm algo, String firstRow, String lastRow,
369    int numRegions) {
370    algo.setFirstRow(firstRow);
371    algo.setLastRow(lastRow);
372    return splitFailsPrecondition(algo, numRegions);
373  }
374
375  private boolean splitFailsPrecondition(SplitAlgorithm algo, int numRegions) {
376    try {
377      byte[][] s = algo.split(numRegions);
378      LOG.debug("split algo = " + algo);
379      if (s != null) {
380        StringBuilder sb = new StringBuilder();
381        for (byte[] b : s) {
382          sb.append(Bytes.toStringBinary(b) + "  ");
383        }
384        LOG.debug(sb.toString());
385      }
386      return false;
387    } catch (IllegalArgumentException e) {
388      return true;
389    } catch (IllegalStateException e) {
390      return true;
391    } catch (IndexOutOfBoundsException e) {
392      return true;
393    }
394  }
395
396  /**
397   * Creates a pre-split table with expectedBounds.size()+1 regions, then verifies that the region
398   * boundaries are the same as the expected region boundaries in expectedBounds.
399   * @throws Various junit assertions
400   */
401  private void preSplitTableAndVerify(List<byte[]> expectedBounds, String splitClass,
402    TableName tableName) throws Exception {
403    final int numRegions = expectedBounds.size() - 1;
404    final Configuration conf = UTIL.getConfiguration();
405    conf.setInt("split.count", numRegions);
406    SplitAlgorithm splitAlgo = RegionSplitter.newSplitAlgoInstance(conf, splitClass);
407    RegionSplitter.createPresplitTable(tableName, splitAlgo, new String[] { CF_NAME }, conf);
408    verifyBounds(expectedBounds, tableName);
409  }
410
411  @Test
412  public void noopRollingSplit() throws Exception {
413    final List<byte[]> expectedBounds = new ArrayList<>(1);
414    expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
415    rollingSplitAndVerify(TableName.valueOf(TestRegionSplitter.class.getSimpleName()),
416      "UniformSplit", expectedBounds);
417  }
418
419  private void rollingSplitAndVerify(TableName tableName, String splitClass,
420    List<byte[]> expectedBounds) throws Exception {
421    final Configuration conf = UTIL.getConfiguration();
422
423    // Set this larger than the number of splits so RegionSplitter won't block
424    conf.setInt("split.outstanding", 5);
425    SplitAlgorithm splitAlgo = RegionSplitter.newSplitAlgoInstance(conf, splitClass);
426    RegionSplitter.rollingSplit(tableName, splitAlgo, conf);
427    verifyBounds(expectedBounds, tableName);
428  }
429
430  private void verifyBounds(List<byte[]> expectedBounds, TableName tableName) throws Exception {
431    // Get region boundaries from the cluster and verify their endpoints
432    final int numRegions = expectedBounds.size() - 1;
433    try (Table table = UTIL.getConnection().getTable(tableName);
434      RegionLocator locator = UTIL.getConnection().getRegionLocator(tableName)) {
435      final List<HRegionLocation> regionInfoMap = locator.getAllRegionLocations();
436      assertEquals(numRegions, regionInfoMap.size());
437      for (HRegionLocation entry : regionInfoMap) {
438        final RegionInfo regionInfo = entry.getRegion();
439        byte[] regionStart = regionInfo.getStartKey();
440        byte[] regionEnd = regionInfo.getEndKey();
441
442        // This region's start key should be one of the region boundaries
443        int startBoundaryIndex = indexOfBytes(expectedBounds, regionStart);
444        assertNotSame(-1, startBoundaryIndex);
445
446        // This region's end key should be the region boundary that comes
447        // after the starting boundary.
448        byte[] expectedRegionEnd = expectedBounds.get(startBoundaryIndex + 1);
449        assertEquals(0, Bytes.compareTo(regionEnd, expectedRegionEnd));
450      }
451    }
452  }
453
454  /**
455   * List.indexOf() doesn't really work for a List&lt;byte[]>, because byte[] doesn't override
456   * equals(). This method checks whether a list contains a given element by checking each element
457   * using the byte array comparator.
458   * @return the index of the first element that equals compareTo, or -1 if no elements are equal.
459   */
460  static private int indexOfBytes(List<byte[]> list, byte[] compareTo) {
461    int listIndex = 0;
462    for (byte[] elem : list) {
463      if (Bytes.BYTES_COMPARATOR.compare(elem, compareTo) == 0) {
464        return listIndex;
465      }
466      listIndex++;
467    }
468    return -1;
469  }
470
471}