You have a map and want to prune the oldest values (fifo) on add.

fifo-map.cljs

(defn assoc-ordered
  [[m v :as mv] k value]
  
  [(assoc m k value)
   (if (get m k)
     (->
       (remove #{k} v)
       vec
       (conj k))
     (conj (or v []) k))])

(defn prune-ordered-fifo
  [mv num]
  (loop [[m v :as mv] mv]
   (if (> (count v) num)
       (recur
         [(dissoc m (first v))
          (rest v)])
       mv)))

(defn assoc-ordered-fifo
  "You have a map and want to prune the oldest values (fifo) on add.
   
   Takes a vector of a map and a vector with the keys of the map.
   "
  [mv k value fifo-size]
  (-> mv
      (assoc-ordered k value)
      (prune-ordered-fifo fifo-size)))