class SkullIsland::LRUCache
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.
Attributes
Public Class Methods
@raise [Exceptions::InvalidCacheSize] if the max_size
isn't an Integer
# File lib/skull_island/lru_cache.rb, line 14 def initialize(max_size = 10_000) raise 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
Public Instance Methods
Allow iterating over the cached items, represented as key+value pairs
# File lib/skull_island/lru_cache.rb, line 57 def each(&block) to_hash.each(&block) end
Similar to {#truncate} (in fact, it calls it) but it also clears the statistical metadata. @return [Boolean] was the flush operation successful?
# File lib/skull_island/lru_cache.rb, line 86 def flush if truncate @meta_mutex.synchronize do @hits = 0 @misses = 0 end true else false end end
Does the cache contain the requested item? This doesn't count against cache misses @param key [Symbol] the index of the potentially cached object
# File lib/skull_island/lru_cache.rb, line 30 def has?(key) @meta_mutex.synchronize { @keys.include?(key) } end
Invalidate a cached item by its index / key. Returns `nil` if the object doesn't exist. @param key [Symbol] the cached object's index
# File lib/skull_island/lru_cache.rb, line 64 def invalidate(key) invalidate_key(key) @write_mutex.synchronize { @data.delete(key) } end
# File lib/skull_island/lru_cache.rb, line 160 def marshal_dump [@max_size, @hits, @misses, @keys, @data] end
# File lib/skull_island/lru_cache.rb, line 164 def marshal_load(array) @max_size, @hits, @misses, @keys, @data = array end
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. @param key [Symbol] the index to retrieve
# File lib/skull_island/lru_cache.rb, line 147 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
The number of items in the cache @return [Fixnum] key count
# File lib/skull_island/lru_cache.rb, line 39 def size @meta_mutex.synchronize { @keys.size } end
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`). @return [Hash] cache statistics
# File lib/skull_island/lru_cache.rb, line 102 def statistics { size: size, hits: @meta_mutex.synchronize { @hits }, misses: @meta_mutex.synchronize { @misses } } end
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.
@param key [Symbol] the index to use for referencing this cached item @param value [Object] the data to cache
# File lib/skull_island/lru_cache.rb, line 121 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 @write_mutex.synchronize do @meta_mutex.synchronize { @keys << key } @data[key] = value end end end
Convert the contents of the cache to a Hash @return [Hash] the cached data
# File lib/skull_island/lru_cache.rb, line 45 def to_hash @read_mutex.synchronize { @data.dup } end
Remove all items from the cache without clearing statistics @return [Boolean] was the truncate operation successful?
# File lib/skull_island/lru_cache.rb, line 73 def truncate @read_mutex.synchronize do @write_mutex.synchronize do @meta_mutex.synchronize { @keys = [] } @data = {} end @data.empty? end end
Return a raw Array of the cache data without its keys. Not particularly useful but it may be useful in the future. @return [Array] just the cached values
# File lib/skull_island/lru_cache.rb, line 52 def values @read_mutex.synchronize { @data.values } end
Private Instance Methods
Invalidate just the key of a cached item. Dangerous if used incorrectly.
# File lib/skull_island/lru_cache.rb, line 171 def invalidate_key(key) @meta_mutex.synchronize { @keys.delete(key) } end