hbase-server/src/test/java/org/apache/hadoop/hbase/util/TestRegionSplitter.java

   1 /**
   2  * Licensed to the Apache Software Foundation (ASF) under one
   3  * or more contributor license agreements.  See the NOTICE file
   4  * distributed with this work for additional information
   5  * regarding copyright ownership.  The ASF licenses this file
   6  * to you under the Apache License, Version 2.0 (the
   7  * "License"); you may not use this file except in compliance
   8  * with the License.  You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package org.apache.hadoop.hbase.util;
  19
  20 import static org.junit.Assert.assertArrayEquals;
  21 import static org.junit.Assert.assertEquals;
  22 import static org.junit.Assert.assertFalse;
  23 import static org.junit.Assert.assertNotSame;
  24 import static org.junit.Assert.assertTrue;
  25
  26 import java.util.ArrayList;
  27 import java.util.List;
  28 import org.apache.commons.lang3.ArrayUtils;
  29 import org.apache.hadoop.conf.Configuration;
  30 import org.apache.hadoop.hbase.HBaseClassTestRule;
  31 import org.apache.hadoop.hbase.HBaseTestingUtility;
  32 import org.apache.hadoop.hbase.HRegionLocation;
  33 import org.apache.hadoop.hbase.TableName;
  34 import org.apache.hadoop.hbase.client.RegionInfo;
  35 import org.apache.hadoop.hbase.client.RegionLocator;
  36 import org.apache.hadoop.hbase.client.Table;
  37 import org.apache.hadoop.hbase.testclassification.MediumTests;
  38 import org.apache.hadoop.hbase.testclassification.MiscTests;
  39 import org.apache.hadoop.hbase.util.RegionSplitter.DecimalStringSplit;
  40 import org.apache.hadoop.hbase.util.RegionSplitter.HexStringSplit;
  41 import org.apache.hadoop.hbase.util.RegionSplitter.SplitAlgorithm;
  42 import org.apache.hadoop.hbase.util.RegionSplitter.UniformSplit;
  43 import org.junit.AfterClass;
  44 import org.junit.BeforeClass;
  45 import org.junit.ClassRule;
  46 import org.junit.Rule;
  47 import org.junit.Test;
  48 import org.junit.experimental.categories.Category;
  49 import org.junit.rules.TestName;
  50 import org.slf4j.Logger;
  51 import org.slf4j.LoggerFactory;
  52
  53 /**
  54  * Tests for {@link RegionSplitter}, which can create a pre-split table or do a
  55  * rolling split of an existing table.
  56  */
  57 @Category({MiscTests.class, MediumTests.class})
  58 public class TestRegionSplitter {
  59
  60   @ClassRule
  61   public static final HBaseClassTestRule CLASS_RULE =
  62       HBaseClassTestRule.forClass(TestRegionSplitter.class);
  63
  64     private final static Logger LOG = LoggerFactory.getLogger(TestRegionSplitter.class);
  65     private final static HBaseTestingUtility UTIL = new HBaseTestingUtility();
  66     private final static String CF_NAME = "SPLIT_TEST_CF";
  67     private final static byte xFF = (byte) 0xff;
  68
  69     @Rule
  70     public TestName name = new TestName();
  71
  72     @BeforeClass
  73     public static void setup() throws Exception {
  74         UTIL.startMiniCluster();
  75     }
  76
  77     @AfterClass
  78     public static void teardown() throws Exception {
  79         UTIL.shutdownMiniCluster();
  80     }
  81
  82     /**
  83      * Test creating a pre-split table using the HexStringSplit algorithm.
  84      */
  85   @Test
  86   public void testCreatePresplitTableHex() throws Exception {
  87     final List<byte[]> expectedBounds = new ArrayList<>(17);
  88     expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
  89     expectedBounds.add(Bytes.toBytes("10000000"));
  90     expectedBounds.add(Bytes.toBytes("20000000"));
  91     expectedBounds.add(Bytes.toBytes("30000000"));
  92     expectedBounds.add(Bytes.toBytes("40000000"));
  93     expectedBounds.add(Bytes.toBytes("50000000"));
  94     expectedBounds.add(Bytes.toBytes("60000000"));
  95     expectedBounds.add(Bytes.toBytes("70000000"));
  96     expectedBounds.add(Bytes.toBytes("80000000"));
  97     expectedBounds.add(Bytes.toBytes("90000000"));
  98     expectedBounds.add(Bytes.toBytes("a0000000"));
  99     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,
 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(Bytes.toBytes("80000000"), twoRegionsSplits[0]);
 153
 154     byte[][] threeRegionsSplits = splitter.split(3);
 155     assertEquals(2, threeRegionsSplits.length);
 156     byte[] expectedSplit0 = Bytes.toBytes("55555555");
 157     assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
 158     byte[] expectedSplit1 = Bytes.toBytes("aaaaaaaa");
 159     assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
 160
 161     // Check splitting existing regions that have start and end points
 162     byte[] splitPoint = splitter.split(Bytes.toBytes("10000000"), Bytes.toBytes("30000000"));
 163     assertArrayEquals(Bytes.toBytes("20000000"), splitPoint);
 164
 165     byte[] lastRow = Bytes.toBytes("ffffffff");
 166     assertArrayEquals(lastRow, splitter.lastRow());
 167     byte[] firstRow = Bytes.toBytes("00000000");
 168     assertArrayEquals(firstRow, splitter.firstRow());
 169
 170     // Halfway between 00... and 20... should be 10...
 171     splitPoint = splitter.split(firstRow, Bytes.toBytes("20000000"));
 172     assertArrayEquals(Bytes.toBytes("10000000"), splitPoint);
 173
 174     // Halfway between df... and ff... should be ef....
 175     splitPoint = splitter.split(Bytes.toBytes("dfffffff"), lastRow);
 176     assertArrayEquals(Bytes.toBytes("efffffff"), splitPoint);
 177
 178     // Check splitting region with multiple mappers per region
 179     byte[][] splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("30000000"),
 180         3, false);
 181     assertEquals(2, splits.length);
 182     assertArrayEquals(Bytes.toBytes("10000000"), splits[0]);
 183     assertArrayEquals(Bytes.toBytes("20000000"), splits[1]);
 184
 185     splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("20000000"), 2, true);
 186     assertEquals(3, splits.length);
 187     assertArrayEquals(Bytes.toBytes("10000000"), splits[1]);
 188   }
 189
 190   /**
 191    * Unit tests for the DecimalStringSplit algorithm. Makes sure it divides up the
 192    * space of keys in the way that we expect.
 193    */
 194   @Test
 195   public void unitTestDecimalStringSplit() {
 196     DecimalStringSplit splitter = new DecimalStringSplit();
 197     // Check splitting while starting from scratch
 198
 199     byte[][] twoRegionsSplits = splitter.split(2);
 200     assertEquals(1, twoRegionsSplits.length);
 201     assertArrayEquals(Bytes.toBytes("50000000"), twoRegionsSplits[0]);
 202
 203     byte[][] threeRegionsSplits = splitter.split(3);
 204     assertEquals(2, threeRegionsSplits.length);
 205     byte[] expectedSplit0 = Bytes.toBytes("33333333");
 206     assertArrayEquals(expectedSplit0, threeRegionsSplits[0]);
 207     byte[] expectedSplit1 = Bytes.toBytes("66666666");
 208     assertArrayEquals(expectedSplit1, threeRegionsSplits[1]);
 209
 210     // Check splitting existing regions that have start and end points
 211     byte[] splitPoint = splitter.split(Bytes.toBytes("10000000"), Bytes.toBytes("30000000"));
 212     assertArrayEquals(Bytes.toBytes("20000000"), splitPoint);
 213
 214     byte[] lastRow = Bytes.toBytes("99999999");
 215     assertArrayEquals(lastRow, splitter.lastRow());
 216     byte[] firstRow = Bytes.toBytes("00000000");
 217     assertArrayEquals(firstRow, splitter.firstRow());
 218
 219     // Halfway between 00... and 20... should be 10...
 220     splitPoint = splitter.split(firstRow, Bytes.toBytes("20000000"));
 221     assertArrayEquals(Bytes.toBytes("10000000"), splitPoint);
 222
 223     // Halfway between 00... and 19... should be 09...
 224     splitPoint = splitter.split(firstRow, Bytes.toBytes("19999999"));
 225     assertArrayEquals(Bytes.toBytes("09999999"), splitPoint);
 226
 227     // Halfway between 79... and 99... should be 89....
 228     splitPoint = splitter.split(Bytes.toBytes("79999999"), lastRow);
 229     assertArrayEquals(Bytes.toBytes("89999999"), splitPoint);
 230
 231     // Check splitting region with multiple mappers per region
 232     byte[][] splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("30000000"),
 233         3, false);
 234     assertEquals(2, splits.length);
 235     assertArrayEquals(Bytes.toBytes("10000000"), splits[0]);
 236     assertArrayEquals(Bytes.toBytes("20000000"), splits[1]);
 237
 238     splits = splitter.split(Bytes.toBytes("00000000"), Bytes.toBytes("20000000"), 2, true);
 239     assertEquals(3, splits.length);
 240     assertArrayEquals(Bytes.toBytes("10000000"), splits[1]);
 241   }
 242
 243   /**
 244    * Unit tests for the UniformSplit algorithm. Makes sure it divides up the space of
 245    * keys in the way that we expect.
 246    */
 247   @Test
 248   public void unitTestUniformSplit() {
 249     UniformSplit splitter = new UniformSplit();
 250
 251     // Check splitting while starting from scratch
 252     try {
 253       splitter.split(1);
 254       throw new AssertionError("Splitting into <2 regions should have thrown exception");
 255     } catch (IllegalArgumentException e) { }
 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 = splitter.split(new byte[] {(byte)0xdf, xFF, xFF, xFF, xFF,
 282       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 = splitter.split(new byte[] {'a', 'a', 'a'}, new byte[] {'a', 'a', 'd'},
 290         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,
 335       String lastRow) {
 336     return splitFailsPrecondition(algo, firstRow, lastRow, 100);
 337   }
 338
 339   private boolean splitFailsPrecondition(SplitAlgorithm algo, String firstRow,
 340       String lastRow, int numRegions) {
 341     algo.setFirstRow(firstRow);
 342     algo.setLastRow(lastRow);
 343     return splitFailsPrecondition(algo, numRegions);
 344   }
 345
 346   private boolean splitFailsPrecondition(SplitAlgorithm algo, int numRegions) {
 347     try {
 348       byte[][] s = algo.split(numRegions);
 349       LOG.debug("split algo = " + algo);
 350       if (s != null) {
 351         StringBuilder sb = new StringBuilder();
 352         for (byte[] b : s) {
 353           sb.append(Bytes.toStringBinary(b) + "  ");
 354         }
 355         LOG.debug(sb.toString());
 356       }
 357       return false;
 358     } catch (IllegalArgumentException e) {
 359       return true;
 360     } catch (IllegalStateException e) {
 361       return true;
 362     } catch (IndexOutOfBoundsException e) {
 363       return true;
 364     }
 365   }
 366
 367   /**
 368    * Creates a pre-split table with expectedBounds.size()+1 regions, then
 369    * verifies that the region boundaries are the same as the expected
 370    * region boundaries in expectedBounds.
 371    * @throws Various junit assertions
 372    */
 373   private void preSplitTableAndVerify(List<byte[]> expectedBounds,
 374       String splitClass, TableName tableName) throws Exception {
 375     final int numRegions = expectedBounds.size()-1;
 376     final Configuration conf = UTIL.getConfiguration();
 377     conf.setInt("split.count", numRegions);
 378     SplitAlgorithm splitAlgo = RegionSplitter.newSplitAlgoInstance(conf, splitClass);
 379     RegionSplitter.createPresplitTable(tableName, splitAlgo, new String[] { CF_NAME }, conf);
 380     verifyBounds(expectedBounds, tableName);
 381   }
 382
 383   @Test
 384   public void noopRollingSplit() throws Exception {
 385     final List<byte[]> expectedBounds = new ArrayList<>(1);
 386     expectedBounds.add(ArrayUtils.EMPTY_BYTE_ARRAY);
 387     rollingSplitAndVerify(TableName.valueOf(TestRegionSplitter.class.getSimpleName()),
 388         "UniformSplit", expectedBounds);
 389   }
 390
 391   private void rollingSplitAndVerify(TableName tableName, String splitClass,
 392       List<byte[]> expectedBounds)  throws Exception {
 393     final Configuration conf = UTIL.getConfiguration();
 394
 395     // Set this larger than the number of splits so RegionSplitter won't block
 396     conf.setInt("split.outstanding", 5);
 397     SplitAlgorithm splitAlgo = RegionSplitter.newSplitAlgoInstance(conf, splitClass);
 398     RegionSplitter.rollingSplit(tableName, splitAlgo, conf);
 399     verifyBounds(expectedBounds, tableName);
 400   }
 401
 402   private void verifyBounds(List<byte[]> expectedBounds, TableName tableName)
 403           throws Exception {
 404     // Get region boundaries from the cluster and verify their endpoints
 405     final int numRegions = expectedBounds.size()-1;
 406     try (Table table = UTIL.getConnection().getTable(tableName);
 407         RegionLocator locator = UTIL.getConnection().getRegionLocator(tableName)) {
 408       final List<HRegionLocation> regionInfoMap = locator.getAllRegionLocations();
 409       assertEquals(numRegions, regionInfoMap.size());
 410       for (HRegionLocation entry : regionInfoMap) {
 411         final RegionInfo regionInfo = entry.getRegion();
 412         byte[] regionStart = regionInfo.getStartKey();
 413         byte[] regionEnd = regionInfo.getEndKey();
 414
 415         // This region's start key should be one of the region boundaries
 416         int startBoundaryIndex = indexOfBytes(expectedBounds, regionStart);
 417         assertNotSame(-1, startBoundaryIndex);
 418
 419         // This region's end key should be the region boundary that comes
 420         // after the starting boundary.
 421         byte[] expectedRegionEnd = expectedBounds.get(startBoundaryIndex + 1);
 422         assertEquals(0, Bytes.compareTo(regionEnd, expectedRegionEnd));
 423       }
 424     }
 425   }
 426
 427   /**
 428    * List.indexOf() doesn't really work for a List&lt;byte[]>, because byte[]
 429    * doesn't override equals(). This method checks whether a list contains
 430    * a given element by checking each element using the byte array comparator.
 431    * @return the index of the first element that equals compareTo, or -1 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