clfu

package module
v0.0.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 18, 2023 License: MIT Imports: 3 Imported by: 0

README

clfu

Tests Go Reference

Implementation of Constant Time LFU (least frequently used) cache in Go with concurrency safety. This implementation is based on the paper An O(1) algorithm for implementing the LFU cache eviction scheme. As opposed to priority heap based LFU cache, this algorithm provides almost O(1) insertion, retrieval and eviction operations by using Linked lists and hash-maps instead of frequency based min-heap data-structure. This algorithm trade-offs memory to improve performance.

Using the module

The codebase can be imported and used as a go-module. To add clfu as a go module dependency to your project, run:

go get github.com/Narasimha1997/clfu

Example

The example below shows some of the basic operations provided by clfu:

import (
	"clfu"
	"fmt"
)

func main() {

	// create a new instance of LFU cache with a max size, you can also use NewLazyLFUCache(size uint, lazyCacheSize uint) to use LFU cache
    // in lazy mode.
	lfuCache := clfu.NewLFUCache(3)

	// insert values, any interface{} can be used as key, value
	lfuCache.Put("u939801", 123, false)
	lfuCache.Put("u939802", 411, false)
	lfuCache.Put("u939803", 234, false)

	// insert with replace=true, will replace the value of 'u939802'
	lfuCache.Put("u939802", 512, true)

	// get the current size (should return '3')
	fmt.Printf("current_size=%d\n", lfuCache.CurrentSize())

	// get the max size (should return '3')
	fmt.Printf("max_size=%d\n", lfuCache.MaxSize())

	// check if the cache if full
	fmt.Printf("is_full=%v\n", lfuCache.IsFull())

	// get values (this will increase the frequency of given key 1)
	rawValue, found := lfuCache.Get("u939802")
	if found {
		fmt.Printf("Value of 'u939802' is %d\n", (*rawValue).(int))
	}

	rawValue, found = lfuCache.Get("u939803")
	if found {
		fmt.Printf("Value of 'u939803' is %d\n", (*rawValue).(int))
	}

	// insert new entry, should evict `u939801` now  because it is the least used element
	lfuCache.Put("u939804", 1000, false)

	// delete the entry from cache
	err := lfuCache.Delete("u939804")
	if err != nil {
		fmt.Printf("failed to delete, no key 'u939804'")
	}
}
Lazy mode

As per the algorithm specification, whenever we call a Get on given key, the linked list structure has to be modified to update the frequency of the given key by 1, in normal mode (i.e when lazy mode is disabled) the structural update to linked list is performed on every Get, this can be avoided using lazy mode, in lazy mode the frequency updates are not made immediately, instead a slice is used to keep track of the keys whose frequencies needs to be updated, once this slice reaches it's maximum capacity, the linked list is updated in bulk. The bulk update is also triggered when Put or Evict methods are called to make sure writes always happen on the correct state of the linked list, however the bulk update can also be triggered manually by calling FlushLazyCounter. This is how LFU cache can be instantiated in lazy mode:

// here 1000 is the size of the LFU cache, 10000 is the size of lazy update slice,
// i.e bulk update on the linked list will be triggered once after every 10000 gets.
lfuCache := clfu.NewLFUCache(1000, 10000)

// you can also manually trigger lazy update
lfuCache.FlushLazyCounter()

Lazy mode is best suitable when Put operations are not so frequent and Get operations occur in very high volumes.

Obtaining the cache entries as slice

The module provides AsSlice() method which can be used to obtain all the elements in LFU cache at that given point in time as a slice, the entries in the returned slice will be in the increasing order of their access frequency.

lfuCache := clfu.NewLFUCache(3)

// insert some values
lfuCache.Put("u939801", 123, false)
lfuCache.Put("u939802", 411, false)
lfuCache.Put("u939803", 234, false)

// obtain them as slice
entries := lfuCache.AsSlice()
for _, entry := range *entries {
	fmt.Printf("Frequency=%d\n", entry.Frequency)
	fmt.Printf("Key=%s\n", (*entry.Key).(string))
	fmt.Printf("Value=%d\n", (*entry.Value).(int))
}

Similarly we can also use GetTopFrequencyItems() to obtain the list entries having highest frequency value and GetLeastFrequencyItems() to get the list of entries having least frequency value.

Testing

If you want to make modifications or validate the functions locally run the following command from project root:

go test -v

This will execute the testing suite against the module:

=== RUN   TestPut
--- PASS: TestPut (0.00s)
=== RUN   TestPutWithReplace
--- PASS: TestPutWithReplace (0.00s)
=== RUN   TestComplexStructPutAndGet
--- PASS: TestComplexStructPutAndGet (0.00s)
=== RUN   TestManualEvict
--- PASS: TestManualEvict (0.00s)
=== RUN   TestDelete
--- PASS: TestDelete (0.00s)
=== RUN   TestLeastAndFrequentItemsGetter
--- PASS: TestLeastAndFrequentItemsGetter (0.00s)
=== RUN   TestMaxSizeResize
--- PASS: TestMaxSizeResize (0.00s)
=== RUN   TestConcurrentPut
--- PASS: TestConcurrentPut (2.84s)
=== RUN   TestConcurrentGet
--- PASS: TestConcurrentGet (1.42s)
=== RUN   TestConcurrentLazyGet
--- PASS: TestConcurrentLazyGet (1.54s)
PASS
ok      clfu    5.800s
Benchmarks

To run the benchmark suite, run the following command from the project root:

go test -bench=. -benchmem

This will run the benchmark suite against the module:

goos: linux
goarch: amd64
pkg: clfu
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkPut-12                          3022968               405.9 ns/op           129 B/op          6 allocs/op
BenchmarkConcurrentPut-12                2232406               522.9 ns/op           129 B/op          6 allocs/op
BenchmarkGetOperation-12                 7356638               136.7 ns/op            49 B/op          1 allocs/op
BenchmarkConcurrentGet-12                5105284               212.7 ns/op            51 B/op          1 allocs/op
BenchmarkLazyLFUGet-12                   7642183               153.8 ns/op            49 B/op          1 allocs/op
BenchmarkConcurrentLazyLFUGet-12         4828609               217.3 ns/op            51 B/op          1 allocs/op
PASS
ok      clfu    15.317s

Going with the above numbers we can achieve at max 2.46M PUTs and 7.3M GETs per second on a single core, in lazy mode we can get max 6.9M GETs. Note that the LFU cache is suitable for linear operation and not concurrent operations because all the operations need a write lock to be imposed to avoid race conditions. From the benchmarks it is evident that the performance will decrease as we perform concurrent PUT and GET because of lock-contention.

From examples/main.go we can also notice that on average, it takes 11.8s to perform 48M GETs using concurrency of 12. (tested on 12vCPU machine) and 13.4s to do the same using lazy mode.

Normal (lazy not enabled): n_goroutines=12, n_access=48000000, time_taken=11.846151472s
Lazy (with size 1000 as cache size): n_goroutines=12, n_access=48000000, time_taken=13.357687219s
Contributing

Feel free to raise issues, submit PRs or suggest improvements.

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type FrequencyNode 

type FrequencyNode struct {
	// contains filtered or unexported fields
}

`FrequencyNode` represents a node in the frequency linked list

type KeyRefNode 

type KeyRefNode[K comparable, V any] struct {
	// contains filtered or unexported fields
}

`KeyRefNode“ represents the value held on the LRU cache frequency list node

type KeyValueEntry 

type KeyValueEntry[K comparable, V any] struct {
	Key       *K   // pointer to key
	Value     *V   // pointer to value
	Frequency uint // frequency of access
}

`KeyValueEntry` represents an item in the slice representation of LFU cache

type LFUCache 

type LFUCache[K comparable, V any] struct {
	// contains filtered or unexported fields
}

`LFUCache` implements all the methods and data-structures required for LFU cache

func NewLFUCache 

func NewLFUCache[K comparable, V any](maxSize uint) *LFUCache[K, V]

`NewLFUCache` returns the new instance of LFU cache with specified size.

Parameters:

1. maxSize: `uint` representing the max size of LFU cache.

Returns: (*LFUCache) a pointer to LFU cache instance.

func NewLazyLFUCache 

func NewLazyLFUCache[K comparable, V any](maxSize uint, lazyCounterSize uint) *LFUCache[K, V]

`NewLFUCache` returns the new instance of LFU cache with specified size and lazy mode enabled.

Parameters:

1. maxSize: `uint` representing the max size of LFU cache.

2. lazyCounterSize: size of lazy counter to use, frequencies will be updated in batch or when some write happens or manually FlushLazyCounter is called. Returns: (*LFUCache) a pointer to LFU cache instance.

func (*LFUCache[comparable, any]) AsSlice 

func (lfu *LFUCache[comparable, any]) AsSlice() *[]KeyValueEntry[comparable, any]

`AsSlice` returns the list of all elements in the key lfu cache and their frequencies

Returns: a pointer to the slice of `KeyValueEntry` type, which contains the list of elements (key, value and frequency) in the current state of LFU cache.

func (*LFUCache[comparable, any]) CurrentSize 

func (lfu *LFUCache[comparable, any]) CurrentSize() uint

`CurrentSize` returns the number of elements in that cache

Returns: `uint` representing the current size

func (*LFUCache[comparable, any]) Delete 

func (lfu *LFUCache[comparable, any]) Delete(key comparable) error

`Delete` removes the specified entry from LFU cache

Parameters:

key: key is of type `KeyType` (or simply `interface{}`) which represents the key to be deleted

Returns: `error` which is nil if `key` is deleted, non-nil if there are some errors while deletion

func (*LFUCache[comparable, any]) Evict 

func (lfu *LFUCache[comparable, any]) Evict() error

`Evict` can be called to manually perform eviction

Returns: `error` if there are any errors during eviction

func (*LFUCache[comparable, any]) FlushLazyCounter 

func (lfu *LFUCache[comparable, any]) FlushLazyCounter() error

FlushLazyCounter updates the state LFU cache with pending frequency updates in lazy counter

Returns: error if lazy update fails

func (*LFUCache[comparable, any]) Get 

func (lfu *LFUCache[comparable, any]) Get(key comparable) (*any, bool)

`Get` can be called to obtain the value for given key

Parameters:

key: key: Key is of `KeyType` (or simply an `interface{}`) which represents the key, note that the key must be hashable type

Returns: `(*ValueType, bool)` - returns a pointer to the value in LFU cache if `key` exists, else it will be `nil` with `error` non-nil.

func (*LFUCache[comparable, any]) GetLeastFrequencyItems 

func (lfu *LFUCache[comparable, any]) GetLeastFrequencyItems() *[]KeyValueEntry[comparable, any]

`GetLeastFrequencyItems` returns the list of all elements in the key lfu cache and their frequencies

Returns: a pointer to the slice of `KeyValueEntry` type, which contains the list of elements (key, value and frequency) having least frequency value in the current state of the LFU cache.

func (*LFUCache[comparable, any]) GetTopFrequencyItems 

func (lfu *LFUCache[comparable, any]) GetTopFrequencyItems() *[]KeyValueEntry[comparable, any]

`GetTopFrequencyItems` returns the list of all elements in the key lfu cache and their frequencies

Returns: a pointer to the slice of `KeyValueEntry` type, which contains the list of elements (key, value and frequency) having highest frequency value in the current state of the LFU cache.

func (*LFUCache[comparable, any]) IsFull 

func (lfu *LFUCache[comparable, any]) IsFull() bool

`IsFull` checks if the LFU cache is full

Returns (true/false), `true` if LFU cache is full, `false` if LFU cache is not full

func (*LFUCache[comparable, any]) Keys 

func (lfu *LFUCache[comparable, any]) Keys() []comparable

func (*LFUCache[comparable, any]) MaxSize 

func (lfu *LFUCache[comparable, any]) MaxSize() uint

`MaxSize` returns the maximum size of the cache at that point in time

func (*LFUCache[comparable, any]) Put 

func (lfu *LFUCache[comparable, any]) Put(key comparable, value any, replace bool) error

`Put` method inserts a `<KeyType, ValueType>` to the LFU cache and updates internal data structures to keep track of access frequencies, if the cache is full, it evicts the least frequently used value from the cache.

Parameters:

1. key: Key is of `KeyType` (or simply an `interface{}`) which represents the key, note that the key must be hashable type.

2. value: Value is of `ValueType` (or simply an `interface{}`) which represents the value

3. replace: replace is a `bool`, if set to `true`, the `value` of the given `key` will be overwritten if exists, if set to `false`, an `error` is thrown if `key` already exists.

Returns: `error` if there are any errors during insertions

func (*LFUCache[comparable, any]) SetMaxSize 

func (lfu *LFUCache[comparable, any]) SetMaxSize(size uint)

`SetMaxSize` updates the max size of the LFU cache

Parameters

1. size: `uint` value which specifies the new size of the LFU cache

type LFULazyCounter 

type LFULazyCounter[K comparable] struct {
	// contains filtered or unexported fields
}

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.