gcra.go

Documentation: github.com/letsencrypt/boulder/ratelimits

     1  package ratelimits
     2  
     3  import (
     4  	"time"
     5  
     6  	"github.com/jmhodges/clock"
     7  )
     8  
     9  // maybeSpend uses the GCRA algorithm to decide whether to allow a request. It
    10  // returns a Decision struct with the result of the decision and the updated
    11  // TAT. The cost must be 0 or greater and <= the burst capacity of the limit.
    12  func maybeSpend(clk clock.Clock, rl limit, tat time.Time, cost int64) *Decision {
    13  	if cost < 0 || cost > rl.Burst {
    14  		// The condition above is the union of the conditions checked in Check
    15  		// and Spend methods of Limiter. If this panic is reached, it means that
    16  		// the caller has introduced a bug.
    17  		panic("invalid cost for maybeSpend")
    18  	}
    19  	nowUnix := clk.Now().UnixNano()
    20  	tatUnix := tat.UnixNano()
    21  
    22  	// If the TAT is in the future, use it as the starting point for the
    23  	// calculation. Otherwise, use the current time. This is to prevent the
    24  	// bucket from being filled with capacity from the past.
    25  	if nowUnix > tatUnix {
    26  		tatUnix = nowUnix
    27  	}
    28  
    29  	// Compute the cost increment.
    30  	costIncrement := rl.emissionInterval * cost
    31  
    32  	// Deduct the cost to find the new TAT and residual capacity.
    33  	newTAT := tatUnix + costIncrement
    34  	difference := nowUnix - (newTAT - rl.burstOffset)
    35  
    36  	if difference < 0 {
    37  		// Too little capacity to satisfy the cost, deny the request.
    38  		residual := (nowUnix - (tatUnix - rl.burstOffset)) / rl.emissionInterval
    39  		return &Decision{
    40  			Allowed:   false,
    41  			Remaining: residual,
    42  			RetryIn:   -time.Duration(difference),
    43  			ResetIn:   time.Duration(tatUnix - nowUnix),
    44  			newTAT:    time.Unix(0, tatUnix).UTC(),
    45  		}
    46  	}
    47  
    48  	// There is enough capacity to satisfy the cost, allow the request.
    49  	var retryIn time.Duration
    50  	residual := difference / rl.emissionInterval
    51  	if difference < costIncrement {
    52  		retryIn = time.Duration(costIncrement - difference)
    53  	}
    54  	return &Decision{
    55  		Allowed:   true,
    56  		Remaining: residual,
    57  		RetryIn:   retryIn,
    58  		ResetIn:   time.Duration(newTAT - nowUnix),
    59  		newTAT:    time.Unix(0, newTAT).UTC(),
    60  	}
    61  }
    62  
    63  // maybeRefund uses the Generic Cell Rate Algorithm (GCRA) to attempt to refund
    64  // the cost of a request which was previously spent. The refund cost must be 0
    65  // or greater. A cost will only be refunded up to the burst capacity of the
    66  // limit. A partial refund is still considered successful.
    67  func maybeRefund(clk clock.Clock, rl limit, tat time.Time, cost int64) *Decision {
    68  	if cost <= 0 || cost > rl.Burst {
    69  		// The condition above is checked in the Refund method of Limiter. If
    70  		// this panic is reached, it means that the caller has introduced a bug.
    71  		panic("invalid cost for maybeRefund")
    72  	}
    73  	nowUnix := clk.Now().UnixNano()
    74  	tatUnix := tat.UnixNano()
    75  
    76  	// The TAT must be in the future to refund capacity.
    77  	if nowUnix > tatUnix {
    78  		// The TAT is in the past, therefore the bucket is full.
    79  		return &Decision{
    80  			Allowed:   false,
    81  			Remaining: rl.Burst,
    82  			RetryIn:   time.Duration(0),
    83  			ResetIn:   time.Duration(0),
    84  			newTAT:    tat,
    85  		}
    86  	}
    87  
    88  	// Compute the refund increment.
    89  	refundIncrement := rl.emissionInterval * cost
    90  
    91  	// Subtract the refund increment from the TAT to find the new TAT.
    92  	newTAT := tatUnix - refundIncrement
    93  
    94  	// Ensure the new TAT is not earlier than now.
    95  	if newTAT < nowUnix {
    96  		newTAT = nowUnix
    97  	}
    98  
    99  	// Calculate the new capacity.
   100  	difference := nowUnix - (newTAT - rl.burstOffset)
   101  	residual := difference / rl.emissionInterval
   102  
   103  	return &Decision{
   104  		Allowed:   (newTAT != tatUnix),
   105  		Remaining: residual,
   106  		RetryIn:   time.Duration(0),
   107  		ResetIn:   time.Duration(newTAT - nowUnix),
   108  		newTAT:    time.Unix(0, newTAT).UTC(),
   109  	}
   110  }
   111
View as plain text