Yenta/Store/Merkle.pm untested

filter: Statementstmt 0.0% 0 / 200 Branchbran 0.0% 0 / 30 Conditioncond 0.0% 0 / 5 Subroutinesub 0.0% 0 / 24 Podpod 0.0% 0 / 19 totaltotal 0.0% 0 / 278 CC 16 SCAR 24.7
CC
16
Cov
0%
_merkle_update
42.0
get_merkle
20.0
merkle
12.0
CRAP 11.8
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;