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