sema-cache 0.1.0
TTL and LRU caching, memoization, and optional persistent kv-backed caches
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 caches2;;3;; General-purpose caching for everything the LLM runtime's built-in response4;; 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 message8;; keyword (:lookup!, :contains?, :put!, :evict!, :clear!, :stats). The public9;; cache/* functions wrap that protocol, so the in-memory and kv-backed handles10;; are interchangeable.1112(module sema-cache13(export cache/new14cache/get15cache/get-or16cache/put!17cache/contains?18cache/evict!19cache/clear!20cache/stats21cache/memoize22cache/kv-cache)2324;; ---------------------------------------------------------------------25;; Private: in-memory cache internals26;; ---------------------------------------------------------------------2728;; Entry shape: {:value v :written ms :touched n :inserted n} where n is a29;; monotonic counter shared by the whole cache. :touched orders LRU recency30;; (bumped on put and on every touching get); :inserted orders FIFO (bumped31;; on put only, so gets never affect FIFO order).3233(define (entry-expired? entry ttl-ms clock-fn)34(and ttl-ms (>= (- (clock-fn) (get entry :written)) ttl-ms)))3536;; Victim selection scans every entry for the minimum counter. O(n) per37;; eviction is fine at the sizes this package targets (hundreds to a few38;; 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 more40;; to maintain than it saves.41(define (victim-key entries slot)42(first43(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)48best)))49nil50(map/entries entries))))5152(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 to58time-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(cond81((nil? entry)82(set! misses (+ misses 1))83nil)84((expired? entry)85(set! entries (dissoc entries k))86(set! evictions (+ evictions 1))87(set! misses (+ misses 1))88nil)89(else90(set! counter (+ counter 1))91(set! entries (assoc entries k (assoc entry :touched counter)))92(set! hits (+ hits 1))93entry))))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 v102:written (clock-fn)103:touched counter104:inserted counter}))105nil)106(fn (msg . args)107(cond108((= msg :lookup!) (lookup! (first args)))109((= msg :contains?)110;; Non-touching and non-counting: answers expiry-aware presence111;; 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 {})121nil)122((= msg :stats)123{:hits hits :misses misses :evictions evictions :size (count entries)})124(else125(error (format "sema-cache: unknown message ~a" msg)))))))126127;; ---------------------------------------------------------------------128;; Public operations (work on any cache handle)129;; ---------------------------------------------------------------------130131(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 an134expired entry — counts toward :misses. nil values are cacheable, so a nil135return 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))))140141(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 too144(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)150v)151(get entry :value))))152153(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))158159(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))163164(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 tracks167capacity- and TTL-driven evictions only)."168(c :evict! k))169170(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!))174175(define (cache/stats c)176"Return {:hits n :misses n :evictions n :size n} for the cache."177(c :stats))178179;; ---------------------------------------------------------------------180;; Memoization181;; ---------------------------------------------------------------------182183(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 and186variadic functions work; (m 1 2) and (m 2 1) are distinct keys. Accepts the187same options map as cache/new, plus :cache — a pre-built handle to use188instead, 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))))))193194;; ---------------------------------------------------------------------195;; Persistent kv-backed cache196;; ---------------------------------------------------------------------197198;; kv rows are {:value v :written ms}; TTL is enforced by comparing the199;; stored :written timestamp against :clock-fn on every access.200201(define (kv-key! k)202(if (string? k)203k204(error (format "cache/kv-cache: keys must be strings — got ~a" k))))205206(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 become210strings, string map keys come back as keywords, NaN/Infinity floats become211nil — 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, so214capacity eviction belongs in an in-memory cache/new, not here. Returns a215handle usable with every cache/* function; the :hits/:misses/:evictions216counters 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(cond229((nil? row)230(set! misses (+ misses 1))231nil)232((expired? row)233(kv/delete name k)234(set! evictions (+ evictions 1))235(set! misses (+ misses 1))236nil)237(else238(set! hits (+ hits 1))239row))))240(fn (msg . args)241(cond242((= 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)})249nil)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))253nil)254((= msg :stats)255{:hits hits :misses misses :evictions evictions256:size (length (kv/keys name))})257(else258(error (format "sema-cache: unknown message ~a" msg))))))))