approx-lru

This provides the lru package which implements a fixed-size thread safe LRU cache. It is based on hashicorp/golang-lru, which is in turn based on the cache in Groupcache.

The major difference in bobby-stripe/approx-lru is that instead of strictly ordering all items in the cache in a doubly-linked list (like golang-lru does), approx-lru contains a fixed-sized array of cache entries with a lastUsed timestamp. If the cache is full and needs to evict an item, we randomly probe several entries, and evict the oldest. This is the same strategy as Redis's allkeys-lru, and approximates a perfect LRU with less bookkeeping and memory overhead (each linked list entry in Go is 40-bytes, in addition to the data).

Documentation

Full docs are available on Godoc

Example

Using the LRU is very simple:

l, _ := New(128)
for i := 0; i < 256; i++ {
    l.Add(strconv.Itoa(i), i)
}
if l.Len() != 128 {
    panic(fmt.Sprintf("bad len: %v", l.Len()))
}
if v, ok := l.Get("200"); ok {
	_ = v // use v
}