Skip to content

SamSaffron/lru_redux

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

56 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

LruRedux Gem Version

An efficient, thread safe LRU cache.

Installation

Add this line to your application's Gemfile:

gem 'lru_redux'

And then execute:

$ bundle

Or install it yourself as:

$ gem install lru_redux

Ruby 1.8 - v0.8.4 is the last compatible release:

gem 'lru_redux', '~> 0.8.4'

Usage

require 'lru_redux'

# non thread safe
cache = LruRedux::Cache.new(100)
cache[:a] = "1"
cache[:b] = "2"

cache.to_a
# [[:b,"2"],[:a,"1"]]
# note the order matters here, last accessed is first

cache[:a] # a pushed to front
# "1"

cache.to_a
# [[:a,"1"],[:b,"2"]]
cache.delete(:a)
cache.each {|k,v| p "#{k} #{v}"}
# b 2

cache.max_size = 200 # cache now stores 200 items
cache.clear # cache has no items

cache.getset(:a){1}
cache.to_a
#[[:a,1]]

# already set so don't call block
cache.getset(:a){99}
cache.to_a
#[[:a,1]]

# for thread safe access, all methods on cache
# are protected with a mutex
cache = LruRedux::ThreadSafeCache.new(100)

TTL Cache

The TTL cache extends the functionality of the LRU cache with a Time To Live eviction strategy. TTL eviction occurs on every access and takes precedence over LRU eviction, meaning a 'live' value will never be evicted over an expired one.

# Timecop is gem that allows us to change Time.now
# and is used for demonstration purposes.
require 'lru_redux'
require 'timecop'

# Create a TTL cache with a size of 100 and TTL of 5 minutes.
# The first argument is the size and
# the second optional argument is the TTL in seconds.
cache = LruRedux::TTL::Cache.new(100, 5 * 60)

Timecop.freeze(Time.now)

cache[:a] = "1"
cache[:b] = "2"

cache.to_a
# => [[:b,"2"],[:a,"1"]]

# Now we advance time 5 min 30 sec into the future.
Timecop.freeze(Time.now + 330)

# And we see that the expired values have been evicted.
cache.to_a
# => []

# The TTL can be updated on a live cache using #ttl=.
# Currently cached items will be evicted under the new TTL.
cache[:a] = "1"
cache[:b] = "2"

Timecop.freeze(Time.now + 330)

cache.ttl = 10 * 60

# Since ttl eviction is triggered by access,
# the items are still cached when the ttl is changed and
# are now under the 10 minute TTL.
cache.to_a
# => [[:b,"2"],[:a,"1"]]

# TTL eviction can be triggered manually with the #expire method.
Timecop.freeze(Time.now + 330)

cache.expire
cache.to_a
# => []

Timecop.return

# The behavior of a TTL cache with the TTL set to `:none`
# is identical to the LRU cache.

cache = LruRedux::TTL::Cache.new(100, :none)

# The TTL argument is optional and defaults to `:none`.
cache = LruRedux::TTL::Cache.new(100)

# A thread safe version is available.
cache = LruRedux::TTL::ThreadSafeCache.new(100, 5 * 60)

Cache Methods

  • #getset Takes a key and block. Will return a value if cached, otherwise will execute the block and cache the resulting value.
  • #fetch Takes a key and optional block. Will return a value if cached, otherwise will execute the block and return the resulting value or return nil if no block is provided.
  • #[] Takes a key. Will return a value if cached, otherwise nil.
  • #[]= Takes a key and value. Will cache the value under the key.
  • #delete Takes a key. Will return the deleted value, otherwise nil.
  • #evict Alias for #delete.
  • #clear Clears the cache. Returns nil.
  • #each Takes a block. Executes the block on each key-value pair in LRU order (most recent first).
  • #to_a Return an array of key-value pairs (arrays) in LRU order (most recent first).
  • #key? Takes a key. Returns true if the key is cached, otherwise false.
  • #has_key? Alias for #key?.
  • #count Return the current number of items stored in the cache.
  • #max_size Returns the current maximum size of the cache.
  • #max_size= Takes a positive number. Changes the current max_size and triggers a resize. Also triggers TTL eviction on the TTL cache.

TTL Cache Specific

  • #ttl Returns the current TTL of the cache.
  • #ttl= Takes :none or a positive number. Changes the current ttl and triggers a TTL eviction.
  • #expire Triggers a TTL eviction.

Benchmarks

see: benchmark directory (a million random lookup / store)

LRU

Ruby 2.2.1
$ ruby ./bench/bench.rb

Rehearsal -------------------------------------------------------------
ThreadSafeLru               4.500000   0.030000   4.530000 (  4.524213)
LRU                         2.250000   0.000000   2.250000 (  2.249670)
LRUCache                    1.720000   0.010000   1.730000 (  1.728243)
LruRedux::Cache             0.960000   0.000000   0.960000 (  0.961292)
LruRedux::ThreadSafeCache   2.180000   0.000000   2.180000 (  2.187714)
--------------------------------------------------- total: 11.650000sec

                                user     system      total        real
ThreadSafeLru               4.390000   0.020000   4.410000 (  4.415703)
LRU                         2.140000   0.010000   2.150000 (  2.149626)
LRUCache                    1.680000   0.010000   1.690000 (  1.688564)
LruRedux::Cache             0.910000   0.000000   0.910000 (  0.913108)
LruRedux::ThreadSafeCache   2.200000   0.010000   2.210000 (  2.212108)
Ruby 2.0.0-p643

Implementation is slightly different for Ruby versions before 2.1 due to a Ruby bug. http://bugs.ruby-lang.org/issues/8312

$ ruby ./bench/bench.rb
Rehearsal -------------------------------------------------------------
ThreadSafeLru               4.790000   0.040000   4.830000 (  4.828370)
LRU                         2.170000   0.010000   2.180000 (  2.180630)
LRUCache                    1.810000   0.000000   1.810000 (  1.814737)
LruRedux::Cache             1.330000   0.010000   1.340000 (  1.325554)
LruRedux::ThreadSafeCache   2.770000   0.000000   2.770000 (  2.777754)
--------------------------------------------------- total: 12.930000sec

                                user     system      total        real
ThreadSafeLru               4.710000   0.060000   4.770000 (  4.773233)
LRU                         2.120000   0.010000   2.130000 (  2.135111)
LRUCache                    1.780000   0.000000   1.780000 (  1.781392)
LruRedux::Cache             1.190000   0.010000   1.200000 (  1.201908)
LruRedux::ThreadSafeCache   2.650000   0.010000   2.660000 (  2.652580)

TTL

Ruby 2.2.1
$ ruby ./bench/bench_ttl.rb
Rehearsal -----------------------------------------------------------------------
FastCache                             6.240000   0.070000   6.310000 (  6.302569)
LruRedux::TTL::Cache                  4.700000   0.010000   4.710000 (  4.712858)
LruRedux::TTL::ThreadSafeCache        6.300000   0.010000   6.310000 (  6.319032)
LruRedux::TTL::Cache (TTL disabled)   2.460000   0.010000   2.470000 (  2.470629)
------------------------------------------------------------- total: 19.800000sec

                                          user     system      total        real
FastCache                             6.470000   0.070000   6.540000 (  6.536193)
LruRedux::TTL::Cache                  4.640000   0.010000   4.650000 (  4.661793)
LruRedux::TTL::ThreadSafeCache        6.310000   0.020000   6.330000 (  6.328840)
LruRedux::TTL::Cache (TTL disabled)   2.440000   0.000000   2.440000 (  2.446269)

Other Caches

This is a list of the caches that are used in the benchmarks.

LRU

LRUCache

ThreadSafeLru

FastCache

Contributing

  1. Fork it
  2. Create your feature branch (git checkout -b my-new-feature)
  3. Commit your changes (git commit -am 'Add some feature')
  4. Push to the branch (git push origin my-new-feature)
  5. Create new Pull Request

Changelog

version 1.1.0 - 30-Mar-2015

  • New: TTL cache added. This cache is LRU like with the addition of time-based eviction. Check the Usage -> TTL Cache section in README.md for details.

version 1.0.0 - 26-Mar-2015

  • Ruby Support: Ruby 1.9+ is now required by LruRedux. If you need to use LruRedux in Ruby 1.8, please specify gem version 0.8.4 in your Gemfile. v0.8.4 is the last 1.8 compatible release and included a number of fixes and performance improvements for the Ruby 1.8 implementation. @Seberius
  • Perf: improve performance in Ruby 2.1+ on the MRI @Seberius

version 0.8.4 - 20-Feb-2015

  • Fix: regression of ThreadSafeCache under JRuby 1.7 @Seberius

version 0.8.3 - 20-Feb-2015

  • Perf: improve ThreadSafeCache performance @Seberius

version 0.8.2 - 16-Feb-2015

  • Perf: use #size instead of #count when checking length @Seberius
  • Fix: Cache could grow beyond its size in Ruby 1.8 @Seberius
  • Fix: #each could deadlock in Ruby 1.8 @Seberius

version 0.8.1 - 7-Sep-2013

  • Fix #each implementation
  • Fix deadlocks with ThreadSafeCache
  • Version jump is because its been used in production for quite a while now

version 0.0.6 - 24-April-2013

  • Fix bug in getset, overflow was not returning the yeilded val

version 0.0.5 - 23-April-2013

  • Added getset and fetch
  • Optimised implementation so it 20-30% faster on Ruby 1.9+

version 0.0.4 - 23-April-2013

  • Initial version

About

An efficient optionally thread safe LRU Cache

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Languages