[Fixes #11512] improves cache size calculation in ActiveSupport::Cache::MemoryStore

Previously, the cache size of `ActiveSupport::Cache::MemoryStore` was calculated
as the sum of the size of its entries, ignoring the size of keys and any data
structure overhead. This could lead to the calculated cache size sometimes being
10-100x smaller than the memory used, e.g., in the case of small values.

The size of a key/entry pair is now calculated via `#cached_size`:

    def cached_size(key, entry)
      key.to_s.bytesize + entry.size + PER_ENTRY_OVERHEAD
    end

The value of `PER_ENTRY_OVERHEAD` is 240 bytes based on an [empirical
estimation](https://gist.github.com/ssimeonov/6047200) for 64-bit MRI on
1.9.3 and 2.0.

Fixes GH#11512 https://github.com/rails/rails/issues/11512

3 files changed, 53 insertions, 5 deletions

diff --git a/activesupport/CHANGELOG.md b/activesupport/CHANGELOG.md
index c00cbaaa08..918a43bf36 100644
--- a/activesupport/CHANGELOG.md
+++ b/activesupport/CHANGELOG.md
@@ -143,4 +143,17 @@
 
     *Daniel Schierbeck*
 
+*   Improve `ActiveSupport::Cache::MemoryStore` cache size calculation.
+    The memory used by a key/entry pair is calculated via `#cached_size`:
+
+        def cached_size(key, entry)
+          key.to_s.bytesize + entry.size + PER_ENTRY_OVERHEAD
+        end
+
+    The value of `PER_ENTRY_OVERHEAD` is 240 bytes based on an [empirical
+    estimation](https://gist.github.com/ssimeonov/6047200) for 64-bit MRI on 
+    1.9.3 and 2.0. GH#11512
+
+    *Simeon Simeonov*
+
 Please check [4-0-stable](https://github.com/rails/rails/blob/4-0-stable/activesupport/CHANGELOG.md) for previous changes.
diff --git a/activesupport/lib/active_support/cache/memory_store.rb b/activesupport/lib/active_support/cache/memory_store.rb
index 4d26fb7e42..b0aae54aa4 100644
--- a/activesupport/lib/active_support/cache/memory_store.rb
+++ b/activesupport/lib/active_support/cache/memory_store.rb
@@ -122,6 +122,14 @@ module ActiveSupport
       end
 
       protected
+
+        # See https://gist.github.com/ssimeonov/6047200
+        PER_ENTRY_OVERHEAD = 240
+
+        def cached_size(key, entry)
+          key.to_s.bytesize + entry.size + PER_ENTRY_OVERHEAD
+        end
+
         def read_entry(key, options) # :nodoc:
           entry = @data[key]
           synchronize do
@@ -139,8 +147,11 @@ module ActiveSupport
           synchronize do
             old_entry = @data[key]
             return false if @data.key?(key) && options[:unless_exist]
-            @cache_size -= old_entry.size if old_entry
-            @cache_size += entry.size
+            if old_entry
+              @cache_size -= (old_entry.size - entry.size)
+            else
+              @cache_size += cached_size(key, entry)
+            end
             @key_access[key] = Time.now.to_f
             @data[key] = entry
             prune(@max_size * 0.75, @max_prune_time) if @cache_size > @max_size
@@ -152,7 +163,7 @@ module ActiveSupport
           synchronize do
             @key_access.delete(key)
             entry = @data.delete(key)
-            @cache_size -= entry.size if entry
+            @cache_size -= cached_size(key, entry) if entry
             !!entry
           end
         end
diff --git a/activesupport/test/caching_test.rb b/activesupport/test/caching_test.rb
index d2382f0f5b..df570d485a 100644
--- a/activesupport/test/caching_test.rb
+++ b/activesupport/test/caching_test.rb
@@ -713,8 +713,8 @@ end
 
 class MemoryStoreTest < ActiveSupport::TestCase
   def setup
-    @record_size = ActiveSupport::Cache::Entry.new("aaaaaaaaaa").size
-    @cache = ActiveSupport::Cache.lookup_store(:memory_store, :expires_in => 60, :size => @record_size * 10)
+    @record_size = ActiveSupport::Cache.lookup_store(:memory_store).send(:cached_size, 1, ActiveSupport::Cache::Entry.new("aaaaaaaaaa"))
+    @cache = ActiveSupport::Cache.lookup_store(:memory_store, :expires_in => 60, :size => @record_size * 10 + 1)
   end
 
   include CacheStoreBehavior
@@ -764,6 +764,30 @@ class MemoryStoreTest < ActiveSupport::TestCase
     assert !@cache.exist?(1), "no entry"
   end
 
+  def test_prune_size_on_write_based_on_key_length
+    @cache.write(1, "aaaaaaaaaa") && sleep(0.001)
+    @cache.write(2, "bbbbbbbbbb") && sleep(0.001)
+    @cache.write(3, "cccccccccc") && sleep(0.001)
+    @cache.write(4, "dddddddddd") && sleep(0.001)
+    @cache.write(5, "eeeeeeeeee") && sleep(0.001)
+    @cache.write(6, "ffffffffff") && sleep(0.001)
+    @cache.write(7, "gggggggggg") && sleep(0.001)
+    @cache.write(8, "hhhhhhhhhh") && sleep(0.001)
+    @cache.write(9, "iiiiiiiiii") && sleep(0.001)
+    long_key = '*' * 2 * @record_size
+    @cache.write(long_key, "llllllllll")
+    assert @cache.exist?(long_key)
+    assert @cache.exist?(9)
+    assert @cache.exist?(8)
+    assert @cache.exist?(7)
+    assert @cache.exist?(6)
+    assert !@cache.exist?(5), "no entry"
+    assert !@cache.exist?(4), "no entry"
+    assert !@cache.exist?(3), "no entry"
+    assert !@cache.exist?(2), "no entry"
+    assert !@cache.exist?(1), "no entry"
+  end
+
   def test_pruning_is_capped_at_a_max_time
     def @cache.delete_entry (*args)
       sleep(0.01)