view release on metacpan or  search on metacpan

README  view on Meta::CPAN

NAME
    Cache::Memcached::Turnstile - Thundering Herd Protection for Memcached
    Clients

SYNOPSIS
      use Cache::Memcached::Turnstile qw(:all);
  
      my $memd_client = Cache::Memcached::Fast->new(...);
  
      my $value = cache_get_or_compute(
        $memd_client,
        key          => "foo", # key to fetch
        expiration   => 60,    # [s] expiration to set if need to compute the value
        compute_cb   => sub { ... expensive computation... return $result },
        compute_time => 1,
        wait         => 0.1,
      );
  
      my $value_hash = multi_cache_get_or_compute(
        $memd_client,
        key          => [["foo", 60], ["bar", 120]], # key/expiration pairs
        compute_cb   => sub {
          my ($memd_client, $args, $keys_ary) = @_;
          ... expensive computation...
          return \@values;
        },
        compute_time => 1, # approx computation time per key (see below)
      );

DESCRIPTION
    This is a prototype of a Thundering-Herd prevention algorithm for
    memcached. As most such systems, it doesn't play entirely nicely with
    incompatible modes of access to the same keys, but that's not so much
    surprise, one would hope. Access to different keys in the same memcached
    instance through different means is perfectly safe and compatible.

    The logic in this module should be compatible with any Memcached client
    library that has the same API as the Cache::Memcached::Fast module at
    least for the following methods: "get", "set", "add", "gets", "cas". It
    has only been tested with the aforementioned client library.

  The Problem Statement
    The algorithm described and implemented here attempts to provide means
    of dealing with two kinds of situations. Most similar systems appear to
    be targeted at the first and more common situation only:

    1 A hot cached value expires. Between the point in time when it expired
      and the time when the first user has recomputed the value and
      successfully filled the cache, all users of the cache will, in a naive
      cache client implementation, attempt to recalculate the value to store
      in the cache. This can bring down back-end systems that are not
      designed to handle the load of all front-ends that rely on the
      cache[1].

    2 A normal web environment has rather friendly, randomized access
      patterns. But if your cache has a number of near-synchronized clients
      that all attempt to access a new cache key in unison (such as when a
      second or a minute roll around), then some of the mechanisms that can
      help in situation 1 break down.

  The Solution
    A very effective approach to deal with most causes of situation 1) is
    described in [2]. In a nutshell, it's a trade-off in that we accept that
    for a small amount of time, we will serve data from a stale cache. This
    small amount of time is the minimum of either: the time it takes for a
    single process to regenerate a fresh cache value, or a configured safety
    threshold. This has the effect that when a cache entry has expired, the
    first to request the cache entry will start reprocessing, and all
    subsequent accesses (until the reprocessing is done) will use the old,
    slightly outdated cached data. This is a perfectly valid strategy in
    many use cases and where extreme accuracy of the cached values is
    required, it's usually possible to address that either by active
    invalidation (deleting from memcached) or by simply setting a more
    stringent expire time.

    That approach does not handle situation 2), in which many clients
    attempt to access a cache entry that didn't previously exist. To my
    knowledge, there is no generic solution for handling that situation. It
    will always require application specific knowledge to handle. For this
    situation, there is a configurable back-off time, or a custom hook
    interface to intercept such cases and handle them with custom logic.

  The Algorithm
    Situation 1 from above is handled by always storing a tuple in the cache
    that includes the real, user-supplied expiration time of the cached
    value. The expiration time that is set on the cache entry is the sum of
    the user-supplied expiration time and an upper-bound estimate of the
    time it takes to recalculate the cached value.

    On retrieval of the cache entry (tuple), the client checks whether the
    real, user-supplied expiration time has passed and if so, it will
    recalculate the value. Before doing so, it attempts to obtain a lock on
    the cache entry to prevent others from concurrently also recalculating
    the same cache entry.

    The locking is implemented by setting a flag on the tuple structure in
    the cache that indicates that the value is already being reprocessed.
    This can be done race-condition free by using the "add", "gets", and
    "cas" commands supplied by Memcached. With the command that sets the
    being-reprocessed flag on a tuple, the client always sets an expiration
    time of the upper-bound of the expected calculation time, thus
    protecting against indefinitely invalidating the cache when a
    re-calculation fails, slows, or locks up.

    On retrieval of a cache entry that is being reprocessed, other clients
    than the one doing the reprocessing will continue to return the old
    cached value. The time this stale value is in use is bounded by the
    reprocessing time set as expiration above.

    There are a number of conditions under which there is no such stale
    value to use, however, including the first-use of the cache entry and a
    cache entry that is used rarely enough to expire altogether before a
    client finds it to be outdated. The pathological variant is one in which
    a large number of clients concurrently request a cache value that is not
    available at all (stale or not). In this situation, the remedy is
    application dependent. By default, all clients but one wait for up to