001/*
002 * Licensed to the Apache Software Foundation (ASF) under one
003 * or more contributor license agreements.  See the NOTICE file
004 * distributed with this work for additional information
005 * regarding copyright ownership.  The ASF licenses this file
006 * to you under the Apache License, Version 2.0 (the
007 * "License"); you may not use this file except in compliance
008 * with the License.  You may obtain a copy of the License at
009 *
010 *     http://www.apache.org/licenses/LICENSE-2.0
011 *
012 * Unless required by applicable law or agreed to in writing, software
013 * distributed under the License is distributed on an "AS IS" BASIS,
014 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
015 * See the License for the specific language governing permissions and
016 * limitations under the License.
017 */
018package org.apache.hadoop.hbase.quotas;
019
020import static org.junit.Assert.assertEquals;
021import static org.junit.Assert.assertFalse;
022import static org.junit.Assert.assertNotEquals;
023import static org.junit.Assert.assertTrue;
024
025import java.util.concurrent.TimeUnit;
026import org.apache.hadoop.hbase.HBaseClassTestRule;
027import org.apache.hadoop.hbase.testclassification.RegionServerTests;
028import org.apache.hadoop.hbase.testclassification.SmallTests;
029import org.apache.hadoop.hbase.util.EnvironmentEdge;
030import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
031import org.apache.hadoop.hbase.util.ManualEnvironmentEdge;
032import org.junit.ClassRule;
033import org.junit.Test;
034import org.junit.experimental.categories.Category;
035
036/**
037 * Verify the behaviour of the Rate Limiter.
038 */
039@Category({ RegionServerTests.class, SmallTests.class })
040public class TestRateLimiter {
041
042  @ClassRule
043  public static final HBaseClassTestRule CLASS_RULE =
044    HBaseClassTestRule.forClass(TestRateLimiter.class);
045
046  @Test
047  public void testWaitIntervalTimeUnitSeconds() {
048    testWaitInterval(TimeUnit.SECONDS, 10, 100);
049  }
050
051  @Test
052  public void testWaitIntervalTimeUnitMinutes() {
053    testWaitInterval(TimeUnit.MINUTES, 10, 6000);
054  }
055
056  @Test
057  public void testWaitIntervalTimeUnitHours() {
058    testWaitInterval(TimeUnit.HOURS, 10, 360000);
059  }
060
061  @Test
062  public void testWaitIntervalTimeUnitDays() {
063    testWaitInterval(TimeUnit.DAYS, 10, 8640000);
064  }
065
066  private void testWaitInterval(final TimeUnit timeUnit, final long limit,
067    final long expectedWaitInterval) {
068    RateLimiter limiter = new AverageIntervalRateLimiter();
069    limiter.set(limit, timeUnit);
070
071    long nowTs = 0;
072    // consume all the available resources, one request at the time.
073    // the wait interval should be 0
074    for (int i = 0; i < (limit - 1); ++i) {
075      assertEquals(0, limiter.getWaitIntervalMs());
076      limiter.consume();
077      long waitInterval = limiter.waitInterval();
078      assertEquals(0, waitInterval);
079    }
080
081    for (int i = 0; i < (limit * 4); ++i) {
082      // There is one resource available, so we should be able to
083      // consume it without waiting.
084      limiter.setNextRefillTime(limiter.getNextRefillTime() - nowTs);
085      assertEquals(0, limiter.getWaitIntervalMs());
086      assertEquals(0, limiter.waitInterval());
087      limiter.consume();
088      // No more resources are available, we should wait for at least an interval.
089      long waitInterval = limiter.waitInterval();
090      assertEquals(expectedWaitInterval, waitInterval);
091
092      // set the nowTs to be the exact time when resources should be available again.
093      nowTs = waitInterval;
094
095      // artificially go into the past to prove that when too early we should fail.
096      long temp = nowTs + 500;
097      limiter.setNextRefillTime(limiter.getNextRefillTime() + temp);
098      assertNotEquals(0, limiter.getWaitIntervalMs());
099      // Roll back the nextRefillTime set to continue further testing
100      limiter.setNextRefillTime(limiter.getNextRefillTime() - temp);
101    }
102  }
103
104  @Test
105  public void testOverconsumptionAverageIntervalRefillStrategy() {
106    RateLimiter limiter = new AverageIntervalRateLimiter();
107    limiter.set(10, TimeUnit.SECONDS);
108
109    // 10 resources are available, but we need to consume 20 resources
110    // Verify that we have to wait at least 1.1sec to have 1 resource available
111    assertEquals(0, limiter.getWaitIntervalMs());
112    limiter.consume(20);
113    // We consumed twice the quota. Need to wait 1s to get back to 0, then another 100ms for the 1
114    assertEquals(1100, limiter.waitInterval(1));
115    // We consumed twice the quota. Need to wait 1s to get back to 0, then another 1s to get to 10
116    assertEquals(2000, limiter.waitInterval(10));
117
118    // Verify that after 1sec we need to wait for another 0.1sec to get a resource available
119    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
120    assertNotEquals(0, limiter.getWaitIntervalMs(1));
121    limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
122    // We've waited the full 1.1sec, should now have 1 available
123    assertEquals(0, limiter.getWaitIntervalMs(1));
124    assertEquals(0, limiter.waitInterval());
125  }
126
127  @Test
128  public void testOverconsumptionFixedIntervalRefillStrategy() throws InterruptedException {
129    RateLimiter limiter = new FixedIntervalRateLimiter();
130    limiter.set(10, TimeUnit.SECONDS);
131
132    // fix the current time in order to get the precise value of interval
133    EnvironmentEdge edge = new EnvironmentEdge() {
134      private final long ts = EnvironmentEdgeManager.currentTime();
135
136      @Override
137      public long currentTime() {
138        return ts;
139      }
140    };
141    EnvironmentEdgeManager.injectEdge(edge);
142    assertEquals(0, limiter.getWaitIntervalMs());
143    // 10 resources are available, but we need to consume 20 resources
144    limiter.consume(20);
145    // We over-consumed by 10. Since this is a fixed interval refill, where
146    // each interval we refill the full limit amount, we need to wait 2 intervals -- first
147    // interval gets us from -10 to 0, second gets us from 0 to 10, though we just want the 1.
148    assertEquals(2000, limiter.waitInterval(1));
149    EnvironmentEdgeManager.reset();
150
151    // Verify that after 1sec also no resource should be available
152    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
153    assertNotEquals(0, limiter.getWaitIntervalMs());
154    // Verify that after total 2sec the 10 resource is available
155    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
156    assertEquals(0, limiter.getWaitIntervalMs());
157    assertEquals(0, limiter.waitInterval());
158  }
159
160  @Test
161  public void testFixedIntervalResourceAvailability() throws Exception {
162    RateLimiter limiter = new FixedIntervalRateLimiter();
163    limiter.set(10, TimeUnit.SECONDS);
164
165    assertEquals(0, limiter.getWaitIntervalMs(10));
166    limiter.consume(3);
167    assertEquals(7, limiter.getAvailable());
168    assertNotEquals(0, limiter.getWaitIntervalMs(10));
169    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
170    assertEquals(0, limiter.getWaitIntervalMs(10));
171    assertEquals(10, limiter.getAvailable());
172  }
173
174  @Test
175  public void testLimiterBySmallerRate() throws InterruptedException {
176    // set limiter is 10 resources per seconds
177    RateLimiter limiter = new FixedIntervalRateLimiter();
178    limiter.set(10, TimeUnit.SECONDS);
179
180    int count = 0; // control the test count
181    while ((count++) < 10) {
182      // test will get 3 resources per 0.5 sec. so it will get 6 resources per sec.
183      limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
184      for (int i = 0; i < 3; i++) {
185        // 6 resources/sec < limit, so limiter.canExecute(nowTs, lastTs) should be true
186        assertEquals(limiter.getWaitIntervalMs(), 0);
187        limiter.consume();
188      }
189    }
190  }
191
192  @Test
193  public void testCanExecuteOfAverageIntervalRateLimiter() throws InterruptedException {
194    RateLimiter limiter = new AverageIntervalRateLimiter();
195    // when set limit is 100 per sec, this AverageIntervalRateLimiter will support at max 200 per
196    // sec
197    limiter.set(100, TimeUnit.SECONDS);
198    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
199    assertEquals(50, testCanExecuteByRate(limiter, 50));
200
201    // refill the avail to limit
202    limiter.set(100, TimeUnit.SECONDS);
203    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
204    assertEquals(100, testCanExecuteByRate(limiter, 100));
205
206    // refill the avail to limit
207    limiter.set(100, TimeUnit.SECONDS);
208    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
209    assertEquals(200, testCanExecuteByRate(limiter, 200));
210
211    // refill the avail to limit
212    limiter.set(100, TimeUnit.SECONDS);
213    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
214    assertEquals(200, testCanExecuteByRate(limiter, 500));
215  }
216
217  @Test
218  public void testCanExecuteOfFixedIntervalRateLimiter() throws InterruptedException {
219    RateLimiter limiter = new FixedIntervalRateLimiter();
220    // when set limit is 100 per sec, this FixedIntervalRateLimiter will support at max 100 per sec
221    limiter.set(100, TimeUnit.SECONDS);
222    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
223    assertEquals(50, testCanExecuteByRate(limiter, 50));
224
225    // refill the avail to limit
226    limiter.set(100, TimeUnit.SECONDS);
227    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
228    assertEquals(100, testCanExecuteByRate(limiter, 100));
229
230    // refill the avail to limit
231    limiter.set(100, TimeUnit.SECONDS);
232    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
233    assertEquals(100, testCanExecuteByRate(limiter, 200));
234  }
235
236  public int testCanExecuteByRate(RateLimiter limiter, int rate) {
237    int request = 0;
238    int count = 0;
239    while ((request++) < rate) {
240      limiter.setNextRefillTime(limiter.getNextRefillTime() - limiter.getTimeUnitInMillis() / rate);
241      if (limiter.getWaitIntervalMs() == 0) {
242        count++;
243        limiter.consume();
244      }
245    }
246    return count;
247  }
248
249  @Test
250  public void testRefillOfAverageIntervalRateLimiter() throws InterruptedException {
251    RateLimiter limiter = new AverageIntervalRateLimiter();
252    limiter.set(60, TimeUnit.SECONDS);
253    assertEquals(60, limiter.getAvailable());
254    // first refill, will return the number same with limit
255    assertEquals(60, limiter.refill(limiter.getLimit()));
256
257    limiter.consume(30);
258
259    // after 0.2 sec, refill should return 12
260    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
261    assertEquals(12, limiter.refill(limiter.getLimit()));
262
263    // after 0.5 sec, refill should return 30
264    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
265    assertEquals(30, limiter.refill(limiter.getLimit()));
266
267    // after 1 sec, refill should return 60
268    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
269    assertEquals(60, limiter.refill(limiter.getLimit()));
270
271    // after more than 1 sec, refill should return at max 60
272    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
273    assertEquals(60, limiter.refill(limiter.getLimit()));
274    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
275    assertEquals(60, limiter.refill(limiter.getLimit()));
276  }
277
278  @Test
279  public void testRefillOfFixedIntervalRateLimiter() throws InterruptedException {
280    RateLimiter limiter = new FixedIntervalRateLimiter();
281    limiter.set(60, TimeUnit.SECONDS);
282    assertEquals(60, limiter.getAvailable());
283    // first refill, will return the number same with limit
284    assertEquals(60, limiter.refill(limiter.getLimit()));
285
286    limiter.consume(30);
287
288    // after 0.2 sec, refill should return 0
289    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
290    assertEquals(0, limiter.refill(limiter.getLimit()));
291
292    // after 0.5 sec, refill should return 0
293    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
294    assertEquals(0, limiter.refill(limiter.getLimit()));
295
296    // after 1 sec, refill should return 60
297    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
298    assertEquals(60, limiter.refill(limiter.getLimit()));
299
300    // after more than 1 sec, refill should return at max 60
301    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
302    assertEquals(60, limiter.refill(limiter.getLimit()));
303    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
304    assertEquals(60, limiter.refill(limiter.getLimit()));
305  }
306
307  @Test
308  public void testUnconfiguredLimiters() throws InterruptedException {
309
310    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
311    EnvironmentEdgeManager.injectEdge(testEdge);
312    long limit = Long.MAX_VALUE;
313
314    // For unconfigured limiters, it is supposed to use as much as possible
315    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
316    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
317
318    assertEquals(limit, avgLimiter.getAvailable());
319    assertEquals(limit, fixLimiter.getAvailable());
320
321    assertEquals(0, avgLimiter.getWaitIntervalMs(limit));
322    avgLimiter.consume(limit);
323
324    assertEquals(0, fixLimiter.getWaitIntervalMs(limit));
325    fixLimiter.consume(limit);
326
327    // Make sure that available is Long.MAX_VALUE
328    assertEquals(limit, avgLimiter.getAvailable());
329    assertEquals(limit, fixLimiter.getAvailable());
330
331    // after 100 millseconds, it should be able to execute limit as well
332    testEdge.incValue(100);
333
334    assertEquals(0, avgLimiter.getWaitIntervalMs(limit));
335    avgLimiter.consume(limit);
336
337    assertEquals(0, fixLimiter.getWaitIntervalMs(limit));
338    fixLimiter.consume(limit);
339
340    // Make sure that available is Long.MAX_VALUE
341    assertEquals(limit, avgLimiter.getAvailable());
342    assertEquals(limit, fixLimiter.getAvailable());
343
344    EnvironmentEdgeManager.reset();
345  }
346
347  @Test
348  public void testExtremeLimiters() throws InterruptedException {
349
350    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
351    EnvironmentEdgeManager.injectEdge(testEdge);
352    long limit = Long.MAX_VALUE - 1;
353
354    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
355    avgLimiter.set(limit, TimeUnit.SECONDS);
356    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
357    fixLimiter.set(limit, TimeUnit.SECONDS);
358
359    assertEquals(limit, avgLimiter.getAvailable());
360    assertEquals(limit, fixLimiter.getAvailable());
361
362    assertEquals(0, avgLimiter.getWaitIntervalMs(limit / 2));
363    avgLimiter.consume(limit / 2);
364
365    assertEquals(0, fixLimiter.getWaitIntervalMs(limit / 2));
366    fixLimiter.consume(limit / 2);
367
368    // Make sure that available is whatever left
369    assertEquals((limit - (limit / 2)), avgLimiter.getAvailable());
370    assertEquals((limit - (limit / 2)), fixLimiter.getAvailable());
371
372    // after 100 millseconds, both should not be able to execute the limit
373    testEdge.incValue(100);
374
375    assertNotEquals(0, avgLimiter.getWaitIntervalMs(limit));
376    assertNotEquals(0, fixLimiter.getWaitIntervalMs(limit));
377
378    // after 500 millseconds, average interval limiter should be able to execute the limit
379    testEdge.incValue(500);
380    assertEquals(0, avgLimiter.getWaitIntervalMs(limit));
381    assertNotEquals(0, fixLimiter.getWaitIntervalMs(limit));
382
383    // Make sure that available is correct
384    assertEquals(limit, avgLimiter.getAvailable());
385    assertEquals((limit - (limit / 2)), fixLimiter.getAvailable());
386
387    // after 500 millseconds, both should be able to execute
388    testEdge.incValue(500);
389    assertEquals(0, avgLimiter.getWaitIntervalMs(limit));
390    assertEquals(0, fixLimiter.getWaitIntervalMs(limit));
391
392    // Make sure that available is Long.MAX_VALUE
393    assertEquals(limit, avgLimiter.getAvailable());
394    assertEquals(limit, fixLimiter.getAvailable());
395
396    EnvironmentEdgeManager.reset();
397  }
398
399  /*
400   * This test case is tricky. Basically, it simulates the following events: Thread-1 Thread-2 t0:
401   * canExecute(100) and consume(100) t1: canExecute(100), avail may be increased by 80 t2:
402   * consume(-80) as actual size is 20 It will check if consume(-80) can handle overflow correctly.
403   */
404  @Test
405  public void testLimiterCompensationOverflow() throws InterruptedException {
406
407    long limit = Long.MAX_VALUE - 1;
408    long guessNumber = 100;
409
410    // For unconfigured limiters, it is supposed to use as much as possible
411    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
412    avgLimiter.set(limit, TimeUnit.SECONDS);
413
414    assertEquals(limit, avgLimiter.getAvailable());
415
416    // The initial guess is that 100 bytes.
417    assertEquals(0, avgLimiter.getWaitIntervalMs(guessNumber));
418    avgLimiter.consume(guessNumber);
419
420    // Make sure that available is whatever left
421    assertEquals((limit - guessNumber), avgLimiter.getAvailable());
422
423    // Manually set avil to simulate that another thread call canExecute().
424    // It is simulated by consume().
425    avgLimiter.consume(-80);
426    assertEquals((limit - guessNumber + 80), avgLimiter.getAvailable());
427
428    // Now thread1 compensates 80
429    avgLimiter.consume(-80);
430    assertEquals(limit, avgLimiter.getAvailable());
431  }
432
433  @Test
434  public void itRunsFullWithPartialRefillInterval() {
435    RateLimiter limiter = new FixedIntervalRateLimiter(100);
436    limiter.set(10, TimeUnit.SECONDS);
437    assertEquals(0, limiter.getWaitIntervalMs());
438
439    // Consume the quota
440    limiter.consume(10);
441
442    // Need to wait 1s to acquire another resource
443    long waitInterval = limiter.waitInterval(10);
444    assertTrue(900 < waitInterval);
445    assertTrue(1000 >= waitInterval);
446    // We need to wait 2s to acquire more than 10 resources
447    waitInterval = limiter.waitInterval(20);
448    assertTrue(1900 < waitInterval);
449    assertTrue(2000 >= waitInterval);
450
451    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
452    // We've waited the full interval, so we should now have 10
453    assertEquals(0, limiter.getWaitIntervalMs(10));
454    assertEquals(0, limiter.waitInterval());
455  }
456
457  @Test
458  public void itRunsPartialRefillIntervals() {
459    RateLimiter limiter = new FixedIntervalRateLimiter(100);
460    limiter.set(10, TimeUnit.SECONDS);
461    assertEquals(0, limiter.getWaitIntervalMs());
462
463    // Consume the quota
464    limiter.consume(10);
465
466    // Need to wait 1s to acquire another resource
467    long waitInterval = limiter.waitInterval(10);
468    assertTrue(900 < waitInterval);
469    assertTrue(1000 >= waitInterval);
470    // We need to wait 2s to acquire more than 10 resources
471    waitInterval = limiter.waitInterval(20);
472    assertTrue(1900 < waitInterval);
473    assertTrue(2000 >= waitInterval);
474    // We need to wait 0<=x<=100ms to acquire 1 resource
475    waitInterval = limiter.waitInterval(1);
476    assertTrue(0 < waitInterval);
477    assertTrue(100 >= waitInterval);
478
479    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
480    // We've waited half the interval, so we should now have half available
481    assertEquals(0, limiter.getWaitIntervalMs(5));
482    assertEquals(0, limiter.waitInterval());
483  }
484
485  @Test
486  public void itRunsRepeatedPartialRefillIntervals() {
487    RateLimiter limiter = new FixedIntervalRateLimiter(100);
488    limiter.set(10, TimeUnit.SECONDS);
489    assertEquals(0, limiter.getWaitIntervalMs());
490    // Consume the quota
491    limiter.consume(10);
492    for (int i = 0; i < 100; i++) {
493      limiter.setNextRefillTime(limiter.getNextRefillTime() - 100); // free 1 resource
494      limiter.consume(1);
495      assertFalse(limiter.isAvailable(1)); // all resources consumed
496      assertTrue(limiter.isAvailable(0)); // not negative
497    }
498  }
499}