cache.bend

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