eviction.go - Overview

1. Overview This file defines the interfaces, data structures, and a base implementation for eviction strategies used in a key-value store. It includes definitions for tracking eviction statistics, representing eviction results, defining access types, and managing the eviction process.

2. Detailed Documentation

EvictionStats

type EvictionStats struct {
	totalEvictions     uint64
	totalKeysEvicted   uint64
	lastEvictionCount  int64
	lastEvictionTimeMs int64
}

• Purpose: EvictionStats tracks common statistics for all eviction strategies.
  • totalEvictions: Total number of eviction cycles.
  • totalKeysEvicted: Total number of keys evicted.
  • lastEvictionCount: Number of keys evicted in the last eviction cycle.
  • lastEvictionTimeMs: Timestamp of the last eviction cycle in milliseconds.

EvictionStats.recordEviction

func (s *EvictionStats) recordEviction(count int64) {
	s.totalEvictions++
	s.totalKeysEvicted += uint64(count)
	s.lastEvictionCount = count
	s.lastEvictionTimeMs = time.Now().UnixMilli()
}

• Purpose: Updates the eviction statistics with the number of evicted keys.
  • Parameters:
    • count: The number of keys evicted. Type: int64.
  • Returns: None.

EvictionResult

type EvictionResult struct {
	Victims map[string]*object.Obj // Keys and objects that were selected for eviction
	Count   int64                  // Number of items selected for eviction
}

• Purpose: EvictionResult represents the outcome of an eviction operation.
  • Victims: A map of keys and their corresponding objects that were selected for eviction.
  • Count: The number of items selected for eviction.

AccessType

type AccessType int

const (
	AccessGet AccessType = iota
	AccessSet
	AccessDel
)

• Purpose: AccessType represents different types of access to a key.
  • AccessGet: Represents a get operation.
  • AccessSet: Represents a set operation.
  • AccessDel: Represents a delete operation.

evictionItem

type evictionItem struct {
	key          string
	lastAccessed uint32
}

• Purpose: evictionItem stores essential data needed for eviction decisions.
  • key: The key of the item.
  • lastAccessed: The last access time of the item.

EvictionStrategy

type EvictionStrategy interface {
	ShouldEvict(store *Store) int
	EvictVictims(store *Store, toEvict int)
	OnAccess(key string, obj *object.Obj, accessType AccessType)
}

• Purpose: EvictionStrategy defines the interface for different eviction strategies.
  • ShouldEvict: Checks if eviction should be triggered based on the current store state.
    • Parameters:
      • store: A pointer to the Store struct. Type: *Store.
    • Returns: The number of items that should be evicted, or 0 if no eviction is needed. Type: int.
  • EvictVictims: Evicts items from the store based on the eviction strategy.
    • Parameters:
      • store: A pointer to the Store struct. Type: *Store.
      • toEvict: The number of items to evict. Type: int.
    • Returns: None.
  • OnAccess: Called when an item is accessed (get/set).
    • Parameters:
      • key: The key of the accessed item. Type: string.
      • obj: A pointer to the accessed object. Type: *object.Obj.
      • accessType: The type of access (get/set/del). Type: AccessType.
    • Returns: None.

BaseEvictionStrategy

type BaseEvictionStrategy struct {
	stats EvictionStats
}

• Purpose: BaseEvictionStrategy provides common functionality for all eviction strategies.
  • stats: An EvictionStats struct for tracking eviction statistics.

BaseEvictionStrategy.AfterEviction

func (b *BaseEvictionStrategy) AfterEviction(result EvictionResult) {
	b.stats.recordEviction(result.Count)
}

• Purpose: Called after victims have been evicted from the store. Updates the eviction statistics.
  • Parameters:
    • result: The result of the eviction operation. Type: EvictionResult.
  • Returns: None.

BaseEvictionStrategy.GetStats

func (b *BaseEvictionStrategy) GetStats() EvictionStats {
	return b.stats
}

• Purpose: Returns the eviction statistics.
  • Parameters: None.
  • Returns: The eviction statistics. Type: EvictionStats.

getCurrentClock

func getCurrentClock() uint32 {
	return uint32(utils.GetCurrentTime().Unix()) & 0x00FFFFFF
}

• Purpose: Returns the current time as a uint32.
  • Parameters: None.
  • Returns: The current time. Type: uint32.

GetIdleTime

func GetIdleTime(lastAccessedAt uint32) uint32 {
	c := getCurrentClock()
	lastAccessedAt &= 0x00FFFFFF
	if c >= lastAccessedAt {
		return c - lastAccessedAt
	}
	return (0x00FFFFFF - lastAccessedAt) + c
}

• Purpose: Calculates the idle time since the last access.
  • Parameters:
    • lastAccessedAt: The last access time. Type: uint32.
  • Returns: The idle time. Type: uint32.

3. Code Examples None.

4. Getting Started Relevance