Class: RubyFFDB::CacheProviders::LRUCache

Inherits:
RubyFFDB::CacheProvider show all
Defined in:
lib/rffdb/cache_providers/lru_cache.rb

Overview

A very simple Least Recently Used (LRU) cache implementation. Stores data in a Hash, uses a dedicated Array for storing and sorting keys (and implementing the LRU algorithm), and doesn’t bother storing access information for cache data. It stores hit and miss counts for the entire cache (not for individual keys). It also uses three mutexes for thread-safety: a write lock, a read lock, and a metadata lock.

Direct Known Subclasses

RRCache

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_size = 100) ⇒ LRUCache

Returns a new instance of LRUCache.

Raises:



13
14
15
16
17
18
19
20
21
22
23
24
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 13

def initialize(max_size = 100)
  fail Exceptions::InvalidCacheSize unless max_size.is_a?(Integer)

  @max_size     = max_size
  @hits         = 0
  @misses       = 0
  @keys         = []
  @data         = {}
  @read_mutex   = Mutex.new
  @write_mutex  = Mutex.new
  @meta_mutex   = Mutex.new
end

Instance Attribute Details

#keys ⇒ Object (readonly)

Returns the value of attribute keys.



10
11
12
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 10

def keys
  @keys
end

#max_size ⇒ Object (readonly)

Returns the value of attribute max_size.



10
11
12
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 10

def max_size
  @max_size
end

Instance Method Details

#each(&block) ⇒ Object

Allow iterating over the cached items, represented as key+value pairs



55
56
57
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 55

def each(&block)
  to_hash.each(&block)
end

#flush ⇒ Boolean

Similar to #truncate (in fact, it calls it) but it also clears the statistical metadata.

Returns:

  • (Boolean) —

    was the flush operation successful?



84
85
86
87
88
89
90
91
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 84

def flush
  if truncate
    @meta_mutex.synchronize { @hits, @misses = 0, 0 }
    true
  else
    false
  end
end

#has?(key) ⇒ Boolean Also known as: has_key?, include?

Does the cache contain the requested item?

Parameters:

  • key (Symbol) —

    the index of the potentially cached object

Returns:

  • (Boolean) 


28
29
30
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 28

def has?(key)
  @meta_mutex.synchronize { @keys.include?(key) }
end

#invalidate(key) ⇒ Object Also known as: delete

Invalidate a cached item by its index / key. Returns ‘nil` if the object doesn’t exist.

Parameters:

  • key (Symbol) —

    the cached object’s index



62
63
64
65
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 62

def invalidate(key)
  invalidate_key(key)
  @write_mutex.synchronize { @data.delete(key) }
end

#marshal_dump ⇒ Object 



155
156
157
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 155

def marshal_dump
  [@max_size, @hits, @misses, @keys, @data]
end

#marshal_load(array) ⇒ Object 



159
160
161
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 159

def marshal_load(array)
  @max_size, @hits, @misses, @keys, @data = array
end

#retrieve(key) ⇒ Object Also known as: []

Retrieve an item from the cache. Returns ‘nil` if the item does not exist. Relies on #store returning the stored value to ensure the LRU algorithm is maintained safely.

Parameters:

  • key (Symbol) —

    the index to retrieve



142
143
144
145
146
147
148
149
150
151
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 142

def retrieve(key)
  if has?(key)
    @meta_mutex.synchronize { @hits += 1 }
    # Looks dumb, but it actually only reorganizes the keys Array
    store(key, @read_mutex.synchronize { @data[key] })
  else
    @meta_mutex.synchronize { @misses += 1 }
    nil
  end
end

#size ⇒ Fixnum

The number of items in the cache

Returns:

  • (Fixnum) —

    key count



37
38
39
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 37

def size
  @meta_mutex.synchronize { @keys.size }
end

#statistics ⇒ Hash

Provides a hash of the current metadata for the cache. It provides the current cache size (‘:size`),the number of cache hits (`:hits`), and the number of cache misses (`:misses`).

Returns:

  • (Hash) —

    cache statistics



97
98
99
100
101
102
103
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 97

def statistics
  {
    size: size,
    hits: @meta_mutex.synchronize { @hits },
    misses: @meta_mutex.synchronize { @misses }
  }
end

#store(key, value) ⇒ Object Also known as: []=

Store some data (‘value`) indexed by a `key`. If an object exists with the same key, and the value is different, it will be overwritten. Storing a value causes its key to be moved to the end of the keys array (meaning it is the __most recently used__ item), and this happens on #store regardless of whether or not the key previously existed. This behavior is relied upon by #retrieve to allow reorganization of the keys without necessarily modifying the data it indexes. Uses recursion for overwriting existing items.

Parameters:

  • key (Symbol) —

    the index to use for referencing this cached item

  • value (Object) —

    the data to cache



116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 116

def store(key, value)
  if has?(key)
    if @read_mutex.synchronize { @data[key] == value }
      invalidate_key(key)
      @meta_mutex.synchronize { @keys << key }
      value
    else
      invalidate(key)
      store(key, value)
    end
  else
    invalidate(@keys.first) until size < @max_size if size >= @max_size

    @write_mutex.synchronize do
      @meta_mutex.synchronize { @keys << key }
      @data[key] = value
    end
  end
end

#to_hash ⇒ Hash

Convert the contents of the cache to a Hash

Returns:

  • (Hash) —

    the cached data



43
44
45
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 43

def to_hash
  @read_mutex.synchronize { @data.dup }
end

#truncate ⇒ Boolean

Remove all items from the cache without clearing statistics

Returns:

  • (Boolean) —

    was the truncate operation successful?



71
72
73
74
75
76
77
78
79
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 71

def truncate
  @read_mutex.synchronize do
    @write_mutex.synchronize do
      @meta_mutex.synchronize { @keys   = [] }
      @data   = {}
    end
    @data.empty?
  end
end

#values ⇒ Array

Return a raw Array of the cache data without its keys. Not particularly useful but it may be useful in the future.

Returns:

  • (Array) —

    just the cached values



50
51
52
 
# File 'lib/rffdb/cache_providers/lru_cache.rb', line 50

def values
  @read_mutex.synchronize { @data.values }
end