<< Back to previous view

[CCACHE-15] It appears that TTL cache exhibits quadratic performance (+ its evict is buggy) Created: 14/Dec/11  Updated: 07/Mar/17

Status: Open
Project: core.cache
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jason Wolfe Assignee: Fogus
Resolution: Unresolved Votes: 4
Labels: None

Attachments: Text File Avoid-scanning-all-ttl-entries.patch     Text File quadratic-fix-using-queue.patch    


The library looks useful, thanks!

I looked at the code, and unless I'm mistaken, every cache miss seems to result in a full pass over the entire cache to evict old entries. The performance implications of this would be unacceptable for my target application. Replacing the TTL data structure with a persistent analog of a LinkedHashMap and using a take-while instead could fix this problem.

Also, evict seems to pass the cache in twice, rather than the cache and the TTL...

Comment by Fogus [ 15/Dec/11 12:21 PM ]

TTLCache eviction fixed. Patches welcomed for the other change, but we might be able to get away with a sorted map ttl map.

Comment by Kimmo Koskinen [ 22/May/14 12:09 AM ]

Could we use a priority map (https://github.com/clojure/data.priority-map) for the ttl map and iterate it with

 (for [... :while]) 
so that we break out early?

Comment by Kimmo Koskinen [ 25/May/14 5:16 AM ]

I tried using priority-map for the ttl data and take-while instead of filter in key-killer. This would seem to help in the case where the entries in the cache are mostly fresh, since in that case we avoid iterating over all entries in ttl. We'r still in the original complexity class, but this should be an improvement still.

The change is here https://github.com/viesti/core.cache/commit/ca76508ae89ea22ce6551017403d76879805c26c, what do you think about it? I'm planning on getting to test it in our environment (~30000 cache entries, 100-200 queries per second).

Comment by Kimmo Koskinen [ 25/May/14 5:28 AM ]

Here's the change as a patch file too. Replaces filter with take-while in key-killer and uses priority-map to keep ttl data sorted.

Comment by Kimmo Koskinen [ 27/May/14 4:38 AM ]

Hmm, I made another observation. I have a scenario where I combine TTLCache with LUCache so that I keep a bounded number of items in cache and have an expiration time limit too.

The ttl structure in TTLCache isn't aware of this behaviour, so it just accumulates entries that have been evicted from the backing cache.

Comment by Leon Barrett [ 29/May/16 1:08 AM ]

I also noticed this problem and made a patch. This quadratic performance really needs to be fixed--it bit me kind of badly. Using a cache should not make my code unusably slower!

Comment by Ivan Kryvoruchko [ 07/Mar/17 11:11 AM ]

Is it an intended behavior? http://dev.clojure.org/jira/browse/CCACHE-15?focusedCommentId=34738&page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel#comment-34738 Spent some time debugging this problem today, looks like bug to me. In case this is really a bug should a separate issue be created for it?

Simplest way to reproduce (`has?` returns true, but item itself is no longer in cache):

user> (require '[clojure.core.cache :as cache])
user> (let [C (-> {}
                  (cache/lru-cache-factory :threshold 1)
                  (cache/ttl-cache-factory :ttl 360000))
            C2 (if (cache/has? C :c)
                 (cache/hit C :c)
                 (cache/miss C :c 42))
            C3 (if (cache/has? C2 :d)
                 (cache/hit C2 :d)
                 (cache/miss C2 :d 42))]
        [(cache/has? C3 :c)
         (cache/lookup C3 :c)])
[true nil]
Generated at Wed Oct 18 20:44:44 CDT 2017 using JIRA 4.4#649-r158309.