Different algorithms and structures have been used to solve ratelimiting. In this post I want to focus on use of probabilistic method & countmin sketch in particular.
Why
To save space or time. It approximates the result.
There is extensive research on solving the membership problem using data structures from hash tables to balanced trees and Btree indices, and these form the backbone of systems from OSs, compilers, databases and beyond. Many of these data structures have been in widespread use for forty or more years.
Countmin consumes a stream of events and produces approximate frequency of each of the events. It can be queried for frequency of a certain event and it will return the frequency of that event with certain probability.
Usage
Compressed sensing, Networking, Databases, NLP, Security (cryptography, finding primes), Computation Geometry (finding vertices), Machine Learning.
Implementation
Simple python implementation from github.
[code lang=python]
def query(self, x):
“””
Return an estimation of the amount of times
x
has occurred. The returned value always
overestimates the real value.
“””
return min(table[i] for table, i in zip(self.tables,
self._hash(x))
[/code]
References

CountMin C Implementation  https://sites.google.com/site/countminsketch/home

CountMin Go Implementation  https://github.com/tylertreat/BoomFilters

Algorithms to live by  http://algorithmstoliveby.com/

CImplementation  http://www.cs.rutgers.edu/∼muthu/ massdalcodeindex.html