Skip to content

Latest commit

 

History

History
139 lines (115 loc) · 6.38 KB

LIMITERS.md

File metadata and controls

139 lines (115 loc) · 6.38 KB
Raw

Redis Lua script rate limiters

PlugLimit is using Redis Lua scripts to perform following tasks:

  1. Establish if given request should be allowed or denied.
  2. Determine rate limiting http headers values.

Redis Lua scripts must internally manage request counters as Redis keys, sets or hashes to provide rate limiting functionality.

All tasks listed above must be executed as a single check-and-set Redis Lua script operation.

Input

Redis Lua script input is a concatenation of two PlugLimit configuration keys values: :key MFA tuple derivative and :opts. Please refer to PlugLimit module documentation for detailed configuration description.

Redis Lua scripts should accept following input parameters sourced from Elixir code:

  1. List of all Redis keys used by a script. Keys are generated by user function specified with :key MFA tuple. Keys list should especially include an unique name used by script to create Redis key/set/hash counting requests.
  2. List of rate limiting algorithm options set with :opts configuration key.

Example Redis Lua script input for built-in :fixed_window limiter (Elixir syntax):

["my_protected_pipeline_name:12345", 10, 60]

Fixed window Lua script will use the first list value for the Redis key name - used to store given request group requests counter. Remaining list elements correspond to the fixed window rate limiting algorithm options :opts: 10 requests are allowed in 60 seconds time window. Number and order of :opts parameters depends on the individual Redis Lua script implementation.

Output

Redis Lua script output is passed as an argument to the PlugLimit.put_response/4 function or user provided equivalent response function as a third argument. Redis Lua script output format might differ from specification given below if user is using customized response function implementation.

Redis Lua script compatible with PlugLimit.put_response/4 function should return a list with following items:

  1. String "allow" | "deny" specifying if given request should be allowed or denied.
  2. List of http headers values consistent with a list of http headers keys defined with :headers configuration key.
  3. Other optional output parameters. Optional script output is ignored by built-in PlugLimit.put_response/4.

Rate limiting http response headers should comply with "RateLimit Fields for HTTP" IETF specification.

Example Redis Lua script output for the built-in :fixed_window limiter (Elixir syntax):

["allow", ["10", "60", "9"]]

Output above means that request should be allowed and following http headers should be set:

"x-ratelimit-limit" => "10"
"x-ratelimit-reset" => "60"
"x-ratelimit-remaining" => "9"

Custom Redis Lua scripts can overwrite individual http headers keys if required, for example:

["allow", ["10", ["x-acme-header", "60"], "9"]]

Output above will translate to the following http headers when using PlugLimit.put_response/4 with :headers set as for :fixed_window:

"x-ratelimit-limit" => "10"
"x-acme-header" => "60"
"x-ratelimit-remaining" => "9"

Fixed window

Algorithm is selected by setting limiter: :fixed_window in a plug call. Fixed window algorithm assumes that timeline is divided into windows of a fixed length, for example 60 seconds. Time window is associated with requests counter set initially to the requests limit value, for example limit 10 requests in 60 seconds time window. Request counter is decreased by one on each request. If current request counter value is greater than zero request is allowed, otherwise rate limit was exceeded and request is denied. Requests counter is reset to original state after time window seconds number.

Pros:

  • Simplicity which translates into high performance.
  • Simple key => value is sufficient to store rate-limiter state, which means minimal Redis memory requirements.

Cons:

  • Requests limit might be consumed by potential attacker in a single burst, which might put increased pressure on the server resources.

Inputs:

  • function set by :key value should return list with a single string. String will be used as a Redis key name.
  • :opts should provide list with two integers: 1. requests limit and 2. time window length in seconds.

Output list:

  • string "allow" | "deny",
  • list of three http headers values in a following order: ["x-ratelimit-limit", "x-ratelimit-reset", "x-ratelimit-remaining"]

Token bucket

Algorithm is selected by setting limiter: :token_bucket in a plug call. Token bucket algorithm is based on an analogy of a fixed capacity bucket filled with tokens. Initial amount of tokens in the bucket is equal to the burst value. On each request one token is removed from the bucket. If bucket is empty request is denied. Tokens in the bucket are added with a constant rate calculated in PlugLimit implementation as: (limit - burst) / time_window_length. For example: if time window length is set to 60 seconds, limit is equal 15 requests and burst equal to 3 requests, tokens will be added at the rate 0.2 tokens per second, or in other words new token will be added every 5 seconds. Bucket is reset to original state every time window length seconds.

Pros:

  • Protected endpoint traffic is smoother than in case of fixed window algorithm, which translates into smoother server load.

Cons:

  • More complex implementation than fixed window, translating into more Redis CPU resources usage.
  • Limiter state is stored as a Redis hash with three numeric values: remaining requests count, tokens count and timestamp. It means higher Redis memory requirements than for a fixed window algorithm.

Inputs:

  • function set by :key value should return list with a single string. String will be used as a Redis hash name.
  • :opts should provide list with three integers in a following order:
    1. requests limit, 2. time window length in seconds and 3. allowed initial requests burst count.

Output list:

  • string "allow" | "deny",
  • list of three or four http headers values depending on a bucket tokens count. If limiter's bucket is filled with tokens three http headers values are returned: ["x-ratelimit-limit", "x-ratelimit-reset", "x-ratelimit-remaining"]. If bucket is empty, additional header "retry-after" is returned. "retry-after" header specifies amount of time in seconds required for user agent to wait for making a new request.