| 1 | # -*- perl -*- | ||
| 2 | |||
| 3 | # Copyright (c) 2010 AdCopy | ||
| 4 | # Author: Jeff Weisberg | ||
| 5 | # Created: 2010-Jun-01 18:11 (EDT) | ||
| 6 | # Function: merkle tree for detecting missing data | ||
| 7 | # | ||
| 8 | # $Id$ | ||
| 9 | |||
| 10 | package AC::Yenta::Store::Merkle; | ||
| 11 | use AC::Yenta::Debug 'merkle'; | ||
| 12 | use AC::Yenta::SixtyFour; | ||
| 13 | use AC::Cache; | ||
| 14 | use AC::Import; | ||
| 15 | use Digest::SHA 'sha1_base64'; | ||
| 16 | use strict; | ||
| 17 | |||
| 18 | our @EXPORT = qw(encode_version decode_version encode_shard decode_shard); | ||
| 19 | |||
| 20 | my $CACHESIZE = 256; | ||
| 21 | |||
| 22 | sub merkle_init { | ||
| 23 | my $me = shift; | ||
| 24 | |||
| 25 | $me->{merkle_cache} = AC::Cache->new( $CACHESIZE ); | ||
| 26 | } | ||
| 27 | |||
| 28 | my($cachechk, $cachemiss, $cacheT); | ||
| 29 | |||
| 30 | sub _mcget { | ||
| 31 | my $me = shift; | ||
| 32 | my $mk = shift; | ||
| 33 | |||
| 34 | $cachechk++; | ||
| 35 | my $d = $me->{merkle_cache}->fetch( $mk ); | ||
| 36 | return $d if $d; | ||
| 37 | $cachemiss ++; | ||
| 38 | |||
| 39 | my $db = $me->{db}; | ||
| 40 | return $db->get($me->{name}, 'merkle', $mk); | ||
| 41 | } | ||
| 42 | |||
| 43 | sub _mcput { | ||
| 44 | my $me = shift; | ||
| 45 | my $mk = shift; | ||
| 46 | my $d = shift; | ||
| 47 | |||
| 48 | my $db = $me->{db}; | ||
| 49 | $db->put($me->{name}, 'merkle', $mk, $d); | ||
| 50 | $me->{merkle_cache}->store( $mk, $d ); | ||
| 51 | } | ||
| 52 | |||
| 53 | sub _mcdel { | ||
| 54 | my $me = shift; | ||
| 55 | my $mk = shift; | ||
| 56 | |||
| 57 | my $db = $me->{db}; | ||
| 58 | $db->del($me->{name}, 'merkle', $mk); | ||
| 59 | $me->{merkle_cache}->remove( $mk ); | ||
| 60 | |||
| 61 | } | ||
| 62 | |||
| 63 | sub get_merkle { | ||
| 64 | my $me = shift; | ||
| 65 | my $shard = shift; | ||
| 66 | my $ver = shift; | ||
| 67 | my $lev = shift; | ||
| 68 | |||
| 69 | return if $lev > $me->{merkle_height}; | ||
| 70 | |||
| 71 | my $db = $me->{db}; | ||
| 72 | my $mk = $me->_mkey(encode_shard($shard), encode_version($ver), $lev); | ||
| 73 | debug("getting merkle for $mk"); | ||
| 74 | |||
| 75 | my $d = $me->_mcget( $mk ); | ||
| 76 | return unless $d; | ||
| 77 | my @d = split /\0/, $d; | ||
| 78 | |||
| 79 | my @res; | ||
| 80 | |||
| 81 | if( $^T - $cacheT > 60 ){ | ||
| 82 | debug("merk cache stats: check: $cachechk, miss: $cachemiss") if $cachechk > 1; | ||
| 83 | $cacheT = $^T; | ||
| 84 | } | ||
| 85 | |||
| 86 | if( $lev == $me->{merkle_height} ){ | ||
| 87 | # data is: lkey, ... | ||
| 88 | for my $r (@d){ | ||
| 89 | my($s,$v,$k) = $me->_decode_lkey($r); | ||
| 90 | push @res, { version => decode_version($v), key => $k, count => 1, shard => decode_shard($s) }; | ||
| 91 | } | ||
| 92 | }else{ | ||
| 93 | # data is: mkey => hash count, ... | ||
| 94 | my %d = @d; | ||
| 95 | for my $lv (keys %d){ | ||
| 96 | my($l, $s, $v) = $me->_decode_mkey( $lv ); | ||
| 97 | my($h,$c) = split /\s/, $d{$lv}; | ||
| 98 | push @res, { version => decode_version($v), level => hex($l), hash => $h, count => $c, shard => decode_shard($s) }; | ||
| 99 | } | ||
| 100 | } | ||
| 101 | |||
| 102 | return \@res; | ||
| 103 | } | ||
| 104 | |||
| 105 | ################################################################ | ||
| 106 | # we maintain a 16-ary merkle tree of all of the <key,version>s we have stored | ||
| 107 | |||
| 108 | sub merkle { | ||
| 109 | my $me = shift; | ||
| 110 | my $add = shift; | ||
| 111 | my @del = @_; | ||
| 112 | |||
| 113 | # update leaf nodes | ||
| 114 | my %todo; | ||
| 115 | for my $rm (@del){ | ||
| 116 | my($ns,$nv,$h,$c) = $me->_merkle_leaf_del(encode_shard($rm->{shard}), $rm->{key}, encode_version($rm->{version})); | ||
| 117 | $todo{"$ns $nv"} = { ver => $nv, hash => $h, count => $c, shard => $ns }; | ||
| 118 | } | ||
| 119 | if( defined $add ){ | ||
| 120 | my($ns,$nv,$h,$c) = $me->_merkle_leaf_add(encode_shard($add->{shard}), $add->{key}, encode_version($add->{version})); | ||
| 121 | $todo{"$ns $nv"} = { ver => $nv, hash => $h, count => $c, shard => $ns }; | ||
| 122 | } | ||
| 123 | |||
| 124 | # update upper levels | ||
| 125 | my $level = $me->{merkle_height}; | ||
| 126 | |||
| 127 | while($level >= 0 && keys %todo){ | ||
| 128 | my %next = %todo; | ||
| 129 | %todo = (); | ||
| 130 | |||
| 131 | for my $hd (values %next){ | ||
| 132 | # update level - 1 with hash | ||
| 133 | # put level-1 hash into todo | ||
| 134 | my($ns, $nv, $h, $c) = $me->_merkle_update( $hd->{shard}, $level, $hd->{ver}, $hd->{hash}, $hd->{count} ); | ||
| 135 | $todo{"$ns $nv"} = { ver => $nv, hash => $h, count => $c, shard => $ns } if defined $nv; | ||
| 136 | } | ||
| 137 | $level --; | ||
| 138 | } | ||
| 139 | } | ||
| 140 | |||
| 141 | # non-leaf node: | ||
| 142 | # list of (ver => hash+count) | ||
| 143 | # of up to 16 next-level-down vers | ||
| 144 | # \0 delimited, sorted by ver | ||
| 145 | |||
| 146 | # update merkle node | ||
| 147 | sub _merkle_update { | ||
| 148 | my $me = shift; | ||
| 149 | my $shard = shift; | ||
| 150 | my $lev = shift; | ||
| 151 | my $ver = shift; | ||
| 152 | my $hash = shift; | ||
| 153 | my $count = shift; | ||
| 154 | |||
| 155 | my $db = $me->{db}; | ||
| 156 | |||
| 157 | my $k0 = $me->_mkey($shard, $ver, $lev); | ||
| 158 | my $k1 = $me->_mkey($shard, $ver, $lev - 1); | ||
| 159 | |||
| 160 | my(undef, $nextshard, $nextver) = $me->_decode_mkey($k1); | ||
| 161 | |||
| 162 | unless( $lev ){ | ||
| 163 | # root hash - not used | ||
| 164 | debug("updating merkle node root => $hash"); | ||
| 165 | $me->_mcput( 'root', $hash ); | ||
| 166 | return; | ||
| 167 | } | ||
| 168 | |||
| 169 | # get node | ||
| 170 | my $d = $me->_mcget( $k1 ); | ||
| 171 | my $oldh = sha1_base64($d); | ||
| 172 | my %d = split /\0/, $d; | ||
| 173 | |||
| 174 | if($hash){ | ||
| 175 | # add/update | ||
| 176 | debug("updating merkle node $k1 + { $k0 => $hash, $count }"); | ||
| 177 | $d{$k0} = "$hash $count"; | ||
| 178 | }else{ | ||
| 179 | # remove | ||
| 180 | debug("updating merkle node $k1 - { $k0 => empty }"); | ||
| 181 | delete $d{$k0}; | ||
| 182 | } | ||
| 183 | |||
| 184 | if( keys %d ){ | ||
| 185 | |||
| 186 | $d = join("\0", map {"$_\0$d{$_}"} (sort keys %d)); | ||
| 187 | $me->_mcput( $k1, $d ); | ||
| 188 | my $newh = sha1_base64($d); | ||
| 189 | return if $newh eq $oldh; # unchanged | ||
| 190 | return ($nextshard, $nextver, $newh, scalar keys %d); | ||
| 191 | }else{ | ||
| 192 | $me->_mcdel( $k1 ); | ||
| 193 | return unless $oldh; # unchanged | ||
| 194 | return ($nextshard, $nextver, undef); | ||
| 195 | } | ||
| 196 | } | ||
| 197 | |||
| 198 | # leaf nodes: | ||
| 199 | # list of all "ver/key" | ||
| 200 | # \0 delimited. sorted by "ver/key" | ||
| 201 | |||
| 202 | # add new <key,version> to merkle leaf | ||
| 203 | sub _merkle_leaf_add { | ||
| 204 | my $me = shift; | ||
| 205 | my $shard = shift; | ||
| 206 | my $key = shift; | ||
| 207 | my $ver = shift; | ||
| 208 | |||
| 209 | my $db = $me->{db}; | ||
| 210 | my $mk = $me->_mkey($shard, $ver, $me->{merkle_height}); | ||
| 211 | my $vk = $me->_lkey($key, $ver, $shard); | ||
| 212 | |||
| 213 | debug("adding to merkle leaf $mk - $vk"); | ||
| 214 | |||
| 215 | # get current data | ||
| 216 | my $d = $me->_mcget( $mk ); | ||
| 217 | my @d = split /\0/, $d; | ||
| 218 | # append new item + uniqify | ||
| 219 | my %d; | ||
| 220 | @d{@d} = (); | ||
| 221 | $d{$vk} = undef; | ||
| 222 | $d = join("\0", sort keys %d); | ||
| 223 | $me->_mcput( $mk, $d ); | ||
| 224 | |||
| 225 | my $hash = sha1_base64($d); | ||
| 226 | return ($shard, $ver, $hash, scalar keys %d); | ||
| 227 | } | ||
| 228 | |||
| 229 | # remove <key,version> from merkle leaf | ||
| 230 | sub _merkle_leaf_del { | ||
| 231 | my $me = shift; | ||
| 232 | my $shard = shift; | ||
| 233 | my $key = shift; | ||
| 234 | my $ver = shift; | ||
| 235 | |||
| 236 | my $db = $me->{db}; | ||
| 237 | my $mk = $me->_mkey($shard, $ver, $me->{merkle_height}); | ||
| 238 | my $vk = $me->_lkey($key, $ver, $shard); | ||
| 239 | |||
| 240 | debug("removing from merkle leaf $mk - $vk"); | ||
| 241 | |||
| 242 | # get current data | ||
| 243 | my $d = $me->_mcget( $mk ); | ||
| 244 | my @d = split /\0/, $d; | ||
| 245 | # remove item | ||
| 246 | @d = grep { $vk ne $_ } @d; | ||
| 247 | |||
| 248 | if( @d ){ | ||
| 249 | $d = join("\0", @d); | ||
| 250 | $me->_mcput( $mk, $d ); | ||
| 251 | |||
| 252 | my $hash = sha1_base64($d); | ||
| 253 | return ($shard, $ver, $hash, scalar @d); | ||
| 254 | }else{ | ||
| 255 | $me->_mcdel( $mk ); | ||
| 256 | # empty node => empty hash | ||
| 257 | return ($shard, $ver, undef); | ||
| 258 | } | ||
| 259 | } | ||
| 260 | |||
| 261 | ################################################################ | ||
| 262 | |||
| 263 | sub _get_actual_keys { | ||
| 264 | my $me = shift; | ||
| 265 | my $shard = shift; | ||
| 266 | my $ver = shift; | ||
| 267 | |||
| 268 | my $db = $me->{db}; | ||
| 269 | |||
| 270 | # get range on data | ||
| 271 | my @key = map { | ||
| 272 | my $k = $_->{k}; $k =~ s|.*/||; $k | ||
| 273 | } $db->range($me->{name}, 'data', encode_version($ver), encode_version($ver + 1)); | ||
| 274 | debug("actual key: @key"); | ||
| 275 | |||
| 276 | return @key unless defined $shard; | ||
| 277 | |||
| 278 | # get vers list to filter on shard | ||
| 279 | my $sh = encode_shard($shard); | ||
| 280 | return grep { | ||
| 281 | my $k = $_; | ||
| 282 | |||
| 283 | my $vl = $db->get($me->{name}, 'vers', $k); | ||
| 284 | my($s) = $vl =~ /;\s*(.*)/; | ||
| 285 | |||
| 286 | $s == $sh; | ||
| 287 | } @key; | ||
| 288 | } | ||
| 289 | |||
| 290 | # check merkle leaf node against actual data | ||
| 291 | sub merkle_scrub { | ||
| 292 | my $me = shift; | ||
| 293 | my $shard = shift; | ||
| 294 | my $ver = shift; | ||
| 295 | |||
| 296 | debug("scrub $me->{name} $shard/$ver"); | ||
| 297 | |||
| 298 | # get list of keys from merkle leaf node | ||
| 299 | my $mlist = $me->get_merkle($shard, $ver, $me->{merkle_height}) || []; | ||
| 300 | my @mkey = map { $_->{key} } @$mlist; | ||
| 301 | my %mkey; | ||
| 302 | @mkey{@mkey} = @mkey; | ||
| 303 | |||
| 304 | # get list of keys from actual data | ||
| 305 | my @akey = $me->_get_actual_keys( $shard, $ver ); | ||
| 306 | |||
| 307 | # compare lists | ||
| 308 | |||
| 309 | for my $k (@akey){ | ||
| 310 | next if $mkey{$k}; | ||
| 311 | debug("missing key in merkle tree: $shard/$ver/$k"); | ||
| 312 | $me->merkle( { key => $k, shard => $shard, version => $ver } ); | ||
| 313 | } | ||
| 314 | } | ||
| 315 | |||
| 316 | |||
| 317 | ################################################################ | ||
| 318 | |||
| 319 | sub _mkey { | ||
| 320 | my $me = shift; | ||
| 321 | my $shard = shift; | ||
| 322 | my $ver = shift; | ||
| 323 | my $lev = shift; | ||
| 324 | |||
| 325 | # 10/000484D6594DB72B | ||
| 326 | sprintf '%02X/%s', $lev, $me->_ver_lev($ver, $lev); | ||
| 327 | } | ||
| 328 | |||
| 329 | sub _decode_mkey { | ||
| 330 | my $me = shift; | ||
| 331 | my $mk = shift; | ||
| 332 | |||
| 333 | # 10/000484D6594DB72B | ||
| 334 | my($l,$sv) = split m|/|, $mk, 2; | ||
| 335 | # level, shard, version | ||
| 336 | return ($l, undef, $sv); | ||
| 337 | } | ||
| 338 | |||
| 339 | sub _lkey { | ||
| 340 | my $me = shift; | ||
| 341 | my $k = shift; | ||
| 342 | my $v = shift; | ||
| 343 | my $s = shift; | ||
| 344 | |||
| 345 | # 000484D6594DB72B/foobar | ||
| 346 | return "$v/$k"; | ||
| 347 | } | ||
| 348 | |||
| 349 | sub _decode_lkey { | ||
| 350 | my $me = shift; | ||
| 351 | my $lk = shift; | ||
| 352 | |||
| 353 | # 000484D6594DB72B/foobar | ||
| 354 | my($sv, $k) = split m|/|, $lk, 2; | ||
| 355 | # shard, version, key | ||
| 356 | return (undef, $sv, $k); | ||
| 357 | } | ||
| 358 | |||
| 359 | sub _ver_lev { | ||
| 360 | my $me = shift; | ||
| 361 | my $ver = shift; | ||
| 362 | my $lev = shift; | ||
| 363 | |||
| 364 | return substr($ver, 0, $lev) . ('0' x ($me->{merkle_height} - $lev)); | ||
| 365 | } | ||
| 366 | |||
| 367 | ################################################################ | ||
| 368 | |||
| 369 | sub encode_version { | ||
| 370 | my $v = shift; | ||
| 371 | return x64_number_to_hex($v); | ||
| 372 | } | ||
| 373 | |||
| 374 | sub decode_version { | ||
| 375 | my $v = shift; | ||
| 376 | return x64_hex_to_number($v); | ||
| 377 | } | ||
| 378 | |||
| 379 | sub encode_shard { | ||
| 380 | my $v = shift; | ||
| 381 | return undef unless defined $v; | ||
| 382 | return x64_number_to_hex($v); | ||
| 383 | } | ||
| 384 | |||
| 385 | sub decode_shard { | ||
| 386 | my $v = shift; | ||
| 387 | return undef unless defined $v; | ||
| 388 | return x64_hex_to_number($v); | ||
| 389 | } | ||
| 390 | |||
| 391 | sub _version_max_bitmask { | ||
| 392 | return x64_sixty_four_ones(); | ||
| 393 | } | ||
| 394 | |||
| 395 | |||
| 396 | # numeric version + level => numeric version | ||
| 397 | sub normalize_version { | ||
| 398 | my $me = shift; | ||
| 399 | my $shard = shift; | ||
| 400 | my $ver = shift; | ||
| 401 | my $lev = shift; | ||
| 402 | |||
| 403 | my $n = ($me->{merkle_height} - $lev) * 4; | ||
| 404 | my $nv = ($ver >> $n) << $n; | ||
| 405 | return (undef, $nv); | ||
| 406 | } | ||
| 407 | |||
| 408 | sub version_max { | ||
| 409 | my $me = shift; | ||
| 410 | my $ver = shift; | ||
| 411 | my $lev = shift; | ||
| 412 | |||
| 413 | my $bm = _version_max_bitmask() >> ($lev * 4); | ||
| 414 | return $ver | $bm; | ||
| 415 | } | ||
| 416 | |||
| 417 | |||
| 418 | 1; |