Yenta/Store/AE.pm untested

filter: Statementstmt 0.0% 0 / 299 Branchbran 0.0% 0 / 98 Conditioncond 0.0% 0 / 23 MC/DCmcdc 0.0% 0 / 14 Subroutinesub 0.0% 0 / 31 Podpod 0.0% 0 / 20 totaltotal 0.0% 0 / 485 CC 50 SCAR 34.1
CC
50
Cov
0%
_init_peer
90.0
_pick_peer
56.0
_pick_map
42.0
CRAP 30.2
1 # -*- perl -*-
2  
3 # Copyright (c) 2009 AdCopy
4 # Author: Jeff Weisberg
5 # Created: 2009-Apr-03 10:05 (EDT)
6 # Function: Anti-Entropy (find missing/stale data, and sync up)
7 #
8 # $Id$
9  
10 package AC::Yenta::Store::AE;
11 use AC::Yenta::Store;
12 use AC::Yenta::Config;
13 use AC::Yenta::Debug 'ae';
14 use AC::Yenta::Stats;
15 use AC::Yenta::Conf;
16 use AC::Yenta::MySelf;
17 use AC::Yenta::Protocol;
18 use AC::DC::Sched;
19 use AC::Misc;
20 use Socket;
21 use strict;
22  
23 my $MAXGET = 32; # maximum number of records per fetch
24 my $MAXFILES = 4; # maximum number of files per fetch
25 my $MAXFETCH = 32; # maximum number of simultaneous fetches
26 my $MAXMISSING = 10; # maximum number of missing records to be considered up to date
27 my $MAXLOAD = 0.5; # do not run if load average is too high
28 my $EXPIRE = 300; # expire hung job after this long
29 my $TOONEW = 60; # don't consider things missing if they are less than this old
30  
31 my $msgid = $$;
32 my %DONE; # maps which have finished
33 my @AE; # normally, just one
34  
35 AC::DC::Sched->new(
36 info => 'anti-entropy',
37 freq => 60,
38 func => \&AC::Yenta::Store::AE::periodic,
39 );
40  
41 sub new {
42 my $class = shift;
43  
44 my $me = bless {
45 badnode => [ {version => 0, shard => 0, level => 0} ],
46 cache => {},
47 kvneed => [],
48 kvneedorig => [],
49 kvfetching => 0,
50 missing => 0,
51 }, $class;
52  
53 debug("new ae");
54 $me->_pick_map() || return;
55  
56 AC::Yenta::Store::store_set_internal($me->{map}, 'ae_last_start', $^T);
57 $me->_init_peer() || return;
58  
59 debug("checking $me->{map} with $me->{peer}{id}");
60 inc_stat('ae_runs');
61 $me->_next_step();
62  
63 push @AE, $me;
64 return $me;
65 }
66  
67 sub periodic {
68 # kill dead sessions, start new ones
69  
70 my @keep;
71 for my $ae (@AE){
72 if( $ae->{timestamp} + $EXPIRE > $^T ){
73 push @keep, $ae;
74 }
75 }
76 @AE = @keep;
77  
78 return if @AE;
79 return if loadave() > (conf_value('ae_maxload') || $MAXLOAD);
80 __PACKAGE__->new();
81 }
82  
83 # we are up to date if we have AE'ed every map at least once since starting
84 sub up_to_date {
85 my $class = shift;
86  
87 my $maps = conf_value('map');
88 for my $m (keys %$maps){
89 return 0 unless $DONE{$m};
90 }
91 return 1;
92 }
93  
94 ################################################################
95  
96 # find most stale map
97 sub _pick_map {
98 my $me = shift;
99  
100 my $maps = conf_value('map');
101 my(@best, $bestv);
102 for my $m (keys %$maps){
103 my $lt = AC::Yenta::Store::store_get_internal($m, 'ae_last_start');
104 if( !@best || $lt < $bestv ){
105 @best = $m;
106 $bestv = $lt;
107 }elsif( $lt == $bestv ){
108 push @best, $m;
109 }
110 }
111  
112 return unless @best;
113  
114 my $map = $best[ rand(@best) ];
115 $me->{map} = $map;
116  
117 # is this a data or file map?
118 # adjust accordingly
119 my $cf = conf_map( $map );
120 $me->{has_files} = 1 if $cf->{basedir};
121 $me->{maxget} = $me->{has_files} ? $MAXFILES : $MAXGET;
122 $me->{expire} = $cf->{expire};
123  
124 return 1;
125 }
126  
127 sub _init_peer {
128 my $me = shift;
129  
130 my $here = my_datacenter();
131 my @peer = AC::Yenta::Status->mappeers( $me->{map} );
132 my $env = conf_value('environment');
133  
134 my(@near, @far, @ood);
135  
136 for my $p (@peer){
137 my $d = AC::Yenta::Status->peer($p);
138 next unless $d->{environment} eq $env;
139 next unless $d->{status} == 200;
140  
141 if( $d->{uptodate} ){
142 if( $d->{datacenter} eq $here ){
143 push @near, $d;
144 }else{
145 push @far, $d;
146 }
147 }else{
148 push @ood, $d;
149 }
150 }
151  
152 $me->{peers_near} = \@near if @near;
153 $me->{peers_far} = \@far if @far;
154 $me->{peers_ood} = \@ood if @ood;
155  
156 my $peer = $me->_pick_peer();
157 return unless $peer;
158 $me->{peer} = $peer;
159 return 1;
160  
161 }
162  
163 sub _pick_peer {
164 my $me = shift;
165  
166 my @peer;
167 if( $me->{peers_near} && $me->{peers_far} ){
168 # prefer close peers, usually
169 if( int(rand(8)) ){
170 @peer = @{$me->{peers_near}};
171 }else{
172 @peer = @{$me->{peers_far}};
173 }
174 }elsif( $me->{peers_near} ){
175 @peer = @{$me->{peers_near}};
176 }elsif( $me->{peers_far} ){
177 @peer = @{$me->{peers_far}};
178 }elsif( $me->{peers_ood} ){
179 # only use out-of-date peers as a last resort
180 # NB: if we never used ood peers, we'd have a bootstrap deadlock
181 @peer = @{$me->{peers_ood}};
182 }
183  
184 return unless @peer;
185 my $peer = $peer[ rand(@peer) ];
186  
187 return $peer;
188 }
189  
190 ################################################################
191  
192 sub _finished {
193 my $me = shift;
194  
195 debug("finished $me->{map}");
196 $DONE{$me->{map}} = $^T if $me->{missing} < $MAXMISSING;
197 AC::Yenta::Store::store_set_internal($me->{map}, 'ae_last_finish', $^T);
198 @AE = grep{ $_ != $me } @AE;
199 }
200  
201 sub _next_step {
202 my $me = shift;
203  
204 $me->{timestamp} = $^T;
205  
206 if( $me->{kvfetching} < $MAXFETCH ){
207 # any missing data?
208 if( @{$me->{kvneedorig}} || @{$me->{kvneed}} ){
209 debug("starting nextgetkv ($me->{kvfetching})");
210 $me->_next_get_kv();
211 }
212 }
213  
214 # check nodes?
215 if( @{$me->{badnode}} ){
216 $me->_start_check();
217 return;
218 }
219  
220 $me->_finished();
221 }
222  
223 ################################################################
224  
225 sub _start_check {
226 my $me = shift;
227  
228 my $node = shift @{$me->{badnode}};
229 debug("checking next node: $me->{map} $node->{level}/$node->{version}");
230 inc_stat('ae_check_node');
231  
232 my $enc = use_encryption($me->{peer});
233 my $proto = AC::Yenta::Protocol->new( secret => conf_value('secret') );
234 my $request = $proto->encode_request( {
235 type => 'yenta_check',
236 msgidno => $msgid++,
237 want_reply => 1,
238 data_encrypted => $enc,
239 }, {
240 map => $me->{map},
241 level => $node->{level},
242 version => $node->{version},
243 shard => $node->{shard},
244 } );
245  
246 # connect + send
247 my $io = AC::Yenta::Kibitz::Store::Client->new(
248 $me->{peer}{ip}, undef,
249 $request,
250 info => "AE node $node->{level}/$node->{version} with $me->{peer}{id}" );
251  
252 if( $io ){
253 $io->set_callback('load', \&_check_load, $me);
254 $io->set_callback('error', \&_check_error, $me);
255 $io->start();
256 }
257  
258 }
259  
260 sub _check_load {
261 my $io = shift;
262 my $evt = shift;
263 my $me = shift;
264  
265  
266 debug("check results");
267 $evt->{data} ||= {};
268  
269 # determine highest level returned
270  
271 my @keydata;
272 my @nodedata;
273 my $maxlev = 0;
274  
275 for my $d ( @{ $evt->{data}{check} }){
276 debug("recvd result for $d->{map} $d->{level}/$d->{shard}/$d->{version} $d->{key}");
277  
278 if( $d->{key} ){
279 push @keydata, $d;
280 next;
281 }
282 next if $d->{level} < $maxlev;
283  
284 if( $d->{level} > $maxlev ){
285 @nodedata = ();
286 $maxlev = $d->{level};
287 }
288 push @nodedata, $d;
289 }
290  
291 if( @keydata ){
292 $me->_check_result_keys( \@keydata );
293 }elsif( @nodedata ){
294 $me->_check_result_nodes( $maxlev, \@nodedata );
295 }
296  
297 $me->_next_step();
298 }
299  
300 sub _check_error {
301 my $io = shift;
302 my $evt = shift;
303 my $me = shift;
304  
305 verbose("AE check error with $me->{peer}{id} map $me->{map} ($io->{info})");
306 $me->_next_step();
307 }
308  
309 sub _check_result_keys {
310 my $me = shift;
311 my $chk = shift;
312  
313 my %vscnt;
314 my %vsadd;
315  
316 for my $d (@$chk){
317 inc_stat('ae_check_key');
318 my $vsk = "$d->{version} $d->{shard}";
319 $vscnt{ $vsk } ++;
320  
321 next unless AC::Yenta::Store::store_want( $me->{map}, $d->{shard}, $d->{key}, $d->{version} );
322  
323 debug("missing data $d->{map}/$d->{key}/$d->{shard}/$d->{version}");
324 push @{$me->{kvneed}}, { key => $d->{key}, version => $d->{version}, shard => $d->{shard} };
325 inc_stat('ae_key_missing');
326 $me->{missing} ++;
327 $vsadd{ $vsk } ++;
328 }
329 }
330  
331 sub _is_expired {
332 my $me = shift;
333 my $map = shift;
334 my $lev = shift;
335 my $ver = shift;
336  
337 return unless $me->{expire};
338  
339 my $vmx = AC::Yenta::Store::store_version_max( $map, $ver, $lev );
340 return unless defined $vmx;
341  
342 if( $vmx < timet_to_yenta_version($^T - $me->{expire} + $TOONEW) ){
343 debug("skipping expired $lev/$ver - $vmx");
344 return 1;
345 }
346  
347 return;
348 }
349  
350 sub _check_result_nodes {
351 my $me = shift;
352 my $lev = shift;
353 my $chk = shift;
354  
355 # determine all of the base versions of the recvd data
356 my %ver;
357 for my $d (@$chk){
358 my($shard, $ver) = AC::Yenta::Store::store_normalize_version( $d->{map}, $d->{shard}, $d->{version}, $lev - 1);
359 $ver{"$ver $shard"} = { ver => $ver, shard => $shard };
360 }
361  
362 # get all of our merkle data for these versions
363 my %merkle;
364 my $t_new = timet_to_yenta_version($^T - $TOONEW);
365  
366 for my $d (values %ver){
367 next if $d->{ver} > $t_new; # too new, ignore
368 next if $me->_is_expired($me->{map}, $lev, $d->{ver});
369 # RSN - skip unwanted shards
370 my $ms = AC::Yenta::Store::store_get_merkle($me->{map}, $d->{shard}, $d->{ver}, $lev - 1);
371 for my $m (@$ms){
372 # debug("my hash $me->{map} $m->{level}/$m->{shard}/$m->{version} => $m->{hash}");
373 $merkle{"$m->{version} $m->{shard}"} = $m->{hash};
374 }
375 }
376  
377 # compare (don't bother with things that are too new (the data may still be en route))
378 for my $d (@$chk){
379 next if $d->{version} > $t_new; # too new, ignore
380 next if $me->_is_expired($me->{map}, $lev, $d->{version});
381 # RSN - skip unwanted shards
382 my $hash = $merkle{"$d->{version} $d->{shard}"};
383  
384 if( $d->{hash} eq $hash ){
385 debug("check $d->{level}/$d->{shard}/$d->{version}: $d->{hash} => match");
386 next;
387 }else{
388 debug("check $d->{level}/$d->{shard}/$d->{version}: $d->{hash} != $hash");
389 }
390  
391 # stick them at the front
392 unshift @{$me->{badnode}}, { version => $d->{version}, shard => $d->{shard}, level => $lev };
393 }
394 }
395  
396 ################################################################
397 # we try to spread the load out by picking a random peer to fetch from
398 # if that peer does not have the data, we retry using the original peer
399 # (the one that said it has the data)
400  
401 sub _next_get_kv {
402 my $me = shift;
403  
404 return $me->_start_get_kv_orig() if @{$me->{kvneedorig}};
405 return $me->_start_get_kv_any() if @{$me->{kvneed}};
406 }
407  
408 sub _start_get_kv_any {
409 my $me = shift;
410  
411 my @get = splice @{$me->{kvneed}}, 0, $me->{maxget}, ();
412  
413 # pick a peer
414 my $peer = $me->_pick_peer();
415 debug("getting kv data from peer $peer->{id}");
416 $me->_start_get_kv( $peer, 1, \@get);
417 }
418  
419 sub _start_get_kv_orig {
420 my $me = shift;
421  
422 my @get = splice @{$me->{kvneedorig}}, 0, $me->{maxget}, ();
423  
424 debug("getting kv data from current peer");
425 $me->_start_get_kv( $me->{peer}, 0, \@get);
426 }
427  
428 sub _start_get_kv {
429 my $me = shift;
430 my $peer = shift;
431 my $retry = shift;
432 my $get = shift;
433  
434 # insert map into request
435 $_->{map} = $me->{map} for @$get;
436  
437 # for (@$get){ debug("requesting $_->{key}/$_->{version}") }
438  
439 my $enc = use_encryption($peer);
440 my $proto = AC::Yenta::Protocol->new( secret => conf_value('secret') );
441  
442 # build request
443 my $request = $proto->encode_request( {
444 type => 'yenta_get',
445 msgidno => $msgid++,
446 want_reply => 1,
447 data_encrypted => $enc,
448 }, {
449 data => $get,
450 } );
451  
452 # connect + send
453 debug("sending to $peer->{id}");
454 my $io = AC::Yenta::Kibitz::Store::Client->new($peer->{ip}, undef, $request,
455 info => "AE getkv from $peer->{id}" );
456  
457 if( $io ){
458 $me->{kvfetching} ++;
459 $io->set_callback('load', \&_getkv_load, $me, $retry, $get);
460 $io->set_callback('error', \&_getkv_error, $me, $retry, $get);
461 $io->start();
462 }
463 }
464  
465 sub _getkv_load {
466 my $io = shift;
467 my $evt = shift;
468 my $me = shift;
469 my $retry = shift;
470 my $get = shift;
471  
472 $me->{kvfetching} --;
473 $evt->{data} ||= {};
474  
475 debug("got kv data results");
476  
477 my %need = map {
478 ( "$_->{key}/$_->{version}" => $_ )
479 } @$get;
480  
481 for my $d ( @{$evt->{data}{data}}){
482 debug("got $d->{map}/$d->{key}/$d->{version}");
483 next unless $d->{key} && $d->{version}; # not found
484  
485 delete $need{ "$d->{key}/$d->{version}" };
486 my $file = $evt->{content};
487 $file = \ $d->{file} if $d->{file};
488  
489 AC::Yenta::Store::store_put( $d->{map}, $d->{shard}, $d->{key}, $d->{version},
490 $d->{value}, $file, $d->{meta} );
491  
492 }
493  
494 push @{$me->{kvneedorig}}, (values %need) if $retry;
495  
496 $me->_next_get_kv();
497  
498 }
499  
500 sub _getkv_error {
501 my $io = shift;
502 my $evt = shift;
503 my $me = shift;
504 my $retry = shift;
505 my $get = shift;
506  
507 $me->{kvfetching} --;
508  
509 if( $retry ){
510 push @{$me->{kvneedorig}}, @$get;
511 }
512  
513 $me->_next_get_kv();
514 }
515  
516 1;