Any multitenant service with public REST APIs needs to be able to protect itself from excessive usage by one or more tenants. Additionally, as the number of instances that support these services is dynamic and varies based on load, the need arrises to perform coordinated rate limiting on a per tenant, per endpoint\u00a0basis.<\/p>\n
Take the following scenario where a multitenant service has two endpoints:<\/p>\n
GET \/v1\/organizations\/{orgId}\/product\/{id}PUT \/v1\/organizations\/{orgId}\/product\/{id}<\/p>\n
Since a read operation is cheaper than a write operation, you may want limit them differently, say 100 calls per second vs. 10 calls per second. There is also a need to publish a service level agreement (SLA) about how often the service can be called to let integrating developers know what to expect when building out their applications. Finally, you don\u2019t want these numbers to change based on the number of instances running of the\u00a0service.<\/p>\n
For multitenant services, there is a need to make sure no organization can consume too much of the resources. For example, let\u2019s say both Org A and Org B are calling the service. While we promise horizontal scale to solve some of this problem, it isn\u2019t instantaneous. Excessive calls from Org A cannot be allowed to block calls from Org B from executing, even while the service is scaling\u00a0up.<\/p>\n
To solve this problem in a highly performant manner, we use a simple implementation of a Servlet Filter. This class makes use of defined per endpoint rate limits, a two layer cache, and a distributed counter.<\/p>\n
Note: this solution does perform strict rate limit checking. Due to running multiple independent, instances each org may go slightly over their limit during the last synchronization interval. We deemed this to be acceptable, as the goal is to be highly performant and protect the service, not to be completely strict.<\/em><\/p>\n The first step in this process is defining the rate limit definitions; how often can a given endpoint be called per organization? To do this, the limits are defined in YAML, which can easily be read by any application.<\/p>\n slas: The above definition defines limits for both getting and creating\/updating products.<\/p>\n For get product, a limit of 1000 calls enforced on a 10 second boundary is\u00a0defined.For put product, a limit of 100 calls enforced on a 10 second boundary is\u00a0defined.<\/p>\n You might ask, \u201cWhy don\u2019t we just define them per second?\u201d The answer is that we want to handle bursts, but still protect ourselves. By increasing the window size, the bursty nature of the traffic can be supported.<\/p>\n It is also possible to define multiple tiers. In that case, all tiers must pass evaluation. For example, 10 calls in 1 second but no more than 50 in 10 seconds. Again, this allows supporting the bursty nature of API calls while still managing the overall throughput allowed.<\/p>\n In order to solve the coordination problem between multiple instances of the service, a distributed counter is used (See \u201cA Deeper Look\u201d below for details of the key<\/em>). The counter is then synchronized out to a distributed cache so that an accurate count across all instances of the service can be maintained.<\/p>\n This information is then matched up with the rate limit definitions that determine how often an API can be invoked over what period of time. This period of time is used as a window that maintains the count until the limit\u00a0resets.<\/p>\n Now that per tenant, per endpoint limits are enforced, the caller of the API needs to be informed of what they are allowed to do. To do this, the following headers are returned with each API\u00a0call.<\/p>\n x-ratelimit-limit: number of calls allowed in the time\u00a0windowx-ratelimit-remaining: number of remaining calls that can be made in time\u00a0windowx-ratelimit-reset: number of seconds remaining in the time\u00a0window<\/p>\n If the caller has exceeded the limit, a 429 \u201cToo Many Requests\u201d error is returned, and the caller needs to back off for the remaining time in the\u00a0window.<\/p>\n Note: The format of x-ratelimit-XXX, while not an <\/em>RFC<\/em><\/a>, is commonly used by SaaS services such as Github and\u00a0Twitter.<\/em><\/p>\n The Counter\u2019s Key<\/strong><\/p>\n To ensure uniqueness, the counter needs to include the tenant (or org) ID, the endpoint (minus any variables within the path), the HTTP method being invoked, and the start and end time in its\u00a0name.<\/p>\n So then, how do we compute the start and end\u00a0time?<\/p>\n As shown above, each rate limit definition has a \u201cperiod\u201d or window over which it is enforced. In the example, this is 10\u00a0seconds.<\/p>\n To compute the window start time and end time, the following algorithm is used. This will always truncate the current system time to the nearest bucket as long as it is within the\u00a0window.<\/p>\n long windowTime = 10000; \/\/ 10 seconds in milliseconds Once a new window begins, the key automatically changes to the new start\u00a0time.<\/p>\n Let\u2019s take the example of a system time of 162731878077 (which is 2021\u201307\u201326 12:59:40.077).<\/p>\n Window Start = 162731878077 \/ 10000 = 16273187.8077 (truncated to 16273187 due to integer math) * 10000 = 162731870000Window End = 162731870000 + 10000 = 162731880000<\/p>\n 100 ms\u00a0later<\/p>\n Window Start = 162731878177 \/ 10000 = 16273187.8177 (truncated to 16273187) * 10000 = 162731870000Window End = 162731870000 + 10000 = 162731880000<\/p>\n Note: This algorithm favors simplicity in order to avoid having all instances synchronize the start time. What this means is that the first window may end up being short (roll over early), but all subsequent windows will match the desired\u00a0size.<\/em><\/p>\n A Two Layer Caching System with Automated Clean\u00a0Up<\/strong><\/p>\n As with any SaaS offering, minimizing the latency induced within an API call is crucial to success. For this implementation, a two layer caching system is used, one local to the service instance, that utilizes the library Caffeine<\/a>, and a second externalized via Redis. (These were chosen as they are lightweight, highly efficient, and support setting a time to live on an entry. Additionally, Redis supports atomic increment operations which allows for easily maintaining the distributed count).<\/p>\n This approach allows for choosing what interval to synchronize with Redis instead of forcing each API call to reach out to the external cache. The way this is implemented is as\u00a0follows.<\/p>\n \/\/ The rate limit window in milliseconds \/\/ If the counter expire time has not been set, set it In order to validate the performance of the rate limiter, the following test was run on the following environment.<\/p>\n Test<\/strong><\/p>\n 1000 calls per second to a single API\u00a0endpoint25 tenants3 instances of the\u00a0serviceSynchronize with Redis once per second, per tenant\/endpoint<\/p>\n Environment<\/strong><\/p>\n Kubernetes Environment deployed in AWS US-East-13 instances each running on their own m5.xlarge instance (4 vCPU, 16 GB\u00a0RAM)Test Clients running in AWS US-East-1.Redis Atomic Increment Call Rate per\u00a0Second<\/strong>Redis Atomic Increment p95 Latency in milliseconds<\/strong>Redis Rate Limiter p95 Latency in Milliseconds<\/strong><\/p>\n The above charts show that the expected 75 (25 tenants across three instances) calls are made to Redis per second, that the Redis atomic increment latency is a p95 of 15.7ms, and that, by only syncing once per second, the rate limiter induces a p95 of 1 <\/strong>millisecond of latency under\u00a0load.<\/p>\n As companies move more towards API-first, multitenant, horizontally scalable, distributed offerings, it is paramount that they build in the service protection to maintain stability under load. The above article demonstrates a simple implementation with a two layer cache approach that can be employed to protect the system without hindering performance.<\/p>\n Coordinated Rate Limiting in Microservices<\/a> was originally published in Salesforce Engineering<\/a> on Medium, where people are continuing the conversation by highlighting and responding to this story.<\/p>\n Read More<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"The Rate Limit Definition<\/h3>\n
– id: get-product
enabled: true
match:
methods: [ ‘GET’ ]
pathPattern: \/product\/*
tiers:
– period: 10
threshold: 1000
– id: put-product
enabled: true
match:
methods: [ ‘PUT’ ]
pathPattern: \/product\/*
tiers:
– period: 10
threshold: 100<\/p>\nDistributed Counter<\/h3>\n
The Response<\/h3>\n
A Deeper\u00a0Look<\/h3>\n
long startTime = System.currentTimeMillis<\/em>();
long windowStart = (startTime \/ windowTime) * windowTime;
long windowEnd = windowStart + windowTime;String counterKey = orgId + “_” + endpoint + “_” + httpMethod +
“_” + windowStart + “_” + windowEnd;<\/p>\n
long windowTime = 10000;\/\/ The local cache
Cache<String, Counter> callsPerCounterCache = Caffeine.newBuilder<\/em>().maximumSize(1000)
.expireAfterWrite(windowTime + 2000, TimeUnit.MILLISECONDS<\/em>).build();\/\/ The counter class
class Counter {
long callsSinceLastSync = 0;
long totalCalls = 0;
long lastSyncTimeMs = 0;
boolean firstTime = true;
}\/\/ Get Counter and Increment
Counter counter = callsPerCounterCache.get(counterKey, k -> new Counter());
counter.callsSinceLastSync++;
counter.totalCalls++;\/\/ If we have reached a sync interval, sync with Redis
\/\/ This is always true on the first pass
if (System.currentTimeMillis() – counter.lastSyncTimeMs > syncThresholdMs) {
syncWithRedis(counterName, windowTime, counter);
}return counter.totalCalls;\/\/\/\/\/\/\/ syncWithRedis method \/\/\/\/\/\/\/
long currentTime = System.currentTimeMillis();
RedisCommands<String, String> sync = redisConnection.sync();
counter.totalCalls = sync.incrby(counterName, counter.callsSinceLastSync);<\/p>\n
if (counter.firstTime) {
sync.expire(counterName, TimeUnit.SECONDS.convert(windowTime + 2000, TimeUnit.MILLISECONDS));
counter.firstTime = false;
}\/\/ Reset the local count and last sync time
counter.lastSyncTimeMs = currentTime;
counter.callsSinceLastSync = 0;<\/p>\nPerformance Testing<\/h3>\n
Conclusion<\/h3>\n