cashless2ecash

cashless2ecash: pay with cards for digital cash (experimental)
Log | Files | Refs | README

exponential-backoff.go (3029B)

      1 // This file is part of taler-cashless2ecash.
      2 // Copyright (C) 2024 Joel Häberli
      3 //
      4 // taler-cashless2ecash is free software: you can redistribute it and/or modify it
      5 // under the terms of the GNU Affero General Public License as published
      6 // by the Free Software Foundation, either version 3 of the License,
      7 // or (at your option) any later version.
      8 //
      9 // taler-cashless2ecash is distributed in the hope that it will be useful, but
     10 // WITHOUT ANY WARRANTY; without even the implied warranty of
     11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     12 // Affero General Public License for more details.
     13 //
     14 // You should have received a copy of the GNU Affero General Public License
     15 // along with this program.  If not, see <http://www.gnu.org/licenses/>.
     16 //
     17 // SPDX-License-Identifier: AGPL3.0-or-later
     18 
     19 package internal_utils
     20 
     21 import (
     22 	"crypto/rand"
     23 	"fmt"
     24 	"math"
     25 	"math/big"
     26 	"time"
     27 )
     28 
     29 const EXPONENTIAL_BACKOFF_BASE = 2
     30 
     31 const RANDOMIZATION_THRESHOLD_FACTOR = 0.2 // +/- 20%
     32 
     33 /*
     34 Generic implementation of a limited exponential backoff
     35 algorithm. It includes a randomization to prevent
     36 self-synchronization issues.
     37 
     38 Parameters:
     39 
     40   - lastExecution: time of the last execution
     41   - retryCount   : number of the retries
     42   - limitMs 	 : field shall be the maximal milliseconds to backoff before retry happens
     43 */
     44 func ShouldStartRetry(
     45 	lastExecution time.Time,
     46 	retryCount int,
     47 	limitMs int,
     48 ) bool {
     49 
     50 	backoffMs := exponentialBackoffMs(retryCount)
     51 	randomizedBackoffSeconds := int64(limitMs) / 1000
     52 	if backoffMs < int64(limitMs) {
     53 		randomizedBackoffSeconds = randomizeBackoff(backoffMs)
     54 	} else {
     55 		LogInfo("exponential-backoff", fmt.Sprintf("backoff limit exceeded. setting manual limit: %d", limitMs))
     56 	}
     57 
     58 	now := time.Now().Unix()
     59 	backoffTime := lastExecution.Unix() + randomizedBackoffSeconds
     60 	// LogInfo("exponential-backoff", fmt.Sprintf("lastExec=%d, now=%d, backoffTime=%d, shouldStartRetry=%s", lastExecution.Unix(), now, backoffTime, strconv.FormatBool(now >= backoffTime)))
     61 	return now >= backoffTime
     62 }
     63 
     64 func exponentialBackoffMs(retries int) int64 {
     65 
     66 	return int64(math.Pow(EXPONENTIAL_BACKOFF_BASE, float64(retries)))
     67 }
     68 
     69 func randomizeBackoff(backoff int64) int64 {
     70 
     71 	// it's about randomizing on millisecond base... we mustn't care about rounding
     72 	threshold := int64(math.Floor(float64(backoff)*RANDOMIZATION_THRESHOLD_FACTOR)) + 1 // +1 to guarantee positive threshold
     73 	randomizedThreshold, err := rand.Int(rand.Reader, big.NewInt(backoff+threshold))
     74 	if err != nil {
     75 		LogError("exponential-backoff", err)
     76 	}
     77 	subtract, err := rand.Int(rand.Reader, big.NewInt(100)) // upper boundary is exclusive (value is between 0 and 99)
     78 	if err != nil {
     79 		LogError("exponential-backoff", err)
     80 	}
     81 
     82 	if !randomizedThreshold.IsInt64() {
     83 		LogWarn("exponential-backoff", "the threshold is not int64")
     84 		return backoff
     85 	}
     86 
     87 	if subtract.Int64() < 50 {
     88 		subtracted := backoff - randomizedThreshold.Int64()
     89 		if subtracted < 0 {
     90 			return 0
     91 		}
     92 		return subtracted
     93 	}
     94 	return backoff + randomizedThreshold.Int64()
     95 }