Class: Heroic::LRUCache

Inherits:
Object
  • Object
show all
Defined in:
lib/heroic/lru_cache.rb

Overview

This LRU Cache is a generic key-value store that is designed to be safe for concurrent access. It uses a doubly-linked-list to identify which item was least recently retrieved, and a Hash for fast retrieval by key.

To support concurrent access, it uses two levels of locks: a cache-level lock is used to locate or create the desired node and move it to the front of the LRU list. A node-level lock is used to synchronize access to the node’s value.

If a thread is busy generating a value to be stored in the cache, other threads will still be able to read and write to other keys with no conflict. However, if a second thread tries to read the value that the first thread is generating, it will block until the first thread has completed its work.

Defined Under Namespace

Classes: Node

Instance Method Summary collapse

Constructor Details

#initialize(capacity, &block) ⇒ LRUCache

If you yield a block to the constructor, it will be called on every cache miss to generate the needed value. This is optional but recommended, as the block will run while holding a lock on the cache node associated with the key. Additional attempts to retrieve the same key will wait for your block to return a result, avoiding duplication of work. However, this also means you MUST NOT access the cache itself from the block, or you will risk creating deadlock. (If you need to create cacheable items from other cacheable items, consider using two separate caches.)

Raises:

  • (ArgumentError) 


28
29
30
31
32
33
34
35
36
 
# File 'lib/heroic/lru_cache.rb', line 28

def initialize(capacity, &block)
  raise ArgumentError unless capacity > 0
  @capacity = capacity
  @block = block || Proc.new { nil }
  @lock = Mutex.new
  @store = Hash.new
  @leftmost = nil
  @rightmost = nil
end

Instance Method Details

#get(key) ⇒ Object

Retrieve a value from the cache for a given key. If the value is in the cache, the method will return immediately. If the value is not in the cache and a block was provided to the constructor, it will be invoked to generate the value and insert it into the cache. If another thread is in the process of generating the same value, the current thread will wait for it to complete.

If the cache is full, this method may cause the least recently used item to be evicted from the cache.



48
49
50
51
 
# File 'lib/heroic/lru_cache.rb', line 48

def get(key)
  node = node_for_key(key)
  node.read(&@block)
end

#put(key, value) ⇒ Object

Inserts a value into the cache, assigning it to the given key. (Instead of directly inserting values into the cache, it is recommended that you supply a block to the constructor to generate values on demand.)



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

def put(key, value)
  node = node_for_key(key)
  node.write(value)
end

#verify! ⇒ Object

Verify the data structures used to maintain the cache. If a problem is detected, an exception is raised. This method is intended for testing and debugging only.



66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
 
# File 'lib/heroic/lru_cache.rb', line 66

def verify!
  @lock.synchronize do
    left_to_right = Array.new
    begin
      node = @leftmost
      while node
        left_to_right << node
        node = node.right
      end
    end
    right_to_left = Array.new
    begin
      node = @rightmost
      while node
        right_to_left << node
        node = node.left
      end
    end
    begin
      raise "leftmost has a left node" if @leftmost && @leftmost.left
      raise "rightmost has a right node" if @rightmost && @rightmost.right
      raise "leftmost pointer mismatch" unless @leftmost == left_to_right.first
      raise "rightmost pointer mismatch" unless @rightmost == right_to_left.first
      raise "list size mismatch" unless right_to_left.length == left_to_right.length
      raise "list order mismatch" unless left_to_right.reverse == right_to_left
      raise "node missing from list" if left_to_right.length < @store.size
      raise "node missing from store" if left_to_right.length > @store.size
      raise "store size exceeds capacity" if @store.size > @capacity
    rescue
      $stderr.puts "Store: #{@store}"
      $stderr.puts "L-to-R: #{left_to_right}"
      $stderr.puts "R-to-L: #{right_to_left}"
      raise
    end
  end
end