Uploaded image for project: 'core.cache'
  1. CCACHE-39

FIFOCache member exempted from expulsion after evict


    • Type: Bug
    • Status: Closed
    • Priority: Critical
    • Resolution: Completed
    • Labels:


      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:

      user> (require '[clojure.core.cache :as cache])
      user> (def C (cache/fifo-cache-factory {:a 1 :b 2} :threshold 2))
      user> C
      {:b 2, :a 1}
      user> (.toString C)
      "{:b 2, :a 1}, (:b :a)"
      user> (def C2 (cache/evict C :b))
      user> (.toString C2)
      "{:a 1}, (:a)"
      user> (def C3 (cache/miss C2 :c 42))
      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:

      user> (def C4 (cache/miss C3 :d 43))
      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.

      (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))))




            • Assignee:
              seancorfield Sean Corfield
              alex+import import
            • Votes:
              0 Vote for this issue
              0 Start watching this issue


              • Created: