cache.bend
bend-kit-cache@0.1.0.0 · 163 lines · 0 definitions
1# Cache validity: expiry, negative results, invalidation, and generation-safe fetch completion. Source: https://github.com/paymog/bend-kit/tree/main/cache
2import Base
3import bend-kit-collections@0.1.2.0/omap.bend as OMap
4
5# How long a result stays fresh, in the units of the caller's clock.
6type Policy is Data:
7 Policy{ttl: Nat, negative_ttl: Nat}
8
9# What one fetch found upstream: a value at an upstream version, or nothing.
10type Found<-V: Data> is Data:
11 Found{version: Nat, value: V}
12 Missing{}
13
14# A cached result. It serves a read at `now` only while now < expires.
15type Entry<-V: Data> is Data:
16 Hit{version: Nat, value: V, expires: Nat}
17 Miss{expires: Nat}
18
19# The state of one key. Fetches take the generations floor, floor+1, ..., next-1.
20# A completion lands only when floor <= its generation < next. It then raises
21# floor past its generation, so no older fetch can land after it.
22type Slot<-V: Data> is Data:
23 Slot{next: Nat, floor: Nat, entry: Maybe<&2, Entry<V>>}
24
25# One fetch in flight: its key, its generation, and the clock when it started.
26# It is affine, so it completes at most once.
27type Ticket is Type:
28 Ticket{key: String, gen: Nat, at: Nat}
29
30type Cache<-V: Data> is Data:
31 Cache{policy: Policy, slots: OMap.OMap<String, Slot<V>>}
32
33# Slot
34# ----
35
36def Slot.new(-V: Data) -> Slot<V>:
37 Slot{0n, 0n, None{}}
38
39def Entry.expires(-V: Data, e: Entry<V>) -> Nat:
40 match e:
41 case Hit{v, x, t}:
42 t
43 case Miss{t}:
44 t
45
46# The entry for a result fetched at `at`. Its age counts from the fetch start.
47def Entry.of(-V: Data, r: Found<V>, p: Policy, at: Nat) -> Entry<V>:
48 match r:
49 case Found{v, x}:
50 Policy{ttl, neg} = p
51 Hit{v, x, Nat.add(at, ttl)}
52 case Missing{}:
53 Policy{ttl, neg} = p
54 Miss{Nat.add(at, neg)}
55
56def Slot.serve(-V: Data, fresh: Bool, e: Entry<V>) -> Maybe<&2, Entry<V>>:
57 match fresh:
58 case True{}:
59 Some{e}
60 case False{}:
61 None{}
62
63def Slot.lookup(-V: Data, m: Maybe<&2, Entry<V>>, +now: Nat) -> Maybe<&2, Entry<V>>:
64 match m:
65 case None{}:
66 None{}
67 case Some{+e}:
68 Slot.serve(V, Nat.is_lt(now, Entry.expires(V, e)), e)
69
70# The fresh entry at `now`, or None when the caller must fetch.
71def Slot.read(-V: Data, s: Slot<V>, +now: Nat) -> Maybe<&2, Entry<V>>:
72 Slot{n, f, m} = s
73 Slot.lookup(V, m, now)
74
75# Takes the next generation for a new fetch.
76def Slot.start(-V: Data, s: Slot<V>) -> Nat & Slot<V>:
77 Slot{+n, f, m} = s
78 (n, Slot{1n+n, f, m})
79
80def Slot.complete.if(-V: Data, ok: Bool, n: Nat, f: Nat, m: Maybe<&2, Entry<V>>, g: Nat, e: Entry<V>) -> Slot<V>:
81 match ok:
82 case True{}:
83 Slot{n, 1n+g, Some{e}}
84 case False{}:
85 Slot{n, f, m}
86
87# Stores the result of fetch g, unless g is stale or was never issued.
88def Slot.complete(-V: Data, p: Policy, s: Slot<V>, +g: Nat, at: Nat, r: Found<V>) -> Slot<V>:
89 Slot{+n, +f, m} = s
90 Slot.complete.if(V, Nat.is_le(f, g) && Nat.is_lt(g, n), n, f, m, g, Entry.of(V, r, p, at))
91
92# Drops the entry and voids every fetch issued so far.
93def Slot.invalidate(-V: Data, s: Slot<V>) -> Slot<V>:
94 Slot{+n, f, m} = s
95 Slot{n, n, None{}}
96
97# Drops the entry. The generations stay, so no fetch that was stale before is accepted after.
98def Slot.evict(-V: Data, s: Slot<V>) -> Slot<V>:
99 Slot{n, f, m} = s
100 Slot{n, f, None{}}
101
102# Cache
103# -----
104
105def key.cmp.fin(c: Cmp, rest: Cmp) -> Cmp:
106 match c:
107 case LT{}:
108 LT{}
109 case EQ{}:
110 rest
111 case GT{}:
112 GT{}
113
114# Keys in code-point order. String.order rebuilds both strings on every call.
115def key.cmp(a: String, b: String) -> Cmp:
116 match a b:
117 case SNil{} SNil{}:
118 EQ{}
119 case SNil{} SCon{h, t}:
120 LT{}
121 case SCon{h, t} SNil{}:
122 GT{}
123 case SCon{Chr{+x}, s} SCon{Chr{+y}, t}:
124 key.cmp.fin(U32.cmp(x, y), key.cmp(s, t))
125
126def Cache.new(-V: Data, p: Policy) -> Cache<V>:
127 Cache{p, OMap.OMap.new(String, Slot<V>)}
128
129def Cache.slot(~V: Data, slots: OMap.OMap<String, Slot<V>>, +key: String) -> Slot<V>:
130 Maybe.default(&2, Slot<V>, OMap.OMap.get(~String, ~Slot<V>, ~key.cmp, slots, key), Slot.new(V))
131
132def Cache.put(~V: Data, p: Policy, slots: OMap.OMap<String, Slot<V>>, +key: String, +s: Slot<V>) -> Cache<V>:
133 Cache{p, OMap.OMap.put(~String, ~Slot<V>, ~key.cmp, slots, key, s)}
134
135# The fresh entry for key at `now`, or None when the caller must fetch.
136def Cache.read(~V: Data, c: Cache<V>, +key: String, +now: Nat) -> Maybe<&2, Entry<V>>:
137 Cache{p, slots} = c
138 Slot.read(V, Cache.slot(~V, slots, key), now)
139
140def Cache.start.fin(~V: Data, p: Policy, slots: OMap.OMap<String, Slot<V>>, +key: String, at: Nat, r: Nat & Slot<V>) -> Ticket & Cache<V>:
141 (g, s) = r
142 (Ticket{key, g, at}, Cache.put(~V, p, slots, key, s))
143
144# Starts a fetch of key at clock `at`. Fetch upstream, then pass the ticket to complete.
145def Cache.start(~V: Data, c: Cache<V>, +key: String, at: Nat) -> Ticket & Cache<V>:
146 Cache{p, +slots} = c
147 Cache.start.fin(~V, p, slots, key, at, Slot.start(V, Cache.slot(~V, slots, key)))
148
149# Stores what the ticket's fetch found. A stale ticket changes nothing.
150def Cache.complete(~V: Data, c: Cache<V>, t: Ticket, r: Found<V>) -> Cache<V>:
151 Cache{+p, +slots} = c
152 Ticket{+key, g, at} = t
153 Cache.put(~V, p, slots, key, Slot.complete(V, p, Cache.slot(~V, slots, key), g, at, r))
154
155# Drops key's entry and voids its fetches in flight.
156def Cache.invalidate(~V: Data, c: Cache<V>, +key: String) -> Cache<V>:
157 Cache{p, +slots} = c
158 Cache.put(~V, p, slots, key, Slot.invalidate(V, Cache.slot(~V, slots, key)))
159
160# Drops key's entry. Its generations stay, so stale fetches stay stale.
161def Cache.evict(~V: Data, c: Cache<V>, +key: String) -> Cache<V>:
162 Cache{p, +slots} = c
163 Cache.put(~V, p, slots, key, Slot.evict(V, Cache.slot(~V, slots, key)))