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 = EnvironmentEdgeManager.currentTime();
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
197    // sec
198    limiter.set(100, TimeUnit.SECONDS);
199    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
200    assertEquals(50, testCanExecuteByRate(limiter, 50));
201
202    // refill the avail to limit
203    limiter.set(100, TimeUnit.SECONDS);
204    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
205    assertEquals(100, testCanExecuteByRate(limiter, 100));
206
207    // refill the avail to limit
208    limiter.set(100, TimeUnit.SECONDS);
209    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
210    assertEquals(200, testCanExecuteByRate(limiter, 200));
211
212    // refill the avail to limit
213    limiter.set(100, TimeUnit.SECONDS);
214    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
215    assertEquals(200, testCanExecuteByRate(limiter, 500));
216  }
217
218  @Test
219  public void testCanExecuteOfFixedIntervalRateLimiter() throws InterruptedException {
220    RateLimiter limiter = new FixedIntervalRateLimiter();
221    // when set limit is 100 per sec, this FixedIntervalRateLimiter will support at max 100 per sec
222    limiter.set(100, TimeUnit.SECONDS);
223    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
224    assertEquals(50, testCanExecuteByRate(limiter, 50));
225
226    // refill the avail to limit
227    limiter.set(100, TimeUnit.SECONDS);
228    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
229    assertEquals(100, testCanExecuteByRate(limiter, 100));
230
231    // refill the avail to limit
232    limiter.set(100, TimeUnit.SECONDS);
233    limiter.setNextRefillTime(EnvironmentEdgeManager.currentTime());
234    assertEquals(100, testCanExecuteByRate(limiter, 200));
235  }
236
237  public int testCanExecuteByRate(RateLimiter limiter, int rate) {
238    int request = 0;
239    int count = 0;
240    while ((request++) < rate) {
241      limiter.setNextRefillTime(limiter.getNextRefillTime() - limiter.getTimeUnitInMillis() / rate);
242      if (limiter.canExecute()) {
243        count++;
244        limiter.consume();
245      }
246    }
247    return count;
248  }
249
250  @Test
251  public void testRefillOfAverageIntervalRateLimiter() throws InterruptedException {
252    RateLimiter limiter = new AverageIntervalRateLimiter();
253    limiter.set(60, TimeUnit.SECONDS);
254    assertEquals(60, limiter.getAvailable());
255    // first refill, will return the number same with limit
256    assertEquals(60, limiter.refill(limiter.getLimit()));
257
258    limiter.consume(30);
259
260    // after 0.2 sec, refill should return 12
261    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
262    assertEquals(12, limiter.refill(limiter.getLimit()));
263
264    // after 0.5 sec, refill should return 30
265    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
266    assertEquals(30, limiter.refill(limiter.getLimit()));
267
268    // after 1 sec, refill should return 60
269    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
270    assertEquals(60, limiter.refill(limiter.getLimit()));
271
272    // after more than 1 sec, refill should return at max 60
273    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
274    assertEquals(60, limiter.refill(limiter.getLimit()));
275    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
276    assertEquals(60, limiter.refill(limiter.getLimit()));
277  }
278
279  @Test
280  public void testRefillOfFixedIntervalRateLimiter() throws InterruptedException {
281    RateLimiter limiter = new FixedIntervalRateLimiter();
282    limiter.set(60, TimeUnit.SECONDS);
283    assertEquals(60, limiter.getAvailable());
284    // first refill, will return the number same with limit
285    assertEquals(60, limiter.refill(limiter.getLimit()));
286
287    limiter.consume(30);
288
289    // after 0.2 sec, refill should return 0
290    limiter.setNextRefillTime(limiter.getNextRefillTime() - 200);
291    assertEquals(0, limiter.refill(limiter.getLimit()));
292
293    // after 0.5 sec, refill should return 0
294    limiter.setNextRefillTime(limiter.getNextRefillTime() - 500);
295    assertEquals(0, limiter.refill(limiter.getLimit()));
296
297    // after 1 sec, refill should return 60
298    limiter.setNextRefillTime(limiter.getNextRefillTime() - 1000);
299    assertEquals(60, limiter.refill(limiter.getLimit()));
300
301    // after more than 1 sec, refill should return at max 60
302    limiter.setNextRefillTime(limiter.getNextRefillTime() - 3000);
303    assertEquals(60, limiter.refill(limiter.getLimit()));
304    limiter.setNextRefillTime(limiter.getNextRefillTime() - 5000);
305    assertEquals(60, limiter.refill(limiter.getLimit()));
306  }
307
308  @Test
309  public void testUnconfiguredLimiters() throws InterruptedException {
310
311    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
312    EnvironmentEdgeManager.injectEdge(testEdge);
313    long limit = Long.MAX_VALUE;
314
315    // For unconfigured limiters, it is supposed to use as much as possible
316    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
317    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
318
319    assertEquals(limit, avgLimiter.getAvailable());
320    assertEquals(limit, fixLimiter.getAvailable());
321
322    assertTrue(avgLimiter.canExecute(limit));
323    avgLimiter.consume(limit);
324
325    assertTrue(fixLimiter.canExecute(limit));
326    fixLimiter.consume(limit);
327
328    // Make sure that available is Long.MAX_VALUE
329    assertTrue(limit == avgLimiter.getAvailable());
330    assertTrue(limit == fixLimiter.getAvailable());
331
332    // after 100 millseconds, it should be able to execute limit as well
333    testEdge.incValue(100);
334
335    assertTrue(avgLimiter.canExecute(limit));
336    avgLimiter.consume(limit);
337
338    assertTrue(fixLimiter.canExecute(limit));
339    fixLimiter.consume(limit);
340
341    // Make sure that available is Long.MAX_VALUE
342    assertTrue(limit == avgLimiter.getAvailable());
343    assertTrue(limit == fixLimiter.getAvailable());
344
345    EnvironmentEdgeManager.reset();
346  }
347
348  @Test
349  public void testExtremeLimiters() throws InterruptedException {
350
351    ManualEnvironmentEdge testEdge = new ManualEnvironmentEdge();
352    EnvironmentEdgeManager.injectEdge(testEdge);
353    long limit = Long.MAX_VALUE - 1;
354
355    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
356    avgLimiter.set(limit, TimeUnit.SECONDS);
357    RateLimiter fixLimiter = new FixedIntervalRateLimiter();
358    fixLimiter.set(limit, TimeUnit.SECONDS);
359
360    assertEquals(limit, avgLimiter.getAvailable());
361    assertEquals(limit, fixLimiter.getAvailable());
362
363    assertTrue(avgLimiter.canExecute(limit / 2));
364    avgLimiter.consume(limit / 2);
365
366    assertTrue(fixLimiter.canExecute(limit / 2));
367    fixLimiter.consume(limit / 2);
368
369    // Make sure that available is whatever left
370    assertTrue((limit - (limit / 2)) == avgLimiter.getAvailable());
371    assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
372
373    // after 100 millseconds, both should not be able to execute the limit
374    testEdge.incValue(100);
375
376    assertFalse(avgLimiter.canExecute(limit));
377    assertFalse(fixLimiter.canExecute(limit));
378
379    // after 500 millseconds, average interval limiter should be able to execute the limit
380    testEdge.incValue(500);
381    assertTrue(avgLimiter.canExecute(limit));
382    assertFalse(fixLimiter.canExecute(limit));
383
384    // Make sure that available is correct
385    assertTrue(limit == avgLimiter.getAvailable());
386    assertTrue((limit - (limit / 2)) == fixLimiter.getAvailable());
387
388    // after 500 millseconds, both should be able to execute
389    testEdge.incValue(500);
390    assertTrue(avgLimiter.canExecute(limit));
391    assertTrue(fixLimiter.canExecute(limit));
392
393    // Make sure that available is Long.MAX_VALUE
394    assertTrue(limit == avgLimiter.getAvailable());
395    assertTrue(limit == fixLimiter.getAvailable());
396
397    EnvironmentEdgeManager.reset();
398  }
399
400  /*
401   * This test case is tricky. Basically, it simulates the following events: Thread-1 Thread-2 t0:
402   * canExecute(100) and consume(100) t1: canExecute(100), avail may be increased by 80 t2:
403   * consume(-80) as actual size is 20 It will check if consume(-80) can handle overflow correctly.
404   */
405  @Test
406  public void testLimiterCompensationOverflow() throws InterruptedException {
407
408    long limit = Long.MAX_VALUE - 1;
409    long guessNumber = 100;
410
411    // For unconfigured limiters, it is supposed to use as much as possible
412    RateLimiter avgLimiter = new AverageIntervalRateLimiter();
413    avgLimiter.set(limit, TimeUnit.SECONDS);
414
415    assertEquals(limit, avgLimiter.getAvailable());
416
417    // The initial guess is that 100 bytes.
418    assertTrue(avgLimiter.canExecute(guessNumber));
419    avgLimiter.consume(guessNumber);
420
421    // Make sure that available is whatever left
422    assertTrue((limit - guessNumber) == avgLimiter.getAvailable());
423
424    // Manually set avil to simulate that another thread call canExecute().
425    // It is simulated by consume().
426    avgLimiter.consume(-80);
427    assertTrue((limit - guessNumber + 80) == avgLimiter.getAvailable());
428
429    // Now thread1 compensates 80
430    avgLimiter.consume(-80);
431    assertTrue(limit == avgLimiter.getAvailable());
432  }
433}