/// Rate buckets every instance shares, in PostgreSQL (ADR 0081): one row /// per key in a table of the app's (`Store`), the same token bucket as /// `resilience/rate_limit` (`per_minute` units a millisecond, a minute's /// worth at most, `rate_limit.cost` a request), timed by the database's /// clock so that instances' clocks never disagree. One atomic statement /// admits or refuses; a refusal reads how long until the next request is /// paid for. An error is the caller's to handle (`throttle` falls back to /// its own buckets). import postgres as pg import resilience/rate_limit.{type Admission, Admitted, Wait} import std/list import std/process.{type proc} import std/result import std/string @test import std/test.{assert_equal} /// Where the buckets are: a table and its key column. Both are SQL /// identifiers checked when the store is made, since they are part of the /// statement's text (only values can be its parameters). pub opaque type Store { Store(table: String, key_column: String) } /// The table `rates`, keyed by `key`. pub fn rates :: -> Store { Store("rates", "key") } /// The table `table`, keyed by `key_column`: lowercase letters, digits and /// `_`, starting with a letter or `_`, 63 bytes at most. pub fn store :: table: String key_column: String -> Result { if identifier table && identifier key_column { Ok(Store(table, key_column)) } else { Error( "a rate table and its key column are plain SQL names: {table}, {key_column}" ) } } fn identifier :: name: String -> Bool { let chars = string.chars name match chars { [] -> False , [first, ..] -> string.length name <= 63 && (lower first || first == "_") && list.all chars fn c { lower c || digit c || c == "_" } } } fn lower :: c: String -> Bool { c >= "a" && c <= "z" } fn digit :: c: String -> Bool { c >= "0" && c <= "9" } /// The statement that makes the store's table, for the app's schema. pub fn create_table :: store: Store -> String { "create table if not exists {store.table} ({store.key_column} text primary key, units bigint not null, at_ms bigint not null)" } /// One request under `key`, against the shared bucket. pub fn admission :: pool: pg.Pool store: Store per_minute: Int key: String -> Result / { if per_minute <= 0 { Ok(Admitted) } else { let full = per_minute * rate_limit.cost () let cost = rate_limit.cost () use taken <- result.try (rows pool (taking store key full cost per_minute)) match taken { [_, ..] -> Ok(Admitted) , [] -> { use left <- result.try (rows pool (left store key full per_minute)) match left { [row, ..] -> match pg.row_int row "units" { Ok(Some(units)) -> Ok(Wait(rate_limit.wait_for per_minute units)) , _ -> Error("{store.table}: no units for {key}") } , [] -> Ok(Wait(1)) } } } } } /// Take one request's units if the bucket has them, refilled since its /// last request; no row comes back when it has not. fn taking :: store: Store key: String full: Int cost: Int per_minute: Int -> pg.Statement { let t = store.table let k = store.key_column pg.Statement( "insert into {t} as r ({k}, units, at_ms) values ($1, $2::bigint - $3::bigint, (extract(epoch from clock_timestamp()) * 1000)::bigint) on conflict ({k}) do update set units = least($2::bigint, r.units + (excluded.at_ms - r.at_ms) * $4::bigint) - $3::bigint, at_ms = excluded.at_ms where least($2::bigint, r.units + (excluded.at_ms - r.at_ms) * $4::bigint) >= $3::bigint returning units" , [pg.text key, pg.int full, pg.int cost, pg.int per_minute] ) } /// The units a refused bucket holds now. fn left :: store: Store key: String full: Int per_minute: Int -> pg.Statement { pg.Statement( "select least($2::bigint, units + ((extract(epoch from clock_timestamp()) * 1000)::bigint - at_ms) * $3::bigint) as units from {store.table} where {store.key_column} = $1" , [pg.text key, pg.int full, pg.int per_minute] ) } fn rows :: pool: pg.Pool statement: pg.Statement -> Result, String> / { pg.with_connection pool fn { pg.query_statement statement } |> result.flatten |> result.map fn found { found.rows } |> result.map_error pg.error_message } @test fn a_store_names_only_plain_sql_names :: { assert_equal (store "api_rates" "agent" |> result.is_ok) True assert_equal (store "_r2" "k_1" |> result.is_ok) True assert_equal (store "rates; drop table x" "key" |> result.is_ok) False assert_equal (store "Rates" "key" |> result.is_ok) False assert_equal (store "rates" "" |> result.is_ok) False assert_equal (store "9rates" "key" |> result.is_ok) False assert_equal (create_table (rates ())) "create table if not exists rates (key text primary key, units bigint not null, at_ms bigint not null)" }