Yenta/Store/Merkle.pm untested

filter: Statementstmt 0.0% 0 / 229 Branchbran 0.0% 0 / 36 Conditioncond 0.0% 0 / 5 MC/DCmcdc 0.0% 0 / 3 Subroutinesub 0.0% 0 / 29 Podpod 0.0% 0 / 23 totaltotal 0.0% 0 / 325 CC 19 SCAR 26.3
CC
19
Cov
0%
get_merkle
42.0
_merkle_update
42.0
merkle
12.0
CRAP 13.9
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;