Class: TrafficJam::GCRALimit

Inherits:
Limit
  • Object
show all
Defined in:
lib/traffic_jam/gcra_limit.rb

Overview

GCRA (Generic Cell Rate Algorithm) is a leaky bucket type rate limiting algorithm. GCRA works by storing a key in Redis with a ms-precision expiry representing the time that the limit will be completely reset. Each increment operation converts the increment amount into the number of milliseconds to be added to the expiry.

When a request comes in, we take the existing expiry value, subtract a fixed amount representing the limit’s total burst capacity from it, and compare the result to the current time. This result represents the next time to allow a request. If it’s in the past, we allow the incoming request, and if it’s in the future, we don’t. After a successful request, a new expiry is calculated. (see brandur.org/rate-limiting)

This limit type does not support decrements or changing the max value without a complete reset. This means that if the period or max value for an action/value key changes, the used and remaining values cannot be preserved.

Example: Limit is 5 per 10 seconds.

An increment by 1 first sets the key to expire in 2s.
Another immediate increment by 4 sets the expiry to 10s.
Subsequent increments fail until clock time catches up to expiry

Instance Attribute Summary

Attributes inherited from Limit

#action, #max, #period, #value

Instance Method Summary collapse

Methods inherited from Limit

#exceeded?, #flatten, #increment!, #initialize, #limit_exceeded, #remaining, #reset

Constructor Details

This class inherits a constructor from TrafficJam::Limit

Instance Method Details

#decrement(_amount = 1, time: Time.now) ⇒ Object

Decrement the amount used by the given number.

Parameters:

  • amount (Integer) —

    amount to decrement by

  • time (Time) (defaults to: Time.now) —

    time is ignored

Raises:

  • (NotImplementedError) —

    decrement is not defined for SimpleLimit



76
77
78
 
# File 'lib/traffic_jam/gcra_limit.rb', line 76

def decrement(_amount = 1, time: Time.now)
  raise NotImplementedError, "decrement is not defined for SimpleLimit"
end

#increment(amount = 1, time: Time.now) ⇒ Boolean

Increment the amount used by the given number. Does not perform increment if the operation would exceed the limit. Returns whether the operation was successful.

Parameters:

  • amount (Integer) (defaults to: 1) —

    amount to increment by

  • time (Time) (defaults to: Time.now) —

    time is ignored

Returns:

  • (Boolean) —

    true if increment succeded and false if incrementing would exceed the limit

Raises:

  • (ArgumentError) 


35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
# File 'lib/traffic_jam/gcra_limit.rb', line 35

def increment(amount = 1, time: Time.now)
  return true if amount == 0
  return false if max == 0
  raise ArgumentError.new("Amount must be positive") if amount < 0

  if amount != amount.to_i
    raise ArgumentError.new("Amount must be an integer")
  end

  return false if amount > max

  incrby = (period * 1000 * amount / max).to_i
  argv = [incrby, period * 1000]

  result =
    begin
      redis.evalsha(
        Scripts::INCREMENT_GCRA_HASH, keys: [key], argv: argv)
    rescue Redis::CommandError
      redis.eval(Scripts::INCREMENT_GCRA, keys: [key], argv: argv)
    end

  case result
  when 0
    return true
  when -1
    raise Errors::InvalidKeyError, "Redis key #{key} has no expire time set"
  when -2
    return false
  else
    raise Errors::UnknownReturnValue,
          "Received unexpected return value #{result} from " \
          "increment_gcra eval"
  end
end

#key_prefix ⇒ Object 



97
98
99
 
# File 'lib/traffic_jam/gcra_limit.rb', line 97

def key_prefix
  "#{config.key_prefix}:s"
end

#used ⇒ Integer

Return amount of limit used, taking time drift into account.

Returns:

  • (Integer) —

    amount used



83
84
85
86
87
88
89
90
91
92
93
94
95
 
# File 'lib/traffic_jam/gcra_limit.rb', line 83

def used
  return 0 if max.zero?

  expiry = redis.pttl(key)
  case expiry
  when -1  # key exists but has no associated expire
    raise Errors::InvalidKeyError, "Redis key #{key} has no expire time set"
  when -2  # key does not exist
    return 0
  end

  (max * expiry / (period * 1000.0)).ceil
end