关于后端:编程随想基于历史状态的算法

最近想到一个对于限流的问题，比方一个 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}}
  end
end

测试用例：

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
  end
end

这种基于历史状态的算法在很多畛域都用被利用，例如比特币网络中会依据过来一段时间的出块速度来调整以后的工作量证实难度，以使得出块工夫放弃在 10 分钟左右。