The “token bucket” algorithm is often used in packet switched computer networks and telecommunications networks to rate-limit or throttle traffic flows. The Wikipedia article in this link provides more information.
We had a need to implement a light-weight rate-limiting system on the login forms which protect our Registrar Console and other internal systems. We have a wide range of security measures in place to prevent brute-force attacks against accounts with weak passwords, such as two-factor authentication, auto-locking of accounts after too many failed logins, and so on, but we had no protection against brute-force password reuse attacks such as the one that recently hit GitHub.
After we received a report through our bug bounty program we decided that we needed to implement rate-limiting at the IP address level. The token bucket approach seemed like a good one, because we would only need to store two pieces of data about each IP address: an integer containing the number of tokens in its bucket, and a timestamp recording when the bucket was last “topped up”.
Rather than use a relational database to store this information we chose to use memcached, since it’s very fast, we already have a memcached system running at each of our operations centres, and the data doesn’t need to be persistent in the long term.
Since our registry system is written in PHP, we needed an implementation of the token bucket algorithm in that language. Some existing implementations already exist, but were not compatible with the (rather old) operating system and PHP version we currently have deployed in production, so we need to roll our own. This was then integrated into the general-purpose “CRC” foundation library which supports our registry software, and which is also used by our some of sister companies.
Here’s the core of the implementation, an object method which returns a boolean if the client has hit a rate limit. The key() method is a way of turning a client identifer such as an IP address into a key that is unique for the specific application. The cache object property is an instance of the memcache class (not to be confused with the memcached class, no, we don’t know why PHP has two memcached client classes either!).