[−][src]Crate xfetch

This crate implements the XFetch probabilistic early expiration algorithm.

Cache Stampede

A cache stampede is a type of cascading failure that can occur when massively parallel computing systems with caching mechanisms come under very high load. This behaviour is sometimes also called dog-piling.

Under normal load, cache misses will trigger a recomputation to refresh the cache. Other process or thread can continue as before.

Under heavy load, cache misses may trigger multipre process / threads trying to refresh content thus add more loading to the resource source which the cache was meant to reduce the loading.

Several approaches can be used to mitigate cache stampedes. The algorithm used here is proposed by Vattani, A.; Chierichetti, F.; Lowenstein, K. (2015) in the paper Optimal Probabilistic Cache Stampede Prevention.

The idea is any worker can volunteer to recompute the value before it expires. With a probability that increases when the cache entry approaches expiration, each worker may recompute the cache by making an independent decision. The effect of the cache stampede is mitigated as fewer workers will expire at the same time.

The following is the algorithm pseudo code:

ⓘThis example is not tested
function XFetch(key, ttl; beta = 1)
    value, delta, expiry <- cache_read(key)
    if !value or time() - delta * beta * ln(rand()) >= expiry then
        start <- time()
        value <- recompute_value()
        delta <- time() - start
        cache_write(key, (value, delta), ttl)
    end
    return value
end

The parameter beta can be set to greater than 1.0 to favor earlier recomputation or lesser to favor later. The default 1.0 is optimal for most use cases.

rand() is a random number in the range (0, 1].

delta is the time required for the recomputation. If it takes longer to recompute then the algorithm will also favor earlier recomputation.

Examples

Create a single cache entry and test it's expiration:

use xfetch::CacheEntry;
use std::time::Duration;

let entry = CacheEntry::new(|| {
    expensive_computation()
})
.with_ttl(|value| {
    Duration::from_millis(value.ttl)
})
.build();

assert!(!entry.is_expired());

The CacheEntry can be used with any cache library. For example the lru crate:

use lru::LruCache;
use xfetch::CacheEntry;
use std::time::Duration;

struct SomeValue {
    value: u64,
    ttl: u64
};

fn recompute_value(n: u64) -> SomeValue {
    SomeValue { value: n, ttl: 10000 }
}

fn main() {
    let mut cache = LruCache::new(2);

    cache.put("apple", CacheEntry::new(|| recompute_value(3))
        .with_ttl(|v| Duration::from_millis(v.ttl))
        .build());
    cache.put("banana", CacheEntry::new(|| recompute_value(2))
        .with_ttl(|v| Duration::from_millis(v.ttl))
        .build());

    if let Some(entry) = cache.get(&"apple") {
        if !entry.is_expired() {
            assert_eq!(entry.get().value, 3);
        } else {
            cache.put("apple", CacheEntry::new(|| recompute_value(3))
                .with_ttl(|v| Duration::from_millis(v.ttl))
                .build());
        }
    }
}

References

Structs

CacheEntry

A cache entry that employs probabilistic early expiration

CacheEntryBuilder

The builder for building CacheEntry with supplied parameters.