Debian Codegraph @

lib/data/cache.scm

raw
1 ;;;
2 ;;; data.cache - Implementation of various cache strategies
3 ;;;
4 ;;; Copyright (c) 2015-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 ;; This class takes care of various cache algorithms.
35 ;; The cache works like a dictionary that you can associate value
36 ;; to a key. The entry may disappear silently, when it is expired
37 ;; according to the cache policy. This module is inspired by Clojure's
38 ;; core.cache, but note that the API spec is different from Clojure's.
39 ;;
40 ;; User-side API
41 ;;
42 ;; (make-***-cache [args ...] :key storage comparator ...) procedure
43 ;; Arguments varies depending on the alrogithm.
44 ;;
45 ;; (cache-lookup! cache key [default]) => value procedure
46 ;; (cache-through! cache key value-fn) => value procedure
47 ;; (cache-evict! cache key) => void method
48 ;; (cache-clear! cache) => void method
49 ;; (cache-write! cache key value) => void method
50 ;;
51 ;; (cache-storage cache) => dictionary procedure
52 ;; (cache-comparator cache) => comparator procedure
53 ;;
54 ;; Implementor-side API
55 ;;
56 ;; An implementation of cache algorithm must provide at least the
57 ;; following two methods:
58 ;;
59 ;; (cache-check! cache key) => Maybe (key . value)
60 ;; Check if key has a value in cache. If not, returns #f.
61 ;; If it does, returns a cons of the key and the value.
62 ;;
63 ;; (cache-register! cache key value) => (key . value)
64 ;; Called when cache doesn't have an entry for the key, in order
65 ;; to insert the value with the key.
66 ;; This inserts the key-value pair into the cache, and returns
67 ;; cons of them.
68 ;;
69 ;; The initialize method must take care of set up the internal state.
70 ;; It should also handle the case when the existing dictionary is given.
71 ;;
72 ;; The default method of cache-evict! and cache-clear! only takes
73 ;; care of the storage. If the algorithm needs to modify other internal
74 ;; states, it should override those methods.
75 ;;
76 ;; The default method of cache-write! is evict! + register!. In most
77 ;; cases there exists a better way.
78
79 (define-module data.cache
80 (use gauche.collection)
81 (use gauche.dictionary)
82 (use data.queue)
83 (use data.heap)
84 (use srfi.114)
85 (export <cache>
86 ;; Protocol
87 cache-storage cache-comparator
88 cache-lookup! cache-through!
89 cache-check! cache-register! cache-write!
90 cache-evict! cache-clear!
91
92 ;; Some auxiliary procedures for implementors
93 cache-populate-queue! cache-compact-queue!
94 cache-renumber-entries!
95
96 ;; Concrete implementations
97 make-fifo-cache
98 make-ttl-cache
99 make-ttlr-cache
100 make-lru-cache
101 make-counting-cache cache-stats))
102 (select-module data.cache)
103
104 ;; storage and comparator
105
106 (define-class <cache> ()
107 (;; private. must be treated read-only.
108 [storage :init-keyword :storage :init-value #f]
109 [comparator :init-keyword :comparator :init-value #f]
110 ))
111
112 (define-inline (cache-storage cache) (slot-ref cache 'storage))
113 (define-inline (cache-comparator cache) (slot-ref cache 'comparator))
114
115 (define-method initialize ((c <cache>) initargs)
116 (next-method)
117 (if (cache-storage c)
118 (unless (cache-comparator c)
119 (slot-set! c 'comparator (dict-comparator (cache-storage c))))
120 (begin
121 (unless (cache-comparator c)
122 (slot-set! c 'comparator default-comparator))
123 (slot-set! c 'storage (make-hash-table (cache-comparator c))))))
124
125 ;;;
126 ;;; Cache external API
127 ;;;
128
129 (define (cache-lookup! cache key . maybe-default)
130 (if-let1 kv (cache-check! cache key)
131 (cdr kv)
132 (if (pair? maybe-default)
133 (car maybe-default)
134 (errorf "cache ~s doesn't have an entry for key ~s" cache key))))
135
136 (define (cache-through! cache key value-fn)
137 (cdr (or (cache-check! cache key)
138 (cache-register! cache key (value-fn key)))))
139
140 (define-method cache-evict! ((cache <cache>) key)
141 (dict-delete! (cache-storage cache) key))
142
143 (define-method cache-clear! ((cache <cache>))
144 (dict-clear! (cache-storage cache)))
145
146 (define-method cache-write! ((cache <cache>) key value)
147 (cache-evict! cache key)
148 (cache-register! cache key value))
149
150 ;; Some common routines
151 ;; Most of cache implementations uses a queue as an auxiliary struct.
152 ;; They keep <key> -> (<n> . <value>) in the storage, and
153 ;; pushd (<key> . <n>) into the queue, where <n> is a number and
154 ;; monotonically increasing within the queue. There may be multiple
155 ;; entries with the same <key> in the queue.
156 ;; Although the meaning of <n> depends on the algorithm, some
157 ;; operations can be common.
158
159 ;; Queue must be an empty queue. Fills queue according to the contents of
160 ;; storage. This is called from initialize, in order to set up a cache
161 ;; with existing storage. Returns maximum <n>.
162 (define (cache-populate-queue! queue storage)
163 (let1 entries (dict->alist storage) ; entries :: [(key n . val)]
164 (fold (^[entry maxn]
165 (enqueue! queue (cons (car entry) (cadr entry))) ; (key . n)
166 (if (> (cadr entry) maxn)
167 (cadr entry)
168 maxn))
169 0
170 (sort entries < cadr))))
171
172 ;; When the algorithm increments <n> monotonically, it can eventually fell
173 ;; to bignum, but we don't want that. This routine renumbers entries,
174 ;; while removing duplicate keys in the queue.
175 (define (cache-renumber-entries! queue storage)
176 (let1 seen (make-hash-table (dict-comparator storage))
177 (define cnt (- (size-of storage) 1))
178 (dolist [kn (sort (dequeue-all! queue) > cdr)]
179 (unless (hash-table-exists? seen (car kn))
180 (hash-table-put! seen (car kn) #t)
181 (queue-push! queue (cons (car kn) cnt))
182 (dict-update! storage (car kn) (^[nv] (cons cnt (cdr nv))))
183 (dec! cnt)))))
184
185 ;; We allow duplicate keys in the queue, but we don't want the queue to
186 ;; get too long (e.g. Repeatedly hitting the same key in LRU cache would
187 ;; quickly pile up entries in the queue). So occasionally we want to
188 ;; compact the queue, by removing the duplicate entries.
189 ;; This routine is quite similar to cache-renumber-entries! but we don't
190 ;; change <n>'s, so we don't need to mutate the storage.
191 (define (cache-compact-queue! queue storage)
192 (let1 seen (make-hash-table (dict-comparator storage))
193 (dolist [kn (sort (dequeue-all! queue) > cdr)]
194 (unless (hash-table-exists? seen (car kn))
195 (hash-table-put! seen (car kn) #t)
196 (queue-push! queue kn)))))
197
198 ;;;
199 ;;; Cache implementations
200 ;;;
201
202 ;; FIFO Cache
203 ;; - To recover the order from dict, we keep (<n> . <value>) in the storage.
204 ;; <n> being increasing order of nonnegative integers.
205 ;; - The queue holds (<key> . <n>)
206 ;; - We don't want <n> to become bignums in long-running process, so
207 ;; when we see <n> gets too big, we renumber entries.
208
209 (define-class <fifo-cache> (<cache>)
210 ([capacity :init-keyword :capacity]
211 ;; private
212 [queue :init-form (make-queue)]
213 [counter :init-value 0]))
214
215 (define (make-fifo-cache capacity :key (storage #f) (comparator #f))
216 (make <fifo-cache> :storage storage :comparator comparator
217 :capacity capacity))
218
219 (define-method initialize ((c <fifo-cache>) initargs)
220 (next-method)
221 (set! (~ c'counter)
222 (+ 1 (cache-populate-queue! (~ c'queue) (cache-storage c)))))
223
224 (define-method cache-check! ((cache <fifo-cache>) key)
225 (and-let1 nv (dict-get (cache-storage cache) key #f)
226 (cons key (cdr nv))))
227
228 (define (%fifo-add! cache key value)
229 (let ([dict (cache-storage cache)]
230 [queue (~ cache'queue)])
231 (when (>= (size-of dict) (~ cache'capacity))
232 ;; NB: The queue may have multiple entries for the key. We only
233 ;; concern the newest entry, so we loop if the queue head is old.
234 ;; The queue should never be empty during this loop, because size of
235 ;; queue >= size of dict.
236 (let loop ([kn (dequeue! queue)])
237 (let1 nv (dict-get dict (car kn) #f)
238 (if (and (pair? nv) (= (cdr kn) (car nv)))
239 (dict-delete! dict (car kn))
240 (loop (dequeue! queue))))))
241 (dict-put! dict key (cons (~ cache'counter) value))
242 (%fifo-touch! cache queue key)))
243
244 (define (%fifo-touch! cache queue key)
245 (let ([n (~ cache'counter)]
246 [storage (cache-storage cache)])
247 (enqueue! queue (cons key n))
248 (cond [(= n (greatest-fixnum))
249 (cache-renumber-entries! queue storage)
250 (set! (~ cache'counter) (size-of storage))]
251 [(> (queue-length queue) (* 3 (size-of storage)))
252 (cache-compact-queue! queue storage)
253 (set! (~ cache'counter) (+ n 1))]
254 [else
255 (set! (~ cache'counter) (+ n 1))])))
256
257 (define-method cache-register! ((cache <fifo-cache>) key value)
258 (%fifo-add! cache key value)
259 (cons key value))
260
261 (define-method cache-write! ((cache <fifo-cache>) key value)
262 (%fifo-add! cache key value))
263
264 ;; We don't provide cache-evict!. Leaving stale entry in the queue
265 ;; doesn't do harm.
266
267 (define-method cache-clear! ((cache <fifo-cache>))
268 (dict-clear! (cache-storage cache))
269 (dequeue-all! (~ cache'queue))
270 (undefined))
271
272 ;; LRU Cache
273 ;; - LRU cache is actually a variation of FIFO cache, except that
274 ;; we touch the entry on read operaion as well.
275 (define-class <lru-cache> (<fifo-cache>) ())
276
277 (define (make-lru-cache capacity :key (storage #f) (comparator #f))
278 (make <lru-cache> :storage storage :comparator comparator
279 :capacity capacity))
280
281 (define-method cache-check! ((cache <lru-cache>) key)
282 (and-let* ([nv (dict-get (cache-storage cache) key #f)]
283 [nv2 (cons (~ cache'counter) (cdr nv))])
284 (dict-put! (cache-storage cache) key nv2)
285 (%fifo-touch! cache (~ cache'queue) key)
286 (cons key (cdr nv))))
287
288 ;; TTL Cache
289 ;; - Timestamps is a heap with (<timestamp> . <key>). There can
290 ;; be multiple entries with the same <key>.
291 ;; - The storage holds (<timestamp> . <value>).
292
293 (define-class <ttl-cache> (<cache>)
294 ([ttl :init-keyword :ttl] ; time to live, in seconds
295 [timestamper :init-keyword :timestamper] ; a thunk to return a timestamp
296 [timestamps :init-form (make-queue)])) ; (<key> . <timestamp>)
297
298 (define (make-ttl-cache ttl :key (storage #f) (comparator #f)
299 (timestamper sys-time))
300 (make <ttl-cache> :storage storage :comparator comparator
301 :ttl ttl :timestamper timestamper))
302
303 (define-method initialize ((c <ttl-cache>) initargs)
304 (next-method)
305 (cache-populate-queue! (~ c'timestamps) (cache-storage c)))
306
307 (define (%ttl-sweep! c)
308 (let ([cutoff (- ((~ c'timestamper)) (~ c'ttl))]
309 [ts (~ c'timestamps)]
310 [tab (cache-storage c)])
311 (let loop ()
312 (and-let* ([kt (queue-front ts #f)]
313 [ (< (cdr kt) cutoff) ])
314 (dequeue! ts)
315 ;; The dict-get below may return #f, if there's more than one
316 ;; entry of the key in the heap with the same timestamp.
317 (and-let* ([tv (dict-get tab (car kt) #f)]
318 [ (<= (car tv) (cdr kt)) ])
319 (dict-delete! tab (car kt)))
320 (loop)))))
321
322 (define (%ttl-timestamp c) ((~ c'timestamper)))
323
324 (define-method cache-check! ((c <ttl-cache>) key)
325 (%ttl-sweep! c)
326 (and-let1 tv (dict-get (cache-storage c) key #f)
327 (cons key (cdr tv))))
328
329 (define-method cache-register! ((c <ttl-cache>) key val)
330 (let1 t (%ttl-timestamp c)
331 (dict-put! (cache-storage c) key (cons t val))
332 (enqueue! (~ c'timestamps) (cons key t)))
333 (cons key val))
334
335 (define-method cache-clear! ((c <ttl-cache>))
336 (dict-clear! (cache-storage c))
337 (dequeue-all! (~ c'timestamps)))
338
339 (define-method cache-write! ((c <ttl-cache>) key val)
340 (if-let1 tv (dict-get (cache-storage c) key #f)
341 (let1 t (%ttl-timestamp c)
342 (set! (car tv) t)
343 (set! (cdr tv) val)
344 (enqueue! (~ c'timestamps) (cons key t)))
345 (cache-register! c key val))
346 (undefined))
347
348 ;; TTLR Cache
349 ;; - TTL with refreshing. The timestamp of the entry is updated every
350 ;; time it is read. It's kind of combination of LRU + TTL.
351 ;; - Most methods are inherited from TTL cache. The only difference
352 ;; is cache-check!, in which we 'touch' the entry.
353 (define-class <ttlr-cache> (<ttl-cache>)
354 ())
355
356 (define (make-ttlr-cache ttl :key (storage #f) (comparator #f)
357 (timestamper sys-time))
358 (make <ttlr-cache> :storage storage :comparator comparator
359 :ttl ttl :timestamper timestamper))
360
361 (define-method cache-check! ((c <ttlr-cache>) key)
362 (%ttl-sweep! c)
363 (and-let* ([tv (dict-get (cache-storage c) key #f)]
364 [t (%ttl-timestamp c)])
365 (set! (car tv) t)
366 (enqueue! (~ c'timestamps) (cons key t))
367 (when (> (queue-length (~ c'timestamps)) (* 3 (size-of (cache-storage c))))
368 (cache-compact-queue! (~ c'timestamps) (cache-storage c)))
369 (cons key (cdr tv))))
370
371 ;; Counting cache
372 ;; - This is a wrapper cache to count cache misses/hits
373 ;; NB: counting cache's storage directly points to inner-cache's storage.
374 ;; We assume that any modification on the storage is done via inner-cache's
375 ;; method, so that it won't cause inconsistency.
376
377 (define-class <counting-cache> (<cache>)
378 ([inner-cache :init-keyword :inner-cache]
379 [hits :init-value 0]
380 [misses :init-value 0]))
381
382 (define (make-counting-cache inner-cache)
383 (make <counting-cache>
384 :inner-cache inner-cache
385 :storage (cache-storage inner-cache)
386 :comparator (cache-comparator inner-cache)))
387
388 (define-method cache-check! ((cache <counting-cache>) key)
389 (rlet1 r (cache-check! (~ cache'inner-cache) key)
390 (if r
391 (inc! (~ cache'hits))
392 (inc! (~ cache'misses)))))
393
394 (define-method cache-register! ((cache <counting-cache>) key value)
395 (cache-register! (~ cache'inner-cache) key value))
396
397 (define-method cache-write! ((cache <counting-cache>) key value)
398 (cache-write! (~ cache'inner-cache) key value))
399
400 (define-method cache-evict! ((cache <counting-cache>) key)
401 (cache-evict! (~ cache'inner-cache) key))
402
403 (define-method cache-clear! ((cache <counting-cache>))
404 (cache-clear! (~ cache'inner-cache)))
405
406 (define-method cache-stats ((cache <counting-cache>))
407 `(:hits ,(~ cache'hits) :misses ,(~ cache'misses)))