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    // We consumed twice the quota. Need to wait 1s to get back to 0, then another 100ms for the 1
113    assertEquals(1100, limiter.waitInterval(1));
114    // We consumed twice the quota. Need to wait 1s to get back to 0, then another 1s to get to 10
115    assertEquals(2000, limiter.waitInterval(10));
116
117    // Verify that after 1sec we need to wait for another 0.1sec to get a resource available
118    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
119    assertFalse(limiter.canExecute(1));
120    limiter.setNextRefillTime(limiter.getNextRefillTime() - 100);
121    // We've waited the full 1.1sec, should now have 1 available
122    assertTrue(limiter.canExecute(1));
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 = EnvironmentEdgeManager.currentTime();
134
135      @Override
136      public long currentTime() {
137        return ts;
138      }
139    };
140    EnvironmentEdgeManager.injectEdge(edge);
141    assertTrue(limiter.canExecute());
142    // 10 resources are available, but we need to consume 20 resources
143    limiter.consume(20);
144    // We over-consumed by 10. Since this is a fixed interval refill, where
145    // each interval we refill the full limit amount, we need to wait 2 intervals -- first
146    // interval gets us from -10 to 0, second gets us from 0 to 10, though we just want the 1.
147    assertEquals(2000, limiter.waitInterval(1));
148    EnvironmentEdgeManager.reset();
149
150    // Verify that after 1sec also no resource should be available
151    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
152    assertFalse(limiter.canExecute());
153    // Verify that after total 2sec the 10 resource is available
154    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
155    assertTrue(limiter.canExecute());
156    assertEquals(0, limiter.waitInterval());
157  }
158
159  @Test
160  public void testFixedIntervalResourceAvailability() throws Exception {
161    RateLimiter limiter = new FixedIntervalRateLimiter();
162    limiter.set(10, TimeUnit.SECONDS);
163
164    assertTrue(limiter.canExecute(10));
165    limiter.consume(3);
166    assertEquals(7, limiter.getAvailable());
167    assertFalse(limiter.canExecute(10));
168    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
169    assertTrue(limiter.canExecute(10));
170    assertEquals(10, limiter.getAvailable());
171  }
172
173  @Test
174  public void testLimiterBySmallerRate() throws InterruptedException {
175    // set limiter is 10 resources per seconds
176    RateLimiter limiter = new FixedIntervalRateLimiter();
177    limiter.set(10, TimeUnit.SECONDS);
178
179    int count = 0; // control the test count
180    while ((count++) < 10) {
181      // test will get 3 resources per 0.5 sec. so it will get 6 resources per sec.
182      limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
183      for (int i = 0; i < 3; i++) {
184        // 6 resources/sec < limit, so limiter.canExecute(nowTs, lastTs) should be true
185        assertEquals(true, limiter.canExecute());
186        limiter.consume();
187      }
188    }
189  }
190
191  @Test
192  public void testCanExecuteOfAverageIntervalRateLimiter() throws InterruptedException {
193    RateLimiter limiter = new AverageIntervalRateLimiter();
194    // when set limit is 100 per sec, this AverageIntervalRateLimiter will support at max 200 per
195    // 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(200, testCanExecuteByRate(limiter, 200));
209
210    // refill the avail to limit
211    limiter.set(100, TimeUnit.SECONDS);
212    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
213    assertEquals(200, testCanExecuteByRate(limiter, 500));
214  }
215
216  @Test
217  public void testCanExecuteOfFixedIntervalRateLimiter() throws InterruptedException {
218    RateLimiter limiter = new FixedIntervalRateLimiter();
219    // when set limit is 100 per sec, this FixedIntervalRateLimiter will support at max 100 per sec
220    limiter.set(100, TimeUnit.SECONDS);
221    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
222    assertEquals(50, testCanExecuteByRate(limiter, 50));
223
224    // refill the avail to limit
225    limiter.set(100, TimeUnit.SECONDS);
226    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
227    assertEquals(100, testCanExecuteByRate(limiter, 100));
228
229    // refill the avail to limit
230    limiter.set(100, TimeUnit.SECONDS);
231    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
232    assertEquals(100, testCanExecuteByRate(limiter, 200));
233  }
234
235  public int testCanExecuteByRate(RateLimiter limiter, int rate) {
236    int request = 0;
237    int count = 0;
238    while ((request++) < rate) {
239      limiter.setNextRefillTime(limiter.getNextRefillTime() - limiter.getTimeUnitInMillis() / rate);
240      if (limiter.canExecute()) {
241        count++;
242        limiter.consume();
243      }
244    }
245    return count;
246  }
247
248  @Test
249  public void testRefillOfAverageIntervalRateLimiter() throws InterruptedException {
250    RateLimiter limiter = new AverageIntervalRateLimiter();
251    limiter.set(60, TimeUnit.SECONDS);
252    assertEquals(60, limiter.getAvailable());
253    // first refill, will return the number same with limit
254    assertEquals(60, limiter.refill(limiter.getLimit()));
255
256    limiter.consume(30);
257
258    // after 0.2 sec, refill should return 12
259    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
260    assertEquals(12, limiter.refill(limiter.getLimit()));
261
262    // after 0.5 sec, refill should return 30
263    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
264    assertEquals(30, limiter.refill(limiter.getLimit()));
265
266    // after 1 sec, refill should return 60
267    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
268    assertEquals(60, limiter.refill(limiter.getLimit()));
269
270    // after more than 1 sec, refill should return at max 60
271    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
272    assertEquals(60, limiter.refill(limiter.getLimit()));
273    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
274    assertEquals(60, limiter.refill(limiter.getLimit()));
275  }
276
277  @Test
278  public void testRefillOfFixedIntervalRateLimiter() throws InterruptedException {
279    RateLimiter limiter = new FixedIntervalRateLimiter();
280    limiter.set(60, TimeUnit.SECONDS);
281    assertEquals(60, limiter.getAvailable());
282    // first refill, will return the number same with limit
283    assertEquals(60, limiter.refill(limiter.getLimit()));
284
285    limiter.consume(30);
286
287    // after 0.2 sec, refill should return 0
288    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
289    assertEquals(0, limiter.refill(limiter.getLimit()));
290
291    // after 0.5 sec, refill should return 0
292    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
293    assertEquals(0, limiter.refill(limiter.getLimit()));
294
295    // after 1 sec, refill should return 60
296    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
297    assertEquals(60, limiter.refill(limiter.getLimit()));
298
299    // after more than 1 sec, refill should return at max 60
300    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
301    assertEquals(60, limiter.refill(limiter.getLimit()));
302    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
303    assertEquals(60, limiter.refill(limiter.getLimit()));
304  }
305
306  @Test
307  public void testUnconfiguredLimiters() throws InterruptedException {
308
309    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
310    EnvironmentEdgeManager.injectEdge(testEdge);
311    long limit = Long.MAX_VALUE;
312
313    // For unconfigured limiters, it is supposed to use as much as possible
314    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
315    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
316
317    assertEquals(limit, avgLimiter.getAvailable());
318    assertEquals(limit, fixLimiter.getAvailable());
319
320    assertTrue(avgLimiter.canExecute(limit));
321    avgLimiter.consume(limit);
322
323    assertTrue(fixLimiter.canExecute(limit));
324    fixLimiter.consume(limit);
325
326    // Make sure that available is Long.MAX_VALUE
327    assertTrue(limit == avgLimiter.getAvailable());
328    assertTrue(limit == fixLimiter.getAvailable());
329
330    // after 100 millseconds, it should be able to execute limit as well
331    testEdge.incValue(100);
332
333    assertTrue(avgLimiter.canExecute(limit));
334    avgLimiter.consume(limit);
335
336    assertTrue(fixLimiter.canExecute(limit));
337    fixLimiter.consume(limit);
338
339    // Make sure that available is Long.MAX_VALUE
340    assertTrue(limit == avgLimiter.getAvailable());
341    assertTrue(limit == fixLimiter.getAvailable());
342
343    EnvironmentEdgeManager.reset();
344  }
345
346  @Test
347  public void testExtremeLimiters() throws InterruptedException {
348
349    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
350    EnvironmentEdgeManager.injectEdge(testEdge);
351    long limit = Long.MAX_VALUE - 1;
352
353    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
354    avgLimiter.set(limit, TimeUnit.SECONDS);
355    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
356    fixLimiter.set(limit, TimeUnit.SECONDS);
357
358    assertEquals(limit, avgLimiter.getAvailable());
359    assertEquals(limit, fixLimiter.getAvailable());
360
361    assertTrue(avgLimiter.canExecute(limit / 2));
362    avgLimiter.consume(limit / 2);
363
364    assertTrue(fixLimiter.canExecute(limit / 2));
365    fixLimiter.consume(limit / 2);
366
367    // Make sure that available is whatever left
368    assertTrue((limit - (limit / 2)) == avgLimiter.getAvailable());
369    assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
370
371    // after 100 millseconds, both should not be able to execute the limit
372    testEdge.incValue(100);
373
374    assertFalse(avgLimiter.canExecute(limit));
375    assertFalse(fixLimiter.canExecute(limit));
376
377    // after 500 millseconds, average interval limiter should be able to execute the limit
378    testEdge.incValue(500);
379    assertTrue(avgLimiter.canExecute(limit));
380    assertFalse(fixLimiter.canExecute(limit));
381
382    // Make sure that available is correct
383    assertTrue(limit == avgLimiter.getAvailable());
384    assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
385
386    // after 500 millseconds, both should be able to execute
387    testEdge.incValue(500);
388    assertTrue(avgLimiter.canExecute(limit));
389    assertTrue(fixLimiter.canExecute(limit));
390
391    // Make sure that available is Long.MAX_VALUE
392    assertTrue(limit == avgLimiter.getAvailable());
393    assertTrue(limit == fixLimiter.getAvailable());
394
395    EnvironmentEdgeManager.reset();
396  }
397
398  /*
399   * This test case is tricky. Basically, it simulates the following events: Thread-1 Thread-2 t0:
400   * canExecute(100) and consume(100) t1: canExecute(100), avail may be increased by 80 t2:
401   * consume(-80) as actual size is 20 It will check if consume(-80) can handle overflow correctly.
402   */
403  @Test
404  public void testLimiterCompensationOverflow() throws InterruptedException {
405
406    long limit = Long.MAX_VALUE - 1;
407    long guessNumber = 100;
408
409    // For unconfigured limiters, it is supposed to use as much as possible
410    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
411    avgLimiter.set(limit, TimeUnit.SECONDS);
412
413    assertEquals(limit, avgLimiter.getAvailable());
414
415    // The initial guess is that 100 bytes.
416    assertTrue(avgLimiter.canExecute(guessNumber));
417    avgLimiter.consume(guessNumber);
418
419    // Make sure that available is whatever left
420    assertTrue((limit - guessNumber) == avgLimiter.getAvailable());
421
422    // Manually set avil to simulate that another thread call canExecute().
423    // It is simulated by consume().
424    avgLimiter.consume(-80);
425    assertTrue((limit - guessNumber + 80) == avgLimiter.getAvailable());
426
427    // Now thread1 compensates 80
428    avgLimiter.consume(-80);
429    assertTrue(limit == avgLimiter.getAvailable());
430  }
431}