void chooseExcessReplicates(Collection<DatanodeDescriptor> nonExcess,
                              Block b, short replication,
                              DatanodeDescriptor addedNode,
                              DatanodeDescriptor delNodeHint,
                              INodeFile inode,
                              List<DatanodeID> excessReplicateMapTmp) {
    // first form a rack to datanodes map and
    HashMap<String, ArrayList<DatanodeDescriptor>> rackMap =
      new HashMap<String, ArrayList<DatanodeDescriptor>>();
    for (Iterator<DatanodeDescriptor> iter = nonExcess.iterator();
         iter.hasNext();) {
      DatanodeDescriptor node = iter.next();
      String rackName = node.getNetworkLocation();
      ArrayList<DatanodeDescriptor> datanodeList = rackMap.get(rackName);
      if (datanodeList == null) {
        datanodeList = new ArrayList<DatanodeDescriptor>();
      }
      datanodeList.add(node);
      rackMap.put(rackName, datanodeList);
    }

    // split nodes into two sets
    // priSet contains nodes on rack with more than one replica
    // remains contains the remaining nodes
    // It may be useful for the corresponding BlockPlacementPolicy.
    ArrayList<DatanodeDescriptor> priSet = new ArrayList<DatanodeDescriptor>();
    ArrayList<DatanodeDescriptor> remains = new ArrayList<DatanodeDescriptor>();
    for (Iterator<Entry<String, ArrayList<DatanodeDescriptor>>> iter =
      rackMap.entrySet().iterator(); iter.hasNext();) {
      Entry<String, ArrayList<DatanodeDescriptor>> rackEntry = iter.next();
      ArrayList<DatanodeDescriptor> datanodeList = rackEntry.getValue();
      if (datanodeList.size() == 1) {
        remains.add(datanodeList.get(0));
      } else {
        priSet.addAll(datanodeList);
      }
    }

    // pick one node to delete that favors the delete hint
    // otherwise follow the strategy of corresponding BlockPlacementPolicy.
    boolean firstOne = true;
    while (nonExcess.size() - replication > 0) {
      DatanodeInfo cur = null;
      long minSpace = Long.MAX_VALUE;

      // check if we can del delNodeHint
      if (firstOne && delNodeHint != null && nonExcess.contains(delNodeHint) &&
        (priSet.contains(delNodeHint) || (addedNode != null && !priSet.contains(addedNode)))) {
        cur = delNodeHint;
      } else { // regular excessive replica removal
        cur = replicator.chooseReplicaToDelete(inode, b, replication, priSet, remains);
      }

      firstOne = false;
      // adjust rackmap, priSet, and remains
      String rack = cur.getNetworkLocation();
      ArrayList<DatanodeDescriptor> datanodes = rackMap.get(rack);
      datanodes.remove(cur);
      if (datanodes.isEmpty()) {
        rackMap.remove(rack);
      }
      if (priSet.remove(cur)) {
        if (datanodes.size() == 1) {
          priSet.remove(datanodes.get(0));
          remains.add(datanodes.get(0));
        }
      } else {
        remains.remove(cur);
      }
      nonExcess.remove(cur);

      excessReplicateMapTmp.add(cur);
      if (NameNode.stateChangeLog.isDebugEnabled()) {
        NameNode.stateChangeLog.debug("BLOCK* NameSystem.chooseExcessReplicates: "
          + "(" + cur.getName() + ", " + b
          + ") is added to excessReplicateMapTmp");
      }
    }
  }
void chooseExcessReplicates ( Collection < DatanodeDescriptor > nonExcess , Block b , short replication , DatanodeDescriptor addedNode , DatanodeDescriptor delNodeHint , INodeFile inode , List < DatanodeID > excessReplicateMapTmp ) { HashMap < String , ArrayList < DatanodeDescriptor > > rackMap = new HashMap < String , ArrayList < DatanodeDescriptor > > ( ) ; for ( Iterator < DatanodeDescriptor > iter = nonExcess . iterator ( ) ; iter . hasNext ( ) ; ) { DatanodeDescriptor node = iter . next ( ) ; String rackName = node . getNetworkLocation ( ) ; ArrayList < DatanodeDescriptor > datanodeList = rackMap . get ( rackName ) ; if ( datanodeList == null ) { datanodeList = new ArrayList < DatanodeDescriptor > ( ) ; } datanodeList . add ( node ) ; rackMap . put ( rackName , datanodeList ) ; } ArrayList < DatanodeDescriptor > priSet = new ArrayList < DatanodeDescriptor > ( ) ; ArrayList < DatanodeDescriptor > remains = new ArrayList < DatanodeDescriptor > ( ) ; for ( Iterator < Entry < String , ArrayList < DatanodeDescriptor > > > iter = rackMap . entrySet ( ) . iterator ( ) ; iter . hasNext ( ) ; ) { Entry < String , ArrayList < DatanodeDescriptor > > rackEntry = iter . next ( ) ; ArrayList < DatanodeDescriptor > datanodeList = rackEntry . getValue ( ) ; if ( datanodeList . size ( ) == 1 ) { remains . add ( datanodeList . get ( 0 ) ) ; } else { priSet . addAll ( datanodeList ) ; } } boolean firstOne = true ; while ( nonExcess . size ( ) - replication > 0 ) { DatanodeInfo cur = null ; long minSpace = Long . MAX_VALUE ; if ( firstOne && delNodeHint != null && nonExcess . contains ( delNodeHint ) && ( priSet . contains ( delNodeHint ) || ( addedNode != null && ! priSet . contains ( addedNode ) ) ) ) { cur = delNodeHint ; } else { cur = replicator . chooseReplicaToDelete ( inode , b , replication , priSet , remains ) ; } firstOne = false ; String rack = cur . getNetworkLocation ( ) ; ArrayList < DatanodeDescriptor > datanodes = rackMap . get ( rack ) ; datanodes . remove ( cur ) ; if ( datanodes . isEmpty ( ) ) { rackMap . remove ( rack ) ; } if ( priSet . remove ( cur ) ) { if ( datanodes . size ( ) == 1 ) { priSet . remove ( datanodes . get ( 0 ) ) ; remains . add ( datanodes . get ( 0 ) ) ; } } else { remains . remove ( cur ) ; } nonExcess . remove ( cur ) ; excessReplicateMapTmp . add ( cur ) ; if ( NameNode . stateChangeLog . isDebugEnabled ( ) ) { NameNode . stateChangeLog . debug ( "BLOCK* NameSystem.chooseExcessReplicates: " + "(" + cur . getName ( ) + ", " + b + ") is added to excessReplicateMapTmp" ) ; } } }
We want "replication" replicates for the block, but we now have too many.
In this method, copy enough nodes from 'srcNodes' into 'dstNodes' such that:
<p/>
srcNodes.size() - dstNodes.size() == replication
<p/>
We pick node that make sure that replicas are spread across racks and
also try hard to pick one with least free space.