Ayende @ Rahien

Damien Guard commented on Implementing LRU cache

Sat, 06 Oct 2012 17:11:56 GMT

If multiple threads call in on a cache miss at the same time you'll end up with a cache entry that has a usage of 1. [)amien

Patrick Huizinga commented on Implementing LRU cache

Tue, 18 Sep 2012 13:45:23 GMT

One small nitpick: this doesn't look like a LRU (Least Recently Used) cache, but more like a (LFU) Least Frequently Used cache.

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:45:18 GMT

Davh, The only requests that require admin privileges are things like "create new db, back a db, delete a db". Those tend to be fairly rare :-)

davh commented on Implementing LRU cache

Fri, 14 Sep 2012 07:43:11 GMT

You never know when someone chose to make all their users admin and let them access the db :) e.g. some test server in a software development company where they all have admin access to it.

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:28:43 GMT

Dennis, I see, good point. I fixed both issues, but I don't think either would have been a problem. This is a LRU for admins, the number of expected admins is low, and the number of requests requiring them is even lower :-)

Dennis commented on Implementing LRU cache

Fri, 14 Sep 2012 07:22:18 GMT

The most annoying part about LRU caches is that they are prune to cache trashing. If you have more users (in this case) than the max cache size, a LRU is worse than not having a cache. So it would therefore be very useful to get a log entry every time the max size is exceed. Then it is very visible for someone complaining about slow logins if they are in the situation where the cache is not working. And btw, you forgot to prune expired entries before the Least recently used.

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:15:44 GMT

Davh, Can you explain a bit more about what you mean here?

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:14:57 GMT

Rafal, We actually have several. The difference is that each have different semantics. From Admin, we take into account duration, for caching execution plans, we take into account memory and time. We use specialized versions, because we don't have the need for a uber generic one.

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:08:32 GMT

Tobi, Excellent commentary, I've modified the actual cache to use Lazy to avoid this issue.

Ayende Rahien commented on Implementing LRU cache

Fri, 14 Sep 2012 07:01:18 GMT

Steve, That is a ConcurretnDictionary there, it won't throw under this scenario.

davh commented on Implementing LRU cache

Fri, 14 Sep 2012 06:45:58 GMT

You forgot to add a log entry when it does clear the cache, so that it is possible to see when cache trashing occurs.

Steve commented on Implementing LRU cache

Thu, 13 Sep 2012 20:58:29 GMT

@tobi, If he doesn't expect to even reach MaxCacheSize (25) then I see no problem with this implementation. But do you have the name of the pattern that could handle the load you are describing?

Steve commented on Implementing LRU cache

Thu, 13 Sep 2012 20:55:59 GMT

ConcurrentDictionary does not work with a "version" like the generic collections and doesn't throw on modified collections while enumerating, it seems to handle most cases like expected :) var dict = new ConcurrentDictionary(); for (var i = 0; i < 5; i++) dict.TryAdd("Test" + i, ""); foreach (var entry in dict) { string value; dict.TryRemove(entry.Key, out value); } Leaves you with an empty dict.

tobi commented on Implementing LRU cache

Thu, 13 Sep 2012 20:07:00 GMT

A simple fix is not to cache a T but a Lazy[T] at the highest mode of synchronization.

Rafal commented on Implementing LRU cache

Thu, 13 Sep 2012 20:05:23 GMT

Nice implementation, but how is it possible that there was no general-purpose LRU cache in Raven? And watch out for the API: Some time ago I have been tasked with implementing similar, windows-based security and had quite serious problems with accessing user information through UserPrincipal API (there were two mutually trusted domains where users could belong to groups in both of them - in such case the MS API sometimes kept throwing undocumented errors at me). And this made me wonder if we could give all that work to Windows file system - by checking user permissions to designated files representing various application rights.

tobi commented on Implementing LRU cache

Thu, 13 Sep 2012 20:03:40 GMT

This cache suffers from cache stampeding. At 1000k requests per seconds and 2s to produce a cache value this will *overwhelm* the poor AD server. It will need to handle 2k requests in 2sec suddenly when the cache item expires. I hate caches which use the CAS pattern (get, produce, try-insert). This only goes well if there is little load on the individual cache item.

Steve commented on Implementing LRU cache

Thu, 13 Sep 2012 19:57:39 GMT

Doesn't the foreach throw an exception if you modify the cache inside the loop?