| 1 | # -*- perl -*- | ||
| 2 | |||
| 3 | # Copyright (c) 2009 AdCopy | ||
| 4 | # Author: Jeff Weisberg | ||
| 5 | # Created: 2009-Mar-30 19:21 (EDT) | ||
| 6 | # Function: storage maps | ||
| 7 | # | ||
| 8 | # $Id: Map.pm,v 1.30 2010/12/24 18:13:26 jaw Exp $ | ||
| 9 | |||
| 10 | package AC::Yenta::Store::Map; | ||
| 11 | use AC::Yenta::Store::File; | ||
| 12 | use AC::Yenta::Store::Merkle; | ||
| 13 | use AC::Yenta::Debug 'map'; | ||
| 14 | use AC::Yenta::Conf; | ||
| 15 | use strict; | ||
| 16 | |||
| 17 | our @ISA = 'AC::Yenta::Store::Merkle'; | ||
| 18 | |||
| 19 | my $DEFAULT = 'bdb'; | ||
| 20 | my %BACKEND ; | ||
| 21 | |||
| 22 | |||
| 23 | sub add_backend { | ||
| 24 | my $class = shift; | ||
| 25 | my $name = shift; | ||
| 26 | my $impl = shift; | ||
| 27 | |||
| 28 | $BACKEND{$name} = $impl; | ||
| 29 | } | ||
| 30 | |||
| 31 | sub new { | ||
| 32 | my $class = shift; | ||
| 33 | my $name = shift; | ||
| 34 | my $bkend = shift; | ||
| 35 | my $conf = shift; | ||
| 36 | |||
| 37 | my $c = $BACKEND{$bkend || $DEFAULT}; | ||
| 38 | unless( $c ){ | ||
| 39 | problem("invalid storage backend: $bkend - ignoring map"); | ||
| 40 | return ; | ||
| 41 | } | ||
| 42 | |||
| 43 | debug("configuring map $name with $c"); | ||
| 44 | |||
| 45 | my $db = $c->new( $name, $conf ); | ||
| 46 | my $fs = AC::Yenta::Store::File->new( $name, $conf ); | ||
| 47 | |||
| 48 | return bless { | ||
| 49 | name => $name, | ||
| 50 | conf => $conf, | ||
| 51 | db => $db, | ||
| 52 | fs => $fs, | ||
| 53 | merkle_height => 16, | ||
| 54 | }, $class; | ||
| 55 | } | ||
| 56 | |||
| 57 | sub get { | ||
| 58 | my $me = shift; | ||
| 59 | my $key = shift; | ||
| 60 | my $ver = shift; | ||
| 61 | |||
| 62 | my $db = $me->{db}; | ||
| 63 | |||
| 64 | my($versions, $foundver) = $db->get($me->{name}, 'vers', $key); | ||
| 65 | return unless $foundver; | ||
| 66 | my @versions = split /\s+/, $versions; | ||
| 67 | debug("found ver: @versions"); | ||
| 68 | |||
| 69 | if( $ver ){ | ||
| 70 | $ver = encode_version($ver); | ||
| 71 | return unless grep { $_ eq $ver } @versions; | ||
| 72 | }else{ | ||
| 73 | $ver = $versions[0]; | ||
| 74 | } | ||
| 75 | |||
| 76 | my $vk = $me->vkey($key, $ver); | ||
| 77 | my $extver = decode_version($ver); | ||
| 78 | |||
| 79 | my($data, $founddat) = $db->get($me->{name}, 'data', $vk); | ||
| 80 | |||
| 81 | if( wantarray ){ | ||
| 82 | if( $founddat ){ | ||
| 83 | my $meta = $db->get($me->{name}, 'meta', $vk); | ||
| 84 | my $file = $me->{fs}->get($data) if $data; | ||
| 85 | return( $data, $extver, $file, $meta ); | ||
| 86 | }else{ | ||
| 87 | # we don't have data, but we have it in history; fake it. | ||
| 88 | return (undef, $extver, undef, undef); | ||
| 89 | } | ||
| 90 | } | ||
| 91 | |||
| 92 | return $data; | ||
| 93 | } | ||
| 94 | |||
| 95 | # someone sent me something, do I want it? | ||
| 96 | sub want { | ||
| 97 | my $me = shift; | ||
| 98 | my $shard = shift; | ||
| 99 | my $key = shift; | ||
| 100 | my $ver = shift; | ||
| 101 | |||
| 102 | my $cf = $me->{conf}; | ||
| 103 | my $db = $me->{db}; | ||
| 104 | my $v = encode_version($ver); | ||
| 105 | |||
| 106 | # data belongs here? | ||
| 107 | return if $me->is_sharded() && !$me->is_my_shard($shard); | ||
| 108 | |||
| 109 | my $versions = $db->get($me->{name}, 'vers', $key); | ||
| 110 | my @versions = split /\s+/, $versions; | ||
| 111 | |||
| 112 | # I have it? | ||
| 113 | return if grep { $_ eq $v } @versions; | ||
| 114 | |||
| 115 | # expired? | ||
| 116 | return if $cf->{expire} && ($ver < timet_to_yenta_version($^T - $cf->{expire})); | ||
| 117 | |||
| 118 | # I want everything? | ||
| 119 | return 1 unless $cf->{history}; | ||
| 120 | |||
| 121 | # I have room for it? | ||
| 122 | return 1 if @versions < $cf->{history}; | ||
| 123 | |||
| 124 | # I can make room for it? | ||
| 125 | return 1 if $v gt $versions[-1]; | ||
| 126 | |||
| 127 | # I'll just throw it away. | ||
| 128 | return; | ||
| 129 | } | ||
| 130 | |||
| 131 | sub put { | ||
| 132 | my $me = shift; | ||
| 133 | my $shard = shift; | ||
| 134 | my $key = shift; | ||
| 135 | my $ver = shift; | ||
| 136 | my $data = shift; | ||
| 137 | my $file = shift; # reference | ||
| 138 | my $meta = shift; | ||
| 139 | |||
| 140 | my $cf = $me->{conf}; | ||
| 141 | my $db = $me->{db}; | ||
| 142 | my $v = encode_version($ver); | ||
| 143 | my $vk = $me->vkey($key, $v); | ||
| 144 | |||
| 145 | debug("storing $vk"); | ||
| 146 | |||
| 147 | # get version history | ||
| 148 | my @deletehist; | ||
| 149 | my @deletedata; | ||
| 150 | my $versions = $db->get($me->{name}, 'vers', $key); | ||
| 151 | my @versions = split /\s+/, $versions; | ||
| 152 | |||
| 153 | return if grep { $_ eq $v } @versions; # dupe! | ||
| 154 | |||
| 155 | # is this the newest version? should we save this data? | ||
| 156 | if( !@versions || ($v gt $versions[0]) || $cf->{keepold} ){ | ||
| 157 | |||
| 158 | # save file; data is filename | ||
| 159 | if( $file ){ | ||
| 160 | my $r = $me->{fs}->put($data, $file); | ||
| 161 | return unless $r; | ||
| 162 | } | ||
| 163 | # put meta + data | ||
| 164 | $db->put($me->{name}, 'meta', $vk, $meta) if length $meta; | ||
| 165 | $db->put($me->{name}, 'data', $vk, $data); | ||
| 166 | |||
| 167 | unless( $cf->{keepold} ){ | ||
| 168 | # unless we are keeping old data, remove previous version | ||
| 169 | push @deletedata, $versions[0] if @versions; | ||
| 170 | } | ||
| 171 | } | ||
| 172 | |||
| 173 | # add new version to list. newest 1st | ||
| 174 | @versions = sort {$b cmp $a} (@versions, $v); | ||
| 175 | if( $cf->{history} && @versions > $cf->{history} ){ | ||
| 176 | # trim list | ||
| 177 | my @rm = splice @versions, $cf->{history}, @versions, (); | ||
| 178 | push @deletehist, (map { ({version => decode_version($_), key => $key, shard => $shard}) } @rm); | ||
| 179 | push @deletedata, @rm; | ||
| 180 | } | ||
| 181 | $versions = join(' ', @versions); | ||
| 182 | if( $me->is_sharded() ){ | ||
| 183 | # QQQ - shard changed? | ||
| 184 | $db->put($me->{name}, 'shard', $key, encode_shard($shard || 0)); | ||
| 185 | } | ||
| 186 | |||
| 187 | my $dd = join(' ', map { $_->{version} } @deletehist); | ||
| 188 | debug("version list: $versions [delete: $dd]"); | ||
| 189 | |||
| 190 | $db->put($me->{name}, 'vers', $key, $versions); | ||
| 191 | |||
| 192 | # update merkles | ||
| 193 | $me->merkle( { shard => $shard, key => $key, version => $ver }, @deletehist); | ||
| 194 | |||
| 195 | # delete old data | ||
| 196 | for my $rm (@deletedata){ | ||
| 197 | debug("removing old version $key/$rm"); | ||
| 198 | my $rmvk = $me->vkey($key, $rm); | ||
| 199 | $db->del($me->{name}, 'data', $rmvk); | ||
| 200 | $db->del($me->{name}, 'meta', $rmvk); | ||
| 201 | } | ||
| 202 | |||
| 203 | $db->sync(); | ||
| 204 | |||
| 205 | return 1; | ||
| 206 | } | ||
| 207 | |||
| 208 | sub remove { | ||
| 209 | my $me = shift; | ||
| 210 | my $key = shift; | ||
| 211 | my $ver = shift; | ||
| 212 | |||
| 213 | my $shard = $me->_remove( $key, $ver ); | ||
| 214 | $me->merkle( undef, { shard => decode_shard($shard), key => $key, version => $ver } ); | ||
| 215 | $me->{db}->sync(); | ||
| 216 | |||
| 217 | return 1; | ||
| 218 | } | ||
| 219 | |||
| 220 | # NB: does not update merkle tree | ||
| 221 | sub _remove { | ||
| 222 | my $me = shift; | ||
| 223 | my $key = shift; | ||
| 224 | my $ver = shift; | ||
| 225 | |||
| 226 | my $db = $me->{db}; | ||
| 227 | my $v = encode_version($ver); | ||
| 228 | |||
| 229 | my $cshard = $db->get($me->{name}, 'shard', $key); | ||
| 230 | my $versions = $db->get($me->{name}, 'vers', $key); | ||
| 231 | my @versions = grep { $_ ne $v } split /\s+/, $versions; | ||
| 232 | $versions = join(' ', @versions); | ||
| 233 | debug("new ver list: $versions"); | ||
| 234 | |||
| 235 | if( $versions ){ | ||
| 236 | $db->put($me->{name}, 'vers', $key, $versions); | ||
| 237 | }else{ | ||
| 238 | $db->del($me->{name}, 'vers', $key); | ||
| 239 | $db->del($me->{name}, 'shard', $key); | ||
| 240 | } | ||
| 241 | |||
| 242 | my $vk = $me->vkey($key, $ver); | ||
| 243 | $db->del($me->{name}, 'data', $vk); | ||
| 244 | $db->del($me->{name}, 'meta', $vk); | ||
| 245 | |||
| 246 | return $cshard; | ||
| 247 | } | ||
| 248 | |||
| 249 | ################################################################ | ||
| 250 | |||
| 251 | sub range { | ||
| 252 | my $me = shift; | ||
| 253 | my $start = shift; | ||
| 254 | my $end = shift; | ||
| 255 | |||
| 256 | my $db = $me->{db}; | ||
| 257 | return $db->range($me->{name}, 'vers', $start, $end); | ||
| 258 | } | ||
| 259 | |||
| 260 | ################################################################ | ||
| 261 | |||
| 262 | sub get_internal { | ||
| 263 | my $me = shift; | ||
| 264 | my $key = shift; | ||
| 265 | |||
| 266 | my($d, $found) = $me->{db}->get($me->{name}, 'internal', $key); | ||
| 267 | return $d; | ||
| 268 | } | ||
| 269 | |||
| 270 | sub set_internal { | ||
| 271 | my $me = shift; | ||
| 272 | my $key = shift; | ||
| 273 | my $val = shift; | ||
| 274 | |||
| 275 | $me->{db}->put($me->{name}, 'internal', $key, $val); | ||
| 276 | } | ||
| 277 | |||
| 278 | ################################################################ | ||
| 279 | |||
| 280 | sub expire { | ||
| 281 | my $me = shift; | ||
| 282 | my $expire = shift; | ||
| 283 | |||
| 284 | debug("expiring $me->{name}"); | ||
| 285 | |||
| 286 | my $db = $me->{db}; | ||
| 287 | |||
| 288 | # walk merkle tree, find all k/v to remove | ||
| 289 | my @delete; | ||
| 290 | |||
| 291 | my @walk = { level => 0, version => 0, shard => 0 }; | ||
| 292 | while(@walk){ | ||
| 293 | my @next; | ||
| 294 | for my $node (@walk){ | ||
| 295 | my $res = $me->get_merkle( $node->{shard}, $node->{version}, $node->{level} ); | ||
| 296 | |||
| 297 | for my $r (@$res){ | ||
| 298 | next if $r->{version} > $expire; | ||
| 299 | if( $r->{key} ){ | ||
| 300 | push @delete, { key => $r->{key}, version => $r->{version}, shard => $r->{shard} }; | ||
| 301 | }else{ | ||
| 302 | push @next, $r; | ||
| 303 | } | ||
| 304 | } | ||
| 305 | } | ||
| 306 | @walk = @next; | ||
| 307 | } | ||
| 308 | |||
| 309 | # remove k/v | ||
| 310 | for my $r (@delete){ | ||
| 311 | debug("expiring $r->{key}/$r->{version}"); | ||
| 312 | $me->_remove( $r->{key}, $r->{version} ); | ||
| 313 | } | ||
| 314 | |||
| 315 | # update merkle | ||
| 316 | $me->merkle(undef, @delete); | ||
| 317 | |||
| 318 | $db->sync(); | ||
| 319 | } | ||
| 320 | |||
| 321 | ################################################################ | ||
| 322 | |||
| 323 | sub vkey { | ||
| 324 | my $me = shift; | ||
| 325 | my $k = shift; | ||
| 326 | my $v = shift; | ||
| 327 | |||
| 328 | return "$v/$k"; | ||
| 329 | } | ||
| 330 | |||
| 331 | ################################################################ | ||
| 332 | |||
| 333 | sub is_sharded { | ||
| 334 | return 0; | ||
| 335 | } | ||
| 336 | |||
| 337 | sub is_my_shard { | ||
| 338 | return 1; | ||
| 339 | } | ||
| 340 | |||
| 341 | |||
| 342 | 1; | ||
| 343 | |||
| 344 | =head1 NAME | ||
| 345 | |||
| 346 | AC::Yenta::Store::Map - persistent storage for yenta maps | ||
| 347 | |||
| 348 | =head1 SYNOPSIS | ||
| 349 | |||
| 350 | your code: | ||
| 351 | |||
| 352 | AC::Yenta::Store::Map->add_backend( postgres => 'Local::Yenta::Postgres' ); | ||
| 353 | |||
| 354 | your config: | ||
| 355 | |||
| 356 | map mappyfoo { | ||
| 357 | backend postgres | ||
| 358 | # ... | ||
| 359 | } | ||
| 360 | |||
| 361 | =cut | ||
| 362 |