最近想到一个对于限流的问题， 比方一个 api 限度每秒最多申请 100 次，那么咱们在本地就须要做这样一个限度机制，来保障任意一个 1 秒的时间段内，申请次数都小于 100 次。
咱们设时间段为 T （这里是 1 秒），申请次数为 R （这里是 100 次），而后取正整数 n （n > 1)，示意将时间段均匀分成 n 份。定义 t = T / n 为每份的时长。定义 r(t(i)) = R - sum(r‘(t(i-n))...r’(t(i-1)))， 示意任意一份工夫片中的最大申请次数，等于 R 减去过来 n 份工夫片的申请次数总和。道歉我还没有开始学 Latex，没法精确地写出公式。总之依照这种办法能够满足咱们的需要，即任意一个 T 的时间段内，申请次数都小于 R 次。
上面是一个简略的实现：
defmodule Limit do use GenServer @n 30 @_R 100 # ms @_T 1000 def req() do GenServer.call(__MODULE__, :req) end def start() do if GenServer.whereis(__MODULE__) do GenServer.stop(__MODULE__) end GenServer.start_link(__MODULE__, :ok, name: __MODULE__) end def init(_) do :timer.send_interval(div(@_T, @n), :update) {:ok, %{ queue: :queue.from_list(List.duplicate(0, @n)), r_max: @_R, r: 0 }} end def handle_call(:req, _from, state = %{r: r, r_max: r_max}) do r = r + 1 if r <= r_max do {:reply, :ok, %{state | r: r}} else {:reply, {:error, :limit}, state} end end def handle_info(:update, state = %{r: r, queue: q}) do ## debug # :queue.to_list(q) |> IO.inspect() {_, q} = :queue.out(q) q = :queue.in(r, q) s = :queue.fold(fn x, acc -> x + acc end, 0, q) r_max = @_R - s {:noreply, %{state | r: 0, r_max: r_max, queue: q}} endend测试用例：
defmodule LimitTest do use ExUnit.Case test "100 request at same time should all return ok" do Limit.start() r = for _ <- 1..100 do Limit.req() end |> Enum.all?(fn x -> x == :ok end) assert r end test "101 request at same time should return 100 ok and 1 error at last req" do Limit.start() r = for _ <- 1..100 do Limit.req() end |> Enum.all?(fn x -> x == :ok end) assert r assert Limit.req() == {:error, :limit} end test "request capacity should re-fill after 1 second (500 ms more to avoid race)" do Limit.start() for _ <- 1..100 do Limit.req() end :timer.sleep(1500) assert Limit.req() == :ok endend这种基于历史状态的算法在很多畛域都用被利用，例如比特币网络中会依据过来一段时间的出块速度来调整以后的工作量证实难度，以使得出块工夫放弃在 10 分钟左右。