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