Implementation of exponential backoff algorithm

Question

You can read about the algorithm here.

An exponential backoff algorithm retries requests exponentially, increasing the waiting time between retries up to a maximum backoff time. An example is:

1. Make a request to Cloud Storage.
2. If the request fails, wait 1 + random_number_milliseconds seconds and retry the request.
3. If the request fails, wait 2 + random_number_milliseconds seconds and retry the request.
4. If the request fails, wait 4 + random_number_milliseconds seconds and retry the request.
5. And so on, up to a maximum_backoff time.
6. Continue waiting and retrying up to a maximum amount of time (deadline), but do not increase the maximum_backoff wait period between retries.

where:

1. The wait time is min((2n +random_number_milliseconds), maximum_backoff), with n incremented by 1 for each iteration (request).
2. random_number_milliseconds is a random number of milliseconds less than or equal to 1000. This helps to avoid cases where many clients become synchronized and all retry at once, sending requests in synchronized waves. The value of random_number_milliseconds is recalculated after each retry request.
3. maximum_backoff is typically 32 or 64 seconds. The appropriate value depends on the use case. You can continue retrying once you reach the maximum_backoff time, but we recommend your request fail out after an amount of time to prevent your application from becoming unresponsive. For example, if a client uses a maximum_backoff time of 64 seconds, then after reaching this value, the client can retry every 64 seconds. The client then stops retrying after a deadline of 600 seconds.

EBARetrier.js

const utils = require("./utils");

async function EBARetrier(callback, argsList) {
  const context = getEBAContext(callback, argsList);

  while (isProcessingEntities(context)) {
    try {
      await processEntity(context);
    } catch (error) {
      handleFailedEntity(context, error);
    }
  }
}

function getEBAContext(callback, argsList) {
  return {
    maximumBackoff: 64,
    deadline: 600,
    startTime: Date.now(),
    totalEntities: argsList.length,
    failedEntities: [],
    retryAttempt: 0,
    processedEntities: 0,
    lastProcessFailed: false,
    args: null,
    callback,
    argsList,
  };
}

function isProcessingEntities(context) {
  return (
    utils.getTimeElapsed(context.startTime) < context.deadline &&
    context.processedEntities < context.totalEntities
  );
}

async function processEntity(context) {
  const args = context.failedEntities.shift() || context.argsList.shift();
  context.args = args;

  if (context.lastProcessFailed) {
    const ms = getWaitTime(context);
    await utils.wait(ms);
  }

  await context.callback(...args);
  context.processedEntities++;
  context.lastProcessFailed = false;
  context.retryAttempt = 0;
}

function handleFailedEntity(context, error) {
  console.error(error);
  context.failedEntities.push(context.args);
  context.lastProcessFailed = true;
  context.retryAttempt++;
}

function getWaitTime(context) {
  const randomMS = utils.getRandomInt(1001);
  const attempt = context.retryAttempt - 1;
  const ms = Math.pow(2, attempt) * 1000 + randomMS;
  const maxBackoffMs = context.maximumBackoff * 1000;

  if (ms > maxBackoffMs) {
    return maxBackoffMs;
  }

  return ms;
}

module.exports = {
  EBARetrier,
};

utils.js

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}

function getTimeElapsed(startTime) {
  return (Date.now() - startTime) / 1000;
}

function wait(ms) {
  return new Promise((resolve) => {
    setTimeout(resolve, ms);
  });
}

module.exports = {
  getRandomInt,
  getTimeElapsed,
  wait,
};

Any help will be appreciated! Thanks!

Answer 1

Code should be correct, maintainable, robust, reasonably efficient, and, most importantly, readable.

---

Your code appears to be mathematically unsound.

---

You write:

deadline: 600,
startTime: Date.now(),

.

function getTimeElapsed(startTime) {
  return (Date.now() - startTime) / 1000;
}

.

getTimeElapsed(context.startTime) < context.deadline 

The Javascript Date.now() and performance.now() methods are documented in MDN: JavaScript and elsewhere.

Also unlike Date.now(), the values returned by performance.now() always increase at a constant rate, independent of the system clock (which might be adjusted manually or skewed by software like NTP).

and

To offer protection against timing attacks and fingerprinting, the precision of Date.now() might get rounded depending on browser settings. In Firefox, the privacy.reduceTimerPrecision preference is enabled by default and defaults to 20µs in Firefox 59; in 60 it will be 2ms.

Your getTimeElapsed function may return variable rate positive, negative, or zero values. Use monotonic clock values that increase at a constant rate. Write:

deadline: 600,
startTime: performance.now(),

.

function getTimeElapsed(startTime) {
  return (performance.now() - startTime) / 1000;
}

.

getTimeElapsed(context.startTime) < context.deadline 

---

Your getWaitTime function is based on an exponential backoff algorithm that appears to be mathematically unsound.

function getWaitTime(context) {
  const randomMS = utils.getRandomInt(1001);
  const attempt = context.retryAttempt - 1;
  const ms = Math.pow(2, attempt) * 1000 + randomMS;
  const maxBackoffMs = context.maximumBackoff * 1000;

  if (ms > maxBackoffMs) {
    return maxBackoffMs;
  }

  return ms;
}

The algorithm definition states:

random_number_milliseconds is a random number of milliseconds less than or equal to 1000. This helps to avoid cases where many clients become synchronized and all retry at once, sending requests in synchronized waves. The value of random_number_milliseconds is recalculated after each retry request.

If we implement the algorithm from the definition, we can see that it appears to be mathematically unsound. It does not avoid synchronized waves once it reaches the backoff value.

retry.js:

'use strict';

// Truncated exponential backoff wait time in milliseconds.
// https://cloud.google.com/storage/docs/retry-strategy#exponential-backoff
// https://en.wikipedia.org/wiki/Exponential_backoff
function tebWait(backoff, deadline) {
    let n = 0;
    let sum = 0;

    return function waitTime() {
        let wait = Math.pow(2, n++);
        wait += Math.random();
        wait = Math.min(wait, backoff);
        sum+=wait;
        if (sum > deadline) {
            return null;
        }
        return Math.ceil(wait * 1000);
    }
}

let backoff = 64;
let deadline = 600;
let retryWait = tebWait(backoff, deadline);

for (let wait = 0; (wait = retryWait()) != null; ) {
    console.log(wait);
}

.

$ node retry.js
1361
2848
4065
8746
16236
32305
64000
64000
64000
64000
64000
64000
64000
64000

Here's a revised version of the algorithm that does avoid synchronized waves once it reaches the backoff value.

retry.js:

'use strict';

// Truncated exponential backoff wait time in milliseconds.
// https://cloud.google.com/storage/docs/retry-strategy#exponential-backoff
// https://en.wikipedia.org/wiki/Exponential_backoff
function tebWait(backoff, deadline) {
    let n = 0;
    let sum = 0;

    return function waitTime() {
        let wait = Math.pow(2, n++);
        wait = Math.min(wait, backoff);
        sum+=wait;
        if (sum > deadline) {
            return null;
        }
        wait += Math.random();
        return Math.ceil(wait * 1000);
    }
}

let backoff = 64;
let deadline = 600;
let retryWait = tebWait(backoff, deadline);

for (let wait = 0; (wait = retryWait()) != null; ) {
    console.log(wait);
}

.

$ node retry.js
1344
2548
4239
8110
16564
32013
64615
64397
64501
64318
64602
64680
64477
64123