1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
45
46
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();
56 limiter.acquire();
57 limiter.acquire();
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();
120 stopwatch.sleepMillis(200);
121 limiter.acquire();
122 limiter.acquire();
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);
129 stopwatch.sleepMillis(200);
130 assertEquals(0.0, limiter.acquire(), EPSILON);
131 assertEquals(0.2, limiter.acquire(), EPSILON);
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);
147 stopwatch.sleepMillis(1000);
148 limiter.acquire(1);
149
150 limiter.acquire(1);
151 limiter.acquire(3);
152 limiter.acquire(1);
153
154 limiter.acquire();
155 assertEvents("U1.00", "U1.00",
156 "R0.00", "R0.00", "R0.00", "R0.00",
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();
181 }
182 stopwatch.sleepMillis(500);
183 stopwatch.sleepMillis(4000);
184 for (int i = 0; i < 8; i++) {
185 limiter.acquire();
186 }
187 stopwatch.sleepMillis(500);
188 stopwatch.sleepMillis(2000);
189 for (int i = 0; i < 8; i++) {
190 limiter.acquire();
191 }
192 assertEvents(
193 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50",
194 "U0.50",
195 "U4.00",
196 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50",
197 "U0.50",
198 "U2.00",
199 "R0.00, R0.50, R0.50, R0.50, R0.50, R0.50, R0.50, R0.50");
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();
206 }
207 stopwatch.sleepMillis(4500);
208 for (int i = 0; i < 3; i++) {
209 limiter.acquire();
210 }
211
212 limiter.setRate(4.0);
213 limiter.acquire();
214 for (int i = 0; i < 4; i++) {
215 limiter.acquire();
216 }
217 stopwatch.sleepMillis(4250);
218 for (int i = 0; i < 11; i++) {
219 limiter.acquire();
220 }
221
222
223 assertEvents(
224 "R0.00, R1.38, R1.13, R0.88, R0.63, R0.50, R0.50, R0.50",
225 "U4.50",
226 "R0.00, R1.38, R1.13",
227 "R0.88",
228 "R0.34, R0.28, R0.25, R0.25",
229 "U4.25",
230 "R0.00, R0.72, R0.66, R0.59, R0.53, R0.47, R0.41",
231 "R0.34, R0.28, R0.25, R0.25");
232 }
233
234 public void testBurstyAndUpdate() {
235 RateLimiter rateLimiter = RateLimiter.create(stopwatch, 1.0);
236 rateLimiter.acquire(1);
237 rateLimiter.acquire(1);
238
239 rateLimiter.setRate(2.0);
240
241 rateLimiter.acquire(1);
242 rateLimiter.acquire(2);
243 rateLimiter.acquire(4);
244 rateLimiter.acquire(1);
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);
285 rateLimiter.acquire(1);
286 rateLimiter.acquire(2);
287 rateLimiter.acquire(4);
288 rateLimiter.acquire(8);
289 rateLimiter.acquire(1);
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");
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",
308 "R0.00",
309 "R0.00",
310 "R0.50",
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");
318 }
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
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
380 assertTrue(burst <= 1000);
381 long afterBurst = measureTotalTimeMillis(limiter, oneSecWorthOfWork, new Random());
382
383 assertTrue(afterBurst >= 1000);
384 }
385 }
386
387
388
389
390
391
392
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
401
402
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);
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
436
437
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
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 }