Rust in Everything
基于 tower 0.5.3

RateLimit

主线位置:就绪主线。次数用完后 poll_ready 返回 Pending,等窗口结束;请求主线上它不包 future,响应 future 就是内层的。

stateDiagram-v2
  [*] --> Ready: new
  Ready --> Ready: call 扣一次
  Ready --> Limited: 用掉最后一次
  Limited --> Limited: Sleep 未到期
  Limited --> Ready: 到期开新窗口

RateLimit 回答的问题是「每 per 时间最多放过 num 个请求」。它用的是最简单的办法:数次数,数满了就睡到窗口结束。没有令牌桶,没有滑动窗口,也不区分来源。

结构:状态、速率和一个常驻的 Sleep

RateLimit 和 State:

#[derive(Debug)]
pub struct RateLimit<T> {
    inner: T,
    rate: Rate,
    state: State,
    sleep: Pin<Box<Sleep>>,
}

#[derive(Debug)]
enum State {
    // The service has hit its limit
    Limited,
    Ready { until: Instant, rem: u64 },
}
  • Ready { until, rem }:当前窗口在 until 结束,还剩 rem 次。
  • Limited:次数用完,等 sleep 到期。
  • Rate 只是 num 和 per 两个字段,Rate::new 用 assert! 拒绝 0:num > 0、per.as_nanos() > 0。它是 const fn,所以 RateLimitLayer::new 可以写在 const 里,这正是 PR #760 给出的动机(「The main reason was to allow to initialize the RateLimitLayer in a const context.」)。

sleep 不放在 State::Limited 里,而是常驻在结构体上、Box::pin 一次,之后只 reset。这是升级 Tokio 1.0 时(PR #489,tower 0.4.0)改的:tokio 1.0 的 Sleep 不再是 Unpin,要 pin 在堆上,PR 描述说为了避免每次限流都分配、释放一个 Box,把 Sleep 挪出了 State,「we only allocate the box once when the service is created」。reset 为什么便宜,见 Sleep 的一生。

new 的初始状态是 Ready { until: Instant::now(), rem: num }。until 就是现在,所以第一次 call 时窗口一定已经「过期」,会被重置成 now + per:第一个窗口从第一次 call 开始,不是从创建服务开始。

call:扣次数

call:

    fn call(&mut self, request: Request) -> Self::Future {
        match self.state {
            State::Ready { mut until, mut rem } => {
                let now = Instant::now();

                // If the period has elapsed, reset it.
                if now >= until {
                    until = now + self.rate.per();
                    rem = self.rate.num();
                }

                if rem > 1 {
                    rem -= 1;
                    self.state = State::Ready { until, rem };
                } else {
                    // The service is disabled until further notice
                    // Reset the sleep future in place, so that we don't have to
                    // deallocate the existing box and allocate a new one.
                    self.sleep.as_mut().reset(until);
                    self.state = State::Limited;
                }

                // Call the inner future
                self.inner.call(request)
            }
            State::Limited => panic!("service not ready; poll_ready must be called first"),
        }
    }
  • 计数在 call 里扣,不在 poll_ready 里。poll_ready 返回 Ready 并不预留名额,名额在 call 的那一刻才用掉。
  • 窗口过期的检查也在 call 里:处于 Ready 状态时,过了 until 再来的请求会开一个从现在算起的新窗口。
  • rem > 1 而不是 rem > 0:扣掉的是最后一次时直接转 Limited,并把 sleep 拨到本窗口的 until。所以 Limited 不是「下一个请求被拒绝」之后才进入,而是用完最后一个名额的同时就进入,下一次 poll_ready 立刻就会 Pending。
  • 响应 future 就是 self.inner.call(request) 的返回值,type Future = S::Future,Error 也是内层的。RateLimit 不包 future,也不产生错误。

Limited 状态下 call 会 panic,信息是 service not ready; poll_ready must be called first。Ready 状态下不先 poll_ready 就 call 不会 panic,下面的实验里能看到。

📝NOTE
冷知识:有一段时间,过期的窗口只重置了一半

2020 年 4 月以前,call 里重置窗口的那段是这样写的(摘自修复的 diff):

                if now >= until {
                    until = now + self.rate.per();
                    let rem = self.rate.num();

                    self.state = State::Ready { until, rem }
                }

                if rem > 1 {
                    rem -= 1;
                    self.state = State::Ready { until, rem };

let rem 在 if 块里新建了一个同名变量,块外的 rem 还是旧窗口剩下的次数;紧接着第二个 if 又用旧的 rem 把 self.state 覆盖掉了。结果是 until 换成了新窗口,rem 却没恢复。PR #438 的描述:「the rate limit remaining count never got reset and we always hit the branch that sets the limited state」,状态只能等 Limited 之后在 poll_ready 里才真正重置,后果是「we were probably rate limiting more than expected」。修法就是本页的代码:去掉 let,直接给外面的 rem 赋值,并加了一个测试 remaining_gets_reset。#438 修的是 v0.1.x 分支,同样的修复以 PR #439 进了 master,首次随 tower 0.4.0 发布。

poll_ready:Limited 时等 Sleep

poll_ready:

    fn poll_ready(&mut self, cx: &mut Context<'_>) -> Poll<Result<(), Self::Error>> {
        match self.state {
            State::Ready { .. } => return self.inner.poll_ready(cx),
            State::Limited => {
                if Pin::new(&mut self.sleep).poll(cx).is_pending() {
                    tracing::trace!("rate limit exceeded; sleeping.");
                    return Poll::Pending;
                }
            }
        }

        self.state = State::Ready {
            until: Instant::now() + self.rate.per(),
            rem: self.rate.num(),
        };

        self.inner.poll_ready(cx)
    }

Limited 时 poll 那个常驻的 Sleep:没到期就 Pending,Sleep 已经登记了调用方的 waker,到期时会叫醒它;到期了就开新窗口,再问内层。

新窗口的起点是 poll_ready 发现到期的那一刻(Instant::now()),不是旧窗口的 until。如果到期后很久才有人来 poll_ready,窗口就从那时算起。窗口不对齐到任何固定的时间刻度,跟着请求走。

固定窗口的边界

固定窗口只保证「每个窗口内不超过 num 次」,不保证「任意 per 长的时间段内不超过 num 次」。下面的程序按每秒 3 次限流:0ms 发一个请求,打开窗口 [0, 1000);等到 900ms,再连续发 5 个。时钟暂停,输出确定。

tower = { version = "=0.5.3", features = ["limit", "util"] }
tokio = { version = "=1.54.1", features = ["rt", "macros", "time", "test-util"] }
use std::{convert::Infallible, time::Duration};
use tokio::time::{sleep, Instant};
use tower::{limit::RateLimitLayer, service_fn, Layer, Service, ServiceExt};

#[tokio::main(flavor = "current_thread", start_paused = true)]
async fn main() {
  let start = Instant::now();
  let ms = move || start.elapsed().as_millis();
  let inner = service_fn(|x: u32| async move { Ok::<_, Infallible>(x) });
  // 3 requests per second
  let mut svc = RateLimitLayer::new(3, Duration::from_secs(1)).layer(inner);

  svc.ready().await.unwrap().call(0).await.unwrap();
  println!("req 0 at {}ms", ms());

  sleep(Duration::from_millis(900)).await;
  for id in 1..=5 {
    svc.ready().await.unwrap().call(id).await.unwrap();
    println!("req {id} at {}ms", ms());
  }
}
❗IMPORTANT
动脑筋:请求 1 到 5 分别在什么时刻被放行?

限速是每秒 3 次。先想清楚 900ms 时窗口里还剩几次,用完以后 sleep 被拨到哪一刻、新窗口从哪一刻开始,再写出五个时间。从 900ms 到最后一个请求放行,一共经过了多久、放过了几个请求?答案在文末。

一般地,一个窗口最后时刻还能放过 num − 1 次(第一次 call 开启了窗口,至少用掉一次),紧接着新窗口一开又是 num 次,所以窗口边界附近一小段时间里最多可以有 2 × num − 1 个请求通过。令牌桶不会这样:桶的容量就是突发的上限。需要平滑限速时,RateLimit 不是合适的工具。

没有 Clone

RateLimit 只 derive 了 Debug,没有 Clone。试着复制一份:

use std::{convert::Infallible, time::Duration};
use tower::{limit::RateLimitLayer, service_fn, Layer};

fn main() {
  let inner = service_fn(|x: u32| async move { Ok::<_, Infallible>(x) });
  let svc = RateLimitLayer::new(2, Duration::from_secs(1)).layer(inner);
  let _copy = svc.clone();
}
error[E0599]: no method named `clone` found for struct `RateLimit<T>` in the current scope
 --> src/bin/rate_clone.rs:7:19
  |
7 |   let _copy = svc.clone();
  |                   ^^^^^ method not found in `RateLimit<ServiceFn<{closure@src/bin/rate_clone.rs:5:26: 5:34}>>`

For more information about this error, try `rustc --explain E0599`.
error: could not compile `exp-tower-mwa` (bin "rate_clone") due to 1 previous error

RateLimitLayer 本身可以 Clone,它只存一个 Rate;但 layer 每次都 RateLimit::new,每个实例从满额开始,单独计数。下面同一个 layer 套出 a、b 两个实例,每秒 2 次(依赖与上面固定窗口的实验相同):

use std::{
  convert::Infallible,
  panic::{catch_unwind, AssertUnwindSafe},
  time::Duration,
};
use tower::{limit::RateLimitLayer, service_fn, Layer, Service};

#[tokio::main(flavor = "current_thread", start_paused = true)]
async fn main() {
  let inner = service_fn(|x: u32| async move { Ok::<_, Infallible>(x) });
  let layer = RateLimitLayer::new(2, Duration::from_secs(1));
  let mut a = layer.layer(inner);
  let mut b = layer.layer(inner);

  // never call poll_ready: fine while the state is Ready
  println!("a.call(1) -> {:?}", a.call(1).await);
  println!("a.call(2) -> {:?}", a.call(2).await);
  // two instances made by the same layer count separately
  println!("b.call(3) -> {:?}", b.call(3).await);

  std::panic::set_hook(Box::new(|_| {})); // keep the default hook quiet
  let r = catch_unwind(AssertUnwindSafe(|| {
    let _ = a.call(4); // a is Limited now
  }));
  let p = r.unwrap_err();
  println!("a.call(4) panics: {:?}", p.downcast_ref::<&str>());
}
a.call(1) -> Ok(1)
a.call(2) -> Ok(2)
b.call(3) -> Ok(3)
a.call(4) panics: Some("service not ready; poll_ready must be called first")

(M2 Max、rustc 1.99.0、--release,连跑 3 次输出相同。)a 用完 2 次后进入 Limited,b 不受影响;a 前两次没有 poll_ready 也照常返回,第三次在 Limited 状态下 call 才 panic。

📝NOTE
没有蠢问题

问: 有些地方要求服务能 Clone,比如要给每个连接复制一份服务。RateLimit 为什么不干脆 derive 一个 Clone?

答: 源码没有写理由,但能推出后果:状态全在实例身上(state、sleep),复制出来的每一份都会各数各的,效果和上面的 a、b 一样:N 份副本合起来每秒放过 N × num 次,限流形同虚设。要让很多调用方共用一个计数,就得让它们都经过同一个实例:在 RateLimit 外面套 Buffer。Buffer 可以 Clone,所有副本把请求送进同一个 worker,worker 里只有一个 RateLimit。注意这得到的仍是整个服务共用一个窗口,不是按客户端分别限流。

动脑筋答案

M2 Max、rustc 1.99.0、--release,连跑 3 次,输出相同:

req 0 at 0ms
req 1 at 900ms
req 2 at 900ms
req 3 at 1000ms
req 4 at 1000ms
req 5 at 1000ms
  • req 0:第一次 call,窗口过期(until 是创建时的 now),重置为 [0, 1000),rem 从 3 扣到 2。
  • req 1、2 在 900ms:窗口还剩 2 次。req 1 扣到 1;req 2 时 rem 不大于 1,于是 sleep 拨到 1000ms,状态转 Limited。
  • req 3 在 1000ms:ready() 在 Limited 下等 Sleep,暂停的时钟快进到 1000ms,poll_ready 开新窗口 [1000, 2000),rem 回到 3。
  • req 4、5 也在 1000ms:新窗口的第 2、3 次。req 5 用掉最后一次,Limited 到 2000ms。

从 900ms 到 1000ms 这 100ms 里放过了 5 个请求,正好是 2 × 3 − 1。

小结

  • 状态只有两个:Ready { until, rem } 和 Limited;Sleep 常驻在结构体上,只 reset,不重新分配。
  • call 扣次数并检查窗口是否过期;扣掉最后一次时把 Sleep 拨到 until,转 Limited。Limited 时 call 会 panic,Ready 时不 poll_ready 也能 call。
  • poll_ready 在 Limited 时等 Sleep,到期后从「现在」开新窗口。第一个窗口从第一次 call 开始。
  • 固定窗口:边界前后的一小段时间里最多放过 2 × num − 1 个请求。
  • 不包响应 future,不产生错误;没有 Clone,每个实例单独计数,多个调用方共用一个计数要靠 Buffer。

💬 关联讨论

发起讨论
加载中...