nx_rate_limit_v1.nx source
↩ module page · 144 lines · 5560 B
1// rate_limit.nx -- token-bucket rate limiter.
2//
3// Standard algorithm (RFC 2698 / IEEE; also what HAProxy, nginx,
4// AWS API Gateway, and Stripe use):
5//
6// - Bucket has a max capacity (burst size) of B tokens
7// - Tokens refill at rate R per second up to B
8// - Each request consumes 1 token (or more for weighted ops)
9// - Request allowed iff current tokens >= needed; otherwise
10// reject (429 Too Many Requests) or wait
11//
12// Time is passed in as unix_microseconds -- caller reads a
13// monotonic clock and hands it to us. This keeps the module
14// pure + testable and decoupled from the OS time source.
15// For real use pair with ntp.nx + sys_clock_monotonic.
16//
17// Use cases: HTTP API throttling (per IP / per token), login
18// attempt rate limiting (anti-brute-force), outbound API call
19// pacing, mail-send pacing, git clone pacing.
20//
21// Invariants:
22// RL1 tokens clamped to capacity on every refill (bucket
23// never overflows).
24// RL2 Time going backwards does nothing (malicious / NTP
25// adjustment) -- we record max(now, last_refill).
26// RL3 Rate is expressed in tokens per second; sub-second
27// granularity handled via microsecond timestamps.
28
29// nx_safety_envelope:
30// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
31// sil_target: SIL1
32// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
33// verdict: NOT_YET_EVALUATED
34
35import "nx_syscalls.nx"
36const RL_MAGIC_500000: i64 = 500000
37const RL_MAGIC_5500000: i64 = 5500000
38
39struct RateLimiter {
40 capacity: i64, // bucket max (burst size)
41 refill_per_sec: i64, // tokens added per second
42 tokens_scaled: i64, // current tokens * 1_000_000 (so we can
43 // add fractional tokens without FP)
44 last_refill_us: i64, // last top-up timestamp in microseconds
45}
46
47const RL_SCALE: i64 = 1000000
48
49// Initialise a limiter. Starts full (so new clients get a burst
50// before they have to wait for refill).
51func rate_limit_init(rl: *RateLimiter, capacity: i64,
52 refill_per_sec: i64, now_us: i64) -> i64 {
53 rl.capacity = capacity
54 rl.refill_per_sec = refill_per_sec
55 rl.tokens_scaled = capacity * RL_SCALE
56 rl.last_refill_us = now_us
57 return 0
58}
59
60// Recompute tokens given current time. Safe to call
61// idempotently; extracted for use by try_take + peek.
62func rate_limit_refill(rl: *RateLimiter, now_us: i64) -> i64 {
63 if now_us <= rl.last_refill_us { return 0 }
64 let elapsed_us: i64 = now_us - rl.last_refill_us
65 // Tokens to add scaled: (elapsed_us * refill_per_sec) so the
66 // scale stays tokens*1_000_000.
67 let add_scaled: i64 = elapsed_us * rl.refill_per_sec
68 var new_scaled: i64 = rl.tokens_scaled + add_scaled
69 let max_scaled: i64 = rl.capacity * RL_SCALE
70 if new_scaled > max_scaled { new_scaled = max_scaled }
71 rl.tokens_scaled = new_scaled
72 rl.last_refill_us = now_us
73 return 0
74}
75
76// Try to take n tokens. Returns 1 if granted, 0 if denied.
77func rate_limit_try_take(rl: *RateLimiter, n: i64, now_us: i64) -> i64 {
78 rate_limit_refill(rl, now_us)
79 let need_scaled: i64 = n * RL_SCALE
80 if rl.tokens_scaled < need_scaled { return 0 }
81 rl.tokens_scaled = rl.tokens_scaled - need_scaled
82 return 1
83}
84
85// Peek: how many integer tokens available right now.
86func rate_limit_available(rl: *RateLimiter, now_us: i64) -> i64 {
87 rate_limit_refill(rl, now_us)
88 return rl.tokens_scaled / RL_SCALE
89}
90
91// Time until next single token (or 0 if available now), in us.
92// Useful for 429-Retry-After header values.
93func rate_limit_next_token_us(rl: *RateLimiter, now_us: i64) -> i64 {
94 rate_limit_refill(rl, now_us)
95 if rl.tokens_scaled >= RL_SCALE { return 0 }
96 let deficit_scaled: i64 = RL_SCALE - rl.tokens_scaled
97 if rl.refill_per_sec == 0 { return -1 } // never
98 // deficit_scaled tokens to generate at refill_per_sec per
99 // second. Each us of elapsed_us contributes refill_per_sec
100 // to new_scaled. us_needed = ceil(deficit_scaled / refill_per_sec).
101 let us_needed: i64 = (deficit_scaled + rl.refill_per_sec - 1) / rl.refill_per_sec
102 return us_needed
103}
104
105// Compile-only smoke.
106func main() -> i64 {
107 let rl_raw: *u8 = sys_mmap(64)
108 let rl: *RateLimiter = rl_raw as *RateLimiter
109
110 // 10-token burst, 2 tokens per second, start at t=0us.
111 rate_limit_init(rl, 10, 2, 0)
112 if rate_limit_available(rl, 0) != 10 { return 1 }
113
114 // Consume 10 tokens rapidly -- all should succeed.
115 var i: i64 = 0
116 while i < 10 {
117 if rate_limit_try_take(rl, 1, 0) != 1 { return 2 }
118 i = i + 1
119 }
120 if rate_limit_available(rl, 0) != 0 { return 3 }
121
122 // 11th -- no tokens.
123 if rate_limit_try_take(rl, 1, 0) != 0 { return 4 }
124
125 // At t=500ms (500_000 us), we've refilled 1 token.
126 if rate_limit_available(rl, RL_MAGIC_500000) != 1 { return 5 }
127 if rate_limit_try_take(rl, 1, RL_MAGIC_500000) != 1 { return 6 }
128
129 // Can't take another immediately.
130 if rate_limit_try_take(rl, 1, RL_MAGIC_500000) != 0 { return 7 }
131
132 // Time needed for next token: 500_000us.
133 let wait_us: i64 = rate_limit_next_token_us(rl, RL_MAGIC_500000)
134 if wait_us != RL_MAGIC_500000 { return 8 }
135
136 // 5 seconds later, bucket refills up to capacity.
137 if rate_limit_available(rl, RL_MAGIC_5500000) != 10 { return 9 }
138
139 // Time going backwards: harmless.
140 if rate_limit_try_take(rl, 5, RL_MAGIC_5500000) != 1 { return 10 }
141 if rate_limit_available(rl, 100) != 5 { return 11 }
142
143 return 0
144}