Skip to content

Rate limiting with a token bucket gate

An SMS provider takes five messages a second: a token bucket gate in a stream lets five through, and the rest come back after their lease, in order.

Updated View as Markdown

An SMS provider accepts five messages a second for each customer. Send more and it refuses them, or blocks the account. The messages must still all go out, in order.

A stream with a gate decides, message by message, whether a message may go on now. The token bucket gate keeps its state per partition, in the broker: here five tokens per customer, refilled at five a second. A message the gate refuses stops its partition there, and comes back, with the ones after it, when its lease ends.

// The SMS provider accepts 5 messages a second for each customer.
// A refused message comes back when its lease ends: here after 1 second.
await queen.queue('sms-out').config({ leaseTime: 1 }).create()

const limiter = await Stream
  .from(queen.queue('sms-out'))                          // one partition per customer
  .gate(tokenBucketGate({ capacity: 5, refillPerSec: 5 }))  // 5 at once, then 5 a second
  .foreach(async (sms) => sendSms(sms))                  // only what the gate lets through
  .run({ queryId: 'sms-gate', url, subscriptionMode: 'all' })

// Twelve messages for one customer, all at once.
await queen.queue('sms-out').partition('customer-42')
  .push(Array.from({ length: 12 }, (_, i) => ({ data: { n: i + 1, text: `#${i + 1}` } })))

Five messages went at once, and the rest followed at about five a second, so the twelfth left about two seconds after the first: all twelve, in order.

Twelve SMS for customer-42 pushed at once. The gate starts with 5 tokens. At 0 seconds messages 1 to 5 pass; message 6 is refused, which stops the partition: 6 to 12 wait for the lease, 1 second. At 1 second the bucket has refilled 5 tokens (4.99 if the lease ends a few milliseconds early, and then only 4 pass) and messages 6 to 10 pass; 11 is refused. At 2 seconds 11 and 12 pass. All twelve go out, in order, 5 a second.Twelve SMS for customer-42 pushed at once. The gate starts with 5 tokens. At 0 seconds messages 1 to 5 pass; message 6 is refused, which stops the partition: 6 to 12 wait for the lease, 1 second. At 1 second the bucket has refilled 5 tokens (4.99 if the lease ends a few milliseconds early, and then only 4 pass) and messages 6 to 10 pass; 11 is refused. At 2 seconds 11 and 12 pass. All twelve go out, in order, 5 a second.
The token bucket gate: 5, 5, then 2, in order. A refill a few milliseconds short lets 4 through, not 5.
Why
the bucket lives in the broker, per customer, and survives restarts: no Redis next to it. Waiting messages stay in their queue, in order, and never need a queue of your own.

One thing to know: the refused messages wait for their lease, so size the two together. The most a gate can let through is the smaller of refillPerSec and capacity divided by the lease in seconds, so keep capacity near refillPerSec times the lease.

Built from: Streams, Queues (the lease).

Navigation

Type to search…

↑↓ navigate↵ selectEsc close