public static Map calculateInitialIdealState()

in helix-core/src/main/java/org/apache/helix/tools/DefaultIdealStateCalculator.java [197:346]


  public static Map<String, Object> calculateInitialIdealState(List<String> instanceNames,
      int partitions, int replicas) {
    Random r = new Random(54321);
    assert (replicas <= instanceNames.size() - 1);

    ArrayList<Integer> masterPartitionAssignment = new ArrayList<Integer>();
    for (int i = 0; i < partitions; i++) {
      masterPartitionAssignment.add(i);
    }
    // shuffle the partition id array
    Collections.shuffle(masterPartitionAssignment, new Random(r.nextInt()));

    // 1. Generate the random master partition assignment
    // instanceName -> List of master partitions on that instance
    Map<String, List<Integer>> nodeMasterAssignmentMap = new TreeMap<String, List<Integer>>();
    for (int i = 0; i < masterPartitionAssignment.size(); i++) {
      String instanceName = instanceNames.get(i % instanceNames.size());
      if (!nodeMasterAssignmentMap.containsKey(instanceName)) {
        nodeMasterAssignmentMap.put(instanceName, new ArrayList<Integer>());
      }
      nodeMasterAssignmentMap.get(instanceName).add(masterPartitionAssignment.get(i));
    }

    // instanceName -> slave assignment for its master partitions
    // slave assignment: instanceName -> list of slave partitions on it
    List<Map<String, Map<String, List<Integer>>>> nodeSlaveAssignmentMapsList =
        new ArrayList<Map<String, Map<String, List<Integer>>>>(replicas);

    Map<String, Map<String, List<Integer>>> firstNodeSlaveAssignmentMap =
        new TreeMap<String, Map<String, List<Integer>>>();
    Map<String, Map<String, List<Integer>>> combinedNodeSlaveAssignmentMap =
        new TreeMap<String, Map<String, List<Integer>>>();

    if (replicas > 0) {
      // 2. For each node, calculate the evenly distributed slave as the first slave assignment
      // We will figure out the 2nd ...replicas-th slave assignment based on the first level slave
      // assignment
      for (int i = 0; i < instanceNames.size(); i++) {
        List<String> slaveInstances = new ArrayList<String>();
        ArrayList<Integer> slaveAssignment = new ArrayList<Integer>();
        TreeMap<String, List<Integer>> slaveAssignmentMap = new TreeMap<String, List<Integer>>();

        for (int j = 0; j < instanceNames.size(); j++) {
          if (j != i) {
            slaveInstances.add(instanceNames.get(j));
            slaveAssignmentMap.put(instanceNames.get(j), new ArrayList<Integer>());
          }
        }
        // Get the number of master partitions on instanceName
        List<Integer> masterAssignment = nodeMasterAssignmentMap.get(instanceNames.get(i));
        // do a random shuffling as in step 1, so that the first-level slave are distributed among
        // rest instances

        for (int j = 0; j < masterAssignment.size(); j++) {
          slaveAssignment.add(j);
        }
        Collections.shuffle(slaveAssignment, new Random(r.nextInt()));

        Collections.shuffle(slaveInstances, new Random(instanceNames.get(i).hashCode()));

        // Get the slave assignment map of node instanceName
        for (int j = 0; j < masterAssignment.size(); j++) {
          String slaveInstanceName =
              slaveInstances.get(slaveAssignment.get(j) % slaveInstances.size());
          if (!slaveAssignmentMap.containsKey(slaveInstanceName)) {
            slaveAssignmentMap.put(slaveInstanceName, new ArrayList<Integer>());
          }
          slaveAssignmentMap.get(slaveInstanceName).add(masterAssignment.get(j));
        }
        firstNodeSlaveAssignmentMap.put(instanceNames.get(i), slaveAssignmentMap);
      }
      nodeSlaveAssignmentMapsList.add(firstNodeSlaveAssignmentMap);
      // From the first slave assignment map, calculate the rest slave assignment maps
      for (int replicaOrder = 1; replicaOrder < replicas; replicaOrder++) {
        // calculate the next slave partition assignment map
        Map<String, Map<String, List<Integer>>> nextNodeSlaveAssignmentMap =
            calculateNextSlaveAssignemntMap(firstNodeSlaveAssignmentMap, replicaOrder);
        nodeSlaveAssignmentMapsList.add(nextNodeSlaveAssignmentMap);
      }

      // Combine the calculated 1...replicas-th slave assignment map together

      for (String instanceName : nodeMasterAssignmentMap.keySet()) {
        Map<String, List<Integer>> combinedSlaveAssignmentMap =
            new TreeMap<String, List<Integer>>();

        for (Map<String, Map<String, List<Integer>>> slaveNodeAssignmentMap : nodeSlaveAssignmentMapsList) {
          Map<String, List<Integer>> slaveAssignmentMap = slaveNodeAssignmentMap.get(instanceName);

          for (String slaveInstance : slaveAssignmentMap.keySet()) {
            if (!combinedSlaveAssignmentMap.containsKey(slaveInstance)) {
              combinedSlaveAssignmentMap.put(slaveInstance, new ArrayList<Integer>());
            }
            combinedSlaveAssignmentMap.get(slaveInstance).addAll(
                slaveAssignmentMap.get(slaveInstance));
          }
        }
        migrateSlaveAssignMapToNewInstances(combinedSlaveAssignmentMap, new ArrayList<String>());
        combinedNodeSlaveAssignmentMap.put(instanceName, combinedSlaveAssignmentMap);
      }
    }
    /*
     * // Print the result master and slave assignment maps
     * System.out.println("Master assignment:");
     * for(String instanceName : nodeMasterAssignmentMap.keySet())
     * {
     * System.out.println(instanceName+":");
     * for(Integer x : nodeMasterAssignmentMap.get(instanceName))
     * {
     * System.out.print(x+" ");
     * }
     * System.out.println();
     * System.out.println("Slave assignment:");
     * int slaveOrder = 1;
     * for(Map<String, Map<String, List<Integer>>> slaveNodeAssignmentMap :
     * nodeSlaveAssignmentMapsList)
     * {
     * System.out.println("Slave assignment order :" + (slaveOrder++));
     * Map<String, List<Integer>> slaveAssignmentMap = slaveNodeAssignmentMap.get(instanceName);
     * for(String slaveName : slaveAssignmentMap.keySet())
     * {
     * System.out.print("\t" + slaveName +":\n\t" );
     * for(Integer x : slaveAssignmentMap.get(slaveName))
     * {
     * System.out.print(x + " ");
     * }
     * System.out.println("\n");
     * }
     * }
     * System.out.println("\nCombined slave assignment map");
     * Map<String, List<Integer>> slaveAssignmentMap =
     * combinedNodeSlaveAssignmentMap.get(instanceName);
     * for(String slaveName : slaveAssignmentMap.keySet())
     * {
     * System.out.print("\t" + slaveName +":\n\t" );
     * for(Integer x : slaveAssignmentMap.get(slaveName))
     * {
     * System.out.print(x + " ");
     * }
     * System.out.println("\n");
     * }
     * }
     */
    Map<String, Object> result = new TreeMap<String, Object>();
    result.put("MasterAssignmentMap", nodeMasterAssignmentMap);
    result.put("SlaveAssignmentMap", combinedNodeSlaveAssignmentMap);
    result.put("replicas", new Integer(replicas + 1));
    result.put("partitions", new Integer(partitions));
    return result;
  }