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 custom offset FNV-1a Hash algorithm which is resistant to Hash DOS attacks.

• It has two options:

  • WithShards: It allows the user to customize the number of shards tlru.LRU creates.
  • WithUnsafe: It allows the Mux32 instance present for routing the internal shards to use fast pointer based conversions to achieve peak speeds.

• Both the instances have an experimental feature called Compaction. It allows the cache to fix memory fragmentation by using an expensive O(N) call. It can be used on both the instances anytime manually. It does not happen automatically.

Installation

go get -u github.com/justpranavrs/tlru

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(cacheCapacity, tlru.WithUnsafe[int, User]())

Note : For more examples, refer here

Benchmarks

Environment

• os: archlinux/amd64
• cpu : AMD Ryzen 7 260 w/ Radeon 780M Graphics

Component & Workload	Iterations	Latency	Memory	Allocations
tlru (Basic Sharded LRU Cache)
Zipf Puts	23,886,063	55.05 ns/op	10 B/op	1 allocs/op
Zipf Gets	42,368,697	30.47 ns/op	10 B/op	1 allocs/op
Zipf Mixed	23,678,805	52.33 ns/op	10 B/op	1 allocs/op
Zipf Mixed Parallel	61,236,249	19.19 ns/op	10 B/op	1 allocs/op
Random Puts	18,772,122	62.63 ns/op	15 B/op	1 allocs/op
Random Gets	40,221,781	29.62 ns/op	15 B/op	1 allocs/op
Random Mixed	20,971,242	57.95 ns/op	15 B/op	1 allocs/op
Random Mixed Parallel	72,212,966	15.43 ns/op	15 B/op	1 allocs/op
tlru (Zero Allocation, Sharded LRU Cache)
Zipf Puts	27,370,032	38.32 ns/op	0 B/op	0 allocs/op
Zipf Gets	82,687,224	14.10 ns/op	0 B/op	0 allocs/op
Zipf Mixed	31,359,452	38.13 ns/op	0 B/op	0 allocs/op
Zipf Mixed Parallel	63,528,969	17.29 ns/op	0 B/op	0 allocs/op
Random Puts	24,723,649	45.68 ns/op	0 B/op	0 allocs/op
Random Gets	80,985,068	14.77 ns/op	0 B/op	0 allocs/op
Random Mixed	32,517,832	38.02 ns/op	0 B/op	0 allocs/op
Random Mixed Parallel	87,168,492	14.36 ns/op	0 B/op	0 allocs/op
lrucore (Single Threaded LRU Cache)
Zipf Puts	27,305,832	43.23 ns/op	0 B/op	0 allocs/op
Zipf Gets	172,443,609	6.926 ns/op	0 B/op	0 allocs/op
Zipf Mixed	28,464,217	41.26 ns/op	0 B/op	0 allocs/op
Zipf Mixed Parallel	11,175,440	95.03 ns/op	0 B/op	0 allocs/op
Random Puts	20,641,852	58.40 ns/op	0 B/op	0 allocs/op
Random Gets	182,889,151	6.570 ns/op	0 B/op	0 allocs/op
Random Mixed	25,888,710	46.57 ns/op	0 B/op	0 allocs/op
Random Mixed Parallel	13,382,323	96.44 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 ...LRUOption[K, V]) (*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]) Size() int
• type LRUOption
  • func WithShards[K comparable, V any](num int) LRUOption[K, V]
  • func WithUnsafe[K comparable, V any]() LRUOption[K, V]

Examples

• Cache

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)

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

	// 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, it removes its 'LRU', but not the globally oldest item in the cache.

mux.Mux32 takes care of routing the shards to their containers consistently using the FNV-1a non cryptographic hashing algorithm. It uses a custom offset unlike the fixed offset to prevent Hash DOS attacks.

func New

func New[K comparable, V any](capacity int, opts ...LRUOption[K, V]) (*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.Mux32 for shard routing.

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.

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.

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.

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.

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.

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.

type LRUOption

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

LRUOption allows the use of custom options on the New method of LRU.

func WithShards

func WithShards[K comparable, V any](num int) LRUOption[K, V]

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 [err.ErrNoShards] if num is less than 1.

func WithUnsafe

func WithUnsafe[K comparable, V any]() LRUOption[K, V]

WithUnsafe provides a faster routing method to [Mux32] by using Go's unsafe package. It does byte conversion with worrying about Go's Garbage Collector (GC).