Edge Rate Limiting: Putting Noisy Clients in the Penalty Box

Some clients send a service far more requests than any person would. When that happens, you usually want to stop answering that client for a while. That's rate limiting: you count each client's requests, and once a client goes over a limit you've chosen, you refuse its requests for a period of time.

Fastly builds this into its network as Edge Rate Limiting, and a Compute program reaches it through the erl interface in compute.wit.

What edge rate limiting does

Fastly's rate limiting guide (opens in a new window) says rate limiting "is typically applied for one of two purposes: to prevent abusive use of a website or service (e.g. by a scraping bot or a denial of service attack) or to apply a limit on use of an expensive or billable resource (e.g. to allow up to 1000 requests an hour to an API endpoint)."

Those two jobs want different counters. Stopping abuse means reacting quickly to a sudden flood from one source, and a rough count is good enough. Metering an API means counting exactly, across the whole network, and a slower answer is fine. Edge Rate Limiting is built for the first job, and the guide calls it "an anti-abuse mechanism." For the second, it suggests "real-time log streaming combined with post-processing within your logging provider," the logging covered in the realtime logging post.

The product gives you two primitives: the rate counter and the penalty box. In the guide's words, "Rate counters allow you to count requests by individual client and penalty boxes allow you to penalize clients for exceeding rate limits you set." On each request, you check the client's rate. If it's over your limit, the client goes into the penalty box for a period you choose, and your service refuses its requests while it's there, usually with a 429 Too Many Requests response.

The guide calls each client in a counter or a penalty box an entry, and an entry is identified by a key: "The most common key is an IP address but any string value can be provided." If one IP address stands for many users, the guide suggests combining it with something else, such as the User-Agent or the URL path.

The guide describes everything in VCL terms first, but it notes that "the behavior of the Compute functions matches the behavior described here for VCL."

The whole interface

interface erl {
  use types.{error, open-error};

  /// A rate counter that can be used with a edge rate limiter or
  /// standalone for counting and rate calculations.
  resource rate-counter {
    /// Opens a `rate-counter` with the given name.
    ///
    /// The name must not exceed 1024 bytes in length. If the name is too long,
    /// `open-error::name-too-long` will be returned.
    open: static func(name: string) -> result<rate-counter, open-error>;

    /// Returns the name of this rate counter.
    get-name: func() -> string;

    /// Increments an entry in a rate counter and check if the client has exceeded some average number
    /// of requests per second (RPS) over the window.
    ///
    /// If the client is over the rps limit for the window, add to the penaltybox for ttl. Valid ttl
    /// span is 1m to 1h and TTL value is truncated to the nearest minute.
    ///
    /// Returns `true` if the client is penalized (i.e. should be limited), or `false` if not.
    check-rate: func(
      entry: string,
      delta: u32,
      window: u32,
      limit: u32,
      penalty-box: borrow<penalty-box>,
      ttl: u32,
    ) -> result<bool, error>;

    /// Increments an entry in the ratecounter by `delta`.
    increment: func(
      entry: string,
      delta: u32,
    ) -> result<_, error>;

    /// Looks up the current rate for entry in the ratecounter for a window.
    lookup-rate: func(
      entry: string,
      window: u32,
    ) -> result<u32, error>;

    /// Looks up the current count for entry in the ratecounter for duration.
    lookup-count: func(
      entry: string,
      duration: u32,
    ) -> result<u32, error>;
  }

  /// A penaltybox that can be used with the edge rate limiter or
  /// standalone for adding and checking if some entry is in the data set.
  resource penalty-box {
    /// Opens a `penalty-box` identified by the given name.
    ///
    /// The name must not exceed 1024 bytes in length. If the name is too long,
    /// `open-error::name-too-long` will be returned.
    open: static func(name: string) -> result<penalty-box, open-error>;

    /// Returns the name of this penaltybox.
    get-name: func() -> string;

    /// Adds `entry` to the penaltybox for the duration of ttl.
    ///
    /// Valid ttl span is 1m to 1h and TTL value is truncated to the nearest minute.
    add: func(
      entry: string,
      ttl: u32,
    ) -> result<_, error>;

    /// Checks if `entry` is in the penaltybox.
    has: func(
      entry: string,
    ) -> result<bool, error>;
  }
}

There are two resources, one per primitive, and both are opened by name with the same static func shape as every store since Config Store. From the ABI's side, a rate counter keeps a count per entry, and a penalty box is a set of entries that expire.

There's no resource called a rate limiter. The limiter is check-rate, a method on the counter that borrows a penalty box. It increments the entry, estimates its rate, and if the rate is over the limit, puts the entry in the box. The Rust SDK gives you an ERL struct that pairs a counter with a penalty box, but that pairing is the SDK's. The ABI just passes the box in on every call.

Four u32s with no units

Read check-rate's parameters again. delta, window, limit, and ttl are all u32. The doc comment calls limit an "rps limit," and says a ttl can span "1m to 1h" without saying what one of its integers is worth. window gets nothing at all.

The rate limiting guide fills in the rest. Its Rust example labels delta as "the number of requests this execution counts as." Rates are always requests per second, estimated over one of exactly three windows: 1 second, 10 seconds, or 60 seconds. Counts come in 10-second buckets over the last minute, so lookup-count's duration can be 10, 20, 30, 40, 50, or 60.

If you were designing an SDK around this interface, you'd want a separate type for each of these, so a window can never be passed where a limit or a duration belongs. The Rust SDK does exactly that. In fastly 0.13.1, lookup_rate and check_rate take a RateWindow, an enum with OneSec = 1, TenSecs = 10, and SixtySecs = 60. lookup_count takes a CounterDuration, whose variants are the six multiples of ten. And ttl is a std::time::Duration, sent across as ttl.as_secs() as u32, so the integer is seconds.

So window: u32 accepts about four billion values and three of them mean something. The WIT can't tell you which three.

Locally, nothing is enforced

Full working code: full example on GitHub (opens in a new window).

The example keys a counter by client IP and allows five requests per second, averaged over ten seconds, before penalizing a client for sixty. Then it reports what every other call says, and tries three things the doc comments rule out.

imports, and helpers for formatting an IP and sending a text response (26 lines)
mod bindings;

use bindings::{
    exports::fastly::compute::http_incoming,
    fastly::compute::{erl, http_body, http_downstream, http_resp, types},
};

fn format_ip(ip: Option<types::IpAddress>) -> String {
    match ip {
        Some(types::IpAddress::Ipv4((a, b, c, d))) => format!("{a}.{b}.{c}.{d}"),
        Some(types::IpAddress::Ipv6(p)) => {
            let parts = [p.0, p.1, p.2, p.3, p.4, p.5, p.6, p.7];
            parts.iter().map(|x| format!("{x:x}")).collect::<Vec<_>>().join(":")
        }
        None => "unknown".to_string(),
    }
}

fn respond(status: u16, text: String) -> Result<(), ()> {
    let response = http_resp::Response::new().map_err(|_| ())?;
    response.set_status(status).map_err(|_| ())?;
    response.insert_header("content-type", b"text/plain").map_err(|_| ())?;
    let body = http_body::new().map_err(|_| ())?;
    http_body::write(&body, text.as_bytes()).map_err(|_| ())?;
    http_resp::send_downstream(response, body).map_err(|_| ())
}

struct EdgeRateLimiting;

impl http_incoming::Guest for EdgeRateLimiting {
    fn handle(request: http_incoming::Request, _request_body: http_body::Body) -> Result<(), ()> {
        let entry = format_ip(http_downstream::downstream_client_ip_addr(&request));
        let mut lines = format!("{:<36}{entry:?}\n", "entry");

        let counter = erl::RateCounter::open("requests_by_ip").map_err(|_| ())?;
        let penalty_box = erl::PenaltyBox::open("banned_ips").map_err(|_| ())?;

        // Over 5 requests per second, averaged across 10 seconds, earns 60 seconds in the box.
        let limited = counter.check_rate(&entry, 1, 10, 5, &penalty_box, 60);
        lines.push_str(&format!("{:<36}{limited:?}\n", "check-rate (5 rps over 10s, 60s)"));

        lines.push_str(&format!("{:<36}{:?}\n", "lookup-rate (10s window)", counter.lookup_rate(&entry, 10)));
        lines.push_str(&format!("{:<36}{:?}\n", "lookup-count (last 60s)", counter.lookup_count(&entry, 60)));
        lines.push_str(&format!("{:<36}{:?}\n", "penalty-box has", penalty_box.has(&entry)));

        // Things the doc comments say shouldn't work.
        lines.push_str(&format!("{:<36}{:?}\n", "add, ttl 5s (under the 1m minimum)", penalty_box.add("someone-else", 5)));
        lines.push_str(&format!("{:<36}{:?}\n", "lookup-rate, window 7", counter.lookup_rate(&entry, 7)));
        let long_name = "x".repeat(2000);
        lines.push_str(&format!("{:<36}{}\n", "open, 2000-byte name", match erl::RateCounter::open(&long_name) {
            Ok(_) => "Ok".to_string(),
            Err(e) => format!("Err({e:?})"),
        }));

        if matches!(limited, Ok(true)) {
            return respond(429, lines);
        }
        respond(200, lines)
    }
}

bindings::export!(EdgeRateLimiting with_types_in bindings);

There's nothing to configure in fastly.toml, for local testing or for production. Counters and penalty boxes aren't declared anywhere; opening one by a new name creates it.

Run fastly compute serve and send thirty requests as fast as curl will go:

for i in $(seq 1 30); do curl -s -o /dev/null -w "%{http_code} " http://127.0.0.1:7676/; done

200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200

Then look at the thirty-first:

entry                               "127.0.0.1"
check-rate (5 rps over 10s, 60s)    Ok(false)
lookup-rate (10s window)            Ok(0)
lookup-count (last 60s)             Ok(0)
penalty-box has                     Ok(false)
add, ttl 5s (under the 1m minimum)  Ok(())
lookup-rate, window 7               Ok(0)
open, 2000-byte name                Ok

The client isn't limited, the counter reports no traffic, and the penalty box is empty. The three calls that should have been rejected all succeeded: a TTL under a minute, a window that isn't one of the three, and a name twice as long as open's doc comment allows, which promises open-error::name-too-long.

It turns out this is not an accident. This is one of those features that aren't implemented for local testing.

Viceroy implements all six functions in src/component/erl.rs as constants, and none of them reads its arguments. check-rate returns Ok(false), the lookups return Ok(0), has returns Ok(false), and increment and add return Ok(()). The two opens never fail. There's no counter storage anywhere in the sandbox.

What a real service does

On a real Compute service, the counters count. That's the one thing a local run can't show you, and once they're counting, a few more behaviors appear that are worth planning for before your first deploy. Everything in this section comes from running erl against a real service.

Nothing needs to be enabled or provisioned. The host creates a rate counter or a penalty box the first time you open it by name, so there's no store to create and link to the service beforehand. Edge Rate Limiting itself needs nothing switched on for Compute, which Fastly confirmed when I asked, and it worked on the first deploy. That's worth writing down, because VCL is different: the guide warns that the product "must be enabled on your account by a Fastly employee in order to use the primitives in VCL." When a limiter seems not to be working, checking whether the product is on is the natural first move. On Compute, it leads nowhere.

Counts are estimates, and the guide is blunt about it: rate counters "are designed to quickly count high volumes of traffic, not to count precisely." A counter belongs to the service, and the guide describes each 10-second count as covering requests "across the entire Fastly POP."

The buckets are fixed to the wall clock rather than sliding. At 12:01:03, the current 10-second bucket covers 12:01:00 to 12:01:10, so every bucket boundary falls on a multiple of ten seconds.

Writes don't show up right away. The first check-rate on a new entry routinely comes back false, even with a delta far above the limit, and the server that handles the next request often hasn't seen that increment yet. Expect about a second of lag. The same goes for increment followed by lookup-count: call them in quick succession and you'll see the old value.

That lag is what makes a limiter hard to test, even on a real service. A test that sends one request with a huge delta and expects true will fail, and so will one that increments and reads the count straight back. Traffic has to arrive, and then the test has to wait before it looks.

lookup-rate comes back quantized to whole requests per second.

And the shortest penalty is a minute, which is what the doc comment's "1m to 1h" is telling you. Asking for five seconds doesn't get you a five-second penalty, and a test that waits for a penalty to expire takes at least a minute.

Beyond the WIT

erl is an interface where you must stay very aware of differences in behavior between local testing and the Fastly platform.

Locally, it is a host that agrees with everything. When Viceroy doesn't implement something, as with the HTTP cache, it typically says so with error.unsupported, and your tests fail where you can see them. Viceroy does sometimes disagree more quietly than that: the realtime logging post found it opening endpoint names a real service refuses. But that was one call, and a name you could check. Here the disagreement covers the whole interface, and every call succeeds with a plausible value. A test that sends a burst of requests and expects a 429 fails, which is at least honest. A test that sends one request and expects a 200 passes against Viceroy, and it would pass just as well if your limit were set to zero, or if you'd passed the arguments to check-rate in the wrong order.

Don't take this last case lightly. check-rate takes delta, window, limit, and ttl as four adjacent u32s. If you were to swap window and limit, the code still compiles, still runs, and passes every local test. On a real service it asks for a window of five seconds, which isn't one of the three that exist, with a limit of ten.

This is where a binding earns its keep, and it can do three things the ABI doesn't.

It can make the units types. A RateWindow with three variants, a CounterDuration with six, and a real duration type for ttl. That turns the adjacent-integer mistake into a compile error, exactly the shape the Rust SDK took.

It can validate when the host won't. A TTL under a minute, or a name over 1,024 bytes, can be rejected in the binding before it ever reaches a host that may or may not check. The doc comments already state the rules, but a binding is the place they can be enforced the same way under every host.

It can make the limiter testable without a host at all. Code that decides what to do with a true from check-rate is ordinary logic. If the binding exposes the counter behind an interface, or a trait in Rust, that code can be tested against a fake counter that counts, which is the one thing Viceroy's can't do. The real counter then only needs a smoke test on a real service, and nobody mistakes a green local run for proof that rate limiting works.

Next: a pair of functions the very first post in this series quoted a doc comment pointing at, and we've stepped around ever since. next-request and await-request let one sandbox handle more than one request.