<< Previous | Home

Is Asynchronous EJB Just a Gimmick?

In previous articles (here and here) I showed that creating non-blocking asynchronous applications could increase performance when the server is under a heavy load. EJB 3.1 introduced the @Asynchronous annotation for specifying that a method will return its result at some time in the future. The Javadocs state that either void or a Future must be returned. An example of a service using this annotation is shown in the following listing:

The annotation is on line 4. The method returns a Future of type String and does so on line 10 by wrapping the output in an AsyncResult. At the point that client code calls the EJB method, the container intercepts the call and creates a task which it will run on a different thread, so that it can return a Future immediately. When the container then runs the task using a different thread, it calls the EJB's method and uses the AsyncResult to complete the Future which the caller was given. There are several problems with this code, even though it looks exactly like the code in all the examples found on the internet. For example, the Future class only contains blocking methods for getting at the result of the Future, rather than any methods for registering callbacks for when it is completed. That results in code like the following, which is bad when the container is under load:

This kind of code is bad, because it causes threads to block meaning that they cannot do anything useful during that time. While other threads can run, there needs to be a context switch which wastes time and energy (see this good article for details about the costs, or the results of my previous articles). Code like this causes servers that are already under load to come under even more load, and grind to a halt.

So is it possible to get the container to execute methods asynchronously, but to write a client which doesn't need to block threads? It is. The following listing shows a servlet doing so.

Line 1 declares that the servlet supports running asynchronously - don't forget this bit! Lines 8-10 start writing data to the response but the interesting bit is on line 13 where the asynchronous service method is called. Instead of using a Future as the return type, we pass it a CompletableFuture, which it uses to return us the result. How? Well line 16 starts the asynchronous servlet context, so that we can still write to the response after the doGet method returns. Lines 17 onwards then effectively register a callback on the CompletableFuture which will be called once the CompletableFuture is completed with a result. There is no blocking code here - no threads are blocked and no threads are polled, waiting for a result! Under load, the number of threads in the server can be kept to a minimum, making sure that the server can run efficiently because less context switches are required.

The service implementation is shown next:

Line 7 is really ugly, because it blocks, but pretend that this is code calling a web service deployed remotely in the internet or a slow database, using an API which blocks, as most web service clients and JDBC drivers do. Alternatively, use an asynchronous driver and when the result becomes available, complete the future as shown on line 9. That then signals to the CompletableFuture that the callback registered in the previous listing can be called.

Isn't that just like using a simple callback? It is certainly similar, and the following two listings show a solution using a custom callback interface.

Again, in the client, there is absolutely no blocking going on. But the earlier example of the AsyncServlet2 together with the Service3 class, which use the CompletableFuture are better for the following reasons:
  • The API of CompletableFuture allows for exceptions / failures,
  • The CompletableFuture class provides methods for executing callbacks and dependent tasks asynchronously, i.e. in a fork-join pool, so that the system as a whole runs using as few threads as possible and so can handle concurrency more efficiently,
  • A CompletableFuture can be combined with others so that you can register a callback to be called only when several CompletableFutures complete,
  • The callback isn't called immediately, rather a limited number of threads in the pool are servicing the CompletableFutures executions in the order in which they are due to run.
After the first listing, I mentioned that there were several problems with the implementation of asynchronous EJB methods. Other than blocking clients, another problem is that according to chapter 4.5.3 of the EJB 3.1 Spec, the client transaction context does not propagate with an asynchronous method invocation. If you wanted to use the @Asynchronous annotation to create two methods which could run in parallel and update a database within a single transaction, it wouldn't work. That limits the use of the @Asynchronous annotation somewhat.

Using the CompletableFuture, you might think that you could run several tasks in parallel within the same transactional context, by first starting a transaction in say an EJB, then creating a number of runnables and run them using the runAsync method which runs them in an execution pool, and then register a callback to fire once all were done using the allOf method. But you're likely to fail because of a number of things:
  • If you use container managed transactions, then the transaction will be committed once the EJB method which causes the transaction to be started returns control to the container - if your futures are not completed by then, you will have to block the thread running the EJB method so that it waits for the results of the parallel execution, and blocking is precisely what we want to avoid,
  • If all the threads in the single execution pool which runs the tasks are blocked waiting for their DB calls to answer then you will be in danger of creating an inperformant solution - in such cases you could try using a non-blocking asynchronous driver, but not every database has a driver like that,
  • Thread local storage (TLS) is no longer usable as soon as a task is running on a different thread e.g. like those in the execution pool, because the thread which is running is different from the thread which submitted the work to the execution pool and set values into TLS before submitting the work,
  • Resources like EntityManager are not thread-safe. That means you cannot pass the EntityManager into the tasks which are submitted to the pool, rather each task needs to get hold of it's own EntityManager instance, but the creation of an EntityManager depends on TLS (see below).
Let's consider TLS in more detail with the following code which shows an asyncronous service method attempting to do several things, to test what is allowed.

Line 12 is no problem, you can rollback the transaction that is automatically started on line 9 when the container calls the EJB method. But that transaction will not be the global transaction that might have been started by code which calls line 9. Line 16 is also no problem, you can use the EntityManager to write to the database inside the transaction started by line 9. Lines 4 and 18 show another way of running code on a different thread, namely using the ManagedExecutorService introduced in Java EE 7. But this too fails anytime there is a reliance on TLS, for example lines 22 and 31 cause exceptions because the transaction that is started on line 9 cannot be located because TLS is used to do so and the code on lines 21-35 is run using a different thread than the code prior to line 19.

The next listing shows that the completion callback registered on the CompletableFuture from lines 11-14 also runs in a different thread than lines 4-10, because the call to commit the transaction that is started outside of the callback on line 6 will fail on line 13, again because the call on line 13 searches TLS for the current transaction and because the thread running line 13 is different to the thread that ran line 6, the transaction cannot be found. In fact the listing below actually has a different problem: the thread handling the GET request to the web server runs lines 6, 8, 9 and 11 and then it returns at which point JBoss logs JBAS010152: APPLICATION ERROR: transaction still active in request with status 0 - even if the thread running line 13 could find the transaction, it is questionable whether it would still be active or whether the container would have closed it.

The transaction clearly relies on the thread and TLS. But it's not just transactions that rely on TLS. Take for example JPA which is either configured to store the session (i.e. the connection to the database) directly in TLS or is configured to scope the session to the current JTA transaction which in turn relies on TLS. Or take for example security checks using the Principal which is fetched from EJBContextImpl.getCallerPrincipal which makes a call to AllowedMethodsInformation.checkAllowed which then calls the CurrentInvocationContext which uses TLS and simply returns if no context is found in TLS, rather than doing a proper permission check as is done on line 112.

These reliances on TLS mean that many standard Java EE features no longer work when using CompletableFutures or indeed the Java SE fork-join pool or indeed other thread pools, whether they are managed by the container or not.

To be fair to Java EE, the things I have been doing here work as designed! Starting new threads in the EJB container is actually forbidden by the specs. I remember a test I once ran with an old version of Websphere more than ten years ago - starting a thread caused an exception to be thrown because the container was really strictly adhering to the specifications. It makes sense: not only because the number of threads should be managed by the container but also because Java EE's reliance on TLS means that using new threads causes problems. In a way, that means that using the CompletableFuture is illegal because it uses a thread pool which isn't managed by the container (the pool is managed by the JVM). The same goes for using Java SE's ExecutorService as well. Java EE 7's ManagedExecutorService is a special case - it's part of the specs, so you can use it, but you have to be aware of what it means to do so. The same is true of the @Asynchronous annotation on EJBs.

The result is that writing asynchronous non-blocking applications in a Java EE container might be possible, but you really have to know what you are doing and you will probably have to handle things like security and transactions manually, which does sort of beg the question of why you are using a Java EE container in the first place.

So is it possible to write a container which removes the reliance on TLS in order to overcome these limitations? Indeed it is, but the solution doesn't depend on just Java EE. The solution might require changes in the Java language. Many years ago before the days of dependency injection, I used to write POJO services which passed a JDBC connection around from method to method, i.e. as a parameter to the service methods. I did that so that I could create new JDBC statements within the same transaction i.e. on the same connection. What I was doing was not all that different to what things like JPA or EJB containers need to do. But rather than pass things like connections or users around explicitly, modern frameworks use TLS as a place to store the "context", i.e. connections, transactions, security info, etc. centrally. As long as you are running on the same thread, TLS is a great way of hiding such boilerplate code. Let's pretend though that TLS had never been invented. How could we pass a context around without forcing it to be a parameter in each method? Scala's implicit keyword is one solution. You can declare that a parameter can be implicitly located and that makes it the compilers problem to add it to the method call. So if Java SE introduced such a mechanism, Java EE wouldn't need to rely on TLS and we could build truly asynchronous applications where the container could automatically handle transactions and security by checking annotations, just as we do today! Saying that, when using synchronous Java EE the container knows when to commit the transaction - at the end of the method call which started the transaction. If you are running asynchronously you would need to explicitly close the transaction because the container could no longer know when to do so.

Of course, the need to stay non-blocking and hence the need to not depend on TLS, depends heavily on the scenario at hand. I don't believe that the problems I've described here are a general problem today, rather they are a problem faced by applications dealing with a niche sector of the market. Just take a look at the number of jobs that seem to be currently on offer for good Java EE engineers, where synchronous programming is the norm. But I do believe that the larger IT software systems become and the more data they process, the more that blocking APIs will become a problem. I also believe that this problem is compounded by the current slow down in the growth hardware speed. What will be interesting to see is whether Java a) needs to keep up with the trends toward asynchronous processing and b) whether the Java platform will make moves to fix its reliance on TLS.

Copyright © 2015, Ant Kutschera
Social Bookmarks :  Add this post to Slashdot    Add this post to Digg    Add this post to Reddit    Add this post to Delicious    Add this post to Stumble it    Add this post to Google    Add this post to Technorati    Add this post to Bloglines    Add this post to Facebook    Add this post to Furl    Add this post to Windows Live    Add this post to Yahoo!

Javascript everywhere

I can think of at least two scenarios when you might need to run the same algorithms in both a Javascript and a Java environment.

  • A Javascript client is running in offline mode and needs to run some business logic or complex validation which the server will need to run again later when say the model is persisted and the server needs to verify the consistent valid state of the model,
  • You have several clients which need access to the same algorithms, for example a Javascript based single page application running in the browser and web service which your business partners use which is deployed in a Java EE application server.

You could build the algorithm twice: once in Java and once in Javascript but that isn't very friendly in terms of maintenance. You could build it once in just Java and make the client call the server to run the algorithm, but that doesn't work in an offline application like you can build using HTML 5 and AngularJS, and it doesn't make for a very responsive client.

So why not build the algorithm just once, using Javascript, and then use the javax.script Java package which first shipped with Java SE 7 and was improved with Java SE 8, in order to execute the algorithm when you need to use it from Java? That is precisely what I asked myself, and so I set about building an example of how to do it.

The first thing I considered was deployment and how the browser could access the Javascript. I didn't want anything with complex build processes which for example copy code maintained in a Node.js environment into a repo like Nexus. Rather I wanted to just drop the Javascript into a Java source folder and be able to use it from there. By having Javascript in a source folder of a Java project, it is automatically deployed inside a web archive so I built a little Servlet capable of serving the Javascript to a client over HTTP. Listing 1 shows the Servlet.

@WebServlet("/ScriptLoader.js")
public class ScriptLoader extends HttpServlet {

  protected void doGet(HttpServletRequest request, ...

    String script = request.getParameter("script");

    response.setContentType("text/javascript");

    Classloader cl = this.getClass().getClassLoader();
    try (InputStream is = cl.getResourceAsStream(script)) {
      int curr = -1;
      while ((curr = is.read()) != -1) {
        response.getOutputStream().write(curr);
      }
    }
  }
}

Listing 1: A Servlet capable of reading Javascript deployed in a WAR

Using the Servlet, you can load the Javascript into the browser, using normal HTML:

    <script type="text/javascript" src="ScriptLoader.js?script=rules.js">

Let's take a look at the Javascript algorithm in Listing 2.

;
(function() {
    var _global = this;

    ///////////////////////////////////////////
    // some javascript that we want to be able
    // to run on the server, but also on the
    // client
    ///////////////////////////////////////////
    function rule419(input) {
        return _(input)
        .filter(function(e){ 
            return e.name === "John"; 
        })
        .value().length == 1 ? "OK" : "Scam";
    };

    ///////////////////////////////////////////
    //create and assemble object for exporting
    ///////////////////////////////////////////
    var maxant = {};
    maxant.rule419 = rule419;

    ///////////////////////////////////////////
    //export module depending upon environment
    ///////////////////////////////////////////
    if (typeof (module) != 'undefined' && module.exports) {
        // Publish as node.js module
        module.exports = maxant;
    } else if (typeof define === 'function' && define.amd) {
        // Publish as AMD module
        define(function() {
            return maxant;
        });
    } else {
        // Publish as global (in browsers and rhino/nashorn)
        var _previousRoot = _global.maxant;

        // **`noConflict()` - (browser only) to reset global 'maxant' var**
        maxant.noConflict = function() {
            _global.maxant = _previousRoot;
            return maxant;
        };

        _global.maxant = maxant;
    }
}).call(this);

Listing 2: An example of an algorithm that we want to run in both Java and Javascript environments

Lines 10-16 are the algorithm that we want to run. The rest of the script is standard Javascript boiler plate when you want to create a script that can be run in all kinds of environments, for example, the browser, Rhino/Nashorn, require (e.g. Node.js) or AMD. Lines 27-35 and lines 39-43 aren't really necessary in the context of this article because we only run the code in the browser or Rhino/Nashorn, and we don't really care about being kind enough to provide a function for making our script non-conflicting if some other script is loaded with the same "namespace" (in this case 'maxant'). The algorithm itself, rule419 isn't really that interesting, but notice how it makes use of lodash when it wraps the input by calling the function _(...). That shows that we are able to make use of other modules loaded into the global space who use script patterns similar to that shown in Listing 2. For demo purposes, I have created an algorithm which simply counts the number of times that 'John' is present in the model. The model is an array of objects with the name attribute. In reality, if we are going to go to the extent of writing an algorithm in just Javascript but making it possible to run it both in Java and Javascript environments, I hope that it would be a damn site more complicated that the algorithm shown here :-)

To make the algorithm useful, I have chosen to run it from a mini- AngularJS application. If you aren't familiar with AngularJS then all you need to know is that you can now call rule419 from Javascript like this:

    var result = maxant.rule419(model);

In AngularJS it is recommended to make modules injectable, which can easily be done as shown in Listing 3, when bootstrapping the application. See here for more details.

'use strict';

// Declare app which depends on views, and components
angular.module('app', [
  'ngRoute',
  'app.view1'
])...

//make rules injectable
.factory('maxant', function(){return window.maxant;})
...

Listing 3: app.js - Making rules injectable in AngularJS

The AngularJS controller can then inject the module as shown in Listing 4.

...
.controller('View1Ctrl', ['$scope', '$http', '$routeParams', 'maxant',
  function($scope, $http, $routeParams, maxant) {

    //create a model
    var model = [
                 {name: 'Ant'}, 
                 {name: 'John'}
                ];
...    
    //execute javascript that can also be executed on the server using Java
    $scope.clientResult = maxant.rule419(model);    
...
}]);

Listing 4: Controller code making use of the injected module in order to run the algorithm in question

Lines 2-3 inject the module named maxant and line 12 then uses the rule419 function and puts the result into scope so that it can be displayed to the user.

The harder part of this exercise is getting the Javascript to be runnable in a Java environment like a Java EE application server or a batch program. This Java 7 link and this Java 8 link give examples of how to run Javascript from Java. I've encapsulated code from those examples to provide a very simple API which Java application code can use to run the Javascript.

//instantiate the engine
Engine engine = new Engine(Arrays.asList("lodash-3.10.0.js", "rules.js"));

//prepare data model - the input to the javascript
Person[] people = new Person[]{new Person("John"), new Person("John")};

//invoke engine
String result = engine.invoke(people, "maxant", "rule419");

//evaluate output
assertEquals("Scam", result);

Listing 5: Calling the Javascript algorithm from Java

Listing 5 starts on line 2 by instantiating the abstraction that I have created (see Listing 6). It simply needs a list of Javascript file names which it should load into the scripting engines' space. The two Javascript files used in this example live in the src/main/resources folder so that Maven packs them into the JAR/WAR that is built. That makes them accessible via the Classloader as shown in Listings 1 and 6. Listing 5 then continues on line 5 by creating some kind of data model which is the input to the algorithm. The Person class has an attribute named name which is private, but nonetheless used by the algorithm. In Java we would use getter/setter methods to access that data, but notice line 13 of Listing 2 just references the attribute by its name and not by a bean-style accessor method. More on that shortly... Line 8 of Listing 5 then executes the algorithm, by telling the engine to invoke rule419 of the maxant module, using people as the input. The result of the Javascript execution which happens under the hood can then be used, for example on line 11. It doesn't have to be a String, it could also be a Java object which the rule returns.

The implementation behind that simple API is shown in Listings 6, 7 and 8. That code can be thought of as library code.

public Engine(List<String> javascriptFilesToLoad) {
  ScriptEngineManager engineManager = new ScriptEngineManager();
  engine = engineManager.getEngineByName("nashorn");
  if (engine == null) {
      //java 7 fallback
      engine = engineManager.getEngineByName("JavaScript");
  }

  //preload all scripts and dependencies given by the caller
  for (String js : javascriptFilesToLoad) {
      load(engine, js);
  }

  referenceToJavascriptJSONInstance = engine.eval("JSON");
}

Listing 6: The implementation behind the neat API, part 1

Listing 6 shows the constructor which first instantiates a ScriptEngineManager from the javax.scripting package and uses it to create the real Javascript engine which executes the algorithm in question, rule419. Notice the fallback used for making the code compatible with Java 7 and 8. I didn't try it but probably just getting the engine by the name "JavaScript" suffices... The constructor does two more things: it loads all the scripts which the caller wants in scope and then gets itself a reference to the Javascript JSON object which is used later for converting JSON to Javascript objects.

private void load(ScriptEngine engine, String scriptName) {
  //fetch script file from classloader (e.g. out of a JAR) 
  //and put it into the engine
  ClassLoader cl = this.getClass().getClassLoader();
  try (InputStream script = cl.getResourceAsStream(scriptName)) {
      engine.eval(new InputStreamReader(script));
  }
}

Listing 7: The implementation behind the neat API, part 2

Listing 7 is called from Listing 6 and shows how the Javascript files are loaded using the Classloader and then sent to the ScriptEngine on line 6. Finally, Listing 8 shows the process of invoking the Javascript.

public <T> T invoke(Object input, String module, 
                              String functionNameToExecute) {

  final Invocable invocable = (Invocable) engine;

  //convert
  ObjectMapper om = new ObjectMapper();
  String dataString = om.writeValueAsString(input);
  Object data = invocable.invokeMethod(
                          referenceToJavascriptJSONInstance, 
                          "parse", dataString);

  //execute
  Object moduleRef = engine.get(module);
  Object result = invocable.invokeMethod(moduleRef, 
                                  functionNameToExecute, data);
  return (T) result;
}

Listing 8: The implementation behind the neat API, part 3

First, lines 6-7 use Jackson to convert the Java model into a JSON string. That JSON string is then parsed inside the ScriptEngine on lines 9-11, which is equivalent to calling JSON.parse(dataString) in Javascript. The conversion from Java to JSON and then Javascript isn't strictly necessary since Rhino/Nashorn know how to use Java objects. But I've chosen to do it that way so that you can skip wrapping all the attributes in accessor code like getXYZ(...). This way, the Javascript can simply access fields like this: input[2].name which gets the third elements attribute called name, rather than say input.get(2).getName(), like you would have to do in plain old Java.

There is one thing to note: as far as I can tell, Rhino and Nashorn are not thread-safe, so you might need to think about that in any implementation that you write. I would probably use a pool of Engine objects, each pre-loaded with the necessary scripts, because it is the instantiation and setup that takes the longest amount of time.

So, to conclude, it is indeed possible to write algorithms once and run them in both Javascript and Java environments, but unlike Java and its "write once, run anywhere" slogan, the algorithms are written in Javascript.

All the code for this demo is available at Github/maxant/javascript-everywhere.

Copyright ©2015, Ant Kutschera

Social Bookmarks :  Add this post to Slashdot    Add this post to Digg    Add this post to Reddit    Add this post to Delicious    Add this post to Stumble it    Add this post to Google    Add this post to Technorati    Add this post to Bloglines    Add this post to Facebook    Add this post to Furl    Add this post to Windows Live    Add this post to Yahoo!

A reactive and performant Spray + Akka solution to "Playing with concurrency and performance in Java and Node.js"

In my previous post I examined a fictitious trading engine and compared a Java based blocking solution to a Node.js based non-blocking solution. At the end of the post I wrote that:

I suspect that following the recent success of Node.js, more and more asynchronous Java libraries will start to appear.

Well such libraries already exist, for example: Akka, Spray, and this Mysql async driver.

I set myself the challenge of creating a non-blocking Java based solution using exactly those libraries, so that I could compare its performance to that of the Node.js solution created for the last article. The first thing you might have noticed is that these are all Scala based libraries, but I wrote this solution in Java even though it is a little less syntactically elegant. In the last article I introduced a solution based upon Akka whereby the trading engine was wrapped in an actor. Here, I have dropped Tomcat as the HTTP server and replaced it with Spray, which neatly integrates the HTTP server straight into Akka. In theory this should make no difference to performance, because Spray is NIO just as Tomcat 8 is, out of the box. But what attracted me to this solution was that overall, the number of threads is greatly reduced, as Spray, Akka and the async Mysql library all use the same execution context. Running on my Windows development machine, Tomcat has over 30 threads compared to just a few over 10 for the solution built here, or compared to Websphere or JBoss where there are hundreds of threads. The execution context is basically a pool of threads which run tasks that are given to it. Since all the libraries used in the solution presented here were non-blocking, the number of threads can be kept low and close to the theoretical optimum, so that as little context switching takes place as possible, making the process run efficiently.

The code written for this article is on GitHub. The first part of the program is the main method which starts up Spray and Akka:


Line 1 creates an actor system which is public so that I can access it from elsewhere, since it is used to access the single execution context which I want to use throughout the program. (In code where maintainability is an issue I would write something so that this object could be injected into the relevant parts of the program.) Line 5 then uses the system to instantiate an actor which is used to handle all HTTP requests for purchase and sales orders. Lines 7-11 just set up configuration data for the server. Lines 12 and 13 are where we then take the configuration and our actor and tell Akka IO use them and the HTTP module to send all HTTP requests as messages to our actor from line 5. Lines 15-17 are where I effectively setup a timer task which fires every 5 seconds to output some statistics. The important part here is to notice that I am not using Java's Timer to schedule the task since that just adds more unnecessary threads to my process. Instead I use the same execution context as Akka, so as few threads as possible are created.

Next is the actor for handling the HTTP requests:


Line 3 shows an example of how integrating Scala in a Java program can be ugly, but how you can sometimes hide away those ugly parts by adding your own abstractions. The HTTP actor which responds to HTTP requests has 3 jobs. The first job, on line 6, is where it creates a router which I shall describe below, and which it can use to delegate work to. The second job is to handle all new connections on lines 24-25 which tells Spray that this actor will also handle the actual requests and not only the connections. The third job this actor has is shown on lines 9-18 where the actor takes an HTTP request and delegates (routes) some work to another actor in the system.

This actor knows the HTTP model but the HTTP abstraction doesn't leak into the next layer of the system. Instead, the actor passes domain objects (or value objects or case classes or similar) onto the actors which encapsulate the trading engines. The construction of such a domain objects can be seen on lines 15 and 16, using data extracted from the HTTP request, e.g. on line 13, or out of say a JSON object in the request body. Spray contains useful directives which can help you extract the data from the request, and abstract a little away from HTTP, if that is what you want. Which domain object to construct depend on the REST-like interface which I have built and is handled on lines 9, 12 and 19. Had I used Scala, I could have written more elegant code using pattern matching on the HttpRequest object. The domain object is passed onto the trading engine by getting the router from line 6 to route the domain object to a suitable actor, on line 17. Last, but not least, line 18 is where the sales order request is acknowledged in an HTTP response which passes a JSON object back to the consumer, together with the unique ID assigned to the order, so that its status can be queried later (it gets persisted into the sales objects).

The next snippet shows how we partition the market and create a number of actors to handle requests in parallel.


This code is similar to what we did in the last article. In order to scale out and use more than one core concurrently, the market is partitioned by product ID and each trading engine runs concurrently for a different market partition. In the solution presented here, an EngineActor is created per partition and wrapped in a Routee on line 10. A map of actors keyed by product ID is also filled on line 14. The router is built using the routees and the map on line 19 and it is this which the HttpActor uses in the previous snippet, when delegating work. Note also line 17, which starts the trading engine contained in the EngineActor, so that it is up and running, ready to trade purchase and sales orders, when they are passed to these actors.

The EngineActor class isn't shown here explicitly since it is almost identical to the actors used in the last article, and it simply encapsulate a trading engine which handles all products from a particular market partition. Line 19 above uses a RoutingLogic to build the router, which is shown below:


The select(...) method on line 10 is called by the router when it receives an object which it must route to the correct actor. Using the map created in the previous listing, and the product ID obtained from the request, it is easy to find the actor which contains the trading engine responsible for the relevant market partition. By returning the routee which wraps that actor, Akka will pass the order object on to the correct EngineActor, which then puts the data into the model when that message is handled at a time when the trading engine is between trading cycles and the actor next checks its inbox.

OK, so that is the front end dealt with. The second major change that was required to the solution from the previous article, was the design of the method which persists sales after trading takes place. In the Java based solution I was synchronously iterating over each sale and sending an insert statement to the database and only processing the next sale once the database had replied. With the solution presented here, I chose to process the sales in parallel by fire off an insert request to the database and immediately moving to the next sale and doing the same. The responses were handled asynchronously within the execution context using a callback which I provided. I wrote the program to wait for the last insert to be acknowledged before trading continued with newly created purchase and sales orders which had arrived since the last trading session had started. This is shown in the following listing:


The persistSales(...) method is called by the trading engine after each trading cycle, and is passed a list of sales made during that trading cycle, and a callback function to be called once all the persistence is complete. If nothing was sold, then line 38 calls the callback immediately. Otherwise, a counter is created on line 5 which is initialised with the number of sales to be persisted. Each sale is persisted asynchronously on lines 7-15. Note how a Future is returned on line 15 and how we use another callback on lines 16-35 to handle completion of the future - there is no blocking done here, waiting for the future to complete! The above mentioned counter is decremented on line 25, once the sale is persisted, and once all sales are persisted, the callback passed into the persistSales(...) method is called. Note that the class JFunction1 used on line 16 is a shim allowing easier integration of Scala - the code is on GitHub at the link given above. Lines 21 and 22 show that I had a little problem with the async Mysql library that I used. It is still a beta, and doesn't seem to have a way to get hold of the generated (autoincrement) primary key of the sale. Note also line 35, where I pass in the execution context which Akka is using, so that the Future which handles completion of the insert statement is processed on one of the existing threads, rather than some new thread - again, keeping the total number of threads as low as possible.

This listing also shows an interesting problem, namely that the thread which calls the database to insert the data is not necessarily the same thread which might need to close the connection [1]. In normal Java EE and Spring there is often use of thread local storage (also see here). If you called through to a bean from the function handling the completion of the future, resources which are injected into it may not work, because the container cannot work out what the context is. Scala solves this problem using implicit parameters, which are passed into methods under the hood.

The listing above uses the PersistenceComplete callback, which is shown below on lines 14-16. It also uses a connection pool which is created using the following code. Yet again, the execution context which Akka uses is passed over to the async Mysql library, on line 10 below. Line 10 below also shows a non-default pool configuration where I allow a maximum queue size of up to a thousand. During load testing I was getting a lot of errors indicating that the pool was saturated, and increasing this value solved the problem.


The callback passed into persistSales(...) is shown in the next listing. The following code is hardly different from the original shown in the last article, except that it is now asynchronous in style. It is called once all sales are persisted and only then does the callback send a message (via its event listener) to the actor, on line 14 below. That message will normally be at the back of the inbox after a load of new purchase and sales orders. Each of those messages will be processed, leading to the trading engine model being updated with the new orders, before trading is recommenced.


The final code listing is the modification to the Node.js solution which was made so that it too would persist sales in parallel, rather than one after the other, as was the case in the last article.


Line 5 fetches a connection from the pool and the same connection is reused for all sales, "in parallel", and only released, i.e. returned to the pool, once the last sale is persisted, on line 19.

So, yet again, it's time to compare the solutions via some load tests. This time I chose to see what maximum rate of sales I could achieve with each of the following three solutions:

  • Case 1 - The solution presented here, namely Spray + Akka + the async Mysql driver,
  • Case 2 - The modified Node.js solution using persistence in parallel,
  • Case 3 - The original Tomcat non-blocking connector, but with synchronous persistence.

The cases were run using the hardware from the last article, with the trading engines running on the fast hardware and the database on the slow hardware, because that was the best setup to show how blocking I/O causes performance problems. For each case, there were three variables which I could adjust while tuning. These were:

  • Number of trading engines (either as actors or as child processes),
  • Time waited by client between calls to the server,
  • Number of concurrent clients.

The last two basically tuned the number of requests per second, since the connections were not kept open awaiting the trading results (see previous article). The results were as follows, with the best performance shown in bold.

Case 1 - Spray + Akka + async Mysql driver
# trading engines client wait time between calls concurrent clients sales per minute approx. CPU on trading hardware
8 100ms 60 42,810 25-35%
8 80ms 70 62,392 25-35%
8 60ms 80 75,600 30-40%
8 40ms 90 59,217 30-50%
10 60ms 80 too many DB connection problems
5 60ms 60 67,398 25-35%
6 60ms 80 79,536 25-35%

 

Case 2 - Node.js with persistence in parallel
# trading engines client wait time between calls concurrent clients sales per minute approx. CPU on trading hardware
8 200ms 30 6,684 40-50%
8 100ms 60 started to lag behind
8 100ms 40 17,058 25-35%
8 100ms 50 started to lag behind
12 100ms 50 20,808 45-60%
16 100ms 60 24,960 45-65%
20 100ms 80 32,718 45-70%
25 60ms 80 51,234 75-85%
30 50ms 80 22,026 75-85%
25 10ms 70 17,604 75-90%

 

Case 3 - Tomcat 8 NIO, with synchronous blocking persistence
# trading engines client wait time between calls concurrent clients sales per minute approx. CPU on trading hardware
4 200ms 30 9,586 5%
4 150ms 30 10,221 5%
8 200ms 30 9,510 5%


The results show that bolting a NIO connector onto Tomcat and thinking that you are non-blocking and performant is dangerous, as that solution underperformed by a factor of nearly 8 compared to the Akka solution. The results also show that by using non-blocking libraries and writing a non-blocking solution in Java, it is possible to create very performant solution in comparison to Node.js. Not only was the Java solution capable of some 50% throughput, it used less than half the CPU doing so.

Very important: please note that this is a result particular to the algorithms used here and my architecture, design and implementation. It is also dependent on using "non-standard" Java libraries, and indeed, the Mysql library I used was missing functionality, for example reading generated primary keys out of the result of an insert. Please do your own experiments for your use cases before drawing conclusions on relative performance of Java vs. Scala vs. Node.js!

A noteworthy point when comparing the variation of the number of trading engines: in Node.js it directly controlled the number of child processes, analagous to the number of threads; in the Akka solution it had no effect whatsoever on the number of threads in the system - that number stayed constant! In Akka solutions, varying the number of actors has an effect on the number of messages in their inboxes.

Further information pertaining to the use of Akka and Spray can be found at this good video. Please take the time to also quickly read up about the reactive manifesto. The Akka solution presented here is reactive because it is responsive (highest throughput of all three cases), resilient (Akka provides easy ways to deal with failure, although none were necessary here), elastic (it automatically scales out because Akka manages the thread pool size in the execution context and it scales up because Akka provides transparent location of actors), and it is message driven (due to using the actor model).

[1] The Mysql library used here doesn't require that the connection be closed and returned to the pool, as e.g. Apache database pool does. Doing so in fact causes problems! Leaving it open causes no problems, as proven by the load tests which I ran.

Copyright © 2014, Ant Kutschera

Social Bookmarks :  Add this post to Slashdot    Add this post to Digg    Add this post to Reddit    Add this post to Delicious    Add this post to Stumble it    Add this post to Google    Add this post to Technorati    Add this post to Bloglines    Add this post to Facebook    Add this post to Furl    Add this post to Windows Live    Add this post to Yahoo!

Playing with concurrency and performance in Java and Node.js

Imagine a simple market where buyers and sellers interested in the same product come together to trade. For each product in the market, buyers interested in the product could form an orderly queue, sorted on a "first come, first serve" basis. Each buyer could then approach the cheapest seller and trade, purchasing as much of the product from the seller as they wish for the price dictated by the seller. Should no seller be offering the product at a price low enough, the buyer could step to the side, giving the next buyer the opportunity to trade. Once all buyers have had the chance to make a trade, and after all products in the market have been through the cycle, the whole process can start again, after satisfied buyers and sellers leave and new ones take their place. In the internet age, there is no reason why buyers and sellers could not trade on a virtual platform, using this type of algorithm, from the comfort of their armchair. Indeed, trading platforms like this have existed for many years.

While basic, this type of problem becomes interesting when used to build a computer based trading engine. Simple questions pose challenges:
  • How could the market scale up across multiple cores?
  • How could the market scale out across multiple machines?
Inherently, the answers boil down to requiring some form of concurrency so that such a trading engine can scale. Typically I would jump into writing a Java based solution using perhaps an execution pool and the synchronized keyword to ensure that multiple threads updated the central model in an orderly fashion.

But recently I have started to play around with Node.js, and this platform is interesting for problems like that described above because it is a single threaded non-blocking platform. The idea is that the programmer has less to reason about when designing and writing algorithms, because there is no danger that two threads might want to access common data at the same time.

I took the time to model the market described above in JavaScript and the trading function is as follows (the rest of the JavaScript code can be found here [1]).

The code makes use of the Underscore.js library which provides a bunch of useful functional helpers, much like those added to Java 8 Streams.

The next step was to create a trading engine, which encapsulates a market as shown in the following snippet, which: prepares the market on line 1 by removing timed out sales where no suitable buyer and seller could be paired; runs through the trading process on line 3; notes statistics on line 6; and persists sales on line 8.


So far we haven't seen any code which is really interesting, except for line 8 above, where the sales are persisted. Sales are inserted into a table which contains indexes on the sale ID (an auto incremented primary key), the product ID, sales order ID and purchase order ID (which comes from the program). The call to the persistSale(...) function makes a call to a MySQL database and the library used makes use of non-blocking I/O when it calls the database. It has to do that because in Node.js there are no other threads available in the process and everything running in the process would block while waiting for the results of the database insertion. What actually happens is that the Node.js process fires off the insertion request and the rest of the code runs immediately, to completion. If you examine the rest of the JavaScript code, you'll notice that there is in fact no other code which runs after the call to the persistSale(...) function. At that point, Node.js goes to the event queue and looks for something else to do.

To make the trading engine useful, I decided to architect it as a standalone component in my landscape and expose its interface a simple HTTP service. That way I profit in a number of ways, for example having a deployable unit which can be scaled outwards by deploying it on several nodes in a cluster and having the back end decoupled from any front ends which I have yet to create.

The script named trading-engine-parent3.js has a dependency on a little web framework named express, and the relevant parts of that script are shown below:


Lines 8 and 12 call through to the engine and add a purchase order / sales order respectively. Exactly how is something we shall examine shortly. Line 16 shows an important choice that I made in the design, namely HTTP requests are not kept open while waiting for the result of a trade order. Originally I tried keeping the requests open, but during load testing I ran into classic dead locking problems. The market contained orders, but none with matching products, and the server wouldn't accept new requests after its TCP backlog filled (see also here), and so new purchase and sales orders could not be created by other clients and so the market didn't contain the necessary products for sales to flow consistently.

So, let's return to what happens after the sales of a trade are persisted. Since persisting is asynchronous, we provide a callback function on lines 8-20 of the previous script (trading-engine-loop.js) which handles the result by sending the appropriate events to the buyer/seller (lines 13-14) and making a call to setTimeout(loop, 0+delay) which tells Node.js to run the loop function after at least delay milliseconds. The setTimeout function puts this work onto the event queue. By calling this function, we allow Node.js to service other work which has been placed on the event queue, for example HTTP requests to add purchase or sales orders, or indeed calling the loop function to start trading again.

Because of the non-blocking asynchronous nature of the code that I have written for this Node.js solution, there really is no need for more threads. Except... how do we scale up the process and use other cores on the machine? Node.js supports creating child processes and doing so is very easy indeed, as shown by the following snippets.


Line 5 imports the API for working with child processes and we partition the market by grouping product IDs on lines 14-25. For each partition, we start a new child process (line 17) and register a callback for receiving data piped from the child process back to the parent on line 18. We stick a reference to the child process into a map keyed by the product ID on line 23 so that we can send it messages by calling for example: n.send(someObject). It is quite nifty how you simply send and receive objects and how they are transported as (presumably) JSON - it's very similar to RMI calls in Java.

With the solution presented above, the trading engine can be scaled vertically by adding child processes as well as horizontally by deploying the trading engine parent (including its web server) on multiple nodes and using a load balancer to distribute requests based on product ID to the correct node handling trading of that product.

In case you are wondering if a buyer can be present in multiple markets then the answer is yes of course - the markets are virtual, and buyers are not restricted by a physical location as they might be in real life :-)

What would the equivalent Java solution look like, and how would it perform? The complete Java code is available here [1].

Starting with the market and its trade() method, the Java code looks similar to the JavaScript version, using Java 8 Streams instead of the Underscore library. Interestingly, it is just about identical in number of lines of code or put more subjectively, maintainability.


As I wrote in my book a couple of years ago, it's normal to write multi-paradigm solutions these days, with functional programming being used for data manipulation, object orientation used for encapsulating say a buyer or seller or market, and as we shall see shortly, service and aspect oriented programming for glueing complex framework code into place to provide say a REST-like HTTP service. Next, the run method of the trading engine in Java, which trades as long as the engine is in a running state:


The Java design is a little different than the Node.js design in that I created a simple method named run which I will call once. It runs over and over so long as the boolean field named running is true. I can do this in Java because I can utilise other threads to do work in parallel to trading. In order to tune the engine, I introduced a short configurable delay at the end of each iteration, where the thread pauses. It was set to pause for 3 milliseconds during all the tests I did, which was the same used for the JavaScript solution.

Now I just mentioned using threads to scale out the system. In this case, threads are analogous to the child processes used in the Node.js solution. Just as in the Node.js solution, the Java solution partitions the market by product ID but instead of using child processes, the Java solution runs each trading engine (which encapsulates a market) on a different thread. Theory dictates that the optimum number of partitions will be similar to the number of cores, but experience shows that it also depends on how much the threads are blocked waiting for example to persist sales in the database. Blocked threads make room for other threads to run in their place, but too many threads reduces performance as context switching between threads becomes more relevant. The only reliable way to tune the system is to run several load tests and play with the variables like the number of engines in use.

The thread simply delegates running to the engine, which as shown above, runs in a loop until it's shut down.


For the Java solution, I used Tomcat as a web server and created a simple HttpServlet to handle requests to create purchase and sales orders. The servlet partitions the market and creates the relevant threads as well as starting them (note that a better way to do this would be to start the threads upon servlet startup and shutdown the engines when the servlet is stopped - the code shown is not production ready!). Line 15 of the following code starts the threads shown in the previous snippet.


The servlet handles purchase and sales requests as follows:


The relevant engine is looked up on line 8 and given the details for example to create a purchase order on line 14. Now it initially looks as though we have everything we need for the Java solution, but no sooner as I put load on the server, I was running into ConcurrentModificationExceptions and it was obvious what was happening: line 14 in the above snippet was adding purchase orders to the model in the engine at the same time that the market was say iterating over buyers purchase orders to determine which buyers were interested in which products.

It is exactly this kind of problem which Node.js avoids with its single threaded approach. It is also the kind of problem which can be really hard to fix in the Java world! The following tips may help:
  • Using the synchronized keyword to ensure synchronous access to the given (data) object,
  • In cases where you only need to read data and react to it, make a copy of the data,
  • Use thread safe collections for your data structures,
  • Modify the design.
The first tip can lead to deadlocks and is somewhat notorious in the Java world. The second tip is sometimes useful but involves the overhead of copying data. The third tip sometimes helps, but note the following comment contained in the Javadocs of java.util.Collections#synchronizedCollection(Collection):
Returns a synchronized (thread-safe) collection backed by the specified collection... It is imperative that the user manually synchronize on the returned collection when traversing it... Failure to follow this advice may result in non-deterministic behavior.
Using thread-safe collections is simply not enough and the problems related to the first tip don't go away as simply as one might hope. That leaves the fourth tip. If you take a look back at the code above, you will find a method named prepareMarket(). Why don't we store all purchase and sales orders in their own model until the trading engine which runs in its own thread gets to the point where it needs to prepare the market, and at that point, take all those open orders and add them to the market's model, before trading commences? That way we can avoid concurrent access from several threads and the need to synchronize on the data. When you look at all the Java source code you'll see that the TradingEngine does exactly this with the two fields named newPurchaseOrders and newSalesOrders.

The interesting thing about this kind of design is that it closely resembles the actor model, and the perfect library for Java already exists, namely Akka. So I added a second servlet to the application which uses Akka rather than threads, to show how it solves the concurrency problems. Described basically, an actor is an object which contains state (data), behaviour and an inbox of messages. No one has access to the state except for the actor, since it should be private to the actor. The actor responds to messages in the inbox and runs its behaviour based on what the messages tell it to do. The actor guarantees that it will only ever read and respond to a single message at any one time, so that no concurrent state modifications can occur. The new servlet creates new actors as follows, on line 13, using the actor system created on line 4. Note that just as above, this code is not production ready, as the actor system should be started when the servlet starts rather than within a static context as shown below, and it should be shut down when the servlet is stopped. Line 19 sends a message to the newly created actor to tell it to start the trading engine which it contains.


The actor class is shown next, with its data and behaviour being encapsulated in its instance of the trading engine.


You can see that the trading engine on line 4 of the actor class is private and only ever used when messages are received, for example on lines 12, 18 or 20. That way, the guarantee that no two threads can access it at the same time can be upheld, and importantly for us, there is absolutely no need to synchronize on the engine, meaning that our ability to reason about concurrency has been massively improved! Note that to allow messages in the inbox to be processed, the trading engine runs one trading session, and then a new "run" message is pushed to the inbox. That way, any messages from the HTTP server to add purchase/sales orders are first processed, before the trading continues.

It's now time to start looking at the performance of the designs under load. I had three machines at my disposal:
  • A "high performance" 6 core AMD processor with 16 GB RAM running Linux (Fedora Core 20),
  • A "medium performance" quad core I5 processor with 4GB RAM running Windows 7, and
  • A "low performance" Intel Core 2 Duo processor with 4GB RAM also running Linux.
Of all the possible deployment combinations I chose to run the following two:

# Load test client Trading engine Database
1 medium fast slow
2 medium slow fast

Before running the tests I made the prediction that the first case, running the trading engine on the fast hardware, would favour the Node.js solution, because Node.js should be better in situations where there is blocking. Since the database would be running on a slow machine, my hypothesis was that there would be a considerable amount of blocking compared to the other case with the trading engine running on the slow hardware.

The three machines were connected on a 100 megabit/second cabled network. The load test client was a custom built Java program which uses an execution pool to run 50 parallel threads making random purchase and sales orders, continuously. Between requests, the client pauses. The pause time was tuned so that the worse performing of the Java and Node.js processes could keep up with the load but were close to the tipping point where they started to lag, and is recorded below in the results. Results were not recorded before at least half a million sales had been persisted, and not before the throughput had stabilised (think hot spot optimisations). Throughput was measured using the number of rows inserted into the database, rather than the dodgy statistics which the programs output.

The results were:

Case 1 - 200ms client wait time, 4 trading engines
Fast trading engines, slow database
Synchronized Java Java with Akka Node.js
throughput (sales per minute) 5,100 5,000 6,400
average CPU on machine with trading engines <50% <40% 40-60%

Case 2 - 50ms client wait time, 2 trading engines
Slow trading engines, fast database
Synchronized Java Java with Akka Node.js
throughput (sales per minute) 32,800 30,100 15,000
average CPU on machine with trading engines 85% 90% >95%

In case one, the trading engines were not CPU bound. In case two, the trading engines were CPU bound, but the system as a whole performed faster than case one. In neither case was the system network bound, because I measured up to a maximum of 300 Kilobytes per second transfer speeds which is less than 3% of the network capability. In case one, where the database was the slowest component, the trading engines appeared to be I/O bound, waiting for the results of the database inserts. Since Node.js uses the non-blocking paradigm for all its code, it performed better than the Java solution. While I used Tomcat 8 with its preconfigured non-blocking (NIO) connector, the MySQL driver was the standard JDBC blocking version. In case two, where the database was faster, the trading engines were CPU bound, and the Java solution worked out faster.

My results were not actually that surprising - Node.js is well known to perform well, especially under blocking conditions. See the following two links for results which I think correlate well with my results: What Makes Node.js Faster Than Java? and Analysis of PayPal's Node-vs-Java Benchmarks. The comments at the end of the second link are very interesting and I feel mostly valid points.

Something I didn't try was to optimise the Java solution by making the persistence also non-blocking, so that it too was an entirely non-blocking solution. It would be possible because a non-blocking (albeit non-JDBC) MySQL driver exists. But it would also require changing the design of the Java solution. And, as pointed out in one of the comments in the above links, perhaps this redesign would be the most challenging part to the average Java programmer, who until recently, if at all, has never had to program within the asynchronous non-blocking paradigm. It isn't that it is hard, it's that it is different, and I suspect that following the recent success of Node.js, more and more asynchronous Java libraries will start to appear. Please note that this last paragraph is not meant so spawn any kind of debate - I am in no way saying that any one of Java, JavaScript, the JVM or Node.js is better. What I am saying is that a) I used to be a staunch supporter of Java and its ecosystem and in the last few years I have matured to realise that other platforms are also great and b) choose the right tools for the job at hand by evaluating with a proof of concept, for example as I have done here.

[1] Please note that the code provided in this article is not fit for any purpose and is certainly not production ready, nor representative of what I might produce professionally - it's hacked together to investigate the topics discussed above!

Copyright © 2014, Ant Kutschera
Social Bookmarks :  Add this post to Slashdot    Add this post to Digg    Add this post to Reddit    Add this post to Delicious    Add this post to Stumble it    Add this post to Google    Add this post to Technorati    Add this post to Bloglines    Add this post to Facebook    Add this post to Furl    Add this post to Windows Live    Add this post to Yahoo!

Rule Engine for Node.js

Based on my original blog posting, this posting introduces a ported Javascript version of my rule engine, for Node.js.

I have the requirement to use a rule engine. I want something light weight and fairly simple, yet powerful. While there are products out there which are super good, I don't want something with the big learning overhead. And, I fancied writing my own!

Here are my few basic requirements:

  • Use some kind of expression language to write the rules,
  • It should be possible to store rules in a database,
  • Rules need a priority, so that only the best can be fired,
  • It should also be possible to fire all matching rules,
  • Rules should evaluate against one input which can be an object like a tree, containing all the information which rules need to evaluate against
  • Predefined actions which are programmed in the system should be executed when certains rules fire.

So to help clarify those requirements, imagine the following examples:

1) In some forum system, the administrator needs to be able to configure when emails are sent.

Here, I would write some rules like "when the config flag called sendUserEmail is set to true, send an email to the user" and "when the config flag called sendAdministratorEmail is true and the user has posted less than 5 postings, send an email to the administrator".

2) A tarif system needs to be configurable, so that the best tarif can be offered to customers.

For that, I could write rules like these: "when the person is younger than 26 the Youth tarif is applicable", "when the person is older than 59, the Senior tarif is applicable", and "when the person is neither a youth, nor a senior, then they should be given the Default tarif, unless they have had an account for more than 24 months, in which case they should be offered the Loyalty tarif".

3) A train ticket can be considered to be a product. Depending upon the travel request, different products are suitable.

A rule here, could be something like: "if the travel distance is more than 100km and first class is desired, then product A is to be sold."

Finally, a more complex example, involving some iteration of the input, rather than just property evaluation:

4) Timetable software needs to deterimine when students can leave school.

A rule for that might read: "If a class contains any student under age 10, the entire class gets to leave early. Otherwise, they leave at the normal time."

So, with those requirements in mind, as well as wanting to use Node.js and Javascript (rather than the Java which is what the original engine runs on), I set to work porting the original code. It works like this:

1) An engine is configured with some rules.

2) A rule has these attributes:
    - namespace: an engine may contain many rules, but only some may be relevant to a particular call and this namespace can be used for filtering
    - name: a unique name within a namespace
    - expression: a Javascript expression for the rule
    - outcome: a string which the engine might use if this rules expression evaluates to true
    - priority: an integer. The bigger the value, the higher the priority.
    - description: a useful description to aid the management of rules.

3) The engine is given an input object and evaluates all rules (optionally within a namespace) and either:
    a) returns all rules which evaluate to true,
    b) returns the outcome (string) from the rule with the highest priority, out of all rules evaluating to true,
    c) execute an action (defined within the application) which is associated with the outcome of the rule with the highest priority, out of all rules evaluating to true.

4) "Action"s are objects which the application programmer can supply. An action must have a property called 'name'. When the engine is asked to execute an action based on the rules, the name of the action matching the "winning" rule's outcome property is executed.

5) A rule can be built up of "sub-rules". A subrule is only ever used as a building block on which to base more complex rules. When evaluating rules, the engine will never select a subrule to be the best (highest priority) "winning" rule, i.e. one evaluating to true. Subrules make it easier to build complex rules, as I shall show shortly.

So, time for some code!


First, install the library using npm install maxant-rules, passing it the optional --save argument to save the dependency to the package.json file.

In order to use the library, you need to "require" the library, for example by adding the following lines to your script.

var rules = require('maxant-rules');
var Rule = rules.Rule;
var Engine = rules.Engine;
var NoActionFoundException = rules.NoActionFoundException;
var DuplicateNameException = rules.DuplicateNameException;
var SubRule = rules.SubRule;
var ParseException = rules.ParseException;
var NoMatchingRuleFoundException = rules.NoMatchingRuleFoundException;


First, let's look at the code for the tarif system:

 

var r1 = new Rule("YouthTarif", "input.person.age < 26", "YT2011", 3, "ch.maxant.someapp.tarifs");
var r2 = new Rule("SeniorTarif", "input.person.age > 59", "ST2011", 3, "ch.maxant.someapp.tarifs");
var r3 = new Rule("DefaultTarif", "!#YouthTarif && !#SeniorTarif", "DT2011", 3, "ch.maxant.someapp.tarifs");
var r4 = new Rule("LoyaltyTarif", "#DefaultTarif && input.account.ageInMonths > 24", "LT2011", 4, "ch.maxant.someapp.tarifs");
var rules = [r1, r2, r3, r4];

var engine = new Engine(rules);

var request = {person: {name: "p", age: 24}, account: {ageInMonths: 5}};
var tarif = engine.getBestOutcome(request);


So, in the above code, I have added 4 rules to the engine. Then, I created a tarif request object, which is the input object. That object is passed into the engine, when I ask the engine to give me the best outcome. In this case, the best outcome is the string "YT2011", the name of the most suitable tarif for the customer I added to the tarif request.

How does it all work? When the engine is given the rules, it does some validation on them. Notice how the first two rules refer to an object called "input"? That is the object passed into the "getBestOutcome" method on the engine. The engine creates a local reference to the input object named input and then calls eval for each rules expression. Anytime an expression evaluates to "true", the rule is put to the side as a candidate to be the winner. At the end, the candidates are sorted in order of priority, and the outcome property of the rule with the highest priority is returned by the engine.

Notice how the third and fourth rules contain the '#' character. That is not standard Javascript. The engine examines all rules when they are passed to it, and it replaces any token starting with a hash symbol, with the expression found in the rule named the same as the token. It wraps the expression in brackets. The logger outputs the full rule after reference rules have been resolved and replaced, just in case you want to check the rule.

In the above business case, we were only interested in the best tarif for the customer. Equally, we might have been interested in a list of possible tarifs, so that we could offer the customer a choice. In that case, we could have called the "getMatchingRules" method on the engine, which would have returned all rules, sorted by priority. The tarif names are (in this case) the "outcome" field of the rules.

In the above example, I wanted to receive any of the four outcomes, from the four rules. Sometimes however, you might want to build complex rules based on building blocks, but you might never want those building blocks to be a winning outcome. The train trip example from above can be used to show what I mean here:

var rule1 = new SubRule("longdistance", "input.distance > 100", "ch.maxant.produkte");
var rule2 = new SubRule("firstclass", "input.travelClass == "1", "ch.maxant.produkte");
var rule3 = new Rule("productA", "#longdistance && #firstclass", "productA", 3, "ch.maxant.produkte");
var rules = [rule1, rule2, rule3];

var e = new Engine(rules);

var request = {travelClass: 1, distance: 150};
var rs = e.getMatchingRules(request); 


In the above code, I build rule3 from two subrules. But I never want the outcomes of those building blocks to be output from the engine. So I create them as SubRules. SubRules don't have an outcome property or priority. They are simply used to build up more complex rules. After the engine has used the sub-rules to replace all tokens beginning in a hash during initialisation, it discards the SubRules - they are not evaluated.

The travel request above contains the distance and travel class.

Next, consider the business case of wanting to configure a forum system. The code below introduces actions. Actions are created by the application programmer and supplied to the engine. The engine takes the outcomes (as described in the first example), and searches for actions with the same names as those outcomes, and calls the "execute" method on those actions. This functionality is useful when a system must be capable of predefined things, but the choice of what to do needs to be highly configurable and independent of deployment.

var r1 = new Rule("SendEmailToUser", "input.config.sendUserEmail == true", "SendEmailToUser", 1, "ch.maxant.someapp.config");
var r2 = new Rule("SendEmailToModerator", "input.config.sendAdministratorEmail == true and input.user.numberOfPostings < 5", "SendEmailToModerator", 2, "ch.maxant.someapp.config");
var rules = [r1, r2];
		
var log = [];
log.add = function(i){this[this.length] = i;};
		
var action1 = {name: "SendEmailToUser", execute: function(i) {
    log.add("Sending email to user!");
}};
var action2 = {name: "SendEmailToModerator", execute: function(i) {     log.add("Sending email to moderator!");
}};

var engine = new Engine(rules);

var forumSetup = 
  {config: 
    {sendUserEmail: true, 
     sendAdministratorEmail: true}, 
   user: {numberOfPostings: 2}};
			
engine.executeAllActions(forumSetup, [a1, a2]);


In the code above, the actions are passed to the engine when we call the "executeAllActions" method. In this case, both actions are executed, because the forumSetup object causes both rules to evaluate to true. Note that the actions are executed in the order of highest priority rule first. Each action is only ever executed once - it's name is noted after execution and it will not be executed again, until the engines "execute*Action*" method is called again. Also, if you only want the action associated with the best outcome to be executed, call the "executeBestAction" method instead of "executeAllActions".

Finally, let's consider the classroom example.

var expression = 
    "var result = _.find(input.students, function(student){" +
    "    return student.age < 10;" +
    "});" +
    "result != undefined";

var r1 = new Rule("containsStudentUnder10", expression , "leaveEarly", 1, "ch.maxant.rules", "If a class contains a student under 10 years of age, then the class may go home early");
		
var r2 = new Rule("default", "true" , "leaveOnTime", 0, "ch.maxant.rules", "this is the default");
		
var classroom = {students: [{age: 12}, {age: 10}, {age: 8}]};

var e = new Engine([r1, r2]);
		
var outcome = e.getBestOutcome(classroom);


The outcome above is "leaveEarly", because the classroom contains one student whose age is less than 10. See how I have written an expression which uses the 'find' method from the underscorejs library. The engine simply requires a rule to return true, if the rule is to be considered a candidate for firing.

There are more examples in the tests contained in the source code, which can be found here: https://github.com/maxant/rules/tree/master/rules-js.

So, the requirements are fulfiled, except for "It should be possible to store rules in a database". While this library doesn't support reading and writing rules to / from a database, rules are String based. So it wouldn't be hard to create some database code which reads rules out of a database and populates Rule objects and passes them to the Engine. I haven't added this to the library, because normally these things as well as the management of rules is something quite project specific. And because my library will never be as cool or popular as something like Drools, I'm not sure it would be worth my while to add such functionality.


© 2014, Ant Kutschera

Social Bookmarks :  Add this post to Slashdot    Add this post to Digg    Add this post to Reddit    Add this post to Delicious    Add this post to Stumble it    Add this post to Google    Add this post to Technorati    Add this post to Bloglines    Add this post to Facebook    Add this post to Furl    Add this post to Windows Live    Add this post to Yahoo!