feat: add lru cache (optimizely#306)

andrewleap-optimizely · web-flow · commit 6c12bfd93a31 · 2022-08-09T15:07:27.000-04:00
* add lru cache
* add min ruby version to readme
diff --git a/README.md b/README.md
@@ -11,6 +11,9 @@ Optimizely Rollouts is free feature flags for development teams. Easily roll out
 
 ## Getting Started
 
+### Requirements
+* Ruby 2.7+
+
 ### Installing the SDK
 
 The SDK is available through [RubyGems](https://rubygems.org/gems/optimizely-sdk). To install:
diff --git a/lib/optimizely/odp/lru_cache.rb b/lib/optimizely/odp/lru_cache.rb
@@ -0,0 +1,114 @@
+# frozen_string_literal: true
+
+#
+#    Copyright 2022, Optimizely and contributors
+#
+#    Licensed under the Apache License, Version 2.0 (the "License");
+#    you may not use this file except in compliance with the License.
+#    You may obtain a copy of the License at
+#
+#        http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS,
+#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#    See the License for the specific language governing permissions and
+#    limitations under the License.
+#
+
+module Optimizely
+  class LRUCache
+    # Least Recently Used cache that invalidates entries older than the timeout.
+
+    attr_reader :capacity, :timeout
+
+    def initialize(capacity, timeout_in_secs)
+      # @param capacity - The max size of the cache. If set <= 0, caching is disabled.
+      # @param timeout_in_secs - Seconds until a cache item is considered stale.
+      #                          If set <= 0, items never expire.
+      @cache_mutex = Mutex.new
+      @map = {}
+      @capacity = capacity
+      @timeout = timeout_in_secs
+    end
+
+    # Retrieve the non stale value from the cache corresponding to the provided key
+    # or nil if key is not found
+    # Moves the key/value pair to the end of the cache
+    #
+    # @param key - The key to retrieve
+
+    def lookup(key)
+      return nil if @capacity <= 0
+
+      @cache_mutex.synchronize do
+        return nil unless @map.include?(key)
+
+        element = @map.delete(key)
+        return nil if element.stale?(@timeout)
+
+        @map[key] = element
+
+        element.value
+      end
+    end
+
+    # Save a key/value pair into the cache
+    # Moves the key/value pair to the end of the cache
+    #
+    # @param key - A user key
+    # @param value - A user value
+
+    def save(key, value)
+      return if @capacity <= 0
+
+      @cache_mutex.synchronize do
+        @map.delete(key) if @map.key?(key)
+
+        @map[key] = CacheElement.new(value)
+
+        @map.delete(@map.first[0]) if @map.size > @capacity
+        nil
+      end
+    end
+
+    # Clears the cache
+
+    def reset
+      return if @capacity <= 0
+
+      @cache_mutex.synchronize { @map.clear }
+      nil
+    end
+
+    # Retrieve a value from the cache for a given key or nil if key is not found
+    # Doesn't update the cache
+    #
+    # @param key - The key to retrieve
+
+    def peek(key)
+      return nil if @capacity <= 0
+
+      @cache_mutex.synchronize { @map[key]&.value }
+    end
+  end
+
+  class CacheElement
+    # Individual element for the LRUCache.
+    attr_reader :value, :timestamp
+
+    def initialize(value)
+      @value = value
+      @timestamp = Time.new
+    end
+
+    def stale?(timeout)
+      # Returns true if the provided timeout has passed since the element's timestamp.
+      #
+      # @param timeout - The duration to check against
+      return false if timeout <= 0
+
+      Time.new - @timestamp >= timeout
+    end
+  end
+end
diff --git a/spec/odp/lru_cache_spec.rb b/spec/odp/lru_cache_spec.rb
@@ -0,0 +1,152 @@
+# frozen_string_literal: true
+
+#
+#    Copyright 2022, Optimizely and contributors
+#
+#    Licensed under the Apache License, Version 2.0 (the "License");
+#    you may not use this file except in compliance with the License.
+#    You may obtain a copy of the License at
+#
+#        http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS,
+#    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+#    See the License for the specific language governing permissions and
+#    limitations under the License.
+#
+require 'optimizely/odp/lru_cache'
+
+describe Optimizely::LRUCache do
+  it 'should create a cache with min config' do
+    cache = Optimizely::LRUCache.new(1000, 2000)
+    expect(cache.capacity).to eq 1000
+    expect(cache.timeout).to eq 2000
+
+    cache = Optimizely::LRUCache.new(0, 0)
+    expect(cache.capacity).to eq 0
+    expect(cache.timeout).to eq 0
+  end
+
+  it 'should save and lookup correctly' do
+    max_size = 2
+    cache = Optimizely::LRUCache.new(max_size, 1000)
+
+    expect(cache.peek(1)).to be_nil
+    cache.save(1, 100)                       # [1]
+    cache.save(2, 200)                       # [1, 2]
+    cache.save(3, 300)                       # [2, 3]
+    expect(cache.peek(1)).to be_nil
+    expect(cache.peek(2)).to be 200
+    expect(cache.peek(3)).to be 300
+
+    cache.save(2, 201)                       # [3, 2]
+    cache.save(1, 101)                       # [2, 1]
+    expect(cache.peek(1)).to eq 101
+    expect(cache.peek(2)).to eq 201
+    expect(cache.peek(3)).to be_nil
+
+    expect(cache.lookup(3)).to be_nil        # [2, 1]
+    expect(cache.lookup(2)).to eq 201        # [1, 2]
+    cache.save(3, 302)                       # [2, 3]
+    expect(cache.peek(1)).to be_nil
+    expect(cache.peek(2)).to eq 201
+    expect(cache.peek(3)).to eq 302
+
+    expect(cache.lookup(3)).to eq 302        # [2, 3]
+    cache.save(1, 103)                       # [3, 1]
+    expect(cache.peek(1)).to eq 103
+    expect(cache.peek(2)).to be_nil
+    expect(cache.peek(3)).to eq 302
+
+    expect(cache.instance_variable_get('@map').size).to be max_size
+    expect(cache.instance_variable_get('@map').size).to be cache.capacity
+  end
+
+  it 'should disable cache with size zero' do
+    cache = Optimizely::LRUCache.new(0, 1000)
+
+    expect(cache.lookup(1)).to be_nil
+    cache.save(1, 100)                       # [1]
+    expect(cache.lookup(1)).to be_nil
+  end
+
+  it 'should disable with cache size less than zero' do
+    cache = Optimizely::LRUCache.new(-2, 1000)
+
+    expect(cache.lookup(1)).to be_nil
+    cache.save(1, 100)                       # [1]
+    expect(cache.lookup(1)).to be_nil
+  end
+
+  it 'should make elements stale after timeout' do
+    max_timeout = 0.5
+
+    cache = Optimizely::LRUCache.new(1000, max_timeout)
+
+    cache.save(1, 100)                       # [1]
+    cache.save(2, 200)                       # [1, 2]
+    cache.save(3, 300)                       # [1, 2, 3]
+    sleep(1.1) # wait to expire
+    cache.save(4, 400)                       # [1, 2, 3, 4]
+    cache.save(1, 101)                       # [2, 3, 4, 1]
+
+    expect(cache.lookup(1)).to eq 101        # [4, 1]
+    expect(cache.lookup(2)).to be_nil
+    expect(cache.lookup(3)).to be_nil
+    expect(cache.lookup(4)).to eq 400
+  end
+
+  it 'should make element stale after timeout even with lookup' do
+    max_timeout = 1
+
+    cache = Optimizely::LRUCache.new(1000, max_timeout)
+
+    cache.save(1, 100)
+    sleep(0.5)
+    cache.lookup(1)
+    sleep(0.5)
+    expect(cache.lookup(1)).to be_nil
+  end
+
+  it 'should not make elements stale when timeout is zero' do
+    max_timeout = 0
+    cache = Optimizely::LRUCache.new(1000, max_timeout)
+
+    cache.save(1, 100)                       # [1]
+    cache.save(2, 200)                       # [1, 2]
+    sleep(1) # wait to expire
+
+    expect(cache.lookup(1)).to eq 100
+    expect(cache.lookup(2)).to eq 200
+  end
+
+  it 'should not expire when timeout is less than zero' do
+    max_timeout = -2
+    cache = Optimizely::LRUCache.new(1000, max_timeout)
+
+    cache.save(1, 100)                       # [1]
+    cache.save(2, 200)                       # [1, 2]
+    sleep(1) # wait to expire
+
+    expect(cache.lookup(1)).to eq 100
+    expect(cache.lookup(2)).to eq 200
+  end
+
+  it 'should clear cache when reset is called' do
+    cache = Optimizely::LRUCache.new(1000, 600)
+    cache.save('wow', 'great')
+    cache.save('tow', 'freight')
+
+    expect(cache.lookup('wow')).to eq 'great'
+    expect(cache.instance_variable_get('@map').size).to eq 2
+
+    cache.reset
+
+    expect(cache.lookup('wow')).to be_nil
+    expect(cache.instance_variable_get('@map').size).to eq 0
+
+    cache.save('cow', 'crate')
+    expect(cache.lookup('cow')).to eq 'crate'
+  end
+end
