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.HBaseTestingUtility;
032import org.apache.hadoop.hbase.HRegionInfo;
033import org.apache.hadoop.hbase.HRegionLocation;
034import org.apache.hadoop.hbase.TableName;
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
055 * rolling split of an 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 HBaseTestingUtility UTIL = new HBaseTestingUtility();
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("10000000".getBytes());
090      expectedBounds.add("20000000".getBytes());
091      expectedBounds.add("30000000".getBytes());
092      expectedBounds.add("40000000".getBytes());
093      expectedBounds.add("50000000".getBytes());
094      expectedBounds.add("60000000".getBytes());
095      expectedBounds.add("70000000".getBytes());
096      expectedBounds.add("80000000".getBytes());
097      expectedBounds.add("90000000".getBytes());
098      expectedBounds.add("a0000000".getBytes());
099      expectedBounds.add("b0000000".getBytes());
100      expectedBounds.add("c0000000".getBytes());
101      expectedBounds.add("d0000000".getBytes());
102      expectedBounds.add("e0000000".getBytes());
103      expectedBounds.add("f0000000".getBytes());
104          expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
105
106          // Do table creation/pre-splitting and verification of region boundaries
107    preSplitTableAndVerify(expectedBounds,
108        HexStringSplit.class.getSimpleName(),
109        TableName.valueOf(name.getMethodName()));
110    }
111
112    /**
113     * Test creating a pre-split table using the UniformSplit algorithm.
114     */
115    @Test
116    public void testCreatePresplitTableUniform() throws Exception {
117      List<byte[]> expectedBounds = new ArrayList<>(17);
118      expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
119      expectedBounds.add(new byte[] {      0x10, 0, 0, 0, 0, 0, 0, 0});
120      expectedBounds.add(new byte[] {      0x20, 0, 0, 0, 0, 0, 0, 0});
121      expectedBounds.add(new byte[] {      0x30, 0, 0, 0, 0, 0, 0, 0});
122      expectedBounds.add(new byte[] {      0x40, 0, 0, 0, 0, 0, 0, 0});
123      expectedBounds.add(new byte[] { 0x50, 0, 0, 0, 0, 0, 0, 0 });
124      expectedBounds.add(new byte[] { 0x60, 0, 0, 0, 0, 0, 0, 0 });
125      expectedBounds.add(new byte[] { 0x70, 0, 0, 0, 0, 0, 0, 0 });
126      expectedBounds.add(new byte[] { (byte) 0x80, 0, 0, 0, 0, 0, 0, 0 });
127      expectedBounds.add(new byte[] { (byte) 0x90, 0, 0, 0, 0, 0, 0, 0 });
128      expectedBounds.add(new byte[] {(byte)0xa0, 0, 0, 0, 0, 0, 0, 0});
129      expectedBounds.add(new byte[] { (byte) 0xb0, 0, 0, 0, 0, 0, 0, 0 });
130      expectedBounds.add(new byte[] { (byte) 0xc0, 0, 0, 0, 0, 0, 0, 0 });
131      expectedBounds.add(new byte[] { (byte) 0xd0, 0, 0, 0, 0, 0, 0, 0 });
132      expectedBounds.add(new byte[] {(byte)0xe0, 0, 0, 0, 0, 0, 0, 0});
133      expectedBounds.add(new byte[] { (byte) 0xf0, 0, 0, 0, 0, 0, 0, 0 });
134      expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
135
136      // Do table creation/pre-splitting and verification of region boundaries
137      preSplitTableAndVerify(expectedBounds, UniformSplit.class.getSimpleName(),
138          TableName.valueOf(name.getMethodName()));
139    }
140
141    /**
142     * Unit tests for the HexStringSplit algorithm. Makes sure it divides up the
143     * space of keys in the way that we expect.
144     */
145    @Test
146    public void unitTestHexStringSplit() {
147        HexStringSplit splitter = new HexStringSplit();
148        // Check splitting while starting from scratch
149
150        byte[][] twoRegionsSplits = splitter.split(2);
151        assertEquals(1, twoRegionsSplits.length);
152        assertArrayEquals("80000000".getBytes(), twoRegionsSplits[0]);
153
154        byte[][] threeRegionsSplits = splitter.split(3);
155        assertEquals(2, threeRegionsSplits.length);
156        byte[] expectedSplit0 = "55555555".getBytes();
157        assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
158        byte[] expectedSplit1 = "aaaaaaaa".getBytes();
159        assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
160
161        // Check splitting existing regions that have start and end points
162        byte[] splitPoint = splitter.split("10000000".getBytes(), "30000000".getBytes());
163        assertArrayEquals("20000000".getBytes(), splitPoint);
164
165        byte[] lastRow = "ffffffff".getBytes();
166        assertArrayEquals(lastRow, splitter.lastRow());
167        byte[] firstRow = "00000000".getBytes();
168        assertArrayEquals(firstRow, splitter.firstRow());
169
170        // Halfway between 00... and 20... should be 10...
171        splitPoint = splitter.split(firstRow, "20000000".getBytes());
172        assertArrayEquals("10000000".getBytes(), splitPoint);
173
174        // Halfway between df... and ff... should be ef....
175        splitPoint = splitter.split("dfffffff".getBytes(), lastRow);
176        assertArrayEquals("efffffff".getBytes(), splitPoint);
177
178        // Check splitting region with multiple mappers per region
179        byte[][] splits = splitter.split("00000000".getBytes(), "30000000".getBytes(), 3, false);
180        assertEquals(2, splits.length);
181        assertArrayEquals("10000000".getBytes(), splits[0]);
182        assertArrayEquals("20000000".getBytes(), splits[1]);
183
184        splits = splitter.split("00000000".getBytes(), "20000000".getBytes(), 2, true);
185        assertEquals(3, splits.length);
186        assertArrayEquals("10000000".getBytes(), splits[1]);
187    }
188
189    /**
190     * Unit tests for the DecimalStringSplit algorithm. Makes sure it divides up the
191     * space of keys in 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("50000000".getBytes(), twoRegionsSplits[0]);
201
202        byte[][] threeRegionsSplits = splitter.split(3);
203        assertEquals(2, threeRegionsSplits.length);
204        byte[] expectedSplit0 = "33333333".getBytes();
205        assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
206        byte[] expectedSplit1 = "66666666".getBytes();
207        assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
208
209        // Check splitting existing regions that have start and end points
210        byte[] splitPoint = splitter.split("10000000".getBytes(), "30000000".getBytes());
211        assertArrayEquals("20000000".getBytes(), splitPoint);
212
213        byte[] lastRow = "99999999".getBytes();
214        assertArrayEquals(lastRow, splitter.lastRow());
215        byte[] firstRow = "00000000".getBytes();
216        assertArrayEquals(firstRow, splitter.firstRow());
217
218        // Halfway between 00... and 20... should be 10...
219        splitPoint = splitter.split(firstRow, "20000000".getBytes());
220        assertArrayEquals("10000000".getBytes(), splitPoint);
221
222        // Halfway between 00... and 19... should be 09...
223        splitPoint = splitter.split(firstRow, "19999999".getBytes());
224        assertArrayEquals("09999999".getBytes(), splitPoint);
225
226        // Halfway between 79... and 99... should be 89....
227        splitPoint = splitter.split("79999999".getBytes(), lastRow);
228        assertArrayEquals("89999999".getBytes(), splitPoint);
229
230        // Check splitting region with multiple mappers per region
231        byte[][] splits = splitter.split("00000000".getBytes(), "30000000".getBytes(), 3, false);
232        assertEquals(2, splits.length);
233        assertArrayEquals("10000000".getBytes(), splits[0]);
234        assertArrayEquals("20000000".getBytes(), splits[1]);
235
236        splits = splitter.split("00000000".getBytes(), "20000000".getBytes(), 2, true);
237        assertEquals(3, splits.length);
238        assertArrayEquals("10000000".getBytes(), splits[1]);
239    }
240
241    /**
242     * Unit tests for the UniformSplit algorithm. Makes sure it divides up the space of
243     * keys in the way that we expect.
244     */
245    @Test
246    public void unitTestUniformSplit() {
247        UniformSplit splitter = new UniformSplit();
248
249        // Check splitting while starting from scratch
250        try {
251            splitter.split(1);
252            throw new AssertionError("Splitting into <2 regions should have thrown exception");
253        } catch (IllegalArgumentException e) { }
254
255        byte[][] twoRegionsSplits = splitter.split(2);
256        assertEquals(1, twoRegionsSplits.length);
257        assertArrayEquals(twoRegionsSplits[0], new byte[] { (byte) 0x80, 0, 0, 0, 0, 0, 0, 0 });
258
259        byte[][] threeRegionsSplits = splitter.split(3);
260        assertEquals(2, threeRegionsSplits.length);
261        byte[] expectedSplit0 = new byte[] {0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55, 0x55};
262        assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
263        byte[] expectedSplit1 = new byte[] {(byte)0xAA, (byte)0xAA, (byte)0xAA, (byte)0xAA,
264                (byte)0xAA, (byte)0xAA, (byte)0xAA, (byte)0xAA};
265        assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
266
267        // Check splitting existing regions that have start and end points
268        byte[] splitPoint = splitter.split(new byte[] {0x10}, new byte[] {0x30});
269        assertArrayEquals(new byte[] { 0x20 }, splitPoint);
270
271        byte[] lastRow = new byte[] {xFF, xFF, xFF, xFF, xFF, xFF, xFF, xFF};
272        assertArrayEquals(lastRow, splitter.lastRow());
273        byte[] firstRow = ArrayUtils.EMPTY_BYTE_ARRAY;
274        assertArrayEquals(firstRow, splitter.firstRow());
275
276        splitPoint = splitter.split(firstRow, new byte[] {0x20});
277        assertArrayEquals(splitPoint, new byte[] { 0x10 });
278
279        splitPoint = splitter.split(new byte[] {(byte)0xdf, xFF, xFF, xFF, xFF,
280                xFF, xFF, xFF}, lastRow);
281        assertArrayEquals(splitPoint, new byte[] { (byte) 0xef, xFF, xFF, xFF, xFF, xFF, xFF, xFF
282        });
283
284        splitPoint = splitter.split(new byte[] {'a', 'a', 'a'}, new byte[] {'a', 'a', 'b'});
285        assertArrayEquals(splitPoint, new byte[] { 'a', 'a', 'a', (byte) 0x80 });
286
287        // Check splitting region with multiple mappers per region
288        byte[][] splits = splitter.split(new byte[] {'a', 'a', 'a'}, new byte[] {'a', 'a', 'd'}, 3, false);
289        assertEquals(2, splits.length);
290        assertArrayEquals(splits[0], new byte[]{'a', 'a', 'b'});
291        assertArrayEquals(splits[1], new byte[]{'a', 'a', 'c'});
292
293        splits = splitter.split(new byte[] {'a', 'a', 'a'}, new byte[] {'a', 'a', 'e'}, 2, true);
294        assertEquals(3, splits.length);
295        assertArrayEquals(splits[1], new byte[] { 'a', 'a', 'c'});
296    }
297
298  @Test
299  public void testUserInput() {
300    SplitAlgorithm algo = new HexStringSplit();
301    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
302    assertFalse(splitFailsPrecondition(algo, "00", "AA")); // custom is fine
303    assertTrue(splitFailsPrecondition(algo, "AA", "00")); // range error
304    assertTrue(splitFailsPrecondition(algo, "AA", "AA")); // range error
305    assertFalse(splitFailsPrecondition(algo, "0", "2", 3)); // should be fine
306    assertFalse(splitFailsPrecondition(algo, "0", "A", 11)); // should be fine
307    assertTrue(splitFailsPrecondition(algo, "0", "A", 12)); // too granular
308
309    algo = new DecimalStringSplit();
310    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
311    assertFalse(splitFailsPrecondition(algo, "00", "99")); // custom is fine
312    assertTrue(splitFailsPrecondition(algo, "99", "00")); // range error
313    assertTrue(splitFailsPrecondition(algo, "99", "99")); // range error
314    assertFalse(splitFailsPrecondition(algo, "0", "2", 3)); // should be fine
315    assertFalse(splitFailsPrecondition(algo, "0", "9", 10)); // should be fine
316    assertTrue(splitFailsPrecondition(algo, "0", "9", 11)); // too granular
317
318    algo = new UniformSplit();
319    assertFalse(splitFailsPrecondition(algo)); // default settings are fine
320    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\xAA")); // custom is fine
321    assertTrue(splitFailsPrecondition(algo, "\\xAA", "\\x00")); // range error
322    assertTrue(splitFailsPrecondition(algo, "\\xAA", "\\xAA")); // range error
323    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x02", 3)); // should be fine
324    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x0A", 11)); // should be fine
325    assertFalse(splitFailsPrecondition(algo, "\\x00", "\\x0A", 12)); // should be fine
326  }
327
328  private boolean splitFailsPrecondition(SplitAlgorithm algo) {
329    return splitFailsPrecondition(algo, 100);
330  }
331
332  private boolean splitFailsPrecondition(SplitAlgorithm algo, String firstRow,
333      String lastRow) {
334    return splitFailsPrecondition(algo, firstRow, lastRow, 100);
335  }
336
337  private boolean splitFailsPrecondition(SplitAlgorithm algo, String firstRow,
338      String lastRow, int numRegions) {
339    algo.setFirstRow(firstRow);
340    algo.setLastRow(lastRow);
341    return splitFailsPrecondition(algo, numRegions);
342  }
343
344  private boolean splitFailsPrecondition(SplitAlgorithm algo, int numRegions) {
345    try {
346      byte[][] s = algo.split(numRegions);
347      LOG.debug("split algo = " + algo);
348      if (s != null) {
349        StringBuilder sb = new StringBuilder();
350        for (byte[] b : s) {
351          sb.append(Bytes.toStringBinary(b) + "  ");
352        }
353        LOG.debug(sb.toString());
354      }
355      return false;
356    } catch (IllegalArgumentException e) {
357      return true;
358    } catch (IllegalStateException e) {
359      return true;
360    } catch (IndexOutOfBoundsException e) {
361      return true;
362    }
363  }
364
365    /**
366     * Creates a pre-split table with expectedBounds.size()+1 regions, then
367     * verifies that the region boundaries are the same as the expected
368     * region boundaries in expectedBounds.
369     * @throws Various junit assertions
370     */
371    private void preSplitTableAndVerify(List<byte[]> expectedBounds,
372            String splitClass, 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)
401            throws Exception {
402      // Get region boundaries from the cluster and verify their endpoints
403      final int numRegions = expectedBounds.size()-1;
404      try (Table table = UTIL.getConnection().getTable(tableName);
405          RegionLocator locator = UTIL.getConnection().getRegionLocator(tableName)) {
406        final List<HRegionLocation> regionInfoMap = locator.getAllRegionLocations();
407        assertEquals(numRegions, regionInfoMap.size());
408        for (HRegionLocation entry : regionInfoMap) {
409          final HRegionInfo regionInfo = entry.getRegionInfo();
410          byte[] regionStart = regionInfo.getStartKey();
411          byte[] regionEnd = regionInfo.getEndKey();
412
413          // This region's start key should be one of the region boundaries
414          int startBoundaryIndex = indexOfBytes(expectedBounds, regionStart);
415          assertNotSame(-1, startBoundaryIndex);
416
417          // This region's end key should be the region boundary that comes
418          // after the starting boundary.
419          byte[] expectedRegionEnd = expectedBounds.get(startBoundaryIndex + 1);
420          assertEquals(0, Bytes.compareTo(regionEnd, expectedRegionEnd));
421        }
422      }
423    }
424
425    /**
426     * List.indexOf() doesn't really work for a List &lt;byte[]&gt;, because byte[]
427     * doesn't override equals(). This method checks whether a list contains
428     * a given element by checking each element using the byte array
429     * comparator.
430     * @return the index of the first element that equals compareTo, or -1
431     * if no elements are equal.
432     */
433    static private int indexOfBytes(List<byte[]> list,  byte[] compareTo) {
434        int listIndex = 0;
435        for(byte[] elem: list) {
436            if(Bytes.BYTES_COMPARATOR.compare(elem, compareTo) == 0) {
437                return listIndex;
438            }
439            listIndex++;
440        }
441        return -1;
442    }
443
444}
445