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.22+

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.MuxHash 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.MuxHash.

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

goos: linux
goarch: amd64
pkg: github.com/justpranavrs/tlru
cpu: AMD Ryzen 7 260 w/ Radeon 780M Graphics

BenchmarkLRUWith64/Zipf_Puts-16                     33895142      35.50 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Gets-16                    100000000      10.74 ns/op       0 B/op       0 allocs/op
Hits : 10346504, Miss : 22689820, Ratio: 0.3132

BenchmarkLRUWith64/Zipf_Mixed-16                    33036324      34.23 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Zipf_Mixed_Parallel-16           59677258      19.84 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Puts-16                   28279300      42.84 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Gets-16                  100000000      11.16 ns/op       0 B/op       0 allocs/op
Hits : 530268, Miss : 33483160, Ratio: 0.0156

BenchmarkLRUWith64/Random_Mixed-16                  34013428      34.95 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith64/Random_Mixed_Parallel-16         76379761      15.54 ns/op       0 B/op       0 allocs/op

BenchmarkLRU/Zipf_Puts-16                           32656112      36.36 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Zipf_Gets-16                          100000000      11.24 ns/op       0 B/op       0 allocs/op
Hits : 10665195, Miss : 23736553, Ratio: 0.3100

BenchmarkLRU/Zipf_Mixed-16                          34401748      34.94 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Zipf_Mixed_Parallel-16                 60444584      19.27 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Random_Puts-16                         28685742      41.55 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Random_Gets-16                        100000000      11.01 ns/op       0 B/op       0 allocs/op
Hits : 565990, Miss : 35638611, Ratio: 0.0156

BenchmarkLRU/Random_Mixed-16                        36204601      33.29 ns/op       0 B/op       0 allocs/op
BenchmarkLRU/Random_Mixed_Parallel-16              100000000      11.78 ns/op       0 B/op       0 allocs/op

BenchmarkLRUWith256/Zipf_Puts-16                    34739044      37.05 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Zipf_Gets-16                    90376778      11.86 ns/op       0 B/op       0 allocs/op
Hits : 8720847, Miss : 20926643, Ratio: 0.2942

BenchmarkLRUWith256/Zipf_Mixed-16                   29647490      37.26 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Zipf_Mixed_Parallel-16          73194765      16.23 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Random_Puts-16                  28679670      41.81 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Random_Gets-16                 100000000      11.42 ns/op       0 B/op       0 allocs/op
Hits : 556574, Miss : 35059573, Ratio: 0.0156

BenchmarkLRUWith256/Random_Mixed-16                 35616147      32.98 ns/op       0 B/op       0 allocs/op
BenchmarkLRUWith256/Random_Mixed_Parallel-16       100000000      10.06 ns/op       0 B/op       0 allocs/op
PASS
ok      github.com/justpranavrs/tlru    117.784s

---

goos: linux
goarch: amd64
pkg: github.com/justpranavrs/tlru/lrucore
cpu: AMD Ryzen 7 260 w/ Radeon 780M Graphics

BenchmarkLRUCore/Zipf_Puts-16                       28624830      42.47 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Zipf_Gets-16                      176645416       6.66 ns/op       0 B/op       0 allocs/op
Hits : 9701277, Miss : 20902822, Ratio: 0.3170

BenchmarkLRUCore/Zipf_Mixed-16                      30604099      39.83 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Zipf_Mixed_Parallel-16             12427209     100.40 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Random_Puts-16                     18420439      59.85 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Random_Gets-16                    173226816       6.78 ns/op       0 B/op       0 allocs/op
Hits : 381034, Miss : 24014774, Ratio: 0.0156

BenchmarkLRUCore/Random_Mixed-16                    24395808      48.63 ns/op       0 B/op       0 allocs/op
BenchmarkLRUCore/Random_Mixed_Parallel-16           13277698     101.00 ns/op       0 B/op       0 allocs/op
PASS
ok      github.com/justpranavrs/tlru/lrucore    40.171s

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]) GetQuiet(key K) (V, bool)
  • func (l *LRU[K, V]) Put(key K, value V)
  • func (l *LRU[K, V]) PutGrows(key K, value V) bool
  • func (l *LRU[K, V]) Size() int
• type Option
  • func WithMux[K comparable](cm mux.MuxHash[K]) Option
  • func WithShards(num int) Option

Examples

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

Constants

const DefaultShards uint32 = 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)

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

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

	// PutGrows 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.
	PutGrows(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.MuxHash 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.MuxHash for shard routing.

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

Returns errs.ErrInvalidCapacity if capacity is not in [uint32] 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]) GetQuiet

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

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

Example

ExampleLRU_GetQuiet shows an example of how GetQuiet 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.GetQuiet(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]) PutGrows

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

PutGrows 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]) 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.MuxHash[K]) Option

WithMux requires a custom mux.MuxHash 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.

For performance optimizations, number of shards are automatically rounded up to the next power of 2.

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