clock

Documentation

Overview

Package clock provides a thread-safe Clock (Second Chance) cache implementation.

When to Use Clock

Use Clock when you want LRU-like behavior with simpler implementation and potentially better performance characteristics. Clock is ideal for:

• Memory-constrained environments where simpler data structures help
• Workloads where approximate LRU is sufficient
• Systems where you want second-chance behavior for recently accessed items

How Clock Works

Clock uses a circular buffer with a "hand" pointer and reference bits:

1. Each item has a reference bit, set to true when accessed
2. On eviction, the hand sweeps the buffer looking for items to evict
3. If an item's reference bit is true, it gets a "second chance": bit cleared, hand moves on
4. If an item's reference bit is false, it's evicted

This approximates LRU: frequently accessed items keep getting their bit set, surviving eviction sweeps.

Thread Safety

All methods are safe for concurrent use. The cache uses a mutex internally.

Performance

All operations (Get, Set, Delete, Peek, Len) are O(1) amortized.

Example Usage

cache := clock.New[string, int](100)
cache.Set("key", 42)
cache.Get("key")        // Sets reference bit
// On eviction, "key" gets a second chance

Index

• type Cache
  • func New[K comparable, V any](capacity uint64) *Cache[K, V]
  • func (c *Cache[K, V]) Delete(key K) bool
  • func (c *Cache[K, V]) Get(key K) (V, bool)
  • func (c *Cache[K, V]) Len() uint64
  • func (c *Cache[K, V]) Peek(key K) (V, bool)
  • func (c *Cache[K, V]) Set(key K, value V)

Types

type Cache

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

Cache implements a Clock cache (also known as Second Chance).

It approximates LRU with O(1) access time by using a circular buffer and a reference bit instead of reordering on every access. When an item is accessed, its reference bit is set. During eviction, items with set bits get a "second chance" (bit cleared), while items with cleared bits are evicted.

The zero value is not usable; create instances with New.

func New

func New[K comparable, V any](capacity uint64) *Cache[K, V]

New creates a new Clock cache with the specified maximum capacity.

The capacity determines how many key-value pairs the cache can hold. When this limit is exceeded, items are evicted using the clock algorithm.

Example:

cache := clock.New[string, *Session](1000)

func (*Cache[K, V]) Delete

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

Delete removes a key from the cache.

Returns true if the key existed and was removed, false if the key was not found. The slot in the ring buffer is marked as empty and can be reused.

Example:

cache.Delete("invalidated-token")

func (*Cache[K, V]) Get

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

Get retrieves a value from the cache and sets its reference bit.

Returns:

• (value, true) if the key exists
• (zero value, false) if the key does not exist

Setting the reference bit gives the item a "second chance" during eviction. Use Cache.Peek if you need to check a value without affecting eviction.

Example:

if session, ok := cache.Get("session:abc"); ok {
    // session found, now protected from immediate eviction
}

func (*Cache[K, V]) Len

func (c *Cache[K, V]) Len() uint64

Len returns the current number of items in the cache.

This value is always <= the capacity specified in New.

Example:

fmt.Printf("Cache contains %d items\n", cache.Len())

func (*Cache[K, V]) Peek

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

Peek retrieves a value without setting the reference bit.

Returns:

• (value, true) if the key exists
• (zero value, false) if the key does not exist

Unlike Cache.Get, this does not give the item a "second chance" during eviction. Use Peek when you need to check a value without affecting the cache's eviction behavior.

Example:

// Check without protecting from eviction
if _, ok := cache.Peek("maybe-expired"); ok {
    // Item exists but won't get second chance
}

func (*Cache[K, V]) Set

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

Set adds or updates a key-value pair in the cache.

Behavior:

• If the key exists: updates the value and sets the reference bit (second chance)
• If the key is new and cache is full: evicts an item using clock algorithm first
• If the key is new and cache has space: simply adds the item

New items start with their reference bit cleared, making them eligible for eviction until they are accessed via Cache.Get.

Example:

cache.Set("config", configData)
cache.Set("config", newConfig)  // Updates and sets reference bit