kahora

package module
v0.1.0 Latest Latest
Warning

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

 Go to latest Published: May 3, 2026 License: MIT Imports: 6 Imported by: 0

README

kahora

A high-performance, sharded, in-memory cache for Go — with gradual map shrink to prevent unbounded memory growth.

import "github.com/BawNer/kahora"

Go Reference Go Report Card

Why kahora

Go's built-in map does not shrink after entries are deleted or expire. In long-running services with high TTL turnover and millions of entries, this leads to unbounded heap growth — even when the live entry count is small.

kahora reconstructs shard maps gradually in the background — one shard per tick — to reclaim memory without spikes. It's designed for the painful case nobody talks about: 13–18M entries per pod, 300k+ RPS, and Go maps that never give memory back.

If you don't have this problem, you probably don't need kahora. sync.Map or a plain map[K]V with a mutex is simpler and just as fast at sub-million entry counts.

Design principles

  • Simple API — generic Cache[K, V], three methods: Get, Set, Delete.
  • Honest metrics — bring your own MetricsRecorder, or use the built-in one.
  • No magic — no auto-tuning, no hidden goroutines per shard, no surprises.
  • Fail fast — invalid options return errors at New, not at first use.
  • For developers, not over them — every knob is documented; defaults are opinionated but overridable.

Quick start

package main

import (
    "log"
    "time"

    "github.com/BawNer/kahora"
)

func main() {
    c, err := kahora.New[string, []byte](
        kahora.WithShardCount(kahora.ShardCountM), // 256 shards
        kahora.WithTTL(5 * time.Minute),
        kahora.WithActiveExpiry(30 * time.Second),
        kahora.WithMaxEntries(10_000_000),
    )
    if err != nil {
        log.Fatal(err)
    }
    defer c.Close()

    c.Set("user:42", payload)

    if v, ok := c.Get("user:42"); ok {
        use(v)
    }
}

Architecture

Sharding

The cache is partitioned into N independent shards (default 256). Each shard has its own RWMutex, its own map, and its own atomic counters. Operations on different shards never contend.

Sharding uses maphash.Comparable for zero-allocation key hashing. Shard count must be a power of two — enforced at New.

ShardCount Value Use case
ShardCountXS 16 Small caches, low concurrency
ShardCountS 64 Moderate concurrency
ShardCountM 256 Default — high concurrency
ShardCountL 1024 Very high concurrency, large memory budget
ShardCountXL 4096 Extreme concurrency
Gradual shrink

Shrink runs on a single background goroutine, processing one shard per tick via round-robin. The full cycle duration is configurable via WithShrinkCycleInterval (default 60s).

Each shrink uses a three-phase approach to minimise lock hold time:

  1. Phase 1 (write lock, brief): snapshot live entries, set the shrinking flag.
  2. Phase 2 (no lock): build a new map from the snapshot — the slow part.
  3. Phase 3 (write lock, brief): delta-merge keys mutated during phase 2, swap atomically.

A dirty set tracks keys written or deleted during phase 2, ensuring no mutation is lost even under heavy concurrent load.

Monotonic clock

All time measurements use a monotonic clock derived from time.Since(processStart). NTP adjustments, leap seconds, and manual time changes do not affect TTL behaviour.

TTL

TTL is optional. When enabled:

  • Lazy expiry is always on — expired entries are removed on Get.
  • Active expiry is opt-in via WithActiveExpiry(interval) — a background sweep removes expired entries proactively.

Without active expiry, expired entries occupy memory until either a Get removes them or shrink reconstructs the shard.

Configuration

All options validate eagerly. New returns an error if any option is invalid or options are logically inconsistent.

Option Default Description
WithShardCount(n) ShardCountM (256) Number of shards. Must be power of two.
WithTTL(d) none Global TTL for all entries.
WithActiveExpiry(interval) disabled Background sweep interval. Requires TTL.
WithMaxEntries(n) unlimited Approximate global entry cap (per-shard enforced).
WithMetricsRecorder(r) nop Custom metrics backend.
WithShrinkCycleInterval(d) 60s Full shrink cycle duration across all shards.
WithShrinkMinEntries(n) 0 Skip shrink if shard has fewer live entries than this. 
kahora.New[K, V](
    kahora.WithShardCount(kahora.ShardCountM),
    kahora.WithMaxEntries(estimatedPeak),  // pre-allocates maps, avoids growth
    kahora.WithTTL(ttl),
    kahora.WithActiveExpiry(ttl / 4),
    kahora.WithMetricsRecorder(recorder),
)

WithMaxEntries is especially important — it pre-allocates each shard's map to the expected size, avoiding the cost of incremental rehashing during steady-state writes.

Metrics

kahora exposes a MetricsRecorder interface. All methods receive a shard index, allowing per-shard observability without kahora itself aggregating anything.

type MetricsRecorder interface {
    RecordHit(shard int)
    RecordMiss(shard int)
    RecordSet(shard int)
    RecordDelete(shard int)
    RecordLazyEviction(shard int)
    RecordActiveEviction(shard int)
    RecordShrink(shard, before, after int)
    RecordCapacityExceeded(shard int)
}

Implement this against your metrics backend (Prometheus, OpenTelemetry, StatsD, etc).

Built-in DefaultRecorder

If you don't need a specific backend, use the built-in DefaultRecorder:

r := kahora.NewRecorder(kahora.ShardCountM)
c, _ := kahora.New[K, V](kahora.WithMetricsRecorder(r))

// ... later ...
snap := r.Snapshot()
fmt.Printf("hits=%d misses=%d shrinks=%d\n",
    snap.Hits, snap.Misses, len(snap.Shards))

// Per-shard breakdown for distribution analysis
for _, s := range snap.Shards {
    fmt.Printf("shard %d: hits=%d sets=%d shrinks=%d\n",
        s.Index, s.Hits, s.Sets, s.ShrinkCount)
}

Per-shard counters reveal whether keys are distributed uniformly. If one shard sees 10x more traffic than its peers, your hash function or key distribution may be off.

Reading the metrics
Signal Meaning
High LazyEvictions rate Active expiry is too infrequent or disabled.
High CapacityExceeded maxEntries is too low for your workload.
Uneven per-shard Sets Keys are not distributed uniformly.
Large LastShrinkBefore - LastShrinkAfter Shrink is reclaiming significant memory — TTL turnover is high.

Benchmarks

Measured on Apple M1 Pro, Go 1.25.

BenchmarkGetHit-10                  39.45 ns/op   0 B/op   0 allocs/op
BenchmarkGetMiss-10                 31.54 ns/op   0 B/op   0 allocs/op
BenchmarkSet-10                    245.4  ns/op  78 B/op   0 allocs/op
BenchmarkSetOverwrite-10            30.65 ns/op   0 B/op   0 allocs/op

BenchmarkParallelGetHit-10          23.41 ns/op   0 B/op   0 allocs/op
BenchmarkParallelMixed-10           27.05 ns/op   0 B/op   0 allocs/op  (95% read / 5% write)
BenchmarkParallelSet-10             96.89 ns/op  96 B/op   0 allocs/op

BenchmarkGetWithTTL-10              38.26 ns/op   0 B/op   0 allocs/op
BenchmarkGetWithDefaultRecorder-10  43.08 ns/op   0 B/op   0 allocs/op
BenchmarkGetStringKey-10            43.49 ns/op   0 B/op   0 allocs/op
Read scaling (ParallelGetHit)
Cores ns/op Speedup
1 144.9 1.00x
2 88.08 1.65x
4 46.03 3.15x
8 30.45 4.76x
16 21.85 6.63x
Shard count comparison (parallel reads)
Shards ns/op
16 25.53
64 17.07
256 15.35
1024 14.64
4096 14.30

The 256-shard default captures most of the benefit; going higher costs memory for diminishing returns.

Run benchmarks yourself:

go test -bench=. -benchmem -benchtime=3s ./...
go test -bench=Parallel -benchmem -cpu=1,2,4,8,16 ./...

When NOT to use kahora

  • You have fewer than ~1M entries. Plain map[K]V with a mutex, or sync.Map, is simpler and likely faster.
  • You need byte-aware eviction. kahora limits entry count, not bytes. Wrap it or use a different library.
  • You need a distributed cache. kahora is in-process only. Use Redis or similar.
  • You need LRU/LFU eviction. kahora evicts only by TTL or explicit Delete. There is no recency-based eviction.

Caveats

  • Approximate maxEntries. Enforced per-shard via atomic counters. The global limit may be exceeded slightly under concurrent load — this is intentional, avoiding a global lock on the hot path is worth the imprecision.
  • Shrink briefly blocks readers. Phase 1 takes a write lock to snapshot the shard. For 50k entries this is ~1–3 ms once per shrink cycle per shard. With a 60s cycle and 256 shards, any given shard is blocked once per minute.
  • Get after Close. Get and Delete remain safe after Close, but operate on a static snapshot — no further eviction or shrink occurs.
  • Power-of-two shard counts only. Required for fast bitmask-based shard selection. Validated at New.

License

MIT — see LICENSE.

Documentation

Overview

Package kahora is a high-performance, sharded, in-memory cache for Go.

kahora targets a specific pain point: Go's built-in map does not shrink after entries are deleted or expire, leading to unbounded memory growth in long-running services with high TTL turnover. kahora reconstructs shard maps gradually in the background — one shard per tick — to reclaim memory without spikes.

Design

The cache is sharded into N independent partitions (default 256). Each shard has its own RWMutex, its own map, and its own atomic counters. Operations on different shards never contend. Sharding uses maphash.Comparable for zero-allocation key hashing.

All time measurements use a monotonic clock derived from time.Since, immune to NTP adjustments and wall clock jumps.

Shrink

Shrink runs on a single background goroutine, processing one shard per tick via round-robin. The full cycle duration is configurable (default 60s).

Each shrink uses a three-phase approach to minimise lock hold time:

  1. Snapshot live entries under write lock (brief).
  2. Build a new map from the snapshot without holding any lock.
  3. Delta-merge keys mutated during phase 2 and swap atomically (brief).

A "dirty" set tracks keys written or deleted during phase 2, ensuring no mutation is lost even under heavy concurrent load.

TTL

TTL is optional. When enabled, expired entries are removed lazily on Get, or proactively by the active expiry sweep if WithActiveExpiry is set.

Limits

kahora limits entry count, not bytes. For byte-aware caching, wrap kahora or use a different library — keeping the API simple is a deliberate choice. The maxEntries limit is enforced per-shard via atomic counters and may be exceeded slightly under concurrent load.

Metrics

kahora exposes a MetricsRecorder interface — bring your own backend. A DefaultRecorder is provided with thread-safe counters and a Snapshot method for direct inspection. If no recorder is set, metrics are discarded at zero cost (the no-op implementation is inlined by the compiler).

Quick start 

c, err := kahora.New[string, []byte](
    kahora.WithShardCount(kahora.ShardCountM),
    kahora.WithTTL(5 * time.Minute),
    kahora.WithActiveExpiry(30 * time.Second),
    kahora.WithMaxEntries(10_000_000),
)
if err != nil {
    log.Fatal(err)
}
defer c.Close()

c.Set("user:42", payload)
if v, ok := c.Get("user:42"); ok {
    use(v)
}

When to use kahora

kahora is designed for read-heavy in-memory caches with millions of entries and high TTL turnover, where Go's native map memory behaviour becomes a problem. It is not a distributed cache, not a byte-aware cache, and not a replacement for Redis. For sub-million entry counts, the standard library sync.Map or a simple map+mutex will likely be simpler and equally fast.

Index

Examples

Constants

This section is empty.

Variables

View Source 
var ErrCapacityExceeded = errors.New("kahora: capacity exceeded")

ErrCapacityExceeded is returned by Set when the cache has reached its maxEntries limit. The limit is per-shard and approximate — see WithMaxEntries.

View Source 
var ErrClosed = errors.New("kahora: cache is closed")

ErrClosed is returned by Set when called on a closed cache. Get and Delete remain safe after Close but no further writes are accepted.

Functions

This section is empty.

Types

type Cache 

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

Cache is a generic, sharded, in-memory cache. Safe for concurrent use by multiple goroutines.

K must be comparable. V can be any type. Zero value is not usable — always create via New.

func New 

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

New creates a new Cache with the given options. Returns an error if any option is invalid or options are logically inconsistent.

New starts a background goroutine for shrink and active expiry (if enabled). Always call Close when the cache is no longer needed.

Example

ExampleNew demonstrates basic cache creation, Set, and Get. 

package main

import (
	"fmt"

	"github.com/BawNer/kahora"
)

func main() {
	c, err := kahora.New[string, string]()
	if err != nil {
		panic(err)
	}
	defer c.Close()

	c.Set("greeting", "hello")

	v, ok := c.Get("greeting")
	if ok {
		fmt.Println(v)
	}
}

Output:
hello
Example (WithCapacity)

ExampleNew_withCapacity demonstrates capping the cache to a maximum number of entries. Set returns ErrCapacityExceeded once the limit is reached. 

package main

import (
	"errors"
	"fmt"

	"github.com/BawNer/kahora"
)

func main() {
	c, err := kahora.New[int, int](
		kahora.WithShardCount(kahora.ShardCountXS),
		kahora.WithMaxEntries(16),
	)
	if err != nil {
		panic(err)
	}
	defer c.Close()

	for i := range 100 {
		if err := c.Set(i, i); errors.Is(err, kahora.ErrCapacityExceeded) {
			fmt.Println("hit capacity limit")
			break
		}
	}
}

Output:
hit capacity limit
Example (WithTTL)

ExampleNew_withTTL demonstrates configuring a cache with a TTL and active background expiry. 

package main

import (
	"fmt"
	"time"

	"github.com/BawNer/kahora"
)

func main() {
	c, err := kahora.New[string, int](
		kahora.WithTTL(time.Minute),
		kahora.WithActiveExpiry(10*time.Second),
	)
	if err != nil {
		panic(err)
	}
	defer c.Close()

	c.Set("counter", 42)

	if v, ok := c.Get("counter"); ok {
		fmt.Println(v)
	}
}

Output:
42

func (*Cache[K, V]) Close 

func (c *Cache[K, V]) Close()

Close stops the background goroutine and releases resources. After Close, Set returns ErrClosed. Get and Delete remain safe to call but operate on a static snapshot — no further eviction or shrink occurs.

Close is idempotent — safe to call multiple times.

Example

ExampleCache_Close demonstrates the cache lifecycle. After Close, Set returns ErrClosed but Get remains usable against the static snapshot. 

package main

import (
	"errors"
	"fmt"

	"github.com/BawNer/kahora"
)

func main() {
	c, err := kahora.New[string, string]()
	if err != nil {
		panic(err)
	}

	c.Set("k", "v")
	c.Close()

	err = c.Set("k2", "v2")
	if errors.Is(err, kahora.ErrClosed) {
		fmt.Println("cache is closed")
	}
}

Output:
cache is closed

func (*Cache[K, V]) Delete 

func (c *Cache[K, V]) Delete(key K)

Delete removes key from the cache. No-op if key does not exist or has already expired.

Example

ExampleCache_Delete demonstrates explicit removal of an entry. 

package main

import (
	"fmt"

	"github.com/BawNer/kahora"
)

func main() {
	c, err := kahora.New[string, string]()
	if err != nil {
		panic(err)
	}
	defer c.Close()

	c.Set("temp", "value")
	c.Delete("temp")

	if _, ok := c.Get("temp"); !ok {
		fmt.Println("gone")
	}
}

Output:
gone

func (*Cache[K, V]) Get 

func (c *Cache[K, V]) Get(key K) (V, bool)

Get returns the value associated with key. Returns (value, true) on hit, (zero, false) on miss or expiry. Expired entries are removed lazily on Get.

func (*Cache[K, V]) Set 

func (c *Cache[K, V]) Set(key K, value V) error

Set writes key/value into the cache. If the key already exists, it is overwritten. Returns ErrCapacityExceeded if the cache is at its maxEntries limit. Returns ErrClosed if the cache has been closed.

type DefaultRecorder 

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

DefaultRecorder is a thread-safe, zero-dependency MetricsRecorder. Use NewRecorder to create one, then pass it to New via WithMetricsRecorder. Call Snapshot at any time to read current state.

func NewRecorder 

func NewRecorder(shardCount ShardCount) *DefaultRecorder

NewRecorder creates a DefaultRecorder sized for the given shard count. Pass the same ShardCount you use in New — or use ShardCountM (256) if default.

Example

ExampleNewRecorder demonstrates using the built-in DefaultRecorder to observe cache activity without integrating an external metrics backend. 

package main

import (
	"fmt"

	"github.com/BawNer/kahora"
)

func main() {
	r := kahora.NewRecorder(kahora.ShardCountM)
	c, err := kahora.New[string, string](
		kahora.WithMetricsRecorder(r),
	)
	if err != nil {
		panic(err)
	}
	defer c.Close()

	c.Set("k", "v")
	c.Get("k")       // hit
	c.Get("missing") // miss

	snap := r.Snapshot()
	fmt.Printf("hits=%d misses=%d sets=%d\n", snap.Hits, snap.Misses, snap.Sets)
}

Output:
hits=1 misses=1 sets=1

func (*DefaultRecorder) RecordActiveEviction 

func (r *DefaultRecorder) RecordActiveEviction(_ int)

func (*DefaultRecorder) RecordCapacityExceeded 

func (r *DefaultRecorder) RecordCapacityExceeded(_ int)

func (*DefaultRecorder) RecordDelete 

func (r *DefaultRecorder) RecordDelete(_ int)

func (*DefaultRecorder) RecordHit 

func (r *DefaultRecorder) RecordHit(shard int)

func (*DefaultRecorder) RecordLazyEviction 

func (r *DefaultRecorder) RecordLazyEviction(_ int)

func (*DefaultRecorder) RecordMiss 

func (r *DefaultRecorder) RecordMiss(shard int)

func (*DefaultRecorder) RecordSet 

func (r *DefaultRecorder) RecordSet(shard int)

func (*DefaultRecorder) RecordShrink 

func (r *DefaultRecorder) RecordShrink(shard, before, after int)

func (*DefaultRecorder) Snapshot 

func (r *DefaultRecorder) Snapshot() Snapshot

Snapshot returns a point-in-time copy of all metrics. Safe to call concurrently. Non-blocking.

type MetricsRecorder 

type MetricsRecorder interface {
	// RecordHit is called when Get returns a live entry.
	RecordHit(shard int)

	// RecordMiss is called when Get returns nothing —
	// either key not found or entry expired (lazy eviction).
	RecordMiss(shard int)

	// RecordSet is called when Set writes a new or existing entry.
	RecordSet(shard int)

	// RecordDelete is called when Delete explicitly removes an entry.
	RecordDelete(shard int)

	// RecordLazyEviction is called when Get finds an expired entry and removes it.
	// High rate here means active expiry is too infrequent or disabled.
	RecordLazyEviction(shard int)

	// RecordActiveEviction is called when the background sweep removes an expired entry.
	// Requires WithActiveExpiry to be set.
	RecordActiveEviction(shard int)

	// RecordShrink is called when a shard completes map reconstruction.
	// before and after are the live entry counts before and after shrink.
	// Lets you observe how much memory pressure was relieved per cycle.
	RecordShrink(shard, before, after int)

	// RecordCapacityExceeded is called when Set is rejected because
	// the shard has reached its share of maxEntries.
	RecordCapacityExceeded(shard int)
}

MetricsRecorder is the interface for recording cache metrics. Implement this to plug in your own metrics backend (Prometheus, StatsD, etc).

All methods are called on the hot path — implementations must be non-blocking and must not allocate. If you need to batch or buffer, do it inside your implementation.

Shard index is provided where relevant — allows per-shard observability without kahora itself aggregating anything. Aggregation is your job.

type Option 

type Option func(*options) error

Option is a functional option for Cache.

func WithActiveExpiry 

func WithActiveExpiry(interval time.Duration) Option

WithActiveExpiry enables a background goroutine that proactively sweeps shards and deletes expired entries. Without this, expiry is lazy — stale entries are only evicted on Get. Requires WithTTL to be set.

func WithMaxEntries 

func WithMaxEntries(n int) Option

WithMaxEntries sets a best-effort cap on total live entries across all shards. The limit is enforced per-shard via atomic counters and may be exceeded slightly under concurrent load. This is intentional — avoiding a global lock on the hot path is worth the approximation. 0 means unlimited.

func WithMetricsRecorder 

func WithMetricsRecorder(r MetricsRecorder) Option

WithMetricsRecorder attaches a custom metrics recorder. If not set, a nop recorder is used — zero overhead.

func WithShardCount 

func WithShardCount(n ShardCount) Option

WithShardCount sets the number of shards. Use ShardCount* constants (XS/S/M/L/XL) or a custom positive value. Default: ShardCountM (256).

func WithShrinkCycleInterval 

func WithShrinkCycleInterval(d time.Duration) Option

WithShrinkCycleInterval sets the duration of one full shrink cycle across all shards. Internally: tick = cycleInterval / shardCount. One shard per tick, round-robin. Higher value = less frequent reconstruction, lower CPU/alloc pressure. Default: 60s (tick ~234ms for 256 shards).

func WithShrinkMinEntries 

func WithShrinkMinEntries(n int) Option

WithShrinkMinEntries sets the minimum number of live entries required for a shard to be eligible for reconstruction. Shards below this threshold are skipped — already small enough. 0 means always reconstruct when the cycle reaches this shard. Default: 0.

func WithTTL 

func WithTTL(ttl time.Duration) Option

WithTTL sets a global TTL for all entries. Expiry is lazy by default — checked on Get. To enable background sweep, also use WithActiveExpiry.

type ShardCount 

type ShardCount int

ShardCount defines the number of shards used by the cache. More shards — less lock contention, more memory overhead per shard. 

const (
	ShardCountXS ShardCount = 16
	ShardCountS  ShardCount = 64
	ShardCountM  ShardCount = 256 // default
	ShardCountL  ShardCount = 1024
	ShardCountXL ShardCount = 4096
)

type ShardSnapshot 

type ShardSnapshot struct {
	Index            int
	Hits             int64
	Misses           int64
	Sets             int64
	ShrinkCount      int64
	LastShrinkBefore int64
	LastShrinkAfter  int64
}

ShardSnapshot is a point-in-time snapshot of a single shard's metrics.

type Snapshot 

type Snapshot struct {
	// Global
	Hits             int64
	Misses           int64
	Sets             int64
	Deletes          int64
	LazyEvictions    int64
	ActiveEvictions  int64
	CapacityExceeded int64

	// Per-shard — use to observe distribution uniformity and shrink activity.
	Shards []ShardSnapshot
}

Snapshot is a point-in-time view of all cache metrics. Global counters are independent atomics — not derived from shards — so they are always consistent with what was actually recorded.

Source Files

View all Source files

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.