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.master.balancer;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertNotNull;
022import static org.junit.Assert.assertNull;
023import static org.junit.Assert.assertTrue;
024import static org.mockito.Mockito.mock;
025import static org.mockito.Mockito.when;
026
027import java.util.ArrayList;
028import java.util.List;
029import java.util.Map;
030import java.util.Queue;
031import java.util.TreeMap;
032import org.apache.hadoop.conf.Configuration;
033import org.apache.hadoop.hbase.ClusterMetrics;
034import org.apache.hadoop.hbase.HBaseClassTestRule;
035import org.apache.hadoop.hbase.HBaseConfiguration;
036import org.apache.hadoop.hbase.HConstants;
037import org.apache.hadoop.hbase.RegionMetrics;
038import org.apache.hadoop.hbase.ServerMetrics;
039import org.apache.hadoop.hbase.ServerName;
040import org.apache.hadoop.hbase.Size;
041import org.apache.hadoop.hbase.client.RegionInfo;
042import org.apache.hadoop.hbase.master.MockNoopMasterServices;
043import org.apache.hadoop.hbase.master.RegionPlan;
044import org.apache.hadoop.hbase.master.balancer.BaseLoadBalancer.Cluster;
045import org.apache.hadoop.hbase.master.balancer.StochasticLoadBalancer.ServerLocalityCostFunction;
046import org.apache.hadoop.hbase.testclassification.MasterTests;
047import org.apache.hadoop.hbase.testclassification.MediumTests;
048import org.apache.hadoop.hbase.util.Bytes;
049import org.junit.ClassRule;
050import org.junit.Test;
051import org.junit.experimental.categories.Category;
052
053@Category({ MasterTests.class, MediumTests.class })
054public class TestStochasticLoadBalancer extends BalancerTestBase {
055
056  @ClassRule
057  public static final HBaseClassTestRule CLASS_RULE =
058      HBaseClassTestRule.forClass(TestStochasticLoadBalancer.class);
059
060  private static final String REGION_KEY = "testRegion";
061
062  // Mapping of locality test -> expected locality
063  private float[] expectedLocalities = {1.0f, 0.0f, 0.50f, 0.25f, 1.0f};
064
065  /**
066   * Data set for testLocalityCost:
067   * [test][0][0] = mapping of server to number of regions it hosts
068   * [test][region + 1][0] = server that region is hosted on
069   * [test][region + 1][server + 1] = locality for region on server
070   */
071
072  private int[][][] clusterRegionLocationMocks = new int[][][]{
073
074      // Test 1: each region is entirely on server that hosts it
075      new int[][]{
076          new int[]{2, 1, 1},
077          new int[]{2, 0, 0, 100},   // region 0 is hosted and entirely local on server 2
078          new int[]{0, 100, 0, 0},   // region 1 is hosted and entirely on server 0
079          new int[]{0, 100, 0, 0},   // region 2 is hosted and entirely on server 0
080          new int[]{1, 0, 100, 0},   // region 1 is hosted and entirely on server 1
081      },
082
083      // Test 2: each region is 0% local on the server that hosts it
084      new int[][]{
085          new int[]{1, 2, 1},
086          new int[]{0, 0, 0, 100},   // region 0 is hosted and entirely local on server 2
087          new int[]{1, 100, 0, 0},   // region 1 is hosted and entirely on server 0
088          new int[]{1, 100, 0, 0},   // region 2 is hosted and entirely on server 0
089          new int[]{2, 0, 100, 0},   // region 1 is hosted and entirely on server 1
090      },
091
092      // Test 3: each region is 25% local on the server that hosts it (and 50% locality is possible)
093      new int[][]{
094          new int[]{1, 2, 1},
095          new int[]{0, 25, 0, 50},   // region 0 is hosted and entirely local on server 2
096          new int[]{1, 50, 25, 0},   // region 1 is hosted and entirely on server 0
097          new int[]{1, 50, 25, 0},   // region 2 is hosted and entirely on server 0
098          new int[]{2, 0, 50, 25},   // region 1 is hosted and entirely on server 1
099      },
100
101      // Test 4: each region is 25% local on the server that hosts it (and 100% locality is possible)
102      new int[][]{
103          new int[]{1, 2, 1},
104          new int[]{0, 25, 0, 100},   // region 0 is hosted and entirely local on server 2
105          new int[]{1, 100, 25, 0},   // region 1 is hosted and entirely on server 0
106          new int[]{1, 100, 25, 0},   // region 2 is hosted and entirely on server 0
107          new int[]{2, 0, 100, 25},   // region 1 is hosted and entirely on server 1
108      },
109
110      // Test 5: each region is 75% local on the server that hosts it (and 75% locality is possible everywhere)
111      new int[][]{
112          new int[]{1, 2, 1},
113          new int[]{0, 75, 75, 75},   // region 0 is hosted and entirely local on server 2
114          new int[]{1, 75, 75, 75},   // region 1 is hosted and entirely on server 0
115          new int[]{1, 75, 75, 75},   // region 2 is hosted and entirely on server 0
116          new int[]{2, 75, 75, 75},   // region 1 is hosted and entirely on server 1
117      },
118  };
119
120  @Test
121  public void testKeepRegionLoad() throws Exception {
122
123    ServerName sn = ServerName.valueOf("test:8080", 100);
124    int numClusterStatusToAdd = 20000;
125    for (int i = 0; i < numClusterStatusToAdd; i++) {
126      ServerMetrics sl = mock(ServerMetrics.class);
127
128      RegionMetrics rl = mock(RegionMetrics.class);
129      when(rl.getReadRequestCount()).thenReturn(0L);
130      when(rl.getWriteRequestCount()).thenReturn(0L);
131      when(rl.getMemStoreSize()).thenReturn(Size.ZERO);
132      when(rl.getStoreFileSize()).thenReturn(new Size(i, Size.Unit.MEGABYTE));
133
134      Map<byte[], RegionMetrics> regionLoadMap = new TreeMap<>(Bytes.BYTES_COMPARATOR);
135      regionLoadMap.put(Bytes.toBytes(REGION_KEY), rl);
136      when(sl.getRegionMetrics()).thenReturn(regionLoadMap);
137
138      ClusterMetrics clusterStatus = mock(ClusterMetrics.class);
139      Map<ServerName, ServerMetrics> serverMetricsMap = new TreeMap<>();
140      serverMetricsMap.put(sn, sl);
141      when(clusterStatus.getLiveServerMetrics()).thenReturn(serverMetricsMap);
142//      when(clusterStatus.getLoad(sn)).thenReturn(sl);
143
144      loadBalancer.setClusterMetrics(clusterStatus);
145    }
146
147    String regionNameAsString = RegionInfo.getRegionNameAsString(Bytes.toBytes(REGION_KEY));
148    assertTrue(loadBalancer.loads.get(regionNameAsString) != null);
149    assertTrue(loadBalancer.loads.get(regionNameAsString).size() == 15);
150
151    Queue<BalancerRegionLoad> loads = loadBalancer.loads.get(regionNameAsString);
152    int i = 0;
153    while(loads.size() > 0) {
154      BalancerRegionLoad rl = loads.remove();
155      assertEquals(i + (numClusterStatusToAdd - 15), rl.getStorefileSizeMB());
156      i ++;
157    }
158  }
159
160  @Test
161  public void testNeedBalance() {
162    float minCost = conf.getFloat("hbase.master.balancer.stochastic.minCostNeedBalance", 0.05f);
163    conf.setFloat("hbase.master.balancer.stochastic.minCostNeedBalance", 1.0f);
164    try {
165      // Test with/without per table balancer.
166      boolean[] perTableBalancerConfigs = {true, false};
167      for (boolean isByTable : perTableBalancerConfigs) {
168        conf.setBoolean(HConstants.HBASE_MASTER_LOADBALANCE_BYTABLE, isByTable);
169        loadBalancer.setConf(conf);
170        for (int[] mockCluster : clusterStateMocks) {
171          Map<ServerName, List<RegionInfo>> servers = mockClusterServers(mockCluster);
172          List<RegionPlan> plans = loadBalancer.balanceCluster(servers);
173          assertNull(plans);
174        }
175      }
176    } finally {
177      // reset config
178      conf.unset(HConstants.HBASE_MASTER_LOADBALANCE_BYTABLE);
179      conf.setFloat("hbase.master.balancer.stochastic.minCostNeedBalance", minCost);
180      loadBalancer.setConf(conf);
181    }
182  }
183
184  @Test
185  public void testLocalityCost() throws Exception {
186    Configuration conf = HBaseConfiguration.create();
187    MockNoopMasterServices master = new MockNoopMasterServices();
188    StochasticLoadBalancer.CostFunction
189        costFunction = new ServerLocalityCostFunction(conf, master);
190
191    for (int test = 0; test < clusterRegionLocationMocks.length; test++) {
192      int[][] clusterRegionLocations = clusterRegionLocationMocks[test];
193      MockCluster cluster = new MockCluster(clusterRegionLocations);
194      costFunction.init(cluster);
195      double cost = costFunction.cost();
196      double expected = 1 - expectedLocalities[test];
197      assertEquals(expected, cost, 0.001);
198    }
199  }
200
201  @Test
202  public void testMoveCost() throws Exception {
203    Configuration conf = HBaseConfiguration.create();
204    StochasticLoadBalancer.CostFunction
205        costFunction = new StochasticLoadBalancer.MoveCostFunction(conf);
206    for (int[] mockCluster : clusterStateMocks) {
207      BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
208      costFunction.init(cluster);
209      double cost = costFunction.cost();
210      assertEquals(0.0f, cost, 0.001);
211
212      // cluster region number is smaller than maxMoves=600
213      cluster.setNumRegions(200);
214      cluster.setNumMovedRegions(10);
215      cost = costFunction.cost();
216      assertEquals(0.05f, cost, 0.001);
217      cluster.setNumMovedRegions(100);
218      cost = costFunction.cost();
219      assertEquals(0.5f, cost, 0.001);
220      cluster.setNumMovedRegions(200);
221      cost = costFunction.cost();
222      assertEquals(1.0f, cost, 0.001);
223
224
225      // cluster region number is bigger than maxMoves=2500
226      cluster.setNumRegions(10000);
227      cluster.setNumMovedRegions(250);
228      cost = costFunction.cost();
229      assertEquals(0.1f, cost, 0.001);
230      cluster.setNumMovedRegions(1250);
231      cost = costFunction.cost();
232      assertEquals(0.5f, cost, 0.001);
233      cluster.setNumMovedRegions(2500);
234      cost = costFunction.cost();
235      assertEquals(1.0f, cost, 0.01);
236    }
237  }
238
239  @Test
240  public void testSkewCost() {
241    Configuration conf = HBaseConfiguration.create();
242    StochasticLoadBalancer.CostFunction
243        costFunction = new StochasticLoadBalancer.RegionCountSkewCostFunction(conf);
244    for (int[] mockCluster : clusterStateMocks) {
245      costFunction.init(mockCluster(mockCluster));
246      double cost = costFunction.cost();
247      assertTrue(cost >= 0);
248      assertTrue(cost <= 1.01);
249    }
250
251    costFunction.init(mockCluster(new int[]{0, 0, 0, 0, 1}));
252    assertEquals(0,costFunction.cost(), 0.01);
253    costFunction.init(mockCluster(new int[]{0, 0, 0, 1, 1}));
254    assertEquals(0, costFunction.cost(), 0.01);
255    costFunction.init(mockCluster(new int[]{0, 0, 1, 1, 1}));
256    assertEquals(0, costFunction.cost(), 0.01);
257    costFunction.init(mockCluster(new int[]{0, 1, 1, 1, 1}));
258    assertEquals(0, costFunction.cost(), 0.01);
259    costFunction.init(mockCluster(new int[]{1, 1, 1, 1, 1}));
260    assertEquals(0, costFunction.cost(), 0.01);
261    costFunction.init(mockCluster(new int[]{10000, 0, 0, 0, 0}));
262    assertEquals(1, costFunction.cost(), 0.01);
263  }
264
265  @Test
266  public void testCostAfterUndoAction() {
267    final int runs = 10;
268    loadBalancer.setConf(conf);
269    for (int[] mockCluster : clusterStateMocks) {
270      BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
271      loadBalancer.initCosts(cluster);
272      for (int i = 0; i != runs; ++i) {
273        final double expectedCost = loadBalancer.computeCost(cluster, Double.MAX_VALUE);
274        Cluster.Action action = loadBalancer.nextAction(cluster);
275        cluster.doAction(action);
276        loadBalancer.updateCostsWithAction(cluster, action);
277        Cluster.Action undoAction = action.undoAction();
278        cluster.doAction(undoAction);
279        loadBalancer.updateCostsWithAction(cluster, undoAction);
280        final double actualCost = loadBalancer.computeCost(cluster, Double.MAX_VALUE);
281        assertEquals(expectedCost, actualCost, 0);
282      }
283    }
284  }
285
286  @Test
287  public void testTableSkewCost() {
288    Configuration conf = HBaseConfiguration.create();
289    StochasticLoadBalancer.CostFunction
290        costFunction = new StochasticLoadBalancer.TableSkewCostFunction(conf);
291    for (int[] mockCluster : clusterStateMocks) {
292      BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
293      costFunction.init(cluster);
294      double cost = costFunction.cost();
295      assertTrue(cost >= 0);
296      assertTrue(cost <= 1.01);
297    }
298  }
299
300  @Test
301  public void testRegionLoadCost() {
302    List<BalancerRegionLoad> regionLoads = new ArrayList<>();
303    for (int i = 1; i < 5; i++) {
304      BalancerRegionLoad regionLoad = mock(BalancerRegionLoad.class);
305      when(regionLoad.getReadRequestsCount()).thenReturn(new Long(i));
306      when(regionLoad.getStorefileSizeMB()).thenReturn(i);
307      regionLoads.add(regionLoad);
308    }
309
310    Configuration conf = HBaseConfiguration.create();
311    StochasticLoadBalancer.ReadRequestCostFunction readCostFunction =
312        new StochasticLoadBalancer.ReadRequestCostFunction(conf);
313    double rateResult = readCostFunction.getRegionLoadCost(regionLoads);
314    // read requests are treated as a rate so the average rate here is simply 1
315    assertEquals(1, rateResult, 0.01);
316
317    StochasticLoadBalancer.StoreFileCostFunction storeFileCostFunction =
318        new StochasticLoadBalancer.StoreFileCostFunction(conf);
319    double result = storeFileCostFunction.getRegionLoadCost(regionLoads);
320    // storefile size cost is simply an average of it's value over time
321    assertEquals(2.5, result, 0.01);
322  }
323
324  @Test
325  public void testCostFromArray() {
326    Configuration conf = HBaseConfiguration.create();
327    StochasticLoadBalancer.CostFromRegionLoadFunction
328        costFunction = new StochasticLoadBalancer.MemStoreSizeCostFunction(conf);
329    costFunction.init(mockCluster(new int[]{0, 0, 0, 0, 1}));
330
331    double[] statOne = new double[100];
332    for (int i =0; i < 100; i++) {
333      statOne[i] = 10;
334    }
335    assertEquals(0, costFunction.costFromArray(statOne), 0.01);
336
337    double[] statTwo= new double[101];
338    for (int i =0; i < 100; i++) {
339      statTwo[i] = 0;
340    }
341    statTwo[100] = 100;
342    assertEquals(1, costFunction.costFromArray(statTwo), 0.01);
343
344    double[] statThree = new double[200];
345    for (int i =0; i < 100; i++) {
346      statThree[i] = (0);
347      statThree[i+100] = 100;
348    }
349    assertEquals(0.5, costFunction.costFromArray(statThree), 0.01);
350  }
351
352  @Test
353  public void testLosingRs() throws Exception {
354    int numNodes = 3;
355    int numRegions = 20;
356    int numRegionsPerServer = 3; //all servers except one
357    int replication = 1;
358    int numTables = 2;
359
360    Map<ServerName, List<RegionInfo>> serverMap =
361        createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
362    List<ServerAndLoad> list = convertToList(serverMap);
363
364
365    List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
366    assertNotNull(plans);
367
368    // Apply the plan to the mock cluster.
369    List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
370
371    assertClusterAsBalanced(balancedCluster);
372
373    ServerName sn = serverMap.keySet().toArray(new ServerName[serverMap.size()])[0];
374
375    ServerName deadSn = ServerName.valueOf(sn.getHostname(), sn.getPort(), sn.getStartcode() - 100);
376
377    serverMap.put(deadSn, new ArrayList<>(0));
378
379    plans = loadBalancer.balanceCluster(serverMap);
380    assertNull(plans);
381  }
382
383  // This mock allows us to test the LocalityCostFunction
384  private class MockCluster extends BaseLoadBalancer.Cluster {
385
386    private int[][] localities = null;   // [region][server] = percent of blocks
387
388    public MockCluster(int[][] regions) {
389
390      // regions[0] is an array where index = serverIndex an value = number of regions
391      super(mockClusterServers(regions[0], 1), null, null, null);
392
393      localities = new int[regions.length - 1][];
394      for (int i = 1; i < regions.length; i++) {
395        int regionIndex = i - 1;
396        localities[regionIndex] = new int[regions[i].length - 1];
397        regionIndexToServerIndex[regionIndex] = regions[i][0];
398        for (int j = 1; j < regions[i].length; j++) {
399          int serverIndex = j - 1;
400          localities[regionIndex][serverIndex] = regions[i][j] > 100 ? regions[i][j] % 100 : regions[i][j];
401        }
402      }
403    }
404
405    @Override
406    float getLocalityOfRegion(int region, int server) {
407      // convert the locality percentage to a fraction
408      return localities[region][server] / 100.0f;
409    }
410
411    @Override
412    public int getRegionSizeMB(int region) {
413      return 1;
414    }
415  }
416}