W-TinyLFU

This is an implementation of Window TinyLFU - A Highly Efficient Cache Admission Policy - from the 2015 TinyLFU paper by Gil Einziger and Roy Friedman.

Description

TinyLFU is a frequency-based cache admission and eviction policy that utilizes approximate counting schemes to estimate access freqency of items.

Window TinyLFU is a variation of TinyLFU that limits the size of the meta-data adapts the caching and eviction decisions to the more recent popularity of items. It adds a Window cache where new items are admitted and the window cache's victims is given a chance to be admitted to the main cache. This ensures that only frequently accessed items get a chance to be admitted to the main cache.

Find more details on the blog

How to use

1. Import the package

import "github.com/oryankibandi/w_tinyflu/pkg/wtinylfu"

2. Create an instance of the cache, pass capacity for the Window cache and Main cacherespectively as parameters.

cache, err := wtinylfu.NewCache[T](uint64(4), uint64(80))
   if err != nil {
   	fmt.Println("Error setting up...")
   	panic(err.Error())
   }

3. Store and Retrieve values

// set key
key := "city"
val := "NYC"

st.Put([]byte(key), []byte(val))

// get val
v, err := st.Get([]byte(key))

if err != nil {
	panic(err.Error())
}

fmt.Println("Val: ", v)

How to run

0. Ensure you have Go installed.

1. Clone repo

git clone git@github.com:oryankibandi/w_tinyflu.git

2. Run server

make run

3. Set Value

ubuntu@ubuntu: curl -i -X PUT http://localhost:8080/kv -H 'Content-Type=application/json' -d '{"key": "city", "val": "Amsterdam"}'
HTTP/1.1 200 OK
Content-Type: application/json
Content-Length: 33

{"key":"city","val":"Amsterdam"}

ubuntu@ubuntu:

4. Retrieve Value

ubuntu@ubuntu: curl -i http://localhost:8080/kv/city
HTTP/1.1 200 OK
Content-Type: application/json
Content-Length: 33

{"key":"city","val":"Amsterdam"}

ubuntu@ubuntu: