ConcurrentCache: FIFO cache eviction and time-based eviction

[adambajguz]

Hello,
Are there any plans of adding FIFO and time-based (e.g. time aware least recently used) eviction policies to ConcurrentCache?

[sakno]

Hi,

What you mean by FIFO? FIFO is a way of access to the data structure that doesn't support random access (e.g. queue). ConcurrentCache provides random access (by key), just like dictionary. Time-based eviction is not planned, because .NET provides MemoryCache class. Instead, ConcurrentCache provides frequency-based eviction when cache exceeds its capacity (which is not supported by MemoryCache).

[adambajguz]

Hi @sakno
Using FIFO algorithm the cache behaves in the same way as a FIFO queue. The cache evicts the entires in the order they were added, without any regard to how often or how many times they were accessed before.

[sakno]

What's the use case for that?

[sakno]

Also, I'm curious about update operation. Key is the same but with different value. In case of what you proposed, update operation doesn't impact this case and pair evicts according to the first occurrence of the key.

[adambajguz]

As far as I understood this, the FIFO cache eviction is quite simple: instead of evicting least recently or frequently used entry, the oldest entry is evicted.

Example:

CacheCapacity=3
ADD(A, 1)     ->   Cache { (A,1) }
ADD(B, 2)     ->   Cache { (A,1), (B,2) }
ADD(C, 3)     ->   Cache { (A,1), (B,2), (C,3) }
UPDATE(A, 0)  ->   Cache { (A,0), (B,2), (C,3) }
ADD(D, 4)     ->   Cache { (B,2), (C,3), (D,4) }
ADD(E, 5)     ->   Cache { (C,3), (D,4), (E,5) }

What's the use case for that?
I think that it is faster or at least consumes less resources then LRU or LFU policies.

[sakno]

In this case, update operation has different effect on the cache depending on the presence of the key. If key A doesn't exist, Update behaves like Add operation, adding a new pair with the longest lifetime. Otherwise, the lifetime of the pair remains the same, which looks unfair.

it is faster or at least consumes less resources

It will not consume less resources, the cache still needs a list of size N with synchronized access to it to reorder the elements. Currently, LRU and LFU reuses the same approach to improve the performance: load balancing between threads and decoupling internal dictionary from the command queue. For instance, LRU/LFU don't require a lock to read from the dictionary.