tlru

README

tlru

tlru is a high-performance, array-based LRU cache for Go with zero runtime allocations and zero dependencies. It also supports utilizing multiple independent containers to eliminate lock contention and allow high-concurrency operations without bottlenecks.

NOTE: The current version has no support for TTL. It will be added in the future versions.

Built with Go 1.26. Supports Go 1.24+

Table of Contents

• Introduction
  • How does lrucore.LRUCore work?
  • What is tlru.LRU?
• Installation
• Examples
  • Basic LRU Cache
  • Customization
• Benchmarks
• License

Introduction

How does lrucore.LRUCore work?

• The lrucore.LRUCore 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.LRUCore has Go's support for generics.

What is tlru.LRU?

• While lrucore.LRUCore is incredibly powerful, struggles under heavy concurrent workloads. That is where tlru.LRU shines. It uses a sharded architecture, consisting of many lrucore.LRUCore 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.LRUCore.
• 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.

For a detailed walkthrough, refer here

Installation

go get -u github.com/justpranavrs/tlru@latest

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 and mux.NewF32 algorithm:

BenchmarkLRUWith64/Zipf_Puts-16                       31532216       37.47 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Gets-16                      104158029       11.54 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Mixed-16                      32247319       36.78 ns/op       0 B/op       0 allocs/op
Hits : 10177212, Miss : 22070107, Ratio: 0.3156

BenchmarkLRUWith64/Zipf_Mixed_Parallel-16             62996503       19.02 ns/op       0 B/op       0 allocs/op

BenchmarkLRUWith64/Random_Puts-16                     27204386       44.24 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Gets-16                    100000000       11.57 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Mixed-16                    32178608       37.22 ns/op       0 B/op       0 allocs/op
Hits : 503870, Miss : 31674738, Ratio: 0.0157

BenchmarkLRUWith64/Random_Mixed_Parallel-16           77972881       15.49 ns/op       0 B/op       0 allocs/op

• tlru.LRU with 64 shards and mux.NewX32 algorithm:

BenchmarkLRUWith64/Zipf_Puts-16                       33432204       35.96 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Gets-16                      100000000       11.19 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Mixed-16                      33517881       36.02 ns/op       0 B/op       0 allocs/op
Hits : 10505944, Miss : 23011937, Ratio: 0.3134

BenchmarkLRUWith64/Zipf_Mixed_Parallel-16             64254285       18.47 ns/op       0 B/op       0 allocs/op

BenchmarkLRUWith64/Random_Puts-16                     27679622       43.94 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Gets-16                    100000000       11.24 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Mixed-16                    31981122       35.51 ns/op       0 B/op       0 allocs/op
Hits : 499739, Miss : 31481383, Ratio: 0.0156

BenchmarkLRUWith64/Random_Mixed_Parallel-16           79188930       15.47 ns/op       0 B/op       0 allocs/op

• tlru.LRU with 64 shards and mux.NewMH32 algorithm:

BenchmarkLRUWith64/Zipf_Puts-16                       33054550       36.26 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Gets-16                      100000000       11.28 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Mixed-16                      33174410       35.66 ns/op       0 B/op       0 allocs/op
Hits : 10369406, Miss : 22805004, Ratio: 0.3126

BenchmarkLRUWith64/Zipf_Mixed_Parallel-16             58955106       19.96 ns/op       0 B/op       0 allocs/op

BenchmarkLRUWith64/Random_Puts-16                     27217233       44.25 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Gets-16                    100000000       11.55 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Mixed-16                    32497040       37.01 ns/op       0 B/op       0 allocs/op
Hits : 507588, Miss : 31989452, Ratio: 0.0156

BenchmarkLRUWith64/Random_Mixed_Parallel-16           77845632       15.53 ns/op       0 B/op       0 allocs/op

• tlru.LRU with 128 shards and mux.NewX32 algorithm:

BenchmarkLRU/Zipf_Puts-16                             33516466       35.88 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Zipf_Gets-16                            100000000       10.74 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Zipf_Mixed-16                            34404482       34.58 ns/op       0 B/op       0 allocs/op
Hits : 10630761, Miss : 23773721, Ratio: 0.3090

BenchmarkLRU/Zipf_Mixed_Parallel-16                   60228430       19.66 ns/op       0 B/op       0 allocs/op

BenchmarkLRU/Random_Puts-16                           28159216       42.65 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Random_Gets-16                          100000000       10.83 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Random_Mixed-16                          34258018       33.99 ns/op       0 B/op       0 allocs/op
Hits : 533000, Miss : 33725018, Ratio: 0.0156

BenchmarkLRU/Random_Mixed_Parallel-16                100000000       11.66 ns/op       0 B/op       0 allocs/op

• tlru.LRU with 256 shards and mux.NewX32 algorithm:

BenchmarkLRUWith256/Zipf_Puts-16                      34538334       34.77 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Zipf_Gets-16                     100000000       10.95 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Zipf_Mixed-16                     35645792       33.64 ns/op       0 B/op       0 allocs/op
Hits : 10676624, Miss : 24969168, Ratio: 0.2995

BenchmarkLRUWith256/Zipf_Mixed_Parallel-16            75248469       16.22 ns/op       0 B/op       0 allocs/op

BenchmarkLRUWith256/Random_Puts-16                    28202634       42.61 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Random_Gets-16                   100000000       11.24 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Random_Mixed-16                   35532368       33.46 ns/op       0 B/op       0 allocs/op
Hits : 557243, Miss : 34975125, Ratio: 0.0157

BenchmarkLRUWith256/Random_Mixed_Parallel-16         121141429       9.901 ns/op       0 B/op       0 allocs/op

• lrucore.LRUCore:

BenchmarkLRUCore/Zipf_Puts-16                         28712246       41.79 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Zipf_Gets-16                        198613611       6.069 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Zipf_Mixed-16                        30072946       40.02 ns/op       0 B/op       0 allocs/op
Hits : 9533449, Miss : 20539497, Ratio: 0.3170

BenchmarkLRUCore/Zipf_Mixed_Parallel-16               11084142       91.50 ns/op       0 B/op       0 allocs/op

BenchmarkLRUCore/Random_Puts-16                       21257362       56.26 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Random_Gets-16                      193248979       6.135 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Random_Mixed-16                      25733350       45.89 ns/op       0 B/op       0 allocs/op
Hits : 402293, Miss : 25331057, Ratio: 0.0156

BenchmarkLRUCore/Random_Mixed_Parallel-16             13872712       85.06 ns/op       0 B/op       0 allocs/op

License

Copyright(c) 2026 Pranav R S

Licensed under BSD-3-Clause

Documentation

Index

• Constants
• type Cache
• type LRU
  • func New[K comparable, V any](capacity int, opts ...Option) (*LRU[K, V], error)
  • func (l *LRU[K, V]) Capacity() int
  • func (l *LRU[K, V]) Compaction()
  • func (l *LRU[K, V]) Contains(key K) bool
  • func (l *LRU[K, V]) Flush()
  • func (l *LRU[K, V]) Get(key K) (V, bool)
  • func (l *LRU[K, V]) Peek(key K) (V, bool)
  • func (l *LRU[K, V]) Put(key K, value V)
  • func (l *LRU[K, V]) PutGrew(key K, value V) bool
  • func (l *LRU[K, V]) Shards() int
  • func (l *LRU[K, V]) Size() int
• type Option
  • func WithMux[K comparable](cm mux.Mux[K]) Option
  • func WithShards(num int) Option

Examples

• Cache
• LRU.Capacity
• LRU.Contains
• LRU.Get
• LRU.Peek
• LRU.Put
• LRU.Size

Constants

const DefaultShards int = 128

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

Types

type Cache

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

	// Compaction is an expensive O(N) operation to deal with memory fragmentation.
	Compaction()

	// Contains verifies if the key is present in the LRU Cache.
	// It does not update the key to recent status.
	Contains(key K) bool

	// 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)

	// PutGrew adds a new value to the cache with the given key.
	// It returns true if the size of the cache has grown, else returns false.
	PutGrew(key K, value V) bool

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

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, Contains 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
	fmt.Println(cache.Contains(2))

	fmt.Println(cache.Contains(1)) // 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.LRUCore. It is a 'Least Recently Used' cache with many instances of lrucore.LRUCore 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.LRUCore 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.MuxX32.Get.

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.LRUCore instances, initiates the mux.Mux for shard routing. It defaults to the Mux with xxHash32 algorithm. Check `tlru/mux` package for alternatives.

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

Returns errs.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.LRUCore.

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]) Compaction

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

Compaction is an expensive O(N) operation to deal with memory fragmentation. It compacts all keys across the sharded architecture. For more details, refer lrucore.LRUCore.Compaction

func (*LRU[K, V]) Contains

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

Contains verifies if the key is present in the LRU Cache by checking the correct sharded instance. It does not update the key to recent status.

Example

ExampleLRU_Contains shows an example of how Contains 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
	}

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

}

Output:
true
false

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

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 LRUCore 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",
	})
	fmt.Println(cache.Contains(3))

}

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",
	})
	fmt.Println(cache.Contains(2))
	fmt.Println(cache.Contains(1))

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

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

}

Output:
false
true
true
false
true

func (*LRU[K, V]) PutGrew

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

PutGrew adds a new value to the cache with the given key. It returns true if the size of the cache has grown, else returns false. It evicts or updates locally on the shard, instead of global cache.

func (*LRU[K, V]) Shards

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

type Option

type Option func(c *config) error

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

func WithMux

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.LRUCore to prevent mutex locks from slowing down the cache.

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