BalancedRandomRoutingTableBuilder implements RoutingTableBuilder { @Override public synchronized List<ServerToSegmentSetMap> computeRoutingTableFromExternalView(String tableName, ExternalView externalView, List<InstanceConfig> instanceConfigList) { RoutingTableInstancePruner pruner = new RoutingTableInstancePruner(instanceConfigList); List<Map<String, Set<String>>> routingTables = new ArrayList<Map<String, Set<String>>>(); for (int i = 0; i < _numberOfRoutingTables; ++i) { routingTables.add(new HashMap<String, Set<String>>()); } String[] segmentSet = externalView.getPartitionSet().toArray(new String[0]); for (String segment : segmentSet) { Map<String, String> instanceToStateMap = externalView.getStateMap(segment); for (String instance : instanceToStateMap.keySet().toArray(new String[0])) { if (!instanceToStateMap.get(instance).equals("ONLINE") || pruner.isShuttingDown(instance)) { instanceToStateMap.remove(instance); } } if (instanceToStateMap.size() > 0) { List<String> instanceList = new ArrayList<String>(instanceToStateMap.keySet()); for (int i = 0; i < _numberOfRoutingTables; ++i) { Collections.shuffle(instanceList); String[] instances = instanceList.toArray(new String[instanceList.size()]); int minInstances = Integer.MAX_VALUE; int minIdx = -1; int base = 2; for (int k = 0; k < instances.length; ++k) { int sizeOfCurrentInstance = 0; if (routingTables.get(i).containsKey(instances[k])) { sizeOfCurrentInstance = routingTables.get(i).get(instances[k]).size(); } if (sizeOfCurrentInstance < minInstances) { minInstances = sizeOfCurrentInstance; minIdx = k; base = 2; } if (sizeOfCurrentInstance == minInstances && (System.currentTimeMillis() % base == 0)) { minIdx = k; base = 2; } else { base++; } } if (routingTables.get(i).containsKey(instances[minIdx])) { routingTables.get(i).get(instances[minIdx]).add(segment); } else { Set<String> instanceSegmentSet = new HashSet<String>(); instanceSegmentSet.add(segment); routingTables.get(i).put(instances[minIdx], instanceSegmentSet); } } } } List<ServerToSegmentSetMap> resultRoutingTableList = new ArrayList<ServerToSegmentSetMap>(); for (int i = 0; i < _numberOfRoutingTables; ++i) { resultRoutingTableList.add(new ServerToSegmentSetMap(routingTables.get(i))); } return resultRoutingTableList; } BalancedRandomRoutingTableBuilder();  BalancedRandomRoutingTableBuilder(int numberOfRoutingTables); @Override void init(Configuration configuration); @Override synchronized List<ServerToSegmentSetMap> computeRoutingTableFromExternalView(String tableName,
      ExternalView externalView, List<InstanceConfig> instanceConfigList);  }
@Test public void isRandom() { BalancedRandomRoutingTableBuilder routingTableBuilder = new BalancedRandomRoutingTableBuilder(); List<InstanceConfig> instanceConfigList = new ArrayList<>(); ExternalView externalView = new ExternalView("dummy"); externalView.setState("segment_1", "Server_1.2.3.4_1234", "ONLINE"); externalView.setState("segment_1", "Server_1.2.3.5_2345", "ONLINE"); externalView.setState("segment_1", "Server_1.2.3.6_3456", "ONLINE"); externalView.setState("segment_2", "Server_1.2.3.4_1234", "ONLINE"); externalView.setState("segment_2", "Server_1.2.3.5_2345", "ONLINE"); externalView.setState("segment_2", "Server_1.2.3.6_3456", "ONLINE"); externalView.setState("segment_3", "Server_1.2.3.4_1234", "ONLINE"); externalView.setState("segment_3", "Server_1.2.3.5_2345", "ONLINE"); externalView.setState("segment_3", "Server_1.2.3.6_3456", "ONLINE"); List<ServerToSegmentSetMap> routingTable = routingTableBuilder.computeRoutingTableFromExternalView("dummy", externalView, instanceConfigList); Iterator<ServerToSegmentSetMap> routingTableIterator = routingTable.iterator(); ServerToSegmentSetMap previous = routingTableIterator.next(); while (routingTableIterator.hasNext()) { ServerToSegmentSetMap current = routingTableIterator.next(); System.out.println("current = " + current); System.out.println("previous = " + previous); if (!current.equals(previous)) { return; } } Assert.fail("All routing tables are equal!"); }