| 1 | # -*- perl -*- | ||
| 2 | |||
| 3 | # Copyright (c) 2010 AdCopy | ||
| 4 | # Author: Jeff Weisberg | ||
| 5 | # Created: 2010-Jun-07 17:34 (EDT) | ||
| 6 | # Function: consistently-hashed shards (unfinished) | ||
| 7 | # | ||
| 8 | # $Id: Sharded.pm,v 1.7 2010/12/23 19:09:39 jaw Exp $ | ||
| 9 | |||
| 10 | |||
| 11 | package AC::Yenta::Store::Sharded; | ||
| 12 | use AC::Yenta::Debug 'map'; | ||
| 13 | use AC::Yenta::Config; | ||
| 14 | use strict; | ||
| 15 | |||
| 16 | our @ISA = 'AC::Yenta::Store::Map'; | ||
| 17 | |||
| 18 | # using too large a size, makes the tree heavy at the top, thin at the bottom | ||
| 19 | # taking up more space, and slowing down AE | ||
| 20 | my $SHARDLEN = 5; | ||
| 21 | |||
| 22 | sub new { | ||
| 23 | my $class = shift; | ||
| 24 | my $name = shift; | ||
| 25 | my $bend = shift; | ||
| 26 | my $conf = shift; | ||
| 27 | |||
| 28 | # die "nyi\n"; | ||
| 29 | my $me = $class->SUPER::new( $name, $bend, $conf ); | ||
| 30 | $me->{merkle_height} = 16 + $SHARDLEN; | ||
| 31 | return $me; | ||
| 32 | } | ||
| 33 | |||
| 34 | sub _shver_lev { | ||
| 35 | my $me = shift; | ||
| 36 | my $ver = shift; | ||
| 37 | my $lev = shift; | ||
| 38 | |||
| 39 | return substr($ver, 0, $lev) . ('0' x (16 - $lev)); | ||
| 40 | } | ||
| 41 | |||
| 42 | sub _mkey { | ||
| 43 | my $me = shift; | ||
| 44 | my $shard = shift; | ||
| 45 | my $ver = shift; | ||
| 46 | my $lev = shift; | ||
| 47 | |||
| 48 | # L/<S & mask>:V | ||
| 49 | |||
| 50 | # least significant only | ||
| 51 | $shard = ('0' x (16 - $SHARDLEN)) . substr($shard, - $SHARDLEN); | ||
| 52 | |||
| 53 | if( $lev == $me->{merkle_height} ){ | ||
| 54 | return sprintf '%02X/%s:%s', $lev, $shard, $ver; | ||
| 55 | } | ||
| 56 | |||
| 57 | if( $lev >= $SHARDLEN ){ | ||
| 58 | return sprintf '%02X/%s:%s', $lev, $shard, $me->_shver_lev($ver, $lev - $SHARDLEN); | ||
| 59 | } | ||
| 60 | |||
| 61 | return sprintf '%02X/%s:%s', $lev, $me->_shver_lev($shard, 16 + $lev - $SHARDLEN), ('0' x 16); | ||
| 62 | } | ||
| 63 | |||
| 64 | sub _decode_mkey { | ||
| 65 | my $me = shift; | ||
| 66 | my $mk = shift; | ||
| 67 | |||
| 68 | # 20/8843d7f92416211d:0000000049D2A314 | ||
| 69 | my($l,$sv) = split m|/|, $mk, 2; | ||
| 70 | my($s,$v) = split /:/, $sv, 2; | ||
| 71 | return ($l, $s, $v); | ||
| 72 | } | ||
| 73 | |||
| 74 | sub _lkey { | ||
| 75 | my $me = shift; | ||
| 76 | my $k = shift; | ||
| 77 | my $v = shift; | ||
| 78 | my $s = shift; | ||
| 79 | |||
| 80 | return "$s:$v/$k"; | ||
| 81 | } | ||
| 82 | |||
| 83 | |||
| 84 | sub _decode_lkey { | ||
| 85 | my $me = shift; | ||
| 86 | my $lk = shift; | ||
| 87 | |||
| 88 | # 8843d7f92416211d:0000000049D2A314/acso | ||
| 89 | my($sv, $k) = split m|/|, $lk, 2; | ||
| 90 | # shard, version, key | ||
| 91 | return ((split /:/, $sv), $k); | ||
| 92 | } | ||
| 93 | |||
| 94 | sub is_sharded { | ||
| 95 | return 1; | ||
| 96 | } | ||
| 97 | |||
| 98 | sub is_my_shard { | ||
| 99 | # XXX | ||
| 100 | return 1; | ||
| 101 | } | ||
| 102 | |||
| 103 | ################################################################ | ||
| 104 | |||
| 105 | sub normalize_version { | ||
| 106 | my $me = shift; | ||
| 107 | my $shard = shift; | ||
| 108 | my $ver = shift; | ||
| 109 | my $lev = shift; | ||
| 110 | |||
| 111 | my($ns, $nv); | ||
| 112 | if( $lev <= $SHARDLEN ){ | ||
| 113 | my $n = ($SHARDLEN - $lev) * 4; | ||
| 114 | $ns = ($shard >> $n) << $n; | ||
| 115 | $nv = 0; | ||
| 116 | }else{ | ||
| 117 | $ns = $shard; | ||
| 118 | my $n = ($me->{merkle_height} - $lev) * 4; | ||
| 119 | my $nv = ($ver >> $n) << $n; | ||
| 120 | } | ||
| 121 | return ($ns, $nv); | ||
| 122 | } | ||
| 123 | |||
| 124 | sub version_max { | ||
| 125 | my $me = shift; | ||
| 126 | my $ver = shift; | ||
| 127 | my $lev = shift; | ||
| 128 | |||
| 129 | my $bm = _version_max_bitmask(); | ||
| 130 | return $bm if $lev <= $SHARDLEN; | ||
| 131 | $bm >>= (($lev - $SHARDLEN) * 4); | ||
| 132 | return $ver | $bm; | ||
| 133 | } | ||
| 134 | |||
| 135 | |||
| 136 | 1; |