Class: Dalli::RateLimiter

Inherits:
Object
  • Object
show all
Defined in:
lib/dalli/rate_limiter.rb,
lib/dalli/rate_limiter/version.rb

Overview

Dalli::RateLimiter provides arbitrary Memcached-backed rate limiting for your Ruby applications.

See Also:

Constant Summary collapse

LockError = 
Class.new RuntimeError
LimitError = 
Class.new RuntimeError
DEFAULT_OPTIONS = 
{
  :key_prefix => "dalli-rate_limiter",
  :max_requests => 5,
  :period => 8,
  :lock_timeout => 30
}.freeze
VERSION = 
"0.2.0"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(dalli = nil, options = {}) ⇒ RateLimiter

Create a new instance of Dalli::RateLimiter.

Parameters:

  • dalli (ConnectionPool, Dalli::Client) (defaults to: nil) —

    the Dalli::Client (or ConnectionPool of Dalli::Client) to use as a backing store for this rate limiter

  • options (Hash) (defaults to: {}) —

    configuration options for this rate limiter

Options Hash (options):

  • :key_prefix (String, #to_s) — default: "dalli-rate_limiter" —

    a unique string describing this rate limiter

  • :max_requests (Integer, Float) — default: 5 —

    maximum number of requests over the governed interval

  • :period (Integer, Float) — default: 8 —

    number of seconds over which to enforce the maximum number of requests

  • :lock_timeout (Integer, Float) — default: 30 —

    maximum number of seconds to wait for the lock to become available



44
45
46
47
48
49
50
51
52
53
 
# File 'lib/dalli/rate_limiter.rb', line 44

def initialize(dalli = nil, options = {})
  @pool = dalli || ConnectionPool.new { Dalli::Client.new }

  options = normalize_options options

  @key_prefix = options[:key_prefix]
  @max_requests = options[:max_requests]
  @period = options[:period]
  @lock_timeout = options[:lock_timeout]
end

Instance Attribute Details

#max_requests ⇒ Float (readonly)

Returns the maximum number of requests.

Returns:

  • (Float) —

    the maximum number of requests



16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
 
# File 'lib/dalli/rate_limiter.rb', line 16

class RateLimiter
  LockError = Class.new RuntimeError
  LimitError = Class.new RuntimeError

  DEFAULT_OPTIONS = {
    :key_prefix => "dalli-rate_limiter",
    :max_requests => 5,
    :period => 8,
    :lock_timeout => 30
  }.freeze

  attr_reader :max_requests

  # Create a new instance of Dalli::RateLimiter.
  #
  # @param dalli [ConnectionPool, Dalli::Client] the Dalli::Client (or
  #   ConnectionPool of Dalli::Client) to use as a backing store for this
  #   rate limiter
  # @param options [Hash] configuration options for this rate limiter
  #
  # @option options [String, #to_s] :key_prefix ("dalli-rate_limiter") a
  #   unique string describing this rate limiter
  # @option options [Integer, Float] :max_requests (5) maximum number of
  #   requests over the governed interval
  # @option options [Integer, Float] :period (8) number of seconds over
  #    which to enforce the maximum number of requests
  # @option options [Integer, Float] :lock_timeout (30) maximum number of
  #    seconds to wait for the lock to become available
  def initialize(dalli = nil, options = {})
    @pool = dalli || ConnectionPool.new { Dalli::Client.new }

    options = normalize_options options

    @key_prefix = options[:key_prefix]
    @max_requests = options[:max_requests]
    @period = options[:period]
    @lock_timeout = options[:lock_timeout]
  end

  # Determine whether processing a given request would exceed the rate limit.
  #
  # @param unique_key [String, #to_s] a key to use, in combination with the
  #   optional `:key_prefix` and any `:namespace` defined in the
  #   Dalli::Client, to distinguish the item being limited from similar items
  # @param to_consume [Integer, Float] the number of requests to consume from
  #   the allowance (used to represent a partial request or a batch of
  #   requests)
  #
  # @return [false] if the request can be processed as given without
  #   exceeding the limit (including the case where the number to consume is
  #   zero)
  # @return [Float] if processing the request as given would exceed
  #   the limit and the caller should wait so many (fractional) seconds
  #   before retrying
  # @return [-1] if the number to consume exceeds the maximum, and the
  #   request as given would never not exceed the limit
  #
  # @raise [LockError] if a lock cannot be obtained before `@lock_timeout`
  def exceeded?(unique_key = nil, to_consume = 1)
    return false if to_consume <= 0
    return -1 if to_consume > max_requests

    key = [@key_prefix, unique_key].compact.join(":")
    to_consume = to_consume.to_f

    try = 1
    total_time = 0
    loop do
      @pool.with do |dc|
        result = dc.cas(key, @period) do |previous_value|
          wait, value = compute(previous_value, to_consume)
          return wait if wait > 0 # caller must wait
          value
        end

        # TODO: We can get rid of this block when Dalli::Client supports #cas!
        if result.nil?
          _, value = compute(nil, to_consume)
          result = dc.add(key, value, @period)
        end

        return false if result # caller can proceed
      end

      time = rand * Math.sqrt(try / Math::E)
      raise LockError, "Unable to lock key for update" \
        if time + total_time > @lock_timeout
      sleep time

      try += 1
      total_time += time
    end
  end

  # Execute a block without exceeding the rate limit.
  #
  # @param (see #exceeded?)
  # @param options [Hash] configuration options
  #
  # @option options [Integer] :wait_timeout maximum number of seconds to wait
  #   before yielding
  #
  # @yield block to execute within limit
  #
  # @raise [LimitError] if the block cannot be yielded to within
  #  `:wait_timeout` seconds without going over the limit
  # @raise (see #exceeded?)
  #
  # @return the return value of the passed block
  def without_exceeding(unique_key = nil, to_consume = 1, options = {})
    options[:wait_timeout] = options[:wait_timeout].to_f \
      if options[:wait_timeout]

    start_time = Time.now.to_f
    while time = exceeded?(unique_key, to_consume)
      raise LimitError, "Unable to yield without exceeding limit" \
        if time < 0 || options[:wait_timeout] && time + Time.now.to_f - start_time > options[:wait_timeout]
      sleep time
    end

    yield
  end

  private

  def compute(previous, to_consume)
    current_timestamp = Time.now.to_f

    previous ||= {}
    previous_allowance = previous[:allowance] || @max_requests
    previous_timestamp = previous[:timestamp] || current_timestamp

    allowance_delta = (current_timestamp - previous_timestamp) * @max_requests / @period
    projected_allowance = previous_allowance + allowance_delta
    if projected_allowance > @max_requests
      projected_allowance = @max_requests
      allowance_delta = @max_requests - previous_allowance
    end

    if to_consume > projected_allowance
      # Determine how long the caller must wait (in seconds) before retrying the request.
      wait = (to_consume - projected_allowance) * @period / @max_requests
    else
      current = {
        :allowance => previous_allowance + allowance_delta - to_consume,
        :timestamp => current_timestamp
      }
    end

    [wait || 0, current || previous]
  end

  def normalize_options(options)
    normalized_options = {}

    normalized_options[:key_prefix] = options[:key_prefix].to_s \
      if options.key? :key_prefix

    normalized_options[:max_requests] = options[:max_requests].to_f \
      if options[:max_requests] && options[:max_requests].to_f > 0

    normalized_options[:period] = options[:period].to_f \
      if options[:period] && options[:period].to_f > 0

    normalized_options[:lock_timeout] = options[:lock_timeout].to_f \
      if options[:lock_timeout] && options[:lock_timeout].to_f >= 0

    DEFAULT_OPTIONS.dup.merge! normalized_options
  end
end

Instance Method Details

#exceeded?(unique_key = nil, to_consume = 1) ⇒ false, ...

Determine whether processing a given request would exceed the rate limit.

Parameters:

  • unique_key (String, #to_s) (defaults to: nil) —

    a key to use, in combination with the optional ‘:key_prefix` and any `:namespace` defined in the Dalli::Client, to distinguish the item being limited from similar items

  • to_consume (Integer, Float) (defaults to: 1) —

    the number of requests to consume from the allowance (used to represent a partial request or a batch of requests)

Returns:

  • (false) —

    if the request can be processed as given without exceeding the limit (including the case where the number to consume is zero)

  • (Float) —

    if processing the request as given would exceed the limit and the caller should wait so many (fractional) seconds before retrying

  • (-1) —

    if the number to consume exceeds the maximum, and the request as given would never not exceed the limit

Raises:

  • (LockError) —

    if a lock cannot be obtained before ‘@lock_timeout`



74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
 
# File 'lib/dalli/rate_limiter.rb', line 74

def exceeded?(unique_key = nil, to_consume = 1)
  return false if to_consume <= 0
  return -1 if to_consume > max_requests

  key = [@key_prefix, unique_key].compact.join(":")
  to_consume = to_consume.to_f

  try = 1
  total_time = 0
  loop do
    @pool.with do |dc|
      result = dc.cas(key, @period) do |previous_value|
        wait, value = compute(previous_value, to_consume)
        return wait if wait > 0 # caller must wait
        value
      end

      # TODO: We can get rid of this block when Dalli::Client supports #cas!
      if result.nil?
        _, value = compute(nil, to_consume)
        result = dc.add(key, value, @period)
      end

      return false if result # caller can proceed
    end

    time = rand * Math.sqrt(try / Math::E)
    raise LockError, "Unable to lock key for update" \
      if time + total_time > @lock_timeout
    sleep time

    try += 1
    total_time += time
  end
end

#without_exceeding(unique_key = nil, to_consume = 1, options = {}) { ... } ⇒ Object

Execute a block without exceeding the rate limit.

Parameters:

  • options (Hash) (defaults to: {}) —

    configuration options

  • unique_key (String, #to_s) (defaults to: nil) —

    a key to use, in combination with the optional ‘:key_prefix` and any `:namespace` defined in the Dalli::Client, to distinguish the item being limited from similar items

  • to_consume (Integer, Float) (defaults to: 1) —

    the number of requests to consume from the allowance (used to represent a partial request or a batch of requests)

Options Hash (options):

  • :wait_timeout (Integer) —

    maximum number of seconds to wait before yielding

Yields:

  • block to execute within limit

Returns:

  • the return value of the passed block

Raises:

  • (LimitError) —

    if the block cannot be yielded to within ‘:wait_timeout` seconds without going over the limit

  • (LockError) —

    if a lock cannot be obtained before ‘@lock_timeout`



125
126
127
128
129
130
131
132
133
134
135
136
137
 
# File 'lib/dalli/rate_limiter.rb', line 125

def without_exceeding(unique_key = nil, to_consume = 1, options = {})
  options[:wait_timeout] = options[:wait_timeout].to_f \
    if options[:wait_timeout]

  start_time = Time.now.to_f
  while time = exceeded?(unique_key, to_consume)
    raise LimitError, "Unable to yield without exceeding limit" \
      if time < 0 || options[:wait_timeout] && time + Time.now.to_f - start_time > options[:wait_timeout]
    sleep time
  end

  yield
end