Bluebird: Load balancing / throttling

[vitaly-t]

Promise approach has a great potential to solving the load balancing / throttling problem, which is yet missing. This is a proposal to add such feature to the library.

As an example, use a question + my answer from StackOverflow for massive amounts of queries.

In essence, we have a number of promises that need to be resolved sequentially. Typically, this can be achieved by using promise.all(). However, in cases where the number of promise objects is so large that a single call to promise.all() is impossible, we need to implement a complex workaround, like the one link to which I provided earlier (perhaps not a very good one at that).

What we need is something called promise.page or promise.throttle that would adhere to the idea of splitting one huge chunk of promises into smaller chunks and page through them all till they are all resolved. In addition, we need a flexibility in the resolution strategy:

• specify that each chunk/page of promises is to be resolved one after another. This is very-very important, because in many cases an attempt to execute a chunk of promises before the previous one is finished will lead to running out of memory.
• by default, the whole request should reject, if one chunk rejects, but we need an option where it is possible to either just stop or carry on with other chunks of promises.
• such a method would need to request each next chunk of data through a promise, because typically the data would never reside in memory in its entirety.

It should help greatly if you think if this all as an almost-infinite queue that got terminated and now needs to be processed entirely, fast and in huge bulks.

And you don't need to think of it as something that deals only with copious amounts of promises. Totally not. Here's an example:

We have 100 requests to be sent to a particular service in one go. However, the service accepts only up to 10 at a time, so we need to send it in 10 blocks. Promise support for throttling would shine in this case.

P.S. I've been tempted to implement it in my own library - pg-promise, but it's just truly a generic promise task, and not just database-related.

[spion]

This issue comes up again and again but its not solved because its impossible to solve it in the way people suggest.

This is because promises are eager. When a promise is created, the operation it represents has inevitably been already started/executed. Therefore its impossible to schedule its start at a later time.

As such, you _cannot_ have a throttle operation that runs on promises.

What you can do, though, is:

1. Guard individual functions.

For example see https://github.com/cujojs/when/blob/master/docs/api.md#whenguard - this will work for both of your database queries and service queries examples

1. Deal with arrays of items rather than arrays of promises

Bluebird has concurrency options on Promise.map etc.

1. Use a lazy abstraction instead, like futures or lazy promises.

Its possible to write promise.throttle and promise.page for those. But they have to be produced by something like lazyPromisify. It might be worth investigating this direction - it would be a promise that starts the operation once then (or equivalent derived methods like catch) is called, and it should be compatible with normal promises.

[vitaly-t]

@spion , when you talk about the impossibility and scheduling a start time for the promise, I'm afraid you are talking about something else. If you look at the code example that I provided in that link, that workaround is based solely on promises, nothing else. But let me quote the code here again:

function insertRecords(N) {
    return db.tx(function (ctx) {
        var queries = [];
        for (var i = 1; i <= N; i++) {
            queries.push(ctx.none('insert into test(name) values($1)', 'name-' + i));
        }
        return promise.all(queries);
    });
}
function insertAll(idx) {
    if (!idx) {
        idx = 0;
    }
    return insertRecords(100000)
        .then(function () {
            if (idx >= 9) {
                return promise.resolve('SUCCESS');
            } else {
                return insertAll(++idx);
            }
        }, function (reason) {
            return promise.reject(reason);
        });
}
insertAll()
    .then(function (data) {
        console.log(data);
    }, function (reason) {
        console.log(reason);
    })
    .done(function () {
        pgp.end();
    });

Wrapping this logic up in a single promise call is very doable, and it has nothing to do with scheduling a start time. All that's needed is an objective look at it to turn this into a good generic method.

Some people are even trying to implement something similar: https://www.npmjs.com/package/promise-throttle, though I think this isn't a great example.

[spion]

That library is misleading. If you look at the code carefully, you will realize that it doesn't actually queue promises. It queues functions that returns promises, which is very different.

[vitaly-t]

The implementation approach only matters from the point of whether or not it is done using just promises, and in my book relying on a callback function to return a promise or a set of, is still a valid approach.

I've been thinking about the protocol, and here're the 2 interesting methods that I tried to implement:

function cascade(route, context){
   // route - array of functions, each takes context and returns a promise,
  // except for the last one;

  // loop through the array: resolve the first one, pass data into the second one,
 // and so on;
}

That's cascading promises: resolving them in a chain, while passing the result from the one to the next one, along with the context;

Another one:

function channel(source, dest, context) {
// pump paged data from source to the destination, till the source is dry;
// both source and dest are functions that return a promise;
// context can be passed to allow paging logic + state control;
}

And while the cascade is for other tasks, channel is what's needed to make throttling work.

For the time being, I'm trying to better think them through and implement. Those are interesting logical patterns that I believe will fit nicely into the promise architecture as search/logic patterns.

[dsernst]

Is there a definitive reason this was closed? It continues to be implemented by hand, even though a more general function would be helpful.

In particular see the approach listed at the end of this answer: http://stackoverflow.com/a/28223454/2348750

Often when people ask about this problem what they actually care about is making a function return a result at most every number of milliseconds or make a function act as a monitor for how often calls are made. This is to throttle the number of calls that are made to a web service that rate-limits. This should be limited at the level of the function that returns the promise. For example:

var queue = Promise.resolve();
function throttle(fn, ms){
    var res = queue.then(function(){ // wait for queue
        return fn(); // call the function
    });
    queue = Promise.delay(ms).return(queue); // make the queue wait
    return res; // return the result
}

This would let you do:

function myApiCall(){
    // returns a promise
}
var api = throttle(myApiCall, 300); // make call at most every 300 ms;

api(); // calls will be sequenced and queued
api(); // calls will be made at most every 300 ms
api(); // just be sure to call this directly, return this to consumers

[vitaly-t]

@dsernst

What I ended with in the end was my own implementation of throttling promises-queries:

// Sequentially resolves dynamic promises returned by a promise factory:
    // - with an array of resolved data, if `empty` = false (default);
    // - with total number of resolved requests, if `empty` = true.
    this.sequence = this.queue = function (factory, empty) {
        if (typeof(factory) !== 'function') {
            return $p.reject("Invalid factory function specified.");
        }
        var idx = 0, result = [];

        function loop() {
            var obj;
            try {
                obj = factory.call(self, idx, self); // get next promise;
            } catch (e) {
                return $p.reject(e);
            }
            if ($isNull(obj)) {
                // no more promises left in the sequence;
                return $p.resolve(empty ? idx : result);
            }
            if (typeof(obj.then) !== 'function') {
                // the result is not a promise;
                return $p.reject("Invalid promise returned by factory for index " + idx);
            }
            return obj
                .then(function (data) {
                    if (!empty) {
                        result.push(data); // accumulate resolved data;
                    }
                    idx++;
                    return loop();
                });
        }

        return loop();
    };

which is now part of pg-promise library. All I care about is that it works perfectly.

Also, I documented the issues I had without it and how to use throttling for database queries.

This might give you a good idea of how to implement this for yourself.

[spion]

Its a somewhat specialized feature best implemented as a stand-alone module (independent of promise implementation).

There are many more strategies on how to enqueue things, including limiting to N requests per M seconds (instead of just controlling how often a single request is made), limiting to N concurrent requests and so on. Each of those has a different implementation.

Note: the implementation (from stackoverflow) may not do what the linked stackoverflow question asks unless the calls to the throttled functions are done in series. This one will work regardless:

function throttle(fn, ms) {
  var queue = Promise.resolve()
  return function() {
    var res = queue.then(fn)
    // Wait for either the result, or the previous request to complete + additional ms
    // (whichever one is slower). Don't keep the value.
    queue = Promise.join(res, queue.delay(ms)).return()
    return res
  }
}

[vitaly-t]

@spion As per my post earlier, the implementation must differentiate between a massive and a super-massive sequence in the following way:

A massive sequence can be set to track the individual resolve results for the entire sequence, to resolve with an array of those in the end for any kind of verification/validation.

A super-massive sequence implies that it is too large too be able to track individual results from it. At best, only a counter can be maintained and resolved with in the end.

And this is how I did it within my implementation. In my example with the database, Node JS can easily track up to 100,000 query results on an average, but when it goes beyond that, one have to disable such result tracking, or else Node JS process will choke, trying to use too much memory. The link I gave above has a good performance test there.

[spion]

@vitaly-t what you've implemented and what @dsernst is asking for are totally different - they want time-based throttling while you want sequencing with or without keeping the results. Thats one reason why queuing / throttling is not in bluebird - they have subtly different meanings for different contexts...

[vitaly-t]

@spion there are usually two types of throttling used:

• Memory balancing throttling, for memory-intensive operations, which is the one that I implemented;
• CPU balancing throttling, for CPU-heavy operations, which is the one @dsernst is looking for, it seems.

It is possible, of course, to implement both at the same time, for the mixed throttling.

There is also a proxy kind of throttling, when a component stretches a queue of requests in time to throttle load for another component that processes the queue, but that's not as interesting.

I believe it is very doable to implement Memory+CPU throttler within a promise library for generic use.

[spion]

No, what @dsernst is looking for is time delays, i.e. making the time between two operations at least N miliseconds. Usually thats called rate-limiting.

What you implemented is usually called sequencing (as the name you've chosen for the method correctly indicates)

Then there is the actual throttling as in lodash.throttle which accepts calls once every N ms and discards the rest, which is different behavior from both the above.

Therefore we're all talking about vastly different ways to limit the number of function calls with different variations, and to cover them well it would be best to write a separate library.

[vitaly-t]

making the time between two operations at least N milliseconds

-that, and CPU-throttling are the same, you are talking semantics. The CPU throttling is done by introducing delays between request batches of either predefined size or dynamic size, based on the current CPU load. The latter is outside any promise library.

[spion]

No, this is not CPU throttling. Thats only one possible reason why you would want to do rate-limiting. The delay could be 30 seconds, because an external service (e.g. yahoo weather, or xively, etc) says they only accept one request every 30 seconds. They could have that limit for various reasons, e.g. to conserve bandwidth, or to reduce IO load, etc.

[vitaly-t]

@spion what you describe is exactly what I called proxy throttling earlier. The size of the delay isn't very relevant here.

Anyhow, I don't see the point in arguing over this any more. I'm gonna try to make time for implementing a generic promise throttling, as I have a good idea of what it should be.

[vitaly-t]

I have finally made time to start working on a promise API that will help with the throttling directly, plus some other generic cases: spex

[vitaly-t]

@spion, @dsernst

Guys, you never commented back about my take on the promises throttling: spex

After so much discussion here, I appreciate some kind of feedback ;)

[spion]

@vitaly-t I only glanced at it, haven't had the time to look in depth.

Regarding batch, I can't see any pressing reasons to use it instead of settle

Regarding sequence, its useful but I'd suggest you look into iterators and generators and see if you could adapt your terminology to match the existing one. A comparison of the similarities and differences would be helpful too.

I've written some of my thoughts on #734 - basically I think the right solution for these kind of problems are streams with promise support, but I haven't added the necessary methods to that promise-streams library, and I still haven't fully fleshed out the design.

[vitaly-t]

@spion batch is there for the following reasons:

• In all the tasks described in Batch Processing we need the promise.all result when it resolves, and we need promise.settle result when rejected.
• As explained there, combining it all the time is very awkward, and way slower than the batch method that executes it all at once. This becomes even more critical when you try to involve it into trhottling implemented by method page, which resolves each package/chunk of requests as a batch.
• My solution works with all promise libraries, without relying one one specific promise library.

I have looked at the generators. And the thing is, they have no provision for any kind of load balancing, not to mention dynamic load balancing. Their implementation is quite fixed, no room for throttling data either. The combination of sequence and page allow for all possible scenarios of data throttling and load balancing via promises.

Have a look at the basic concepts I described there, if you can find a moment, with the examples, they might explain it better ;)