SIEVE Cache: The Future of Efficient Caching

Abu Bakar
4 min readJan 15, 2025

--

“There are only two hard things in Computer Science: cache invalidation and naming things.” — Phil Karlton

If you’ve ever worked with caching, you know this isn’t a joke — it’s a reality! Cache invalidation is one of the trickiest problems in computer science.

While I can’t help you with naming your variables (just call it data and move on 😅), I can introduce you to SIEVE (Size-Inclusive Eviction Engine)—an advanced cache replacement algorithm that’s outperforming traditional approaches like LRU (Least Recently Used).

Why LRU Is No Longer Enough

LRU has been the default choice for cache replacement for decades, but the demands of modern applications reveal its shortcomings. Here’s why:

  • Variable Object Sizes: Small JSON responses and large media files coexist in modern caches.
  • Unpredictable Access Patterns: Bursty workloads are the norm, not the exception.
  • Limited Cache Capacity: Caches often struggle with working sets larger than their size.
  • Mixed Workloads: Traditional eviction strategies aren’t enough for diverse read/write operations environments.

The result? LRU often falls short, leading to inefficient caching and higher latency. That’s where SIEVE steps in.

What Makes SIEVE Different?

SIEVE tackles the modern challenges of caching with a dynamic, size-aware approach. It introduces innovative strategies that go beyond the limitations of LRU:

1. Size-Aware Eviction

  • Tracks the size of each cached entry.
  • Eviction decisions consider object size alongside access patterns.
  • Ensures large objects don’t monopolize limited cache space.

2. Admission Control

  • Uses probabilistic methods to decide which objects enter the cache.
  • Factors in size, access frequency, and historical hit rates.
  • Reduces cache pollution by prioritizing smaller, frequently accessed objects.

3. Ghost Cache

  • Stores metadata about recently evicted items.
  • Learns from eviction history to make smarter decisions about readmission.
  • Adapts dynamically to changing access patterns, improving cache efficiency.

These features allow SIEVE to achieve 15–30% better hit rates than LRU, particularly for workloads with variable object sizes.

SIEVE Implementation in Go

Below is an outline of key components of the SIEVE caching algorithm in Go. For the complete implementation, check the GitHub repository.

Key Structure

type Config[K comparable, V any] struct {
Capacity int64
GhostSize int
AdmitThreshold float64
Logger *slog.Logger
MaxEntrySize int64
TTL time.Duration
}

Sample Methods

Set Method: Handles cache additions with size constraints, TTL, and admission control.

func (c *SieveCache[K, V]) Set(ctx context.Context, key K, value V, size int64) error {
if c.closed.Load() {
return ErrCacheClosed
}

select {
case <-ctx.Done():
return ctx.Err()
default:
if size > c.capacity {
return ErrEntrySizeTooLarge
}

if c.maxEntrySize > 0 && size > c.maxEntrySize {
return fmt.Errorf("entry size %d exceeds maximum allowed size %d", size, c.maxEntrySize)
}

c.mu.Lock()
defer c.mu.Unlock()

if !c.shouldAdmit(key, size) {
return nil
}

var expiry time.Time
if c.ttl > 0 {
expiry = time.Now().Add(c.ttl)
}

if existing, exists := c.items[key]; exists {
c.currentSize.Add(-existing.size)
delete(c.items, key)
}

c.evictEntries(size)

newEntry := &entry[K, V]{
key: key,
value: value,
size: size,
created: time.Now(),
expiry: expiry,
}

newEntry.accessed.Store(time.Now().Unix())
newEntry.freq.Store(1)

c.items[key] = newEntry
c.currentSize.Add(size)

return nil
}
}

Get Method: Retrieves cached items while updating access statistics.

func (c *SieveCache[K, V]) Get(ctx context.Context, key K) (V, bool) {
if c.closed.Load() {
var zero V
return zero, false
}

select {
case <-ctx.Done():
var zero V
return zero, false
default:
c.mu.RLock()
entry, exists := c.items[key]
c.mu.RUnlock()

if !exists {
c.missCount.Add(1)
var zero V
return zero, false
}

if !entry.expiry.IsZero() && time.Now().After(entry.expiry) {
c.mu.Lock()
if _, exists := c.items[key]; exists {
c.removeEntry(key)
}
c.mu.Unlock()
c.missCount.Add(1)
var zero V
return zero, false
}

entry.accessed.Store(time.Now().Unix())
entry.freq.Add(1)
c.hitCount.Add(1)

return entry.value, true
}
}

Eviction Logic: Evicts the least valuable entries based on size and access frequency.

Usage Example

Here’s how to set up and use the SIEVE cache in a Go application:

func main() {
logger := slog.New(slog.NewTextHandler(os.Stdout, &slog.HandlerOptions{
Level: slog.LevelDebug,
}))

config := sieve.Config[string, []byte]{
Capacity: 100 * 1024 * 1024,
GhostSize: 50,
AdmitThreshold: 0.3,
Logger: logger,
MaxEntrySize: 10 * 1024 * 1024,
TTL: time.Hour,
}

cache, err := sieve.NewSieveCacheWithConfig(config)
if err != nil {
logger.Error("Failed to create cache", "error", err)
os.Exit(1)
}
defer cache.Close()

//Add an item to the cache
cache.Set(context.Background(), "fruit", []byte("apple"), 1024)

//Retrieve an item from the cache
if value, exists := cache.Get(context.Background(), "fruit"); exists {
fmt.Println("Cache Hit:", string(value))
}
}

Why SIEVE Outperforms LRU

Real-World Benefits

  • Higher Hit Rates: Achieves 15–30% better hit rates for variable-sized objects.
  • Better Memory Utilization: Effectively balances object size and frequency.
  • Handles Burst Traffic: Adapts dynamically, reducing cache churn and improving efficiency.
  • Faster Access Times: Prioritizes frequently accessed items.

Trade-offs to Consider

While SIEVE provides significant benefits, it does have trade-offs:

  1. Increased Complexity: Includes ghost cache management and probabilistic admission.
  2. Tuning Required: Admission probabilities and thresholds need adjustment for optimal results.
  3. Higher Overhead: Slightly more computational and memory costs compared to LRU.

Despite these, SIEVE’s advantages often outweigh the complexity for most modern applications.

Conclusion

While SIEVE is more complex than LRU, its benefits often outweigh the complexity of implementation. It redefines what’s possible in cache replacement strategies by considering size, access frequency, and historical patterns, it provides a smarter, more efficient alternative to LRU.

Consider using SIEVE when:

  • Your cached objects vary significantly in size
  • You need better adaptation to changing access patterns
  • Traditional LRU isn’t providing optimal performance

Ready to level up your caching game? Dive into the full implementation in my GitHub repository.

--

--

Abu Bakar
Abu Bakar

Written by Abu Bakar

Polyglot Software Engineer | Building end-to-end, turnkey solutions for web | Designer who loves minimalism

No responses yet