View Javadoc

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.master.balancer;
19  
20  import static org.junit.Assert.assertEquals;
21  import static org.junit.Assert.assertNotNull;
22  import static org.junit.Assert.assertNull;
23  import static org.junit.Assert.assertTrue;
24  import static org.mockito.Mockito.mock;
25  import static org.mockito.Mockito.when;
26  
27  import java.util.ArrayList;
28  import java.util.Arrays;
29  import java.util.HashMap;
30  import java.util.Iterator;
31  import java.util.List;
32  import java.util.Map;
33  import java.util.Map.Entry;
34  import java.util.Queue;
35  import java.util.TreeMap;
36  
37  import org.apache.commons.logging.Log;
38  import org.apache.commons.logging.LogFactory;
39  import org.apache.hadoop.conf.Configuration;
40  import org.apache.hadoop.hbase.ClusterStatus;
41  import org.apache.hadoop.hbase.HBaseConfiguration;
42  import org.apache.hadoop.hbase.HRegionInfo;
43  import org.apache.hadoop.hbase.RegionLoad;
44  import org.apache.hadoop.hbase.ServerLoad;
45  import org.apache.hadoop.hbase.ServerName;
46  import org.apache.hadoop.hbase.client.RegionReplicaUtil;
47  import org.apache.hadoop.hbase.master.RackManager;
48  import org.apache.hadoop.hbase.master.RegionPlan;
49  import org.apache.hadoop.hbase.master.balancer.BaseLoadBalancer.Cluster;
50  import org.apache.hadoop.hbase.testclassification.FlakeyTests;
51  import org.apache.hadoop.hbase.testclassification.MediumTests;
52  import org.apache.hadoop.hbase.util.Bytes;
53  import org.junit.Test;
54  import org.junit.Ignore;
55  import org.junit.experimental.categories.Category;
56  
57  @Category({FlakeyTests.class, MediumTests.class})
58  public class TestStochasticLoadBalancer extends BalancerTestBase {
59    public static final String REGION_KEY = "testRegion";
60    private static final Log LOG = LogFactory.getLog(TestStochasticLoadBalancer.class);
61  
62    @Test
63    public void testKeepRegionLoad() throws Exception {
64  
65      ServerName sn = ServerName.valueOf("test:8080", 100);
66      int numClusterStatusToAdd = 20000;
67      for (int i = 0; i < numClusterStatusToAdd; i++) {
68        ServerLoad sl = mock(ServerLoad.class);
69  
70        RegionLoad rl = mock(RegionLoad.class);
71        when(rl.getStores()).thenReturn(i);
72  
73        Map<byte[], RegionLoad> regionLoadMap =
74            new TreeMap<byte[], RegionLoad>(Bytes.BYTES_COMPARATOR);
75        regionLoadMap.put(Bytes.toBytes(REGION_KEY), rl);
76        when(sl.getRegionsLoad()).thenReturn(regionLoadMap);
77  
78        ClusterStatus clusterStatus = mock(ClusterStatus.class);
79        when(clusterStatus.getServers()).thenReturn(Arrays.asList(sn));
80        when(clusterStatus.getLoad(sn)).thenReturn(sl);
81  
82        loadBalancer.setClusterStatus(clusterStatus);
83      }
84      assertTrue(loadBalancer.loads.get(REGION_KEY) != null);
85      assertTrue(loadBalancer.loads.get(REGION_KEY).size() == 15);
86  
87      Queue<RegionLoad> loads = loadBalancer.loads.get(REGION_KEY);
88      int i = 0;
89      while(loads.size() > 0) {
90        RegionLoad rl = loads.remove();
91        assertEquals(i + (numClusterStatusToAdd - 15), rl.getStores());
92        i ++;
93      }
94    }
95  
96    /**
97     * Test the load balancing algorithm.
98     *
99     * Invariant is that all servers should be hosting either floor(average) or
100    * ceiling(average)
101    *
102    * @throws Exception
103    */
104   @Test
105   public void testBalanceCluster() throws Exception {
106 
107     for (int[] mockCluster : clusterStateMocks) {
108       Map<ServerName, List<HRegionInfo>> servers = mockClusterServers(mockCluster);
109       List<ServerAndLoad> list = convertToList(servers);
110       LOG.info("Mock Cluster : " + printMock(list) + " " + printStats(list));
111       List<RegionPlan> plans = loadBalancer.balanceCluster(servers);
112       List<ServerAndLoad> balancedCluster = reconcile(list, plans, servers);
113       LOG.info("Mock Balance : " + printMock(balancedCluster));
114       assertClusterAsBalanced(balancedCluster);
115       List<RegionPlan> secondPlans =  loadBalancer.balanceCluster(servers);
116       assertNull(secondPlans);
117       for (Map.Entry<ServerName, List<HRegionInfo>> entry : servers.entrySet()) {
118         returnRegions(entry.getValue());
119         returnServer(entry.getKey());
120       }
121     }
122 
123   }
124 
125   @Test
126   public void testSkewCost() {
127     Configuration conf = HBaseConfiguration.create();
128     StochasticLoadBalancer.CostFunction
129         costFunction = new StochasticLoadBalancer.RegionCountSkewCostFunction(conf);
130     for (int[] mockCluster : clusterStateMocks) {
131       costFunction.init(mockCluster(mockCluster));
132       double cost = costFunction.cost();
133       assertTrue(cost >= 0);
134       assertTrue(cost <= 1.01);
135     }
136 
137     costFunction.init(mockCluster(new int[]{0, 0, 0, 0, 1}));
138     assertEquals(0,costFunction.cost(), 0.01);
139     costFunction.init(mockCluster(new int[]{0, 0, 0, 1, 1}));
140     assertEquals(0, costFunction.cost(), 0.01);
141     costFunction.init(mockCluster(new int[]{0, 0, 1, 1, 1}));
142     assertEquals(0, costFunction.cost(), 0.01);
143     costFunction.init(mockCluster(new int[]{0, 1, 1, 1, 1}));
144     assertEquals(0, costFunction.cost(), 0.01);
145     costFunction.init(mockCluster(new int[]{1, 1, 1, 1, 1}));
146     assertEquals(0, costFunction.cost(), 0.01);
147     costFunction.init(mockCluster(new int[]{10000, 0, 0, 0, 0}));
148     assertEquals(1, costFunction.cost(), 0.01);
149   }
150 
151   @Test
152   public void testTableSkewCost() {
153     Configuration conf = HBaseConfiguration.create();
154     StochasticLoadBalancer.CostFunction
155         costFunction = new StochasticLoadBalancer.TableSkewCostFunction(conf);
156     for (int[] mockCluster : clusterStateMocks) {
157       BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
158       costFunction.init(cluster);
159       double cost = costFunction.cost();
160       assertTrue(cost >= 0);
161       assertTrue(cost <= 1.01);
162     }
163   }
164 
165   @Test
166   public void testCostFromArray() {
167     Configuration conf = HBaseConfiguration.create();
168     StochasticLoadBalancer.CostFromRegionLoadFunction
169         costFunction = new StochasticLoadBalancer.MemstoreSizeCostFunction(conf);
170     costFunction.init(mockCluster(new int[]{0, 0, 0, 0, 1}));
171 
172     double[] statOne = new double[100];
173     for (int i =0; i < 100; i++) {
174       statOne[i] = 10;
175     }
176     assertEquals(0, costFunction.costFromArray(statOne), 0.01);
177 
178     double[] statTwo= new double[101];
179     for (int i =0; i < 100; i++) {
180       statTwo[i] = 0;
181     }
182     statTwo[100] = 100;
183     assertEquals(1, costFunction.costFromArray(statTwo), 0.01);
184 
185     double[] statThree = new double[200];
186     for (int i =0; i < 100; i++) {
187       statThree[i] = (0);
188       statThree[i+100] = 100;
189     }
190     assertEquals(0.5, costFunction.costFromArray(statThree), 0.01);
191   }
192 
193   @Test(timeout =  60000)
194   public void testLosingRs() throws Exception {
195     int numNodes = 3;
196     int numRegions = 20;
197     int numRegionsPerServer = 3; //all servers except one
198     int replication = 1;
199     int numTables = 2;
200 
201     Map<ServerName, List<HRegionInfo>> serverMap =
202         createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
203     List<ServerAndLoad> list = convertToList(serverMap);
204 
205 
206     List<RegionPlan> plans = loadBalancer.balanceCluster(serverMap);
207     assertNotNull(plans);
208 
209     // Apply the plan to the mock cluster.
210     List<ServerAndLoad> balancedCluster = reconcile(list, plans, serverMap);
211 
212     assertClusterAsBalanced(balancedCluster);
213 
214     ServerName sn = serverMap.keySet().toArray(new ServerName[serverMap.size()])[0];
215 
216     ServerName deadSn = ServerName.valueOf(sn.getHostname(), sn.getPort(), sn.getStartcode() - 100);
217 
218     serverMap.put(deadSn, new ArrayList<HRegionInfo>(0));
219 
220     plans = loadBalancer.balanceCluster(serverMap);
221     assertNull(plans);
222   }
223 
224   @Test
225   public void testReplicaCost() {
226     Configuration conf = HBaseConfiguration.create();
227     StochasticLoadBalancer.CostFunction
228         costFunction = new StochasticLoadBalancer.RegionReplicaHostCostFunction(conf);
229     for (int[] mockCluster : clusterStateMocks) {
230       BaseLoadBalancer.Cluster cluster = mockCluster(mockCluster);
231       costFunction.init(cluster);
232       double cost = costFunction.cost();
233       assertTrue(cost >= 0);
234       assertTrue(cost <= 1.01);
235     }
236   }
237 
238   @Test
239   public void testReplicaCostForReplicas() {
240     Configuration conf = HBaseConfiguration.create();
241     StochasticLoadBalancer.CostFunction
242         costFunction = new StochasticLoadBalancer.RegionReplicaHostCostFunction(conf);
243 
244     int [] servers = new int[] {3,3,3,3,3};
245     TreeMap<ServerName, List<HRegionInfo>> clusterState = mockClusterServers(servers);
246 
247     BaseLoadBalancer.Cluster cluster;
248 
249     cluster = new BaseLoadBalancer.Cluster(clusterState, null, null, null);
250     costFunction.init(cluster);
251     double costWithoutReplicas = costFunction.cost();
252     assertEquals(0, costWithoutReplicas, 0);
253 
254     // replicate the region from first server to the last server
255     HRegionInfo replica1 = RegionReplicaUtil.getRegionInfoForReplica(
256       clusterState.firstEntry().getValue().get(0),1);
257     clusterState.lastEntry().getValue().add(replica1);
258 
259     cluster = new BaseLoadBalancer.Cluster(clusterState, null, null, null);
260     costFunction.init(cluster);
261     double costWith1ReplicaDifferentServer = costFunction.cost();
262 
263     assertEquals(0, costWith1ReplicaDifferentServer, 0);
264 
265     // add a third replica to the last server
266     HRegionInfo replica2 = RegionReplicaUtil.getRegionInfoForReplica(replica1, 2);
267     clusterState.lastEntry().getValue().add(replica2);
268 
269     cluster = new BaseLoadBalancer.Cluster(clusterState, null, null, null);
270     costFunction.init(cluster);
271     double costWith1ReplicaSameServer = costFunction.cost();
272 
273     assertTrue(costWith1ReplicaDifferentServer < costWith1ReplicaSameServer);
274 
275     // test with replication = 4 for following:
276 
277     HRegionInfo replica3;
278     Iterator<Entry<ServerName, List<HRegionInfo>>> it;
279     Entry<ServerName, List<HRegionInfo>> entry;
280 
281     clusterState = mockClusterServers(servers);
282     it = clusterState.entrySet().iterator();
283     entry = it.next(); //first server
284     HRegionInfo hri = entry.getValue().get(0);
285     replica1 = RegionReplicaUtil.getRegionInfoForReplica(hri, 1);
286     replica2 = RegionReplicaUtil.getRegionInfoForReplica(hri, 2);
287     replica3 = RegionReplicaUtil.getRegionInfoForReplica(hri, 3);
288     entry.getValue().add(replica1);
289     entry.getValue().add(replica2);
290     it.next().getValue().add(replica3); //2nd server
291 
292     cluster = new BaseLoadBalancer.Cluster(clusterState, null, null, null);
293     costFunction.init(cluster);
294     double costWith3ReplicasSameServer = costFunction.cost();
295 
296     clusterState = mockClusterServers(servers);
297     hri = clusterState.firstEntry().getValue().get(0);
298     replica1 = RegionReplicaUtil.getRegionInfoForReplica(hri, 1);
299     replica2 = RegionReplicaUtil.getRegionInfoForReplica(hri, 2);
300     replica3 = RegionReplicaUtil.getRegionInfoForReplica(hri, 3);
301 
302     clusterState.firstEntry().getValue().add(replica1);
303     clusterState.lastEntry().getValue().add(replica2);
304     clusterState.lastEntry().getValue().add(replica3);
305 
306     cluster = new BaseLoadBalancer.Cluster(clusterState, null, null, null);
307     costFunction.init(cluster);
308     double costWith2ReplicasOnTwoServers = costFunction.cost();
309 
310     assertTrue(costWith2ReplicasOnTwoServers < costWith3ReplicasSameServer);
311   }
312 
313   @Test
314   public void testNeedsBalanceForColocatedReplicas() {
315     // check for the case where there are two hosts and with one rack, and where
316     // both the replicas are hosted on the same server
317     List<HRegionInfo> regions = randomRegions(1);
318     ServerName s1 = ServerName.valueOf("host1", 1000, 11111);
319     ServerName s2 = ServerName.valueOf("host11", 1000, 11111);
320     Map<ServerName, List<HRegionInfo>> map = new HashMap<ServerName, List<HRegionInfo>>();
321     map.put(s1, regions);
322     regions.add(RegionReplicaUtil.getRegionInfoForReplica(regions.get(0), 1));
323     // until the step above s1 holds two replicas of a region
324     regions = randomRegions(1);
325     map.put(s2, regions);
326     assertTrue(loadBalancer.needsBalance(new Cluster(map, null, null, null)));
327     // check for the case where there are two hosts on the same rack and there are two racks
328     // and both the replicas are on the same rack
329     map.clear();
330     regions = randomRegions(1);
331     List<HRegionInfo> regionsOnS2 = new ArrayList<HRegionInfo>(1);
332     regionsOnS2.add(RegionReplicaUtil.getRegionInfoForReplica(regions.get(0), 1));
333     map.put(s1, regions);
334     map.put(s2, regionsOnS2);
335     // add another server so that the cluster has some host on another rack
336     map.put(ServerName.valueOf("host2", 1000, 11111), randomRegions(1));
337     assertTrue(loadBalancer.needsBalance(new Cluster(map, null, null,
338         new ForTestRackManagerOne())));
339   }
340 
341   @Test (timeout = 60000)
342   public void testSmallCluster() {
343     int numNodes = 10;
344     int numRegions = 1000;
345     int numRegionsPerServer = 40; //all servers except one
346     int replication = 1;
347     int numTables = 10;
348     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
349   }
350 
351   @Test (timeout = 60000)
352   public void testSmallCluster2() {
353     int numNodes = 20;
354     int numRegions = 2000;
355     int numRegionsPerServer = 40; //all servers except one
356     int replication = 1;
357     int numTables = 10;
358     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
359   }
360 
361   @Test (timeout = 60000)
362   public void testSmallCluster3() {
363     int numNodes = 20;
364     int numRegions = 2000;
365     int numRegionsPerServer = 1; // all servers except one
366     int replication = 1;
367     int numTables = 10;
368     /* fails because of max moves */
369     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, false, false);
370   }
371 
372   @Test (timeout = 800000)
373   public void testMidCluster() {
374     int numNodes = 100;
375     int numRegions = 10000;
376     int numRegionsPerServer = 60; // all servers except one
377     int replication = 1;
378     int numTables = 40;
379     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
380   }
381 
382   @Test (timeout = 800000)
383   public void testMidCluster2() {
384     int numNodes = 200;
385     int numRegions = 100000;
386     int numRegionsPerServer = 40; // all servers except one
387     int replication = 1;
388     int numTables = 400;
389     testWithCluster(numNodes,
390         numRegions,
391         numRegionsPerServer,
392         replication,
393         numTables,
394         false, /* num large num regions means may not always get to best balance with one run */
395         false);
396   }
397 
398 
399   @Test (timeout = 800000)
400   public void testMidCluster3() {
401     int numNodes = 100;
402     int numRegions = 2000;
403     int numRegionsPerServer = 9; // all servers except one
404     int replication = 1;
405     int numTables = 110;
406     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
407     // TODO(eclark): Make sure that the tables are well distributed.
408   }
409 
410   @Test
411   public void testLargeCluster() {
412     int numNodes = 1000;
413     int numRegions = 100000; //100 regions per RS
414     int numRegionsPerServer = 80; //all servers except one
415     int numTables = 100;
416     int replication = 1;
417     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
418   }
419 
420   @Test (timeout = 800000)
421   public void testRegionReplicasOnSmallCluster() {
422     int numNodes = 10;
423     int numRegions = 1000;
424     int replication = 3; // 3 replicas per region
425     int numRegionsPerServer = 80; //all regions are mostly balanced
426     int numTables = 10;
427     testWithCluster(numNodes, numRegions, numRegionsPerServer, replication, numTables, true, true);
428   }
429 
430   // This test failed on 1.2 branch
431   @Ignore @Test (timeout = 800000)
432   public void testRegionReplicationOnMidClusterSameHosts() {
433     conf.setLong(StochasticLoadBalancer.MAX_STEPS_KEY, 2000000L);
434     conf.setLong("hbase.master.balancer.stochastic.maxRunningTime", 90 * 1000); // 90 sec
435     conf.setFloat("hbase.master.balancer.stochastic.maxMovePercent", 1.0f);
436     loadBalancer.setConf(conf);
437     int numHosts = 100;
438     int numRegions = 100 * 100;
439     int replication = 3; // 3 replicas per region
440     int numRegionsPerServer = 5;
441     int numTables = 10;
442     Map<ServerName, List<HRegionInfo>> serverMap =
443         createServerMap(numHosts, numRegions, numRegionsPerServer, replication, numTables);
444     int numNodesPerHost = 4;
445 
446     // create a new map with 4 RS per host.
447     Map<ServerName, List<HRegionInfo>> newServerMap = new TreeMap<ServerName, List<HRegionInfo>>(serverMap);
448     for (Map.Entry<ServerName, List<HRegionInfo>> entry : serverMap.entrySet()) {
449       for (int i=1; i < numNodesPerHost; i++) {
450         ServerName s1 = entry.getKey();
451         ServerName s2 = ServerName.valueOf(s1.getHostname(), s1.getPort() + i, 1); // create an RS for the same host
452         newServerMap.put(s2, new ArrayList<HRegionInfo>());
453       }
454     }
455 
456     testWithCluster(newServerMap, null, true, true);
457   }
458 
459   private static class ForTestRackManager extends RackManager {
460     int numRacks;
461     public ForTestRackManager(int numRacks) {
462       this.numRacks = numRacks;
463     }
464     @Override
465     public String getRack(ServerName server) {
466       return "rack_" + (server.hashCode() % numRacks);
467     }
468   }
469 
470   private static class ForTestRackManagerOne extends RackManager {
471   @Override
472     public String getRack(ServerName server) {
473       return server.getHostname().endsWith("1") ? "rack1" : "rack2";
474     }
475   }
476 
477   @Test (timeout = 800000)
478   public void testRegionReplicationOnMidClusterWithRacks() {
479     conf.setLong(StochasticLoadBalancer.MAX_STEPS_KEY, 10000000L);
480     conf.setFloat("hbase.master.balancer.stochastic.maxMovePercent", 1.0f);
481     conf.setLong("hbase.master.balancer.stochastic.maxRunningTime", 120 * 1000); // 120 sec
482     loadBalancer.setConf(conf);
483     int numNodes = 30;
484     int numRegions = numNodes * 30;
485     int replication = 3; // 3 replicas per region
486     int numRegionsPerServer = 28;
487     int numTables = 10;
488     int numRacks = 4; // all replicas should be on a different rack
489     Map<ServerName, List<HRegionInfo>> serverMap =
490         createServerMap(numNodes, numRegions, numRegionsPerServer, replication, numTables);
491     RackManager rm = new ForTestRackManager(numRacks);
492 
493     testWithCluster(serverMap, rm, false, true);
494   }
495 
496 }