Issue creating valid test case for promise rate limit function

Question

I'm trying to create a valid test case for the promiseRateLimit function below. The way the promiseRateLimit function works is it uses a queue to store incoming promises and will place a delay between them.

import Promise from 'bluebird'

export default function promiseRateLimit (fn, delay, count) {
  let working = 0
  let queue = []
  function work () {
    if ((queue.length === 0) || (working === count)) return
    working++
    Promise.delay(delay).tap(() => working--).then(work)
    let {self, args, resolve} = queue.shift()
    resolve(fn.apply(self, args))
  }
  return function debounced (...args) {
    return new Promise(resolve => {
      queue.push({self: this, args, resolve})
      if (working < count) work()
    })
  }
}

Here's an example of the function in action.

async function main () {
  const example = (v) => Promise.delay(50)
  const exampleLimited = promiseRateLimit(example, 100, 1)
  const alpha = await exampleLimited('alpha')
  const beta = await exampleLimited('beta')
  const gamma = await exampleLimited('gamma')
  const epsilon = await exampleLimited('epsilon')
  const phi = await exampleLimited('phi')
}

The example promise takes 50ms to run and the promiseRateLimit function will only allow 1 promise every 100ms. So the interval between promises should be greater than 100ms.

Here's a complete test that sometimes returns successful and sometimes fails:

import test from 'ava'
import Debug from 'debug'
import Promise from 'bluebird'
import promiseRateLimit from './index'
import {getIntervalsBetweenDates} from '../utilitiesForDates'
import {arraySum} from '../utilitiesForArrays'
import {filter} from 'lodash'

test('using async await', async (t) => {
  let timeLog = []
  let runCount = 0
  const example = (v) => Promise.delay(50)
    .then(() => timeLog.push(new Date))
    .then(() => runCount++)
    .then(() => v)
  const exampleLimited = promiseRateLimit(example, 100, 1, 'a')
  const alpha = await exampleLimited('alpha')
  const beta = await exampleLimited('beta')
  const gamma = await exampleLimited('gamma')
  const epsilon = await exampleLimited('epsilon')
  const phi = await exampleLimited('phi')
  const intervals = getIntervalsBetweenDates(timeLog)
  const invalidIntervals = filter(intervals, (interval) => interval < 100)
  const totalTime = arraySum(intervals)
  t.is(intervals.length, 4)
  t.deepEqual(invalidIntervals, [])
  t.deepEqual(totalTime >= 400, true)
  t.is(alpha, 'alpha')
  t.is(beta, 'beta')
  t.is(gamma, 'gamma')
  t.is(epsilon, 'epsilon')
  t.is(phi, 'phi')
})

I've created a getIntervalsBetweenDates function that simply diff's two unix timestamps and get the duration between an array of dates.

export function getIntervalsBetweenDates (dates) {
  let intervals = []
  dates.forEach((date, index) => {
    let nextDate = dates[index + 1]
    if (nextDate) intervals.push(nextDate - date)
  })
  return intervals
}

The issue is that the test above sometimes returns an interval that is lower than the delay. For instance if the delay is 100ms sometimes an interval returns 98ms or 96ms. There is no reason this should ever happen.

Is there any way to make the above test pass 100% of the time? I'm trying to ensure that the delay argument works and that there is at least that much time between promises.

Update 2016-12-28 9:20am (EST)

Here's the full test

import test from 'ava'
import Debug from 'debug'
import Promise from 'bluebird'
import promiseRateLimit from './index'
import {getIntervalsBetweenDates} from '../utilitiesForDates'
import {arraySum} from '../utilitiesForArrays'
import {filter} from 'lodash'

test('using async await', async (t) => {
  let timeLog = []
  let runCount = 0
  let bufferInterval = 100
  let promisesLength = 4
  const example = v => {
    timeLog.push(new Date)
    runCount++
    return Promise.delay(50, v)
  }
  const exampleLimited = promiseRateLimit(example, bufferInterval, 1)
  const alpha = await exampleLimited('alpha')
  const beta = await exampleLimited('beta')
  const gamma = await exampleLimited('gamma')
  const epsilon = await exampleLimited('epsilon')
  const phi = await exampleLimited('phi')
  const intervals = getIntervalsBetweenDates(timeLog)
  const invalidIntervals = filter(intervals, (interval) => interval < bufferInterval)
  const totalTime = arraySum(intervals)
  t.is(intervals.length, promisesLength)
  t.deepEqual(invalidIntervals, [])
  t.deepEqual(totalTime >= bufferInterval * promisesLength, true)
  t.is(alpha, 'alpha')
  t.is(beta, 'beta')
  t.is(gamma, 'gamma')
  t.is(epsilon, 'epsilon')
  t.is(phi, 'phi')
})

test('using Promise.all with 2 promises', async (t) => {
  let timeLog = []
  let runCount = 0
  let bufferInterval = 100
  let promisesLength = 1
  const example = v => {
    timeLog.push(new Date)
    runCount++
    return Promise.delay(50, v)
  }
  const exampleLimited = promiseRateLimit(example, bufferInterval, 1)
  const results = await Promise.all([exampleLimited('alpha'), exampleLimited('beta')])
  const intervals = getIntervalsBetweenDates(timeLog)
  const invalidIntervals = filter(intervals, (interval) => interval < bufferInterval)
  const totalTime = arraySum(intervals)
  t.is(intervals.length, promisesLength)
  t.deepEqual(invalidIntervals, [])
  t.deepEqual(totalTime >= bufferInterval * promisesLength, true)
})

test('using Promise.props with 4 promises', async (t) => {
  let timeLog = []
  let runCount = 0
  let bufferInterval = 100
  let promisesLength = 3
  const example = v => {
    timeLog.push(new Date)
    runCount++
    return Promise.delay(200, v)
  }
  const exampleLimited = promiseRateLimit(example, bufferInterval, 1)
  const results = await Promise.props({
    'alpha': exampleLimited('alpha'),
    'beta': exampleLimited('beta'),
    'gamma': exampleLimited('gamma'),
    'delta': exampleLimited('delta')
  })
  const intervals = getIntervalsBetweenDates(timeLog)
  const invalidIntervals = filter(intervals, (interval) => interval < bufferInterval)
  const totalTime = arraySum(intervals)
  t.is(intervals.length, promisesLength)
  t.deepEqual(invalidIntervals, [])
  t.deepEqual(totalTime >= bufferInterval * promisesLength, true)
  t.is(results.alpha, 'alpha')
  t.is(results.beta, 'beta')
  t.is(results.gamma, 'gamma')
  t.is(results.delta, 'delta')
})


test('using Promise.props with 12 promises', async (t) => {
  let timeLog = []
  let runCount = 0
  let bufferInterval = 100
  let promisesLength = 11
  const example = v => {
    timeLog.push(new Date)
    runCount++
    return Promise.delay(200, v)
  }
  const exampleLimited = promiseRateLimit(example, bufferInterval, 1)
  const results = await Promise.props({
    'a': exampleLimited('a'),
    'b': exampleLimited('b'),
    'c': exampleLimited('c'),
    'd': exampleLimited('d'),
    'e': exampleLimited('e'),
    'f': exampleLimited('f'),
    'g': exampleLimited('g'),
    'h': exampleLimited('h'),
    'i': exampleLimited('i'),
    'j': exampleLimited('j'),
    'k': exampleLimited('k'),
    'l': exampleLimited('l')
  })
  const intervals = getIntervalsBetweenDates(timeLog)
  console.log(intervals)
  const invalidIntervals = filter(intervals, (interval) => interval < bufferInterval)
  const totalTime = arraySum(intervals)
  t.is(intervals.length, promisesLength)
  t.deepEqual(invalidIntervals, [])
  t.deepEqual(totalTime >= bufferInterval * promisesLength, true)
})

I'm still getting the issue even with the example change.

[ 99, 98, 105, 106, 119, 106, 105, 105, 101, 106, 100 ]

  2 passed
  2 failed

  using Promise.props with 4 promises

  t.deepEqual(invalidIntervals, [])
              |                    
              [99]                 

  Generator.next (<anonymous>)

  using Promise.props with 12 promises

  t.deepEqual(invalidIntervals, [])
              |                    
              [99,98]              

  Generator.next (<anonymous>)

Answer 1

setTimeout (which is internally used in Promise.delay) does not guarantee accurate timing, it only ensures that the callback is invoked not before the given timeout expires. The actual timing will depend on machine load, the speed of the event loop, and possibly anything else.

In fact, the Node.js docs only state that

The callback will likely not be invoked in precisely delay milliseconds. Node.js makes no guarantees about the exact timing of when callbacks will fire, nor of their ordering. The callback will be called as close as possible to the time specified.

What will happen in your tests is that Promise.delay(50) sometimes takes longer than 50ms (not by much, but still), and the difference to the following log can become less than 100ms when the next Promise.delay(50) is more on time.

You should be able to mitigate this effect if you simply log the invocation times of your example function immediately, not after the artificial delay of about 50ms:

const example = v => {
  timeLog.push(new Date);
  runCount++;
  return Promise.delay(50, v)
};

To deal with the inaccuracy of the 100ms timeout itself, the easiest solution is to give it some leeway of maybe 5% (which makes 5ms in your case):

const invalidIntervals = filter(intervals, (interval) => interval < 100 * .95)
t.true(totalTime >= 400 * .95)

If you want to be absolutely sure that the delay is never too short, you can write your own function:

Promise.delayAtLeast = function(delay, value) {
    const begin = Date.now()
    return Promise.delay(delay, value).then(function checkTime(v) {
        const duration = Date.now() - begin;
        return duration < delay
          ? Promise.delay(delay - duration, v).then(checkTime);
          : v;
    });
};

and use that in promiseRateLimit.