+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1/** 2* Licensed to the Apache Software Foundation (ASF) under one 3* or more contributor license agreements. See the NOTICE file 4* distributed with this work for additional information 5* regarding copyright ownership. The ASF licenses this file 6* to you under the Apache License, Version 2.0 (the 7* "License"); you may not use this file except in compliance 8* with the License. You may obtain a copy of the License at 9* 10* http://www.apache.org/licenses/LICENSE-2.0 11* 12* Unless required by applicable law or agreed to in writing, software 13* distributed under the License is distributed on an "AS IS" BASIS, 14* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15* See the License for the specific language governing permissions and 16* limitations under the License. 17*/ 18 19package org .apache .hadoop .examples .terasort ; 20 21import java .io .*; 22import java .util .*; 23 24import org .apache .commons .logging .Log ; 25import org .apache .commons .logging .LogFactory ; 26import org .apache .hadoop .conf .Configuration ; 27import org .apache .hadoop .mapreduce .InputSplit ; 28import org .apache .hadoop .mapreduce .lib .input .FileSplit ; 29import org .apache .hadoop .mapreduce .server .tasktracker .TTConfig ; 30 31import com .common .base .Charsets ; 32 33class TeraScheduler { 34static String USE ="mapreduce.terasort.use.terascheduler" ; 35private static final Log LOG =LogFactory .getLog (TeraScheduler .class ); 36private Split []splits ; 37private List <Host >hosts =new ArrayList <Host >(); 38private int slotsPerHost ; 39private int remainingSplits =0 ; 40private FileSplit []realSplits =null ; 41 42static class Split { 43String filename ; 44boolean isAssigned =false ; 45List <Host >locations =new ArrayList <Host >(); 46Split (String filename ) { 47this .filename =filename ; 48 } 49public String toString () { 50StringBuffer result =new StringBuffer (); 51result .append (filename ); 52result .append (" on " ); 53for (Host host :locations ) { 54result .append (host .hostname ); 55result .append (", " ); 56 } 57return result .toString (); 58 } 59 } 60static class Host { 61String hostname ; 62List <Split >splits =new ArrayList <Split >(); 63Host (String hostname ) { 64this .hostname =hostname ; 65 } 66public String toString () { 67StringBuffer result =new StringBuffer (); 68result .append (splits .size ()); 69result .append (" " ); 70result .append (hostname ); 71return result .toString (); 72 } 73 } 74 75List <String >readFile (String filename )throws IOException { 76List <String >result =new ArrayList <String >(10000 ); 77BufferedReader in =new BufferedReader ( 78new InputStreamReader (new FileInputStream (filename ),Charsets .UTF_8 )); 79String line =in .readLine (); 80while (line !=null ) { 81result .add (line ); 82line =in .readLine (); 83 } 84in .close (); 85return result ; 86 } 87 88public TeraScheduler (String splitFilename , 89String nodeFilename )throws IOException { 90slotsPerHost =4 ; 91// get the hosts 92Map <String ,Host >hostIds =new HashMap <String ,Host >(); 93for (String hostName :readFile (nodeFilename )) { 94Host host =new Host (hostName ); 95hosts .add (host ); 96hostIds .put (hostName ,host ); 97 } 98// read the blocks 99List <String >splitLines =readFile (splitFilename ); 100splits =new Split [splitLines .size ()]; 101remainingSplits =0 ; 102for (String line :splitLines ) { 103StringTokenizer itr =new StringTokenizer (line ); 104Split newSplit =new Split (itr .nextToken ()); 105splits [remainingSplits ++] =newSplit ; 106while (itr .hasMoreTokens ()) { 107Host host =hostIds .get (itr .nextToken ()); 108newSplit .locations .add (host ); 109host .splits .add (newSplit ); 110 } 111 } 112 } 113 114public TeraScheduler (FileSplit []realSplits , 115Configuration conf )throws IOException { 116this .realSplits =realSplits ; 117this .slotsPerHost =conf .getInt (TTConfig .TT_MAP_SLOTS ,4 ); 118Map <String ,Host >hostTable =new HashMap <String ,Host >(); 119splits =new Split [realSplits .length ]; 120for (FileSplit realSplit :realSplits ) { 121Split split =new Split (realSplit .getPath ().toString ()); 122splits [remainingSplits ++] =split ; 123for (String hostname :realSplit .getLocations ()) { 124Host host =hostTable .get (hostname ); 125if (host ==null ) { 126host =new Host (hostname ); 127hostTable .put (hostname ,host ); 128hosts .add (host ); 129 } 130host .splits .add (split ); 131split .locations .add (host ); 132 } 133 } 134 } 135 136Host pickBestHost () { 137Host result =null ; 138int splits =Integer .MAX_VALUE ; 139for (Host host :hosts ) { 140if (host .splits .size () <splits ) { 141result =host ; 142splits =host .splits .size (); 143 } 144 } 145if (result !=null ) { 146hosts .remove (result ); 147LOG .debug ("picking " +result ); 148 } 149return result ; 150 } 151 152void pickBestSplits (Host host ) { 153int tasksToPick =Math .min (slotsPerHost , 154 (int )Math .ceil ((double )remainingSplits / 155hosts .size ())); 156Split []best =new Split [tasksToPick ]; 157for (Split cur :host .splits ) { 158LOG .debug (" examine: " +cur .filename +" " +cur .locations .size ()); 159int i =0 ; 160while (i <tasksToPick &&best [i ] !=null && 161best [i ].locations .size () <=cur .locations .size ()) { 162i +=1 ; 163 } 164if (i <tasksToPick ) { 165for (int j =tasksToPick -1 ;j >i ; --j ) { 166best [j ] =best [j -1 ]; 167 } 168best [i ] =cur ; 169 } 170 } 171// for the chosen blocks, remove them from the other locations 172for (int i =0 ;i <tasksToPick ; ++i ) { 173if (best [i ] !=null ) { 174LOG .debug (" best: " +best [i ].filename ); 175for (Host other :best [i ].locations ) { 176other .splits .remove (best [i ]); 177 } 178best [i ].locations .clear (); 179best [i ].locations .add (host ); 180best [i ].isAssigned =true ; 181remainingSplits -=1 ; 182 } 183 } 184// for the non-chosen blocks, remove this host 185for (Split cur :host .splits ) { 186if (!cur .isAssigned ) { 187cur .locations .remove (host ); 188 } 189 } 190 } 191 192void solve ()throws IOException { 193Host host =pickBestHost (); 194while (host !=null ) { 195pickBestSplits (host ); 196host =pickBestHost (); 197 } 198 } 199 200/** 201* Solve the schedule and modify the FileSplit array to reflect the new 202* schedule. It will move placed splits to front and unplacable splits 203* to the end. 204* @return a new list of FileSplits that are modified to have the 205* best host as the only host. 206* @throws IOException 207*/ 208public List <InputSplit >getNewFileSplits ()throws IOException { 209solve (); 210FileSplit []result =new FileSplit [realSplits .length ]; 211int left =0 ; 212int right =realSplits .length -1 ; 213for (int i =0 ;i <splits .length ; ++i ) { 214if (splits [i ].isAssigned ) { 215// copy the split and fix up the locations 216String []newLocations = {splits [i ].locations .get (0 ).hostname }; 217realSplits [i ] =new FileSplit (realSplits [i ].getPath (), 218realSplits [i ].getStart (),realSplits [i ].getLength (),newLocations ); 219result [left ++] =realSplits [i ]; 220 }else { 221result [right --] =realSplits [i ]; 222 } 223 } 224List <InputSplit >ret =new ArrayList <InputSplit >(); 225for (FileSplit fs :result ) { 226ret .add (fs ); 227 } 228return ret ; 229 } 230 231public static void main (String []args )throws IOException { 232TeraScheduler problem =new TeraScheduler ("block-loc.txt" ,"nodes" ); 233for (Host host :problem .hosts ) { 234System .out .println (host ); 235 } 236LOG .info ("starting solve" ); 237problem .solve (); 238List <Split >leftOvers =new ArrayList <Split >(); 239for (int i =0 ;i <problem .splits .length ; ++i ) { 240if (problem .splits [i ].isAssigned ) { 241System .out .println ("sched: " +problem .splits [i ]); 242 }else { 243leftOvers .add (problem .splits [i ]); 244 } 245 } 246for (Split cur :leftOvers ) { 247System .out .println ("left: " +cur ); 248 } 249System .out .println ("left over: " +leftOvers .size ()); 250LOG .info ("done" ); 251 } 252 253}