| 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; |