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 = 10_000) ⇒ 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 = 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

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.



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



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.



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.



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



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`).



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.



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



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



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.



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

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