Dalli::RateLimiter

Dalli::RateLimiter provides arbitrary Memcached-backed rate limiting for your Ruby applications. You may be using an application-level rate limiter such as Rack::Ratelimit, Rack::Throttle, or Rack::Attack, or something higher up in your stack (like an Nginx zone or HAproxy stick-table). This is not intended to be a replacement for any of those functions. Your application may not even be a web service and yet you find yourself needing to throttle certain types of operations.

This library allows you to impose specific rate limits on specific functions at whatever granularity you desire. For example, you have a function in your Ruby web application that allows users to change their username, but you want to limit these requests to two per hour per user. Or your command-line Ruby application makes API calls over HTTP, but you must adhere to a strict rate limit imposed by the provider for a certain endpoint. It wouldn't make sense to apply these limits at the application level—it would be much easier to tightly integrate a check within your business logic.

Dalli::RateLimiter leverages the excellent Dalli and ConnectionPool gems for fast and efficient Memcached access and thread-safe connection pooling. It uses an allowance counter and floating timestamp to implement a sliding window for each unique key, enforcing a limit of m requests over a period of n seconds. If you're familiar with Sidekiq (which is another excellent piece of software, written by the same person who wrote Dalli and ConnectionPool), it is similar to the Window style of the Sidekiq::Limiter class, although the invocation syntax differs slightly (see Block Form below for an example of the differences).

It supports arbitrary unit quantities of consumption for partial operations or for operations that logically count as more than one request (i.e. batched requests). It leverages Memcached's compare-and-set method—which uses an opportunistic locking scheme—in combination with a back-off algorithm to mitigate race conditions while ensuring that limits are enforced under high levels of concurrency with a high degree of confidence. Math operations are performed with floating-point precision.

Installation

Add this line to your application's Gemfile:

gem 'dalli-rate_limiter', '~> 0.2.0'

And then execute:

$ bundle install

Or install it yourself as:

$ gem install dalli-rate_limiter

Basic Usage

def do_foo
  lim = Dalli::RateLimiter.new

  if lim.exceeded?
    fail "Sorry, can't foo right now. Try again later!"
  end

  # Do foo...
end

Dalli::RateLimiter will, by default, create a ConnectionPool with its default options, using a block that yields Dalli::Client instances with its default options. If MEMCACHE_SERVERS is set in your environment, or if your Memcached instance is running on localhost, port 11211, this is the quickest way to get started. Alternatively, you can pass in your own single-threaded Dalli::Client instance—or your own multi-threaded ConnectionPool instance (wrapping Dalli::Client)—as the first argument to customize the connection settings. Pass in nil to force the default behavior.

The library itself defaults to five (5) requests per eight (8) seconds, but these can easily be changed with the :max_requests and :period options. Locking can be fine-tuned by setting the :lock_timeout option. A :key_prefix option can be specified as well; note that this will be used in combination with any :namespace option defined in the Dalli::Client.

The Dalli::RateLimiter instance itself is not stateful, so it can be instantiated as needed (e.g. in a function definition) or in a more global scope (e.g. in a Rails initializer). It does not mutate any of its own attributes so it should be safe to share between threads; in this case, you will definitely want to use either the default ConnectionPool or your own (as opposed to a single-threaded Dalli::Client instance).

The main instance method, #exceeded? will return false if the request is free to proceed. If the limit has been exceeded, it will return a positive floating point value that represents the fractional number of seconds that the caller should wait until retrying the request. Assuming no other requests were process during that time, the retried request will be free to proceed at that point. When invoking this method, please be sure to pass in a key that is unique (in combination with the :key_prefix option described above) to the thing you are trying to limit. An optional second argument specifies the number of requests to "consume" from the allowance; this defaults to one (1).

Please note that if the number of requests is greater than the maximum number of requests, the limit will never not be exceeded. Consider a limit of 50 requests per minute: no amount of waiting would ever allow for a batch of 51 requests! #exceeded? returns -1 in this event. To help detect this edge case proactively, a public getter method #max_requests is available.

An alternative block-form syntax is available using the #without_exceeding method. This method will call sleep on your behalf until the block can be executed without exceeding the limit, and then yield to the block. This is useful in situations where you want to avoid writing your own sleep-while loop. You can limit how long the method will sleep by passing in a :wait_timeout option; please note that the total wait time includes any time spent acquiring the lock.

Advanced Usage

dalli = ConnectionPool.new(:size => 5, :timeout => 3) {
  Dalli::Client.new(nil, :namespace => "myapp")
}

lim1 = Dalli::RateLimiter.new dalli,
  :key_prefix => "username-throttle", :max_requests => 2, :period => 3_600

lim2 = Dalli::RateLimiter.new dalli,
  :key_prefix => "widgets-throttle", :max_requests => 10, :period => 60

def change_username(user_id, new_username)
  if lim1.exceeded? user_id
    halt 422, "Sorry! Only two username changes allowed per hour."
  end

  # Change username...
rescue Dalli::RateLimiter::LockError
  # Unable to acquire a lock...
end

def add_widgets(foo_id, some_widgets)
  if some_widgets.length > lim2.max_requests
    halt 400, "Too many widgets!"
  end

  if time = lim2.exceeded?(foo_id, some_widgets.length)
    halt 422, "Sorry! Unable to process request. " \
      "Please wait at least #{time} seconds before trying again."
  end

  # Add widgets...
rescue Dalli::RateLimiter::LockError
  # Unable to acquire a lock...
end

Block Form

Rewriting the Sidekiq::Limiter.window example from its documentation:

def perform(user_id)
  user_throttle = Dalli::RateLimiter.new nil,
    :key_prefix => "stripe", :max_requests => 5, :period => 1

  user_throttle.without_exceeding(user_id, 1, :wait_timeout => 5) do
    # call stripe with user's account creds
  end
rescue Dalli::RateLimiter::LimitError
  # Unable to execute block before wait timeout...
rescue Dalli::RateLimiter::LockError
  # Unable to acquire a lock...
end

You have the flexibility to set the :key_prefix to nil and pass in "stripe:#{user_id}" as the first argument to #without_exceeding, with same end results. Or, likewise, you could set :key_prefix to "stripe:#{user_id}" and pass in nil as the first argument to #without_exceeding. Sometimes it makes sense to share an instance between method calls, or indeed between different methods, and sometimes it doesn't. Please note that if :key_prefix and the first argument to #exceeded? or #without_exceeding are both nil, Dalli::Client will abort with an ArgumentError ("key cannot be blank").

Compatibility

Dalli::RateLimiter is compatible with Ruby 1.9.3 and greater and has been tested with frozen string literals under Ruby 2.3.0. It has also been tested under Rubinius 2.15 and 3.14, and JRuby 1.7 (in 1.9.3 execution mode) and 9K.

You might consider installing the kgio gem to give Dalli a 10-20% performance boost.

Caveats

A rate-limiting system is only as good as its backing store, and it should be noted that a Memcached ring can lose members or indeed its entire working set (in the event of a flush operation) at the drop of a hat. Mission-critical use cases, where repeated operations absolutely, positively have to be restricted, should probably seek solutions elsewhere.

The limiting algorithm, which was overhauled for the 0.2.0 release to greatly reduce the number of round-trips to Memcached, seems to work well but it is far from battle-tested. Simple benchmarking against a local Memcached instance shows zero lock timeouts with the default settings and 100 threads hitting the same limit concurrently. (Testing performed on a 2012 MacBook Pro with an Intel i7-3615QM processor and 16 GB RAM; benchmarking scripts available in the bin subdirectory of this repository.)

As noted above, this is not a replacement for an application-level rate limit, and if your application faces the web, you should probably definitely have something else in your stack to handle e.g. a casual DoS.

Make sure your ConnectionPool has enough slots for these operations. I aim for one slot per thread plus one or two for overhead in my applications.

Documentation

This README is fairly comprehensive, but additional information about the class and its methods is available in YARD.

Development

After checking out the repo, run bin/setup to install dependencies. Then, run rake spec to run the tests. You can also run bin/console for an interactive prompt that will allow you to experiment.

To install this gem onto your local machine, run bundle exec rake install. To release a new version, update the version number in version.rb, and then run bundle exec rake release, which will create a git tag for the version, push git commits and tags, and push the .gem file to rubygems.org.

Contributing

Bug reports and pull requests are welcome on GitHub at https://github.com/mwpastore/dalli-rate_limiter.

License

The gem is available as open source under the terms of the MIT License.