| 1 | 2 | ▶ | use strict; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 2 | 2 | ▶ | use 5.010; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 3 | |||||||||||
| 4 | package FusqlFS::Cache::Limited; | ||||||||||
| 5 | 2 | ▶ | use FusqlFS::Version; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 6 | our $VERSION = $FusqlFS::Version::VERSION; | ||||||||||
| 7 | 2 | ▶ | use parent 'FusqlFS::Cache::Base'; | ||||||||
|
Subroutine
BEGIN: called CC=1 SCAR=0.0
| |||||||||||
| 8 | |||||||||||
| 9 | =head1 NAME | ||||||||||
| 10 | |||||||||||
| 11 | FusqlFS::Cache::Limited - FusqlFS limited cache strategy implementation | ||||||||||
| 12 | |||||||||||
| 13 | =head1 SYNOPSIS | ||||||||||
| 14 | |||||||||||
| 15 | use FusqlFS::Cache::Limited; | ||||||||||
| 16 | |||||||||||
| 17 | our %cache; | ||||||||||
| 18 | tie %cache, 'FusqlFS::Cache::Limited', 10000; | ||||||||||
| 19 | |||||||||||
| 20 | =head1 DESCRIPTION | ||||||||||
| 21 | |||||||||||
| 22 | This is a limited by items number cache strategy implementation. This class is | ||||||||||
| 23 | not to be used directly. | ||||||||||
| 24 | |||||||||||
| 25 | This cache strategy accepts single `threshold' parameter which must be integer | ||||||||||
| 26 | greater than zero and determines maximum number of items to be stored in cache. | ||||||||||
| 27 | |||||||||||
| 28 | This cache strategy tries to keep memory usage low enough by limiting number of | ||||||||||
| 29 | cache items. If on cache write number of items in cache exceeds given | ||||||||||
| 30 | threshold, cache cleanup is forced, striving to decrease cached items number | ||||||||||
| 31 | down to threshold plus 1/8 of total current number of items. So number of cache | ||||||||||
| 32 | items varies between I<(7/8)*threshold> and I<threshold> in fact. It does | ||||||||||
| 33 | cleanup this way to avoid cleanup situations appearance too often. | ||||||||||
| 34 | |||||||||||
| 35 | The cleanup process chooses items to remove quite cleverly: this class keeps | ||||||||||
| 36 | items usage statistics and cleanup process uses this statistics to remove least | ||||||||||
| 37 | used items first. It makes cleanup and cache hit try processes a little slower, | ||||||||||
| 38 | but speeds up cache performance in whole, as resulting hit/miss ratio is | ||||||||||
| 39 | better, than in case of naive cleanup algorithm. | ||||||||||
| 40 | |||||||||||
| 41 | This cache strategy is good if you are going to mount database with a lot | ||||||||||
| 42 | number of records and you have memory issues because of this, as it focuses on | ||||||||||
| 43 | keeping overall number of cached items low enough. If you need to mount | ||||||||||
| 44 | database with moderate number of large records, like records with huge blob or | ||||||||||
| 45 | text fields, you might consider using L<FusqlFS::Cache::File> strategy. | ||||||||||
| 46 | |||||||||||
| 47 | I also recommend setting threshold for this cache strategy to at least 3/4 of | ||||||||||
| 48 | total objects in your database (including all tables, sequences, views, data | ||||||||||
| 49 | rows etc.), which will bring you about 60% cache hits (~45% for 1/2 and ~56% | ||||||||||
| 50 | for 2/3). But this is just a basic recommendation based on educated guess and | ||||||||||
| 51 | some tests with "entry" names generated with normally distributed random | ||||||||||
| 52 | generator. Experiment is your best advisor in this case. | ||||||||||
| 53 | |||||||||||
| 54 | =head1 SEE ALSO | ||||||||||
| 55 | |||||||||||
| 56 | =over | ||||||||||
| 57 | |||||||||||
| 58 | =item * | ||||||||||
| 59 | |||||||||||
| 60 | L<FusqlFS::Cache> and L<FusqlFS::Cache::Base> about FusqlFS cache strategies. | ||||||||||
| 61 | |||||||||||
| 62 | =item * | ||||||||||
| 63 | |||||||||||
| 64 | L<FusqlFS::Entry> for file system entry structure description. | ||||||||||
| 65 | |||||||||||
| 66 | =item * | ||||||||||
| 67 | |||||||||||
| 68 | L<perltie> about object tie()ing in perl. | ||||||||||
| 69 | |||||||||||
| 70 | =back | ||||||||||
| 71 | |||||||||||
| 72 | =cut | ||||||||||
| 73 | |||||||||||
| 74 | =begin testing | ||||||||||
| 75 | |||||||||||
| 76 | #!noinst | ||||||||||
| 77 | |||||||||||
| 78 | ok FusqlFS::Cache::Limited->is_needed(10), 'Limited cache is needed'; | ||||||||||
| 79 | ok !FusqlFS::Cache::Limited->is_needed(0), 'Limited cache isn\'t needed'; | ||||||||||
| 80 | |||||||||||
| 81 | =end testing | ||||||||||
| 82 | =cut | ||||||||||
| 83 | sub is_needed | ||||||||||
| 84 | 2 | ▶ | { | ||||||||
|
Subroutine
is_needed: called CC=1 SCAR=0.0
| |||||||||||
| 85 | 2 | return $_[1] > 0; | |||||||||
| 86 | } | ||||||||||
| 87 | |||||||||||
| 88 | =begin testing | ||||||||||
| 89 | |||||||||||
| 90 | my %cache; | ||||||||||
| 91 | isa_ok tie(%cache, 'FusqlFS::Cache::Limited', 10), 'FusqlFS::Cache::Limited', 'Limited cache tied'; | ||||||||||
| 92 | |||||||||||
| 93 | ok !scalar(%cache), 'Cache is empty'; | ||||||||||
| 94 | |||||||||||
| 95 | foreach my $n (1..10) | ||||||||||
| 96 | { | ||||||||||
| 97 | $cache{'test'.$n} = 'value'.$n; | ||||||||||
| 98 | } | ||||||||||
| 99 | |||||||||||
| 100 | ok scalar(%cache), 'Cache is not empty'; | ||||||||||
| 101 | |||||||||||
| 102 | foreach my $n (1..10) | ||||||||||
| 103 | { | ||||||||||
| 104 | ok exists($cache{'test'.$n}), 'Entry '.$n.' exists'; | ||||||||||
| 105 | is $cache{'test'.$n}, 'value'.$n, 'Entry '.$n.' is intact'; | ||||||||||
| 106 | } | ||||||||||
| 107 | |||||||||||
| 108 | ok exists($cache{'test10'}), 'Element exists before deletion'; | ||||||||||
| 109 | delete $cache{'test10'}; | ||||||||||
| 110 | ok !exists($cache{'test10'}), 'Deleted element doesn\'t exist'; | ||||||||||
| 111 | is $cache{'test10'}, undef, 'Deleted element is undefined'; | ||||||||||
| 112 | |||||||||||
| 113 | %cache = (); | ||||||||||
| 114 | |||||||||||
| 115 | ok !scalar(%cache), 'Cache is empty after cleanup'; | ||||||||||
| 116 | |||||||||||
| 117 | foreach my $n (1..1000) | ||||||||||
| 118 | { | ||||||||||
| 119 | $cache{'test'.$n} = 'value'.$n; | ||||||||||
| 120 | foreach my $m (1..1000-$n) | ||||||||||
| 121 | { | ||||||||||
| 122 | my $x = $cache{'test'.$n}; | ||||||||||
| 123 | } | ||||||||||
| 124 | } | ||||||||||
| 125 | |||||||||||
| 126 | ok exists($cache{'test1'}), 'Most used element exists'; | ||||||||||
| 127 | is $cache{'test1'}, 'value1', 'Most used element is intact'; | ||||||||||
| 128 | ok !exists($cache{'test999'}), 'Least used element doesn\'t exist'; | ||||||||||
| 129 | is $cache{'test999'}, undef, 'Least used element undefined'; | ||||||||||
| 130 | cmp_ok length(keys %cache), '<=', 10, 'Number of items in cache doesn\'t exceed given threshold'; | ||||||||||
| 131 | |||||||||||
| 132 | while (my ($key, $val) = each %cache) | ||||||||||
| 133 | { | ||||||||||
| 134 | like $key, qr/^test[0-9]+$/, 'Iterate: key is '.$key.' intact'; | ||||||||||
| 135 | like $val, qr/^value[0-9]+$/, 'Iterate: value is '.$val.' intact'; | ||||||||||
| 136 | is substr($key, 4), substr($val, 5), 'Iterate: key matches value'; | ||||||||||
| 137 | } | ||||||||||
| 138 | |||||||||||
| 139 | =end testing | ||||||||||
| 140 | =cut | ||||||||||
| 141 | sub TIEHASH | ||||||||||
| 142 | 1 | ▶ | { | ||||||||
|
Subroutine
TIEHASH: called CC=1 SCAR=0.0
| |||||||||||
| 143 | 1 | my $class = shift; | |||||||||
| 144 | 1 | my $threshold = shift; | |||||||||
| 145 | |||||||||||
| 146 | # real hash, hits count, total count, threshold, cleanups count | ||||||||||
| 147 | 1 | my $self = [ {}, {}, 0, 0+$threshold, 0 ]; | |||||||||
| 148 | |||||||||||
| 149 | 1 | bless $self, $class; | |||||||||
| 150 | } | ||||||||||
| 151 | |||||||||||
| 152 | sub FETCH | ||||||||||
| 153 | 0 | ▶ | { | ||||||||
|
Subroutine
FETCH: not called CC=2 SCAR=17.9
| |||||||||||
| 154 | 0 | my ($self, $key) = @_; | |||||||||
| 155 | 0 | ▶ | return unless exists $self->[0]->{$key}; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 156 | 0 | $self->[1]->{$key}++; | |||||||||
| 157 | 0 | return $self->[0]->{$key}; | |||||||||
| 158 | } | ||||||||||
| 159 | |||||||||||
| 160 | sub STORE | ||||||||||
| 161 | 0 | ▶ | { | ||||||||
|
Subroutine
STORE: not called CC=3 SCAR=24.8
| |||||||||||
| 162 | 0 | my ($self, $key, $value) = @_; | |||||||||
| 163 | 0 | ▶ | $self->cleanup() if $self->[2] > $self->[3]; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 164 | 0 | ▶ | $self->[2]++ unless exists $self->[0]->{$key}; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 165 | 0 | $self->[0]->{$key} = $value; | |||||||||
| 166 | 0 | $self->[1]->{$key} = 1; | |||||||||
| 167 | } | ||||||||||
| 168 | |||||||||||
| 169 | sub DELETE | ||||||||||
| 170 | 0 | ▶ | { | ||||||||
|
Subroutine
DELETE: not called CC=2 SCAR=17.9
| |||||||||||
| 171 | 0 | my ($self, $key) = @_; | |||||||||
| 172 | 0 | ▶ | $self->[2]-- if exists $self->[0]->{$key}; | ||||||||
|
Branch: 1 branch
| |||||||||||
| 173 | 0 | delete $self->[0]->{$key}; | |||||||||
| 174 | 0 | delete $self->[1]->{$key}; | |||||||||
| 175 | } | ||||||||||
| 176 | |||||||||||
| 177 | sub CLEAR | ||||||||||
| 178 | 0 | ▶ | { | ||||||||
|
Subroutine
CLEAR: not called CC=1 SCAR=6.9
| |||||||||||
| 179 | 0 | my ($self)= @_; | |||||||||
| 180 | 0 | $self->[0] = {}; | |||||||||
| 181 | 0 | $self->[1] = {}; | |||||||||
| 182 | 0 | $self->[2] = 0; | |||||||||
| 183 | } | ||||||||||
| 184 | |||||||||||
| 185 | sub EXISTS | ||||||||||
| 186 | 0 | ▶ | { | ||||||||
|
Subroutine
EXISTS: not called CC=1 SCAR=6.9
| |||||||||||
| 187 | 0 | my ($self, $key) = @_; | |||||||||
| 188 | 0 | return exists $self->[0]->{$key}; | |||||||||
| 189 | } | ||||||||||
| 190 | |||||||||||
| 191 | sub FIRSTKEY | ||||||||||
| 192 | { | ||||||||||
| 193 | my ($self) = @_; | ||||||||||
| 194 | my $_ = keys %{$self->[0]}; | ||||||||||
| 195 | each %{$self->[0]}; | ||||||||||
| 196 | } | ||||||||||
| 197 | |||||||||||
| 198 | sub NEXTKEY | ||||||||||
| 199 | { | ||||||||||
| 200 | my ($self, $lastkey) = @_; | ||||||||||
| 201 | return each %{$self->[0]}; | ||||||||||
| 202 | } | ||||||||||
| 203 | |||||||||||
| 204 | sub SCALAR | ||||||||||
| 205 | { | ||||||||||
| 206 | my ($self) = @_; | ||||||||||
| 207 | return scalar(%{$self->[0]}); | ||||||||||
| 208 | } | ||||||||||
| 209 | |||||||||||
| 210 | sub cleanup | ||||||||||
| 211 | { | ||||||||||
| 212 | my ($self) = @_; | ||||||||||
| 213 | my $del_num = $self->[2] - $self->[3] + ($self->[2] >> 3); | ||||||||||
| 214 | #carp "cleanup: remove $del_num out from $self->[2], threshold is $self->[3]"; | ||||||||||
| 215 | #$self->[5]++; | ||||||||||
| 216 | my @keys = sort { $self->[1]->{$a} <=> $self->[1]->{$b} } keys %{$self->[1]}; | ||||||||||
| 217 | |||||||||||
| 218 | #carp "top 10 least used keys: ", join(", ", @keys[0..9]); | ||||||||||
| 219 | #carp "top 10 least counts: ", join(", ", @{$self->[1]}{@keys[0..9]}); | ||||||||||
| 220 | #carp "top 10 most used keys: ", join(", ", @keys[-10..-1]); | ||||||||||
| 221 | #carp "top 10 most counts: ", join(", ", @{$self->[1]}{@keys[-10..-1]}); | ||||||||||
| 222 | |||||||||||
| 223 | $self->[2] -= $del_num; | ||||||||||
| 224 | #carp "calculated total: $self->[2]"; | ||||||||||
| 225 | #carp "before cleanup: ", scalar(keys(%{$self->[0]})); | ||||||||||
| 226 | |||||||||||
| 227 | @keys = @keys[0..$del_num-1]; | ||||||||||
| 228 | delete @{$self->[0]}{@keys}; | ||||||||||
| 229 | delete @{$self->[1]}{@keys}; | ||||||||||
| 230 | |||||||||||
| 231 | #carp "after cleanup: ", scalar(keys(%{$self->[0]})); | ||||||||||
| 232 | } | ||||||||||
| 233 | |||||||||||
| 234 | 1; | ||||||||||
| 235 | |||||||||||