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.assertTrue;
021
022import java.util.ArrayDeque;
023import java.util.ArrayList;
024import java.util.HashMap;
025import java.util.HashSet;
026import java.util.LinkedHashMap;
027import java.util.List;
028import java.util.Map;
029import java.util.NavigableSet;
030import java.util.Queue;
031import java.util.Random;
032import java.util.Set;
033import java.util.TreeMap;
034import java.util.TreeSet;
035import java.util.concurrent.ThreadLocalRandom;
036import java.util.stream.Collectors;
037import java.util.stream.Stream;
038import org.apache.hadoop.conf.Configuration;
039import org.apache.hadoop.hbase.ServerName;
040import org.apache.hadoop.hbase.TableName;
041import org.apache.hadoop.hbase.client.RegionInfo;
042import org.apache.hadoop.hbase.client.RegionInfoBuilder;
043import org.apache.hadoop.hbase.client.RegionReplicaUtil;
044import org.apache.hadoop.hbase.master.RackManager;
045import org.apache.hadoop.hbase.master.RegionPlan;
046import org.apache.hadoop.hbase.util.Bytes;
047import org.apache.hadoop.net.DNSToSwitchMapping;
048import org.junit.Assert;
049import org.slf4j.Logger;
050import org.slf4j.LoggerFactory;
051
052/**
053 * Class used to be the base of unit tests on load balancers. It gives helper methods to create maps
054 * of {@link ServerName} to lists of {@link RegionInfo} and to check list of region plans.
055 */
056public class BalancerTestBase {
057  private static final Logger LOG = LoggerFactory.getLogger(BalancerTestBase.class);
058  static int regionId = 0;
059  protected static Configuration conf;
060
061  protected int[] largeCluster = new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
062    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
063    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
064    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
065    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
066    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
067    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
068    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
069    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
070    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
071    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
072    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
073    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 56 };
074
075  // int[testnum][servernumber] -> numregions
076  protected int[][] clusterStateMocks = new int[][] {
077    // 1 node
078    new int[] { 0 }, new int[] { 1 }, new int[] { 10 },
079    // 2 node
080    new int[] { 0, 0 }, new int[] { 2, 0 }, new int[] { 2, 1 }, new int[] { 2, 2 },
081    new int[] { 2, 3 }, new int[] { 2, 4 }, new int[] { 1, 1 }, new int[] { 0, 1 },
082    new int[] { 10, 1 }, new int[] { 514, 1432 }, new int[] { 48, 53 },
083    // 3 node
084    new int[] { 0, 1, 2 }, new int[] { 1, 2, 3 }, new int[] { 0, 2, 2 }, new int[] { 0, 3, 0 },
085    new int[] { 0, 4, 0 }, new int[] { 20, 20, 0 },
086    // 4 node
087    new int[] { 0, 1, 2, 3 }, new int[] { 4, 0, 0, 0 }, new int[] { 5, 0, 0, 0 },
088    new int[] { 6, 6, 0, 0 }, new int[] { 6, 2, 0, 0 }, new int[] { 6, 1, 0, 0 },
089    new int[] { 6, 0, 0, 0 }, new int[] { 4, 4, 4, 7 }, new int[] { 4, 4, 4, 8 },
090    new int[] { 0, 0, 0, 7 },
091    // 5 node
092    new int[] { 1, 1, 1, 1, 4 },
093    // 6 nodes
094    new int[] { 1500, 500, 500, 500, 10, 0 }, new int[] { 1500, 500, 500, 500, 500, 0 },
095    // more nodes
096    new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
097    new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 10 }, new int[] { 6, 6, 5, 6, 6, 6, 6, 6, 6, 1 },
098    new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 54 }, new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 55 },
099    new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 56 }, new int[] { 0, 0, 0, 0, 0, 0, 0, 0, 0, 16 },
100    new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 8 }, new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 9 },
101    new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 10 }, new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 123 },
102    new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 155 }, new int[] { 10, 7, 12, 8, 11, 10, 9, 14 },
103    new int[] { 13, 14, 6, 10, 10, 10, 8, 10 }, new int[] { 130, 14, 60, 10, 100, 10, 80, 10 },
104    new int[] { 130, 140, 60, 100, 100, 100, 80, 100 }, new int[] { 0, 5, 5, 5, 5 }, largeCluster,
105
106  };
107
108  // int[testnum][servernumber] -> numregions
109  protected int[][] clusterStateMocksWithNoSlop = new int[][] {
110    // 1 node
111    new int[] { 0 }, new int[] { 1 }, new int[] { 10 },
112    // 2 node
113    new int[] { 0, 0 }, new int[] { 2, 1 }, new int[] { 2, 2 }, new int[] { 2, 3 },
114    new int[] { 1, 1 }, new int[] { 80, 120 }, new int[] { 1428, 1432 },
115    // more nodes
116    new int[] { 100, 90, 120, 90, 110, 100, 90, 120 }, };
117
118  // int[testnum][servernumber] -> numregions
119  protected int[][] clusterStateMocksWithSlop = new int[][] {
120    // 2 node
121    new int[] { 1, 4 }, new int[] { 10, 20 }, new int[] { 80, 123 },
122    // more nodes
123    new int[] { 100, 100, 100, 100, 100, 100, 100, 100, 100, 200 },
124    new int[] { 10, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
125      5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
126      5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
127      5, 5, 5, 5, 5, 5, 5, 5, 5, 5 }, };
128
129  // This class is introduced because IP to rack resolution can be lengthy.
130  public static class MockMapping implements DNSToSwitchMapping {
131    public MockMapping(Configuration conf) {
132    }
133
134    @Override
135    public List<String> resolve(List<String> names) {
136      return Stream.generate(() -> "rack").limit(names.size()).collect(Collectors.toList());
137    }
138
139    @Override
140    public void reloadCachedMappings() {
141    }
142
143    @Override
144    public void reloadCachedMappings(List<String> arg0) {
145    }
146  }
147
148  /**
149   * Invariant is that all servers have between floor(avg) and ceiling(avg) number of regions.
150   */
151  public void assertClusterAsBalanced(List<ServerAndLoad> servers) {
152    int numServers = servers.size();
153    int numRegions = 0;
154    int maxRegions = 0;
155    int minRegions = Integer.MAX_VALUE;
156    for (ServerAndLoad server : servers) {
157      int nr = server.getLoad();
158      if (nr > maxRegions) {
159        maxRegions = nr;
160      }
161      if (nr < minRegions) {
162        minRegions = nr;
163      }
164      numRegions += nr;
165    }
166    if (maxRegions - minRegions < 2) {
167      // less than 2 between max and min, can't balance
168      return;
169    }
170    int min = numRegions / numServers;
171    int max = numRegions % numServers == 0 ? min : min + 1;
172
173    for (ServerAndLoad server : servers) {
174      assertTrue("All servers should have a positive load. " + server, server.getLoad() >= 0);
175      assertTrue("All servers should have load no more than " + max + ". " + server,
176        server.getLoad() <= max);
177      assertTrue("All servers should have load no less than " + min + ". " + server,
178        server.getLoad() >= min);
179    }
180  }
181
182  /**
183   * Invariant is that all servers have between acceptable range number of regions.
184   */
185  public boolean assertClusterOverallAsBalanced(List<ServerAndLoad> servers, int tablenum) {
186    int numServers = servers.size();
187    int numRegions = 0;
188    int maxRegions = 0;
189    int minRegions = Integer.MAX_VALUE;
190    for (ServerAndLoad server : servers) {
191      int nr = server.getLoad();
192      if (nr > maxRegions) {
193        maxRegions = nr;
194      }
195      if (nr < minRegions) {
196        minRegions = nr;
197      }
198      numRegions += nr;
199    }
200    if (maxRegions - minRegions < 2) {
201      // less than 2 between max and min, can't balance
202      return true;
203    }
204    int min = numRegions / numServers;
205    int max = numRegions % numServers == 0 ? min : min + 1;
206
207    for (ServerAndLoad server : servers) {
208      // The '5' in below is arbitrary.
209      if (
210        server.getLoad() < 0 || server.getLoad() > max + (tablenum / 2 + 5)
211          || server.getLoad() < (min - tablenum / 2 - 5)
212      ) {
213        LOG.warn("server={}, load={}, max={}, tablenum={}, min={}", server.getServerName(),
214          server.getLoad(), max, tablenum, min);
215        return false;
216      }
217    }
218    return true;
219  }
220
221  /**
222   * Checks whether region replicas are not hosted on the same host.
223   */
224  public void assertRegionReplicaPlacement(Map<ServerName, List<RegionInfo>> serverMap,
225    RackManager rackManager) {
226    TreeMap<String, Set<RegionInfo>> regionsPerHost = new TreeMap<>();
227    TreeMap<String, Set<RegionInfo>> regionsPerRack = new TreeMap<>();
228
229    for (Map.Entry<ServerName, List<RegionInfo>> entry : serverMap.entrySet()) {
230      String hostname = entry.getKey().getHostname();
231      Set<RegionInfo> infos = regionsPerHost.get(hostname);
232      if (infos == null) {
233        infos = new HashSet<>();
234        regionsPerHost.put(hostname, infos);
235      }
236
237      for (RegionInfo info : entry.getValue()) {
238        RegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
239        if (!infos.add(primaryInfo)) {
240          Assert.fail("Two or more region replicas are hosted on the same host after balance");
241        }
242      }
243    }
244
245    if (rackManager == null) {
246      return;
247    }
248
249    for (Map.Entry<ServerName, List<RegionInfo>> entry : serverMap.entrySet()) {
250      String rack = rackManager.getRack(entry.getKey());
251      Set<RegionInfo> infos = regionsPerRack.get(rack);
252      if (infos == null) {
253        infos = new HashSet<>();
254        regionsPerRack.put(rack, infos);
255      }
256
257      for (RegionInfo info : entry.getValue()) {
258        RegionInfo primaryInfo = RegionReplicaUtil.getRegionInfoForDefaultReplica(info);
259        if (!infos.add(primaryInfo)) {
260          Assert.fail("Two or more region replicas are hosted on the same rack after balance");
261        }
262      }
263    }
264  }
265
266  protected String printStats(List<ServerAndLoad> servers) {
267    int numServers = servers.size();
268    int totalRegions = 0;
269    for (ServerAndLoad server : servers) {
270      totalRegions += server.getLoad();
271    }
272    float average = (float) totalRegions / numServers;
273    int max = (int) Math.ceil(average);
274    int min = (int) Math.floor(average);
275    return "[srvr=" + numServers + " rgns=" + totalRegions + " avg=" + average + " max=" + max
276      + " min=" + min + "]";
277  }
278
279  protected List<ServerAndLoad> convertToList(final Map<ServerName, List<RegionInfo>> servers) {
280    List<ServerAndLoad> list = new ArrayList<>(servers.size());
281    for (Map.Entry<ServerName, List<RegionInfo>> e : servers.entrySet()) {
282      list.add(new ServerAndLoad(e.getKey(), e.getValue().size()));
283    }
284    return list;
285  }
286
287  protected String printMock(List<ServerAndLoad> balancedCluster) {
288    NavigableSet<ServerAndLoad> sorted = new TreeSet<>(balancedCluster);
289    ServerAndLoad[] arr = sorted.toArray(new ServerAndLoad[sorted.size()]);
290    StringBuilder sb = new StringBuilder(sorted.size() * 4 + 4);
291    sb.append("{ ");
292    for (int i = 0; i < arr.length; i++) {
293      if (i != 0) {
294        sb.append(" , ");
295      }
296      sb.append(arr[i].getServerName().getHostname());
297      sb.append(":");
298      sb.append(arr[i].getLoad());
299    }
300    sb.append(" }");
301    return sb.toString();
302  }
303
304  /**
305   * This assumes the RegionPlan HSI instances are the same ones in the map, so actually no need to
306   * even pass in the map, but I think it's clearer.
307   * @return a list of all added {@link ServerAndLoad} values.
308   */
309  protected List<ServerAndLoad> reconcile(List<ServerAndLoad> list, List<RegionPlan> plans,
310    Map<ServerName, List<RegionInfo>> servers) {
311    List<ServerAndLoad> result = new ArrayList<>(list.size());
312
313    Map<ServerName, ServerAndLoad> map = new HashMap<>(list.size());
314    for (ServerAndLoad sl : list) {
315      map.put(sl.getServerName(), sl);
316    }
317    if (plans != null) {
318      for (RegionPlan plan : plans) {
319        ServerName source = plan.getSource();
320
321        updateLoad(map, source, -1);
322        ServerName destination = plan.getDestination();
323        updateLoad(map, destination, +1);
324
325        servers.get(source).remove(plan.getRegionInfo());
326        servers.get(destination).add(plan.getRegionInfo());
327      }
328    }
329    result.clear();
330    result.addAll(map.values());
331    return result;
332  }
333
334  protected void updateLoad(final Map<ServerName, ServerAndLoad> map, final ServerName sn,
335    final int diff) {
336    ServerAndLoad sal = map.get(sn);
337    if (sal == null) sal = new ServerAndLoad(sn, 0);
338    sal = new ServerAndLoad(sn, sal.getLoad() + diff);
339    map.put(sn, sal);
340  }
341
342  protected TreeMap<ServerName, List<RegionInfo>> mockClusterServers(int[][] mockCluster) {
343    // dimension1: table, dimension2: regions per server
344    int numTables = mockCluster.length;
345    TreeMap<ServerName, List<RegionInfo>> servers = new TreeMap<>();
346    for (int i = 0; i < numTables; i++) {
347      TableName tableName = TableName.valueOf("table" + i);
348      for (int j = 0; j < mockCluster[i].length; j++) {
349        ServerName serverName = ServerName.valueOf("server" + j, 1000, -1);
350        int numRegions = mockCluster[i][j];
351        List<RegionInfo> regions = createRegions(numRegions, tableName);
352        servers.putIfAbsent(serverName, new ArrayList<>());
353        servers.get(serverName).addAll(regions);
354      }
355    }
356    return servers;
357  }
358
359  protected TreeMap<ServerName, List<RegionInfo>> mockClusterServers(int[] mockCluster) {
360    return mockClusterServers(mockCluster, -1);
361  }
362
363  protected BalancerClusterState mockCluster(int[] mockCluster) {
364    return new BalancerClusterState(mockClusterServers(mockCluster, -1), null, null, null);
365  }
366
367  protected TreeMap<ServerName, List<RegionInfo>> mockClusterServers(int[] mockCluster,
368    int numTables) {
369    int numServers = mockCluster.length;
370    TreeMap<ServerName, List<RegionInfo>> servers = new TreeMap<>();
371    for (int i = 0; i < numServers; i++) {
372      int numRegions = mockCluster[i];
373      ServerAndLoad sal = randomServer(0);
374      List<RegionInfo> regions = randomRegions(numRegions, numTables);
375      servers.put(sal.getServerName(), regions);
376    }
377    return servers;
378  }
379
380  protected Map<ServerName, List<RegionInfo>> mockClusterServersUnsorted(int[] mockCluster,
381    int numTables) {
382    int numServers = mockCluster.length;
383    Map<ServerName, List<RegionInfo>> servers = new LinkedHashMap<>();
384    for (int i = 0; i < numServers; i++) {
385      int numRegions = mockCluster[i];
386      ServerAndLoad sal = randomServer(0);
387      List<RegionInfo> regions = randomRegions(numRegions, numTables);
388      servers.put(sal.getServerName(), regions);
389    }
390    return servers;
391  }
392
393  protected TreeMap<ServerName, List<RegionInfo>> mockUniformClusterServers(int[] mockCluster) {
394    int numServers = mockCluster.length;
395    TreeMap<ServerName, List<RegionInfo>> servers = new TreeMap<>();
396    for (int i = 0; i < numServers; i++) {
397      int numRegions = mockCluster[i];
398      ServerAndLoad sal = randomServer(0);
399      List<RegionInfo> regions = uniformRegions(numRegions);
400      servers.put(sal.getServerName(), regions);
401    }
402    return servers;
403  }
404
405  protected HashMap<TableName, TreeMap<ServerName, List<RegionInfo>>>
406    mockClusterServersWithTables(Map<ServerName, List<RegionInfo>> clusterServers) {
407    HashMap<TableName, TreeMap<ServerName, List<RegionInfo>>> result = new HashMap<>();
408    for (Map.Entry<ServerName, List<RegionInfo>> entry : clusterServers.entrySet()) {
409      ServerName sal = entry.getKey();
410      List<RegionInfo> regions = entry.getValue();
411      for (RegionInfo hri : regions) {
412        TreeMap<ServerName, List<RegionInfo>> servers = result.get(hri.getTable());
413        if (servers == null) {
414          servers = new TreeMap<>();
415          result.put(hri.getTable(), servers);
416        }
417        List<RegionInfo> hrilist = servers.get(sal);
418        if (hrilist == null) {
419          hrilist = new ArrayList<>();
420          servers.put(sal, hrilist);
421        }
422        hrilist.add(hri);
423      }
424    }
425    for (Map.Entry<TableName, TreeMap<ServerName, List<RegionInfo>>> entry : result.entrySet()) {
426      for (ServerName srn : clusterServers.keySet()) {
427        if (!entry.getValue().containsKey(srn)) entry.getValue().put(srn, new ArrayList<>());
428      }
429    }
430    return result;
431  }
432
433  private Queue<RegionInfo> regionQueue = new ArrayDeque<>();
434
435  protected List<RegionInfo> randomRegions(int numRegions) {
436    return randomRegions(numRegions, -1);
437  }
438
439  protected List<RegionInfo> createRegions(int numRegions, TableName tableName) {
440    List<RegionInfo> regions = new ArrayList<>(numRegions);
441    byte[] start = new byte[16];
442    Bytes.random(start);
443    byte[] end = new byte[16];
444    Bytes.random(end);
445    for (int i = 0; i < numRegions; i++) {
446      Bytes.putInt(start, 0, numRegions << 1);
447      Bytes.putInt(end, 0, (numRegions << 1) + 1);
448      RegionInfo hri = RegionInfoBuilder.newBuilder(tableName).setStartKey(start).setEndKey(end)
449        .setSplit(false).build();
450      regions.add(hri);
451    }
452    return regions;
453  }
454
455  protected List<RegionInfo> randomRegions(int numRegions, int numTables) {
456    List<RegionInfo> regions = new ArrayList<>(numRegions);
457    byte[] start = new byte[16];
458    Bytes.random(start);
459    byte[] end = new byte[16];
460    Bytes.random(end);
461    for (int i = 0; i < numRegions; i++) {
462      if (!regionQueue.isEmpty()) {
463        regions.add(regionQueue.poll());
464        continue;
465      }
466      Bytes.putInt(start, 0, numRegions << 1);
467      Bytes.putInt(end, 0, (numRegions << 1) + 1);
468      TableName tableName = TableName
469        .valueOf("table" + (numTables > 0 ? ThreadLocalRandom.current().nextInt(numTables) : i));
470      RegionInfo hri = RegionInfoBuilder.newBuilder(tableName).setStartKey(start).setEndKey(end)
471        .setSplit(false).setRegionId(regionId++).build();
472      regions.add(hri);
473    }
474    return regions;
475  }
476
477  protected List<RegionInfo> uniformRegions(int numRegions) {
478    List<RegionInfo> regions = new ArrayList<>(numRegions);
479    byte[] start = new byte[16];
480    Bytes.random(start);
481    byte[] end = new byte[16];
482    Bytes.random(end);
483    for (int i = 0; i < numRegions; i++) {
484      Bytes.putInt(start, 0, numRegions << 1);
485      Bytes.putInt(end, 0, (numRegions << 1) + 1);
486      TableName tableName = TableName.valueOf("table" + i);
487      RegionInfo hri = RegionInfoBuilder.newBuilder(tableName).setStartKey(start).setEndKey(end)
488        .setSplit(false).build();
489      regions.add(hri);
490    }
491    return regions;
492  }
493
494  protected void returnRegions(List<RegionInfo> regions) {
495    regionQueue.addAll(regions);
496  }
497
498  private Queue<ServerName> serverQueue = new ArrayDeque<>();
499
500  protected ServerAndLoad randomServer(final int numRegionsPerServer) {
501    if (!this.serverQueue.isEmpty()) {
502      ServerName sn = this.serverQueue.poll();
503      return new ServerAndLoad(sn, numRegionsPerServer);
504    }
505    Random rand = ThreadLocalRandom.current();
506    String host = "srv" + rand.nextInt(Integer.MAX_VALUE);
507    int port = rand.nextInt(60000);
508    long startCode = rand.nextLong();
509    ServerName sn = ServerName.valueOf(host, port, startCode);
510    return new ServerAndLoad(sn, numRegionsPerServer);
511  }
512
513  protected List<ServerAndLoad> randomServers(int numServers, int numRegionsPerServer) {
514    List<ServerAndLoad> servers = new ArrayList<>(numServers);
515    for (int i = 0; i < numServers; i++) {
516      servers.add(randomServer(numRegionsPerServer));
517    }
518    return servers;
519  }
520
521  protected void returnServer(ServerName server) {
522    serverQueue.add(server);
523  }
524
525  protected void returnServers(List<ServerName> servers) {
526    this.serverQueue.addAll(servers);
527  }
528
529  protected Map<ServerName, List<RegionInfo>> createServerMap(int numNodes, int numRegions,
530    int numRegionsPerServer, int replication, int numTables) {
531    // construct a cluster of numNodes, having a total of numRegions. Each RS will hold
532    // numRegionsPerServer many regions except for the last one, which will host all the
533    // remaining regions
534    int[] cluster = new int[numNodes];
535    for (int i = 0; i < numNodes; i++) {
536      cluster[i] = numRegionsPerServer;
537    }
538    cluster[cluster.length - 1] = numRegions - ((cluster.length - 1) * numRegionsPerServer);
539    Map<ServerName, List<RegionInfo>> clusterState = mockClusterServers(cluster, numTables);
540    if (replication > 0) {
541      // replicate the regions to the same servers
542      for (List<RegionInfo> regions : clusterState.values()) {
543        int length = regions.size();
544        for (int i = 0; i < length; i++) {
545          for (int r = 1; r < replication; r++) {
546            regions.add(RegionReplicaUtil.getRegionInfoForReplica(regions.get(i), r));
547          }
548        }
549      }
550    }
551
552    return clusterState;
553  }
554}