xf

README

XFetch Go

A library for mitigating against cache stampedes with the XFetch algorithm.

Background

XFetch is a probabilistic early recomputation algorithm for mitigating against cache stampedes.

Any process reading the cache may recompute the cache value before it expires, while others carry on reading from the cache.

This means we don't get a scenario where a value is suddenly expired and every process starts performing an expensive computation.

The probability that a cache value will be recomputed increases the closer we get to the end of the TTL.

Visualization

I've created a graph here: https://www.desmos.com/calculator/bkjyyz3zlp . It visualizes the probability of recomputing the value of a single key the closer we get to the TTL.

a: the time it took to compute the last value (called delta in the below papers)

b: a constant which one can tweak to have earlier or later re-computation (called beta). The higher it is the earlier the computation will be.

y: The value of a random float between 0 and 1.

d: The key TTL (in the graph, 10 seconds)

You can tweak these values to visualize how the algorithm behaves in different scenarios.

Papers

1. http://www.vldb.org/pvldb/vol8/p886-vattani.pdf
2. https://www.slideshare.net/RedisLabs/redisconf17-internet-archive-preventing-cache-stampede-with-redis-and-xfetch

Usage

With Redigo

type arbitraryData struct {
	Something string `redis:"something"`
}

conn, err := redis.Dial("tcp", x.server.Addr())
if err != nil {
    // handle error
}
defer conn.Close()

beta := 1.0
fetcher := xf.NewFetcher(beta)
ttl := time.Hour

cache := xfredigo.Wrap(conn)

retrieval, err := fetcher.Get(ctx, cache, "HGETALL", "some_key")
if err != nil {
   // handle err
}

if !retrieval.ShouldRefresh {
    redisValue, err := redis.Values(retrieval.Value)
    if err != nil {
       // handle
    }	
    
    var data arbitraryData
    err = redis.ScanStruct(redisValue, &data)
    if err != nil {
       // handle
    }
    return data
}

start := time.Now()
data := fetchData()
delta := time.Since(start)
err = fetcher.Put(ctx, cache, "HMSET", "some_key", ttl, delta, redis.Args{}.AddFlat(prsn)...)
if err != nil {
   // handle
}

With other caches/libraries

Any caching library that implements the Cache interface can be used with this library.

Feel free to send a pull-request if you would like to use this library with any other cache or caching library.

Documentation

Index

• type Cache
• type Fetcher
  • func NewFetcher(beta float64) Fetcher
  • func NewFetcherWithRandomizer(beta float64, randomizer Randomizer) Fetcher
• type Randomizer
• type Retrieval

Types

type Cache

type Cache interface {
	// Get retrieves a value at `key` using command `cmd`. It returns the value, the remaining ttl of the key,
	// its delta, and any error.
	Get(ctx context.Context, cmd, key string) (interface{}, float64, float64, error)

	// Put puts the values at `args` at `key` using command `cmd`. It also sets its ttl and stores the delta.
	Put(ctx context.Context, cmd, key string, ttl, delta time.Duration, args ...interface{}) error
}

Cache abstracts away cache operations. You can use any kind of cache or caching library to implement it.

type Fetcher

type Fetcher interface {
	// Get returns a value at `key` from the cache. It wraps it in a Retrieval and returns any error encountered.
	Get(ctx context.Context, cache Cache, cmd, key string) (*Retrieval, error)

	// Put delegates putting an object to the cache to the Cache implementation.
	Put(ctx context.Context, cache Cache, cmd, key string, ttl, delta time.Duration, args ...interface{}) error
}

Fetcher describes an X-Fetch client.

func NewFetcher

func NewFetcher(beta float64) Fetcher

NewFetcher takes the ttl of a cache key and its beta value and returns a Fetcher, using rand.Float64 as a randomizer

func NewFetcherWithRandomizer

func NewFetcherWithRandomizer(beta float64, randomizer Randomizer) Fetcher

NewFetcher takes the ttl of a cache key, its beta value and a Randomizer and returns a Fetcher

type Randomizer

type Randomizer func() float64

Randomizer returns a random float between 0 and 1.

type Retrieval

type Retrieval struct {
	ShouldRefresh bool
	Value         interface{}
}

Retrieval wraps a value and exposes whether you should refresh it.