Rate Limiting in Scheme

Here’s the translation of the Go rate limiting example to Scheme, formatted in Markdown suitable for Hugo:

Rate limiting is an important mechanism for controlling resource utilization and maintaining quality of service. Scheme can implement rate limiting using threads and synchronization primitives.

(import (rnrs) (rnrs control) (srfi :18))

(define (main)
  ;; First we'll look at basic rate limiting. Suppose
  ;; we want to limit our handling of incoming requests.
  ;; We'll serve these requests off a queue.
  (define requests (make-queue))
  (for-each (lambda (i) (enqueue! requests i))
            '(1 2 3 4 5))

  ;; This limiter will allow an action every 200 milliseconds.
  ;; This is the regulator in our rate limiting scheme.
  (define (make-limiter)
    (let ((last-time (current-time)))
      (lambda ()
        (let ((current (current-time)))
          (if (>= (time-difference current last-time) 0.2)
              (begin
                (set! last-time current)
                #t)
              #f)))))

  (define limiter (make-limiter))

  ;; By checking the limiter before serving each request,
  ;; we limit ourselves to 1 request every 200 milliseconds.
  (let loop ()
    (unless (queue-empty? requests)
      (when (limiter)
        (let ((req (dequeue! requests)))
          (display (string-append "request " (number->string req) " "))
          (display (time->string (current-time) #t))
          (newline)))
      (loop)))

  ;; We may want to allow short bursts of requests in
  ;; our rate limiting scheme while preserving the
  ;; overall rate limit. We can accomplish this by
  ;; using a token bucket algorithm.
  (define (make-bursty-limiter burst-size refill-rate)
    (let ((tokens burst-size)
          (last-refill (current-time)))
      (lambda ()
        (let* ((now (current-time))
               (elapsed (time-difference now last-refill))
               (new-tokens (floor (* elapsed refill-rate))))
          (set! tokens (min burst-size (+ tokens new-tokens)))
          (set! last-refill now)
          (if (> tokens 0)
              (begin (set! tokens (- tokens 1)) #t)
              #f)))))

  (define bursty-limiter (make-bursty-limiter 3 5)) ; 3 burst, 5 tokens/second

  ;; Now simulate 5 more incoming requests. The first
  ;; 3 of these will benefit from the burst capability
  ;; of bursty-limiter.
  (define bursty-requests (make-queue))
  (for-each (lambda (i) (enqueue! bursty-requests i))
            '(1 2 3 4 5))

  (let loop ()
    (unless (queue-empty? bursty-requests)
      (when (bursty-limiter)
        (let ((req (dequeue! bursty-requests)))
          (display (string-append "request " (number->string req) " "))
          (display (time->string (current-time) #t))
          (newline)))
      (loop))))

(main)

Running our program, we would see the first batch of requests handled once every ~200 milliseconds as desired.

For the second batch of requests, we would serve the first 3 immediately because of the burstable rate limiting, then serve the remaining 2 with some delay between them.

Note that Scheme doesn’t have built-in concurrency primitives like Go’s goroutines and channels. Instead, we’ve used a queue to simulate the channel behavior and implemented custom functions for rate limiting. The time related functions are also implementation-dependent and may vary based on the Scheme implementation you’re using.

This example demonstrates how to implement basic and bursty rate limiting in Scheme, achieving similar functionality to the original Go example.

Waitgroups in Scheme

Atomic Counters in Scheme

Learn X By Example

Title here

Rate Limiting in Scheme