FIFOCache member exempted from expulsion after evict

Description

Calling evict causes FIFOCache to lose track of one of the remaining
keys, so that member will never expire. Gradually, nearly the entire
FIFOCache may become occupied by permanent members.

FIFOCache keeps a threshold and a sequence of keys. seed fills the
sequence fully to the threshold – the postcondition on
fifo-cache-factory attests to this invariant –
and miss holds the sequence length steady by dropping the first key
when adding a new last key. But evict shortens the key sequence.
And miss, although it always drops the oldest key, removes the
corresponding map entry only if the map's size meets or exceeds the
threshold. The problem arises after evict shortens the key
sequence: the next call to miss throws away the oldest key without
removing its entry from the map. As a result, an old thing, which
should have been removed, remains forever.

The toString of FIFOCache helpfully displays both the map and the
key sequence, so we can observe as the sequence loses keys:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 user> (require '[clojure.core.cache :as cache]) user> (def C (cache/fifo-cache-factory {:a 1 :b 2} :threshold 2)) #'user/C user> C {:b 2, :a 1} user> (.toString C) "{:b 2, :a 1}, (:b :a)" user> (def C2 (cache/evict C :b)) #'user/C2 user> (.toString C2) "{:a 1}, (:a)" user> (def C3 (cache/miss C2 :c 42)) #'user/C3 user> (.toString C3) "{:c 42, :a 1}, (:c)"

Now the map is correct but the key sequence has forgotten :a; it will
never be expired. We will add :d and observe FIFOCache discarding
the new :c instead of the old :a:

1 2 3 4 user> (def C4 (cache/miss C3 :d 43)) #'user/C4 user> (.toString C4) "{:d 43, :a 1}, (:d)"

The following silly loop puts numbers 0 through 999 into a FIFOCache
and evicts half of them immediately after adding them. This pattern
soon exhausts the key sequence – leaving only one slot turning over
according to the FIFO rule. The final println shows 999 occupying
that slot while the oldest items (1 to 61) remain in the FIFOCache.

1 2 3 4 5 6 7 (loop [C (cache/fifo-cache-factory {}), D (range 1000)] (if (seq D) (let [d (first D) C' (-> C (cache/miss d d) (cond-> (even? d) (cache/evict d)))] (recur C' (rest D))) (println (.toString C))))

Environment

None

Status

Assignee

Sean Corfield

Reporter

import

Labels

None

Approval

None

Patch

None

Priority

Critical