MrGamoo/Job/Plan.pm untested

filter: Statementstmt 0.0% 0 / 168 Branchbran 0.0% 0 / 28 Conditioncond 0.0% 0 / 12 MC/DCmcdc 0.0% 0 / 8 Subroutinesub 0.0% 0 / 12 Podpod 0.0% 0 / 9 totaltotal 0.0% 0 / 237 CC 15 SCAR 28.3
CC
15
Cov
0%
_plan_divy_files
42.0
new
20.0
_plan_map
12.0
CRAP 16.9
1 # -*- perl -*-
2  
3 # Copyright (c) 2010 AdCopy
4 # Author: Jeff Weisberg
5 # Created: 2010-Jan-14 17:35 (EST)
6 # Function:
7 #
8 # $Id: Plan.pm,v 1.1 2010/11/01 18:41:56 jaw Exp $
9  
10 package AC::MrGamoo::Job::Plan;
11 use AC::MrGamoo::Debug 'plan';
12 use AC::Misc;
13  
14 use strict;
15  
16 my $REDUCEFACTOR = 1.9; # QQQ - config?
17 my $MAPTARGETMIN = 8; # try to have at least this many maps/server
18 my $MAPSIZELIMIT = 100_000_000;
19  
20 sub new {
21 my $class = shift;
22 my $job = shift;
23 my $servers = shift;
24 my $files = shift;
25  
26 return unless @$servers;
27  
28 # how many reduces?
29 my $nr = _number_of_reduces( $job->{options}, scalar @$servers );
30  
31 # map servers to reduce bins
32 my $redbin = _pick_reduce_bins( $nr, $servers );
33  
34 # plan out the map phase
35 my @phase = 'map';
36 my($planmap, $plancopy) = _plan_map( $job, $servers, $files, $nr, $redbin );
37 my @task = { phase => 'map', task => $planmap };
38  
39 # plan out the reduce phases
40 my $nrp = @{$job->{mr}{content}{reduce}};
41 for my $r (0 .. $nrp - 1){
42 push @phase, "reduce/$r";
43 # last reduce has 1 outfile, otherwise nr.
44 my $nout = ($r == $nrp - 1) ? 1 : $nr;
45 push @task, { phase => "reduce/$r", task => _plan_reduce($job, $r, $nout, $redbin, $task[-1]{task}) };
46 }
47  
48 # plan out a final phase
49 if( $job->{mr}{content}{final} ){
50 push @phase, 'final';
51 push @task, { phase => 'final', task => _plan_final($job, $redbin, $task[-1]{task}) };
52 }
53  
54 # summary
55 my %task;
56 for my $ts (@task){
57 for my $t ( @{$ts->{task}} ){
58 $task{ $t->{id} } = $t;
59 }
60 }
61  
62 # debug("plan: " . dumper( \@task ));
63  
64 debug("infiles: " . @$files . ", precopy: " . @$plancopy . ", maps: " . @$planmap . ", reduces: $nr x $nrp");
65  
66 return bless {
67 nserver => scalar(@$servers),
68 nreduce => $nr,
69 copying => $plancopy,
70 phases => \@phase,
71 taskplan => \@task,
72 redbin => $redbin,
73 taskidx => \%task,
74 }, $class;
75 }
76  
77 sub _number_of_reduces {
78 my $config = shift;
79 my $nserver = shift;
80  
81 my $nr = $config->{reduces} + 0;
82 $nr ||= int $nserver * $REDUCEFACTOR;
83 $nr = 1 if $nr < 1;
84  
85 return $nr;
86 }
87  
88 sub _pick_reduce_bins {
89 my $nr = shift;
90 my $servers = shift;
91  
92  
93 my @redbin;
94 for my $bin (0 .. $nr-1){
95 $redbin[$bin][0] = $servers->[ $bin % @$servers ]->{id};
96  
97 # pick alt location
98 next unless @$servers > 1;
99 $redbin[$bin][1] = $servers->[ ($bin + 1) % @$servers ]->{id};
100 }
101 shuffle(\@redbin);
102  
103 return \@redbin;
104 }
105  
106 sub _plan_map {
107 my $job = shift;
108 my $servers = shift;
109 my $files = shift;
110 my $nr = shift;
111 my $redbin = shift;
112  
113 # plan map
114 # divy files among servers
115 # split server + files into tasks
116  
117 my( $filemap, $copies ) = _plan_divy_files( $job, $files, $servers );
118  
119 my @maptask;
120 for my $s (keys %$filemap){
121 my $totalsize = 0;
122 $totalsize += $_->{size} for @{$filemap->{$s}};;
123 my $sizelimit = $totalsize / $MAPTARGETMIN;
124 $sizelimit = $MAPSIZELIMIT if $sizelimit > $MAPSIZELIMIT;
125  
126 my @todo = sort { $b->{size} <=> $a->{size} } @{$filemap->{$s}};
127 while( @todo ){
128 my @file;
129 my %alt;
130 my $tot;
131  
132 while( @todo && ($tot < $sizelimit) ){
133 my $f = shift @todo;
134 $tot += $f->{size};
135 push @file, $f->{filename};
136 # backup plan?
137 my $as = $f->{location}[1];
138 $alt{$f->{filename}} = $as if $as;
139 }
140  
141 my $id = unique();
142 push @maptask, AC::MrGamoo::Job::TaskInfo->new( $job,
143 id => $id,
144 phase => 'map',
145 server => $s,
146 infile => \@file,
147 altplan => \%alt,
148 _total => $tot,
149 outfile => _plan_outfiles($job, $id, $nr, $redbin, 'map' ),
150 );
151 }
152 }
153  
154 return (\@maptask, $copies);
155 }
156  
157 sub _plan_reduce {
158 my $job = shift;
159 my $rno = shift;
160 my $nout = shift;
161 my $redbin = shift;
162 my $ptasks = shift;
163  
164 my $jid = $job->{request}{jobid};
165  
166 my @reds;
167 my $sn = 0;
168 for my $s (@$redbin){
169 my $id = unique();
170 push @reds, AC::MrGamoo::Job::TaskInfo->new( $job,
171 id => $id,
172 phase => "reduce/$rno",
173 server => $s->[0],
174 altserver => $s->[1],
175 infile => [ map { $_->{outfile}[$sn]{filename} } @$ptasks ],
176 outfile => _plan_outfiles($job, $id, $nout, $redbin, "red$rno"),
177 );
178 $sn++;
179 }
180  
181 return \@reds;
182 }
183  
184 sub _plan_final {
185 my $job = shift;
186 my $redbin = shift;
187 my $ptasks = shift;
188  
189 my $jid = $job->{request}{jobid};
190  
191 my $id = unique();
192 return [
193 AC::MrGamoo::Job::TaskInfo->new( $job,
194 id => $id,
195 server => $redbin->[0][0],
196 altserver => $redbin->[0][1],
197 phase => 'final',
198 infile => [ map { $_->{outfile}[0]{filename} } @$ptasks ],
199 outfile => [ ],
200 ),
201 ];
202 }
203  
204 sub _plan_outfiles {
205 my $job = shift;
206 my $taskid = shift;
207 my $nout = shift;
208 my $redbin = shift;
209 my $pfix = shift;
210  
211 my @out;
212 my $jid = $job->{request}{jobid};
213  
214 for my $n (0 .. $nout - 1){
215 push @out, { filename => "mrtmp/j_$jid/${pfix}_${taskid}_$n", dst => [ @{$redbin->[$n]} ] };
216 }
217  
218 return \@out;
219 }
220  
221 sub _plan_map_these_servers {
222 my $job = shift;
223 my $servers = shift;
224  
225 # limit number of servers?
226 my $nm = ($job->{options}{maps} + 0) || @$servers;
227  
228 my %data;
229 for my $s ( sort { $a->{metric} <=> $b->{metric} } @$servers ){
230 $data{ $s->{id} } = { metric => $s->{metric}, use => ($nm ? 1 : 0) };
231 $nm -- if $nm;
232 }
233  
234 return \%data;
235 }
236  
237 sub _plan_divy_files {
238 my $job = shift;
239 my $files = shift;
240 my $servers = shift;
241  
242 my %filemap;
243 my %bytes;
244 my @copies;
245  
246 my $load = _plan_map_these_servers( $job, $servers );
247  
248 # divy files up among servers
249 for my $f (sort { $b->{size} <=> $a->{size} } @$files){
250 my($best_wgt, $best_loc);
251 for my $loc ( @{$f->{location}} ){
252 next unless exists $load->{$loc}; # down?
253 next unless $load->{$loc}{use};
254 my $w = (1 + $bytes{$loc}) * (1 + $load->{$loc}{metric});
255 if( !$best_loc || $w < $best_wgt ){
256 $best_wgt = $w;
257 $best_loc = $loc;
258 }
259 }
260  
261 if( $best_loc ){
262 # a server has the file. process it there.
263 push @{$filemap{$best_loc}}, $f;
264 $bytes{$best_loc} += $f->{size};
265 next;
266 }
267  
268 # pick best 2 servers
269 my($sa, $sb) =
270 map { $_->[1] }
271 sort{ $a->[0] <=> $b->[0] }
272 map { [(1 + $bytes{$_}) * (1 + $load->{$_}{metric}), $_] }
273 grep { $load->{$_}{use} }
274 (keys %$load);
275  
276 # copy the file
277 my @loc = $sa;
278 push @loc, $sb if $sb;
279 my $newfile = "mrtmp/j_$job->{request}{jobid}/intmp_" . unique();
280 debug("no active servers have file: $f->{filename}, copying to @loc => $newfile");
281  
282 my $ff = {
283 filename => $newfile,
284 location => \@loc,
285 size => $f->{size},
286 };
287 push @{$filemap{$sa}}, $ff;
288 $bytes{$sa} += $ff->{size};
289  
290 # need to copy this file from its current location to the server(s) that will run map on it
291 for my $loc (@loc){
292 push @copies, AC::MrGamoo::Job::XferInfo->new( $job,
293 id => unique(),
294 filename => $f->{filename},
295 dstname => $newfile,
296 size => $f->{size},
297 location => $f->{location},
298 dst => $loc,
299 );
300 }
301 }
302  
303 return (\%filemap, \@copies);
304 }
305  
306 1;