README
cache
Caching for SSPUR services, in three parts:
- an immutable LRU cache value,
Cache[K, V], with per-entry time to live, an optional cost bound, statistics, eviction callbacks (the evicted entries are returned) and get_or_compute, for one thread of work: a batch job, a worker loop, a single request; Shared, a cache in SQLite that the concurrent handlers of http.serve and several processes share, with time to live, LRU eviction at a bound, statistics, and fetch, a get-or-compute with single-flight: of the callers that miss one key at the same time, one computes and the others wait for its result, with leases so a crashed computer doesn't block anyone;- HTTP caching after RFC 9110 and RFC 9111: entity tags (strong and weak, computed from bodies), HTTP dates in all three formats, conditional requests evaluated in the RFC's order (304 Not Modified and 412 Precondition Failed with the right fields), Cache-Control building and parsing, Vary, Age and freshness, and
conditional_get, a handler wrapper.
Install
$ sspur add cache
Example
use cache.{Cache}
fn square(n: Int) -> Int
= n * n
fn page(req: Request) -> Response
= cache.with_cache_control(http.html(200, "<h1>Docs</h1>"), cache.revalidate())
fn main() -> Unit ! log, db, fail[DbErr], time, rand, div
= do
var c: Cache[Int, Int] = cache.lru(2)
for n in [3, 4, 3, 5, 4]
(v, next) = cache.get_or_compute(c, n, 0, square)
c := next
log("{n}^2 = {v}")
log("keys {cache.keys(c)}, {cache.stats(c)}")
s = cache.shared(db.open(":memory:"), "pages", 1000)
a = cache.fetch(s, "report", 60000, cache.flight(), () => "expensive report")
b = cache.fetch(s, "report", 60000, cache.flight(), () => "computed again")
log("{a} / {b} / {cache.shared_stats(s)}")
req = Request{method: "GET", url: "/docs", headers: [], body: "", timeout_ms: 0, retries: 0, redirects: 0}
first = cache.conditional_get(false, page)(req)
tag = first.header("etag").or("")
again = cache.conditional_get(false, page)(req with headers := [("if-none-match", tag)])
log("{first.status} {tag} then {again.status} with {again.body.len} bytes")
log(cache.format_http_date(time_ms(784111777000)))
$ sspur run main.ssp
3^2 = 9
4^2 = 16
3^2 = 9
5^2 = 25
4^2 = 16
keys [4, 5], Stats{hits: 1, misses: 4, puts: 4, evictions: 2, expirations: 0}
expensive report / expensive report / Stats{hits: 1, misses: 1, puts: 1, evictions: 0, expirations: 0}
200 "nSW2vlLb9kmpJq8MMx2dmA" then 304 with 0 bytes
Sun, 06 Nov 1994 08:49:37 GMT
In a server, share the Shared value and build wrappers inside the handler (handlers may not share function values):
http.serve_with(http.server(8080), req => catch route(store, req)
| _ => http.text(500, "error"))
where route calls cache.fetch(store, ...) and cache.conditional_get(true, page)(req). tests/it/main.ssp is such a server; the integration tests start it in both tiers and check the 304s, the cached values and single-flight across 8 concurrent clients.
API
Immutable cache
Config, config(capacity): entry bound, max_cost, default ttl_ms, refresh_on_get.Cache[K, V], Entry[V], new(cfg), lru(capacity), ttl_lru(capacity, ttl_ms).get(c, k, now_ms): the value and the new cache (recency, statistics, expiry).peek, has: read without touching anything.put, put_ttl, insert(c, k, v, now_ms, ttl, cost) (returns the entries that left).remove, take, clear, touch, resize(c, capacity, max_cost), purge_expired.keys (most recent first), items, lru_key, mru_key, ttl_left, size, total_cost.get_or_compute(c, k, now_ms, f).Stats, stats(c), hit_rate(s).
Times are passed in (now_ms), so the cache is deterministic and needs no effects. Expired entries are dropped when read, when room is needed (before any live entry is evicted), or by purge_expired. Operations are O(log n).
Shared cache (SQLite)
Shared, shared(db, table, capacity), valid_table_name(s).shared_get, shared_peek, shared_put(s, key, value, now_ms, ttl_ms), shared_delete, shared_clear, shared_purge, shared_count, shared_stats.shared_get_as(s, key, now_ms, decode), shared_put_as(s, key, value, now_ms, ttl_ms) for JSON-encodable values.Flight, flight(): lease length, how long waiters wait, how often they look.fetch(s, key, ttl_ms, f, compute), fetch_as(..., compute, decode): get or compute with single-flight.shared_computing(s, key, now_ms): whether someone holds the lease.
Values are text: a library can't decode JSON into a type parameter (json.decode[T] needs a concrete type), so typed helpers take a decoder from the caller, such as x => json.decode[User](x).map(some).or(none). Every operation is a transaction; each read records its use for LRU, so reads are small writes.
HTTP caching
Etag, strong_etag, weak_etag, etag_str, parse_etag, etag_text_ok.etag_for(body) (strong, 128 bits of SHA-256), weak_etag_for(body).strong_match, weak_match (RFC 9110 8.8.3.2); Condition (AnyTag, Tags), parse_condition.format_http_date(t), parse_http_date(s, now) (IMF-fixdate, RFC 850, asctime).Validators, validators_of(r, now), Outcome (Proceed, NotModified, PreconditionFailed).evaluate(req, validators, exists, now): RFC 9110 13.2.2, for GET and for state-changing methods.not_modified(r), precondition_failed(v), conditional(req, r, now), with_etag(r, weak).conditional_get(weak, next): the wrapper.CacheControl, cache_control(), no_store(), revalidate(), public_for, private_for, immutable_for.render_cache_control, parse_cache_control, cache_control_header, cache_control_of(r), with_cache_control, parse_delta.vary_of, add_vary, set_header.freshness_lifetime(cc, shared, date, expires), current_age(...) (RFC 9111 4.2.3), is_fresh, age_header.
Notes
- Use weak ETags (
conditional_get(true, ...)) when the server's gzip field is on: the bytes sent then differ from the body, and a strong tag promises byte equality. conditional_get runs the handler first and then decides, which saves bandwidth, not work, and is only right for GET and HEAD. For PUT, PATCH and DELETE call evaluate before changing anything.- A malformed If-Match fails (412); malformed or repeated date conditions are ignored, as are If-Modified-Since dates in the future (RFC 9110 13.1).
- The shared cache's single-flight works across processes sharing the database file. A waiter waits at most
wait_ms and then computes the value itself, so a stuck computer slows callers down but never blocks them.
Out of scope
- A caching proxy (storing responses keyed by request, Vary matching, revalidation on behalf of clients); this package gives the building blocks.
- Range requests and If-Range.
- Distributed caches other than SQLite (Redis, memcached): sspur has no TCP client.
- Generic typed values in the shared cache without a caller-supplied decoder.
License
MIT, see LICENSE.
API
pub type Config = {capacity: Int where _ >= 1, max_cost: Int where _ >= 0, ttl_ms: Int where _ >= 0, refresh_on_get: Bool} derive Eq, Show
How a cache is bounded: at most capacity entries and, when max_cost is above 0, a total cost of at most max_cost (each entry's cost is given when it is put; 1 by default). ttl_ms above 0 is the default time to live; refresh_on_get restarts an entry's time to live when it is read (expire after access instead of after write).
pub type Stats = {hits: Int, misses: Int, puts: Int, evictions: Int, expirations: Int} derive Eq, Show, Json
Counters of what a cache did: reads that found a live entry and reads that didn't, writes, entries evicted for room, and entries dropped because they had expired.
pub type Entry[V] = {value: V, tick: Int, expires_ms: Opt[Int], ttl_ms: Int, cost: Int} derive Eq, Show
One cached value with its recency tick, its expiry time (none for never), its time to live and its cost.
pub type Cache[K, V] = {config: Config, entries: Map[K, Entry[V]], order: Set[(Int, K)], expiry: Set[(Int, Int, K)], tick: Int, cost: Int, stats: Stats} derive Eq, Show
An immutable LRU cache from K to V. Every operation returns the new cache; reads that change recency or statistics return it too. Operations are O(log n). The least recently used live entry is evicted first, after any expired ones.
fn config(capacity: Int where _ >= 1) -> Config
A configuration bounded by capacity entries only.
fn new[K, V](cfg: Config) -> Cache[K, V]
An empty cache with configuration cfg.
fn lru[K, V](capacity: Int where _ >= 1) -> Cache[K, V]
An empty LRU cache of at most capacity entries.
fn ttl_lru[K, V](capacity: Int where _ >= 1, ttl_ms: Int where _ >= 1) -> Cache[K, V]
An empty LRU cache of at most capacity entries that each live ttl_ms after they are written.
fn size[K, V](c: Cache[K, V]) -> Int
The number of entries, live or expired but not yet dropped.
fn total_cost[K, V](c: Cache[K, V]) -> Int
The total cost of the entries.
fn hit_rate(s: Stats) -> F64
The fraction of reads that hit, 0.0 before any read.
fn peek[K, V](c: Cache[K, V], k: K, now_ms: Int) -> Opt[V]
The value for k if it is there and live, without touching recency or statistics.
fn has[K, V](c: Cache[K, V], k: K, now_ms: Int) -> Bool
Whether k has a live entry.
fn get[K, V](c: Cache[K, V], k: K, now_ms: Int) -> (Opt[V], Cache[K, V])
Reads k: the value of a live entry, which becomes the most recently used (and with refresh_on_get gets a new expiry), counted as a hit; otherwise none, counted as a miss, and an expired entry is dropped.
fn touch[K, V](c: Cache[K, V], k: K, now_ms: Int) -> Cache[K, V]
Marks k as just used and restarts its time to live, without reading it (and without counting a hit). Missing or expired keys are left alone.
fn put[K, V](c: Cache[K, V], k: K, v: V, now_ms: Int) -> Cache[K, V]
Writes k with the default time to live and a cost of 1, evicting what must go.
fn put_ttl[K, V](c: Cache[K, V], k: K, v: V, now_ms: Int, ttl_ms: Int where _ >= 1) -> Cache[K, V]
Writes k to live ttl_ms milliseconds.
fn insert[K, V](c: Cache[K, V], k: K, v: V, now_ms: Int, ttl_ms: Opt[Int], cost: Int where _ >= 0) -> (Cache[K, V], List[(K, V)])
Writes k with a time to live (none: it never expires, whatever the default) and a cost, and returns the entries that left to make room or because they had expired, so the caller can release them. An entry that costs more than max_cost is not stored, and an older entry for k is removed.
fn purge_expired[K, V](c: Cache[K, V], now_ms: Int) -> (Cache[K, V], List[(K, V)])
Drops every entry that has expired by now_ms; returns the cache and the dropped entries.
fn remove[K, V](c: Cache[K, V], k: K) -> Cache[K, V]
Removes k (not counted as an eviction).
fn take[K, V](c: Cache[K, V], k: K, now_ms: Int) -> (Opt[V], Cache[K, V])
Removes k and returns its value if it was live.
fn clear[K, V](c: Cache[K, V]) -> Cache[K, V]
Removes every entry, keeping the configuration and the statistics.
fn resize[K, V](c: Cache[K, V], capacity: Int where _ >= 1, max_cost: Int where _ >= 0) -> (Cache[K, V], List[(K, V)])
Changes the bounds, evicting least recently used entries until the cache fits; returns the evicted entries too.
fn keys[K, V](c: Cache[K, V]) -> List[K]
The keys, most recently used first (expired ones not yet dropped included).
fn items[K, V](c: Cache[K, V], now_ms: Int) -> List[(K, V)]
The live entries at now_ms, most recently used first.
fn lru_key[K, V](c: Cache[K, V]) -> Opt[K]
The key that would be evicted next (the least recently used).
fn mru_key[K, V](c: Cache[K, V]) -> Opt[K]
The most recently used key.
fn ttl_left[K, V](c: Cache[K, V], k: K, now_ms: Int) -> Opt[Int]
The milliseconds k has left to live: none if it is missing, expired or never expires.
fn get_or_compute[K, V, e](c: Cache[K, V], k: K, now_ms: Int, f: K -> V ! e) -> (V, Cache[K, V]) ! e
The value for k, computed by f and stored when it is missing or expired.
fn stats[K, V](c: Cache[K, V]) -> Stats
pub type Shared = {db: Db, table: Str, capacity: Int} derive Eq, Show
A cache of text values in a SQLite table, shared by the concurrent handlers of a server (the Db is shared; a ":memory:" database is one connection) and by processes that open the same file. Every operation is a transaction, so reads and writes from anywhere stay consistent. It keeps at most capacity entries, evicting expired ones first and then the least recently used (each read records its use, so a read is a small write). Values are Str: a library can't decode JSON into a type parameter, so store json.encode(x) and decode on the way out (shared_get_as and shared_put_as do it with a decoder you pass). Statistics are kept in the database too.
pub type Flight = {lease_ms: Int where _ >= 1, wait_ms: Int where _ >= 0, poll_ms: Int where _ >= 1} derive Eq, Show
How fetch waits for another caller computing the same key: the lease a computer holds (when it crashes or raises, others take over after it), how long a waiter waits before computing the value itself, and how often it looks.
fn valid_table_name(s: Str) -> Bool
Whether s can name the cache's tables: a letter or underscore, then letters, digits and underscores, at most 50 characters (the tables get suffixes).
fn shared(c: Db, table: Str where valid_table_name(_), capacity: Int where _ >= 1) -> Shared ! db, fail[DbErr]
Opens the cache table in c with room for capacity entries, creating its tables when missing (table, table_meta for the statistics and table_leases for single-flight).
fn flight() -> Flight
The default single-flight settings: 30 s leases, waiters wait up to 30 s, polling every 10 ms.
fn shared_get(s: Shared, key: Str, now_ms: Int) -> Opt[Str] ! db, fail[DbErr]
Reads key: its value when it is there and live (now the most recently used), counted as a hit; otherwise none, counted as a miss (an expired entry is deleted).
fn shared_peek(s: Shared, key: Str, now_ms: Int) -> Opt[Str] ! db, fail[DbErr]
The value of key if it is live, reading only: no recency, no statistics.
fn shared_put(s: Shared, key: Str, value: Str, now_ms: Int, ttl_ms: Int where _ >= 0) -> Int ! db, fail[DbErr]
Writes key to live ttl_ms milliseconds (0: until evicted); returns how many entries left to make room (expired ones first, then the least recently used).
fn shared_delete(s: Shared, key: Str) -> Bool ! db, fail[DbErr]
Deletes key: whether it was there.
fn shared_clear(s: Shared) -> Int ! db, fail[DbErr]
Deletes every entry; returns how many there were. Statistics are kept.
fn shared_purge(s: Shared, now_ms: Int) -> Int ! db, fail[DbErr]
Deletes the entries that have expired by now_ms; returns how many.
fn shared_count(s: Shared) -> Int ! db, fail[DbErr]
The number of entries, live or expired but not yet deleted.
fn shared_stats(s: Shared) -> Stats ! db, fail[DbErr]
The statistics of the shared cache, summed over every process that uses it.
fn shared_get_as[T](s: Shared, key: Str, now_ms: Int, decode: Str -> Opt[T]) -> Opt[T] ! db, fail[DbErr]
Reads key and decodes it with decode (such as x => json.decode[User](x).map(some).or(none)); a value that doesn't decode counts as missing.
fn shared_put_as[T: Json](s: Shared, key: Str, value: T, now_ms: Int, ttl_ms: Int where _ >= 0) -> Int ! db, fail[DbErr]
Writes value as its JSON.
fn shared_computing(s: Shared, key: Str, now_ms: Int) -> Bool ! db, fail[DbErr]
Whether someone holds a live lease on key, computing it.
fn fetch[e](s: Shared, key: Str, ttl_ms: Int, f: Flight, compute: () -> Str ! e) -> Str ! db, fail[DbErr], time, rand, div, e
The value of key, computed by compute (and stored for ttl_ms, 0 or less for no expiry) when it is missing, with single-flight: of the callers that miss at the same time, in this process or any other sharing the database, one takes a lease and computes while the others wait and get its result. A waiter that waits longer than f.wait_ms computes the value itself. When a computer crashes or compute raises, its lease runs out after f.lease_ms and the next caller takes over.
fn fetch_as[T: Json, e](s: Shared, key: Str, ttl_ms: Int, f: Flight, compute: () -> T ! e, decode: Str -> Opt[T]) -> T ! db, fail[DbErr], time, rand, div, e
fetch for a JSON-encodable type: computes a T, stores its JSON, and decodes a cached value with decode; a cached value that doesn't decode is computed again.
pub type Etag = {weak: Bool, tag: Str} derive Eq, Show
An entity tag (RFC 9110 8.8.3): its opaque text, without quotes, and whether it is weak.
fn etag_text_ok(s: Str) -> Bool
Whether s can be the text of an entity tag: etagc characters only (no spaces, quotes or control characters).
fn strong_etag(tag: Str where etag_text_ok(_)) -> Etag
A strong entity tag with text tag.
fn weak_etag(tag: Str where etag_text_ok(_)) -> Etag
A weak entity tag with text tag.
fn etag_str(e: Etag) -> Str
The field value of an entity tag: "tag" or W/"tag".
fn parse_etag(s: Str) -> Opt[Etag]
Parses one entity tag, "..." or W/"...".
fn etag_for(body: Str) -> Etag
A strong entity tag for a body: 128 bits of its SHA-256 in base64url, so the same body always has the same tag. Use it when the bytes sent are the body itself.
fn weak_etag_for(body: Str) -> Etag
A weak entity tag for a body, for responses the server may compress or otherwise transform (the gzip server field), whose bytes then differ from the body.
fn strong_match(a: Etag, b: Etag) -> Bool
Strong comparison (RFC 9110 8.8.3.2): both strong and the same text.
fn weak_match(a: Etag, b: Etag) -> Bool
Weak comparison: the same text, whatever the weakness.
pub type Condition = AnyTag | Tags{tags: List[Etag]} derive Eq, Show
The value of an If-Match or If-None-Match field: * or a list of entity tags.
fn parse_condition(s: Str) -> Opt[Condition]
Parses an If-Match or If-None-Match value; none when it is malformed (a * mixed with tags, or an invalid tag) or empty.
fn format_http_date(t: Time) -> Str
An HTTP date in the preferred IMF-fixdate form, Sun, 06 Nov 1994 08:49:37 GMT (RFC 9110 5.6.7). Milliseconds are dropped.
fn parse_http_date(s: Str, now: Time) -> Opt[Time]
Parses an HTTP date in any of the three forms recipients must accept: IMF-fixdate, the obsolete RFC 850 form (a two-digit year, read relative to now) and asctime. Names are case-sensitive and the time zone must be GMT, as the RFC says; none for anything else.
pub type Validators = {etag: Opt[Etag], last_modified: Opt[Time]} derive Eq, Show
What the server knows about the current representation: its entity tag and its modification time, either of which may be missing.
pub type Outcome = Proceed | NotModified | PreconditionFailed derive Eq, Show
The result of evaluating a request's preconditions: go on, answer 304 Not Modified, or answer 412 Precondition Failed.
fn evaluate(req: Request, v: Validators, exists: Bool, now: Time) -> Outcome
Evaluates the preconditions of req against the current representation (exists is whether there is one) in the order of RFC 9110 13.2.2: If-Match (strong comparison; a malformed value fails), else If-Unmodified-Since; then If-None-Match (weak comparison: 304 for GET and HEAD, 412 otherwise), else If-Modified-Since for GET and HEAD. Dates compare at whole seconds; malformed or repeated dates, and If-Modified-Since dates after now, are ignored. Call it before changing anything for PUT, PATCH and DELETE.
fn validators_of(r: Response, now: Time) -> Validators
The validators a response carries: its ETag and Last-Modified fields.
fn not_modified(r: Response) -> Response
The 304 Not Modified answer for a 200 response (RFC 9110 15.4.5): no body and no representation metadata (Content-*), keeping ETag, Cache-Control, Expires, Vary, Date, Content-Location and the other fields; Last-Modified only when there is no ETag.
fn precondition_failed(v: Validators) -> Response
The 412 Precondition Failed answer, with the current entity tag when there is one.
fn conditional(req: Request, r: Response, now: Time) -> Response
Applies conditional GET to a response already made: for a GET or HEAD answered 200, the request's preconditions are evaluated against the response's own ETag and Last-Modified, giving 304 or 412 where they say so. Other requests and statuses pass unchanged.
fn with_etag(r: Response, weak: Bool) -> Response
Adds an ETag computed from the body (weak with weak) to a 200 response that has none.
fn conditional_get[e](weak: Bool, next: Request -> Response ! e) -> Request -> Response ! e, time
Wraps a handler with conditional GET: 200 answers to GET and HEAD get an ETag from their body (weak with weak, which suits the server's gzip field) unless they have one, and the request's If-None-Match, If-Modified-Since, If-Match and If-Unmodified-Since are applied to them. The handler still runs (this saves bandwidth, not work). Build it inside the handler lambda.
pub type CacheControl = {max_age: Opt[Int], s_maxage: Opt[Int], no_cache: Bool, no_cache_fields: List[Str], no_store: Bool, private: Bool, private_fields: List[Str], public: Bool, must_revalidate: Bool, proxy_revalidate: Bool, must_understand: Bool, no_transform: Bool, immutable: Bool, stale_while_revalidate: Opt[Int], stale_if_error: Opt[Int], max_stale: Opt[Int], min_fresh: Opt[Int], only_if_cached: Bool, extensions: List[(Str, Str)]} derive Eq, Show
The directives of a Cache-Control field (RFC 9111 5.2), for responses and requests. Durations are in seconds; max_stale without a value is 2147483648. Unknown directives are kept in extensions with their values ("" for none).
fn cache_control() -> CacheControl
fn no_store() -> CacheControl
no-store: for anything personal or secret.
fn revalidate() -> CacheControl
no-cache: caches may store it but must revalidate every time (pair it with an ETag).
fn public_for(secs: Int where _ >= 0) -> CacheControl
fn private_for(secs: Int where _ >= 0) -> CacheControl
private, max-age=secs: only the user's own browser may keep it.
fn immutable_for(secs: Int where _ >= 0) -> CacheControl
public, max-age=secs, immutable: for assets whose URL changes with their content.
fn render_cache_control(cc: CacheControl) -> Str
The field value of a Cache-Control, directives in a fixed order.
fn with_cache_control(r: Response, cc: CacheControl) -> Response
Sets the Cache-Control field of a response, replacing any.
fn parse_delta(s: Str) -> Opt[Int]
A delta-seconds value: digits only, clamped to 2^31 as RFC 9111 1.2.2 says.
fn parse_cache_control(s: Str) -> CacheControl
Parses a Cache-Control value: directive names are case-insensitive, values tokens or quoted strings; of a repeated directive the first counts, and a malformed duration is ignored.
fn cache_control_of(r: Response) -> CacheControl
The Cache-Control of a response, every field line together.
fn vary_of(r: Response) -> List[Str]
The field names a response varies on (the Vary field lines together).
fn add_vary(r: Response, names: List[Str]) -> Response
Adds field names to the response's Vary, once each (case-insensitively), in one field line; * absorbs everything.
fn freshness_lifetime(cc: CacheControl, shared: Bool, date: Opt[Time], expires: Opt[Str]) -> Opt[Int]
The freshness lifetime of a response in seconds (RFC 9111 4.2.1): s-maxage for a shared cache, else max-age, else Expires minus Date (an invalid Expires means already stale); none when the response says nothing (a heuristic lifetime is the cache's choice).
fn current_age(age_value: Int where _ >= 0, date: Opt[Time], request_time: Time, response_time: Time, now: Time) -> Int
The current age of a stored response in seconds (RFC 9111 4.2.3), from its Age value, its Date, when the request was sent, when the response arrived, and now.
fn is_fresh(lifetime: Int, age: Int) -> Bool
Whether a response of lifetime seconds and age seconds is still fresh.