Use recyclable cache keys (#29092)

4 files changed, 164 insertions, 18 deletions

diff --git a/activesupport/CHANGELOG.md b/activesupport/CHANGELOG.md
index 3ce4a0bbab..49ff2c88d0 100644
--- a/activesupport/CHANGELOG.md
+++ b/activesupport/CHANGELOG.md
@@ -1,3 +1,9 @@
+*   Add support for versioned cache entries. This enables the cache stores to recycle cache keys, greatly saving
+    on storage in cases with frequent churn. Works together with the separation of #cache_key and #cache_version
+    in Active Record and its use in Action Pack's fragment caching.
+
+    *DHH*
+
 *   Pass gem name and deprecation horizon to deprecation notifications.
 
     *Willem van Bergen*
diff --git a/activesupport/lib/active_support/cache.rb b/activesupport/lib/active_support/cache.rb
index 4d8c2046e8..258140fe1d 100644
--- a/activesupport/lib/active_support/cache.rb
+++ b/activesupport/lib/active_support/cache.rb
@@ -219,6 +219,10 @@ module ActiveSupport
       #   cache = ActiveSupport::Cache::MemoryStore.new(expires_in: 5.minutes)
       #   cache.write(key, value, expires_in: 1.minute) # Set a lower value for one entry
       #
+      # Setting <tt>:version</tt> verifies the cache stored under <tt>name</tt>
+      # is of the same version. nil is returned on mismatches despite contents.
+      # This feature is used to support recyclable cache keys.
+      #
       # Setting <tt>:race_condition_ttl</tt> is very useful in situations where
       # a cache entry is used very frequently and is under heavy load. If a
       # cache expires and due to heavy load several different processes will try
@@ -287,6 +291,7 @@ module ActiveSupport
           instrument(:read, name, options) do |payload|
             cached_entry = read_entry(key, options) unless options[:force]
             entry = handle_expired_entry(cached_entry, key, options)
+            entry = nil if entry && entry.mismatched?(normalize_version(name, options))
             payload[:super_operation] = :fetch if payload
             payload[:hit] = !!entry if payload
           end
@@ -303,21 +308,34 @@ module ActiveSupport
         end
       end
 
-      # Fetches data from the cache, using the given key. If there is data in
+      # Reads data from the cache, using the given key. If there is data in
       # the cache with the given key, then that data is returned. Otherwise,
       # +nil+ is returned.
       #
+      # Note, if data was written with the <tt>:expires_in<tt> or <tt>:version</tt> options,
+      # both of these conditions are applied before the data is returned.
+      #
       # Options are passed to the underlying cache implementation.
       def read(name, options = nil)
         options = merged_options(options)
-        key = normalize_key(name, options)
+        key     = normalize_key(name, options)
+        version = normalize_version(name, options)
+
         instrument(:read, name, options) do |payload|
           entry = read_entry(key, options)
+
           if entry
             if entry.expired?
               delete_entry(key, options)
               payload[:hit] = false if payload
               nil
+            elsif entry.mismatched?(version)
+              if payload
+                payload[:hit]      = false
+                payload[:mismatch] = "#{entry.version} != #{version}"
+              end
+
+              nil
             else
               payload[:hit] = true if payload
               entry.value
@@ -341,11 +359,15 @@ module ActiveSupport
 
         results = {}
         names.each do |name|
-          key = normalize_key(name, options)
-          entry = read_entry(key, options)
+          key     = normalize_key(name, options)
+          version = normalize_version(name, options)
+          entry   = read_entry(key, options)
+
           if entry
             if entry.expired?
               delete_entry(key, options)
+            elsif entry.mismatched?(version)
+              # Skip mismatched versions
             else
               results[name] = entry.value
             end
@@ -396,7 +418,7 @@ module ActiveSupport
         options = merged_options(options)
 
         instrument(:write, name, options) do
-          entry = Entry.new(value, options)
+          entry = Entry.new(value, options.merge(version: normalize_version(name, options)))
           write_entry(normalize_key(name, options), entry, options)
         end
       end
@@ -420,7 +442,7 @@ module ActiveSupport
 
         instrument(:exist?, name) do
           entry = read_entry(normalize_key(name, options), options)
-          (entry && !entry.expired?) || false
+          (entry && !entry.expired? && !entry.mismatched?(normalize_version(name, options))) || false
         end
       end
 
@@ -517,6 +539,17 @@ module ActiveSupport
           end
         end
 
+
+        # Prefixes a key with the namespace. Namespace and key will be delimited
+        # with a colon.
+        def normalize_key(key, options)
+          key = expanded_key(key)
+          namespace = options[:namespace] if options
+          prefix = namespace.is_a?(Proc) ? namespace.call : namespace
+          key = "#{prefix}:#{key}" if prefix
+          key
+        end
+
         # Expands key to be a consistent string value. Invokes +cache_key+ if
         # object responds to +cache_key+. Otherwise, +to_param+ method will be
         # called. If the key is a Hash, then keys will be sorted alphabetically.
@@ -537,14 +570,16 @@ module ActiveSupport
           key.to_param
         end
 
-        # Prefixes a key with the namespace. Namespace and key will be delimited
-        # with a colon.
-        def normalize_key(key, options)
-          key = expanded_key(key)
-          namespace = options[:namespace] if options
-          prefix = namespace.is_a?(Proc) ? namespace.call : namespace
-          key = "#{prefix}:#{key}" if prefix
-          key
+        def normalize_version(key, options = nil)
+          (options && options[:version].try(:to_param)) || expanded_version(key)
+        end
+
+        def expanded_version(key)
+          case
+          when key.respond_to?(:cache_version) then key.cache_version.to_param
+          when key.is_a?(Array)                then key.map { |element| expanded_version(element) }.compact.to_param
+          when key.respond_to?(:to_a)          then expanded_version(key.to_a)
+          end
         end
 
         def instrument(operation, key, options = nil)
@@ -555,6 +590,7 @@ module ActiveSupport
           ActiveSupport::Notifications.instrument("cache_#{operation}.active_support", payload) { yield(payload) }
         end
 
+
         def log
           return unless logger && logger.debug? && !silence?
           logger.debug(yield)
@@ -591,13 +627,16 @@ module ActiveSupport
         end
     end
 
-    # This class is used to represent cache entries. Cache entries have a value and an optional
-    # expiration time. The expiration time is used to support the :race_condition_ttl option
-    # on the cache.
+    # This class is used to represent cache entries. Cache entries have a value, an optional
+    # expiration time, and an optional version. The expiration time is used to support the :race_condition_ttl option
+    # on the cache. The version is used to support the :version option on the cache for rejecting
+    # mismatches.
     #
     # Since cache entries in most instances will be serialized, the internals of this class are highly optimized
     # using short instance variable names that are lazily defined.
     class Entry # :nodoc:
+      attr_reader :version
+
       DEFAULT_COMPRESS_LIMIT = 16.kilobytes
 
       # Creates a new cache entry for the specified value. Options supported are
@@ -610,6 +649,7 @@ module ActiveSupport
           @value = value
         end
 
+        @version    = options[:version]
         @created_at = Time.now.to_f
         @expires_in = options[:expires_in]
         @expires_in = @expires_in.to_f if @expires_in
@@ -619,6 +659,10 @@ module ActiveSupport
         compressed? ? uncompress(@value) : @value
       end
 
+      def mismatched?(version)
+        @version && version && @version != version
+      end
+
       # Checks if the entry is expired. The +expires_in+ parameter can override
       # the value set when the entry was created.
       def expired?
diff --git a/activesupport/lib/active_support/cache/mem_cache_store.rb b/activesupport/lib/active_support/cache/mem_cache_store.rb
index e09cee3335..06fa9f67ad 100644
--- a/activesupport/lib/active_support/cache/mem_cache_store.rb
+++ b/activesupport/lib/active_support/cache/mem_cache_store.rb
@@ -97,12 +97,18 @@ module ActiveSupport
         options = merged_options(options)
 
         keys_to_names = Hash[names.map { |name| [normalize_key(name, options), name] }]
+
         raw_values = @data.get_multi(keys_to_names.keys)
         values = {}
+
         raw_values.each do |key, value|
           entry = deserialize_entry(value)
-          values[keys_to_names[key]] = entry.value unless entry.expired?
+
+          unless entry.expired? || entry.mismatched?(normalize_version(keys_to_names[key], options))
+            values[keys_to_names[key]] = entry.value
+          end
         end
+
         values
       end
 
diff --git a/activesupport/test/caching_test.rb b/activesupport/test/caching_test.rb
index dbec684ce0..f53b98c73e 100644
--- a/activesupport/test/caching_test.rb
+++ b/activesupport/test/caching_test.rb
@@ -579,6 +579,93 @@ module CacheStoreBehavior
   end
 end
 
+module CacheStoreVersionBehavior
+  ModelWithKeyAndVersion = Struct.new(:cache_key, :cache_version)
+
+  def test_fetch_with_right_version_should_hit
+    @cache.fetch("foo", version: 1) { "bar" }
+    assert_equal "bar", @cache.read("foo", version: 1)
+  end
+
+  def test_fetch_with_wrong_version_should_miss
+    @cache.fetch("foo", version: 1) { "bar" }
+    assert_nil @cache.read("foo", version: 2)
+  end
+
+  def test_read_with_right_version_should_hit
+    @cache.write("foo", "bar", version: 1)
+    assert_equal "bar", @cache.read("foo", version: 1)
+  end
+
+  def test_read_with_wrong_version_should_miss
+    @cache.write("foo", "bar", version: 1)
+    assert_nil @cache.read("foo", version: 2)
+  end
+
+  def test_exist_with_right_version_should_be_true
+    @cache.write("foo", "bar", version: 1)
+    assert @cache.exist?("foo", version: 1)
+  end
+
+  def test_exist_with_wrong_version_should_be_false
+    @cache.write("foo", "bar", version: 1)
+    assert !@cache.exist?("foo", version: 2)
+  end
+
+  def test_reading_and_writing_with_model_supporting_cache_version
+    m1v1 = ModelWithKeyAndVersion.new("model/1", 1)
+    m1v2 = ModelWithKeyAndVersion.new("model/1", 2)
+
+    @cache.write(m1v1, "bar")
+    assert_equal "bar", @cache.read(m1v1)
+    assert_nil @cache.read(m1v2)
+  end
+
+  def test_reading_and_writing_with_model_supporting_cache_version_using_nested_key
+    m1v1 = ModelWithKeyAndVersion.new("model/1", 1)
+    m1v2 = ModelWithKeyAndVersion.new("model/1", 2)
+
+    @cache.write([ "something", m1v1 ], "bar")
+    assert_equal "bar", @cache.read([ "something", m1v1 ])
+    assert_nil @cache.read([ "something", m1v2 ])
+  end
+
+  def test_fetching_with_model_supporting_cache_version
+    m1v1 = ModelWithKeyAndVersion.new("model/1", 1)
+    m1v2 = ModelWithKeyAndVersion.new("model/1", 2)
+
+    @cache.fetch(m1v1) { "bar" }
+    assert_equal "bar", @cache.fetch(m1v1) { "bu" }
+    assert_equal "bu", @cache.fetch(m1v2) { "bu" }
+  end
+
+  def test_exist_with_model_supporting_cache_version
+    m1v1 = ModelWithKeyAndVersion.new("model/1", 1)
+    m1v2 = ModelWithKeyAndVersion.new("model/1", 2)
+
+    @cache.write(m1v1, "bar")
+    assert     @cache.exist?(m1v1)
+    assert_not @cache.fetch(m1v2)
+  end
+
+  def test_fetch_multi_with_model_supporting_cache_version
+    m1v1 = ModelWithKeyAndVersion.new("model/1", 1)
+    m2v1 = ModelWithKeyAndVersion.new("model/2", 1)
+    m2v2 = ModelWithKeyAndVersion.new("model/2", 2)
+
+    first_fetch_values  = @cache.fetch_multi(m1v1, m2v1) { |m| m.cache_key }
+    second_fetch_values = @cache.fetch_multi(m1v1, m2v2) { |m| m.cache_key + " 2nd" }
+
+    assert_equal({ m1v1 => "model/1", m2v1 => "model/2" }, first_fetch_values)
+    assert_equal({ m1v1 => "model/1", m2v2 => "model/2 2nd" }, second_fetch_values)
+  end
+
+  def test_version_is_normalized
+    @cache.write("foo", "bar", version: 1)
+    assert_equal "bar", @cache.read("foo", version: "1")
+  end
+end
+
 # https://rails.lighthouseapp.com/projects/8994/tickets/6225-memcachestore-cant-deal-with-umlauts-and-special-characters
 # The error is caused by character encodings that can't be compared with ASCII-8BIT regular expressions and by special
 # characters like the umlaut in UTF-8.
@@ -822,6 +909,7 @@ class FileStoreTest < ActiveSupport::TestCase
   end
 
   include CacheStoreBehavior
+  include CacheStoreVersionBehavior
   include LocalCacheBehavior
   include CacheDeleteMatchedBehavior
   include CacheIncrementDecrementBehavior
@@ -931,6 +1019,7 @@ class MemoryStoreTest < ActiveSupport::TestCase
   end
 
   include CacheStoreBehavior
+  include CacheStoreVersionBehavior
   include CacheDeleteMatchedBehavior
   include CacheIncrementDecrementBehavior
 
@@ -1052,6 +1141,7 @@ class MemCacheStoreTest < ActiveSupport::TestCase
   end
 
   include CacheStoreBehavior
+  include CacheStoreVersionBehavior
   include LocalCacheBehavior
   include CacheIncrementDecrementBehavior
   include EncodedKeyCacheBehavior