Rate limiting
Rate limiting regulates how much or how frequently a resource is used or accessed by consumers. In the following three examples, we demonstrate increasing levels of sophistication in allocation of resource usage. The examples are all written in Java. In all three cases, cells (the messages or the items) arrive at random times. The business use case sets a limit on how many cells can arrive in a stipulated time window. The algorithm maintains the history of cell arrivals and decides whether the new cell is good to go or not. The diagram below shows the design of the solution. All the code samples can be accessed at https://github.com/redislabsdemo/RateLimiter.
Redis Labs Class diagram of RateLimiter and its sub-classes.
Example 1: BurstyRateLimiter
In this implementation, the rate limiter allows cells to arrive in bursts. For example, if the use case has a rule that allows 1,000 cells in an hour, this class allows up to 1,000 cells in the first second. In other words, this algorithm doesn’t check for bursts, but allows the specified number of cells within a time window. The solution uses Redis’s Sorted Set data structure.
public class BurstyRateLimiter extends RateLimiter
{
private String key ="BurstyRateLimiter"; //default key
private int window = 3600; // in seconds. 1 hr default
private int actions = 360; // 1 action every 10 seconds
.
.
// Returns true if the arrival of the cell is within the acceptance
// rate, false if not.
public boolean arrival(String cell){
long currentTime = System.currentTimeMillis();
long lastWindow = (currentTime - (window * 1000))/1000;
//delete all messages outside the window
jedis.zremrangeByScore(key, “0”, Long.toString(lastWindow));
//is zcard less than the allowed number of actions
long card = jedis.zcard(key);
//If yes, add message to the sorted set and return true
if(card < actions){
jedis.zadd(key, (currentTime/1000), cell);
return true;
}
return false;
}
}
Example 2: UniformRateLimiter
The UniformRateLimiter class avoids bursts by spreading out the arrival of cells throughout the time window. For example, if the use case allows 60 cells in an hour, this class allows only one cell every minute. This uses the time-to-live feature of Redis keys.
public class UniformRateLimiter extends RateLimiter
{
private String key ="UniformRateLimiter"; //default key
private int window = 3600; // in seconds. 1 hr default
private int actions = 360; // 1 action every 10 seconds
private int interval = window/actions; //
.
.
.
// Returns true if the arrival of the cell is within the acceptance
// rate, false if not.
public boolean arrival(String cell){
// check if the last message exists.
long ttl = jedis.ttl(key);
if(ttl > 0){
return false;
}
// The key lives through the period defined by the interval
if(key != null && cell != null){
jedis.setex(key, interval, cell);
return true;
}
return false;
}
}
Example 3: SimpleCellRateLimiter
Unlike the previous two examples, this algorithm queues up all of the cells in Redis’s List data structure. It then uses the UniformRateLimiter class to determine when to pop a cell from the List.
public class SimpleCellRateLimiter extends RateLimiter implements Runnable{
private String key ="SimpleCell"; //default key
private RateLimiter uniformRateLimiter = null;
public SimpleCellRateLimiter(Properties props) throws Exception{
super();
props.setProperty(“type”, RateLimiterFactory.DISTRIBUTION_TYPE_UNIFORM);
uniformRateLimiter = RateLimiterFactory.getRateLimiter(props);
Thread t = new Thread(this);
t.start();
}
// This arrival method is different from the previous two examples.
// In this example, the program queues up the cell in a List
// data structure. A separate thread checks whether popping the cell
// is within the acceptance rate.
public boolean arrival(String cell){
// Push the cell to the List
jedis.lpush(key, cell);
return true;
}
public void run(){
try{
RedisConnection conn = RedisConnection.getRedisConnection();
Jedis jedis = conn.getJedis();
while(true){
String cell = jedis.rpop(key);
boolean success = false;
while(!success){
success = uniformRateLimiter.arrival(cell);
if(success){
// Take action here.....
System.out.println(“Out: “
+(System.currentTimeMillis()/1000)+” “
+cell);
}
}
}
}catch(Exception e){
e.printStackTrace();
}
}
}Note that Redis has a module for rate limiting called Redis-cell. Redis-cell implements the sophisticated Generic Cell Rate Algorithm and provides a single command to manage rate limiting (http://redismodules.com/modules/redis-cell/). It offers a language agnostic rate limiter for applications that have Redis as part of their software stack. As a Redis module, redis-cell enjoys full benefits of Redis’ in-memory processing, internal data structures, scalability, and high-availability. It plugs into open source Redis 4.0 seamlessly.
Redis offers powerful tools and capabilities to meet the metering needs of various scenarios. It offers highly optimized data structures and commands that simplify counting and metering at scale. Its single-threaded processing gives you a lock-free architecture by default, while its atomic metering commands ensure data consistency. And Redis has been shown to deliver millions of operations per second with sub-millisecond latency on modest hardware, helping you to address metering implementation challenges in a cost-effective way.
—
New Tech Forum provides a venue to explore and discuss emerging enterprise technology in unprecedented depth and breadth. The selection is subjective, based on our pick of the technologies we believe to be important and of greatest interest to InfoWorld readers. InfoWorld does not accept marketing collateral for publication and reserves the right to edit all contributed content. Send all inquiries to newtechforum@infoworld.com.