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.assertTrue;
023
024import java.util.concurrent.TimeUnit;
025import org.apache.hadoop.hbase.HBaseClassTestRule;
026import org.apache.hadoop.hbase.testclassification.RegionServerTests;
027import org.apache.hadoop.hbase.testclassification.SmallTests;
028import org.apache.hadoop.hbase.util.EnvironmentEdge;
029import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
030import org.apache.hadoop.hbase.util.ManualEnvironmentEdge;
031import org.junit.ClassRule;
032import org.junit.Test;
033import org.junit.experimental.categories.Category;
034
035/**
036 * Verify the behaviour of the Rate Limiter.
037 */
038@Category({RegionServerTests.class, SmallTests.class})
039public class TestRateLimiter {
040
041  @ClassRule
042  public static final HBaseClassTestRule CLASS_RULE =
043      HBaseClassTestRule.forClass(TestRateLimiter.class);
044
045  @Test
046  public void testWaitIntervalTimeUnitSeconds() {
047    testWaitInterval(TimeUnit.SECONDS, 10, 100);
048  }
049
050  @Test
051  public void testWaitIntervalTimeUnitMinutes() {
052    testWaitInterval(TimeUnit.MINUTES, 10, 6000);
053  }
054
055  @Test
056  public void testWaitIntervalTimeUnitHours() {
057    testWaitInterval(TimeUnit.HOURS, 10, 360000);
058  }
059
060  @Test
061  public void testWaitIntervalTimeUnitDays() {
062    testWaitInterval(TimeUnit.DAYS, 10, 8640000);
063  }
064
065  private void testWaitInterval(final TimeUnit timeUnit, final long limit,
066      final long expectedWaitInterval) {
067    RateLimiter limiter = new AverageIntervalRateLimiter();
068    limiter.set(limit, timeUnit);
069
070    long nowTs = 0;
071    // consume all the available resources, one request at the time.
072    // the wait interval should be 0
073    for (int i = 0; i < (limit - 1); ++i) {
074      assertTrue(limiter.canExecute());
075      limiter.consume();
076      long waitInterval = limiter.waitInterval();
077      assertEquals(0, waitInterval);
078    }
079
080    for (int i = 0; i < (limit * 4); ++i) {
081      // There is one resource available, so we should be able to
082      // consume it without waiting.
083      limiter.setNextRefillTime(limiter.getNextRefillTime() - nowTs);
084      assertTrue(limiter.canExecute());
085      assertEquals(0, limiter.waitInterval());
086      limiter.consume();
087      // No more resources are available, we should wait for at least an interval.
088      long waitInterval = limiter.waitInterval();
089      assertEquals(expectedWaitInterval, waitInterval);
090
091      // set the nowTs to be the exact time when resources should be available again.
092      nowTs = waitInterval;
093
094      // artificially go into the past to prove that when too early we should fail.
095      long temp = nowTs + 500;
096      limiter.setNextRefillTime(limiter.getNextRefillTime() + temp);
097      assertFalse(limiter.canExecute());
098      //Roll back the nextRefillTime set to continue further testing
099      limiter.setNextRefillTime(limiter.getNextRefillTime() - temp);
100    }
101  }
102
103  @Test
104  public void testOverconsumptionAverageIntervalRefillStrategy() {
105    RateLimiter limiter = new AverageIntervalRateLimiter();
106    limiter.set(10, TimeUnit.SECONDS);
107
108    // 10 resources are available, but we need to consume 20 resources
109    // Verify that we have to wait at least 1.1sec to have 1 resource available
110    assertTrue(limiter.canExecute());
111    limiter.consume(20);
112    // To consume 1 resource wait for 100ms
113    assertEquals(100, limiter.waitInterval(1));
114    // To consume 10 resource wait for 1000ms
115    assertEquals(1000, limiter.waitInterval(10));
116
117    limiter.setNextRefillTime(limiter.getNextRefillTime() - 900);
118    // Verify that after 1sec the 1 resource is available
119    assertTrue(limiter.canExecute(1));
120    limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
121    // Verify that after 1sec the 10 resource is available
122    assertTrue(limiter.canExecute());
123    assertEquals(0, limiter.waitInterval());
124  }
125
126  @Test
127  public void testOverconsumptionFixedIntervalRefillStrategy() throws InterruptedException {
128    RateLimiter limiter = new FixedIntervalRateLimiter();
129    limiter.set(10, TimeUnit.SECONDS);
130
131    // fix the current time in order to get the precise value of interval
132    EnvironmentEdge edge = new EnvironmentEdge() {
133      private final long ts = System.currentTimeMillis();
134
135      @Override
136      public long currentTime() {
137        return ts;
138      }
139    };
140    EnvironmentEdgeManager.injectEdge(edge);
141    // 10 resources are available, but we need to consume 20 resources
142    // Verify that we have to wait at least 1.1sec to have 1 resource available
143    assertTrue(limiter.canExecute());
144    limiter.consume(20);
145    // To consume 1 resource also wait for 1000ms
146    assertEquals(1000, limiter.waitInterval(1));
147    // To consume 10 resource wait for 100ms
148    assertEquals(1000, limiter.waitInterval(10));
149    EnvironmentEdgeManager.reset();
150
151    limiter.setNextRefillTime(limiter.getNextRefillTime() - 900);
152    // Verify that after 1sec also no resource should be available
153    assertFalse(limiter.canExecute(1));
154    limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
155
156    // Verify that after 1sec the 10 resource is available
157    assertTrue(limiter.canExecute());
158    assertEquals(0, limiter.waitInterval());
159  }
160
161  @Test
162  public void testFixedIntervalResourceAvailability() throws Exception {
163    RateLimiter limiter = new FixedIntervalRateLimiter();
164    limiter.set(10, TimeUnit.SECONDS);
165
166    assertTrue(limiter.canExecute(10));
167    limiter.consume(3);
168    assertEquals(7, limiter.getAvailable());
169    assertFalse(limiter.canExecute(10));
170    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
171    assertTrue(limiter.canExecute(10));
172    assertEquals(10, limiter.getAvailable());
173  }
174
175  @Test
176  public void testLimiterBySmallerRate() throws InterruptedException {
177    // set limiter is 10 resources per seconds
178    RateLimiter limiter = new FixedIntervalRateLimiter();
179    limiter.set(10, TimeUnit.SECONDS);
180
181    int count = 0; // control the test count
182    while ((count++) < 10) {
183      // test will get 3 resources per 0.5 sec. so it will get 6 resources per sec.
184      limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
185      for (int i = 0; i < 3; i++) {
186        // 6 resources/sec < limit, so limiter.canExecute(nowTs, lastTs) should be true
187        assertEquals(true, limiter.canExecute());
188        limiter.consume();
189      }
190    }
191  }
192
193  @Test
194  public void testCanExecuteOfAverageIntervalRateLimiter() throws InterruptedException {
195    RateLimiter limiter = new AverageIntervalRateLimiter();
196    // when set limit is 100 per sec, this AverageIntervalRateLimiter will support at max 200 per 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.canExecute()) {
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    assertTrue(avgLimiter.canExecute(limit));
322    avgLimiter.consume(limit);
323
324    assertTrue(fixLimiter.canExecute(limit));
325    fixLimiter.consume(limit);
326
327    // Make sure that available is Long.MAX_VALUE
328    assertTrue(limit == avgLimiter.getAvailable());
329    assertTrue(limit == fixLimiter.getAvailable());
330
331    // after 100 millseconds, it should be able to execute limit as well
332    testEdge.incValue(100);
333
334    assertTrue(avgLimiter.canExecute(limit));
335    avgLimiter.consume(limit);
336
337    assertTrue(fixLimiter.canExecute(limit));
338    fixLimiter.consume(limit);
339
340    // Make sure that available is Long.MAX_VALUE
341    assertTrue(limit == avgLimiter.getAvailable());
342    assertTrue(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    assertTrue(avgLimiter.canExecute(limit / 2));
363    avgLimiter.consume(limit / 2);
364
365    assertTrue(fixLimiter.canExecute(limit / 2));
366    fixLimiter.consume(limit / 2);
367
368    // Make sure that available is whatever left
369    assertTrue((limit - (limit / 2)) == avgLimiter.getAvailable());
370    assertTrue((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    assertFalse(avgLimiter.canExecute(limit));
376    assertFalse(fixLimiter.canExecute(limit));
377
378    // after 500 millseconds, average interval limiter should be able to execute the limit
379    testEdge.incValue(500);
380    assertTrue(avgLimiter.canExecute(limit));
381    assertFalse(fixLimiter.canExecute(limit));
382
383    // Make sure that available is correct
384    assertTrue(limit == avgLimiter.getAvailable());
385    assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
386
387    // after 500 millseconds, both should be able to execute
388    testEdge.incValue(500);
389    assertTrue(avgLimiter.canExecute(limit));
390    assertTrue(fixLimiter.canExecute(limit));
391
392    // Make sure that available is Long.MAX_VALUE
393    assertTrue(limit == avgLimiter.getAvailable());
394    assertTrue(limit == fixLimiter.getAvailable());
395
396    EnvironmentEdgeManager.reset();
397  }
398
399  /*
400   * This test case is tricky. Basically, it simulates the following events:
401   *           Thread-1                             Thread-2
402   * t0:  canExecute(100) and consume(100)
403   * t1:                                         canExecute(100), avail may be increased by 80
404   * t2:  consume(-80) as actual size is 20
405   * It will check if consume(-80) can handle overflow correctly.
406   */
407  @Test
408  public void testLimiterCompensationOverflow() throws InterruptedException {
409
410    long limit = Long.MAX_VALUE - 1;
411    long guessNumber = 100;
412
413    // For unconfigured limiters, it is supposed to use as much as possible
414    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
415    avgLimiter.set(limit, TimeUnit.SECONDS);
416
417    assertEquals(limit, avgLimiter.getAvailable());
418
419    // The initial guess is that 100 bytes.
420    assertTrue(avgLimiter.canExecute(guessNumber));
421    avgLimiter.consume(guessNumber);
422
423    // Make sure that available is whatever left
424    assertTrue((limit - guessNumber) == avgLimiter.getAvailable());
425
426    // Manually set avil to simulate that another thread call canExecute().
427    // It is simulated by consume().
428    avgLimiter.consume(-80);
429    assertTrue((limit - guessNumber + 80) == avgLimiter.getAvailable());
430
431    // Now thread1 compensates 80
432    avgLimiter.consume(-80);
433    assertTrue(limit == avgLimiter.getAvailable());
434  }
435}