+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

master
7.9 KiB253 linesraw
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.google.common.base.Charsets;
32
33class TeraScheduler {
34  static String USE = "mapreduce.terasort.use.terascheduler";
35  private static final Log LOG = LogFactory.getLog(TeraScheduler.class);
36  private Split[] splits;
37  private List<Host> hosts = new ArrayList<Host>();
38  private int slotsPerHost;
39  private int remainingSplits = 0;
40  private FileSplit[] realSplits = null;
41
42  static class Split {
43    String filename;
44    boolean isAssigned = false;
45    List<Host> locations = new ArrayList<Host>();
46    Split(String filename) {
47      this.filename = filename;
48    }
49    public String toString() {
50      StringBuffer result = new StringBuffer();
51      result.append(filename);
52      result.append(" on ");
53      for(Host host: locations) {
54        result.append(host.hostname);
55        result.append(", ");
56      }
57      return result.toString();
58    }
59  }
60  static class Host {
61    String hostname;
62    List<Split> splits = new ArrayList<Split>();
63    Host(String hostname) {
64      this.hostname = hostname;
65    }
66    public String toString() {
67      StringBuffer result = new StringBuffer();
68      result.append(splits.size());
69      result.append(" ");
70      result.append(hostname);
71      return result.toString();
72    }
73  }
74
75  List<String> readFile(String filename) throws IOException {
76    List<String> result = new ArrayList<String>(10000);
77    BufferedReader in = new BufferedReader(
78        new InputStreamReader(new FileInputStream(filename), Charsets.UTF_8));
79    String line = in.readLine();
80    while (line != null) {
81      result.add(line);
82      line = in.readLine();
83    }
84    in.close();
85    return result;
86  }
87
88  public TeraScheduler(String splitFilename, 
89                       String nodeFilename) throws IOException {
90    slotsPerHost = 4;
91    // get the hosts
92    Map<String, Host> hostIds = new HashMap<String,Host>();
93    for(String hostName: readFile(nodeFilename)) {
94      Host host = new Host(hostName);
95      hosts.add(host);
96      hostIds.put(hostName, host);
97    }
98    // read the blocks
99    List<String> splitLines = readFile(splitFilename);
100    splits = new Split[splitLines.size()];
101    remainingSplits = 0;
102    for(String line: splitLines) {
103      StringTokenizer itr = new StringTokenizer(line);
104      Split newSplit = new Split(itr.nextToken());
105      splits[remainingSplits++] = newSplit;
106      while (itr.hasMoreTokens()) {
107        Host host = hostIds.get(itr.nextToken());
108        newSplit.locations.add(host);
109        host.splits.add(newSplit);
110      }
111    }
112  }
113
114  public TeraScheduler(FileSplit[] realSplits,
115                       Configuration conf) throws IOException {
116    this.realSplits = realSplits;
117    this.slotsPerHost = conf.getInt(TTConfig.TT_MAP_SLOTS, 4);
118    Map<String, Host> hostTable = new HashMap<String, Host>();
119    splits = new Split[realSplits.length];
120    for(FileSplit realSplit: realSplits) {
121      Split split = new Split(realSplit.getPath().toString());
122      splits[remainingSplits++] = split;
123      for(String hostname: realSplit.getLocations()) {
124        Host host = hostTable.get(hostname);
125        if (host == null) {
126          host = new Host(hostname);
127          hostTable.put(hostname, host);
128          hosts.add(host);
129        }
130        host.splits.add(split);
131        split.locations.add(host);
132      }
133    }
134  }
135
136  Host pickBestHost() {
137    Host result = null;
138    int splits = Integer.MAX_VALUE;
139    for(Host host: hosts) {
140      if (host.splits.size() < splits) {
141        result = host;
142        splits = host.splits.size();
143      }
144    }
145    if (result != null) {
146      hosts.remove(result);
147      LOG.debug("picking " + result);
148    }
149    return result;
150  }
151
152  void pickBestSplits(Host host) {
153    int tasksToPick = Math.min(slotsPerHost, 
154                               (int) Math.ceil((double) remainingSplits / 
155                                               hosts.size()));
156    Split[] best = new Split[tasksToPick];
157    for(Split cur: host.splits) {
158      LOG.debug("  examine: " + cur.filename + " " + cur.locations.size());
159      int i = 0;
160      while (i < tasksToPick && best[i] != null && 
161             best[i].locations.size() <= cur.locations.size()) {
162        i += 1;
163      }
164      if (i < tasksToPick) {
165        for(int j = tasksToPick - 1; j > i; --j) {
166          best[j] = best[j-1];
167        }
168        best[i] = cur;
169      }
170    }
171    // for the chosen blocks, remove them from the other locations
172    for(int i=0; i < tasksToPick; ++i) {
173      if (best[i] != null) {
174        LOG.debug(" best: " + best[i].filename);
175        for (Host other: best[i].locations) {
176          other.splits.remove(best[i]);
177        }
178        best[i].locations.clear();
179        best[i].locations.add(host);
180        best[i].isAssigned = true;
181        remainingSplits -= 1;
182      }
183    }
184    // for the non-chosen blocks, remove this host
185    for(Split cur: host.splits) {
186      if (!cur.isAssigned) {
187        cur.locations.remove(host);
188      }
189    }
190  }
191  
192  void solve() throws IOException {
193    Host host = pickBestHost();
194    while (host != null) {
195      pickBestSplits(host);
196      host = 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   */
208  public List<InputSplit> getNewFileSplits() throws IOException {
209    solve();
210    FileSplit[] result = new FileSplit[realSplits.length];
211    int left = 0;
212    int right = realSplits.length - 1;
213    for(int i=0; i < splits.length; ++i) {
214      if (splits[i].isAssigned) {
215        // copy the split and fix up the locations
216        String[] newLocations = {splits[i].locations.get(0).hostname};
217        realSplits[i] = new FileSplit(realSplits[i].getPath(),
218            realSplits[i].getStart(), realSplits[i].getLength(), newLocations);
219        result[left++] = realSplits[i];
220      } else {
221        result[right--] = realSplits[i];
222      }
223    }
224    List<InputSplit> ret = new ArrayList<InputSplit>();
225    for (FileSplit fs : result) {
226      ret.add(fs);
227    }
228    return ret;
229  }
230
231  public static void main(String[] args) throws IOException {
232    TeraScheduler problem = new TeraScheduler("block-loc.txt", "nodes");
233    for(Host host: problem.hosts) {
234      System.out.println(host);
235    }
236    LOG.info("starting solve");
237    problem.solve();
238    List<Split> leftOvers = new ArrayList<Split>();
239    for(int i=0; i < problem.splits.length; ++i) {
240      if (problem.splits[i].isAssigned) {
241        System.out.println("sched: " + problem.splits[i]);        
242      } else {
243        leftOvers.add(problem.splits[i]);
244      }
245    }
246    for(Split cur: leftOvers) {
247      System.out.println("left: " + cur);
248    }
249    System.out.println("left over: " + leftOvers.size());
250    LOG.info("done");
251  }
252
253}