View Javadoc
1   /*
2    * Copyright 2021 TiKV Project Authors.
3    *
4    * Licensed under the Apache License, Version 2.0 (the "License");
5    * you may not use this file except in compliance with the License.
6    * You may obtain a copy of the License at
7    *
8    * http://www.apache.org/licenses/LICENSE-2.0
9    *
10   * Unless required by applicable law or agreed to in writing, software
11   * distributed under the License is distributed on an "AS IS" BASIS,
12   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13   * See the License for the specific language governing permissions and
14   * limitations under the License.
15   *
16   */
17  package org.tikv.common.util;
18  
19  import java.util.concurrent.ThreadLocalRandom;
20  
21  public class BackOffFunction {
22    private final int base;
23    private final int cap;
24    private final BackOffer.BackOffStrategy strategy;
25    private long lastSleep;
26    private int attempts;
27  
28    private BackOffFunction(int base, int cap, BackOffer.BackOffStrategy strategy) {
29      this.base = base;
30      this.cap = cap;
31      this.strategy = strategy;
32      lastSleep = base;
33    }
34  
35    public static BackOffFunction create(int base, int cap, BackOffer.BackOffStrategy strategy) {
36      return new BackOffFunction(base, cap, strategy);
37    }
38  
39    /**
40     * Do back off in exponential with optional jitters according to different back off strategies.
41     * See http://www.awsarchitectureblog.com/2015/03/backoff.html
42     */
43    long getSleepMs(long maxSleepMs) {
44      long sleep = 0;
45      long v = expo(base, cap, attempts);
46      switch (strategy) {
47        case NoJitter:
48          sleep = v;
49          break;
50        case FullJitter:
51          sleep = ThreadLocalRandom.current().nextLong(v);
52          break;
53        case EqualJitter:
54          sleep = v / 2 + ThreadLocalRandom.current().nextLong(v / 2);
55          break;
56        case DecorrJitter:
57          sleep = Math.min(cap, base + ThreadLocalRandom.current().nextLong(lastSleep * 3 - base));
58          break;
59      }
60  
61      if (maxSleepMs > 0 && sleep > maxSleepMs) {
62        sleep = maxSleepMs;
63      }
64  
65      attempts++;
66      lastSleep = sleep;
67      return lastSleep;
68    }
69  
70    private int expo(int base, int cap, int n) {
71      return (int) Math.min(cap, base * Math.pow(2.0d, n));
72    }
73  
74    public enum BackOffFuncType {
75      BoTiKVRPC,
76      BoTxnLock,
77      BoTxnLockFast,
78      BoPDRPC,
79      BoRegionMiss,
80      BoUpdateLeader,
81      BoServerBusy,
82      BoTxnNotFound,
83      BoCheckTimeout,
84      BoCheckHealth,
85      BoTsoBatchUsedUp
86    }
87  }