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.assertNull;
022import static org.junit.Assert.assertTrue;
023import static org.mockito.Mockito.mock;
024import static org.mockito.Mockito.when;
025
026import java.util.ArrayList;
027import java.util.Collections;
028import java.util.HashMap;
029import java.util.LinkedHashMap;
030import java.util.List;
031import java.util.Map;
032import java.util.Set;
033import java.util.TreeMap;
034import java.util.TreeSet;
035import java.util.function.Predicate;
036import java.util.stream.Collectors;
037import org.apache.commons.lang3.ArrayUtils;
038import org.apache.hadoop.conf.Configuration;
039import org.apache.hadoop.hbase.HBaseClassTestRule;
040import org.apache.hadoop.hbase.HBaseConfiguration;
041import org.apache.hadoop.hbase.ServerMetrics;
042import org.apache.hadoop.hbase.ServerName;
043import org.apache.hadoop.hbase.TableName;
044import org.apache.hadoop.hbase.client.RegionInfo;
045import org.apache.hadoop.hbase.client.RegionInfoBuilder;
046import org.apache.hadoop.hbase.client.RegionReplicaUtil;
047import org.apache.hadoop.hbase.master.LoadBalancer;
048import org.apache.hadoop.hbase.master.RackManager;
049import org.apache.hadoop.hbase.master.RegionPlan;
050import org.apache.hadoop.hbase.testclassification.MasterTests;
051import org.apache.hadoop.hbase.testclassification.MediumTests;
052import org.apache.hadoop.hbase.util.Bytes;
053import org.apache.hadoop.net.DNSToSwitchMapping;
054import org.junit.BeforeClass;
055import org.junit.ClassRule;
056import org.junit.Rule;
057import org.junit.Test;
058import org.junit.experimental.categories.Category;
059import org.junit.rules.TestName;
060import org.slf4j.Logger;
061import org.slf4j.LoggerFactory;
062
063import org.apache.hbase.thirdparty.com.google.common.collect.Lists;
064
065@Category({ MasterTests.class, MediumTests.class })
066public class TestBaseLoadBalancer extends BalancerTestBase {
067
068  @ClassRule
069  public static final HBaseClassTestRule CLASS_RULE =
070    HBaseClassTestRule.forClass(TestBaseLoadBalancer.class);
071
072  private static LoadBalancer loadBalancer;
073  private static final Logger LOG = LoggerFactory.getLogger(TestBaseLoadBalancer.class);
074  private static final ServerName master = ServerName.valueOf("fake-master", 0, 1L);
075  private static RackManager rackManager;
076  private static final int NUM_SERVERS = 15;
077  private static ServerName[] servers = new ServerName[NUM_SERVERS];
078
079  int[][] regionsAndServersMocks = new int[][] {
080    // { num regions, num servers }
081    new int[] { 0, 0 }, new int[] { 0, 1 }, new int[] { 1, 1 }, new int[] { 2, 1 },
082    new int[] { 10, 1 }, new int[] { 1, 2 }, new int[] { 2, 2 }, new int[] { 3, 2 },
083    new int[] { 1, 3 }, new int[] { 2, 3 }, new int[] { 3, 3 }, new int[] { 25, 3 },
084    new int[] { 2, 10 }, new int[] { 2, 100 }, new int[] { 12, 10 }, new int[] { 12, 100 }, };
085
086  @Rule
087  public TestName name = new TestName();
088
089  @BeforeClass
090  public static void beforeAllTests() throws Exception {
091    Configuration conf = HBaseConfiguration.create();
092    conf.setClass("hbase.util.ip.to.rack.determiner", MockMapping.class, DNSToSwitchMapping.class);
093    loadBalancer = new MockBalancer();
094    loadBalancer.setClusterInfoProvider(new DummyClusterInfoProvider(conf));
095
096    // Set up the rack topologies (5 machines per rack)
097    rackManager = mock(RackManager.class);
098    for (int i = 0; i < NUM_SERVERS; i++) {
099      servers[i] = ServerName.valueOf("foo" + i + ":1234", -1);
100      if (i < 5) {
101        when(rackManager.getRack(servers[i])).thenReturn("rack1");
102      }
103      if (i >= 5 && i < 10) {
104        when(rackManager.getRack(servers[i])).thenReturn("rack2");
105      }
106      if (i >= 10) {
107        when(rackManager.getRack(servers[i])).thenReturn("rack3");
108      }
109    }
110  }
111
112  public static class MockBalancer extends BaseLoadBalancer {
113
114    @Override
115    protected List<RegionPlan> balanceTable(TableName tableName,
116      Map<ServerName, List<RegionInfo>> loadOfOneTable) {
117      return null;
118    }
119  }
120
121  /**
122   * Tests the bulk assignment used during cluster startup. Round-robin. Should yield a balanced
123   * cluster so same invariant as the load balancer holds, all servers holding either floor(avg) or
124   * ceiling(avg).
125   */
126  @Test
127  public void testBulkAssignment() throws Exception {
128    List<ServerName> tmp = getListOfServerNames(randomServers(5, 0));
129    List<RegionInfo> hris = randomRegions(20);
130    hris.add(RegionInfoBuilder.FIRST_META_REGIONINFO);
131    tmp.add(master);
132    Map<ServerName, List<RegionInfo>> plans = loadBalancer.roundRobinAssignment(hris, tmp);
133    int totalRegion = 0;
134    for (List<RegionInfo> regions : plans.values()) {
135      totalRegion += regions.size();
136    }
137    assertEquals(hris.size(), totalRegion);
138    for (int[] mock : regionsAndServersMocks) {
139      LOG.debug("testBulkAssignment with " + mock[0] + " regions and " + mock[1] + " servers");
140      List<RegionInfo> regions = randomRegions(mock[0]);
141      List<ServerAndLoad> servers = randomServers(mock[1], 0);
142      List<ServerName> list = getListOfServerNames(servers);
143      Map<ServerName, List<RegionInfo>> assignments =
144        loadBalancer.roundRobinAssignment(regions, list);
145      float average = (float) regions.size() / servers.size();
146      int min = (int) Math.floor(average);
147      int max = (int) Math.ceil(average);
148      if (assignments != null && !assignments.isEmpty()) {
149        for (List<RegionInfo> regionList : assignments.values()) {
150          assertTrue(regionList.size() == min || regionList.size() == max);
151        }
152      }
153      returnRegions(regions);
154      returnServers(list);
155    }
156  }
157
158  /**
159   * Test the cluster startup bulk assignment which attempts to retain assignment info.
160   */
161  @Test
162  public void testRetainAssignment() throws Exception {
163    // Test simple case where all same servers are there
164    List<ServerAndLoad> servers = randomServers(10, 10);
165    List<RegionInfo> regions = randomRegions(100);
166    Map<RegionInfo, ServerName> existing = new TreeMap<>(RegionInfo.COMPARATOR);
167    for (int i = 0; i < regions.size(); i++) {
168      ServerName sn = servers.get(i % servers.size()).getServerName();
169      // The old server would have had same host and port, but different
170      // start code!
171      ServerName snWithOldStartCode =
172        ServerName.valueOf(sn.getHostname(), sn.getPort(), sn.getStartcode() - 10);
173      existing.put(regions.get(i), snWithOldStartCode);
174    }
175    List<ServerName> listOfServerNames = getListOfServerNames(servers);
176    Map<ServerName, List<RegionInfo>> assignment =
177      loadBalancer.retainAssignment(existing, listOfServerNames);
178    assertRetainedAssignment(existing, listOfServerNames, assignment);
179
180    // Include two new servers that were not there before
181    List<ServerAndLoad> servers2 = new ArrayList<>(servers);
182    servers2.add(randomServer(10));
183    servers2.add(randomServer(10));
184    listOfServerNames = getListOfServerNames(servers2);
185    assignment = loadBalancer.retainAssignment(existing, listOfServerNames);
186    assertRetainedAssignment(existing, listOfServerNames, assignment);
187
188    // Remove two of the servers that were previously there
189    List<ServerAndLoad> servers3 = new ArrayList<>(servers);
190    servers3.remove(0);
191    servers3.remove(0);
192    listOfServerNames = getListOfServerNames(servers3);
193    assignment = loadBalancer.retainAssignment(existing, listOfServerNames);
194    assertRetainedAssignment(existing, listOfServerNames, assignment);
195  }
196
197  @Test
198  public void testRandomAssignment() throws Exception {
199    for (int i = 1; i != 5; ++i) {
200      LOG.info("run testRandomAssignment() with idle servers:" + i);
201      testRandomAssignment(i);
202    }
203  }
204
205  private void testRandomAssignment(int numberOfIdleServers) throws Exception {
206    assert numberOfIdleServers > 0;
207    List<ServerName> idleServers = new ArrayList<>(numberOfIdleServers);
208    for (int i = 0; i != numberOfIdleServers; ++i) {
209      idleServers.add(ServerName.valueOf("server-" + i, 1000, 1L));
210    }
211    List<ServerName> allServers = new ArrayList<>(idleServers.size() + 1);
212    allServers.add(ServerName.valueOf("server-" + numberOfIdleServers, 1000, 1L));
213    allServers.addAll(idleServers);
214    LoadBalancer balancer = new MockBalancer();
215    Configuration conf = HBaseConfiguration.create();
216    conf.setClass("hbase.util.ip.to.rack.determiner", MockMapping.class, DNSToSwitchMapping.class);
217    balancer.setClusterInfoProvider(new DummyClusterInfoProvider(conf) {
218
219      @Override
220      public List<ServerName> getOnlineServersListWithPredicator(List<ServerName> servers,
221        Predicate<ServerMetrics> filter) {
222        return idleServers;
223      }
224    });
225    RegionInfo hri1 = RegionInfoBuilder.newBuilder(TableName.valueOf(name.getMethodName()))
226      .setStartKey(Bytes.toBytes("key1")).setEndKey(Bytes.toBytes("key2")).setSplit(false)
227      .setRegionId(100).build();
228    assertNull(balancer.randomAssignment(hri1, Collections.emptyList()));
229    assertNull(balancer.randomAssignment(hri1, null));
230    for (int i = 0; i != 3; ++i) {
231      ServerName sn = balancer.randomAssignment(hri1, allServers);
232      assertTrue("actual:" + sn + ", except:" + idleServers, idleServers.contains(sn));
233    }
234  }
235
236  @Test
237  public void testRegionAvailability() throws Exception {
238    // Create a cluster with a few servers, assign them to specific racks
239    // then assign some regions. The tests should check whether moving a
240    // replica from one node to a specific other node or rack lowers the
241    // availability of the region or not
242
243    List<RegionInfo> list0 = new ArrayList<>();
244    List<RegionInfo> list1 = new ArrayList<>();
245    List<RegionInfo> list2 = new ArrayList<>();
246    // create a region (region1)
247    RegionInfo hri1 = RegionInfoBuilder.newBuilder(TableName.valueOf(name.getMethodName()))
248      .setStartKey(Bytes.toBytes("key1")).setEndKey(Bytes.toBytes("key2")).setSplit(false)
249      .setRegionId(100).build();
250    // create a replica of the region (replica_of_region1)
251    RegionInfo hri2 = RegionReplicaUtil.getRegionInfoForReplica(hri1, 1);
252    // create a second region (region2)
253    RegionInfo hri3 = RegionInfoBuilder.newBuilder(TableName.valueOf(name.getMethodName()))
254      .setStartKey(Bytes.toBytes("key2")).setEndKey(Bytes.toBytes("key3")).setSplit(false)
255      .setRegionId(101).build();
256    list0.add(hri1); // only region1
257    list1.add(hri2); // only replica_of_region1
258    list2.add(hri3); // only region2
259    Map<ServerName, List<RegionInfo>> clusterState = new LinkedHashMap<>();
260    clusterState.put(servers[0], list0); // servers[0] hosts region1
261    clusterState.put(servers[1], list1); // servers[1] hosts replica_of_region1
262    clusterState.put(servers[2], list2); // servers[2] hosts region2
263    // create a cluster with the above clusterState. The way in which the
264    // cluster is created (constructor code) would make sure the indices of
265    // the servers are in the order in which it is inserted in the clusterState
266    // map (linkedhashmap is important). A similar thing applies to the region lists
267    BalancerClusterState cluster = new BalancerClusterState(clusterState, null, null, rackManager);
268    // check whether a move of region1 from servers[0] to servers[1] would lower
269    // the availability of region1
270    assertTrue(cluster.wouldLowerAvailability(hri1, servers[1]));
271    // check whether a move of region1 from servers[0] to servers[2] would lower
272    // the availability of region1
273    assertTrue(!cluster.wouldLowerAvailability(hri1, servers[2]));
274    // check whether a move of replica_of_region1 from servers[0] to servers[2] would lower
275    // the availability of replica_of_region1
276    assertTrue(!cluster.wouldLowerAvailability(hri2, servers[2]));
277    // check whether a move of region2 from servers[0] to servers[1] would lower
278    // the availability of region2
279    assertTrue(!cluster.wouldLowerAvailability(hri3, servers[1]));
280
281    // now lets have servers[1] host replica_of_region2
282    list1.add(RegionReplicaUtil.getRegionInfoForReplica(hri3, 1));
283    // create a new clusterState with the above change
284    cluster = new BalancerClusterState(clusterState, null, null, rackManager);
285    // now check whether a move of a replica from servers[0] to servers[1] would lower
286    // the availability of region2
287    assertTrue(cluster.wouldLowerAvailability(hri3, servers[1]));
288
289    // start over again
290    clusterState.clear();
291    clusterState.put(servers[0], list0); // servers[0], rack1 hosts region1
292    clusterState.put(servers[5], list1); // servers[5], rack2 hosts replica_of_region1 and
293                                         // replica_of_region2
294    clusterState.put(servers[6], list2); // servers[6], rack2 hosts region2
295    clusterState.put(servers[10], new ArrayList<>()); // servers[10], rack3 hosts no region
296    // create a cluster with the above clusterState
297    cluster = new BalancerClusterState(clusterState, null, null, rackManager);
298    // check whether a move of region1 from servers[0],rack1 to servers[6],rack2 would
299    // lower the availability
300
301    assertTrue(cluster.wouldLowerAvailability(hri1, servers[0]));
302
303    // now create a cluster without the rack manager
304    cluster = new BalancerClusterState(clusterState, null, null, null);
305    // now repeat check whether a move of region1 from servers[0] to servers[6] would
306    // lower the availability
307    assertTrue(!cluster.wouldLowerAvailability(hri1, servers[6]));
308  }
309
310  @Test
311  public void testRegionAvailabilityWithRegionMoves() throws Exception {
312    List<RegionInfo> list0 = new ArrayList<>();
313    List<RegionInfo> list1 = new ArrayList<>();
314    List<RegionInfo> list2 = new ArrayList<>();
315    // create a region (region1)
316    RegionInfo hri1 = RegionInfoBuilder.newBuilder(TableName.valueOf(name.getMethodName()))
317      .setStartKey(Bytes.toBytes("key1")).setEndKey(Bytes.toBytes("key2")).setSplit(false)
318      .setRegionId(100).build();
319    // create a replica of the region (replica_of_region1)
320    RegionInfo hri2 = RegionReplicaUtil.getRegionInfoForReplica(hri1, 1);
321    // create a second region (region2)
322    RegionInfo hri3 = RegionInfoBuilder.newBuilder(TableName.valueOf(name.getMethodName()))
323      .setStartKey(Bytes.toBytes("key2")).setEndKey(Bytes.toBytes("key3")).setSplit(false)
324      .setRegionId(101).build();
325    list0.add(hri1); // only region1
326    list1.add(hri2); // only replica_of_region1
327    list2.add(hri3); // only region2
328    Map<ServerName, List<RegionInfo>> clusterState = new LinkedHashMap<>();
329    clusterState.put(servers[0], list0); // servers[0] hosts region1
330    clusterState.put(servers[1], list1); // servers[1] hosts replica_of_region1
331    clusterState.put(servers[2], list2); // servers[2] hosts region2
332    // create a cluster with the above clusterState. The way in which the
333    // cluster is created (constructor code) would make sure the indices of
334    // the servers are in the order in which it is inserted in the clusterState
335    // map (linkedhashmap is important).
336    BalancerClusterState cluster = new BalancerClusterState(clusterState, null, null, rackManager);
337    // check whether moving region1 from servers[1] to servers[2] would lower availability
338    assertTrue(!cluster.wouldLowerAvailability(hri1, servers[2]));
339
340    // now move region1 from servers[0] to servers[2]
341    cluster.doAction(new MoveRegionAction(0, 0, 2));
342    // now repeat check whether moving region1 from servers[1] to servers[2]
343    // would lower availability
344    assertTrue(cluster.wouldLowerAvailability(hri1, servers[2]));
345
346    // start over again
347    clusterState.clear();
348    List<RegionInfo> list3 = new ArrayList<>();
349    RegionInfo hri4 = RegionReplicaUtil.getRegionInfoForReplica(hri3, 1);
350    list3.add(hri4);
351    clusterState.put(servers[0], list0); // servers[0], rack1 hosts region1
352    clusterState.put(servers[5], list1); // servers[5], rack2 hosts replica_of_region1
353    clusterState.put(servers[6], list2); // servers[6], rack2 hosts region2
354    clusterState.put(servers[12], list3); // servers[12], rack3 hosts replica_of_region2
355    // create a cluster with the above clusterState
356    cluster = new BalancerClusterState(clusterState, null, null, rackManager);
357    // check whether a move of replica_of_region2 from servers[12],rack3 to servers[0],rack1 would
358    // lower the availability
359    assertTrue(!cluster.wouldLowerAvailability(hri4, servers[0]));
360    // now move region2 from servers[6],rack2 to servers[0],rack1
361    cluster.doAction(new MoveRegionAction(2, 2, 0));
362    // now repeat check if replica_of_region2 from servers[12],rack3 to servers[0],rack1 would
363    // lower the availability
364    assertTrue(cluster.wouldLowerAvailability(hri3, servers[0]));
365  }
366
367  private List<ServerName> getListOfServerNames(final List<ServerAndLoad> sals) {
368    return sals.stream().map(ServerAndLoad::getServerName).collect(Collectors.toList());
369  }
370
371  /**
372   * Asserts a valid retained assignment plan.
373   * <p>
374   * Must meet the following conditions:
375   * <ul>
376   * <li>Every input region has an assignment, and to an online server
377   * <li>If a region had an existing assignment to a server with the same address a a currently
378   * online server, it will be assigned to it
379   * </ul>
380   */
381  private void assertRetainedAssignment(Map<RegionInfo, ServerName> existing,
382    List<ServerName> servers, Map<ServerName, List<RegionInfo>> assignment) {
383    // Verify condition 1, every region assigned, and to online server
384    Set<ServerName> onlineServerSet = new TreeSet<>(servers);
385    Set<RegionInfo> assignedRegions = new TreeSet<>(RegionInfo.COMPARATOR);
386    for (Map.Entry<ServerName, List<RegionInfo>> a : assignment.entrySet()) {
387      assertTrue("Region assigned to server that was not listed as online",
388        onlineServerSet.contains(a.getKey()));
389      for (RegionInfo r : a.getValue())
390        assignedRegions.add(r);
391    }
392    assertEquals(existing.size(), assignedRegions.size());
393
394    // Verify condition 2, if server had existing assignment, must have same
395    Set<String> onlineHostNames = new TreeSet<>();
396    for (ServerName s : servers) {
397      onlineHostNames.add(s.getHostname());
398    }
399
400    for (Map.Entry<ServerName, List<RegionInfo>> a : assignment.entrySet()) {
401      ServerName assignedTo = a.getKey();
402      for (RegionInfo r : a.getValue()) {
403        ServerName address = existing.get(r);
404        if (address != null && onlineHostNames.contains(address.getHostname())) {
405          // this region was prevously assigned somewhere, and that
406          // host is still around, then it should be re-assigned on the
407          // same host
408          assertEquals(address.getHostname(), assignedTo.getHostname());
409        }
410      }
411    }
412  }
413
414  @Test
415  public void testClusterServersWithSameHostPort() {
416    // tests whether the BaseLoadBalancer.Cluster can be constructed with servers
417    // sharing same host and port
418    List<ServerName> servers = getListOfServerNames(randomServers(10, 10));
419    List<RegionInfo> regions = randomRegions(101);
420    Map<ServerName, List<RegionInfo>> clusterState = new TreeMap<>();
421
422    assignRegions(regions, servers, clusterState);
423
424    // construct another list of servers, but sharing same hosts and ports
425    List<ServerName> oldServers = new ArrayList<>(servers.size());
426    for (ServerName sn : servers) {
427      // The old server would have had same host and port, but different start code!
428      oldServers.add(ServerName.valueOf(sn.getHostname(), sn.getPort(), sn.getStartcode() - 10));
429    }
430
431    regions = randomRegions(9); // some more regions
432    assignRegions(regions, oldServers, clusterState);
433
434    // should not throw exception:
435    BalancerClusterState cluster = new BalancerClusterState(clusterState, null, null, null);
436    assertEquals(101 + 9, cluster.numRegions);
437    assertEquals(10, cluster.numServers); // only 10 servers because they share the same host + port
438
439    // test move
440    ServerName sn = oldServers.get(0);
441    int r0 = ArrayUtils.indexOf(cluster.regions, clusterState.get(sn).get(0));
442    int f0 = cluster.serversToIndex.get(sn.getAddress());
443    int t0 = cluster.serversToIndex.get(servers.get(1).getAddress());
444    cluster.doAction(new MoveRegionAction(r0, f0, t0));
445  }
446
447  private void assignRegions(List<RegionInfo> regions, List<ServerName> servers,
448    Map<ServerName, List<RegionInfo>> clusterState) {
449    for (int i = 0; i < regions.size(); i++) {
450      ServerName sn = servers.get(i % servers.size());
451      List<RegionInfo> regionsOfServer = clusterState.get(sn);
452      if (regionsOfServer == null) {
453        regionsOfServer = new ArrayList<>(10);
454        clusterState.put(sn, regionsOfServer);
455      }
456
457      regionsOfServer.add(regions.get(i));
458    }
459  }
460
461  @Test
462  public void testClusterRegionLocations() {
463    // tests whether region locations are handled correctly in Cluster
464    List<ServerName> servers = getListOfServerNames(randomServers(10, 10));
465    List<RegionInfo> regions = randomRegions(101);
466    Map<ServerName, List<RegionInfo>> clusterState = new HashMap<>();
467
468    assignRegions(regions, servers, clusterState);
469
470    // mock block locality for some regions
471    RegionHDFSBlockLocationFinder locationFinder = mock(RegionHDFSBlockLocationFinder.class);
472    // block locality: region:0 => {server:0}
473    // region:1 => {server:0, server:1}
474    // region:42 => {server:4, server:9, server:5}
475    when(locationFinder.getTopBlockLocations(regions.get(0)))
476      .thenReturn(Lists.newArrayList(servers.get(0)));
477    when(locationFinder.getTopBlockLocations(regions.get(1)))
478      .thenReturn(Lists.newArrayList(servers.get(0), servers.get(1)));
479    when(locationFinder.getTopBlockLocations(regions.get(42)))
480      .thenReturn(Lists.newArrayList(servers.get(4), servers.get(9), servers.get(5)));
481    // this server does not exists in clusterStatus
482    when(locationFinder.getTopBlockLocations(regions.get(43)))
483      .thenReturn(Lists.newArrayList(ServerName.valueOf("foo", 0, 0)));
484
485    BalancerClusterState cluster =
486      new BalancerClusterState(clusterState, null, locationFinder, null);
487
488    // this is ok, it is just a test
489    int r0 = ArrayUtils.indexOf(cluster.regions, regions.get(0));
490    int r1 = ArrayUtils.indexOf(cluster.regions, regions.get(1));
491    int r10 = ArrayUtils.indexOf(cluster.regions, regions.get(10));
492    int r42 = ArrayUtils.indexOf(cluster.regions, regions.get(42));
493    int r43 = ArrayUtils.indexOf(cluster.regions, regions.get(43));
494
495    int s0 = cluster.serversToIndex.get(servers.get(0).getAddress());
496    int s1 = cluster.serversToIndex.get(servers.get(1).getAddress());
497    int s4 = cluster.serversToIndex.get(servers.get(4).getAddress());
498    int s5 = cluster.serversToIndex.get(servers.get(5).getAddress());
499    int s9 = cluster.serversToIndex.get(servers.get(9).getAddress());
500
501    // region 0 locations
502    assertEquals(1, cluster.regionLocations[r0].length);
503    assertEquals(s0, cluster.regionLocations[r0][0]);
504
505    // region 1 locations
506    assertEquals(2, cluster.regionLocations[r1].length);
507    assertEquals(s0, cluster.regionLocations[r1][0]);
508    assertEquals(s1, cluster.regionLocations[r1][1]);
509
510    // region 10 locations
511    assertEquals(0, cluster.regionLocations[r10].length);
512
513    // region 42 locations
514    assertEquals(3, cluster.regionLocations[r42].length);
515    assertEquals(s4, cluster.regionLocations[r42][0]);
516    assertEquals(s9, cluster.regionLocations[r42][1]);
517    assertEquals(s5, cluster.regionLocations[r42][2]);
518
519    // region 43 locations
520    assertEquals(1, cluster.regionLocations[r43].length);
521    assertEquals(-1, cluster.regionLocations[r43][0]);
522  }
523}