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
17package com.google.common.util.concurrent;
18
19import static java.lang.reflect.Modifier.isStatic;
20import static java.util.concurrent.TimeUnit.MICROSECONDS;
21import static java.util.concurrent.TimeUnit.MILLISECONDS;
22import static java.util.concurrent.TimeUnit.NANOSECONDS;
23import static java.util.concurrent.TimeUnit.SECONDS;
24
25import com.google.common.collect.ImmutableClassToInstanceMap;
26import com.google.common.collect.ImmutableSet;
27import com.google.common.collect.Lists;
28import com.google.common.testing.NullPointerTester;
29import com.google.common.testing.NullPointerTester.Visibility;
30import com.google.common.util.concurrent.RateLimiter.SleepingStopwatch;
31
32import junit.framework.TestCase;
33
34import org.easymock.EasyMock;
35import org.mockito.Mockito;
36
37import java.lang.reflect.Method;
38import java.util.Arrays;
39import java.util.List;
40import java.util.Random;
41import java.util.concurrent.TimeUnit;
42
43/**
44 * Tests for RateLimiter.
45 *
46 * @author Dimitris Andreou
47 */
48public 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