tlru

package module
v0.4.0 Latest Latest
Warning

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

 Go to latest Published: Jun 21, 2026 License: BSD-3-Clause Imports: 5 Imported by: 0

README

tlru

Made with Go GoDoc Reference Go Report Card CI License GitHub stars

tlru is a high-performance, array-based LRU cache for Go with zero runtime allocations and zero dependencies. It also supports utilizing multiple independent shards to eliminate lock contention and allow high-concurrency operations without bottlenecks. It supports the use of operations for batches and allows a lot of customization, without compromising performance.

NOTE: The current version has no support for TTL. It will be added in the future versions.
Built with Go 1.24. Supports Go 1.24+

Table of Contents

Introduction

How does lrucore.Core work?
  • The lrucore.Core uses an array-based doubly linked list with int32 indices. This guarantees zero runtime allocations.
  • Each of these instances have a mutex lock to ensure safety in concurrent operations.
  • lrucore.Core has Go's support for generics.
  • It has optimized batch operations like GetMany and PutMany which reduce the locking contention during high workloads. This is only limited to lrucore.Core.
What is tlru.LRU?
  • While lrucore.Core is incredibly powerful, struggles under heavy concurrent workloads. That is where tlru.LRU shines. It uses a sharded architecture, consisting of many lrucore.Core instances. Since each Instance is protected by a mutex lock, tlru.LRU doesn't need its own mutex lock.
  • It doesn't undergo a global based eviction. It uses a shard-based local eviction for its keys. The more the shards, the lesser the chance to evict the global least recently used key. To use the global based approach, use lrucore.Core.
  • It uses a mux.Mux to route the key to one of its shards.
  • It has two options:
    • WithShards: It allows the user to customize the number of shards tlru.LRU creates.
    • WithMux: It allows the configuration of mux.Mux.
What is a mux.Mux?
  • A Mux is a router for the shards which uses a hashing algorithm to distribute the keys evenly across the instances.
  • The default hashing algorithms provided in this package are FNV-1a, xxHash32 and Go's hash/maphash. The last one has support for float, complex and struct which the FNV-1a and xxHash32 don't provide.
  • WithMux option allows the configuration by passing a custom hash function of type mux.Mux to the LRU.

For a detailed walkthrough, refer here

Installation

go get -u github.com/justpranavrs/tlru@v0.4.0

Examples

It is very easy to setup a basic LRU cache instance.

Basic LRU Cache
package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

func main() {
	// create a new LRU cache instance.
    // default number of containers is 128.
	cache, err := tlru.New[int, int](1000000)
	if err != nil {
		fmt.Printf("lru cache initialization error: %v", err)
	}
	cache.Put(1, 18)

	val, ok := cache.Get(1)
	if !ok {
		fmt.Println("key not present in cache")
	}
	fmt.Println(val) // 18
}
Customization

To customize the Cache

cache, err := tlru.New[int, User](cacheCapacity, tlru.WithShards(64))
Note : For more examples, refer here

Benchmarks

Environment
  • os: archlinux/amd64
  • cpu: AMD Ryzen 7 260 w/ Radeon 780M Graphics
Performance
  • tlru.LRU with 64 shards:
[ Zipf Data ]
  Puts-16                             36164115       34.87 ns/op       0 B/op       0 allocs/op
  Gets-16                             97302411       13.20 ns/op       0 B/op       0 allocs/op
  Mixed-16                            34324671       35.01 ns/op       0 B/op       0 allocs/op
    Hits : 10739429, Miss : 23585242, Ratio: 0.3129
  Mixed_Parallel-16                   53400261       22.07 ns/op       0 B/op       0 allocs/op

[ Random Data ]
  Puts-16                             29226392       41.45 ns/op       0 B/op       0 allocs/op
  Gets-16                             81335832       13.05 ns/op       0 B/op       0 allocs/op
  Mixed-16                            34635925       34.57 ns/op       0 B/op       0 allocs/op
    Hits : 539935, Miss : 34095990, Ratio: 0.0156
  Mixed_Parallel-16                   76091194       16.21 ns/op       0 B/op       0 allocs/op
  • tlru.LRU with 128 shards (Default):
[ Zipf Data ]
  Puts-16                             35838956       35.16 ns/op       0 B/op       0 allocs/op
  Gets-16                             91117611       13.18 ns/op       0 B/op       0 allocs/op
  Mixed-16                            32812344       35.68 ns/op       0 B/op       0 allocs/op
    Hits : 10086308, Miss : 22726036, Ratio: 0.3074
  Mixed_Parallel-16                   56536936       19.55 ns/op       0 B/op       0 allocs/op

[ Random Data ]
  Puts-16                             29004740       42.09 ns/op       0 B/op       0 allocs/op
  Gets-16                             73972798       13.77 ns/op       0 B/op       0 allocs/op
  Mixed-16                            32143723       35.59 ns/op       0 B/op       0 allocs/op
    Hits : 503441, Miss : 31640282, Ratio: 0.0157
  Mixed_Parallel-16                   97455319       11.89 ns/op       0 B/op       0 allocs/op
  • tlru.LRU with 256 shards:
[ Zipf Data ]
  Puts-16                             33154726       35.86 ns/op       0 B/op       0 allocs/op
  Gets-16                             82692465       14.05 ns/op       0 B/op       0 allocs/op
  Mixed-16                            34448319       34.63 ns/op       0 B/op       0 allocs/op
    Hits : 10296718, Miss : 24151601, Ratio: 0.2989
  Mixed_Parallel-16                   65244442       17.40 ns/op       0 B/op       0 allocs/op

[ Random Data ]
  Puts-16                             27685598       44.87 ns/op       0 B/op       0 allocs/op
  Gets-16                             82208396       14.34 ns/op       0 B/op       0 allocs/op
  Mixed-16                            33635023       37.73 ns/op       0 B/op       0 allocs/op
    Hits : 525149, Miss : 33109874, Ratio: 0.0156
  Mixed_Parallel-16                  100000000       10.10 ns/op       0 B/op       0 allocs/op
  • lrucore.Core:
[ Zipf Data ]
  Puts-16                             30797480       37.65 ns/op       0 B/op       0 allocs/op
  Gets-16                            169850612        7.11 ns/op       0 B/op       0 allocs/op
  Mixed-16                            33556694       36.07 ns/op       0 B/op       0 allocs/op
    Hits : 10637908, Miss : 22918786, Ratio: 0.3170
  Mixed_Parallel-16                   15446341       85.77 ns/op       0 B/op       0 allocs/op

[ Random Data ]
  Puts-16                             21273944       55.90 ns/op       0 B/op       0 allocs/op
  Gets-16                            173406368        6.86 ns/op       0 B/op       0 allocs/op
  Mixed-16                            25647774       45.42 ns/op       0 B/op       0 allocs/op
    Hits : 400380, Miss : 25247394, Ratio: 0.0156
  Mixed_Parallel-16                   14873089       93.58 ns/op       0 B/op       0 allocs/op

License

Copyright(c) 2026 Pranav R S

Licensed under BSD-3-Clause

Documentation

Index

Examples

Constants

View Source 
const DefaultShards int = 128

DefaultShards represents the number of shards allocated to LRU if WithShards option is not configured.

Variables

View Source 
var (
	// ErrInvalidCapacity is returned by [New] when an invalid cache capacity is passed as argument.
	ErrInvalidCapacity = errors.New("invalid LRU cache capacity: must be in the range of int32 and greater than or equal to twice the number of shards")

	// ErrInvalidShards is returned by [New] when an invalid number of shards is passed using WithShards.
	ErrInvalidShards = errors.New("invalid number of shards: must be in the range of int32 and greater than 0")
)

Functions

This section is empty.

Types

type Cache 

type Cache[K comparable, V any] interface {
	// Capacity returns the maximum allocated capacity of the LRU cache.
	Capacity() int

	// Flush clears the LRU cache of all its keys and values.
	Flush()

	// Get retrieves the cache value using key.
	// It returns false if the key is not found.
	Get(key K) (V, bool)

	// Peek retrieves the cache value without updating it
	// to be the most recently used.
	// It returns false if the key is not found.
	Peek(key K) (V, bool)

	// Put adds a new value to the cache with the given key.
	Put(key K, value V)

	// Upsert adds a new value to the cache with the given key.
	// It returns a value based on how the internal state of the cache changed.
	Upsert(key K, value V) lrucore.UpsertState

	// ResetStats resets the stats of the LRU cache.
	ResetStats()

	// Shards returns the number of sharded instances in the LRU cache.
	Shards() int

	// Size returns the current size of the LRU cache.
	Size() int

	// Stats return the current stats of the LRU cache.
	Stats() lrucore.CoreStats
}

Cache defines the general implementation of a 'Least Recently Used' cache. It has thread-safe operations.

As Items are Added to the Cache, The 'Least Recently Used' key is evicted from the Cache.

K represents the type of the key, whereas V represents the type of the Value in the cache

Example

ExampleCache shows a small example of how to initialize a LRU instance and do basic operations like Put, Size, Peek and Capacity. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](256) // create a lru instance
	if err != nil {
		fmt.Printf("[ERROR] could not initialize LRU instance: %v", err)
		return
	}

	cache.Put(1, Member{ // insert in user data with user id 1
		Name:  "justpranavrs",
		Email: "iliketlru@gmail.com",
	})

	fmt.Println(cache.Size()) // gets the current size of the cache

	_, ok := cache.Peek(2)
	fmt.Println(ok)

	_, ok = cache.Peek(1)
	fmt.Println(ok) // reports whether key 1 is present in the cache

	fmt.Println(cache.Capacity())

	cache.Flush()
	fmt.Println(cache.Size())
	fmt.Println(cache.Capacity()) // capacity allocated for the cache

}

Output:
1
false
true
256
0
256

type LRU 

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

LRU is the better implementation of lrucore.Core. It is a 'Least Recently Used' cache with many instances of lrucore.Core to prevent mutual extension locks on a single instance. It has thread-safe but not a completely lock free operations.

It doesn't work on the standard principle of LRU, rather when the mux routes it to a lrucore.Core instance. LRU works on shard-local based eviction not on globally oldest item in the cache.

mux.Mux takes care of routing the shards to their containers consistently using its hashing algorithm. The default mux is mux.NewMH32.

func New 

func New[K comparable, V any](capacity int, opts ...Option) (*LRU[K, V], error)

New creates a LRU instance with the given capacity and options. It creates the required lrucore.Core instances, initiates the mux.Mux for shard routing. It defaults to the Mux with hash/maphash algorithm. Check `tlru/mux` package for alternatives.

Returns ErrInvalidShards if shards is not greater than 0 and in [int32] range.

Returns ErrInvalidCapacity if capacity is not in [int32] range and greater than number of shards.

func (*LRU[K, V]) Capacity 

func (l *LRU[K, V]) Capacity() int

Capacity returns the maximum allocated capacity of the LRU cache across all sharded instances of lrucore.Core.

Example

ExampleLRU_Capacity shows an example of how Capacity works. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](256) // create a lru instance
	if err != nil {
		fmt.Printf("[ERROR] could not initialize LRU instance: %v", err)
		return
	}

	fmt.Println(cache.Capacity())

}

Output:
256

func (*LRU[K, V]) Flush 

func (l *LRU[K, V]) Flush()

Flush clears the LRU cache of all its keys and values across all sharded instances.

func (*LRU[K, V]) Get 

func (l *LRU[K, V]) Get(key K) (V, bool)

Get retrieves the cache value using key. It returns false if the key is not found. It updates the key as 'recent' only in its respective shard.

Example

ExampleLRU_Get shows an example of how Get works and how to handle when the key is not found in the cache. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](256)
	if err != nil {
		fmt.Printf("[ERROR] could not initialize LRU instance: %v", err)
		return
	}

	cache.Put(1, Member{
		Name:  "justpranavrs",
		Email: "iliketlru@gmail.com",
	})
	val, ok := cache.Get(1)
	if !ok {
		fmt.Println("[GET] could not find the key in the cache.")
	} else {
		fmt.Printf("[GET] Name : %v | Email : %v\n", val.Name, val.Email)
	}

	val, ok = cache.Get(2)
	if !ok {
		fmt.Println("[GET] could not find the key in the cache.")
	} else {
		fmt.Printf("[GET] Name : %v | Email : %v\n", val.Name, val.Email)
	}
}

Output:
[GET] Name : justpranavrs | Email : iliketlru@gmail.com
[GET] could not find the key in the cache.

func (*LRU[K, V]) Peek added in v0.3.0 

func (l *LRU[K, V]) Peek(key K) (V, bool)

Peek retrieves the cache value without updating it to be the most recently used. It returns false if the key is not found.

Example

ExampleLRU_Peek shows an example of how Peek works. It doesn't disturb the internal state of the cache. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](2, tlru.WithShards(1))
	if err != nil {
		fmt.Printf("[ERROR] could not initialize Core instance: %v", err)
		return
	}

	cache.Put(1, Member{
		Name:  "justpranavrs",
		Email: "iliketlru@gmail.com",
	})
	cache.Put(3, Member{
		Name:  "welcometotlru",
		Email: "welcometotlru@gmail.com",
	})
	val, ok := cache.Get(1)
	if !ok {
		fmt.Println("[GET] could not find the key in the cache.")
	} else {
		fmt.Printf("[GET] Name : %v | Email : %v\n", val.Name, val.Email)
	}

	val, ok = cache.Peek(3)
	if !ok {
		fmt.Println("[GET] could not find the key in the cache.")
	} else {
		fmt.Printf("[GET] Name : %v | Email : %v\n", val.Name, val.Email)
	}
	cache.Put(2, Member{
		Name:  "tlru",
		Email: "tlruisthebest@gmail.com",
	})
	_, ok = cache.Peek(3)
	fmt.Println(ok)

}

Output:
[GET] Name : justpranavrs | Email : iliketlru@gmail.com
[GET] Name : welcometotlru | Email : welcometotlru@gmail.com
false

func (*LRU[K, V]) Put 

func (l *LRU[K, V]) Put(key K, value V)

Put adds a new value to the cache with the given key. It updates the key as 'recent' only in its respective shard. It evicts the key only from the respective shard the key is linked to.

Example

ExampleLRU_Put shows an example of how Put works and showcases the least recently used key getting evicted in a LRU cache. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](256)
	if err != nil {
		fmt.Printf("[ERROR] could not initialize LRU instance: %v", err)
		return
	}

	cache.Put(1, Member{
		Name:  "justpranavrs",
		Email: "iliketlru@gmail.com",
	})
	_, ok := cache.Peek(2)
	fmt.Println(ok)

	_, ok = cache.Peek(1)
	fmt.Println(ok)

	cache.Put(2, Member{
		Name:  "welcometotlru",
		Email: "welcometotlru@gmail.com",
	})

	_, ok = cache.Peek(2)
	fmt.Println(ok)

	cache.Put(3, Member{
		Name:  "justpranavrs",
		Email: "tlruiscool@gmail.com",
	})

	_, ok = cache.Peek(4)
	fmt.Println(ok)

	_, ok = cache.Peek(3)
	fmt.Println(ok)

}

Output:
false
true
true
false
true

func (*LRU[K, V]) ResetStats added in v0.4.0 

func (l *LRU[K, V]) ResetStats()

ResetStats resets the stats of the sharded LRU cache.

func (*LRU[K, V]) Shards added in v0.3.0 

func (l *LRU[K, V]) Shards() int

Shards returns the number of sharded instances in the LRU cache.

func (*LRU[K, V]) Size 

func (l *LRU[K, V]) Size() int

Size returns the current size of the LRU cache across all sharded instances.

Example

ExampleLRU_Size shows an example on how Size works. It returns the current size of the LRU cache. 

package main

import (
	"fmt"

	"github.com/justpranavrs/tlru"
)

// Member is the type of the value stored in the cache.
type Member struct {
	Name  string
	Email string
}

func main() {
	cache, err := tlru.New[int, Member](256)
	if err != nil {
		fmt.Printf("[ERROR] could not initialize LRU instance: %v", err)
		return
	}

	fmt.Println(cache.Size())
	cache.Put(1, Member{
		Name:  "justpranavrs",
		Email: "iliketlru@gmail.com",
	})
	fmt.Println(cache.Size())

}

Output:
0
1

func (*LRU[K, V]) Stats added in v0.4.0 

func (l *LRU[K, V]) Stats() lrucore.CoreStats

Stats return the current stats of the sharded LRU cache.

func (*LRU[K, V]) Upsert added in v0.4.0 

func (l *LRU[K, V]) Upsert(key K, value V) lrucore.UpsertState

Upsert adds a new value to the cache with the given key. It returns a value based on how the internal state of the cache changed. It evicts or updates locally on the shard, instead of global cache. Returns a value lrucore.UpsertState.

type Option added in v0.2.0 

type Option func(c *config) error

Option is used to configure LRU when creating an instance using New constructor.

func WithMux added in v0.2.0 

func WithMux[K comparable](cm mux.Mux[K]) Option

WithMux requires a custom mux.Mux type function. It is used with LRU to configure its mux, which is responsible for routing the shards.

func WithShards 

func WithShards(num int) Option

WithShards assigns the LRU instance with num shards. Shards are separate instances of lrucore.Core to prevent mutex locks from slowing down the cache.

Returns ErrInvalidShards if num is not in [int32] range or equals zero.

Source Files

View all Source files

Directories

Path Synopsis
internal
mathutil
testutil

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.