sema-cache 0.1.0

TTL and LRU caching, memoization, and optional persistent kv-backed caches

Source

package.sema

258 lines 3a0341cd9f3b
File details

Source stored with sema-cache 0.1.0. Line links refer to these exact bytes.

SHA-256 3a0341cd9f3ba7e617c6f58d9bb47369cd85463cecc17955f928fef345a7421b

1;; sema-cache — TTL and LRU caching, memoization, and optional persistent kv-backed caches
2;;
3;; General-purpose caching for everything the LLM runtime's built-in response
4;; cache doesn't cover: HTTP calls, expensive computations, file parses.
5;; Modeled on Clojure's core.cache / core.memoize.
6;;
7;; A cache handle is a closure over mutable state, dispatching on a message
8;; keyword (:lookup!, :contains?, :put!, :evict!, :clear!, :stats). The public
9;; cache/* functions wrap that protocol, so the in-memory and kv-backed handles
10;; are interchangeable.
11
12(module sema-cache
13  (export cache/new
14          cache/get
15          cache/get-or
16          cache/put!
17          cache/contains?
18          cache/evict!
19          cache/clear!
20          cache/stats
21          cache/memoize
22          cache/kv-cache)
23
24  ;; ---------------------------------------------------------------------
25  ;; Private: in-memory cache internals
26  ;; ---------------------------------------------------------------------
27
28  ;; Entry shape: {:value v :written ms :touched n :inserted n} where n is a
29  ;; monotonic counter shared by the whole cache. :touched orders LRU recency
30  ;; (bumped on put and on every touching get); :inserted orders FIFO (bumped
31  ;; on put only, so gets never affect FIFO order).
32
33  (define (entry-expired? entry ttl-ms clock-fn)
34    (and ttl-ms (>= (- (clock-fn) (get entry :written)) ttl-ms)))
35
36  ;; Victim selection scans every entry for the minimum counter. O(n) per
37  ;; eviction is fine at the sizes this package targets (hundreds to a few
38  ;; thousand entries): sema's sorted maps iterate by key, not by recency,
39  ;; so avoiding the scan would need a second ordered index that costs more
40  ;; to maintain than it saves.
41  (define (victim-key entries slot)
42    (first
43      (foldl (fn (best e)
44               (let ((k (first e))
45                     (n (get (nth e 1) slot)))
46                 (if (or (nil? best) (< n (nth best 1)))
47                     (list k n)
48                     best)))
49             nil
50             (map/entries entries))))
51
52  (define (cache/new . opts)
53    "Create an in-memory cache handle.
54Options: :max-size (1024) entries before eviction, :ttl-ms (nil = no expiry)
55milliseconds after write before an entry expires, :policy :lru (default,
56evicts the least-recently-used entry) or :fifo (evicts the oldest insertion;
57re-putting a key counts as re-insertion), :clock-fn (for testing; defaults to
58time-ms). Expired entries are evicted lazily on access and never count as hits.
59Keys are compared with equal?, so lists, strings, and maps all work as keys."
60    (let* ((o         (if (null? opts) {} (first opts)))
61           (max-size  (get o :max-size 1024))
62           (ttl-ms    (get o :ttl-ms nil))
63           (policy    (get o :policy :lru))
64           (clock-fn  (get o :clock-fn time-ms))
65           (entries   {})
66           (counter   0)
67           (hits      0)
68           (misses    0)
69           (evictions 0))
70      (when (not (or (= policy :lru) (= policy :fifo)))
71        (error (format "cache/new: unknown :policy ~a — use :lru or :fifo" policy)))
72      (when (< max-size 1)
73        (error (format "cache/new: :max-size must be at least 1 — got ~a" max-size)))
74      (define (expired? entry)
75        (entry-expired? entry ttl-ms clock-fn))
76      ;; Touching lookup: returns the entry map, or nil on miss/expiry.
77      ;; The entry map is never nil, so a stored nil value is still a hit.
78      (define (lookup! k)
79        (let ((entry (get entries k)))
80          (cond
81            ((nil? entry)
82             (set! misses (+ misses 1))
83             nil)
84            ((expired? entry)
85             (set! entries (dissoc entries k))
86             (set! evictions (+ evictions 1))
87             (set! misses (+ misses 1))
88             nil)
89            (else
90             (set! counter (+ counter 1))
91             (set! entries (assoc entries k (assoc entry :touched counter)))
92             (set! hits (+ hits 1))
93             entry))))
94      (define (store! k v)
95        (when (and (not (contains? entries k))
96                   (>= (count entries) max-size))
97          (let ((slot (if (= policy :lru) :touched :inserted)))
98            (set! entries (dissoc entries (victim-key entries slot)))
99            (set! evictions (+ evictions 1))))
100        (set! counter (+ counter 1))
101        (set! entries (assoc entries k {:value v
102                                        :written (clock-fn)
103                                        :touched counter
104                                        :inserted counter}))
105        nil)
106      (fn (msg . args)
107        (cond
108          ((= msg :lookup!) (lookup! (first args)))
109          ((= msg :contains?)
110           ;; Non-touching and non-counting: answers expiry-aware presence
111           ;; without bumping recency or the hit/miss counters.
112           (let ((entry (get entries (first args))))
113             (and (not (nil? entry)) (not (expired? entry)))))
114          ((= msg :put!) (store! (first args) (nth args 1)))
115          ((= msg :evict!)
116           (if (contains? entries (first args))
117               (begin (set! entries (dissoc entries (first args))) #t)
118               #f))
119          ((= msg :clear!)
120           (set! entries {})
121           nil)
122          ((= msg :stats)
123           {:hits hits :misses misses :evictions evictions :size (count entries)})
124          (else
125           (error (format "sema-cache: unknown message ~a" msg)))))))
126
127  ;; ---------------------------------------------------------------------
128  ;; Public operations (work on any cache handle)
129  ;; ---------------------------------------------------------------------
130
131  (define (cache/get c k . default)
132    "Return the cached value for k, or default (nil) on a miss.
133A hit counts toward :hits and refreshes LRU recency; a miss — including an
134expired entry — counts toward :misses. nil values are cacheable, so a nil
135return is ambiguous: use cache/contains? or a sentinel default to distinguish."
136    (let ((entry (c :lookup! k)))
137      (if (nil? entry)
138          (if (null? default) nil (first default))
139          (get entry :value))))
140
141  (define (cache/get-or c k thunk)
142    "Return the cached value for k, or run thunk, cache its result, and return it.
143A hit refreshes LRU recency and never calls thunk — a cached nil is a hit too
144(stored entries are distinguished from misses internally, not by value).
145A miss runs thunk exactly once and stores the result, evicting if full."
146    (let ((entry (c :lookup! k)))
147      (if (nil? entry)
148          (let ((v (thunk)))
149            (c :put! k v)
150            v)
151          (get entry :value))))
152
153  (define (cache/put! c k v)
154    "Store v under k, evicting per the cache's policy if it is full.
155Overwriting an existing key never evicts; it refreshes the entry's TTL clock,
156LRU recency, and (for :fifo) its insertion order. Returns nil."
157    (c :put! k v))
158
159  (define (cache/contains? c k)
160    "Return #t if k has a live (non-expired) entry, #f otherwise.
161Does not touch LRU recency and does not count toward :hits/:misses."
162    (c :contains? k))
163
164  (define (cache/evict! c k)
165    "Remove k from the cache. Returns #t if it was present, #f otherwise.
166Manual eviction does not count toward the :evictions stat (which tracks
167capacity- and TTL-driven evictions only)."
168    (c :evict! k))
169
170  (define (cache/clear! c)
171    "Remove every entry. The :hits/:misses/:evictions counters are preserved;
172:size drops to 0. Returns nil."
173    (c :clear!))
174
175  (define (cache/stats c)
176    "Return {:hits n :misses n :evictions n :size n} for the cache."
177    (c :stats))
178
179  ;; ---------------------------------------------------------------------
180  ;; Memoization
181  ;; ---------------------------------------------------------------------
182
183  (define (cache/memoize f . opts)
184    "Return a memoized version of f backed by an internal cache/new.
185The cache key is the full argument list (equal?-based), so multi-arg and
186variadic functions work; (m 1 2) and (m 2 1) are distinct keys. Accepts the
187same options map as cache/new, plus :cache — a pre-built handle to use
188instead, which lets you inspect cache/stats or evict entries from outside."
189    (let* ((o (if (null? opts) {} (first opts)))
190           (c (get o :cache (cache/new (dissoc o :cache)))))
191      (fn ( . args)
192        (cache/get-or c args (fn () (apply f args))))))
193
194  ;; ---------------------------------------------------------------------
195  ;; Persistent kv-backed cache
196  ;; ---------------------------------------------------------------------
197
198  ;; kv rows are {:value v :written ms}; TTL is enforced by comparing the
199  ;; stored :written timestamp against :clock-fn on every access.
200
201  (define (kv-key! k)
202    (if (string? k)
203        k
204        (error (format "cache/kv-cache: keys must be strings — got ~a" k))))
205
206  (define (cache/kv-cache name path . opts)
207    "Open a persistent cache backed by the stdlib kv store (a JSON file at path).
208name is the process-local kv handle; entries survive across runs in the file.
209Keys must be strings. Values must round-trip through JSON: keywords become
210strings, string map keys come back as keywords, NaN/Infinity floats become
211nil — cache only JSON-representable data. Options: :ttl-ms (nil = no expiry),
212:clock-fn (for testing; defaults to time-ms). There is no :max-size/:policy —
213the kv file has no recency index and every write rewrites the whole file, so
214capacity eviction belongs in an in-memory cache/new, not here. Returns a
215handle usable with every cache/* function; the :hits/:misses/:evictions
216counters are per-process and reset on each open."
217    (let* ((o         (if (null? opts) {} (first opts)))
218           (ttl-ms    (get o :ttl-ms nil))
219           (clock-fn  (get o :clock-fn time-ms))
220           (hits      0)
221           (misses    0)
222           (evictions 0))
223      (kv/open name path)
224      (define (expired? row)
225        (entry-expired? row ttl-ms clock-fn))
226      (define (lookup! k)
227        (let ((row (kv/get name (kv-key! k))))
228          (cond
229            ((nil? row)
230             (set! misses (+ misses 1))
231             nil)
232            ((expired? row)
233             (kv/delete name k)
234             (set! evictions (+ evictions 1))
235             (set! misses (+ misses 1))
236             nil)
237            (else
238             (set! hits (+ hits 1))
239             row))))
240      (fn (msg . args)
241        (cond
242          ((= msg :lookup!) (lookup! (first args)))
243          ((= msg :contains?)
244           (let ((row (kv/get name (kv-key! (first args)))))
245             (and (not (nil? row)) (not (expired? row)))))
246          ((= msg :put!)
247           (kv/set name (kv-key! (first args))
248                   {:value (nth args 1) :written (clock-fn)})
249           nil)
250          ((= msg :evict!) (kv/delete name (kv-key! (first args))))
251          ((= msg :clear!)
252           (for-each (fn (k) (kv/delete name k)) (kv/keys name))
253           nil)
254          ((= msg :stats)
255           {:hits hits :misses misses :evictions evictions
256            :size (length (kv/keys name))})
257          (else
258           (error (format "sema-cache: unknown message ~a" msg))))))))