Inconsistent Bucket Duration in Hammer for Periodic Rate Limits

[vijayakumarkarthik]

Describe the bug
In the current implementation of Hammer, the bucket duration can be less than the specified period depending on the precise moment a request is received.
For example, with a 10-second period, requests made at 5 seconds past the epoch will result in a bucket duration of only 5 seconds instead of 10.

1. Configure Hammer with a period of 10 seconds.
2. Make repeated requests at intervals that are not aligned with the period boundary.
3. Observe that the bucket duration varies and does not consistently represent the full time period.

defmodule MyAppWeb.TestRateLimiter do
  alias Hammer

  def test_rate_limit() do
    key = "test_key"
    limit = 1
    period = 10 * 1_000 # 10 seconds
    IO.inspect(Hammer.check_rate(key, limit, period))
    :timer.sleep(2_000)
    IO.inspect(Hammer.check_rate(key, limit, period))
    :timer.sleep(2_000)
    IO.inspect(Hammer.check_rate(key, limit, period))
  end 
end

** Provide the following details

• Elixir version (elixir -v): 1.17.2
• Erlang version (erl -v): 14.2.5.2
• Operating system:

Expected behavior
When configuring a rate limit with a specified period (e.g., 10 seconds), each bucket should consistently cover the full time period. For example, a 10-second period should always represent a 10-second window, regardless of when the request is made within that period.

Actual behavior
The bucket duration can be less than the specified period. For example, with a 10-second period, requests made at 5 seconds past the epoch result in a bucket duration of only 5 seconds instead of 10. This leads to premature allowance of requests within the same time window.

def stamp_key(id, scale_ms) do
  stamp = DateTime.to_unix(DateTime.utc_now(), :millisecond)
  bucket_number = div(stamp, scale_ms) * scale_ms
  key = {bucket_number, id}
  {stamp, key}
end

[epinault]

I ll see if I can look into it but PR welcome too if you have a solution

[ruslandoga]

👋

I don't know about other backends, but this is unlikely to be implemented with ETS. Or at least with the default ETS backend, since (I think) not everyone needs that and it would be slower ... unless there is some clever trick available that I am not seeing.

---

UPDATE: I was updating the guides and noticed that Hammer says it uses token bucket rate limiting, but in reality it uses a fixed winder counter. So maybe it makes sense to actually implement token bucket rate limiting? Otherwise it's probably a bit confusing. For now I updated the tutorial in #104 to describe the current algorithm as a fixed winder counter.

[epinault]

yea as I was looking back this is because it is a fixed window counter. I think this is fine to have it be the default.
we could look at adding

Sliding Window https://www.rdiachenko.com/posts/arch/rate-limiting/sliding-window-algorithm/ as well as Leaky Bucket support?

[ruslandoga]

Yeah, sliding window is easy to implement, here's a clean example, but it's slow. For users with expensive resources, on which they rate limit to like one per hour (#99) it might be a reasonable trade off. Maybe we can have a periodic benchmark of all official backends / algorithms running in CI to make it easier for people to choose.

---

Regarding the API, maybe the chosen algorithm could be passed at module definition:

defmodule MyApp.RateLimit do
  use Hammer, backend: :ets, algorithm: :fixed_window # default
end

defmodule MyApp.RateLimit do
  use Hammer, backend: :ets, algorithm: :sliding_window
end

# etc.

It would then be up to the backend to implement the algorithm. If any option is not supported by the backend, it should raise an error.

Alternatively each algorithm+storage could be a new backend:

defmodule MyApp.RateLimit do
  use Hammer, backend: :fixed_window_ets
end

defmodule MyApp.RateLimit do
  use Hammer, backend: :sliding_window_ets
end

# etc.

---

UPDATE: Ah, no. The above wouldn't work since the current public API relies on scale to be passed in.

[epinault]

I think we need to have a backend (ETS, redis) separted to how they use the window. I think we need to extract that later into something configurable but defaulting on the current way. So your first approach with algorithm is the wya I would approach it