[CCACHE-32] LIRSCache defect allows it's memory use to grow without bound Created: 10/Oct/13  Updated: 01/Mar/18

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

Type: Defect Priority: Major
Reporter: Jonathan Coveney Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Hello! I was messing around with the LIRSCache and ran into what I think is a bug.

https://github.com/clojure/core.cache/blob/master/src/main/clojure/clojure/core/cache.clj#L371

In the case of a bunch of misses on unique keys, then the stack S will grow without bound and violate the limit that you give it.

(def C (cache/lirs-cache-factory {} :s-history-limit 2 :q-history-limit 1))
(defn populate [n] (let [pairs (map (fn [x] [x x]) (range n))] (reduce (fn [cache [k v]] (cache/miss cache k v)) C pairs)))
(.toString (populate 10))
"{9 9, 1 1, 0 0}, {0 1, 1 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10}, {9 10}, 10, 2, 1"

You can see that the S stack is growing without bound, and if you do (populate 1000), then it is 1000 pieces large.

I'm not sure what the desired outcome is, but any time we add something to one of the queues, we need to make sure that we're doing the right thing with what is kicked out, unless I'm misinterpreting things.

Thanks for making Clojure awesome!






[CCACHE-36] Allow ttl to be set for a key on cache miss Created: 10/Oct/14  Updated: 01/Mar/18

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

Type: Enhancement Priority: Major
Reporter: Patrick Gombert Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None

Attachments: File variable-ttl.diff    
Patch: Code and Test

 Description   

Create a second arity for miss that takes an options map. In the TTLCache implementation use the :ttl key from the options to set a non-default ttl for a cache object. All other implementations will disregard the options and call the original version of miss.



 Comments   
Comment by Patrick Gombert [ 10/Oct/14 4:55 PM ]

Here's the use case that motivated this:

We want to store oauth tokens so that we do not constantly have to make service calls to verify the token. The response on this service call has the expiration time of the token. We want to set our ttl to expire when the oauth token expires.

Comment by Sean Corfield [ 01/Mar/18 12:45 AM ]

Definitely an interesting enhancement to the basic TTLCache. It would require that each item be stored with both its creation time and its own TTL, and therefore a miss would have to scan the entire keyset to evict expired items (since each one can expire at a different time). The current TTLCache actually suffers from that performance problem already – see CCACHE-15 – so it wouldn't be any worse than that.

You wouldn't be able to use this new miss call via through, so it also has that disadvantage.





[CCACHE-38] Add ARC or CAR algorithm Created: 25/Nov/14  Updated: 01/Mar/18

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

Type: Enhancement Priority: Major
Reporter: Daniel Compton Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Both ARC and CAR algorithm's look like they could be an improvement on LIRS and LRU algorithms. Specifically, both of them are better at keeping frequently used items in cache.

From: http://en.wikipedia.org/wiki/Cache_algorithms#Examples

Adaptive Replacement Cache (ARC)
Constantly balances between LRU and LFU, to improve the combined result. ARC improves on SLRU by using information about recently-evicted cache items to dynamically adjust the size of the protected segment and the probationary segment to make the best use of the available cache space.

Clock with Adaptive Replacement (CAR)
Combines Adaptive Replacement Cache (ARC) and CLOCK. CAR has performance comparable to ARC, and substantially outperforms both LRU and CLOCK. Like ARC, CAR is self-tuning and requires no user-specified magic parameters.

More details on ARC are at http://blog.acolyer.org/2014/10/08/outperforming-lru-with-an-adaptive-replacement-cache-algorithm/, and the paper is at http://dbs.uni-leipzig.de/file/ARC.pdf.

CAR details are at https://www.usenix.org/conference/fast-04/car-clock-adaptive-replacement

If there is interest in this then I could look at benchmarking both of them, and putting together a patch.



 Comments   
Comment by Sean Corfield [ 01/Mar/18 3:33 AM ]

If you're still interested in investigating and benchmarking this, then I've open to a patch to add these.





[CCACHE-50] Suggested usage subject to Cache Stampede Created: 22/Sep/18  Updated: 03/Oct/18

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

Type: Defect Priority: Major
Reporter: Orestis Markou Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None


 Description   

I've been trying to wrap my head around core.cache, and it seems to me that the suggest use in the documentation, i.e.

(defn get-data [key]
  (cache/lookup (swap! cache-store
                       #(if (cache/has? % key)
                          (cache/hit % key)
                          (cache/miss % key (retrieve-data key))))
                key))

will result in a Cache Stampede since (retrieve-data key) might be called multiple times if swap! retries due to compare-and-swap misses. Unfortunately I don't have a suggestion on how this could be fixed.



 Comments   
Comment by Sean Corfield [ 22/Sep/18 1:41 PM ]

It took me a while to find this suggested usage – https://github.com/clojure/core.cache/wiki/Using

I should update that to use through-cache which is more idiomatic now:

(defn get-data [key]
  (cache/lookup (swap! cache-store cache/through-cache key retrieve-data) key))

It would still suffer from the same possibility of Cache Stampede but at least it would be consistent with the newer API.

I suspect using a local delay would mitigate the stampede issue but it would make for very ugly code and it would not play well with through-cache – so I'll have to give that some thought.

Comment by Sean Corfield [ 03/Oct/18 12:56 AM ]

The local delay version would look like this:

(defn get-data [key]
  (let [data (delay (retrieve-data key)]
    (cache/lookup (swap! cache-store cache/through-cache key (fn [_] @data)) key)))




[CCACHE-35] Add weak-cache Created: 24/Aug/14  Updated: 01/Mar/18

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

Type: Enhancement Priority: Major
Reporter: Peter Fraenkel Assignee: Sean Corfield
Resolution: Unresolved Votes: 1
Labels: None

Patch: Code and Test

 Description   

Makes a weak-cache-factory available. Entries will be eagerly collected by the jvm, rather than only when there's memory pressure.
Implementation is fairly simple. I changed SoftCache to NonStrongCache and added an extra record parameter, which is the function
used to create the reference.
See https://github.com/pnf/core.cache/compare/clojure:master...master



 Comments   
Comment by Sean Corfield [ 01/Mar/18 3:35 AM ]

This looks interesting. For backward compatibility reasons, I would not want to change any of the public names, but I'd be open to a patch that is purely additive to add the NonStrongCache and reimplement SoftCache in terms of it, as well as adding the WeakCache.





[CCACHE-11] Add eviction implementation to LIRSCache Created: 08/Dec/11  Updated: 01/Mar/18

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

Type: Task Priority: Major
Reporter: Fogus Assignee: Sean Corfield
Resolution: Unresolved Votes: 1
Labels: associative, cache, evict, lirs


 Description   

The evict method in the ProtocolCache needs implementation for LIRSCache. I will start initially with a single key eviction method to start. The evict method would form the basis for the associative dissoc which in turn forms the basis for proper limited seeding. LIRS poses an additional complication due to its dual limit lists. Currently only the BasicCache impl has evict.






[CCACHE-16] Benchmark v0.5.x against Google Guava Created: 16/Dec/11  Updated: 01/Mar/18

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

Type: Task Priority: Minor
Reporter: Fogus Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: benchmark, cache, guava


 Description   

Perform some tests and benchmarks of core.cache and Google Guava's com.google.common.cache library.






[CCACHE-17] Create function backed cache Created: 16/Dec/11  Updated: 01/Mar/18

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

Type: Enhancement Priority: Minor
Reporter: Fogus Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: cache, fn-cache, new-feature


 Description   

A cache implementation that is backed by a function that performs some action on a cache miss could serve as a front for any of the existing cache impls.



 Comments   
Comment by Rich Hickey [ 16/Dec/11 9:45 AM ]

It doesn't perform an action per se, it gets a passed key and returns a value, which the cache then caches (associates with the key) and returns. The tricky bit is when the function can't get a value. There needs to be some protocol for communicating that (could be like 3 arg get), and, should the cache be asked again later for the same key, calling the fn again.

Comment by Fogus [ 19/Dec/11 7:29 AM ]

Thanks for the feedback Rich. I believe I understand the subtleties now.

Comment by Sean Corfield [ 01/Mar/18 1:25 AM ]

@fogus is this the basis for FnCache which doesn't seem to have a factory or be documented/tested? Is that just "dead" code now?

Also, it seems that through fills some of this gap since it provides for functions to run on a cache miss (although it still doesn't address when the function can't get a value, right?).





[CCACHE-51] Stats for cache Created: 03/Oct/18  Updated: 11/Nov/18

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

Type: Enhancement Priority: Minor
Reporter: Oleksii Khomchenko Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None

Attachments: Text File wip-cache-stats.patch    
Patch: Code and Test

 Description   

I have used core.cache in some of my projects. It is a great library and I liked it a lot. It only lacks stats so I can adjust size of the cache based on some statistics. I have decided to write a custom cache implementation that would allow to get hit/miss stats for the cache. First it was a separate project but then I figured out that I need one change in core.cache itself which I can not hack nicely around. So here is the patch to add stats-aware cache implementation.

Quick demo:

(require '[clojure.core.cache :as core.cache]
         '[clojure.core.cache.stats :as ccs]
         '[clojure.core.cache.stats.counters :as ccs.counters])

(def cache (-> {} core.cache/lru-cache-factory ccs/measured-cache))
(ccs/stats cache)  ; {:hit 0, :miss 0, :request 0, :hit-ratio 1.0, :miss-ratio 1.0}
(def cache (assoc cache :foo "bar"))
(ccs/stats cache)  ; {:hit 0, :miss 1, :request 1, :hit-ratio 0.0, :miss-ratio 1.0}
(get cache :foo)  ; "bar"
(get cache :foo)  ; "bar"
(ccs/stats cache)  ; {:hit 2, :miss 1, :request 3, :hit-ratio 0.6666666666666666, :miss-ratio 0.3333333333333333}

What's new:

  • core.cache.stats namespace which provides MeasuredCache that implements CacheProtocol and a measured-cache function to instantiate it. MeasuredCache also implements MeasuredCacheProtocol which has only one responsibility - to return snapshot of hit/miss stats
  • core.cache.stats.counters namespace which provides a protocol (StatsCounterProtocol) that allows to implement hit/miss counters. There are two implementations already: one is based on long wrapped in atom, another one (which is used by default) is based on LongAdder
  • tests are there for all the methods that could be invoked

Caveats (in no particular order):

Things to finish before merge:

  • if you would like the idea I'll add more docs (maybe I should have started with this one so higher chances to be accepted?)
  • polish code (I'm not an expert in Clojure at all), naming and namespaces

Thank you in advance for the feedback



 Comments   
Comment by Sean Corfield [ 03/Oct/18 12:59 PM ]

It's a very interesting idea, thank you! I can definitely see value in this for a lot of users of core.cache (including myself).

I'll take a look over the patch but, in the meantime, I don't see your name listed on the Contributors' page – so could you go through the process here https://clojure.org/community/contributors if you haven't already?

Comment by Oleksii Khomchenko [ 03/Oct/18 8:31 PM ]

I have already signed the SLA with my email and github username. Maybe I did it wrong, I'll check again.

Comment by Sean Corfield [ 03/Oct/18 9:29 PM ]

Thanks. I'll confirm with Alex tomorrow since the website lags behind.

Comment by Oleksii Khomchenko [ 06/Oct/18 2:04 PM ]

Good day.

Still no update on that contributors page. Could I help somehow to get it resolved?

Thank you.

Comment by Sean Corfield [ 06/Oct/18 6:25 PM ]

I asked Alex to check the recent CAs submitted – I expect he'll be able to confirm next week. It'll take me a while to review and analyze the patch anyway (and I'm neck-deep in production roll-outs right now so be patient).

Comment by Oleksii Khomchenko [ 06/Oct/18 6:44 PM ]

Ah, I've asked mostly for contributors page not displaying me issue

Comment by Oleksii Khomchenko [ 07/Oct/18 3:08 AM ]

Has added some docs.

Comment by Oleksii Khomchenko [ 11/Nov/18 1:26 PM ]

Good day. Any updates on this? Anything I can do to help? Thanks

Comment by Sean Corfield [ 11/Nov/18 2:21 PM ]

Still under consideration. I'm looking at a bunch of issues with this library and will include this as part of that with when I've figured out the other hard issues.





[CCACHE-55] Split protocols from implementations Created: 19/Mar/19  Updated: 19/Mar/19

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

Type: Enhancement Priority: Minor
Reporter: Andrea Richiardi Assignee: Sean Corfield
Resolution: Unresolved Votes: 0
Labels: None


 Description   

Hi Sean. I would like to propose a change mainly for starting being ClojureScript friendly.

It would be very useful to have all the protocols in one .cljc file and the implementations in different ones. This would open the doors for a ClojureScript port of some of the implementations down the road.

I don't know exactly how the split could be organized as I have just glanced the code but I am opening this issue to taste the waters about the idea.

Thank you!



 Comments   
Comment by Sean Corfield [ 19/Mar/19 4:22 PM ]

Since core.cache is designed to be extensible, the protocols are probably in use by existing user code out there so moving them would be a breaking change.

Comment by Andrea Richiardi [ 19/Mar/19 4:26 PM ]

Oh that's too bad, could they be kept in the core file and move the implementations elsewhere?

Maybe we could go with clojure.core.cache2?

Comment by Sean Corfield [ 19/Mar/19 4:37 PM ]

Yeah, I think it would have to be a whole new set of namespaces at this point. Protocols in one common ns, and then probably each implementation in a separate ns so that some can be clj/cljs (like the BasicCache) and others can be either clj if they touch Java or cljc or cljs.

And core.memoize would probably need to follow suit since the two libs are coupled in various ways.

Comment by Andrea Richiardi [ 19/Mar/19 4:54 PM ]

Sounds like a good plan, as reference I am going to leave also the link to cljs-cache here.





Generated at Wed Apr 24 01:04:19 CDT 2019 using JIRA 4.4#649-r158309.