Exponential backoff

I'm refactoring my cUseful library for some upcoming articles. This means updating some long standing functions that some of you may be using. All the existing ones will continue to work as before, but the new versions of them will have some additional features and will be found in various namespaces within the cUseful library. 

Here's the key, and it's also on github

Mcbr-v4SsYKJP7JMohttAZyz3TLx7pV4j



The first new namespace is cUseful.Utils, and the first enhanced function is exponential backoff. You can see how the previous version worked with Custom checking for exponential backoff.

The new version has a couple of new features.

What is exponential backoff

This is recommended technique to use for calling services that are rate limited. They will be retried a few times if they are detected as having failed with errors that can be recovered from using a special wait algorithm. This is a much better technique than using Utilities.sleep between each call since it only waits if it needs to and therefore doesn't waste any execution time.

How to use

 var response = cUseful.Utils.expBackoff ( function (options, attempts) {  return yourResult; }, {options} );

Your callback function will be called with the options in force and the attempt number. The options and there defaults are as follows

{
    sleepFor:750,            // base starting sleep period between attempts if needed
    maxAttempts:5,      // how many times to try before giving up
    logAttempts:true,   // whether to alert in the log file if backoff had to happen
    checker:function(), // a built in function that checks if an error is a retyable app script error - can be overridden with your own
    lookahead:null         // if specifed, a function that can force a retry even though no error has been thrown
}


Examples

In its simplest and normal form, only one argument is needed - the function to execute. 

The Properties service can fail if you call it too rapidly in succession. This will take of that problem, and retry if necessary
var value = cUseful.Utils.expBackoff (function () {
  return PropertiesService.getScriptProperties().getProperty ('key');
});

The default checker function looks for Apps Script errors. It can be overriden and used to retry errors from external APIS that return different errors. In this example, the Github API indicates a recoverable rate limit with its own error message. If an operation that generated an error should be retried, then return true. 
 var response = cUseful.Utils.expBackoff (
      
      function () {
        return UrlFetchApp.fetch('https://api.github.com/users/brucemcpherson/gists');
      },{
        
        checker:function (err) {
          return err.toString()
            .indexOf('API rate limit exceeded') !== -1;
        }
  });

The lookahead can be used to force a retry, even if the function doesn't return an error. For example, the NASA API simply sends back a message in place of the usual data. If a retry should be attempted for an operation that didn't actually produce an error, then return true.
    var response = cUseful.Utils.expBackoff (
      function () {
        return UrlFetchApp.fetch(url , {
          muteHttpExceptions:true,                     
        });
      }, {
        lookahead:function (response,attempt) {
          // the api doesnt fail on rate limiting in any case
          // so we need to parse the content (if parseable)
          try {
            var r = JSON.parse(response.getContentText());
            return r && r.error && r.error.indexOf('code: 429') !== -1;
          }
          catch(err) {
            return false;
          }
        }
      });

The code

Here's the function code.
/**
* libary for use with Going Gas Videos
* Utils contains useful functions 
* @namespace
*/
var Utils = (function (ns) {
  /**
  * recursive rateLimitExpBackoff()
  * @param {function} callBack some function to call that might return rate limit exception
  * @param {object} options properties as below
  * @param {number} [attempts=1] optional the attempt number of this instance - usually only used recursively and not user supplied
  * @param {number} [options.sleepFor=750] optional amount of time to sleep for on the first failure in missliseconds
  * @param {number} [options.maxAttempts=5] optional maximum number of amounts to try
  * @param {boolean} [options.logAttempts=true] log re-attempts to Logger
  * @param {function} [options.checker] function to check whether error is retryable
  * @param {function} [options.lookahead] function to check response and force retry (passes response,attemprs)
  * @return {*} results of the callback 
  */
  
  ns.expBackoff = function ( callBack,options,attempts) {
    
    //sleepFor = Math.abs(options.sleepFor ||
    
    options = options || {};
    optionsDefault = { 
      sleepFor:  750,
      maxAttempts:5,                  
      checker:errorQualifies,
      logAttempts:true
    }
    
    // mixin
    Object.keys(optionsDefault).forEach(function(k) {
      if (!options.hasOwnProperty(k)) {
        options[k] = optionsDefault[k];
      }
    });
    
    // for recursion
    attempts = attempts || 1;
    
    // make sure that the checker is really a function
    if (typeof(options.checker) !== "function") {
      throw ns.errorStack("if you specify a checker it must be a function");
    }
    
    // check properly constructed
    if (!callBack || typeof(callBack) !== "function") {
      throw ns.errorStack("you need to specify a function for rateLimitBackoff to execute");
    }
    
    // try to execute it
    try {
      var response = callBack(options, attempts);
      
      // maybe not throw an error but is problem nevertheless
      if (options.lookahead && options.lookahead(response,attempts)) {
        if(options.logAttempts) { 
          Logger.log("backoff lookahead:" + attempts);
        }
        waitAbit();
        return ns.expBackoff ( callBack, options, attempts+1) ;
        
      }
      return response;
    }
    
    // there was an error
    catch(err) {
      
      if(options.logAttempts) { 
        Logger.log("backoff " + attempts + ":" +err);
      }
      
      // failed due to rate limiting?
      if (options.checker(err)) {
        waitABit();
        return ns.expBackoff ( callBack, options, attempts+1) ;
      }
      else {
        // some other error
        throw ns.errorStack(err);
      }
    }
    
    function waitAbit () {

      //give up?
      if (attempts > options.maxAttempts) {
        throw errorStack(err + " (tried backing off " + (attempts-1) + " times");
      }
      else {
        // wait for some amount of time based on how many times we've tried plus a small random bit to avoid races
        Utilities.sleep (
          Math.pow(2,attempts)*options.sleepFor + 
          Math.round(Math.random() * options.sleepFor)
        );
        
      }
      
    }
  }
    
  /**
  * get the stack
  * @param {Error} e the error
  * @return {string} the stack trace
  */
  ns.errorStack = function  (e) {
    try {
      // throw a fake error
      throw new Error();  //x is undefined and will fail under use struct- ths will provoke an error so i can get the call stack
    }
    catch(err) {
      return 'Error:' + e + '\n' + err.stack.split('\n').slice(1).join('\n');
    }
  }
  
  
  // default checker
  function errorQualifies (errorText) {

    return ["Exception: Service invoked too many times",
            "Exception: Rate Limit Exceeded",
            "Exception: Quota Error: User Rate Limit Exceeded",
            "Service error:",
            "Exception: Service error:", 
            "Exception: User rate limit exceeded",
            "Exception: Internal error. Please try again.",
            "Exception: Cannot execute AddColumn because another task",
            "Service invoked too many times in a short time:",
            "Exception: Internal error.",
            "User Rate Limit Exceeded",
            "Exception: Превышен лимит: DriveApp."
           ]
    .some(function(e){
      return  errorText.toString().slice(0,e.length) == e  ;
    }) ;
    
  }
  
  /**
   * convert a data into a suitable format for API
   * @param {Date} dt the date
   * @return {string} converted data
   */
  ns.gaDate = function  (dt) {
    return Utilities.formatDate(
      dt, Session.getScriptTimeZone(), 'yyyy-MM-dd'
    );
  }
  
   /** 
  * execute a regex and return the single match
  * @param {Regexp} rx the regexp
  * @param {string} source the source string
  * @param {string} def the default value
  * @return {string} the match
  */
  ns.getMatchPiece = function (rx, source, def) {
    var f = rx.exec(source);
    
    var result = f && f.length >1 ? f[1] : def;
    
    // special hack for boolean
    if (typeof def === typeof true) {
      result = ns.yesish ( result );
    }
    
    return result;
  };
  
  ns.yesish = function(s) {
    var t = s.toString().toLowerCase();
    return t === "yes" || "y" || "true" || "1";
  };
   
  /** 
  * check if item is undefined
  * @param {*} item the item to check
  * @return {boolean} whether it is undefined
  **/
  ns.isUndefined = function (item) {
    return typeof item === 'undefined';
  };
   
  /** 
  * isObject
  * check if an item is an object
  * @param {object} obj an item to be tested
  * @return {boolean} whether its an object
  **/
  ns.isObject = function (obj) {
    return obj === Object(obj);
  };
    
  /** 
  * checksum
  * create a checksum on some string or object
  * @param {*} o the thing to generate a checksum for
  * @return {number} the checksum
  **/
  ns.checksum = function (o) {
    // just some random start number
    var c = 23;
    if (!ns.isUndefined(o)){
      var s =  (ns.isObject(o) || Array.isArray(o)) ? JSON.stringify(o) : o.toString();
      for (var i = 0; i < s.length; i++) {
        c += (s.charCodeAt(i) * (i + 1));
      }
    }
    
    return c;
  };
  

  return ns;
}) (Utils || {});


For more like this, see Google Apps Scripts snippets. Why not join our forumfollow the blog or follow me on twitter to ensure you get updates when they are available. 

You want to learn Google Apps Script?

Learning Apps Script, (and transitioning from VBA) are covered comprehensively in my my book, Going Gas - from VBA to Apps script, available All formats are available now from O'Reilly,Amazon and all good bookshops. You can also read a preview on O'Reilly

If you prefer Video style learning I also have two courses available. also published by O'Reilly.
Google Apps Script for Developers and Google Apps Script for Beginners.






Comments