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