Class: SkullIsland::LRUCache

Inherits:
Object
  • Object
show all
Defined in:
lib/skull_island/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.

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(max_size = 100) ⇒ LRUCache

Returns a new instance of LRUCache.

Raises:



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

def initialize(max_size = 100)
  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

Instance Attribute Details

#keys ⇒ Object (readonly)

Returns the value of attribute keys.



11
12
13
 
# File 'lib/skull_island/lru_cache.rb', line 11

def keys
  @keys
end

#max_size ⇒ Object (readonly)

Returns the value of attribute max_size.



11
12
13
 
# File 'lib/skull_island/lru_cache.rb', line 11

def max_size
  @max_size
end

Instance Method Details

#each(&block) ⇒ Object

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



57
58
59
 
# File 'lib/skull_island/lru_cache.rb', line 57

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?



86
87
88
89
90
91
92
93
94
95
96
 
# 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

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

Does the cache contain the requested item? This doesn’t count against cache misses

Parameters:

  • key (Symbol) —

    the index of the potentially cached object

Returns:

  • (Boolean) 


30
31
32
 
# File 'lib/skull_island/lru_cache.rb', line 30

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



64
65
66
67
 
# File 'lib/skull_island/lru_cache.rb', line 64

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

#marshal_dump ⇒ Object 



160
161
162
 
# File 'lib/skull_island/lru_cache.rb', line 160

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

#marshal_load(array) ⇒ Object 



164
165
166
 
# File 'lib/skull_island/lru_cache.rb', line 164

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



147
148
149
150
151
152
153
154
155
156
 
# 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

#size ⇒ Fixnum

The number of items in the cache

Returns:

  • (Fixnum) —

    key count



39
40
41
 
# File 'lib/skull_island/lru_cache.rb', line 39

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



102
103
104
105
106
107
108
 
# 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(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



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# 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

#to_hash ⇒ Hash

Convert the contents of the cache to a Hash

Returns:

  • (Hash) —

    the cached data



45
46
47
 
# File 'lib/skull_island/lru_cache.rb', line 45

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?



73
74
75
76
77
78
79
80
81
 
# 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

#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



52
53
54
 
# File 'lib/skull_island/lru_cache.rb', line 52

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