hbase-server/src/test/java/org/apache/hadoop/hbase/quotas/TestRateLimiter.java

   1 /**
   2  * Licensed to the Apache Software Foundation (ASF) under one
   3  * or more contributor license agreements.  See the NOTICE file
   4  * distributed with this work for additional information
   5  * regarding copyright ownership.  The ASF licenses this file
   6  * to you under the Apache License, Version 2.0 (the
   7  * "License"); you may not use this file except in compliance
   8  * with the License.  You may obtain a copy of the License at
   9  *
  10  *     http://www.apache.org/licenses/LICENSE-2.0
  11  *
  12  * Unless required by applicable law or agreed to in writing, software
  13  * distributed under the License is distributed on an "AS IS" BASIS,
  14  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  15  * See the License for the specific language governing permissions and
  16  * limitations under the License.
  17  */
  18 package org.apache.hadoop.hbase.quotas;
  19
  20 import static org.junit.Assert.assertEquals;
  21 import static org.junit.Assert.assertFalse;
  22 import static org.junit.Assert.assertTrue;
  23
  24 import java.util.concurrent.TimeUnit;
  25 import org.apache.hadoop.hbase.HBaseClassTestRule;
  26 import org.apache.hadoop.hbase.testclassification.RegionServerTests;
  27 import org.apache.hadoop.hbase.testclassification.SmallTests;
  28 import org.apache.hadoop.hbase.util.EnvironmentEdge;
  29 import org.apache.hadoop.hbase.util.EnvironmentEdgeManager;
  30 import org.apache.hadoop.hbase.util.ManualEnvironmentEdge;
  31 import org.junit.ClassRule;
  32 import org.junit.Test;
  33 import org.junit.experimental.categories.Category;
  34
  35 /**
  36  * Verify the behaviour of the Rate Limiter.
  37  */
  38 @Category({RegionServerTests.class, SmallTests.class})
  39 public class TestRateLimiter {
  40
  41   @ClassRule
  42   public static final HBaseClassTestRule CLASS_RULE =
  43       HBaseClassTestRule.forClass(TestRateLimiter.class);
  44
  45   @Test
  46   public void testWaitIntervalTimeUnitSeconds() {
  47     testWaitInterval(TimeUnit.SECONDS, 10, 100);
  48   }
  49
  50   @Test
  51   public void testWaitIntervalTimeUnitMinutes() {
  52     testWaitInterval(TimeUnit.MINUTES, 10, 6000);
  53   }
  54
  55   @Test
  56   public void testWaitIntervalTimeUnitHours() {
  57     testWaitInterval(TimeUnit.HOURS, 10, 360000);
  58   }
  59
  60   @Test
  61   public void testWaitIntervalTimeUnitDays() {
  62     testWaitInterval(TimeUnit.DAYS, 10, 8640000);
  63   }
  64
  65   private void testWaitInterval(final TimeUnit timeUnit, final long limit,
  66       final long expectedWaitInterval) {
  67     RateLimiter limiter = new AverageIntervalRateLimiter();
  68     limiter.set(limit, timeUnit);
  69
  70     long nowTs = 0;
  71     // consume all the available resources, one request at the time.
  72     // the wait interval should be 0
  73     for (int i = 0; i < (limit - 1); ++i) {
  74       assertTrue(limiter.canExecute());
  75       limiter.consume();
  76       long waitInterval = limiter.waitInterval();
  77       assertEquals(0, waitInterval);
  78     }
  79
  80     for (int i = 0; i < (limit * 4); ++i) {
  81       // There is one resource available, so we should be able to
  82       // consume it without waiting.
  83       limiter.setNextRefillTime(limiter.getNextRefillTime() - nowTs);
  84       assertTrue(limiter.canExecute());
  85       assertEquals(0, limiter.waitInterval());
  86       limiter.consume();
  87       // No more resources are available, we should wait for at least an interval.
  88       long waitInterval = limiter.waitInterval();
  89       assertEquals(expectedWaitInterval, waitInterval);
  90
  91       // set the nowTs to be the exact time when resources should be available again.
  92       nowTs = waitInterval;
  93
  94       // artificially go into the past to prove that when too early we should fail.
  95       long temp = nowTs + 500;
  96       limiter.setNextRefillTime(limiter.getNextRefillTime() + temp);
  97       assertFalse(limiter.canExecute());
  98       //Roll back the nextRefillTime set to continue further testing
  99       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 }