cache_rs

Module gdsf

Source
Expand description

Greedy Dual-Size Frequency (GDSF) cache implementation.

A cache replacement algorithm that combines frequency, size, and aging. Assigns priority based on (Frequency / Size) + Global_Age formula. Greedy Dual-Size Frequency (GDSF) cache implementation.

GDSF is a sophisticated cache replacement algorithm that combines frequency, size, and aging to optimize cache performance for variable-sized objects. It’s particularly well-suited for CDNs and web caches where objects have significantly different sizes.

§Algorithm

GDSF assigns a priority value to each cached item using the formula:

Priority = (Frequency * Cost_Factor / Size) + Global_Age

Where:

  • Frequency: Number of times the item has been accessed
  • Cost_Factor: Optional weighting factor (defaults to 1.0)
  • Size: Size of the item in bytes (or other cost units)
  • Global_Age: A global aging factor that increases when items are evicted

When the cache is full, the item with the lowest priority is evicted. After eviction, the global age is set to the priority of the evicted item.

§Performance Characteristics

  • Time Complexity:

    • Get: O(1)
    • Put: O(1)
    • Remove: O(1)

  • Space Complexity:

    • O(n) where n is the number of items
    • Higher overhead than LRU due to priority calculations

§Size Considerations

Unlike basic LRU or LFU caches, GDSF is size-aware and aims to maximize the hit ratio per byte of cache used. This makes it particularly effective when:

  • Items vary significantly in size
  • Storage space is at a premium
  • You want to optimize for hit rate relative to storage cost

§CDN Use Cases

GDSF is ideal for Content Delivery Networks because it:

  • Favors keeping small, frequently accessed items (e.g., thumbnails, icons)
  • Can intelligently evict large, infrequently accessed items (e.g., large videos)
  • Adapts to changing access patterns through the aging mechanism

§Thread Safety

This implementation is not thread-safe. For concurrent access, wrap the cache with a synchronization primitive such as Mutex or RwLock.

Structs§

GdsfCache
An implementation of a Greedy Dual-Size Frequency (GDSF) cache.