View Javadoc

1   /**
2    * Licensed to the Apache Software Foundation (ASF) under one or more contributor license
3    * agreements. See the NOTICE file distributed with this work for additional information regarding
4    * copyright ownership. The ASF licenses this file to you under the Apache License, Version 2.0 (the
5    * "License"); you may not use this file except in compliance with the License. You may obtain a
6    * copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable
7    * law or agreed to in writing, software distributed under the License is distributed on an "AS IS"
8    * BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License
9    * for the specific language governing permissions and limitations under the License.
10   */
11  
12  package org.apache.hadoop.hbase.quotas;
13  
14  import static org.junit.Assert.assertEquals;
15  import static org.junit.Assert.assertFalse;
16  import static org.junit.Assert.assertTrue;
17  
18  import java.util.concurrent.TimeUnit;
19  
20  import org.apache.hadoop.hbase.testclassification.SmallTests;
21  import org.apache.hadoop.hbase.util.ManualEnvironmentEdge;
22  import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
23  import org.junit.Test;
24  import org.junit.experimental.categories.Category;
25  
26  /**
27   * Verify the behaviour of the Rate Limiter.
28   */
29  @Category({ SmallTests.class })
30  public class TestRateLimiter {
31    @Test
32    public void testWaitIntervalTimeUnitSeconds() {
33      testWaitInterval(TimeUnit.SECONDS, 10, 100);
34    }
35  
36    @Test
37    public void testWaitIntervalTimeUnitMinutes() {
38      testWaitInterval(TimeUnit.MINUTES, 10, 6000);
39    }
40  
41    @Test
42    public void testWaitIntervalTimeUnitHours() {
43      testWaitInterval(TimeUnit.HOURS, 10, 360000);
44    }
45  
46    @Test
47    public void testWaitIntervalTimeUnitDays() {
48      testWaitInterval(TimeUnit.DAYS, 10, 8640000);
49    }
50  
51    private void testWaitInterval(final TimeUnit timeUnit, final long limit,
52                                  final long expectedWaitInterval) {
53      RateLimiter limiter = new AverageIntervalRateLimiter();
54      limiter.set(limit, timeUnit);
55  
56      long nowTs = 0;
57      // consume all the available resources, one request at the time.
58      // the wait interval should be 0
59      for (int i = 0; i < (limit - 1); ++i) {
60        assertTrue(limiter.canExecute());
61        limiter.consume();
62        long waitInterval = limiter.waitInterval();
63        assertEquals(0, waitInterval);
64      }
65  
66      for (int i = 0; i < (limit * 4); ++i) {
67        // There is one resource available, so we should be able to
68        // consume it without waiting.
69        limiter.setNextRefillTime(limiter.getNextRefillTime() - nowTs);
70        assertTrue(limiter.canExecute());
71        assertEquals(0, limiter.waitInterval());
72        limiter.consume();
73        // No more resources are available, we should wait for at least an interval.
74        long waitInterval = limiter.waitInterval();
75        assertEquals(expectedWaitInterval, waitInterval);
76  
77        // set the nowTs to be the exact time when resources should be available again.
78        nowTs = waitInterval;
79  
80        // artificially go into the past to prove that when too early we should fail.
81        long temp = nowTs + 500;
82        limiter.setNextRefillTime(limiter.getNextRefillTime() + temp);
83        assertFalse(limiter.canExecute());
84        //Roll back the nextRefillTime set to continue further testing
85        limiter.setNextRefillTime(limiter.getNextRefillTime() - temp);
86      }
87    }
88  
89    @Test
90    public void testOverconsumptionAverageIntervalRefillStrategy() {
91      RateLimiter limiter = new AverageIntervalRateLimiter();
92      limiter.set(10, TimeUnit.SECONDS);
93  
94      // 10 resources are available, but we need to consume 20 resources
95      // Verify that we have to wait at least 1.1sec to have 1 resource available
96      assertTrue(limiter.canExecute());
97      limiter.consume(20);
98      // To consume 1 resource wait for 100ms
99      assertEquals(100, limiter.waitInterval(1));
100     // To consume 10 resource wait for 1000ms
101     assertEquals(1000, limiter.waitInterval(10));
102 
103     limiter.setNextRefillTime(limiter.getNextRefillTime() - 900);
104     // Verify that after 1sec the 1 resource is available
105     assertTrue(limiter.canExecute(1));
106     limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
107     // Verify that after 1sec the 10 resource is available
108     assertTrue(limiter.canExecute());
109     assertEquals(0, limiter.waitInterval());
110   }
111 
112   @Test
113   public void testOverconsumptionFixedIntervalRefillStrategy() throws InterruptedException {
114     RateLimiter limiter = new FixedIntervalRateLimiter();
115     limiter.set(10, TimeUnit.SECONDS);
116 
117     // 10 resources are available, but we need to consume 20 resources
118     // Verify that we have to wait at least 1.1sec to have 1 resource available
119     assertTrue(limiter.canExecute());
120     limiter.consume(20);
121     // To consume 1 resource also wait for 1000ms
122     assertEquals(1000, limiter.waitInterval(1));
123     // To consume 10 resource wait for 100ms
124     assertEquals(1000, limiter.waitInterval(10));
125 
126     limiter.setNextRefillTime(limiter.getNextRefillTime() - 900);
127     // Verify that after 1sec also no resource should be available
128     assertFalse(limiter.canExecute(1));
129     limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
130 
131     // Verify that after 1sec the 10 resource is available
132     assertTrue(limiter.canExecute());
133     assertEquals(0, limiter.waitInterval());
134   }
135 
136   @Test
137   public void testFixedIntervalResourceAvailability() throws Exception {
138     RateLimiter limiter = new FixedIntervalRateLimiter();
139     limiter.set(10, TimeUnit.SECONDS);
140 
141     assertTrue(limiter.canExecute(10));
142     limiter.consume(3);
143     assertEquals(7, limiter.getAvailable());
144     assertFalse(limiter.canExecute(10));
145     limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
146     assertTrue(limiter.canExecute(10));
147     assertEquals(10, limiter.getAvailable());
148   }
149 
150   @Test
151   public void testLimiterBySmallerRate() throws InterruptedException {
152     // set limiter is 10 resources per seconds
153     RateLimiter limiter = new FixedIntervalRateLimiter();
154     limiter.set(10, TimeUnit.SECONDS);
155 
156     int count = 0; // control the test count
157     while ((count++) < 10) {
158       // test will get 3 resources per 0.5 sec. so it will get 6 resources per sec.
159       limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
160       for (int i = 0; i < 3; i++) {
161         // 6 resources/sec < limit, so limiter.canExecute(nowTs, lastTs) should be true
162         assertEquals(true, limiter.canExecute());
163         limiter.consume();
164       }
165     }
166   }
167 
168   @Test
169   public void testCanExecuteOfAverageIntervalRateLimiter() throws InterruptedException {
170     RateLimiter limiter = new AverageIntervalRateLimiter();
171     // when set limit is 100 per sec, this AverageIntervalRateLimiter will support at max 200 per sec
172     limiter.set(100, TimeUnit.SECONDS);
173     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
174     assertEquals(50, testCanExecuteByRate(limiter, 50));
175 
176     // refill the avail to limit
177     limiter.set(100, TimeUnit.SECONDS);
178     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
179     assertEquals(100, testCanExecuteByRate(limiter, 100));
180 
181     // refill the avail to limit
182     limiter.set(100, TimeUnit.SECONDS);
183     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
184     assertEquals(200, testCanExecuteByRate(limiter, 200));
185 
186     // refill the avail to limit
187     limiter.set(100, TimeUnit.SECONDS);
188     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
189     assertEquals(200, testCanExecuteByRate(limiter, 500));
190   }
191 
192   @Test
193   public void testCanExecuteOfFixedIntervalRateLimiter() throws InterruptedException {
194     RateLimiter limiter = new FixedIntervalRateLimiter();
195     // when set limit is 100 per sec, this FixedIntervalRateLimiter will support at max 100 per sec
196     limiter.set(100, TimeUnit.SECONDS);
197     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
198     assertEquals(50, testCanExecuteByRate(limiter, 50));
199 
200     // refill the avail to limit
201     limiter.set(100, TimeUnit.SECONDS);
202     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
203     assertEquals(100, testCanExecuteByRate(limiter, 100));
204 
205     // refill the avail to limit
206     limiter.set(100, TimeUnit.SECONDS);
207     limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
208     assertEquals(100, testCanExecuteByRate(limiter, 200));
209   }
210 
211   public int testCanExecuteByRate(RateLimiter limiter, int rate) {
212     int request = 0;
213     int count = 0;
214     while ((request++) < rate) {
215       limiter.setNextRefillTime(limiter.getNextRefillTime() - limiter.getTimeUnitInMillis() / rate);
216       if (limiter.canExecute()) {
217         count++;
218         limiter.consume();
219       }
220     }
221     return count;
222   }
223 
224   @Test
225   public void testRefillOfAverageIntervalRateLimiter() throws InterruptedException {
226     RateLimiter limiter = new AverageIntervalRateLimiter();
227     limiter.set(60, TimeUnit.SECONDS);
228     assertEquals(60, limiter.getAvailable());
229     // first refill, will return the number same with limit
230     assertEquals(60, limiter.refill(limiter.getLimit()));
231 
232     limiter.consume(30);
233 
234     // after 0.2 sec, refill should return 12
235     limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
236     assertEquals(12, limiter.refill(limiter.getLimit()));
237 
238     // after 0.5 sec, refill should return 30
239     limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
240     assertEquals(30, limiter.refill(limiter.getLimit()));
241 
242     // after 1 sec, refill should return 60
243     limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
244     assertEquals(60, limiter.refill(limiter.getLimit()));
245 
246     // after more than 1 sec, refill should return at max 60
247     limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
248     assertEquals(60, limiter.refill(limiter.getLimit()));
249     limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
250     assertEquals(60, limiter.refill(limiter.getLimit()));
251   }
252 
253   @Test
254   public void testRefillOfFixedIntervalRateLimiter() throws InterruptedException {
255     RateLimiter limiter = new FixedIntervalRateLimiter();
256     limiter.set(60, TimeUnit.SECONDS);
257     assertEquals(60, limiter.getAvailable());
258     // first refill, will return the number same with limit
259     assertEquals(60, limiter.refill(limiter.getLimit()));
260 
261     limiter.consume(30);
262 
263     // after 0.2 sec, refill should return 0
264     limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
265     assertEquals(0, limiter.refill(limiter.getLimit()));
266 
267     // after 0.5 sec, refill should return 0
268     limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
269     assertEquals(0, limiter.refill(limiter.getLimit()));
270 
271     // after 1 sec, refill should return 60
272     limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
273     assertEquals(60, limiter.refill(limiter.getLimit()));
274 
275     // after more than 1 sec, refill should return at max 60
276     limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
277     assertEquals(60, limiter.refill(limiter.getLimit()));
278     limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
279     assertEquals(60, limiter.refill(limiter.getLimit()));
280   }
281 
282   @Test
283   public void testUnconfiguredLimiters() throws InterruptedException {
284 
285     ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
286     EnvironmentEdgeManager.injectEdge(testEdge);
287     long limit = Long.MAX_VALUE;
288 
289     // For unconfigured limiters, it is supposed to use as much as possible
290     RateLimiter avgLimiter = new AverageIntervalRateLimiter();
291     RateLimiter fixLimiter = new FixedIntervalRateLimiter();
292 
293     assertEquals(limit, avgLimiter.getAvailable());
294     assertEquals(limit, fixLimiter.getAvailable());
295 
296     assertTrue(avgLimiter.canExecute(limit));
297     avgLimiter.consume(limit);
298 
299     assertTrue(fixLimiter.canExecute(limit));
300     fixLimiter.consume(limit);
301 
302     // Make sure that available is Long.MAX_VALUE
303     assertTrue(limit == avgLimiter.getAvailable());
304     assertTrue(limit == fixLimiter.getAvailable());
305 
306     // after 100 millseconds, it should be able to execute limit as well
307     testEdge.incValue(100);
308 
309     assertTrue(avgLimiter.canExecute(limit));
310     avgLimiter.consume(limit);
311 
312     assertTrue(fixLimiter.canExecute(limit));
313     fixLimiter.consume(limit);
314 
315     // Make sure that available is Long.MAX_VALUE
316     assertTrue(limit == avgLimiter.getAvailable());
317     assertTrue(limit == fixLimiter.getAvailable());
318 
319     EnvironmentEdgeManager.reset();
320   }
321 
322   @Test
323   public void testExtremeLimiters() throws InterruptedException {
324 
325     ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
326     EnvironmentEdgeManager.injectEdge(testEdge);
327     long limit = Long.MAX_VALUE - 1;
328 
329     RateLimiter avgLimiter = new AverageIntervalRateLimiter();
330     avgLimiter.set(limit, TimeUnit.SECONDS);
331     RateLimiter fixLimiter = new FixedIntervalRateLimiter();
332     fixLimiter.set(limit, TimeUnit.SECONDS);
333 
334     assertEquals(limit, avgLimiter.getAvailable());
335     assertEquals(limit, fixLimiter.getAvailable());
336 
337     assertTrue(avgLimiter.canExecute(limit / 2));
338     avgLimiter.consume(limit / 2);
339 
340     assertTrue(fixLimiter.canExecute(limit / 2));
341     fixLimiter.consume(limit / 2);
342 
343     // Make sure that available is whatever left
344     assertTrue((limit - (limit / 2)) == avgLimiter.getAvailable());
345     assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
346 
347     // after 100 millseconds, both should not be able to execute the limit
348     testEdge.incValue(100);
349 
350     assertFalse(avgLimiter.canExecute(limit));
351     assertFalse(fixLimiter.canExecute(limit));
352 
353     // after 500 millseconds, average interval limiter should be able to execute the limit
354     testEdge.incValue(500);
355     assertTrue(avgLimiter.canExecute(limit));
356     assertFalse(fixLimiter.canExecute(limit));
357 
358     // Make sure that available is correct
359     assertTrue(limit == avgLimiter.getAvailable());
360     assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
361 
362     // after 500 millseconds, both should be able to execute
363     testEdge.incValue(500);
364     assertTrue(avgLimiter.canExecute(limit));
365     assertTrue(fixLimiter.canExecute(limit));
366 
367     // Make sure that available is Long.MAX_VALUE
368     assertTrue(limit == avgLimiter.getAvailable());
369     assertTrue(limit == fixLimiter.getAvailable());
370 
371     EnvironmentEdgeManager.reset();
372   }
373 
374   /*
375    * This test case is tricky. Basically, it simulates the following events:
376    *           Thread-1                             Thread-2
377    * t0:  canExecute(100) and consume(100)
378    * t1:                                         canExecute(100), avail may be increased by 80
379    * t2:  consume(-80) as actual size is 20
380    * It will check if consume(-80) can handle overflow correctly.
381    */
382   @Test
383   public void testLimiterCompensationOverflow() throws InterruptedException {
384 
385     long limit = Long.MAX_VALUE - 1;
386     long guessNumber = 100;
387 
388     // For unconfigured limiters, it is supposed to use as much as possible
389     RateLimiter avgLimiter = new AverageIntervalRateLimiter();
390     avgLimiter.set(limit, TimeUnit.SECONDS);
391 
392     assertEquals(limit, avgLimiter.getAvailable());
393 
394     // The initial guess is that 100 bytes.
395     assertTrue(avgLimiter.canExecute(guessNumber));
396     avgLimiter.consume(guessNumber);
397 
398     // Make sure that available is whatever left
399     assertTrue((limit - guessNumber) == avgLimiter.getAvailable());
400 
401     // Manually set avil to simulate that another thread call canExecute().
402     // It is simulated by consume().
403     avgLimiter.consume(-80);
404     assertTrue((limit - guessNumber + 80) == avgLimiter.getAvailable());
405 
406     // Now thread1 compensates 80
407     avgLimiter.consume(-80);
408     assertTrue(limit == avgLimiter.getAvailable());
409 
410   }
411 }