class Heroic::LRUCache

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.

Public Class Methods

new(capacity, &block) click to toggle source

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

# 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

Public Instance Methods

get(key) click to toggle source

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.

# File lib/heroic/lru_cache.rb, line 48
def get(key)
  node = node_for_key(key)
  node.read(&@block)
end
put(key, value) click to toggle source

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

# File lib/heroic/lru_cache.rb, line 57
def put(key, value)
  node = node_for_key(key)
  node.write(value)
end
verify!() click to toggle source

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.

# 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

Private Instance Methods

node_for_key(key) click to toggle source
# File lib/heroic/lru_cache.rb, line 123
def node_for_key(key)
  @lock.synchronize do
    node = @store[key]
    if node.nil?
      # I am a new node, add me to the head of the list!
      node = @store[key] = Node.new(key)
      if @leftmost
        node.right = @leftmost
        @leftmost.left = node
      end
      @leftmost = node
      @rightmost = @leftmost if @rightmost.nil?
      if @store.size > @capacity
        # Uh oh, time to evict the tail node!
        evicted_node = @store.delete(@rightmost.key)
        @rightmost = evicted_node.left
        @rightmost.right = nil
      end
    elsif node != @leftmost
      # Move me to the head of the list!
      if node == @rightmost
        # I was the rightmost node, now the node on my left is.
        @rightmost = node.left
        node.left.right = nil
      else
        # The node on my left should now point to the node on my right.
        node.left.right = node.right
        # The node on my right should point to the node on my left.
        node.right.left = node.left
      end
      former_leftmost = @leftmost
      # I am the new head node!
      @leftmost = node
      @leftmost.left = nil
      @leftmost.right = former_leftmost
      former_leftmost.left = @leftmost
    end
    node
  end
end