This is an automated email from the ASF dual-hosted git repository.
markt pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/tomcat.git
The following commit(s) were added to refs/heads/main by this push:
new c1e50fb357 Add an exact rate limit filter.
c1e50fb357 is described below
commit c1e50fb3574ab6aeb02d1346fc0c5ff7b1f9ca08
Author: Mark Thomas <ma...@apache.org>
AuthorDate: Fri Mar 7 14:55:22 2025 +0000
Add an exact rate limit filter.
Based on PR #794 by Chenjp
---
.../apache/catalina/filters/RateLimitFilter.java | 7 +-
.../org/apache/catalina/util/ExactRateLimiter.java | 68 +++++++
java/org/apache/catalina/util/FastRateLimiter.java | 1 +
java/org/apache/catalina/util/RateLimiterBase.java | 10 +
.../catalina/util/TimeBucketCounterBase.java | 3 -
.../TestRateLimitFilterWithExactRateLimiter.java | 211 +++++++++++++++++++++
webapps/docs/changelog.xml | 7 +
webapps/docs/config/filter.xml | 30 ++-
8 files changed, 323 insertions(+), 14 deletions(-)
diff --git a/java/org/apache/catalina/filters/RateLimitFilter.java
b/java/org/apache/catalina/filters/RateLimitFilter.java
index 8e07ca8182..80315948bb 100644
--- a/java/org/apache/catalina/filters/RateLimitFilter.java
+++ b/java/org/apache/catalina/filters/RateLimitFilter.java
@@ -47,8 +47,11 @@ import org.apache.tomcat.util.res.StringManager;
* so it converts some configured values to more efficient values. For
example, a configuration of a 60 seconds time
* bucket is converted to 65.536 seconds. That allows for very fast bucket
calculation using bit shift arithmetic. In
* order to remain true to the user intent, the configured number of requests
is then multiplied by the same ratio, so a
- * configuration of 100 Requests per 60 seconds, has the real values of 109
Requests per 65 seconds. You can specify a
- * different class as long as it implements the
<code>org.apache.catalina.util.RateLimiter</code> interface.
+ * configuration of 100 Requests per 60 seconds, has the real values of 109
Requests per 65 seconds. An alternative
+ * implementation, <code>org.apache.catalina.util.ExactRateLimiter</code>, is
intended to provide a less efficient but
+ * more accurate control, whose effective duration in seconds and number of
requests configuration are consist with the
+ * user declared. You can specify a different class as long as it implements
the
+ * <code>org.apache.catalina.util.RateLimiter</code> interface.
* </p>
* <p>
* It is common to set up different restrictions for different URIs. For
example, a login page or authentication script
diff --git a/java/org/apache/catalina/util/ExactRateLimiter.java
b/java/org/apache/catalina/util/ExactRateLimiter.java
new file mode 100644
index 0000000000..a1b8c9190f
--- /dev/null
+++ b/java/org/apache/catalina/util/ExactRateLimiter.java
@@ -0,0 +1,68 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.catalina.util;
+
+import java.util.concurrent.ScheduledExecutorService;
+
+/**
+ * A RateLimiter that compromises efficiency for accuracy in order to provide
exact rate limiting.
+ */
+public class ExactRateLimiter extends RateLimiterBase {
+
+ @Override
+ protected String getDefaultPolicyName() {
+ return "exact";
+ }
+
+
+ @Override
+ protected TimeBucketCounterBase newCounterInstance(int duration,
ScheduledExecutorService executorService) {
+ return new ExactTimeBucketCounter(duration, executorService);
+ }
+
+
+ /**
+ * An accurate counter with exact bucket index, but slightly less
efficient than another fast counter provided with
+ * the {@link FastRateLimiter}.
+ */
+ class ExactTimeBucketCounter extends TimeBucketCounterBase {
+
+ ExactTimeBucketCounter(int bucketDuration, ScheduledExecutorService
executorService) {
+ super(bucketDuration, executorService);
+ }
+
+ @Override
+ public long getBucketIndex(long timestamp) {
+ return (timestamp / 1000) / getBucketDuration();
+ }
+
+ @Override
+ public double getRatio() {
+ // Actual value is exactly the same as declared
+ return 1.0d;
+ }
+
+ @Override
+ public long getMillisUntilNextBucket() {
+ long millis = System.currentTimeMillis();
+
+ long nextTimeBucketMillis = (getBucketIndex(millis) + 1) *
getBucketDuration() * 1000;
+ long delta = nextTimeBucketMillis - millis;
+ return delta;
+ }
+ }
+}
diff --git a/java/org/apache/catalina/util/FastRateLimiter.java
b/java/org/apache/catalina/util/FastRateLimiter.java
index 17544c5d28..dc7b9d5249 100644
--- a/java/org/apache/catalina/util/FastRateLimiter.java
+++ b/java/org/apache/catalina/util/FastRateLimiter.java
@@ -35,6 +35,7 @@ public class FastRateLimiter extends RateLimiterBase {
}
+ @Override
public TimeBucketCounter getBucketCounter() {
return (TimeBucketCounter) bucketCounter;
}
diff --git a/java/org/apache/catalina/util/RateLimiterBase.java
b/java/org/apache/catalina/util/RateLimiterBase.java
index 1f4c699462..d04c88836e 100644
--- a/java/org/apache/catalina/util/RateLimiterBase.java
+++ b/java/org/apache/catalina/util/RateLimiterBase.java
@@ -142,4 +142,14 @@ public abstract class RateLimiterBase implements
RateLimiter {
actualDuration = bucketCounter.getBucketDuration();
actualRequests = (int) Math.round(bucketCounter.getRatio() * requests);
}
+
+
+ /**
+ * Returns the internal instance of {@link TimeBucketCounterBase}.
+ *
+ * @return instance of {@link TimeBucketCounterBase}
+ */
+ public TimeBucketCounterBase getBucketCounter() {
+ return bucketCounter;
+ }
}
diff --git a/java/org/apache/catalina/util/TimeBucketCounterBase.java
b/java/org/apache/catalina/util/TimeBucketCounterBase.java
index b2b0bbee09..4679a41f0a 100644
--- a/java/org/apache/catalina/util/TimeBucketCounterBase.java
+++ b/java/org/apache/catalina/util/TimeBucketCounterBase.java
@@ -156,10 +156,7 @@ public abstract class TimeBucketCounterBase {
* <strong>WARNING:</strong> This method is used for test purpose.
*
* @return the number of milliseconds until the next bucket
- *
- * @deprecated Will be made package private in Tomcat 12 onwards.
*/
- @Deprecated
public abstract long getMillisUntilNextBucket();
diff --git
a/test/org/apache/catalina/filters/TestRateLimitFilterWithExactRateLimiter.java
b/test/org/apache/catalina/filters/TestRateLimitFilterWithExactRateLimiter.java
new file mode 100644
index 0000000000..de6787844b
--- /dev/null
+++
b/test/org/apache/catalina/filters/TestRateLimitFilterWithExactRateLimiter.java
@@ -0,0 +1,211 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.catalina.filters;
+
+import java.io.IOException;
+
+import jakarta.servlet.FilterChain;
+
+import org.junit.Assert;
+import org.junit.Test;
+
+import org.apache.catalina.Context;
+import org.apache.catalina.filters.TestRemoteIpFilter.MockFilterChain;
+import org.apache.catalina.filters.TestRemoteIpFilter.MockHttpServletRequest;
+import org.apache.catalina.startup.Tomcat;
+import org.apache.catalina.startup.TomcatBaseTest;
+import org.apache.catalina.util.ExactRateLimiter;
+import org.apache.tomcat.unittest.TesterResponse;
+import org.apache.tomcat.util.descriptor.web.FilterDef;
+import org.apache.tomcat.util.descriptor.web.FilterMap;
+
+public class TestRateLimitFilterWithExactRateLimiter extends TomcatBaseTest {
+ private void testRateLimitWith1Clients(boolean exposeHeaders, boolean
enforce) throws Exception {
+
+ int bucketRequests = 40;
+ int bucketDuration = 4;
+
+ FilterDef filterDef = new FilterDef();
+ filterDef.addInitParameter("bucketRequests",
String.valueOf(bucketRequests));
+ filterDef.addInitParameter("bucketDuration",
String.valueOf(bucketDuration));
+ filterDef.addInitParameter("enforce", String.valueOf(enforce));
+ filterDef.addInitParameter("exposeHeaders",
String.valueOf(exposeHeaders));
+ filterDef.addInitParameter("rateLimitClassName",
"org.apache.catalina.util.ExactRateLimiter");
+
+ Tomcat tomcat = getTomcatInstance();
+ Context root = tomcat.addContext("", TEMP_DIR);
+
+ MockFilterChain filterChain = new MockFilterChain();
+ RateLimitFilter rateLimitFilter = testRateLimitFilter(filterDef, root);
+ tomcat.start();
+
+ ExactRateLimiter exactRateLimiter = (ExactRateLimiter)
rateLimitFilter.rateLimiter;
+
+ int allowedRequests = exactRateLimiter.getRequests();
+ long sleepTime =
exactRateLimiter.getBucketCounter().getMillisUntilNextBucket();
+ System.out.printf("Sleeping %d millis for the next time bucket to
start\n", Long.valueOf(sleepTime));
+ Thread.sleep(sleepTime);
+
+ TestClient tc1 = new TestClient(rateLimitFilter, filterChain,
"10.20.20.5", 50, 5); // TPS: 5
+ TestClient tc2 = new TestClient(rateLimitFilter, filterChain,
"10.20.20.10", 100, 10); // TPS: 10
+
+ TestClient tc3 = new TestClient(rateLimitFilter, filterChain,
"10.20.20.20", 200, 20); // TPS: 20
+ TestClient tc4 = new TestClient(rateLimitFilter, filterChain,
"10.20.20.40", 400, 40); // TPS: 40
+ tc1.join();
+ tc2.join();
+ tc3.join();
+ tc4.join();
+ Assert.assertEquals(200, tc1.results[24]); // only 25 requests made in
5 seconds, all allowed
+
+ Assert.assertEquals(200, tc2.results[49]); // only 50 requests made in
5 seconds, all allowed
+
+ Assert.assertEquals(200, tc3.results[39]); // first allowedRequests
allowed
+
+ if (enforce) {
+ Assert.assertEquals(429, tc3.results[allowedRequests]); //
subsequent requests dropped
+ } else {
+ Assert.assertEquals(200, tc3.results[allowedRequests]);
+ }
+
+ Assert.assertEquals(200, tc4.results[allowedRequests - 1]); // first
allowedRequests allowed
+
+ if (enforce) {
+ Assert.assertEquals(429, tc4.results[allowedRequests]); //
subsequent requests dropped
+ } else {
+ Assert.assertEquals(200, tc4.results[allowedRequests]);
+ }
+
+ if (exposeHeaders) {
+ Assert.assertTrue(tc3.rlpHeader[24].contains("q=" +
allowedRequests));
+ Assert.assertTrue(tc3.rlpHeader[allowedRequests].contains("q=" +
allowedRequests));
+ if (enforce) {
+ Assert.assertTrue(tc3.rlHeader[24].contains("r="));
+ Assert.assertFalse(tc3.rlHeader[24].contains("r=0"));
+
Assert.assertTrue(tc3.rlHeader[allowedRequests].contains("r=0"));
+ }
+ } else {
+ Assert.assertTrue(tc3.rlpHeader[24] == null);
+ Assert.assertTrue(tc3.rlHeader[24] == null);
+ Assert.assertTrue(tc3.rlpHeader[allowedRequests] == null);
+ Assert.assertTrue(tc3.rlHeader[allowedRequests] == null);
+ }
+ tomcat.stop();
+ }
+
+ @Test
+ public void testExposeHeaderAndRerferenceRateLimitWith4Clients() throws
Exception {
+ testRateLimitWith1Clients(true, false);
+ }
+
+ @Test
+ public void testUnexposeHeaderAndRerferenceRateLimitWith4Clients() throws
Exception {
+ testRateLimitWith1Clients(false, false);
+ }
+
+ @Test
+ public void testExposeHeaderAndEnforceRateLimitWith4Clients() throws
Exception {
+ testRateLimitWith1Clients(true, true);
+ }
+
+ @Test
+ public void testUnexposeHeaderAndEnforceRateLimitWith4Clients() throws
Exception {
+ testRateLimitWith1Clients(false, true);
+ }
+
+ private RateLimitFilter testRateLimitFilter(FilterDef filterDef, Context
root) {
+
+ RateLimitFilter rateLimitFilter = new RateLimitFilter();
+ filterDef.setFilterClass(RateLimitFilter.class.getName());
+ filterDef.setFilter(rateLimitFilter);
+ filterDef.setFilterName(RateLimitFilter.class.getName());
+ root.addFilterDef(filterDef);
+
+ FilterMap filterMap = new FilterMap();
+ filterMap.setFilterName(RateLimitFilter.class.getName());
+ filterMap.addURLPatternDecoded("*");
+ root.addFilterMap(filterMap);
+
+ return rateLimitFilter;
+ }
+
+ static class TestClient extends Thread {
+ RateLimitFilter filter;
+ FilterChain filterChain;
+ String ip;
+
+ int requests;
+ int sleep;
+
+ int[] results;
+ volatile String[] rlpHeader;
+ volatile String[] rlHeader;
+
+ TestClient(RateLimitFilter filter, FilterChain filterChain, String ip,
int requests, int rps) {
+ this.filter = filter;
+ this.filterChain = filterChain;
+ this.ip = ip;
+ this.requests = requests;
+ this.sleep = 1000 / rps;
+ this.results = new int[requests];
+ this.rlpHeader = new String[requests];
+ this.rlHeader = new String[requests];
+ super.setDaemon(true);
+ super.start();
+ }
+
+ @Override
+ public void run() {
+ try {
+ for (int i = 0; i < requests; i++) {
+ MockHttpServletRequest request = new
MockHttpServletRequest();
+ request.setRemoteAddr(ip);
+ TesterResponse response = new TesterResponseWithStatus();
+ response.setRequest(request);
+ filter.doFilter(request, response, filterChain);
+ results[i] = response.getStatus();
+
+ rlpHeader[i] =
response.getHeader(RateLimitFilter.HEADER_RATE_LIMIT_POLICY);
+ rlHeader[i] =
response.getHeader(RateLimitFilter.HEADER_RATE_LIMIT);
+
+ if (results[i] != 200) {
+ break;
+ }
+ sleep(sleep);
+ }
+ } catch (Exception ex) {
+ ex.printStackTrace();
+ }
+ }
+ }
+
+ static class TesterResponseWithStatus extends TesterResponse {
+
+ int status = 200;
+ String message = "OK";
+
+ @Override
+ public void sendError(int status, String message) throws IOException {
+ this.status = status;
+ this.message = message;
+ }
+
+ @Override
+ public int getStatus() {
+ return status;
+ }
+ }
+}
diff --git a/webapps/docs/changelog.xml b/webapps/docs/changelog.xml
index 39285b90a7..b1cfac4946 100644
--- a/webapps/docs/changelog.xml
+++ b/webapps/docs/changelog.xml
@@ -154,6 +154,13 @@
Return 400 if the amount of content sent for a partial PUT is
inconsistent with the range that was specified. (remm)
</fix>
+ <add>
+ Add a new <code>RateLimiter</code> implementation,
+ <code>org.apache.catalina.util.ExactRateLimiter</code>, that can be
used
+ with <code>org.apache.catalina.filters.RateLimitFilter</code> to
provide
+ rate limit based on the exact values configured. Based on pull request
+ <pr>794</pr> by Chenjp. (markt)
+ </add>
</changelog>
</subsection>
<subsection name="Coyote">
diff --git a/webapps/docs/config/filter.xml b/webapps/docs/config/filter.xml
index 5a879727ab..c69c6d1cbb 100644
--- a/webapps/docs/config/filter.xml
+++ b/webapps/docs/config/filter.xml
@@ -968,13 +968,21 @@ FINE: Request "/docs/config/manager.html" with response
status "200"
from that IP are dropped with a "429 Too many requests" response
until the bucket time ends and a new bucket starts.</p>
- <p>The filter is optimized for efficiency and low overhead, so it converts
- some configured values to more efficient values. For example, a
configuration
- of a 60 seconds time bucket is converted to 65.536 seconds. That allows
- for very fast bucket calculation using bit shift arithmetic. In order to
remain
- true to the user intent, the configured number of requests is then
multiplied
- by the same ratio, so a configuration of 100 Requests per 60 seconds, has
the
- real values of 109 Requests per 65 seconds.</p>
+ <p>The RateLimiter implementation can be set via the
<code>rateLimitClassName</code>
+ init param. The default implementation,
+ <code>org.apache.catalina.util.FastRateLimiter</code>, is optimized for
+ efficiency and low overhead so it converts some configured values to more
+ efficient values. For example, a configuration of a 60 seconds time bucket
+ is converted to 65.536 seconds. That allows for very fast bucket
calculation
+ using bit shift arithmetic. In order to remain true to the user intent, the
+ configured number of requests is then multiplied by the same ratio, so a
+ configuration of 100 Requests per 60 seconds, has the real values of 109
+ Requests per 65 seconds. An alternative implementation,
+ <code>org.apache.catalina.util.ExactRateLimiter</code>, is intended to
+ provide a less efficient but more accurate control, whose effective
duration
+ in seconds and number of requests allowed are consist with the configured
+ values. You can specify a different class as long as it implements the
+ <code>org.apache.catalina.util.RateLimiter</code> interface.</p>
<p>It is common to set up different restrictions for different URIs.
For example, a login page or authentication script is typically expected
@@ -1046,8 +1054,12 @@ FINE: Request "/docs/config/manager.html" with response
status "200"
</attribute>
<attribute name="rateLimitClassName" required="false">
- <p>The full class name of an implementation of the RateLimiter
interface.
- Default is "org.apache.catalina.util.FastRateLimiter".</p>
+ <p>The full class name of an implementation of the RateLimiter
+ interface. Default is
+ "org.apache.catalina.util.FastRateLimiter", which is
optimized
+ for efficiency. If you need exact rate limiting and can accept a small
+ decrease in efficiency, you can use
+ "org.apache.catalina.util.ExactRateLimiter" instead.</p>
</attribute>
<attribute name="statusCode" required="false">
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscr...@tomcat.apache.org
For additional commands, e-mail: dev-h...@tomcat.apache.org
