Let's now choose a computationally expensive problem to use as a base for our experiment. A good candidate is the subset sum problem that consists of deciding whether a set (or multiset) of integers contains a non-empty subset that has a sum equal to zero. For example, if we had as input the set [1, 2, -4, 5, -3], the subsets satisfying the problem are [1, 2, -3] and [2, -4, 5, -3].

The simplest algorithm is the one that checks every possible combination of subsets of any size, and it has a computational cost of O(2ⁿ), or in other words, it grows exponentially with the size of the input. This means that a set of 20 integers would require up to 1,048,576 combinations to be checked, not bad for testing our assumptions. Of course, the solution might be found a lot sooner than that; so, to make things harder, we are going to consider the following variation of the subset sum problem: given a set of integers, we want to calculate all the possible combinations whose sum is equal to a given arbitrary integer.

Let's then work to build such an algorithm; let's create a new module called subsetSum.js. We will start by creating a class called SubsetSum:

const EventEmitter = require('events').EventEmitter; 
 
class SubsetSum extends EventEmitter { 
  constructor(sum, set) { 
    super(); 
    this.sum = sum; 
    this.set = set; 
    this.totalSubsets = 0; 
  } 
//... 

The SubsetSum class is extending from the EventEmitter class; this allows us to produce an event every time we find a new subset matching the sum received as input. As we will see, this will give us a lot of flexibility.

Next, let's see how we can generate all the possible combinations of subsets:

  _combine(set, subset) { 
    for(let i = 0; i < set.length; i++) { 
      let newSubset = subset.concat(set[i]); 
      this._combine(set.slice(i + 1), newSubset); 
      this._processSubset(newSubset); 
    } 
  } 

We will not go into too much detail about the algorithm, but there are two important things to notice:

The _processSubset() method is responsible for verifying that the sum of the elements of the given subset is equal to the number we are looking for:

  _processSubset(subset) { 
    console.log('Subset', ++this.totalSubsets, subset); 
    const res = subset.reduce((prev, item) => (prev + item), 0); 
    if(res == this.sum) { 
      this.emit('match', subset); 
    } 
  } 

Trivially, the _processSubset() method applies a reduce operation to the subset in order to calculate the sum of its elements. Then, it emits an event of type 'match' when the resulting sum is equal to the one we are interested in finding (this.sum).

Finally, the start() method puts all the preceding pieces together:

  start() { 
    this._combine(this.set, []); 
    this.emit('end'); 
  } 

The preceding method triggers the generation of all the combinations by invoking _combine(), and lastly, emits an 'end' event signaling that all the combinations were checked and any possible match has already been emitted. This is possible because _combine() is synchronous; therefore, the 'end' event will be emitted as soon as the function returns, which means that all the combinations were calculated.

Next, we have to expose the algorithm we just created over the network, as always we can use a simple HTTP server for the task. In particular, we want to create an endpoint in the format /subsetSum?data=<Array>&sum=<Integer> that invokes the SubsetSum algorithm with the given array of integers and sum to match.

Let's then implement this simple server in a module named app.js:

const http = require('http'); 
const SubsetSum = require('./subsetSum'); 
 
http.createServer((req, res) => { 
  const url = require('url').parse(req.url, true); 
  if(url.pathname === '/subsetSum') { 
    const data = JSON.parse(url.query.data); 
    res.writeHead(200); 
    const subsetSum = new SubsetSum(url.query.sum, data); 
    subsetSum.on('match', match => { 
      res.write('Match: ' + JSON.stringify(match) + '
'); 
    }); 
    subsetSum.on('end', () => res.end()); 
    subsetSum.start(); 
  } else { 
    res.writeHead(200); 
    res.end('Im alive!
'); 
  } 
}).listen(8000, () => console.log('Started')); 

Thanks to the fact that the SubsetSum object returns its results using events, we can stream the matching subsets as soon as they are generated by the algorithm, in real time. Another detail to mention is that our server responds with the text I'm Alive! every time we hit a URL different from /subsetSum. We will use this for checking the responsiveness of our server, as we will see in a moment.

We are now ready to try our subset sum algorithm. Curious to know how our server will handle it? Let's fire it up then:

node app

As soon as the server starts, we are ready to send our first request; let's try with a set of 17 random numbers, which will result in the generation of 131,071 combinations, a nice amount to keep our server busy for a while:

curl -G http://localhost:8000/subsetSum --data-urlencode "data=[116, 119,101,101,-116,109,101,-105,-102,117,-115,-97,119,-116,-104,-105,115]" --data-urlencode "sum=0"

We will start to see the results streaming live from the server, but if we try the following command in another terminal while the first request is still running, we will spot a huge problem:

curl -G http://localhost:8000

We will immediately see that this last request hangs until the subset sum algorithm of the first request has finished; the server is unresponsive! This was kind of what we expected. The Node.js event loop runs in a single thread, and if this thread is blocked by a long synchronous computation, it will be unable to execute even one more cycle in order to respond with a simple I'm alive!

We quickly understand that this behavior does not work for any kind of application meant to serve multiple requests. But don't despair in Node.js, we can tackle this type of situation in several ways. Let's analyze the two most important ones.

Usually, a CPU-bound algorithm is built upon a set of steps. It can be a set of recursive invocations, a loop, or any variation/combination of those. So, a simple solution to our problem would be to give back the control to the event loop after each one of these steps completes (or after a certain number of them). This way, any pending I/O can still be processed by the event loop in those intervals where the long-running algorithm yields the CPU. A simple way to achieve this is to schedule the next step of the algorithm to run after any pending I/O requests. This sounds like the perfect use case for the setImmediate() function (we already introduced this API in Chapter 2, Node.js Essential Patterns).

_combineInterleaved(set, subset) { 
  this.runningCombine++; 
  setImmediate(() => { 
    this._combine(set, subset); 
    if(--this.runningCombine === 0) { 
      this.emit('end'); 
    } 
  }); 
}   

  _combine(set, subset) { 
    for(let i = 0; i < set.length; i++) { 
      let newSubset = subset.concat(set[i]); 
      this._combineInterleaved(set.slice(i + 1), newSubset); 
      this._processSubset(newSubset); 
    } 
  } 

  start() { 
    this.runningCombine = 0; 
    this._combineInterleaved(this.set, []); 
  } 

const http = require('http'); 
//const SubsetSum = require('./subsetSum'); 
const SubsetSum = require('./subsetSumDefer'); 
 
http.createServer(function(req, res) { 
  // ... 

node app

curl -G http://localhost:8000/subsetSum --data-urlencode "data=[116, 119,101,101,-116,109,101,-105,-102,117,-115,-97,119,-116,-104,-105,115]" --data-urlencode "sum=0"

curl -G http://localhost:8000

Deferring the steps of an algorithm is not the only option we have for running CPU-bound tasks; another pattern for preventing the event loop from blocking is using child processes. We already know that Node.js gives its best when running I/O-intensive applications such as web servers, which allows us to optimize resource utilization thanks to its asynchronous architecture.

So, the best way we have to maintain the responsiveness of an application is to not run expensive CPU-bound tasks in the context of the main application and instead, use separate processes. This has three main advantages:

Node.js has an ample tool belt of APIs for interacting with external processes. We can find all we need in the child_process module. Moreover, when the external process is just another Node.js program, connecting it to the main application is extremely easy and we don't even feel like we are running something external to the local application. The magic happens thanks to the child_process.fork() function, which creates a new child Node.js process and also automatically creates a communication channel with it, allowing us to exchange information using an interface very similar to an EventEmitter. Let's see how this works by refactoring our subset sum server again.

const fork = require('child_process').fork; 
 
class ProcessPool { 
  constructor(file, poolMax) { 
    this.file = file; 
    this.poolMax = poolMax; 
    this.pool = []; 
    this.active = []; 
    this.waiting = []; 
  } 
  //... 

acquire(callback) { 
  let worker; 
  if(this.pool.length > 0) {                // [1] 
    worker = this.pool.pop(); 
    this.active.push(worker); 
    return process.nextTick(callback.bind(null, null, worker)); 
  } 
 
  if(this.active.length >= this.poolMax) {  // [2] 
    return this.waiting.push(callback); 
  } 
 
  worker = fork(this.file);                 // [3] 
  this.active.push(worker); 
  process.nextTick(callback.bind(null, null, worker)); 
} 

  release(worker) { 
    if(this.waiting.length > 0) {                          // [1] 
      const waitingCallback = this.waiting.shift(); 
      waitingCallback(null, worker); 
    } 
    this.active = this.active.filter(w => worker !==  w);  // [2] 
    this.pool.push(worker); 
  } 

const EventEmitter = require('events').EventEmitter; 
const ProcessPool = require('./processPool'); 
const workers = new ProcessPool(__dirname + '/subsetSumWorker.js', 2); 
 
class SubsetSumFork extends EventEmitter { 
  constructor(sum, set) { 
    super(); 
    this.sum = sum; 
    this.set = set; 
  } 
 
  start() { 
    workers.acquire((err, worker) => {               // [1] 
      worker.send({sum: this.sum, set: this.set}); 
 
      const onMessage = msg => { 
        if (msg.event === 'end') {                   // [3] 
          worker.removeListener('message', onMessage); 
          workers.release(worker); 
        } 
 
        this.emit(msg.event, msg.data);             // [4] 
      }; 
 
      worker.on('message', onMessage);             // [2] 
    }); 
  } 
} 
module.exports = SubsetSumFork; 

const SubsetSum = require('./subsetSum'); 
 
process.on('message', msg => {                   // [1] 
  const subsetSum = new SubsetSum(msg.sum, msg.set); 
 
  subsetSum.on('match', data => {                // [2] 
    process.send({event: 'match', data: data}); 
  }); 
 
  subsetSum.on('end', data => { 
    process.send({event: 'end', data: data}); 
  }); 
 
  subsetSum.start(); 
}); 

const http = require('http'); 
//const SubsetSum = require('./subsetSum'); 
//const SubsetSum = require('./subsetSumDefer'); 
const SubsetSum = require('./subsetSumFork'); 
//... 

curl -G http://localhost:8000/subsetSum --data-urlencode "data=[116,119,101,101,-116,109,101,-105,-102,117,-115,-97,119,-116,-104,-105,115]" --data-urlencode "sum=0"

curl -G http://localhost:8000

I'm alive!