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