| 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: AE.pm,v 1.26 2011/01/12 19:13:29 jaw Exp $ | ||
| 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; |