Ton Hospel

NAME

Tie::Cacher - Cache a (sub)set of key/value pairs. Tie and OO interface.

SYNOPSIS

  # The Object Oriented interface:
  use Tie::Cacher;
  $cache   = Tie::Cacher->new($max_count);
  $cache   = Tie::Cacher->new(%options);
  $cache   = Tie::Cacher->new(\%options);

  $cache->store($key, $value);
  $value   = $cache->fetch($key);
  $node    = $cache->fetch_node($key);

  $nr_keys = $cache->keys;
  @keys    = $cache->keys;
  @keys    = $cache->recent_keys;
  @keys    = $cache->old_keys;
  $key     = $cache->most_recent_key;
  $key     = $cache->oldest_key;

  $key      = $cache->first_key;
  ($key, $value) = $cache->first_key;
  $key      = $cache->next_key;
  ($key, $value) = $cache->next_key;

  $exists   = $cache->exists($key);

  $cache->delete(@keys);
  $value    = $cache->delete(@keys);
  @values   = $cache->delete(@keys);
  $cache->clear;

  $nr_keys = $cache->count;

  $hit = $cache->hit;
  $old_hit = $cache->hit($new_hit);
  $missed = $cache->missed;
  $old_missed = $cache->missed($new_missed);

  $max_count     = $cache->max_count;
  $old_max_count = $cache->max_count($new_max_count);
  $validate      = $cache->validate;
  $old_validate  = $cache->validate($new_validate);
  $load          = $cache->load;
  $old_load      = $cache->load($new_load);
  $save          = $cache->save;
  $old_save      = $cache->save($new_save);
  $user_data     = $cache->user_data;
  $old_user_data = $cache->user_data($new_user_data);

  # The Tie interface:
  use Tie::Cacher;
  $tied = tie %cache, 'Tie::Cache', $max_count;
  $tied = tie %cache, 'Tie::Cache', %options;
  $tied = tie %cache, 'Tie::Cache', {%options};

  # cache supports normal tied hash functions
  $cache{1} = 2;       # STORE
  print "$cache{1}\n"; # FETCH

  print "Yes\n" if exists $cache{1};    # EXISTS
  @keys = keys %cache;  # KEYS

  # FIRSTKEY, NEXTKEY
  while(($k, $v) = each %cache) { print "$k: $v\n"; }

  delete $cache{1};    # DELETE
  %cache = ();         # CLEAR

  # Or use the OO methods on the underlying tied object:
  print $tied->max_count, "\n";

DESCRIPTION

This module implements a least recently used (LRU) cache in memory through a tie and a OO interface. Any time a key/value pair is fetched or stored, an entry time is associated with it, and as the cache fills up, those members of the cache that are the oldest are removed to make room for new entries.

So, the cache only "remembers" the last written entries, up to the size of the cache. This can be especially useful if you access great amounts of data, but only access a minority of the data a majority of the time.

The implementation is a hash, for quick lookups, overlaying a doubly linked list for quick insertion and deletion. Notice that the OO interface will be faster than the tie interface.

EXPORT

None

METHODS

Notice that in the methods you will see a number of places where a node is returned where you might have expected a value or a reference to a value. This node is an array reference that actually has the value at index 0, followed by a few internal fields. You are however free to put extra associated data in this array after them or even do things like bless the array. This gives you an easy way to decorate values.

$cache = Tie::Cacher->new($max_count)
$cache = Tie::Cacher->new(%options)
$cache = Tie::Cacher->new(\%options)

Creates a new Tie::Cache object. Will throw an exception on failure (the only possible failures are invalid arguments).

Options are name value pairs, where the following are currently recognized:

validate => \&code

If this option is given, whenever a data fetch or fetch_node is done (notice that when using the tied interface, a list context each implies a fetch for the value) and the requested key already exists, the given code is called like:

 $validate->($cache, $key, $node)

where $node is an internal array reference. You can access the current value corresponding to the key as $node->[0]. The code should either return true, indicating the value is still valid, or false, meaning it's not valid anymore.

In the invalid case the current entry gets removed and the fetch proceeds as if the key had not been found (which includes a possible load).

In the valid case, you may in fact change the value through $node->[0] before returning. (That way you can save a call to load, but there won't be any implied save call, so you'll have to do that yourself if you want it).

If the code dies, the exception will be passed to the application, but The hit counter will have been increased, the key will still be in the cache and will have been marked as recently used.

load => \&load

If this option is given, whenever a data fetch or fetch_node is done (notice that when using the tied interface, a list context each implies a fetch for the value) and the requested key does not exist (or is declared invalid by a validate returning false), the given code is called like:

 $load->($cache, $key, $node)

The $load code reference should now somehow get a value corresponding to $key (e.g. by looking it up in a database or doing a complex calculation or whatever) and then store this new value in $node->[0]. If it fails it should throw an exception (which will not be caught and passed on to the caller of fetch or fetch_node. The entry will be removed from the cache and no save callback will be called for it).

save => \&save

If this option is given, it will be called whenever a new value enters the cache, which means on store or just after a load (triggered by a fetch or fetch_node). It's not called if you store a value in a validate callback.

The code is called like:

 $save->($cache, $key, $node)

where the value is in $node->[0].

If this code dies, the exception is passed on to the application, but the key will be removed from the cache.

max_count => size

If this option is given, the cache has a maximum number of entries. Whenever you store a key/value pair and this would cause the cache to grow beyong the given size, the oldest entry will be dropped from the cache to make place.

user_data => value

This option allows you to associate one scalar value with the cache object. You can retrieve it with the user_data method. The user_data is undef if it has never been set.

$cache->store($key, $value)

Looks up $key in the cache, and replaces its value if it already exists. If it doesn't exist yet, the cache is checked for size (in case a maximum size was given) and the oldest entry is dropped if the maximum is reached. A new slot is created for the new key, and the new value is now stored there.

The node with the new value now gets the newest timestamp.

In either case, the save callback is called if one exists. If a save callback is called and throws an exception, the key is removed from the cache.

The hit and missed counters will remain untouched for all cases.

$value = $cache->fetch($key)

Looks up $key in the cache.

If it does exist, increases the hit counter and marks the node as most recent. Next it will call the validate callback if one exists. If that returns true or there is no validate callback, the value associated with $key is returned.

If the key is not in the cache yet, or the validate callback returns false, it will increase the missed counter, and see if there is a load callback. If there isn't one, fetch will return undef. Otherwise a slot is created for a new value and marked as most recently used, and the load callback is called which will try to produce a value (or throw an exception). If there is a save callback, that will now be called to e.g. store the new value in long term storage. After that, the new value is returned.

If the load callback callback throws an exception, the key is deleted from the cache (even if it existed before and failed a validate) and no save callback will be called for this value.

Notice that if fetch returns undef, you don't normally know if this means that the associated value is "undef" or if the key didn't exist at all. You can check using exists or do the fetch with fetch_node.

$node = $cache->fetch_node($key)

Does exactly the same as fetch, but where fetch would return a value, this returns the node array reference where you can find the value as $node->[0].

One advantage is that you can distinguish a failed fetch (returns undef) from an undefined value (returns a node where $node->[0] is undef).

You can also use this to access extra data associated with the value.

$nr_keys = $cache->keys
@keys = $cache->keys

In scalar context, returns the number of keys in the cache.

In list context, returns all the keys in the cache.

In either case it resets the position of next_key.

Will not do any key validation.

@keys = $cache->recent_keys

Returns all keys, ordered from most recently used to least recently used. This is notably slower than using keys

@keys = $cache->old_keys

Returns all keys, ordered from least recently used to most recently used. This is notably slower than using keys

$key = $cache->most_recent_key

Returns the most recently used key, or "undef" if the cache is empty.

$key = $cache->oldest_key

Returns the least recently used key, or "undef" if the cache is empty.

$key = $cache->first_key
($key, $value) = $cache->first_key

Resets the position for next_key to the start and does a next_key.

$key = $cache->next_key
($key, $value) = $cache->next_key

Returns the next element in the cache, so you can iterate over it. In scalar context it just returns the key, in list context it returns both the key and the corresponding value, but it will do no validation on the value. If you want validation, use the scalar version and do the fetch yourself.

Entries are returned in an apparently random order. The actual random order is subject to change in future versions of perl, but it is guaranteed to be in the same order as that returned by the keys method.

When the cache is entirely read, an empty list is returned in list context (which when assigned produces a false (0) value), and "undef" in scalar context. The next call to "next_key" after that will start iterating again. There is a single iterator for each cache, shared by all "first_key", "next_key" and "keys" calls in the program; it can be reset by reading all the elements from the cache or by calling "keys". If you add or delete elements of a hash while you're iterating over it, you may get entries skipped or duplicated, so don't. Exception: It is always safe to delete the item most recently returned by "first_key" or "next_key", which means that the following code will work:

 while (($key, $value) = $cache->next_key) {
     print $key, "\n";
     $cache->delete($key);   # This is safe
 }
$exists = $cache->exists($key)

Returns true if $key exists in the cache, even if it has the value undef. Returns false otherwise. Does no validation.

$cache->delete(@keys)
$value = $cache->delete(@keys)
@values = $cache->delete(@keys)

deletes all entries in the cache corresponding to the given @keys (quite often only one key to be deleted will be specified of course). Any keys that don't exist in the cache will cause no changes in the cache, but will behave as if they correspond to a value of "undef" for the return value.

In scalar context, returns the last deleted value. In list context, returns the list of deleted values corresponding to the given keys. No validation is done for any of the values.

$cache->clear

Removes all entries from the cache.

$nr_keys = $cache->count

Returns the number of keys in the cache like keys does in scalar context, but does not reset the position for next_key

$hit = $cache->hit

Return the number of times a fetch or fetch_node on a key found that key to already exist.

$old_hit = $cache->hit($new_hit)

Sets the number of hits to $new_hit (typically 0 will be used here). Returns the old value

$missed = $cache->missed

Return the number of times a fetch or fetch_node on a key found that key to not exist yet.

$old_missed = $cache->missed($new_missed)

Sets the number of misses to $new_missed (typically 0 will be used here). Returns the old value

$max_count = $cache->max_count

Returns the maximum number of entries allowed in the cache, or "undef" if there is no maximum.

$old_max_count = $cache->max_count($new_max_count)

Sets a new maximum for the number of allowed entries in the cache. "undef" means there is no maximum. Returns the old value.

$validate = $cache->validate

Returns a code reference to the validate callback or "undef" if there is none.

$old_validate = $cache->validate($new_validate)

Sets a new validate callback. "undef" means no more validate callback. Returns the old value.

$load = $cache->load

Returns a code reference to the load callback or undef if there is none.

$old_load = $cache->load($new_load)

Sets a new load callback. "undef" means no more load callback. Returns the old value.

$save = $cache->save

Returns a code reference to the save callback or undef if there is none.

$old_save = $cache->save($new_save)

Sets a new save callback. "undef" means no more save callback. Returns the old value.

$user_data = $cache->user_data

Returns the user_data associated with the cache.

$old_user_data = $cache->user_data($new_user_data)

Sets a new value as the user data. Returns the old value.

$tied = tie %cache, 'Tie::Cache', $max_count
$tied = tie %cache, 'Tie::Cacher', %options
$tied = tie %cache, 'Tie::Cacher', {%options}

These are like new (with all the same options), with the object returned in $tied. It also ties the object to the hash %cache and fakes the normal hash operations to the corresponding operations on the underlying object as described in Tie::Hash (see also the SYNOPSIS).

If you don't need to do any Object Oriented calls, you can just get rid of the $tied assignment. In fact, you can always drop it and just use tied if you ever need the underlying object. So e.g. a basic size restricted hash is as simple as:

    tie %hash, 'Tie::Cacher', max_count => 1000;

There is one gotcha you have to be aware off:

    ($key, $value) = each %hash;

will use scalar context first_key or next_key and then get the value using a fetch, unlike the list context variants of first_key and next_key that just directly get the value without any validation, loading or saving.

EXAMPLE

Here's a simple memoized fibonacci:

  use Tie::Cacher;
  my $fibo = Tie::Cacher->new(load => sub {
                                  my ($self, $key, $node) = @_;
                                  $node->[0] = $self->fetch($key-1) +
                                               $self->fetch($key-2);
                              });
  $fibo->store(0 => 0);
  $fibo->store(1 => 1);
  print $fibo->fetch(20), "\n";

or as a tie:

  use Tie::Cacher;
  tie my %fibo, "Tie::Cacher", load => sub {
                                  my ($self, $key, $node) = @_;
                                  $node->[0] = $self->fetch($key-1) +
                                               $self->fetch($key-2);
                              };
  $fibo{0} = 0;
  $fibo{1} = 1;
  print "$fibo{20}\n";

SEE ALSO

Tie::Cache, Tie::Cache::LRU

AUTHOR

Ton Hospel, <Tie::Cacher@ton.iguana.be>

COPYRIGHT AND LICENSE

Copyright 2003 by Ton Hospel

This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself.