1 /* 2 * Copyright (C) 2012 The Guava Authors 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.google.common.util.concurrent; 18 19 import static java.lang.reflect.Modifier.isStatic; 20 import static java.util.concurrent.TimeUnit.MICROSECONDS; 21 import static java.util.concurrent.TimeUnit.MILLISECONDS; 22 import static java.util.concurrent.TimeUnit.NANOSECONDS; 23 import static java.util.concurrent.TimeUnit.SECONDS; 24 25 import com.google.common.collect.ImmutableClassToInstanceMap; 26 import com.google.common.collect.ImmutableSet; 27 import com.google.common.collect.Lists; 28 import com.google.common.testing.NullPointerTester; 29 import com.google.common.testing.NullPointerTester.Visibility; 30 import com.google.common.util.concurrent.RateLimiter.SleepingStopwatch; 31 32 import junit.framework.TestCase; 33 34 import org.easymock.EasyMock; 35 import org.mockito.Mockito; 36 37 import java.lang.reflect.Method; 38 import java.util.Arrays; 39 import java.util.List; 40 import java.util.Random; 41 import java.util.concurrent.TimeUnit; 42 43 /** 44 * Tests for RateLimiter. 45 * 46 * @author Dimitris Andreou 47 */ 48 public class RateLimiterTest extends TestCase { 49 private static final double EPSILON = 1e-8; 50 51 private final FakeStopwatch stopwatch = new FakeStopwatch(); 52 53 public void testSimple() { 54 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 55 limiter.acquire(); // R0.00, since it's the first request 56 limiter.acquire(); // R0.20 57 limiter.acquire(); // R0.20 58 assertEvents("R0.00", "R0.20", "R0.20"); 59 } 60 61 public void testImmediateTryAcquire() { 62 RateLimiter r = RateLimiter.create(1); 63 assertTrue("Unable to acquire initial permit", r.tryAcquire()); 64 assertFalse("Capable of acquiring secondary permit", r.tryAcquire()); 65 } 66 67 public void testSimpleRateUpdate() { 68 RateLimiter limiter = RateLimiter.create(5.0, 5, SECONDS); 69 assertEquals(5.0, limiter.getRate()); 70 limiter.setRate(10.0); 71 assertEquals(10.0, limiter.getRate()); 72 73 try { 74 limiter.setRate(0.0); 75 fail(); 76 } catch (IllegalArgumentException expected) {} 77 try { 78 limiter.setRate(-10.0); 79 fail(); 80 } catch (IllegalArgumentException expected) {} 81 } 82 83 public void testAcquireParameterValidation() { 84 RateLimiter limiter = RateLimiter.create(999); 85 try { 86 limiter.acquire(0); 87 fail(); 88 } catch (IllegalArgumentException expected) { 89 } 90 try { 91 limiter.acquire(-1); 92 fail(); 93 } catch (IllegalArgumentException expected) { 94 } 95 try { 96 limiter.tryAcquire(0); 97 fail(); 98 } catch (IllegalArgumentException expected) { 99 } 100 try { 101 limiter.tryAcquire(-1); 102 fail(); 103 } catch (IllegalArgumentException expected) { 104 } 105 try { 106 limiter.tryAcquire(0, 1, SECONDS); 107 fail(); 108 } catch (IllegalArgumentException expected) { 109 } 110 try { 111 limiter.tryAcquire(-1, 1, SECONDS); 112 fail(); 113 } catch (IllegalArgumentException expected) { 114 } 115 } 116 117 public void testSimpleWithWait() { 118 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 119 limiter.acquire(); // R0.00 120 stopwatch.sleepMillis(200); // U0.20, we are ready for the next request... 121 limiter.acquire(); // R0.00, ...which is granted immediately 122 limiter.acquire(); // R0.20 123 assertEvents("R0.00", "U0.20", "R0.00", "R0.20"); 124 } 125 126 public void testSimpleAcquireReturnValues() { 127 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 128 assertEquals(0.0, limiter.acquire(), EPSILON); // R0.00 129 stopwatch.sleepMillis(200); // U0.20, we are ready for the next request... 130 assertEquals(0.0, limiter.acquire(), EPSILON); // R0.00, ...which is granted immediately 131 assertEquals(0.2, limiter.acquire(), EPSILON); // R0.20 132 assertEvents("R0.00", "U0.20", "R0.00", "R0.20"); 133 } 134 135 public void testSimpleAcquireEarliestAvailableIsInPast() { 136 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 137 assertEquals(0.0, limiter.acquire(), EPSILON); 138 stopwatch.sleepMillis(400); 139 assertEquals(0.0, limiter.acquire(), EPSILON); 140 assertEquals(0.0, limiter.acquire(), EPSILON); 141 assertEquals(0.2, limiter.acquire(), EPSILON); 142 } 143 144 public void testOneSecondBurst() { 145 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 146 stopwatch.sleepMillis(1000); // max capacity reached 147 stopwatch.sleepMillis(1000); // this makes no difference 148 limiter.acquire(1); // R0.00, since it's the first request 149 150 limiter.acquire(1); // R0.00, from capacity 151 limiter.acquire(3); // R0.00, from capacity 152 limiter.acquire(1); // R0.00, concluding a burst of 5 permits 153 154 limiter.acquire(); // R0.20, capacity exhausted 155 assertEvents("U1.00", "U1.00", 156 "R0.00", "R0.00", "R0.00", "R0.00", // first request and burst 157 "R0.20"); 158 } 159 160 public void testCreateWarmupParameterValidation() { 161 RateLimiter.create(1.0, 1, NANOSECONDS); 162 RateLimiter.create(1.0, 0, NANOSECONDS); 163 164 try { 165 RateLimiter.create(0.0, 1, NANOSECONDS); 166 fail(); 167 } catch (IllegalArgumentException expected) { 168 } 169 170 try { 171 RateLimiter.create(1.0, -1, NANOSECONDS); 172 fail(); 173 } catch (IllegalArgumentException expected) { 174 } 175 } 176 177 public void testWarmUp() { 178 RateLimiter limiter = RateLimiter.create(stopwatch, 2.0, 4000, MILLISECONDS); 179 for (int i = 0; i < 8; i++) { 180 limiter.acquire(); // #1 181 } 182 stopwatch.sleepMillis(500); // #2: to repay for the last acquire 183 stopwatch.sleepMillis(4000); // #3: becomes cold again 184 for (int i = 0; i < 8; i++) { 185 limiter.acquire(); // // #4 186 } 187 stopwatch.sleepMillis(500); // #5: to repay for the last acquire 188 stopwatch.sleepMillis(2000); // #6: didn't get cold! It would take another 2 seconds to go cold 189 for (int i = 0; i < 8; i++) { 190 limiter.acquire(); // #7 191 } 192 assertEvents( 193 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50", // #1 194 "U0.50", // #2 195 "U4.00", // #3 196 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50", // #4 197 "U0.50", // #5 198 "U2.00", // #6 199 "R0.00, R0.50, R0.50, R0.50, R0.50, R0.50, R0.50, R0.50"); // #7 200 } 201 202 public void testWarmUpAndUpdate() { 203 RateLimiter limiter = RateLimiter.create(stopwatch, 2.0, 4000, MILLISECONDS); 204 for (int i = 0; i < 8; i++) { 205 limiter.acquire(); // // #1 206 } 207 stopwatch.sleepMillis(4500); // #2: back to cold state (warmup period + repay last acquire) 208 for (int i = 0; i < 3; i++) { // only three steps, we're somewhere in the warmup period 209 limiter.acquire(); // #3 210 } 211 212 limiter.setRate(4.0); // double the rate! 213 limiter.acquire(); // #4, we repay the debt of the last acquire (imposed by the old rate) 214 for (int i = 0; i < 4; i++) { 215 limiter.acquire(); // #5 216 } 217 stopwatch.sleepMillis(4250); // #6, back to cold state (warmup period + repay last acquire) 218 for (int i = 0; i < 11; i++) { 219 limiter.acquire(); // #7, showing off the warmup starting from totally cold 220 } 221 222 // make sure the areas (times) remain the same, while permits are different 223 assertEvents( 224 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50", // #1 225 "U4.50", // #2 226 "R0.00, R1.38, R1.13", // #3, after that the rate changes 227 "R0.88", // #4, this is what the throttling would be with the old rate 228 "R0.34, R0.28, R0.25, R0.25", // #5 229 "U4.25", // #6 230 "R0.00, R0.72, R0.66, R0.59, R0.53, R0.47, R0.41", // #7 231 "R0.34, R0.28, R0.25, R0.25"); // #7 (cont.), note, this matches #5 232 } 233 234 public void testBurstyAndUpdate() { 235 RateLimiter rateLimiter = RateLimiter.create(stopwatch, 1.0); 236 rateLimiter.acquire(1); // no wait 237 rateLimiter.acquire(1); // R1.00, to repay previous 238 239 rateLimiter.setRate(2.0); // update the rate! 240 241 rateLimiter.acquire(1); // R1.00, to repay previous (the previous was under the old rate!) 242 rateLimiter.acquire(2); // R0.50, to repay previous (now the rate takes effect) 243 rateLimiter.acquire(4); // R1.00, to repay previous 244 rateLimiter.acquire(1); // R2.00, to repay previous 245 assertEvents("R0.00", "R1.00", "R1.00", "R0.50", "R1.00", "R2.00"); 246 } 247 248 public void testTryAcquire_noWaitAllowed() { 249 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 250 assertTrue(limiter.tryAcquire(0, SECONDS)); 251 assertFalse(limiter.tryAcquire(0, SECONDS)); 252 assertFalse(limiter.tryAcquire(0, SECONDS)); 253 stopwatch.sleepMillis(100); 254 assertFalse(limiter.tryAcquire(0, SECONDS)); 255 } 256 257 public void testTryAcquire_someWaitAllowed() { 258 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 259 assertTrue(limiter.tryAcquire(0, SECONDS)); 260 assertTrue(limiter.tryAcquire(200, MILLISECONDS)); 261 assertFalse(limiter.tryAcquire(100, MILLISECONDS)); 262 stopwatch.sleepMillis(100); 263 assertTrue(limiter.tryAcquire(100, MILLISECONDS)); 264 } 265 266 public void testTryAcquire_overflow() { 267 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 268 assertTrue(limiter.tryAcquire(0, MICROSECONDS)); 269 stopwatch.sleepMillis(100); 270 assertTrue(limiter.tryAcquire(Long.MAX_VALUE, MICROSECONDS)); 271 } 272 273 public void testTryAcquire_negative() { 274 RateLimiter limiter = RateLimiter.create(stopwatch, 5.0); 275 assertTrue(limiter.tryAcquire(5, 0, SECONDS)); 276 stopwatch.sleepMillis(900); 277 assertFalse(limiter.tryAcquire(1, Long.MIN_VALUE, SECONDS)); 278 stopwatch.sleepMillis(100); 279 assertTrue(limiter.tryAcquire(1, -1, SECONDS)); 280 } 281 282 public void testSimpleWeights() { 283 RateLimiter rateLimiter = RateLimiter.create(stopwatch, 1.0); 284 rateLimiter.acquire(1); // no wait 285 rateLimiter.acquire(1); // R1.00, to repay previous 286 rateLimiter.acquire(2); // R1.00, to repay previous 287 rateLimiter.acquire(4); // R2.00, to repay previous 288 rateLimiter.acquire(8); // R4.00, to repay previous 289 rateLimiter.acquire(1); // R8.00, to repay previous 290 assertEvents("R0.00", "R1.00", "R1.00", "R2.00", "R4.00", "R8.00"); 291 } 292 293 public void testInfinity_Bursty() { 294 RateLimiter limiter = RateLimiter.create(stopwatch, Double.POSITIVE_INFINITY); 295 limiter.acquire(Integer.MAX_VALUE / 4); 296 limiter.acquire(Integer.MAX_VALUE / 2); 297 limiter.acquire(Integer.MAX_VALUE); 298 assertEvents("R0.00", "R0.00", "R0.00"); // no wait, infinite rate! 299 300 limiter.setRate(2.0); 301 limiter.acquire(); 302 limiter.acquire(); 303 limiter.acquire(); 304 limiter.acquire(); 305 limiter.acquire(); 306 assertEvents( 307 "R0.00", // First comes the saved-up burst, which defaults to a 1-second burst (2 requests). 308 "R0.00", 309 "R0.00", // Now comes the free request. 310 "R0.50", // Now it's 0.5 seconds per request. 311 "R0.50"); 312 313 limiter.setRate(Double.POSITIVE_INFINITY); 314 limiter.acquire(); 315 limiter.acquire(); 316 limiter.acquire(); 317 assertEvents("R0.50", "R0.00", "R0.00"); // we repay the last request (.5sec), then back to +oo 318 } 319 320 /** https://code.google.com/p/guava-libraries/issues/detail?id=1791 */ 321 public void testInfinity_BustyTimeElapsed() { 322 RateLimiter limiter = RateLimiter.create(stopwatch, Double.POSITIVE_INFINITY); 323 stopwatch.instant += 1000000; 324 limiter.setRate(2.0); 325 for (int i = 0; i < 5; i++) { 326 limiter.acquire(); 327 } 328 assertEvents( 329 "R0.00", // First comes the saved-up burst, which defaults to a 1-second burst (2 requests). 330 "R0.00", 331 "R0.00", // Now comes the free request. 332 "R0.50", // Now it's 0.5 seconds per request. 333 "R0.50"); 334 } 335 336 public void testInfinity_WarmUp() { 337 RateLimiter limiter = RateLimiter.create( 338 stopwatch, Double.POSITIVE_INFINITY, 10, SECONDS); 339 limiter.acquire(Integer.MAX_VALUE / 4); 340 limiter.acquire(Integer.MAX_VALUE / 2); 341 limiter.acquire(Integer.MAX_VALUE); 342 assertEvents("R0.00", "R0.00", "R0.00"); 343 344 limiter.setRate(1.0); 345 limiter.acquire(); 346 limiter.acquire(); 347 limiter.acquire(); 348 assertEvents("R0.00", "R1.00", "R1.00"); 349 350 limiter.setRate(Double.POSITIVE_INFINITY); 351 limiter.acquire(); 352 limiter.acquire(); 353 limiter.acquire(); 354 assertEvents("R1.00", "R0.00", "R0.00"); 355 } 356 357 public void testInfinity_WarmUpTimeElapsed() { 358 RateLimiter limiter = RateLimiter.create(stopwatch, Double.POSITIVE_INFINITY, 10, SECONDS); 359 stopwatch.instant += 1000000; 360 limiter.setRate(1.0); 361 for (int i = 0; i < 5; i++) { 362 limiter.acquire(); 363 } 364 assertEvents("R0.00", "R1.00", "R1.00", "R1.00", "R1.00"); 365 } 366 367 /** 368 * Make sure that bursts can never go above 1-second-worth-of-work for the current 369 * rate, even when we change the rate. 370 */ 371 public void testWeNeverGetABurstMoreThanOneSec() { 372 RateLimiter limiter = RateLimiter.create(stopwatch, 1.0); 373 int[] rates = { 1000, 1, 10, 1000000, 10, 1}; 374 for (int rate : rates) { 375 int oneSecWorthOfWork = rate; 376 stopwatch.sleepMillis(rate * 1000); 377 limiter.setRate(rate); 378 long burst = measureTotalTimeMillis(limiter, oneSecWorthOfWork, new Random()); 379 // we allow one second worth of work to go in a burst (i.e. take less than a second) 380 assertTrue(burst <= 1000); 381 long afterBurst = measureTotalTimeMillis(limiter, oneSecWorthOfWork, new Random()); 382 // but work beyond that must take at least one second 383 assertTrue(afterBurst >= 1000); 384 } 385 } 386 387 /** 388 * This neat test shows that no matter what weights we use in our requests, if we push X 389 * amount of permits in a cool state, where X = rate * timeToCoolDown, and we have 390 * specified a timeToWarmUp() period, it will cost as the prescribed amount of time. E.g., 391 * calling [acquire(5), acquire(1)] takes exactly the same time as 392 * [acquire(2), acquire(3), acquire(1)]. 393 */ 394 public void testTimeToWarmUpIsHonouredEvenWithWeights() { 395 Random random = new Random(); 396 int maxPermits = 10; 397 double[] qpsToTest = { 4.0, 2.0, 1.0, 0.5, 0.1 }; 398 for (int trial = 0; trial < 100; trial++) { 399 for (double qps : qpsToTest) { 400 // Since we know that: maxPermits = 0.5 * warmup / stableInterval; 401 // then if maxPermits == 10, we have: 402 // warmupSeconds = 20 / qps 403 long warmupMillis = (long) ((2 * maxPermits / qps) * 1000.0); 404 RateLimiter rateLimiter = RateLimiter.create( 405 stopwatch, qps, warmupMillis, MILLISECONDS); 406 assertEquals(warmupMillis, measureTotalTimeMillis(rateLimiter, maxPermits, random)); 407 } 408 } 409 } 410 411 public void testNulls() { 412 NullPointerTester tester = new NullPointerTester() 413 .setDefault(SleepingStopwatch.class, stopwatch) 414 .setDefault(int.class, 1); 415 tester.testStaticMethods(RateLimiter.class, Visibility.PACKAGE); 416 tester.testInstanceMethods(RateLimiter.create(stopwatch, 5.0), Visibility.PACKAGE); 417 } 418 419 private long measureTotalTimeMillis(RateLimiter rateLimiter, int permits, Random random) { 420 long startTime = stopwatch.instant; 421 while (permits > 0) { 422 int nextPermitsToAcquire = Math.max(1, random.nextInt(permits)); 423 permits -= nextPermitsToAcquire; 424 rateLimiter.acquire(nextPermitsToAcquire); 425 } 426 rateLimiter.acquire(1); // to repay for any pending debt 427 return NANOSECONDS.toMillis(stopwatch.instant - startTime); 428 } 429 430 private void assertEvents(String... events) { 431 assertEquals(Arrays.toString(events), stopwatch.readEventsAndClear()); 432 } 433 434 /** 435 * The stopwatch gathers events and presents them as strings. 436 * R0.6 means a delay of 0.6 seconds caused by the (R)ateLimiter 437 * U1.0 means the (U)ser caused the stopwatch to sleep for a second. 438 */ 439 static class FakeStopwatch extends SleepingStopwatch { 440 long instant = 0L; 441 final List<String> events = Lists.newArrayList(); 442 443 @Override 444 public long readMicros() { 445 return NANOSECONDS.toMicros(instant); 446 } 447 448 void sleepMillis(int millis) { 449 sleepMicros("U", MILLISECONDS.toMicros(millis)); 450 } 451 452 void sleepMicros(String caption, long micros) { 453 instant += MICROSECONDS.toNanos(micros); 454 events.add(caption + String.format("%3.2f", (micros / 1000000.0))); 455 } 456 457 @Override 458 void sleepMicrosUninterruptibly(long micros) { 459 sleepMicros("R", micros); 460 } 461 462 String readEventsAndClear() { 463 try { 464 return events.toString(); 465 } finally { 466 events.clear(); 467 } 468 } 469 470 @Override 471 public String toString() { 472 return events.toString(); 473 } 474 } 475 476 public void testMocking() throws Exception { 477 RateLimiter mockito = Mockito.mock(RateLimiter.class); 478 RateLimiter easyMock = EasyMock.createNiceMock(RateLimiter.class); 479 EasyMock.replay(easyMock); 480 for (Method method : RateLimiter.class.getMethods()) { 481 if (!isStatic(method.getModifiers()) 482 && !NOT_WORKING_ON_MOCKS.contains(method.getName()) 483 && !method.getDeclaringClass().equals(Object.class)) { 484 method.invoke(mockito, arbitraryParameters(method)); 485 method.invoke(easyMock, arbitraryParameters(method)); 486 } 487 } 488 } 489 490 private static Object[] arbitraryParameters(Method method) { 491 Class<?>[] parameterTypes = method.getParameterTypes(); 492 Object[] params = new Object[parameterTypes.length]; 493 for (int i = 0; i < parameterTypes.length; i++) { 494 params[i] = PARAMETER_VALUES.get(parameterTypes[i]); 495 } 496 return params; 497 } 498 499 private static final ImmutableSet<String> NOT_WORKING_ON_MOCKS = 500 ImmutableSet.of("latestPermitAgeSec", "setRate"); 501 502 // We would use ArbitraryInstances, but it returns 0, invalid for many RateLimiter methods. 503 private static final ImmutableClassToInstanceMap<Object> PARAMETER_VALUES = 504 ImmutableClassToInstanceMap.builder() 505 .put(int.class, 1) 506 .put(long.class, 1L) 507 .put(double.class, 1.0) 508 .put(TimeUnit.class, SECONDS) 509 .build(); 510 } 511
