Skip to main content

runlimit_postgres/
protocol.rs

1use std::time::Duration;
2
3use runlimit_core::CounterKey;
4use sha2::{Digest, Sha256};
5use sqlx::Error;
6use tokio::time::Instant;
7
8const ADVISORY_LOCK_DOMAIN: &[u8] = b"runlimit/postgres-advisory-lock/v1\0";
9pub(crate) const SERVER_TIMEOUT_GRACE: Duration = Duration::from_millis(25);
10/// Number of stable capacity shards used by `PostgreSQL` storage.
11///
12/// The shard derivation is a persistent cross-replica protocol and this value
13/// must not change in place.
14pub const CAPACITY_SHARD_COUNT: usize = 256;
15
16/// Database-enforced maximum number of fixed-window rows in one capacity
17/// shard.
18///
19/// The additive cardinality migration enforces this ceiling independently of
20/// the runtime configuration, including for replicas running older code.
21pub const HARD_MAX_ROWS_PER_SHARD: u32 = 65_536;
22
23pub(crate) const SET_LOCAL_TIMEOUTS_SQL: &str = r"
24SELECT
25    set_config('statement_timeout', $1, true),
26    set_config('lock_timeout', $2, true)
27";
28
29pub(crate) const BATCH_ADVISORY_LOCK_SQL: &str = r"
30WITH RECURSIVE acquired(position, locked) AS (
31    SELECT 1, pg_advisory_xact_lock($1[1])
32    WHERE cardinality($1::BIGINT[]) > 0
33
34    UNION ALL
35
36    SELECT
37        acquired.position + 1,
38        pg_advisory_xact_lock($1[acquired.position + 1])
39    FROM acquired
40    WHERE acquired.position < cardinality($1::BIGINT[])
41)
42SELECT count(*)
43FROM acquired
44";
45
46pub(crate) const BATCH_ROW_LOCK_SQL: &str = r"
47WITH input_keys AS (
48    SELECT *
49    FROM unnest(
50        $1::BYTEA[],
51        $2::BYTEA[]
52    ) WITH ORDINALITY AS keys(
53        config_fingerprint,
54        subject_key,
55        input_position
56    )
57),
58lock_order AS (
59    SELECT *
60    FROM unnest($3::BIGINT[])
61        WITH ORDINALITY AS positions(input_position, lock_position)
62),
63ordered_keys AS (
64    SELECT
65        input_keys.config_fingerprint,
66        input_keys.subject_key,
67        lock_order.lock_position
68    FROM input_keys
69    INNER JOIN lock_order
70        ON lock_order.input_position = input_keys.input_position
71    ORDER BY lock_order.lock_position
72)
73SELECT 1
74FROM ordered_keys
75INNER JOIN runlimit_fixed_windows AS windows
76    ON windows.config_fingerprint = ordered_keys.config_fingerprint
77    AND windows.subject_key = ordered_keys.subject_key
78ORDER BY ordered_keys.lock_position
79FOR UPDATE OF windows
80";
81
82pub(crate) const BATCH_CAPACITY_LOCK_SQL: &str = r"
83WITH input_keys AS (
84    SELECT *
85    FROM unnest(
86        $1::BYTEA[],
87        $2::BYTEA[],
88        $3::SMALLINT[]
89    ) WITH ORDINALITY AS keys(
90        config_fingerprint,
91        subject_key,
92        capacity_shard,
93        input_position
94    )
95),
96missing_keys AS MATERIALIZED (
97    SELECT
98        input_keys.capacity_shard,
99        input_keys.input_position
100    FROM input_keys
101    LEFT JOIN runlimit_fixed_windows AS windows
102        ON windows.config_fingerprint = input_keys.config_fingerprint
103        AND windows.subject_key = input_keys.subject_key
104    WHERE windows.config_fingerprint IS NULL
105),
106target_shards AS (
107    SELECT DISTINCT capacity_shard
108    FROM missing_keys
109),
110locked_shards AS MATERIALIZED (
111    SELECT
112        capacity.capacity_shard,
113        capacity.row_count
114    FROM runlimit_capacity_shards AS capacity
115    INNER JOIN target_shards
116        ON target_shards.capacity_shard = capacity.capacity_shard
117    ORDER BY capacity.capacity_shard
118    FOR UPDATE OF capacity
119),
120lock_barrier AS MATERIALIZED (
121    SELECT count(*) AS locked_count
122    FROM locked_shards
123)
124SELECT
125    missing_keys.input_position - 1 AS input_index,
126    missing_keys.capacity_shard,
127    locked_shards.row_count
128FROM missing_keys
129LEFT JOIN locked_shards
130    ON locked_shards.capacity_shard = missing_keys.capacity_shard
131CROSS JOIN lock_barrier
132ORDER BY missing_keys.input_position
133";
134
135pub(crate) const BATCH_PREFLIGHT_SQL: &str = r"
136WITH input AS (
137    SELECT *
138    FROM unnest(
139        $1::BYTEA[],
140        $2::BYTEA[],
141        $3::BIGINT[],
142        $4::BIGINT[]
143    ) WITH ORDINALITY AS checks(
144        config_fingerprint,
145        subject_key,
146        cost,
147        quota_limit,
148        input_position
149    )
150),
151sample AS (
152    SELECT pg_catalog.clock_timestamp() AS database_now
153),
154first_denial AS (
155    SELECT
156        input.input_position - 1 AS input_index,
157        windows.window_expires_at
158    FROM input
159    CROSS JOIN sample
160    INNER JOIN runlimit_fixed_windows AS windows
161        ON windows.config_fingerprint = input.config_fingerprint
162        AND windows.subject_key = input.subject_key
163    WHERE
164        windows.window_expires_at > sample.database_now
165        AND windows.used > input.quota_limit - input.cost
166    ORDER BY input.input_position
167    LIMIT 1
168)
169SELECT
170    sample.database_now,
171    pg_catalog.clock_timestamp() AS response_now,
172    first_denial.input_index,
173    first_denial.window_expires_at
174FROM sample
175LEFT JOIN first_denial ON TRUE
176";
177
178pub(crate) const BATCH_UPSERT_SQL: &str = r"
179WITH input AS (
180    SELECT *
181    FROM unnest(
182        $1::TEXT[],
183        $2::TEXT[],
184        $3::BYTEA[],
185        $4::BYTEA[],
186        $5::INTERVAL[],
187        $6::BIGINT[],
188        $7::BIGINT[]
189    ) WITH ORDINALITY AS checks(
190        policy_id,
191        scope_id,
192        config_fingerprint,
193        subject_key,
194        window_size,
195        cost,
196        quota_limit,
197        input_position
198    )
199),
200upserted AS (
201    INSERT INTO runlimit_fixed_windows (
202        policy_id,
203        scope_id,
204        config_fingerprint,
205        subject_key,
206        window_started_at,
207        window_expires_at,
208        used
209    )
210    SELECT
211        policy_id,
212        scope_id,
213        config_fingerprint,
214        subject_key,
215        $8,
216        $8 + window_size,
217        cost
218    FROM input
219    ON CONFLICT (config_fingerprint, subject_key)
220    DO UPDATE SET
221        policy_id = EXCLUDED.policy_id,
222        scope_id = EXCLUDED.scope_id,
223        window_started_at = CASE
224            WHEN runlimit_fixed_windows.window_expires_at <= $8 THEN $8
225            ELSE runlimit_fixed_windows.window_started_at
226        END,
227        window_expires_at = CASE
228            WHEN runlimit_fixed_windows.window_expires_at <= $8
229                THEN $8 + (EXCLUDED.window_expires_at - EXCLUDED.window_started_at)
230            ELSE runlimit_fixed_windows.window_expires_at
231        END,
232        used = CASE
233            WHEN runlimit_fixed_windows.window_expires_at <= $8 THEN EXCLUDED.used
234            ELSE runlimit_fixed_windows.used + EXCLUDED.used
235        END
236    WHERE
237        runlimit_fixed_windows.window_expires_at <= $8
238        OR runlimit_fixed_windows.used
239            <= (
240                SELECT quota_limit - cost
241                FROM input
242                WHERE
243                    input.config_fingerprint = EXCLUDED.config_fingerprint
244                    AND input.subject_key = EXCLUDED.subject_key
245            )
246    RETURNING
247        config_fingerprint,
248        subject_key,
249        used,
250        window_expires_at
251),
252response AS (
253    SELECT pg_catalog.clock_timestamp() AS response_now
254    FROM upserted
255    HAVING count(*) >= 0
256)
257SELECT
258    input.input_position - 1 AS input_index,
259    upserted.used,
260    upserted.window_expires_at,
261    response.response_now
262FROM input
263INNER JOIN upserted
264    ON upserted.config_fingerprint = input.config_fingerprint
265    AND upserted.subject_key = input.subject_key
266CROSS JOIN response
267ORDER BY input.input_position
268";
269
270pub(crate) const CLEANUP_SQL: &str = include_str!("cleanup_expired.sql");
271
272pub(crate) fn is_server_timeout(error: &Error) -> bool {
273    let sqlx::Error::Database(database_error) = error else {
274        return false;
275    };
276    matches!(database_error.code().as_deref(), Some("57014" | "55P03"))
277}
278
279pub(crate) fn remaining_server_timeout_settings(deadline: Instant) -> Option<(String, String)> {
280    let remaining = deadline.checked_duration_since(Instant::now())?;
281    let remaining_millis = remaining.as_millis();
282    let statement_millis = remaining_millis
283        .saturating_sub(SERVER_TIMEOUT_GRACE.as_millis())
284        .max(1);
285    let lock_millis = statement_millis.saturating_sub(1).max(1);
286    Some((format!("{statement_millis}ms"), format!("{lock_millis}ms")))
287}
288
289pub(crate) fn advisory_lock_id(counter_key: CounterKey) -> i64 {
290    let mut digest = Sha256::new();
291    digest.update(ADVISORY_LOCK_DOMAIN);
292    digest.update(counter_key.to_bytes());
293    let digest = digest.finalize();
294    let mut id_bytes = [0_u8; 8];
295    let id_length = id_bytes.len();
296    id_bytes.copy_from_slice(&digest[..id_length]);
297    i64::from_be_bytes(id_bytes)
298}
299
300pub(crate) fn capacity_shard(counter_key: CounterKey) -> i16 {
301    i16::from(counter_key.fingerprint().as_bytes()[0] ^ counter_key.subject().as_bytes()[0])
302}