Struct ProbabilisticTokenBucket 

pub struct ProbabilisticTokenBucket { /* private fields */ }

Probabilistic token bucket with fixed sampling rate.

This algorithm samples only a fraction of requests (e.g., 1%) and scales token consumption accordingly. This dramatically reduces atomic operations at the cost of a small error margin.

Performance Characteristics

With 1% sampling (SAMPLE_RATE = 100):

• Single-threaded: 500M+ ops/sec (vs 16M baseline, 31x improvement)
• Multi-threaded: Near-linear scaling (vs degraded scaling in baseline)
• Atomic operations: 99% reduction

Accuracy

• 1% sampling: ~1-2% error margin
• 5% sampling: ~0.5-1% error margin
• 10% sampling: ~0.2-0.5% error margin

Error manifests as allowing slightly more requests than the configured limit. False negatives (denying valid requests) are rare.

Use Cases

Ideal for:

• High-throughput APIs (1M+ req/sec)
• Soft rate limiting (DDoS protection)
• Cost optimization (reducing CPU usage)

Not suitable for:

• Billing/metering (requires exact counts)
• Strict compliance scenarios
• Low-traffic endpoints (<1000 req/sec)

Implementations

impl ProbabilisticTokenBucket

pub fn new(capacity: u64, refill_rate_per_second: u64, sample_rate: u32) -> Self

Creates a new probabilistic token bucket with the specified sampling rate.

Arguments

• capacity - Maximum tokens (burst size)
• refill_rate_per_second - Tokens added per second
• sample_rate - 1 in N requests are sampled (e.g., 100 = 1% sampling)

Recommended Sampling Rates

• 100 (1%): Maximum speed, ~1-2% error
• 20 (5%): High speed, ~0.5-1% error
• 10 (10%): Good speed, ~0.2-0.5% error

Examples

// 1% sampling: 100 req/sec limit, 1% of requests perform atomic ops
let bucket = ProbabilisticTokenBucket::new(200, 100, 100);

// 5% sampling: Better accuracy, still very fast
let bucket = ProbabilisticTokenBucket::new(200, 100, 20);

pub fn with_ttl( capacity: u64, refill_rate_per_second: u64, sample_rate: u32, idle_ttl: Duration, ) -> Self

Creates a new probabilistic token bucket with TTL-based eviction.

pub fn sample_rate(&self) -> u32

Get the configured sampling rate.

Trait Implementations

impl Algorithm for ProbabilisticTokenBucket

fn check<'life0, 'life1, 'async_trait>( &'life0 self, key: &'life1 str, ) -> Pin<Box<dyn Future<Output = Result<RateLimitDecision>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

Checks if a request for the given key should be permitted.

fn check_with_cost<'life0, 'life1, 'async_trait>( &'life0 self, key: &'life1 str, cost: u64, ) -> Pin<Box<dyn Future<Output = Result<RateLimitDecision>> + Send + 'async_trait>>

where Self: 'async_trait, 'life0: 'async_trait, 'life1: 'async_trait,

Checks if a request with the given cost should be permitted.