mgm technology blog

Designing and Implementing our Camel-based mgm Cosmo Router - Robust and Fail-Safe Message Routing with Apache Camel, Part 1

Michael Frieß — Tue, 09 Apr 2013 12:38:56 +0000

We recently finished a subproject to integrate our mgm Cosmo insurance software with an external CRM system. Both systems had to exchange XML documents in a reliable and robust manner in order to keep their data in sync. We used Apache Camel as the middleware to handle all the transfers between the Java and .NET based systems. This blog series discusses our solution and shares our experiences with Apache Camel.

mgm Cosmo is a standardized software solution that allows insurance companies to produce and manage commercial and industrial business. It accompanies the insurance sales process starting with a submission as a sales lead. A submission may produce one or more offers. If an offer is accepted by both the customer and all the other parties, it becomes an insurance policy. This policy can later be extended, changed or cancelled in the form of an endorsement.

Technically, all these five main business entities are managed as self-contained XML documents which you could easily store in document-oriented NoSQL database. In the following they are simply referred to as XML documents.

Exemplary insurance process with all involved parties and its five main business entities.

Project Goals

The business goal for the system integration was first, to make all XML documents from Cosmo available for viewing in an external CRM system and second, to receive all corresponding partner and account information from the CRM.

We chose Apache Camel as the middleware to handle all the Enterprise Application Integration (EAI) tasks, specifically the SOAP transfers between our Java backend application and the external .NET services. This Camel-driven application was simply named “Cosmo Router”.

Our main goal for the Cosmo Router was to be as reliable, automated, robust and fail-safe as possible. For example, we strived for a system which can handle connection failures and timeout errors with adaptable retry strategies like increasing waiting periods. As you can imagine it didn’t take us long to find even more sophisticated failover scenarios. However, retry strategies respectively failover behavior was only one small topic to be encountered during this project.

This blog article is accompanied by several source code examples but assumes a basic understanding of Apache Camel. In case you never heard of Apache Camel, you might want to take a look at these additional resources and examples:

Architecture Overview

Pretty early, our customer defined SOAP as the mandatory messaging technology. The task at hand was both to transfer data to newly created web services as well as to receive data from them. In this article we will only focus on the sending part. For better distinction, the target web services will be called the “external” web services. The external web services were developed by a third party in .NET respectively Windows Communication Foundation 4 (WCF4).

One of our main objectives for our architecture was to decouple the transfer process from the Cosmo Web Application’s workflow in order to process all transfers asynchronously (from the web application’s point of view). This decision was possible because the application workflow did not depend on the transfer results. It was also driven by previous negative experiences with another SOAP web service and its limited availability. In practical words, we wanted a Cosmo user to be able to continue working with the application instead of being blocked by a “Transfer in progress, please wait” popup.

As it turned out, this definition became very handy: during the deployment of the final release, an initial migration of all existing XML documents was planned. In numbers, tens of thousands of transfers needed to be processed. But with the help of asynchronous transferring, the Cosmo Web Application only needed to be unavailable for a few hours to safely prepare all transfers. This was a great improvement compared to two full days needed for the actual transferring. When the initial transferring even became a whole week due to bugs, we could relax with a “no problem” smile and happy users.

Driven by the idea of asynchronism we finally ended up with the following architecture:

This diagram shows the sending process from the Cosmo Web Application to the external CRM web service.

The whole process is triggered by specific user interactions in the web application as indicated by the big grey arrow. We won’t go into details there but instead focus on the “Transfer Table” and particularly the Cosmo Router in the middle lane.

Transfer Processing

Let’s take a closer look at each step in the above shown diagram. Please note that for the sake of simplicity all of the following examples don’t contain log statements or error and exception handling.

Step 1: Getting new Transfers from the Database

The Cosmo Router periodically checks the database’s “Transfer Table” for new transfers. At first, we wanted to do the database polling with Camel’s SQL component which seemed to be a perfect fit. However, it doesn’t support being used as a “Camel Consumer” (i.e. as a starting point of a Camel route or in other words as a “from” endpoint). So we decided to simply start the routing process with the Camel Timer component as described next.

Starting Routes with Timers

A timer as a “from” endpoint triggers the processing und subsequently the polling of the database for new transfers. In Camel’s Spring XML DSL this looks as follows:





  
  ...
  
    ${properties:TRANSFER_TYPE_OFFER}
  
  ...

The route references the timer as a “from” endpoint. The timer fires as soon as the route is started and does nothing more than creating an (almost) empty Camel Exchange object which is all we want at that moment. Afterward, the route just sets a Camel property and delegates the processing to another route called “Send.GetAndProcessNewTransfers”. As you might have guessed already, this is for re-using the route several times (more precisely once for each transferable XML document).

Using multiple, separated timer routes brings some benefits:

Each timer route can be disabled without affecting all the other timer routes. This is very useful when there is a bug in the processing of one specific XML document and you want to “pause” exactly that type. This can keep your log clean of many retry or failure attempts – not to mention the savings on bandwidth, memory or CPU usage (if these count anyways).
All the timer routes can run concurrently which greatly speeds things up but keeps the routing logic simple, too. Or at least simpler than using one asynchronously firing Timer for all the types together.

Fetching new XML Documents from the Transfer Table

As mentioned before, all the timer routes delegate the processing to another Camel route named “Send.GetAndProcessNewTransfers”. Here it is:

...

The obvious thing to recognize is the usage of a custom bean named “sqlExecutor”. We found this approach to be much easier than working with Camel’s SQL component – particularly when using dynamic SQL placeholders. We will come back to this topic later on (in the chapter “Struggling with the SQL Component”) but for now here is the custom bean:

public class SqlExecutor {
  ...

  public List> selectNewTransfers(String body, Exchange exchange) {
    final String transferType = exchange.getProperty(Constants.TRANSFER_TYPE, String.class);
    List> newTransfers =
        jdbcTemplate.queryForList(
            SELECT * FROM TRANSFER WHERE TRANSFER_TYPE = ? AND STATUS = ?",
            transferType,
            TransferStatus.NEW.name() );

    if (newTransfers.size() == 0) {
      log.debug("No '{}' {} transfers - STOP", TransferStatus.NEW, transferType);
      // STOP the routing by appropriately marking the Exchange (equals "" in XML DSL)
      exchange.setProperty(Exchange.ROUTE_STOP, Boolean.TRUE);
      return null;
    }
    log.info("Found {} '{}' {} transfers", new Object[]{ newTransfers.size(), TransferStatus.NEW, transferType });
    return newTransfers;
  }
}

The code should be pretty much straight forward. The bean uses an underlying Spring JdbcTemplate and all new transfers are returned as a List of Maps (with the SQL column names as keys). Until now this is the same behavior as the Camel SQL component. But then the handling of one of our processing definitions follows: don’t continue with the routing if there are no new transfers (see “if”-condition). In contrast, the SQL component would continue with an empty array which would have to be checked and reacted upon similarly in the Camel XML DSL.

Step 2: Preprocessing

After having all new transfers as a List in the Camel body, the route “Send.ProcessSelectedTransfers” is called. Within this route several great Camel features are used: the Splitter (see line 8 ) and the Validate DSL (see line 5 and 13-14).


  

  
  ${body} is 'java.util.List'

  
  
    
    ${body}

    
    ${body} is 'java.util.Map'
    ${body["REQUEST_XML"]} != null

    
    
      ${body["ID"]}
    

    
    
      ${body["REQUEST_XML"]}

Aside from the validations, the first thing to happen is the splitting of the List which the previously described “sqlExecutor” returned. Next, the ID is saved to a Camel property allowing the later correlation of the SOAP reply. Finally, the body is set to the payload XML as required by the (upcoming) CXF component.

Note that the Splitter was configured purposely to sequential processing and immediate stopping on Exceptions (see line 8). We decided against the use of Camel’s asynchronous processing to keep the routing as simple as possible. For example consider you have three transfers: A1, B1 and A2 with A2 being an update of A1. Now A1 fails due to a temporary network failure but B1 and A2 succeed. Furthermore let us define that all failures should be retried. Therefore A1 must either be discarded or A2 must be resend in order to prevent the older A1 to overwrite the newer A2. Discarding of A1 might become a problem if the receiving system requires every state of A being transferred. Resending all dependent states might make the routing logic more complicated. Howsoever, if A2 would not be send unless A1 was successful, additional routing logic would not have to be considered at all. Another example would be that A1 and A2 are sent shortly after each other but A1 gets e.g. delayed by network traffic and arrives a millisecond after A2. The receiving system would have to recognize the out-dated A1 and handle it appropriately. Eventually we felt that the price of a more complex failover behavior was too high for the small performance benefit of parallel processing.

Step 3: Sending via SOAP

Before the sending via SOAP happens, a final XML schema validation of the body containing the request XML happens:

This validation has the benefit of directly getting meaningful validation errors instead of generic SOAP faults from an external web service which you might have no or very little control over.

After the validation, the request XML is sent to the external web service with the help of Apache CXF which is a really simple one-liner:

Note that we configured CXF to build the SOAP envelope automatically, so we only have to bother with the important things, namely the payload XML. Here is the complete configuration of the CXF bean (belongs outside of the “” element):

Step 4: Result Processing

The previous CXF call from Step 3 returns the response XML payload from the external web service as Camel body. In our scenario, the response XML document contains a result code from the external web service like “INTERNAL_ERROR” or “SUCCEEDED“. In the final routing, this response XML is evaluated and saved to the database:

The custom bean “responseEvaluator” inspects the response XML and then decides what the ultimate transfer result should be. For example, we could ignore an “INTERNAL_ERROR” result and just send the transfer again and again, because it is most likely a bug in the external system which will be fixed sooner or later. Such a strategy would not need manual interaction to resume or resend a failed transfer and thus save effort. But regardless of the evaluation’s outcome, the responseEvaluator always sets a Camel property named TransferResult which will be used by the sqlExecutor bean.

The “sqlExecutor” saves both the response XML and the TransferResult in the database. The saving is once more executed with a Spring JdbcTemplate, similar to Step 2:

public class SqlExecutor {
  ... 

  public void insertTransferResult(final String transferResult, final Exchange exchange) {
    final String transferId = exchange.getProperty(Constants.TRANSFER_ID, String.class);
    Validate.notEmpty(transferId, "Camel Property '" + Constants.TRANSFER_ID + "' must not be empty!");
    Validate.notEmpty(transferId, "Parameter transferResult must not be empty!");

    int affectedRows = jdbcTemplate.update(
        "UPDATE TRANSFER SET STATUS = ? WHERE ID = ?", transferResult, transferId
    );

    Validate.isTrue(affectedRows == 1, "Not more or less than exactly one row should have been updated.");
  }
}

In case you wonder why we decided to use a bean as a response evaluator instead of a Camel “choice” statement: one of the main reasons was the beneficial syntax-checking of the Java compiler. The WSDL contains an XML schema and that schema is integrated with JAXB into the Cosmo Router by using JAXB’s XJC compiler to generate Java classes from the XML schema. As a result, XML schema changes like return-code renames (being an enumeration in the XSD) will immediately bring up compiler errors in the Java code. Another reason was readability: many “choice/when/otherwise” evaluations in the Camel XML DSL are more difficult to read than in Java.

This concludes the most important steps in the transfer processing. Of course we were only able to define this behavior because we had the luxury that neither the prevention of duplicate transfers nor high-throughput were very important. Nevertheless we achieved reliability, robustness, simplicity and last but not least project delivery on time.

Struggling with the SQL Component

As mentioned before in “Step 1″, Camel’s SQL component requires the data for dynamic placeholders to be delivered in the Camel body. Although this may make sense for integrating the SQL component into Camel’s way of processing, we felt the mandatory changing of the body to be cumbersome. This is fine if you don’t have a Camel body yet, e.g. when checking the database for new transfers. But it can become a headache when trying to save the response.

Imagine your Camel body contains a SOAP response and you want to save it together with a final result code like “SUCCESS” or “ERROR” in the database. You could use a Camel SQL statement like this:

UPDATE TRANSFER
  SET RESPONSE_XML = #, RESULT_CODE = #
  WHERE ID = #

But for multiple placeholders, the Camel SQL component requires the body to be an iterable array. Thus you need to convert the body with the SOAP response into an iterable array, supplemented with the result code and the ID to update.

Surprisingly we found no way to achieve this directly with the standard Camel XML DSL. So one idea was to write a custom Camel Type Converter which would parse a comma-separated body and split it into an iterable array:


  ...

  
    "${body}" ; "${property.TransferResult}" ; "${property.TransferId}"
  
  
  

  ...

Although this idea would work, it is of course more difficult to read and introduces new logic to test and new potential failure points like empty strings, null values, exceeded string lengths or unescaped quotation marks. Additionally, accessing the SOAP response once more after having it saved is difficult, too. Not only did you change the body to an iterable array but also the SQL component’s behavior is to “overwrite” the body with the number of updated rows! You could of course save the body to a Camel property before the SQL statement is executed. Or you could use Camel’s Multicast DSL to clone the original body with the SOAP response. But why do all this bending in the first place if you just want to execute a simple dynamic SQL statement with multiple placeholders? Well, our answer was simple: avoid the SQL component and just use a custom bean like the previously described “sqlExecutor” bean.

Fighting Doubts with Prototypes

The previously described architecture did not appear out of thin air but did undergo several iterations and prototypes. We especially wanted to collect early experiences in some crucial areas like using Apache CXF as JAX-WS implementation (we previously used Metro) and evaluating how good it integrates into Apache Camel.

Through early prototypes we quickly gained enough confidence in the chosen architecture. Additionally, we were able to start at once with the definition of most failure scenarios and consequently the optimal failover behavior we wanted the Cosmo Router to have. In fact, every time an unexpected failure occurred it was instantly checked against all previously defined failure scenarios and added, if necessary. The corresponding failover logic was implemented at once, too. Following this agile and pragmatic approach we soon achieved a robust messaging router which became better and better the more the implementation and testing went on.

If you are curious how we defined our failure scenarios and the required failover behavior of the Cosmo Router, then watch out for the next part of this blog series.

Experiences with ActiveMQ

Our first architectural draft was based on the idea to use ActiveMQ for exchanging messages between the Cosmo Web Application and the Cosmo Router. The idea was that the “TransferCreator” would insert transferable XML documents as JMS messages into the “Process Queue”. Thus we drafted the architecture shown in the following diagram:

Initial experimental architecture with ActiveMQ.

We built some prototypes around this idea but soon stumbled upon several issues. For example, we wanted both the Cosmo Router and the Cosmo Web Application to support non-availability. However, that would have been problematic in the above described architecture because the TransferCreator is attached to a user request. This user request should not have to wait if the Cosmo Router’s “Process Queue” is not available for several minutes or even hours.

So we came up with the solution to have two queues: one in the Cosmo Web Application and one in the Cosmo Router and both queues are communicating with each other. In ActiveMQ terminology this is called a “store and forward network of brokers“:

Improved experimental architecture with ActiveMQ using a "store and forward network of brokers" approach.

But again we had concerns with this idea as explained in the next chapter.

Why we didn’t choose ActiveMQ

Please consider once more our final architecture which favored a simple database over ActiveMQ:

Our final architecture for comparison as previously described at the beginning of the article.

We saw several benefits in using the transfer table approach as depicted above instead of ActiveMQ:

We didn’t require additional time to gain sufficient ActiveMQ knowledge. Although we were very interested in ActiveMQ, the project timeline was very tight and time was of the essence.
We didn’t have to introduce yet another framework. This was particularly important because the used development process was Scrum and by process definition everyone should be able to implement everything everywhere. Consequently the more frameworks are used, the higher the learning curve becomes.
We didn’t have to worry about transaction support. Unfortunately we didn’t achieve quick und solid results with transaction support. For example it stayed unclear how difficult it would be to integrate both ActiveMQ brokers into transactions while also keeping the Cosmo Router a lightweight stand-alone application.

Thus we finally decided that using a relational database would be absolutely sufficient for our requirements and much easier to setup, maintain and understand, although the use of ActiveMQ might be quite reasonable in more complex scenarios.

Conclusion

In this article we described how Camel can be used to transfer XML documents between SOAP web services. We have shown that the use of a transfer database and the use of synchronous transfer processing allowed us to keep the routing relatively simple and easy to understand. Yet different types can be transferred concurrently which increases the overall throughput and sufficiently reduces bottlenecks. Furthermore the Cosmo Web Application can create and dispatch transfers asynchronously and therefore will not block its users from working with it.

All this is achieved in a transactional way, meaning that as long as a transfer is not completely processed, it stays in a “NEW” state and is therefore tried to be send again and again. This adaptable retry behavior does not only greatly reduce the need for manual investigation and interaction. It has also the benefit that the Cosmo Router can resume from any state even after a sudden cold restart.

Last but not least, our pragmatic approach enabled us to deliver the application integration of mgm Cosmo with the external CRM system on time. Moreover, the asynchronous transfer creation and the highly automated retry strategies saved us effort when going live. We only required a short downtime and we needed no further interaction when several XML document transfers were failing a whole week.

(c) 2013 mgm technology partners. This posting "Designing and Implementing our Camel-based mgm Cosmo Router - Robust and Fail-Safe Message Routing with Apache Camel, Part 1" is part of the mgm technology blog. The author of the posting is Michael Frieß.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Tuning Garbage Collection for Mission-Critical Java Applications

Dr. Andreas Müller — Wed, 27 Mar 2013 11:18:00 +0000

I recently had the opportunity to test and tune the performance of several shop and portal applications built with Java and running on the Sun/Oracle JVM, among them some of the most visited in Germany. In many cases garbage collection is a key aspect of Java server performance. In the following article we take a look at the state-of-the-art advanced GC algorithms and important tuning options and compare them for diverse real-world scenarios.

Seen from the point of Garbage Collection, Java server applications have wide varying requirements:

Some are high-traffic applications serving a huge amount of requests and creating a huge amount of objects. Sometimes, moderate-traffic applications using wasteful software frameworks do the same thing. Anyway, cleaning up these objects in an efficient way is a challenge for the garbage collector.
Others have extremely long uptimes and require a constant quality of service during that uptime without slow degradation or the risk of sudden deterioration.
Some place tight limits on their user response times (as in the online gaming or betting area) which do not leave much room for extended GC pauses.

In many cases you will find a combination of several of these requirements with different priorities. Several of my sample shops and portals were very demanding with respect to point 1, one put extreme priority on point 2 but most applications are not extremely demanding in all of the three aspects at the same time. This leaves you the necessary room to choose the right tradeoffs.

Out-of-the-Box GC Performance

JVMs have improved a lot but still cannot do your job of optimizing the runtime for your application. Default JVM settings have a fourth priority in mind in addition to the 3 mentioned above: minimizing the memory footprint. They need to support millions of users who do not run Java on a server with plenty of memory. This is even true for many e-business products which are most of the time preconfigured to run on developer notebooks instead of production servers. As a consequence, if you run your server with a minimal set of heap and GC parameters like the following

java -Xmx1024m -XX:MaxPermSize=256m -cp Portal.jar my.portal.Portal

you will almost certainly obtain results which are not good enough for efficient server operation. In the first step, it is good practice to configure not only memory limits but also initial sizes to avoid costly step-by-step increases during server startup. Whenever you know how much memory is enough for your server (which you should try to find out in time) it is best to make initial sizes and limits equal by adding

-Xms1024m -XX:PermSize=256m

The last basic option frequently found in JVM configurations is a similar setting for the size of the so-called New generation heap:

-XX:NewSize=200m -XX:MaxNewSize=200m

These and other more sophisticated settings are explained in the next sections but let’s first look how the garbage collector works with them in a load test for one of our portal samples on a rather slow test server:

1. GC behavior of a JVM with little heap tuning (-Xms1024m -Xmx1024m -XX:NewSize=200m -XX:MaxNewSize=200m) over a period of about 25 hours (Click to enlarge).

The blue curve shows the occupied total heap as a function of time, vertical grey lines show the duration of GC pauses.

In addition to these graphs, key indicators of GC operation and performance are shown on the right-hand side. First we have a look at the average amount of garbage created (and collected) in this test run. The value of 30.5 MB/s is marked in yellow because it is a considerable but still moderate garbage creation rate, just about right for an introductory GC tuning example. Other values indicate how well the JVM copes with cleaning up that amount of garbage: 99.55% of that garbage is cleaned up in the New generation and only 0.45% in the Old generation which is rather good and therefore marked green.

Why this is good can be seen from the pauses the GC activity imposes on the JVM (and all the worker threads executing user requests): There are numerous and rather short New generation GC pauses. They occurred on average every 6 seconds and lasted less than 50 milliseconds. Such pauses stopped the JVM during 0.77% of wall time but any single pause is unnoticeable to the users waiting for the server’s response.

On the other hand, Old generation GC pauses stop the JVM during only 0.19% of time. But given the fact that during that time they only clean up 0.45% of the garbage while 99.55% is cleaned up during the 0.77% New generation pause time this shows how extremely inefficient Old generation garbage collection is compared to New generation GC. In addition, Old generation pauses on average occurred less than once per hour but lasted as much as almost 8 seconds on average with a single outlier even reaching 19 seconds. As these are true pauses for all the JVM’s threads processing user requests, they should be as infrequent and short as possible.

From these observations follows the basic tuning goal for generational garbage collection:

Collect as much garbage as possible already in New generation and make Old generation pauses as infrequent and short as possible.

Basic Ideas of Generational Garbage Collection and Heap Sizing

Start from what you see in a JDK tool like jstat or jvisualvm and its visualgc plugin:

2. The JVM heap structure including the sub-segments of the New generation (right column).

The Java heap is made up of the Perm, Old and New (sometimes called Young) generations. The New generation is further made up of Eden space where objects are created and Survivor spaces S0 and S1 where they are kept later for a limited number of New generation garbage collection cycles. If you want more details, you might want to read Sun/Oracle’s whitepaper “Memory Management in the Java HotSpot Virtual Machine”.

By default the New generation as a whole, and the survivor spaces in particular, are too small to hold objects long enough until most of them are no longer needed and can be collected. Therefore, they are moved to the Old generation prematurely which will then fill up too fast and need to be cleaned up frequently which causes relatively many of the Full GC stops visible in figure 1 above.

Tuning the Generation Sizes

Tuning generational GC means making the New generation as a whole and in particular the survivor spaces larger than they are out-of-the-box. But to do this you also have to consider the GC algorithm used:

The default GC algorithm of a Sun/Oracle JVM running on today’s hardware is called ParallelGC and if it were not the default it could be configured explicitly using the JVM parameter

-XX:+UseParallelGC

This algorithm by default does not work with fixed sizes for Eden and the survivor spaces but uses a policy called “AdaptiveSizePolicy”, which is an adjustment-controlled automatic sizing strategy. As described above, it delivers reasonable behavior for many scenarios including non-server usage but it is not optimal for server operation. To switch it off and start setting your survivor sizes explicitly to fixed values use the following JVM configuration switch:

-XX:-UseAdaptiveSizePolicy

Once this has been done, we can not only further increase the New generation but also effectively set the survivor sizes to a suitable value:

-XX:NewSize=400m -XX:MaxNewSize=400m -XX:SurvivorRatio=6

“SurvivorRatio=6” means that each survivor space is 1/6 of Eden size or 1/8 of total New generation size, which in this case means 50 MB while adaptive sizing usually works with much smaller sizes in the range of only a few MB. By repeating the same load test as above with these settings we got the following result:

3. GC behavior of a JVM with tuned heap sizes (-Xms1024m -Xmx1024m -XX:NewSize=400m -XX:MaxNewSize=400m -XX:-UseAdapativeSizePolicy -XX:SurvivorRatio=6) over a period of 50 hours.

Note that during this test run of doubled duration there was on average almost the same garbage creation rate as before (30.2 compared to 30.5 MB/s). Nevertheless, there were only two Old generation (Full) GC pauses, no more than one in 25 hours. This was achieved by decreasing the rate of garbage ending up in the Old generation (the so-called promotion rate) from 137 kB/s to 6 kB/s or only 0.02% of all garbage. At the same time New generation GC pause duration increased only slightly from an average of 48 to 57 milliseconds and the average interval between pauses rose from 6 to 10 seconds. Altogether, switching off adaptive sizing and fine tuning the heap sizes decreased GC pause time from 0.95% to 0.59% of elapsed time which is an excellent result.

Similar results after tuning can be obtained with the ParNew algorithm as an alternative to the default ParallelGC. It was developed for compatibility with the CMS algorithm mentioned below and can be configured by -XX:+UseParNewGC. It does not use adaptive sizing but works with fixed values for the survivor sizes. Therefore and with the default of SurvivorRatio=8 it usually delivers much better out-of-the-box results for server usage than the ParallelGC.

Getting rid of long Old Generation GC Pauses

The only remaining problem with the latest result above are the long Old generation (Full) GC pauses of about 8 seconds on average. These pauses have been made rare by proper generation tuning but when they occur they still are a nuisance to users because during their duration the JVM is not executing worker threads (stop-the-world GC). In our case, these 8 seconds are caused by an old and slow test server and could be up to a factor of 3 faster on modern hardware. On the other hand, today’s applications typically also use larger heaps than 1 GB and have larger amounts of live objects in the heap than in this example. Web applications nowadays work with heaps up to 64 GB and (at least temporarily) need half of that for their live objects. In such cases, 8 seconds is short for Old generation pauses. They can easily come close to one minute which is totally unacceptable for an interactive web application.

One option to alleviate the problem is the use of parallel processing for Old generation GC. By default, the ParallelGC and ParNew GC algorithms in Java 6 used multiple GC threads only for young generation collections while Old generation collections were single-threaded. In the case of the ParallelGC collector this can be changed by adding

-XX:+UseParallelOldGC

Since Java 7 this option is activated by default together with the -XX:+UseParallelGC. However, even with 4 or 8 cpu cores in your system you should not expect much more than an improvement by a factor of 2, often less. In some cases, as in our 8 seconds example above, this can be a welcome improvement but in other more extreme cases it is not enough. The solution is to use low-latency GC algorithms.

The Concurrent Mark and Sweep (CMS) Collector

The CMS garbage collector is the first and most-widely used low-latency collector. It has been available since Java 1.4.2 but suffered from instability issues in the beginning. Solving them required quite a few Java 5 releases.

As indicated by its name the CMS collector uses a concurrent approach where most of the work is done by a GC thread that runs concurrently with the worker threads processing user requests. A single normal Old generation stop-the-world GC run is split up into two much shorter stop-the-world pauses plus 5 concurrent phases where worker threads are allowed to go on with their work. Find a more detailed description of the CMS in the article “Java SE 6 HotSpot Virtual Machine Garbage Collection Tuning”.

The CMS collector is activated by

-XX:+UseConcMarkSweepGC

Applying this to our sample application from above (under higher load than before) led to the following result:

4. GC behavior of a JVM with tuned heap sizes and CMS (-Xms1200m -Xmx1200m -XX:NewSize=400m -XX:MaxNewSize=400m -XX:SurvivorRatio=6 -XX:+UseConcMarkSweepGC) over a period of 50 hours.

It is visible that the Old generation pauses in the 8 seconds range are now gone. For each Old generation collection (in our case 5 of them in 50 hours) there are now two pauses and all of them are below 1 second.

By default, the CMS collector uses the ParNew collector to execute the New generation collections. If the ParNew collector runs together with the CMS its pauses tend to be a bit longer than when it runs without it because their cooperation requires some extra effort. In addition to the slightly higher average New generation pause times compared to the previous results, this can be seen from the frequent outliers in New generation pause times which reach up to 0.5 seconds in the test run shown. But they are all short enough to make the CMS/ParNew collector pair a good low-latency option for many applications.

A more important disadvantage of the CMS collector is related to the fact that it cannot be started when the Old generation heap is full. Once the Old generation is full, it is too late for the CMS and it must then fall back to the usual stop-the-world strategy (announced by a “concurrent mode failure” in the GC log). To reach its low-latency goal the CMS is started whenever Old generation occupation reaches a threshold set by

-XX:CMSInitiatingOccupancyFraction=80

The CMS is started once 80% of the Old generation is occupied. For our application this reasonable value (which at the same time is also the default) worked well, but if the threshold is set too high a concurrent mode failure can any time bring back the long Old generation GC pauses. If on the other hand it is set too low (below the size of the live part of the heap) the CMS might run concurrently all the time and thus consume the processing power of one CPU entirely. If an application experiences brisk changes in its object creation and heap usage behavior, e.g. by the start of specialized tasks either interactively or by a timed trigger, it can be hard to set this threshold right to avoid both risks at all times.

The Specter of Fragmentation

The biggest disadvantage of the CMS, however, is related to the fact that it does not compact the Old generation heap. It therefore carries the risk of heap fragmentation and severe operations degradation over time. Two factors increase this risk: a tight Old generation heap and frequent CMS runs. The first factor can be improved by making the Old generation heap larger than what would be needed with the ParallelGC collector (which I did from 1024 to 1200 MB as can be seen in the previous figures). The second factor can be improved by proper generation sizing as described above. We actually saw how infrequent Old generation GC can be made by it. To demonstrate how essential it is to fine tune the generation sizes before switching to the CMS let’s have a look at what might happen if we do not follow this rule and apply the CMS directly to the little tuned heap of figure 1:

5. GC behavior and sudden degradation by fragmentation when the CMS is applied to the poorly tuned heap of figure 1 (GC indicators on the right from the first 14 hours only).

It is obvious that with these settings the JVM worked well for almost 14 hours under loadtest conditions (in production and with lower load this treacherously benign period may last much longer). Then suddenly there were very long GC pauses which actually stopped the JVM for about half of the remaining time. There were not only attempts to clean up the mess in the Old generation which lasted more than 10 seconds but even New generation GC pauses were in the seconds range because the collector spent a lot of time searching for space in the Old generation when it tried to promote objects from new to Old generation.

The fragmentation risk is the price to pay for the low-latency advantage of the CMS. This risk can be minimized but it is always there and it is hard to predict when it will strike. With proper GC tuning and monitoring, however, the risk can be managed.

The Promise of the Garbage First (G1) Collector

The G1 collector was designed to achieve low-latency behavior without the risk of heap fragmentation. As such, it is announced as a long-term replacement for the CMS collector by Oracle. G1 avoids the fragmentation risks because it is a compacting collector. As far as GC pauses are concerned, it does not aim at the shortest possible pauses but at controlling pauses by placing an upper limit on their duration which is maintained in a best-effort approach. Readers can find more details about the G1 collector in the great tutorial “Getting Started with the G1 Garbage Collector”, German readers also in Angelika Langer’s article “Der Garbage-First Garbage Collector (G1) – Übersicht über die Funktionalität”.

Before we examine the current state of the G1 collector by comparing its performance on our sample application with the performance of the classic collectors described above, let me summarize two important pieces of information about the G1 collector:

G1 is officially supported by Oracle since Java 7u4, but for G1 you should go for the most recent Java 7 update available. The Oracle GC team is working hard on G1 and improvements in recent Java updates (7u7 to 7u9) have been noticeable. On the other hand, G1 has been in no way production-ready in any Java 6 release and the by far superior Java 7 implementation will probably never be backported.
The generation sizing approach I described above is obsolete with G1. Setting generation sizes is in conflict with setting pause time targets and will prevent the G1 collector from doing what it was designed for. With G1 you set the overall memory size using “-Xms” and “-Xmx” and (optionally) a GC pause time target and usually leave all the rest to the G1 collector. It follows a similar approach as the ParallelGC collector’s AdapativeSizingPolicy and adjustment-controls the generation sizes in such a way as to fulfill the pause time target.

Once these guidelines were followed, the G1 collector delivered the following result out-of-the-box:

6. GC behavior of a JVM with G1 and minimal configuration (-Xms1024m -Xmx1024 -XX:+UseG1GC) over a period of 26 hours.

In this case, we used the default GC pause time target of 200 milliseconds. As can be seen from the indicators this target was almost met on average and the longest GC pauses were as good as with the CMS (figure 4). G1 apparently had very good control of GC pauses because outliers compared to the average duration were rather rare and limited.

On the other hand, average GC pause times were much longer than with the CMS collector (270 vs. 100ms) and because they were even more frequent this also means that accumulated GC pause time, i.e. the overhead for GC itself, was more than 4 times higher than with CMS (6,96 vs. 1.66% of elapsed time).

Just like the CMS the G1 works with GC pauses and with concurrent GC phases. In similar ways as the CMS, it starts concurrent phases based on an occupation threshold. It is visible in figure 6 that the available heap of 1GB is by far not fully used. This is because the G1’s default occupation threshold is much lower than the CMS’ threshold. It is also reported that the G1 in general tends to be satisfied with less heap than the other collectors.

Quantitative Comparison of Garbage Collectors

The following table summarizes some key performance indicators achieved with the 4 most important garbage collectors of Oracle Java 7 running the same load test on the same application but with different levels of load (indicated by the garbage creation rate shown in column 2):

Table with Comparison of several Garbage Collectors (Click to enlarge).

All the collectors were run with about 1GB of total heap size; the traditional collectors (ParallelGC, ParNewGC and CMS) in addition used the following heap settings:

-XX:NewSize=400m -XX:MaxNewSize=400m -XX:SurvivorRatio=6

while the G1 collector ran without additional heap size settings and used the default pause time target of 200 milliseconds which can also be set explicitly by

-XX:MaxGCPauseMillis=200

As can be seen from this table the traditional collectors execute New generation collections (column 3) in similar time. This is true for the ParallelGC and the ParNewGC collectors but also for the CMS which in fact uses the ParNewGC to execute New generation collections. Promotion from new to Old generation, however, requires some coordination between ParNewGC and CMS during New generation GC pauses. This coordination creates an extra cost which translates into slightly longer New generation pauses for the CMS.

Column 7 summarizes the time lost in GC pauses as percentage of elapsed time. This number is a good measure of GC overhead because concurrent GC time (last column) and the CPU usage overhead it implies may be neglected. With heap sizes tuned as described above and thus with rare Old generation collections, column 7 is largely dominated by New generation pause time. New generation pause time is the product of New generation pause duration (column 3) and New generation pause frequency. New generation pause frequency is a function of the New generation size which was the same (400 MB) for all of the traditional collectors. Therefore and for these collectors column 7 more or less mirrors column 3 (for similar load).

The benefit of the CMS collector in this picture is evident from column 6: it trades much (one order of magnitude) shorter Old generation GC pauses against a slightly higher overhead. For many real world applications this is a very good deal.

How well does the G1 collector compete for our application? Column 6 (and 5) tells us that it successfully competes with the CMS in reducing Old generation GC pauses. But column 7 indicates that it pays a rather high price to achieve this: GC overhead was 7% compared to 1.6% for the CMS under the same load.

I will examine the conditions under which this higher overhead occurs as well as the strengths and weaknesses of the G1 compared to other collectors (in particular to the CMS collector) in a follow-up to this article as it is a vast and newsworthy subject in its own right.

Summary and Outlook

For all the classic Java GC algorithms (SerialGC, ParallelGC, ParNewGC and CMS) generation sizing is an essential tuning and fine tuning procedure which in many real-world applications is not practiced sufficiently. The consequences are suboptimal application performance and the risk of operations degradation (loss of performance and even application standstill for extended periods of time if it is not well monitored).

Generation sizing can improve application performance noticeably and reduce the occurrence of long GC pauses to a minimum. Elimination of long GC pauses, however, requires the usage of a low-latency collector. The preferred and most proven low-latency collector has been (and still is as of today) the CMS collector which in many cases does what is needed and, with proper tuning, also provides long-term stability in spite of its inherent heap fragmentation risk. The intended replacement, the G1 collector, is now (as of Java 7u9) a supported and usable alternative but there is still room for improvement. For many applications, it will deliver acceptable but not yet better results than the CMS collector. The details of its strengths and weaknesses deserve closer examination.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Securing your Password Database with bcrypt

Dr. Christian Winkler — Fri, 08 Feb 2013 15:19:18 +0000

Do you also spend sleepless nights because you have saved the passwords of your users in clear text or near-clear text (MD5)? We will show you a simple method how you can smoothly migrate your password database to a much more secure format. The transition is transparent to the users and instant, i.e. as soon as you have implemented the process, your passwords are safe. If you still store your passwords in an insecure format, you should convert them to a secure format as soon as possible. Do it now!

Many online shops, forums or communities save their user passwords in either plaintext or MD5 hashed form for historical reasons. Passwords saved in plaintext are obviously a bad idea, but MD5 is not much better these days as modern graphics cards can create several hundred millions of MD5 hashes a second and passwords can easily be broken this way, e.g. by using the Lightning Hash Cracker. Suitable hardware can be rented at a very low price in the cloud, e.g. NVidia’s GPU Cloud Rendering or Amazon EC2, so the danger of exposing user passwords is increasing. Even institutions like the FBI still save their password in clear text, so there is no shame involved, but it’s something you should definitely change as soon as possible.

The usual method to change the hashing algorithm without asking users to modify their passwords is to convert the passwords to the new hash as soon as users log in. Our algorithm, however, instantly converts the database to a safe password format.

Who is not at risk?

You do not need to worry if you are already using a secure hashing algorithm with salts that are hard to break. SHA1 or SHA256 are more secure than MD5, but still not really safe. There is a multitude of hashing algorithms that are more computationally intensive and – due to their intrinsic salt – hard to beat using rainbow tables, the most prominent of which is bcrypt. More generic key derivation functions can also be used for one-way encrypting passwords, a good candidate is e.g. PBKDF2. There are intensive ongoing discussions which algorithm is theoretically superior, but these are, in our opinion, not directly relevant as both seem to be secure enough for a long time being.

A Web App uses a database to persist the users' passwords. The red methods for saving passwords can easily be "inverted" if the database is compromised whereas the blue algorithms are safe today and probably for a few more years.

Some background

Let’s first discuss how an attacker actually gets hold of a database. Passwords (or their hashed versions) are often stored in relational databases. The by far most common attack to get a copy of the database (or individual rows) is a technique called SQL injection. URL parameters or POST parameters of a web page are manipulated to contain malicious characters which are interpreted by the SQL database. Of course not all web sites are susceptible to SQL injection but it is very hard to prove that a web site is invulnerable.

Security vulnerabilities are also a permanent danger. Security leaks might exist in some server software, operating system kernels or even in the database system itself. Such leaks are traded on the Internet in order to abuse them.

You should never underestimate internal attacks. Often databases are accessible from the inside and passwords can readily be found in the source code or server configuration. This makes it easy for employees to get hold of all data and analyze it after it has been saved to a local disk or even transferred to an external medium.

Backups are often performed in data centers and it is not always safe to assume that these backups are treated as confidentially as the servers themselves. Often backup tapes are reused or even disposed; this sometimes leads to interesting finds including old databases. Remember that users tend to change their passwords very infrequently if not forced; so even very old passwords have a high chance to still be working (maybe also on other sites).

The same is basically true for old hard disks. However, hard disks are often changed routinely and the old disks are then sold on used hardware wholesale sites. If you cannot absolutely trust your hosting provider (and who can?) you should take into account that your password database might sometime also go this way.

Different possibilities how an attacker can get hold of the (encrypted) passwords.

How Hashing works

One way to protect the password itself is to not save it at all, but to just save a “fingerprint” of the password instead. If a password is entered, it is enough to calculate the fingerprint of the entered password and compare it to the saved fingerprint. This fingerprinting technique is called “hashing“. There are of course more formal explanations of hashing, but for our discussion it is not necessary to understand it on the deepest level. The most important aspect for us is the use of a cryptographic hash function that ensures that small changes in the original text lead to completely different hashes.

To make fingerprints different for users even if their passwords are the same, an additional (random) value is combined with the password before it is hashed. This value is called “salt” and is also added to the hash to calculate the fingerprint from the entered password correctly using this hash. It is obviously much safer to store the salt in a different place but for our discussion this just complicates matters and therefore we ignore this. Sometimes the algorithm is modified further by adding a “secret”, which is only known to the application, to the password as well before it is hashed. This slightly enhances security if the secret is well-chosen.

There is a variety of hashing algorithms; the most famous ones are MD5 and SHA1. Both were however created in former times and optimized for the calculation of hashes with high performance. This makes them not very well suited for storing passwords as we will see below.

A hash is a one-way function which can calculate fingerprints from passwords. However, it cannot be inverted. So as in real life you cannot find a person by his/her fingerprints; to check the whether the fingerprint belongs to a specific person you have to ask the person for the fingerprint.

How hashed Passwords can be broken

Unfortunately, not all is safe even when passwords are hashed. If an attacker gets hold of the (hashed) password database, there are several ways of how this database can be broken. We concentrate on the most famous ones:

Dictionary attacks: Dictionary attacks make use of the fact that most passwords are words which are also found in a dictionary. The attacker then takes a dictionary (usually one which is specifically designed for cracking passwords) and tries to hash each word in the dictionary and compares the result to the hashed version of the passwords. The tools used for dictionary attacks, like “John the Ripper” have become quite sophisticated and perform all kind of permutations and obvious replacements (like “I” ⇔ “1″ and “E” ⇔ “3″ etc.)Of course this only works if the hashing algorithm is known and the position of the salt can be extracted. This can usually be accomplished quite easily if the attacker creates a login for him/herself before stealing the password database.
Brute force attacks: These attacks are a simpler version of the dictionary attacks. Instead of using a dictionary, all conceivable combinations of characters are created and hashed. Of course the short-term success rate is lower as most users will have passwords which are in a dictionary. However, this method will find all passwords if given enough time and not only passwords which are found in a dictionary.
Rainbow tables: Rainbow tables are precomputed tables that contain hash values for many, many passwords. As specific weaknesses of the hashing algorithm can be taken into account, the size of the table can shrink considerably. Obviously rainbow tables work best when no salt is included in the passwords. Then this method is very efficient and can break a few million passwords a day on decent hardware.

All these methods are dangerous, as computing power has exploded in the last few years. Both generating and checking passwords can be done with a rate of several hundred million passwords a second if common graphics cards and outdated, unsuited algorithms like MD5 or SHA1 are used. It’s naïve to assume this kind of hashing already makes the passwords secure.

Not convinced that this works? We have created the hash 2257151269b83ef0e139c3eec8bbcbcb from a password, so head over to www.md5decrypt.org and try to find the original password. Even search engines carry some of the most popular hashes today.

To create a secure storage of passwords, a more complicated algorithm has to be used. Bcrypt is an algorithm which is specifically designed for this purpose and will be complicated enough to last for several years. bcrypt was specifically designed for adjustable complexity by increasing the number of cycles. Both bcrypt and PBKDF2 take several orders of magnitude longer to calculate than MD5 / SHA1, which is a bit cumbersome if you expect mass logins, but on the other side makes it impossible to crack the password database by using brute force techniques. By adjusting this “work factor” the algorithms will be safe for a long time to come. For a more detailed discussion regarding complexity see article “How To Safely Store A Password“.

Our Conversion Process

Let’s assume that we already have a password database with a significant amount of users. The passwords are hashed with a hashing function hash(cleartext), where hash can be e.g. MD5, SHA-1 or in the most simple case a function just returning the cleartext (in which case the passwords are stored unencrypted).

The challenge

As described above and in the bcrypt Wikipedia page, one of the advantages of bcrypt is its complexity. So it takes time to compute the hash value from the original. This makes the algorithm hard to attack but also poses some problems when converting many values at once as we have to make sure that no concurrent access is modifying the password at the same time (i.e.. a user trying to change his/her password at the same time).

We have to ensure that no password change is lost and no user will be denied login during the whole conversion process.
There are some additional complexities related to the different ways a password was saved before the change; these will be explained individually below.

Prerequisites

As a first step the software has to be made aware of bcrypted passwords. This of course makes it necessary to save bcrypted passwords and check against these saved versions. As the transition cannot be performed for all users at once, it makes sense to introduce a new column in the database first to host these bcrypted passwords. Alternatively, we could also have a Boolean column which tells us whether the password is still saved in the old representation or is already bcrypted. The choice is up to you.

In the next step, the software itself has to be adapted. It has to be aware of the two password formats, must be able to check entered passwords against both formats and be able to write changed passwords in the new format. This software will still be fully functional even if not a single password has been converted to the new format.

Algorithm for Changing Passwords

In the first step the procedure for changing passwords should check whether the row is already locked. This is a good idea as it is possible (though very unlikely) that a user opened multiple windows and is trying to change the password in all of them.

In the next step, the idea is to exclusively lock the row of the current user first, to then read the original (maybe already hashed) password, bcrypt it, write it back, delete the original password, finish the transaction and release the lock. It is essential that all this is performed within a single transaction. This ensures that no password change gets lost and users will be able to log in to the system using their old (and new) passwords without interruption (or only a very small delay if a user whose password is about to be converted tries to log in simultaneously).

Activity diagram for changing the password to a bcrypted version of the password.

Algorithm for Verifying Passwords

To avoid concurrency problems due to passwords just being converted, the conversion algorithm will perform the necessary change in one single transaction, so the verification does not have to concern itself with it. If the password is in bcrypt format, only this value should be used to check the password. The bcrypt value already contains some meta information like salt and number of iterations, so verification is as simple as

Bcrypt.check(hash(enteredPassword), storedBcryptHash)

If the password has not yet been converted the previously used algorithm should take over.
In the other cases below we concentrate only on the verification of the bcrypted password, while the old password is gracefully handled by the old password checking algorithm.

Handling clear-text Passwords

Converting clear text passwords is straightforward. In each step, the row is locked, the unencrypted password from each row taken, bcrypted and saved to the new column.

Verifying the password is similar; depending on whether it has already been bcrypted or not, the clear text or the bcrypted password is used to check against the entered password.

Handling unsalted MD5 passwords

As MD5 cannot be easily inverted (unless you attack the database yourself) it is much simpler to use the MD5 hashed password as a starting point and during conversion just bcrypt that value into a new column.

Verification is a bit more complicated, because the entered password must be MD5 hashed and that hash then be checked against the bcrypted column in the database.

Handling salted MD5 passwords

The conversion procedure is more complicated if MD5 passwords with salt are used. To re-create the salted MD5 hash, the salt has to be separated in a first step and should be kept in an extra column in the database. After doing that, the conversion procedure is identical to the one described above, i.e. the salted MD5 hash will be bcrypted.

Checking an entered password is also a bit more complicated. First the correct salt must be selected from the database, the entered password must be MD5 hashed with this salt and finally this value will be checked with the bcrypt algorithm. Checking in this case works with:

Bcrypt.check(MD5(salt + enteredPassword), storedBcryptPassword)

Converting to a “pure” bcrypt database

Storing the bcrypt’ed version of an already (via e.g. MD5) hashed password is not as secure as storing the password directly with bcrypt, as some of the entropy is eaten up by the original hashing algorithm. However it is still tremendously more secure than storing the password trivially hashed or in clear text.

If you started with an MD5 password database and are now unhappy about the “mixed” hashes in your database, there is also a solution for this. You have to use a flag column which indicates that the passwords are in the double-hashed intermediate format. As soon as a user successfully logs in you know the correct password and can save a pure bcrypted version in the database. Of course you still have to change the flag so that your future password verifications only use bcrypt.

This procedure is also non-intrusive but will never catch all users. If you want to get rid of those “mixed” users completely, you either have to force them to log in or reset their passwords. If they have not logged in for a long time, chances are high that they have forgotten their passwords anyway.

Passwords can be converted incrementally to a "pure" bcrypt format.

Conclusion

After performing the steps described above your users’ passwords will be instantly safe. Now even if the password database is compromised, hackers will have a hard time figuring out the passwords. The process is easy and straightforward as we reuse the already existing passwords and make the process transparent for the users.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

On the Quality Benefits of Formal Domain Specific Languages - Software Quality driven by Formal DSLs, Part 2

Dr. Jürgen Knopp — Sat, 12 Jan 2013 13:40:47 +0000

One of the assets of mgm is dedicated quality for software, including especially portal technology for applications with high-safety and reliance demands. In the first blog within this series, “Using Domain Specific Languages to Implement Interactive Frontends“, we described an approach using a specification language (DSL) family on customer level to specify valid inputs and frontend computations for forms-based interactive or batch systems. Let us continue and focus on the quality benefits of this approach.

The presented specification language family supports modeling of frontends, such as form-based user interfaces, or field-related batch programs that e.g. process XML input.

In a nutshell, the approach is characterized by formal specifications for well-defined and valid field inputs, computation of values for calculated fields and of relationships between these fields. For an example see the summary at the end of part “Using Domain Specific Languages to Implement Interactive Frontends“.

The specification means are as follows:

All fields are typed as numbers, currencies, percentage types, plain text, or enumerations, etc. For some of these types, additional constraints can be expressed, such as minimum and maximum values, field lengths or regular expression restrictions.
Calculated fields have functional dependencies describing value dependencies on values of other fields by means of functional rules.
Constraint rules describe cross-field relationships between fields. Error messages describing the non-compliance of inputs to these rules are part of the specification.

Both, constraint rules and functional rules, aside from referring to values for fields, allow the expression of different behavior dependent on existent or missing values for input fields.

Such specifications automatically lead to control for the specified system:

Field value are computed according to functional rules.
Constraints on and between fields lead to automatic validation:

Type errors are flagged with corresponding messages.
For constraint rules, the specified error messages are issued, if constraints do not hold.

The specification languages are tailored to the application domain (DSL). Therefore specifications can be (and indeed are) written by customers rather than by programmers.

Practical Quality Benefits for Specifications

Let us discuss how the formal language approach supports development, quality and test.

Avoiding implementation errors by code generation

Similarly to programming languages, specification languages substantially simplify the software development process. Code generated from specifications eliminates a great deal of complexity and leads to less error-prone systems. Here’s how code can be generated:

Functional rules are simply compiled to fully operational code.
Field type definitions and cross-field constraints are translated to validation code performing checks and delivering adequate error messages.

At mgm tp, code generators have been implemented for a variety of languages including Java, C++, Javascript and different runtime environments. The generator approach yields a high-quality gain. Once the code generators are well tested, there is not much need to test validation software for each case again. The generated code conforms to the specification.

Generating Test Data from Specifications

Formal specifications substantially facilitate and improve the quality-assurance process, especially testing. Since constraints and dependencies define the set of correct inputs, they are an ideal prerequisite for the generation of test suites. This includes both, consistent (valid inputs) and inconsistent data (deliberately invalid inputs). Generation of test data is discussed in more detail later in this blog series.

Finding Specification Errors

Translating specifications to code and especially to test data improves quality of the specifications, because it shows flaws allowing for an early feedback to the writers of specifications. Inconsistent and sometimes even incomplete specifications can easily be discovered:

Inconsistent specifications lead to contradictions and thus inhibit valid test data generation. This can be detected already at test data generation time.
Incomplete specifications give too much freedom to test data generation. Since “too much freedom” cannot be decided upon statically and automatically, this will show up only later in the process. In most cases such specification errors are reported in the testing phase.

Improving the Processes

Additionally to the above technical benefits, this formalized approach improves the requirement, development, and quality processes as follows:

Formalization of requirements in the user’s domain enforces the analysis of well-known and less well-known informal requirements. In other words, the likelihood that the system does what the customer explicitly or implicitly expected increases.
The differentiation between input validity and business logic modularizes the requirement process and thus substantially improves the latter.
The early availability of validity checks allows early feedback to specification writers.
Early availability of code and test data generation improves testing for front- and backends.

Quality Assurance Methods for Formal Specifications

The aspects mentioned above already substantially improve software quality without any dedicated quality measure. Still, quality assurance, especially testing is needed to deliver software with the behavior the customer expects. Fortunately, even testing becomes simpler, more reliable, adaptable, and measureable, due to the usage of formal specifications. How this is being accomplished is described in the rest of this blog.

Formal specifications facilitate well-defined structuring of tests and a focus on more interesting testing aspects. To explain these aspects we refer to typical system aspects (for both, single and multi-tier architectures) in the following table:

	Aspect	How is it done in our framework?
1.1	Validation of inputs, Valid cases	By generated software that has to be called by the application. After the check input data is known to be consistent.
1.2	Validation of inputs, Invalid cases	By generated software that has to be called by the application. The input data has to be flagged by the system with differentiated error messages.
2	Frontend computations	By generated software that has to be called by the application.
3	Generation of artifacts for backend processing	By generated software that has to be called by a web application. This is not further discussed this blog.
4	Backend behavior	Implemented by other means. Subject to extensive testing triggered by the frontend using valid input data controlled by 1) and 2).

The aspects 1.1, 1.2, 2 and 3 can be tested using automatically generated data: valid (and deliberately invalid) test data for functional tests can be generated using methods described below.

Extensive testing is needed for back end behavior (see 4). This needs to be done for valid data only. And the backend data needed can be automatically generated from the formal frontend specifications.

Automated testing

Automated functional testing for both, newly developed software and for regression purposes is a must for the kind of systems considered here. This not only reduces the amount of manual testing for each delivery, but also is more reliable regarding testing errors and permits to increase the test coverage.

It is beyond the scope of this blog to describe the overall test process. We merely mention two aspects for automated testing: test data, and test paths – the sequence of input processing. These aspects are dealt with separately.

Test data: Test data generation allows to pre-compute test cases by defining various values for input fields. Formal specifications allow the definition of test coverage measures for test cases related to these field values.
Test paths: The same test data sets are being fed into interactive system in different order including multiple inputs, i.e. editing of fields. The term used here is path. A path describes the order of processing, including multiple visits of forms and editing of fields. Within a path, pre-computed test data (as described above) can be used to as input to the system and thus test its behavior.

Test paths and test data are orthogonal aspects which complement each other as described below.

Field value based test data generation

Is there a way to generate all valid test cases for field values? For formal systems described above, the number of input fields, their types, and constraints are well known. Moreover, the number of values per field is finite and so is the number of fields. Thus, at least in principle, the set of all valid test cases is enumerable by enumerating field values and combinations of all values for all fields. Invalid field value combinations – according to constraints – can be automatically excluded from this enumeration.

In theory, this means that all possible input-driven test cases can be generated for the purpose of testing. In practice, however, this finite number is far too large: Without constraints between fields, the overall number of test cases is really huge: it is equal to a product of n factors where n is the number of fields. For each field the factor is defined by the number of valid field values.

Constraints reduce the number of legal inputs but the data variety is still too high. Thus, we must substantially reduce the set of test cases while trying to keep “good” test coverage.

There are two independent and compatible ingredients to reduce the number of test cases:

We reduce the number of different values considered for fields, and focus on fewer but preferably more ”interesting” values.
We reduce the number of combinations of different values for different fields: Rather than considering all combinations, the set of all values for all fields is considered. The number of test cases is reduced to the number of different values for the field with highest number of different values. Sometimes, constraints lead to a reduction or growth of this number.

Both techniques, considered together, substantially reduce the number of test cases.

Let us now analyze what “interesting” means. Certainly the criterion is the likeliness to find errors and to prove correctness using the resulting test data. We describe that in two steps.

Special and interesting values for types

The first step is to define special (“interesting”) values for specific field types. Test cases using these shall primarily be considered:

Special values such as min or max for numbers, currencies and several related types.
Special values such as zero, non-zero, hazardous characters, empty or very large strings, etc.
For enumeration fields, potentially all values are important, since enumeration fields often control business logic ramifications (e.g. in interactive systems, enumerations are often represented by drop down boxes for selecting important choices).

Obviously, this method has limitations. No knowledge about rules is used here. Hence incomplete business logic is applied. Moreover, some types — even enumerations — are sometimes too “large”, i.e. they have many values, and not all of them might really be “interesting” in the application domain. Nevertheless, considering special values depending on field types is a good basis for the techniques described below.

Special and interesting values for specific fields

Considering individual fields rather than types, interesting values can be selected more specifically. The most important information stems from rules (both functional and constraints):

Each comparison with respect to equality of a field value with a specific constant generates an interesting value equal to the constant. These values come on top of the interesting values defined by the field types. The fact that they have impact on business logic is reflected here.
Each comparison with respect to equality of a field with another field implies that the interesting value set of these fields are shared.

Field value coverage of test data generation

The main idea with respect to test coverage for test data generation algorithms is this:

For each interesting value of each field generate at least one occurrence within the test data.
Extend data sets applying all constraints to obtain fields with mutually consistent values.
Extend data sets by generating random or interesting values for unconstrained fields.

Note that in most cases the constraints do not allow the full variety of 1), since constraint rules usually will exclude some values for specific fields. As an example, consider the following constraint rule, which is taken from the prevous blog article “Using Domain Specific Languages to Implement Interactive Frontends“:

   AlternativeVat == 0
   or AlternativeVat == NormalVat
   or AlternativeVat == NormalVat/2
   => failed: "VAT can only be normal, half normal or zero"

The interesting values for AlternativeVat are NormalVat, zero and NormalVat/2, and “undefined” (the latter stands for: no value has been specified). These interesting values are propagated to all dependent fields, thus producing more interesting values for test data. This can be demonstrated for the following specification snippet.

AllVat = If FieldValueSpecified(AlternativeVat)
            then  AlternativeVat/100*NetAmount
            else  NormalVat/100*NetAmount

For the field AllVat the interesting values are (see if clause) NormalVat*100*NetAmount, zero, NormalVat/2*100*NetAmount and (see else clause) NormalVat/100*NetAmount. 

This description of test data generation is by no means complete; here we merely intended to show the relationship to interesting values. For more information, especially on algorithms (in an earlier language setting), see the blog articles “Producing High-Quality Test Data” and “Form Validation with Rule Bases“.

Multiplicity of Fields

A specific testing aim refers to multiplicity, i.e. to multiple occurrences of fields in forms (such as personal data for several people). In the first blog this concept has been explained and exemplified. The following snippet shows rules for multiplicity fields PosFullPrice, UnitPrice, and Quantity.

NetAmount         = Sum(PosFullPrice.all)
PosFullPrice.each = UnitPrice.each * Quantity.each

The number of instances of fields with multiplicity can be defined in advance in order to cover implementation errors occurring in this context. In our experience in most cases generating test data for a multiplicity of 3 suffices to find hidden bugs. In the above example above, three instances of PosFullPrice, UnitPrice, and Quantity are generated. They are fed into the algorithm for enumeration of test data. If a specific multiplicity index is referred to in constraint rules, this multiplicity automatically delivers interesting values (similarly to fields with no multiplicity as shown above). For scaling tests and performance tests, specific fields are selectively be set to a very high multiplicity.

Path Aspects: Considering Order of Field Editing in Tests

At mgm tp, the second automation aspect — the order of editing fields — is pursued with two approaches. Both are independent of test data. Data is simply provided from pre-computed test data sets as described in the previous chapters.

Controlled random testing

One method covering path dependencies consists in using randomly generated contexts. More explicitly controlled random testing (see, e.g. the presentation “Testing for the Unexpected“) increases the likelihood that “interesting” paths/value combinations are found by chance, since both, values and paths, are addressed in parallel. Once interesting contexts are found, by test failure, one can focus further testing around the contexts found.

Explicit testing paths

In contrast to controlled random testing, explicit testing paths specify evaluation orders (interactive forms visits and field assignments). Several strategies such as multiple visits with value reassignments or with cancelations can be configured. The visiting strategy is specified in advance, depending on quality aims of the customers. Random testing is just a special case which can be specified in our test driver infrastructure.

Semantic Test Coverage using adaptable Testing Aims

From the testing perspective, the greatest advantage of using formal specifications is the fact that the set of valid fields and field combinations is very well defined, and it is defined at the customer level. This enables the techniques discussed above. Furthermore, one can profit from the fact that customers possess knowledge about important and less important domain related aspects.

This permits a deviation from the pre-computed aims in terms related to the domain rather than to technology It bridges from the customer domain to technology (semantics beats automatics).

Sometimes interesting values, such as enumerations, have no impact on program ramifications, and in addition have many values which have similar semantics, with the exception of some specific ones – which can be derived from the domain knowledge.
Important cases may neither be modeled by enumerations nor explicitly be visible in constraint rules. In these cases non-formalized domain knowledge might be fed into the set of interesting values for specific fields.
By analogy, the need for multiplicity tests for specific fields might better be decided upon by persons with domain knowledge rather than taking defaults or algorithmic artifacts.
In some cases invalid data are of interest in order to test reactions on invalid inputs. If this requested, it can be achieved simply by generating test data based on rule sets which contain deliberate negations of specific constraints.
Explicit testing paths are set to useful defaults, sometime even including controlled random testing.

The overall method starts from formal specifications and combines domain expert knowledge with automated testing (see the illustration for an overview):

Automatically derive testing aims from specifications and store them in a default configuration.
Let these aims be analyzed by experts with domain knowledge, and adapt the testing aim configuration. This leads to an increase of a reduction of the size of the data set as described in a) to e)
Generate test data starting from an adapted test aim configuration for field values. Within this step specification flaws (e.g. contradicting rules) are being reported.
Perform tests with the generated test data while considering path configurations proven useful in former tests. Within this step any insufficient test coverage (in most cases due to incomplete specifications) is being reported.

Illustration of the method for adaptation of testing aims.

In conclusion, the adaptation of testing aims is a tool-supported manual process which fits well to test data generation and automated testing.

Conclusions

In this blog series we have shown that, in several respects, formal specification languages can be used to deliver high quality software systems. Since specifications are being provided at the comprehension level of the customer, we obtain a high likelihood that the system does, what the customer intended. In particular, we gain high quality due to…

automatic code generation,
well defined automatic test data generation,
and measurable test coverage adaptable testing aims,
fast turnarounds in the presence of requirement changes,
backends guarded by benign frontends, and
backends with well-defined test coverage based on frontend testing aims.

In addition to these implementation and quality assurance benefits, the interaction with the customer is improved as well. Early feedback with respect to errors, inconstancies, and incompleteness in specifications are possible, thus improving the requirement analysis process as well.

(c) 2013 mgm technology partners. This posting "On the Quality Benefits of Formal Domain Specific Languages - Software Quality driven by Formal DSLs, Part 2" is part of the mgm technology blog. The author of the posting is Dr. Jürgen Knopp.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Mobile Dashboard Reporting powered by JAX-RS and Highcharts

Jan Esser — Fri, 04 Jan 2013 15:20:04 +0000

When we developed this sales reporting solution for the insurance sector, we went for a mobile, browser-based dashboard that renders the reports on the client-side and thus enable a high degree of interactivity. That means that once the reporting data is delivered, the client should be able to e.g. drill down into the data or slide along the time axis. This article focuses on the technical aspects of the data delivery in JSON format and interactive charting in the browser.

The basic idea was to develop a data bridge which receives the reporting data from the server side and provide it conveniently for consumption on the client side. The data is delivered on-demand to the HTML single-page application using AJAX to load JSON documents. This gives us very high flexibility (as we will see) and is in contrast to the conventional mixing of data into HTML pages that happens on the server side (think of JSP/ASP.NET).

In our approach, the server is solely responsible for providing a data API (e.g. with support for time-sliced queries) and for delivering the data in the universal JSON format, i.e. it encodes data as code that can be interpreted by a broad range of different client platforms. This reduces the complexity of the server application by leaving the interpretation and visualization to the client application of the solution. The actual display of the data may even differ between the clients like desktop, browser or mobile applications.

The present browser application is based on Highcharts and jQuery. We chose Highcharts since it’s a mature JavaScript charting framework.

Screenshot a of sample Sales Mobile Dashboard.

Providing Reporting Data to the Browser via JAX-RS

Reporting data is known to have a multidimensional nature, while practically reports (in the ROLAP flavor) tend to have several views or perspectives cutting the data cube. Additionally reporting data is time-sliced. For instance, the report data of 2001 is not going to change anymore. This is a perfect situation for caching, for instance in HTML5’s Web Storage or a mobile browser’s database. Furthermore the time-slicing allows querying for distinct portions of the reporting data. Dividing the load leads to achieving an acceptable response time (in opposite to mobile data warehouses).

The choice for the protocol to provide and consume the report data was easy, since HTTP is the most familiar protocol to browsers. The strong points of that decision came up later, when all pieces of that puzzle fit together.

Applying a resource-oriented approach first requires some simple addressability, which will ease the clients to formulate follow-up-requests. Next a collection of resource representations needs to be defined. For the given setup it was evident to focus on JSON. The listing below shows the key part of the JAX-RS bean serving the report data in JSON format using the Jackson JSON processor.

// JAX-RS Resource bean
public abstract class ReportingResource {
	...
	@GET
	@Produces(MediaType.APPLICATION_JSON)
	public final Response getReportData(
        @HeaderParam(DATE_FROM_HEADER) final Date dateFrom,
		@HeaderParam(DATE_UNTIL_HEADER) final Date dateUntil,
        @Context final HttpHeaders httpHeaders,
		@Context final SecurityContext securityContext)
	{
		// require authentication and a certain user role
		if (securityContext.getUserPrincipal() == null
            || !securityContext.isUserInRole(REQUIRED_USER_ROLE))
        {
			return Response.status(Status.UNAUTHORIZED).build();
		}

		return Response.ok(
		    getReportDataInDateRange(dateFrom, dateUntil, httpHeaders))
		    .build();
	}
	...
}

The Data-as-Code Approach using JSON

The principle data-as-code applies here, as seen in the next listing: JSON is a data format and at the same time part of the JavaScript language specification. Furthermore it demonstrates the memory model of JavaScript-runtime-environments.

{
  "data": [
    {
      "lobNames": [
        "LIABILITY_POLICY_PREMIUM",
        "LIABILITY_OFFER_PREMIUM"
      ],
      "currency": "EUR",
      "periodBegin": "2012-08-01",
      "name": "PremiumLobTimelineTimeslice",
      "LIABILITY_POLICY_PREMIUM": 1461812,
      "LIABILITY_OFFER_PREMIUM": 0
    },
    {
      "lobNames": [
        "LIABILITY_POLICY_PREMIUM",
        "LIABILITY_OFFER_PREMIUM",
        "PROPERTY_OFFER_PREMIUM",
        "PROPERTY_POLICY_PREMIUM"
      ],
      "currency": "EUR",
      "periodBegin": "2012-09-01",
      "name": "PremiumLobTimelineTimeslice",
      "LIABILITY_POLICY_PREMIUM": 1081483,
      "LIABILITY_OFFER_PREMIUM": 129314,
      "PROPERTY_OFFER_PREMIUM": 1240473,
      "PROPERTY_POLICY_PREMIUM": 61074854
    }
  ]
}

We use jQuery Ajax requests to asynchronously fetch specific data from server REST/JAX-RS resources that follow the mentioned addressability rules. The data is basically fetched in time-slices, as seen in the listing below (dateFrom and dateUntil). We can restrict the data exchange to just those portions of the report data, which are of current interest to the user.

// Excerpt from Reporting.js
reporting.Reporting = {
	/* ... */
loadData : function(reportType, noCache) {
		/* ... */
		var headerParams = {
		'dateFrom' : reporting.utils.DateNavigator.getStartDate(),
		'dateUntil': reporting.utils.DateNavigator.getEndDate()
		};
		jQuery.ajax({
			url : url,
			dataType : 'json',
			cache : !noCache,
			async : false,
			headers : headerParams,
			success : onSuccess,
			error : onError
		});
		return resultData;
	}
	/* ... */
}

Rendering Data Charts in the Browser

Regarding the JSON structure Highcharts has so-called formatters, like yAxis.labels.formatter, that allow easy access to row-wise reporting data. The minimum requirement is to have an ordered JSON array below data (see listing above). In some edge cases (as in the subsequent listing) it is also possible to re-group the reporting data, so that it fits e.g. for a stacked bar chart like in this example.

// Highcharts configuration
renderChartConfig : function(data) {
	// values for xAxis
	var categories = [];
	// stack of lob (line of business) totals
	var series = [];

	//...

	for ( var i = 0; i < data.length; i++) {
		categories[i] = Highcharts.dateFormat(
				'%b %y', reporting.utils.DateUtil.parseUtcMillis(data[i].periodBegin));
		// series[j].data[i] = data[i][lobName];
	}

	var config = {
		// ...
		xAxis : {
			categories : categories,
			// ...
		},
		yAxis : {
			labels : {
				formatter : function() {
					return Highcharts.numberFormat(
							this.value, 0, '.', ',') + ' €';
				}
			},
		},
		legend : {
			labelFormatter : function() {
				return this.name;
			},
		},
		tooltip : {
			formatter : function() {
				return '' + this.x + ''
					+'
' + this.series.name + ': '
					+ Highcharts.numberFormat(this.y, 0, '.', ',') + '
'
					+ 'Total: ' + Highcharts.numberFormat(
							this.point.stackTotal, 0, '.', ',');
			}
		},
		series : series
	};
	return config;
}

Conclusion

Realizing the server side with JAX-RS and JSON marshalling resulted in a modular and extensible solution. Since reporting needs to have a vital dynamic over time, it should be possible to create a new perspective or view (on the data cube) in no time.

This is achieved by decoupling the client application’s use of the data from the server and its internals of how to provide the data. In other terms, providing data does not mean to know how it will be interpreted. The complexity of browsers and client diversity mentioned above can be moved to the JavaScript frameworks and so away from the server-side.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

How KICKZ uses Facebook for a better Customer Experience

Jiri Honc — Wed, 10 Oct 2012 14:01:17 +0000

The KICKZ online store is our latest e-commerce project that has gained a deep integration with Facebook. This blog article presents the four ways to utilize Facebook for a better and smoother customer experience. First we show how customers can use their Facebook accounts for registration and login into the online store using the OAuth 2.0 protocol. Next we discuss accessing the customer data from Facebook’s Open Graph (if user’s permission is given) in order to prefill registration and order forms. And finally, we deal with product reviews and forwarding customer Facebook posts to the Facebook wall of the online store.

Facebook uses the authentication and authorization protocol OAuth 2.0. Due to the broad, world-wide user base of Facebook, OAuth became a valuable authentication resource for web applications. But Facebook does provide more for web applications – it gives access to the whole social graph of a user, the permission by the user provided. We show now step by step, how an integration can look like.

Facebook OAuth

The benefits of the integration of an authentication provider are manifold. First, the user can use his Facebook account to log-in at several web applications. He hasn’t to remember a bunch of credentials. He doesn’t need to fill-in regristration forms again and again. Thus, an authentication service saves time and helps to keep the amount of accounts to manage low.

Login via Facebook: Users can login into the KICKZ web shop with their Facebook account. For new users, their Facebook profile data is used to prefill the registration form (see also screenshot below).

Second, any Web 2.0 site provides such share buttons to Facebook or Google+, that’s already a must. The integration of Facebook’s OAuth service for user registration in your own web application will lower the bar for new users, because it’s just one click away. The huge popularity of Facebook with nearly 1 billion users around the world makes Facebook a good partner for authentication purposes. And what’s important for users: the OAuth 2.0 protocol ensures that your web application won’t leak any passwords.

Facebook’s Open Graph API

Facebook provides a public API for its social graph (now Open Graph), so any web application, identified to Facebook by its Facebook application, is able to ask the user for permission to access a user’s personal data and his personal wall. Depending on the user’s choice, the web application is able to authenticate the user and do a login. If the user is not yet registered in your web application, it can read the personal data from Facebook and prefill the registration form. Additional actions include posting on the user’s wall and re-post some of his posts to the Facebook wall of the company of the web application.

Example of a prefilled registration form with data obtained from the user's Facebook profile.

In order to get access to the Facebook Open Graph API, a web application developer needs to register a so called “Facebook Application”. The Facebook App describes the connection to our application, in our case the online shop. It’s the integration point of our web application and Facebook.

Once the Facebook App is prepared via the App Dashboard, we need the values “App ID/API Key” and “App Secret”, which we need to login to Facebook ourselves to access the Facebook Open Graph API. In the following screenshot, the App ID/API Key and App Secret values are blurred.

Preparing an Facebook Application on the App Dashboard for your web application. You are provided with an App ID/API Key, App Secret.

The Facebook Applications are bound to a dedicated site URL and domain. This a security mechanism, so only requests from the registered site/domain will be allowed. Find more about the Facebook Applications and the Open Graph API in the Open Graph Tutorial.

Hint: If you’re developing a web application it’s helpful to register a Facebook Application for “localhost”. This way, each developper can share this single Facebook Application. For the production environment, just use another Facebook Application registered to the real web site and domain.

Now with the Facebook Application in place, we’re able to implement the features.

Feature 1: User-Registration with Facebook

Faceboook provides a JavaScript SDK which enables you to connect to your Facebook Application and then to access the Facebook Open Graph API to interact with the users’ Facebook accounts. The JavaScript SDK can be rendered in three ways: XFBML, XFBML in HTML5-compliant markup, and via Iframe. We choose the first two, XFBML and HTML5, because they support better tracking capabilities. For more details, please refer to the Social Plugins documentation.

Client-side authentification flow via the Facebook Javascript SDK (steps 1 and 2 in diagram).

1. Connect with Facebook Application (Javascript)

It is possible to initialize the JavaScript SDK asynchronously, and we prefer this implementation as it provides us with the fastest response if we use the following code right after the opening tag:

2. Login a User (Javascript)

The authentication component of our web application needs to support three use-cases:

Registered user and already logged in to Facebook
Registered user, but not logged in to Facebook
New User: The user has a Facebook account, but is not registered in our web application

The listing below shows the necessary code on the client-side. It just uses the Facebook API to either show the OAuth login dialog, or ask for permission to access the users Facebook data in case he’s not a registered user. Facebook then maintains the granted permissions in our Facebook application, so we don’t need to check, whether this user is already registered or not.

First we define the link:

Login via Facebook

And then we define the JavaScript function fb_login_register:

fb_login_register : function () {
    FB.getLoginStatus(function(response) {
        if (response.status == "connected") {
            // Case 1: Registered user and already logged in to Facebook
            LOGIN_TO_WEBAPP(response.authResponse.accessToken);
        } else {
		    // Cases 2/3: show FB login dialog and ask for permissions to access private data
            FB.login(function(response) {
                if (response.authResponse) {
                    console.log("User is connected to the application.");
                    LOGIN_TO_WEBAPP(response.authResponse.accessToken);
                } else {
                    console.log('User cancelled login or did not fully authorize.');
                }
            }, {scope:'email,read_stream,user_location,publish_stream,offline_access'});
        }
    });
},

For further details see the FB.getLoginStatus and FB.login documentation.

And this is how the login procedure looks like to the user:

Request for Permissions.

After the successful login, we just send the User access token for this user to our server, which then gets the user’s data and provides a session for him.

Hint: Asking for the permission “offline_access” comes very handy on the server-side. This allows to access the users data, without the user being currently logged in. However, the offline_access has been removed! If you are building a new application you shouldn’t use this permission. Instead check the Deprecation of Offline Access Permission.

With our approach, the complete authentication is made on the client side (i.e. browser) as shown above. The client sends Facebook’s user access token, so on the server-side we can access the Open Graph API to get the personal information. This will be done in step 3 before.

Alternative: Server-Side Authentication

Analogous to the steps 1 and 2 above that use the JavaScript API from within the browser, you can also use the OAuth authentication on the server-side using the so-called server-side OAuth flow, an HTTP-based approach. Here again, you would first connect to our Facebook Application, and then access with the Facebook Open Graph API to read the users data is possible (step 3 below).

Doing the authentication with the server-side flow leads to some HTTP redirects, so the user has to leave the origin website (our KICKZ shop) during the login, as shown in the screenshot below. The benefit of the server-side authentication is better security, because the access token has not to be transferred over the network from the user’s browser to the web application on the server.

Here’s how you connect to our Facebook Application:

Step 1: Sending a Request for code and ask for permissions.

In this first step we generate an URL as follows:


https://www.facebook.com/dialog/oauth

    ?client_id=YOUR_APP_ID
    &redirect_uri=YOUR_REDIRECT_URI

Here, you use your Facebook App’s ID as the YOUR_APP_ID parameter. For a full list of parameters, see the OAuth Dialog documentation.

Hint: If you define YOUR_REDIRECT_URI as “http://localhost/” you can test it directly in your browser. First you will be prompted to authorize the Facebook App to your Facebook account, then you will be redirected to your localhost with the code URL parameter as:


http://localhost/?code=OAUTH_CODE_GENERATED_BY_FACEBOOK

In this step you also ask for permissions of your application. The permissions are defined by the scope parameters, e.g.:

scope=email,read_stream,user_location,publish_stream,offline_access

Server-side authentification flow using HTTP requests (steps 1 and 2 in diagram).

Step 2: Request for User Access Token

Now that you’ve got the code, you can ask for the access token as follows:


https://graph.facebook.com/oauth/access_token?

	client_id=YOUR_APP_ID&redirect_uri=YOUR_REDIRECT_URI&
	client_secret=YOUR_APP_SECRET&code=OAUTH_CODE_GENERATED_BY_FACEBOOK

The response for this request contains the access token in the message body. Example:

access_token=USER_ACCESS_TOKEN&expires=YYYY

We just use the GetMethod class of the Apache HttpComponents library for sending the HTTP requests and obtaining the responses.

3. Load the users data and create a session (Server-Side)

Once we have our user access token, either the Javascript way or via the server-side flow, we can now use the any Java library to load the personal information of a user from Facebook.

There are several Java libraries for accessing the Facebook API. In this example we just use the restfb library, because it offers a very intuitive way for working with the Facebook Open Graph.

This is the code to retrieve a user from Facebook, using the access token for the user delivered by the client-side:

FacebookClient facebookClient = new DefaultFacebookClient(accessToken);
FcbUser fbUser = facebookClient.fetchObject(
            USER_ACCESS_TOKEN,
            FcbUser.class,
	        Parameter.with("fields", "id, first_name, last_name, picture, email, location, gender, birthday"));

Now that we’ve successfully got the Facebook user, we can copy his basic data into our user base, create a new session for him and log him in. In our web application we just inform the user, that he’s now logged in, which looks likes this:

The web application greets and informs the user about the successful login via Facebook Connect.

Conclusion

With these fairly easy steps the “Login via Facebook” feature gets implemented. The web application can provide a one-click registration process for new users. In respect to our native registration-process, in which we ask for all relevant information, we now support a so called “partial” registration. All information, like the postal address information, which is not available via Facebook will be retrieved from the user during the first check-out.

Feature 2: Generate posts on the a user’s Facebook wall

Everybody knows the “like buttons” on web-pages, but with the Facebook API there are much more possibilities to interact with the users. In our web shop each user is able to post reviews on products. These reviews are shared with other customers in our web-shop directly.

With the Facebook integration, we can share the reviews of a user and post them directly on his Facebook wall. This leads to a win-win situation, because the user sees his reviews liked by other users. And the web shop gets more incoming links and more attention which helps to boost marketing and SEO.

Let’s look at how to post a message to a user’s Facebook wall. Since we already have the permissions and know how to obtain an access token, we can just use the restfb library like this:

FacebookClient facebookClient = new DefaultFacebookClient(ACCESS_TOKEN);
FacebookType publishMessageResponse = facebookClient.publish(
    "me/feed", FacebookType.class,
    Parameter.with("message", MESSAGE_TO_POST),
    Parameter.with("link", LINK_TO_POST),
    Parameter.with("picture", PICTURE));

String postId = publishMessageResponse.getId();
log.debug("Published message ID: " + postId);

And since we have the id of the post, we can also put a comment to that message as follows:

FacebookType response = facebookClient.publish(
    postId + "/comments", FacebookType.class,
	Parameter.with("message", COMMENT_TO_ORIGINAL_MESSAGE)); 

log.debug("Comment ID: " + response.getId());

In our web application we use this feature to automatically post reviews on products of the user on his personal Facebook wall. The comments are reviewed by a shop personnel, thus not all reviews get distributed automatically. So the code snippets above are integrated in the customers review approval workflow.

Feature 3: Listen on a user’s Facebook wall and copy posts to the shop wall

Facebook provides also a listener interface. So a Facebook application can register listeners for posts of a user. For each new post the listener gets invoked and is then able to decide what to do.

The callback functionality breaks the basic Facebook privacy. With this mechanism each post can break out the walled Facebook garden, in which the user originally wanted to share his post. So this feature also needs to get handled with great respect and empathy to the users privacy feeling. Thus, in order to get these posts a special permission from the user is required.

As KICKZ is a strong shop-brand and the customers have a close relationship to the brand, they usually accept this post forwarding and feel proud to be present on the Facebook wall of their favorite shop. This may not be the case for every company or brand, and customers may get offended when they see their “private messages” on the companies Facebook wall.

The following steps are necessary to allow us to listen and read a user’s posts:

Ask the user for the permissions “read_stream” and “publish_stream”.
Register a Facebook listener (callback server).
Filter user activities and publish them to the company’s Facebook wall or to web shop site.

Main steps of this listening and filtering process (read left-to-right).

We implemented a simple “fb_callback_servlet” which accepts the incoming calls from Facebook. If the user’s post matches certain criteria, then his post is directly posted to the Facebook wall of the shop and its web site.

Here some background information about the steps:

Registration of the callback server: We define a “callback_url” on which we listen in the “fb_callback_servlet”. During the registration process we pass the access token of our Facebook Application and the parameters describing what and on which object of the graph API we want to listen on.
Users activity listener: Our “fb_callback_servlet” provide a doGet() method that verifies the subscription for the user-stream to Facebook. This is also required for any modification or deletion of the subscription. The doPost() method of the servlet is used as a “callback” and receives the data of the user stream.

An official description of this function is available on “Realtime Updates” in the Facebook developer documentation. And a simple implementation example is available on facebook / real-time (Github).

Feature 4: Tracking Facebook communication via Google Analytics

Tracking Facebook communication with the Google Analytics tool provides useful information for the management of e-commerce activities and shows traffic related to Facebook.

The integration of Google Analytics is also straight forward and there are many good examples like Google Analytics Social Tracking Demo and tutorials available, e.g. “Social Plugin Analytics in Google Analytics”.

In this web application we use the tracker in the traditional way, but we just override the global social track abilities, as we are currently only interested in Facebook events on our pages. So we add tracking logic for Facebook directly to the Google Analytics pageTracker object:

The pageTracker.trackFacebook method defined above is called after FB.init() in the web-pages of our web application.

Conclusion

We showed that the integration of Facebook into a web application is quite straightforward. We demonstrated a social login/registration and in the context of a shopping use-case. These features allow a user to quickly login and provide the postal information later on-demand during the check-out.

The integration of customer reviews and forwarded user posts with the shop’s Facebook wall helps to gain visibility of the web site, since a lot of fresh incoming links are generated. In order to respect the users’ privacy, there’s no automatic forwarding applied, the reviews are moderated by the shop personnel. Finally, the integration of Google Analytics helps to monitor the efficiency of our efforts of the Facebook related traffic.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Integrating FredHopper into a hybris Marketplace

Christian Belka — Wed, 26 Sep 2012 15:02:40 +0000

In this blog article we discuss how Fredhopper, an advanced site search and merchandising product, can be integrated into the hybris eCommerce suite not only to search for products, but to create cross selling and campaigns as well. In the used scenario hybris is the foundation of a marketplace with a few million products from thousands of vendors.

The standard edition of hybris uses the open source Lucene-based Solr enterprise search server. But for this project Fredhopperwill be be used instead. The article explains how Fredhopper can be provided with all the required data from the hybris system.

Fredhopper is a commercial Online Marketing Suite with a focus on

On-site Search,
On-site Targeting, and
Predictive Targeting.

Fredhopper also delivers the navigational structure for our project and all other navigation-related items like breadcrumbs, etc.

A marketplace consists not only of one huge catalog, which lists all products from all marketplace vendors. It also contains individual vendor shops, where the vendors can have their own catalog structure, their own navigation and their own search. All ths is also handled by Fredhopper.

A marketplace with two vendors (dealers).

For example, consider the main catalog in the figure above. It can contain an audio player, which is offered by different vendors. Therefore, the audio player must occur in the main catalog and also in the vendor catalogs. In the context of a vendor shop an audio player should be displayed in that context only, while the main catalog of the marketplace will display the product offered by multiple vendors at different prices where the offer with the lowest price will be displayed in the standard result list (either via search or navigation).

Why Fredhopper?

First, Fredhopper can do much more than searching. It can also be used to create campaigns for upselling, has a recommendation feature and offers sophisticated auto-correction for spelling, etc. in a lot of languages, including those used in the marketplace.

Illustrations of Fredhopper-based offers and recommendations.

Secondly, changes in its behavior can be easily configured by marketing users without a need for technical support or code changes. This flexibility was the reason why we switched from the provided Solr product to Fredhopper.

Integrating Fredhopper into hybris

Before I discuss the details of the integration, let’s take a look at the hardware and infrastructure we had to integrate. As the following diagram shows, Fredhopper is deployed on different servers where each server has a specific function (Navigation/search and quick search).

Distributed Fredhopper deployment for Navigation/search and quick search.

To use the Fredhopper features like navigation services, search services, campaigns, etc. we developed a suite of components for the hybris WCMS (Web Content Management System):

Components used to display categories
Search components
Navigation components
Recommendation components

All those components are “regular” hybris components that query the Fredhopper index.

The Fredhopper servers receive requests from and deliver responses to the hybris servers and not directly to the user. The hybris servers use web services to communicate with the Fredhopper servers. Fredhopper provides a Java-based web service library to send queries. We wrote our own wrapper to encapsulate all the technical details and created an API where all project-based queries are encapsulated.

The following snippet shows, how to use this wrapper (NavigationHelper) to communicate with Fredhopper. It’s an excerpt of our WCMS search component:

@RequestMapping("/ProductsSearchComponentController.html")
public String showSearchNavigation(final ModelMap model, final HttpServletRequest request) throws WebException {

    // ProductsListComponentModel is a hybris component
	ProductsListComponentModel component = (ProductsListComponentModel) request
			.getAttribute(FrontendConstants.CMSConstants.COMPONENT_KEY);
	long startTime = System.currentTimeMillis();
	NavigationState navigationState = this.navigationHelper.getOrCreateNavigationState(request);

	// --- Calls a Fredhopper web service through our navigationHelper wrapper
	// NavigationResult is a DTO, result from Fredhopper
	NavigationResult navigationResult = this.navigationHelper
			.getOrCreateNavigationResult(request, navigationState);

	try {
		this.navigationHelper.getSelectedCategory(request, navigationState);
	} catch (final UnknownIdentifierException e) {
		Logger.getLogger(this.getClass()).warn("No navigation category with code '" +
				navigationState.getCategoryPath() + "' found");
		throw new WebException("Category not found", HttpServletResponse.SC_NOT_FOUND, e);
	}

	// --- Build up Spring MVC view model
	model.put("orderByList", SearchOrderEnumeration.getSortOptions(navigationState.getVendorShop() != null));
	model.put("pageSizeList", pageSizeList);
	model.put("isSearch", Boolean.valueOf(navigationState.getSearchTerm() != null));
	model.put("productsPagination", this.paginationHelper.pagination((int) navigationResult.getTotalCount(),
			navigationResult.getPageSize(), navigationResult.getPage()));
	if (navigationState.getSearchTerm() != null) {
		model.put("suggestionList", this.navigationHelper.getSuggestions(navigationState.getSearchTerm()));
		model.put(CampaignComponentConstants.CONTEXT_CAMPAIGN_ELEMENT,
				searchCampaign(navigationResult.getCampaigns(), component.getCampaignName()));
	}
	if (Config.getBoolean(NavigationHelper.FREDHOPPER_LOG_TIME, false)) {
		Logger.getLogger(this.getClass()).warn
				("FREDHOPPER_TIME: showSearchNavigation took " +
						(System.currentTimeMillis() - startTime) + "ms");
	}

	if (navigationState.getVendorShop() == null) {
		return FrontendConstants.CMS2_COMPONENT_VIEW_PATH + COMPONENT_JSP_PATH;
	} else {
		model.put("contextVendorShop", navigationState.getVendorShop());
		return FrontendConstants.CMS2_COMPONENT_VIEW_PATH + COMPONENT_FOR_VENDOR_SHOP_JSP_PATH;
	}
}

The class NavigationHelper calls the Fredhopper Navigation Service. This service is used to create the “real” communication with the Fredhopper Java Webservice Client like this:

public NavigationResult navigate(final NavigationState state) throws NavigationException {
	...
	// Mappingcode to create the query String going to Fredhopper from the NavigationState Object
	final Page page = this.runQuery(query);
	// Mapping Code from FredHopper Page Object to "NavigationResult" on our side
	...
}

In the runQuery() method we really execute the webservice call, as shown below:

private Page runQuery(final Query query) {
	final String queryString = query.toQueryString();
	final FASWebService fasService = getFasWebService();
	return fasService.getAll(queryString);
}

The FASWebService class is the given Fredhopper class, which returns a FredHopper com.fredhopper.webservice.client.Page object which is used to fill our NavigationResult object.

Starting from this base, we can easily provide a toolbox consisting of Fredhopper WCMS components.

Updating the Fredhopper search index

To export the data from hybris to Fredhopper, we use the existing Solr features from hybris (part of the Solr extension), but extended them for usage with Fredhopper. From here on we start an export which exports all the products, row by row.

If a product has multiple offers from different vendors, the cheapest product will be selected for the export. This is because, according to the current business rules, the cheapest offer be displayed as the default. The idea is that the frontend will retrieve the other offers from the database and not from the Fredhopper index, because the index generation will be to huge and therefore too slow otherwise.

Using Kettle ETL Jobs for exporting and updating the Fredhopper search index.

We export the current product list into a CSV file which is then fed into a Kettle ETL Job which imports the data into the Fredhopper index, which is completely regenerated. Pentaho Kettle is a data integration framework for Extraction, Transformation and Loading (ETL) Jobs. This job is triggerd once a week.

We also run two other jobs on a more regular basis which handle delta updates for new, modified and deleted products. This is our solution to keep Fredhopper up-to-date even for huge data stores.

The first incremental job searches for all modifications in the data model (like updated name, change of category etc) to be exported. We get a big search result here and the job takes a few hours to run. It is triggered once a day.

For information about price and availability we use a second incremental job that runs multiple times a day. Fredhopper doesn’t differentiate between price rows and products so this second job only monitors price rows and only the attributes of price rows (like price and availability) are considered.

Scaling the Fredhopper Integration to huge Marketplaces

As mentioned above and shown in the first diagram, there are two contexts, the general marketplace context, where the customer is browsing the marketplace, and the shop context for the specific vendor stores. Therefore we use a mixed mode: we use Fredhopper to create the product listing pages but load vendor-specific product attributes like vendor prices and stock availability directly from the database.

As a result we have a fast, reliable and up-to-date search and navigation engine which fulfils the specific requirements of a broad marketplace, namely to display a large number of products in varying context, extremely well.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

PL/SQL Unit Testing with DBUnit

Nick Giles — Tue, 24 Jul 2012 06:08:04 +0000

My colleague Slavomír Jeleň and I are currently working on a logistics management application for an international food retailer. It’s a data-oriented application that performs pre-calculation steps on billions of rows with PL/SQL stored procedures. In order to ensure the correctness of these calculations, we devised a solution for unit testing the stored procedures in Oracle based on DBUnit.

The logistics management application enables the international food retailer to administer the flow of goods between stores and warehouses. The number of users is relatively low at around 200, but the volume of data is massive with many tables containing hundreds of millions of rows and some containing over one billion. An operating day begins with an import of the latest data from the customer’s central data warehouse. From 7am on, users analyze tables of results and trends derived from this imported historical data, make decisions based on them and the application then recalculates future trends based on these decisions.

In order to reduce the volume of data to be analyzed in real-time when recalculating future trends, the historical data is pre-calculated into a smaller set of aggregated values. For example, sales data describing how many pieces of various items are sold in which store on which day is imported every morning, but one part of the system only needs data per item and per region for a month and so it makes sense to perform this aggregation at the beginning of the day and cache the results in a separate database table. These pre-calculations take the form of PL/SQL stored procedures which are run directly after the import completes every morning.

Overview of how the historical data is pre-calculated into a smaller set of aggregated values.

We had some issue with quality assurance, which generally fell into three groups:

Unusual circumstances would create data that would not be properly aggregated,
The ability to ensure that changes to aggregation rules have been implemented properly, and
Ensuring that changes made do not adversely affect other aggregation rules.

The pre-calculation is split into several stored procedures but together comprise over 2000 lines of PL/SQL. Ensuring that all this logic performs as it should demands special attention. What was required was a system which would be able to test the stored procedures to make sure they function as specified – unit testing for PL/SQL stored procedures.

Proposed solution

The goal we had in mind was a system which could insert the bare minimum amount of data required for one specific test, run the pre-calculation and then compare the actual result with what the expected result. The overall pre-calculation is very complicated and so we split the tests up so that there would be one test for each rule of the aggregation. Using the example mentioned earlier, one test might be to specify sales data on the first day of a month and the last day of the previous month for one given item in a given store and to ensure that only the data in the current month is calculated.

Another test for this aggregation might be to have sales data in a month for two items and to ensure that the data is aggregated separately for each item. Importantly though in each case we specify only the absolute minimum amount of data required for the scenario, for example there might be just one country, one store, one item and perhaps just two rows in the sales table, not forgetting auxiliary data for foreign key integrity.

Implementation

After a few prototypes, we settled on using DBUnit which is able to do exactly what we want. DBUnit is a testing framework for databases which can run stored procedures, fetch, manipulate and compare data. It is a simple and usable interface to the database on top of JDBC including the ability to compare datasets derived from the database against datasets specified in file based structures such as XML and CSV. This means that queries, views and full tables can be compared.

Initial data and the expected output state of the tables containing the aggregated values are specified separately in two simple XML files. These are then referenced in a test method in a Java class along with the command to run the pre-calculation stored procedure.

Relevant parts of our Testing solution and how they play together.

An Example

Using the example mentioned earlier, sales data would be prepared like this:

sales_data

item_id	date	store_id	quantity
1	31/05/12	1	1
1	01/06/12	1	2
1	30/06/12	1	4
1	01/07/12	1	8

In addition to this, auxiliary data would have to be prepared for entities such as the store, the store’s country, the country’s language, etc. Most of this auxiliary data is common and so can be easily duplicated when making new tests, making small changes where necessary.

In this example we are interested in making sure that sales for June are correctly aggregated and that values for May and July are excluded from the June aggregation and so expected values in the table containing the monthly aggregates would look like this:

monthly_data

item_id	month	store_id	quantity
1	01/05/12	1	1
1	01/06/12	1	6
1	01/07/12	1	8

Once the two XML files have been created, the next step is to create the Java test method:

public class PrecalcMonthlyDbTestCase extends ProjectDBTestCase {
  @Override
  protected IDataSet getDataSet() throws Exception {
    return loadXmlDataSet
      ("com/mgmtp/project/db/nonfood/precalc/sales/monthly1.xml");
  }

  @Test
  public void test() throws Exception {
    getConnection().getConnection().createStatement().execute(
      "{call p_recalc_monthly_sales(1, DATE '2012-07-02')}");
    compareResults(
      "com/mgmtp/project/db/nonfood/precalc/sales/monthly1_result.xml");
  }

  //...more tests
}

The class PrecalcMonthlyDbTestCase covers just one test. It extends from ProjectDbTestCase which is our implementation of DBUnit’s base class for test cases, setting common configuration options and providing additional functionality such as loading the source data from a specified location on the classpath before the test and cleaning it afterwards. The test itself is a simple affair; it runs the pre-calculation for a given date and then compares the expected data defined in an XML file with actual data in the corresponding database tables holding the new data aggregated by the pre-calculation.

Test-driven Development

We soon discovered that we were able to use this approach to ensure changes to the aggregation are implemented correctly and that all conceivable corner-cases are correctly handled. A Test-Driven-Development approach was accommodated whereby the first step in implementation was to create a series of tests based on the requirement. Initially these tests must fail as they specify new behavior. Then the implementation begins and afterwards is verified when the tests are run successfully. Similarly, if a bug is found in the pre-calculation, the first step is to reproduce the situation with a failing test case.

Conclusion

Whilst the testing of PL/SQL stored procedures was the initial focus of the work, we are now planning to broaden the scope and use DBUnit to test the large SQL statements in the project. Many of the SQL statements make extensive use of common table expressions and many exceed 200 lines, making them very susceptible to the same vulnerabilities as the pre-calculation stored procedures.

The end result is several suites of tests covering all of the various pre-calculation procedures which are run every night as part of the nightly build and also before every release. We don’t have any numbers to quantify the increase in accuracy and stability of the results, but are now 100% sure that once a problem surfaces, it will not resurface again.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Possibly the most malicious Regular Expression - Hacking Java Puzzlers for Fun and Profit, Part 3

Tobias Budde — Tue, 12 Jun 2012 09:57:01 +0000

This is the next of my episode on regular expressions. Today, we look at the worst regex you can possibly come up with, although it looks innocent and simple. You will learn about this backtracking trap that let’s you easily wait for 10^30 steps, as an example of an errant email regex will illustrate. One possible solution we investigate is the use of possessive quantifiers.

Well, some of you might think: All regular expressions are malicious.

If you are one of them: You have no idea how bad they can become!

Greedily Looking for ‘aa‘

Have a look at this short example:

public static void main (String[] args) {

    final String pattern = "(aa|aab?)*";

    // two 'a'
    final String a002 = "aa";
    // three 'a'
    final String a003 = "aaa";
    // 102 'a'
    final String a102 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
    // 103 'a'
    final String a103 = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";

    System.out.println(a002.matches(pattern)) ;
    System.out.println(a003.matches(pattern)) ;
    System.out.println(a102.matches(pattern)) ;
    System.out.println(a103.matches(pattern)) ;
}

What does it print?

true false true false
Throws an exception
Does not compile
None of the above

The regular expression “(aa|aab?)*” matches all strings that are made up of “aa” or “aab“. I.e., it matches for even numbers of ‘a’ and does not match for odd number of ‘a’. (I know. The same can be done with a simple “(aab?)*” but just follow me.)

So in theory it should print “true false true false” (answer 1 above). But actually, it prints “true false true ” (answer 4). The final “false” will come some billion years later if you are patient and your computer does not want you to reboot in the meantime.

It’s not a bug, It’s a feature

We got caught in a backtracking trap. Let’s have a look at a shorter example: “aaaaa“. The following table shows what the java regular engine does to see if it matches to our pattern.

Step	Group 1	Group 2	Group 3	Result
1	(aa)	(aa)	(aa)	fail
2	(aa)	(aa)	(aab?)	fail
3	(aa)	(aab?)	(aa)	fail
4	(aa)	(aab?)	(aab?)	fail
5	(aab?)	(aa)	(aa)	fail
6	(aab?)	(aa)	(aab?)	fail
7	(aab?)	(aab?)	(aa)	fail
8	(aab?)	(aab?)	(aab?)	fail

Explanation:

Step 1: The engine finds two “aa“, tries to find a third “aa” and fails.
Step 2: The engine finds two “aa“, tries to find a “aab?” next and fails.
Step 3: The engine starts backtracking and replaces the second “aa” with “aab” and fails again for both “aa” …
Step 4: and “aab?“.
And so on.

The result is: “aaaaa” does not match “(aa|aab?)+“.

In our example with 103 ‘a’ the engine will execute 2^100 = 10^30 steps, that is 1000 billion billion billion. The regex “(aa|aab?)*” looks so innocent and simple but is probably the worst regex I ever saw.

But backtracking is useful. If you match “” to the regex “<(.*)>(.*)<\1>” you will find a match of opening and closing tags. I think there is no regular expression for a regex engine without backtracking that can do this match. Please comment on this!

Switching to Possessive Quantifiers

What will change if we use a slightly different regex? We change the quantifier from a greedy “*” to a possessive “*+“.

final String pattern = "(aa|aab?)*+";

What does it print?

true false true false
Throws an exception
Does not compile
None of the above

Since we use a possessive quantifier the regular expression engine will not do backtracking. So the process stops after step 2 and the “aa” in ‘Group 2′ won’t be replaced for “aab?“. The first result is printed at once.

A Case Study with Email Addresses

Let’s take the example of email address. Let’s look at two similar regular expressions for it:

[a-z0-9](([\-.]|[_]+)?([a-z0-9]+))*@[a-z0-9]+[.](([a-z]{2,3})|([a-z]{2,3}[.]{1}[a-z]{2,3}))

[a-z0-9_\+-]+(?:\.[a-z0-9_\+-]+)*@[a-z0-9-]+(?:\.[a-z0-9-]+)*\.(?:[a-z]{2,4})

Do you spot the difference? The first expression is as evil as “(aa|aab?)*” and gets stuck if you try to match e.g. "aaaaaaaaaaaaaaaaaaaaa!" while the second is fine. I.e. if you use the first regex to validate email addresses in your Java code your thread gets stuck for a few million years and your system is vulnerable to a “regular expression denial of service” attack. In principle all regular expression engines that allow backtracking will have the same problem. Imagine what will happen to your database system if there are a few thousand invalid email addresses to be stored and you use an malicious regex in the DB!

There is no simple way to recognize regular expressions which fall into the evil category. But here are some hints:

Be careful with options that imply each other: “aa” vs. “aab?“.
Try to avoid cascading quantifiers like in “(a+)+“.
Try to be possessive like in “(aa|aab?)*+“.

Have a look at the Wikipedia article on Redos for more information and additional examples for malicious regular expressions.

I’m curious to hear your “war” stories: Did you actually have this problem in your systems on production? What did you do to find it and fix it?

(c) 2013 mgm technology partners. This posting "Possibly the most malicious Regular Expression - Hacking Java Puzzlers for Fun and Profit, Part 3" is part of the mgm technology blog. The author of the posting is Tobias Budde.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Regular Expressions: Splitting Pipes - Hacking Java Puzzlers for Fun and Profit, Part 2

Tobias Budde — Wed, 30 May 2012 16:24:38 +0000

It’s a common saying in IT: “I had a problem and used regular expressions to solve it. Now I’ve two problems”. We want to offer help in a series of mgm “Hacking Java Puzzler” blog entries and demonstrate how regular expressions can be useful anyway. In this first episode we will focus on splitting CSV lines.

CSV is a very old file format and parsing it is very simple. There are special libraries for this but Java has built-in support as well. The class String offers the split() method that takes a regular expression to parse the content of a string. The implementation of this function directly uses the split method in the java.util.regex.Pattern class.

Have a look at this short example:

public static void main (String[] args){
    final String text = "a|b|c";
    final String delimiterPattern = "\\|";

    final String[] columns = text.split(delimiterPattern);

    System.out.println(Arrays.toString(columns));
}

Our values in the CSV are delimited by the pipe character ‘|’. This real-world example is taken from a legacy application that represents lists as pipe-concatenated strings, like "a|b|c" in the code above. This example would work in the same way for any other delimiter character.

So, what does it print? Yes, it’s “[a, b, c]“. Well done.

Puzzler 1: Warming up

Now for the first simple Java puzzler. We want to do the same, but our first two columns are empty:

    final String text = "||c";

What does it print?

[, , c]
[null, null, c]
An exception is thrown
None of the above

As expected it’s “[, , c]” and the first two columns are empty strings.

Puzzler 2: You’ll be surprised

Now it gets a little harder. We change the text so that all columns are empty:

    final String text = "||";

What does it print?

[, , ]
[null, null, null]
An exception is thrown
None of the above

Well, you’ll be surprised—it’s number 4, and what will be printed is this: “[]“.
One might want to shout out loud: “That’s *%$#& stupid. I’ll never understand regular expressions!”

What just happened?

If you blame regular expressions for this unexpected result you are actually barking up the wrong tree. Yes, it is implemented in the regex package, but let’s read the JavaDoc:

String.split(): [...] trailing empty strings will be discarded.
Pattern.split(): Trailing empty strings are [...] not included in the resulting array.

If you have a look at the code of the Pattern.split() method, you will find something like this:

// Taken from JDK's Pattern class

int resultSize = matchList.size();
if (limit == 0)
    while (resultSize > 0 && matchList.get(resultSize-1).equals(""))
        resultSize--;
String[] result = new String[resultSize];
return matchList.subList(0, resultSize).toArray(result);

These lines actively delete empty trailing strings, like documented. I.e. your expected result is deliberately destroyed.

What’s the reason for this API design? Does anybody have a clue? I don’t.

How to Get it Right

The workaround is quite simple: Just ensure that limit != 0 in Pattern.split. How? Luckily, there’s a variant of the split() method that takes the limit as a parameter. The following small change does the job (note the -1 as a second parameter):

final String[] columns = text.split(delimiterPattern, -1);

In my opinion this should have been the default behavior.

Another solution is to directly use the regex API:

final String text = "||";
Pattern pattern = Pattern.compile("[^|]*");
Matcher matcher = pattern.matcher(text);
List columns = new ArrayList();

while (matcher.find()){
    columns.add(matcher.group());
}

The regular expression “[^|]*” matches everything that is not a pipe symbol. This includes the empty words in our sample text.

Using the regex API is a little more work but is the only way for a related problem: Extract only not empty words from a CSV. Using split() will always return leading empty words (as you can see in the first simple puzzler). With regex it’s just a minor change to “[^|]+” because the asterisk means ‘none or more‘ while the plus quantifier means ‘one or more‘.

(c) 2013 mgm technology partners. This posting "Regular Expressions: Splitting Pipes - Hacking Java Puzzlers for Fun and Profit, Part 2" is part of the mgm technology blog. The author of the posting is Tobias Budde.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Building a scalable Web-based Call Center CTI Solution

Lars Immisch — Tue, 08 May 2012 13:26:51 +0000

My project was part of our customer’s effort to replace all of the enterprise applications with web applications based on a standardized technology stack. In this strategic move, the call center integration was a crucial step. As it turned out, the technical design of the new call center telephony solution was quite challenging. We did not only learn a lot about CTI; we also had to implement the system to be scalable and ensure that it handles more than 1000 call center agents.

The call center agents should use mostly the standard web applications, but with an additional telephony control that allowed them to accept incoming calls, to disconnect calls, or to make consultation calls to other agents or supervisors.

An incoming call

Let’s have a look at the most important usecase first: an incoming call.

The following diagram gives an overview of the flow of events, before the agent’s telephone rings:

The simplified flow of events before an agent receives a call.

The incoming call of the customer is handled by the PBX (Private Branch Exchange). When the agent finally takes the call, a lot of information about the customer has already been collected. In most cases, the caller will already have gone through an interactive voice response system that has collected his account number and verified his PIN (omitted from the picture above).

This is how the agent screen might look like after the agent has taken the call:

Schematic screen of the call center agent UI.

The box on the left are the telephony controls. They are embedded in an iframe and allow the agent to disconnect the call or place consultation calls to other agents. The telephony controls send commands to the gateway (and in extension to the PBX) and receive asynchronous events.

CSTA as a Model for our Protocol

Before it was even determined whether the telephone system should be integrated directly through the PBX or via an integration layer (Genesys), we decided to use the CSTA Phase III communication protocol as an orientation for the protocol between gateway and browser. CSTA (Computer Supported Telephony Applications) is an ECMA standard (like JavaScript) and describes third-party call control using services and events. Third-party call control roughly means that the standard looks at an entire switch and all connected devices (telephones), and not just a single telephone. This point of view is reflected in the naming of the services and events. For example, when a call arrives at a terminal the event is called Delivered. A sample event flow is given in the following diagram.

Exemplary flow of CSTA services and events in our system.

Services are commands to the telephone system. An outgoing call (from any device within the domain of the switch) is initiated by a Make Call Service. But there are also services like Set Agent State.

CSTA is extremely comprehensive; we used only a small selection of its services and events. It is also easy to extend — the transfer of non-standardized key/value pairs within the data part of services and events is explicitly provided for.

CSTA provides an ASN.1 and an XML encoding. Writing an ASN.1 parser in JavaScript was obviously not a good idea and even the XML mapping is quite heavy-weight and we decided to design our own transport encoding on top of JSON and built a REST-inspired web service as a gateway to the PBX.

Requirements

The customers’ technology framework requirements were:

Internet Explorer 8 as the browser for the call center agents
Wicket as web application framework for the call center application
Tomcat 7 as the web application server for both the call center web app and the gateways.

The technical requirements were: minimal latency, high throughput, and high availability. An average delay below 150 ms was required for latency, i.e. a value slightly below the attention threshold. For the call center callers, very low latency is not crucial — most callers will have waited in the queue for minutes rather than seconds to reach a free agent anyway. But the new web application should — if at all possible — not worsen the ergonomics for the call center agents. In the end, this wasn’t a problem: during tests using moderate load latencies below 80 ms could be achieved.

High availability is an obvious requirement: if a call center with about 1000 agents fails, there will be many unhappy customers. On an unlucky day the failure will even be reported in the news. We solved the problem by designing for redundant server components and a low latency failover protocol. The actual web application uses Tomcat’s built-in clustering mechanism. We couldn’t reuse this for the telephony gateway, because the relevant state is distributed across the switches anyway.

The gateway has two essential reliability requirements:

Commands to the telephone system have to be retried quickly if a gateway fails.
Telephony events must not be lost.

The functional requirements were straightforward:

Incoming and outgoing calls (simple call control)
Call forwarding (single-step/two-step transfer)
Forwarding to the IVR (Interactive Voice Response) — including customer dependent data — as well as routing back to the same agent that originally took the call
Setting and displaying the agent status

Architecture

The architecture consists of several interconnected systems as shown in the diagram below:

The call center agents’ browser with the JavaScript/HTML,
Telephony-related systems (left): the gateway (a server-side web application running in Tomcat) and the PBX,
Call center web application (right): Wicket-based web application and its database(s).

The integration of telephony and web application happens in the browser. The web application includes our JavaScript library and a telephony control panel in an iframe.

The architecture of our CTI solution based on web technology.

Sending Server Events to the Browsers

For redundancy, every client connects to both gateways, and keeps the TCP connection open. This means that every application server (Tomcat) of the gateways has to hold nearly 1000 open connections. We use the AIO-Interface of Tomcat 7, so all these connections can be processed by a single thread. This greatly minimizes memory requirements and scheduling overhead.

Overview of our system architecture with redundant gateways and PBX systems.

Server-sent events (a.k.a. server push) was recently standardized as part of HTML5 in the EventSource interface. Another convenient method to implement bidirectional communication is WebSockets. But we couldn’t use any of these due to the use of legacy browsers — we were glad we didn’t have to support IE6 and could rely on at least IE8. So we implemented a COMET variant, which essentially consists of long running XMLHttpRequest through which events are sent as chunked responses.

The asynchronous events from the gateways are decoded by our JavaScript library, which updates the telephony control and forwards the events to the interface part of the browser, which in turn may trigger a server interaction.

Cross-Domain COMET with IE8

The customer wanted to be able to run the web application and the gateways on different application servers. This means that the Javascript XMLHTTPRequests are cross domain, which turned out to be a small challenge on IE8.

Mozilla Firefox, Safari and Google Chrome all support the CORS (Cross-Origin Resource Sharing) specification of the W3C. IE8 supports it as well; however, with IE8 one must use XDomainRequests instead of XMLHTTPRequests, and the API is slightly different. There is a also a subtle buffering bug within IE8 that makes it necessary to set 2 KB of fill characters on every new COMET connection to ensure that the next event is received by the application immediately.

Redundant Gateways and PBX

Each browser keeps two connections to two different gateways. One is active, and the other is a hot standby. When the connection to the active gateway is broken, the hot standby gateway is immediately activated. If necessary, the last failed command will be retried. As the hot standby gateway has been sending events the whole time as well, it is guaranteed that no event is lost. After this failover, the connection to the failed gateway is retried. When it is active, the previously failed gateway has become the host standby gateway.

Loss of a gateway does not lead to the loss essential state — the gateways hold as little state as possible. All relevant state was either pushed up into the JavaScript library or down into the PBX integration layer. The gateways are also independent of each other and interchangeable. This makes the solution inherently scalable. More gateways can be added at any time.

The PBX (a Genesys installation) itself is also redundant. The fallback on this level is hidden by the Genesys API and the gateway doesn’t have to handle it.

Testing

Our solution was tested with three different methods:

Javascript unit tests with QUnit,
A simulator that implements the gateway’s HTTP services and simulates a single agent telephone (with a Swing GUI), and
Load tests.

Writing the simulator was a substantial effort, but it helped in two ways:

It made development without the telephony hardware possible.
It made it easy to test scenarios that were not reliable testable with real hardware (like deliberate race conditions).

In an ideal world, the load tests would have been performed with an external load test tool. We didn’t have one available, so we wrote our own load test generator using the CSTA API to generate and receive calls.

Conclusion

Our solution is light-weight, conceptually simple and scalable. The simplicity is the result of two development iterations and rather long design phases.

The decision to use CSTA as the blueprint for the communication protocol worked well, too. It was helpful that we did not have to re-invent two-step transfer for the umpteenth time. Also, the CSTA vocabulary (which goes down to the text in the log messages) can be understood by personnel that are familiar with CTI.

In the Footprints of Arnold Schwarzenegger

Call center applications always remind me of a slightly silly movie starring Arnold Schwarzenegger as an undercover agent and Jamie Lee Curtis as his unsuspecting wife. His cover story for her is that he is doing something with IT and in one scene she inquires about his day at work. He starts telling her enthusiastically and quite elaborately about a call center integration — and she nearly falls asleep.

I, however, think the combination of a call center and a web application is technically quite fascinating.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Consequences when using Mutable Fields in hashCode() - Hacking Java Puzzlers for Fun and Profit, Part 1

Ulrich Schrempp — Thu, 08 Mar 2012 13:16:08 +0000

We start our new series with an informative HashSet puzzler. It’s about a bug that gave us quite a headache since its root cause was hard to identify. This subtle bug has without doubt crept into many code bases, so a detailed discussion should interest every Java coder. I will also discuss code inspection tools that detect this violation (sadly, only few). And by the way, what we learned about HashSet also makes a good topic in our job interviews.

The starting point was that we had implemented a class with some fields and needed quick access to its instances. This use case was pretty performance-critical, so we took a HashSet to maintain the class instances. As the instance count was high, we needed a broad distribution of possible hash-values. We used the IDE to generate code for the hashCode() and equals() method. Everything should have been fine with this generated code — at least we thought so. However, our application showed some unexpected results and it took us quite a long time to nail down the root cause.

Here’s a simplified example of code using a HashSet of PhoneNumber instances:

// Class PhoneNumber implements hashCode() and equals()
PhoneNumber obj = new PhoneNumber("mgm", "089/358680");
System.out.println("Hashcode: " +
	obj.hashCode());  //prints "1476725853"

// Add PhoneNumber object to HashSet
Set set = new HashSet();
set.add(obj);

// Modify object after it has been inserted
obj.setNumber("089/358680-0");

// Modification causes a different hash value
System.out.println("New hashcode: " +
	obj.hashCode()); //prints "7130851"

// ... Later or in another class, code such as the following
// is operating on the Set:

// Unexpected Result!
// Output: obj is set member: FALSE
System.out.println("obj is set member: " +
	set.contains(obj));

// Even stranger unexpected Result!
// Output: obj is set member: FALSE
for (PhoneNumber p : set) {
	if (p.equals(obj)) {
		System.out.println("obj is set member: " +
			set.contains(p));
	}
}

Executing the code above surprisingly produces the following output:

obj is set member: FALSE
obj is set member: FALSE

Obviously, what we would expect is a “TRUE”, since obj has been inserted into the HashSet.

What just happened?

The unexpected result from the code above is caused by a trap in the JDK Collections framework into which many developers have fallen: If an implementation of hashCode() uses mutable fields to calculate the value, HashSet.contains() produces unexpected results, i.e. your object seems to be not a member of the set.

For an illustration, let’s look at the class PhoneNumber and its mutable field “number”:

public class PhoneNumber {

    private final String name;
    private String number;

    public PhoneNumber(String number, String name) {
        this.number = number;
        this.name = name;
    }

	// Setter makes "number" mutable!
    public void setNumber(String number) {
        this.number = number;
    }

    @Override
    public int hashCode() {
        int result = name != null ? name.hashCode() : 0;
        result = 31 * result +
			(number != null ? number.hashCode() : 0);
        return result;
    }

	// equals() left out here ...
}

What’s wrong with this class? Well, it’s a bad idea to use mutable fields in hashCode() when its instances are put into a HashSet (or as keys into a HashMap). In general, any hash-based collection is problematic. See also “HashSet contains problem with custom objects” (Stackoverflow) and “hashCode() pitfalls with HashSet and HashMap”.

`HashSet.contains()` surprisingly uses `hashCode()`

Part of our problem to spot our bug was that the HashSet.contains() method relies on hash values to stay immutable. Unfortunately, this is not stated explicitly in the HashSet JavaDoc, which only mentions “…returns true if and only if this set contains an element e such that (o==null ? e==null : o.equals(e))“. Actually, this is the same description as the JavaDoc of Set.contains().

A conscientious reader may also find the following note in the JavaDoc of the Set interface, which only mentions equals():

“Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set.”

By the way, the following Sun JDK bug was reported quite some time ago: “(coll) HashSet.contains method violates Set.contains() contract”. The bug is approved (but not fixed) and the last comment was made in late 2007.

Properly coding the `hashCode()` method

The contract of hashCode() is explained in the JavaDoc of Object. You will also find hints on proper implementations in the very interesting book “Effective Java” from Joshua Bloch. The book covers many interesting topics and especially the items 7 and 8 shed light on good equals() and hashCode() implementation practices. Another book by the same author, “Java Puzzlers”, also contains two puzzlers on this problematic area: specifically, puzzlers 57 and 58 show how these two methods depend on each other.

There are many more discussions about the problems that can occur with hashCode(). For example, in his Google TechTalks presentation “How To Design A Good API and Why it Matters”, Joshua Bloch says that hashCode() is an implementation detail that should not have leaked into the Java API at all (at about 27:30 min).

And don’t forget the lesson learned here: using mutable fields in hashCode() is a recipe for disaster. And disaster strikes when instances of this class are put in a hash-based collection like HashSet or HashMap (as map keys).

Please note that since code usually uses only the respective collection interfaces, e.g. Set and Map, you might not even know about it (as in our case). Or you use a module or library that stores your objects in a collection internally as an implementation detail that’s hidden from you.

Don’t rely on automatic hashCode() Generation

Even with coding rules in mind, a hashCode() implementation that uses mutable fields creeps into our code base faster than you can spell “bug”. This is because developers are reluctant to write the long-winded calculations in the hashCode() methods manually and often generate them with the help of the IDE, as shown in the screenshot below. But it’s just too easy for a developer to press “Generate” without first checking the specific fields that can be included and leaving the mutable fields out. Of all IDEs I tested only NetBeans at least has all fields unchecked, which forces the developer to select them on purpose.

Modern IDEs provide automatic generation of hashCode(). Eclipse and Intellij IDEA by default include all mutable fields.

Code Inspection Tools to the Rescue?

You might wonder if classes of your code base contain an hashCode() implementation that uses mutable fields. One option (besides a manual code review) is using a code inspection tool. Unfortunately, the prominent open source tools like FindBugs, PMD, CheckStyle do not offer such a built-in inspection.

Only IntelliJ IDEA has a built-in code inspection that detects the use of mutable (actually non-final) fields in hashCode().

The only tool support I found was Intellij IDEA. This IDE provides a code inspection named “Non-final field referenced in ‘hashCode()’”. Any violation is highlighted as shown in the screenshot above.

(c) 2013 mgm technology partners. This posting "Consequences when using Mutable Fields in hashCode() - Hacking Java Puzzlers for Fun and Profit, Part 1" is part of the mgm technology blog. The author of the posting is Ulrich Schrempp.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Using Domain Specific Languages to Implement Interactive Frontends - Software Quality driven by Formal DSLs, Part 1

Dr. Jürgen Knopp — Thu, 16 Feb 2012 12:06:17 +0000

For many years we have dealt with the challenges that frontends with interactive forms pose w.r.t. validation, test data and quality. Describing the requirements in formal Domain Specific Languages (DSL) became the way of choice to create a specification that gives a twofold benefit: first, the customer understands it better, and secondly, the software engineers use the specification not only to implement more resilient software, but also to improve quality assurance. This new series will explain how we do it and why we think it’s the best approach.

We develop many applications for e-government, finance and insurance. These usually rely heavily on the presentation and evaluation of data processed within interactive frontends. Legal and business reasons demand that the resulting applications meet very high standards of reliance and safety. For us, this meant that we had to find a way to work close with the customer to understand the domain while simultaneously improving coverage and efficiency of development and QA.

We met this challenge by using Domain Specific Languages to involve the customer in the creation a specification basis for the domain which could be used by our engineers not only as requirement description but also for the implementation of tools for automatic validation or even code generation. The work spent on the definition, development and maintenance of specification language tools proved to be worth it as quality improved and effort decreased. E.g. while we were analyzing and reporting test coverage in terms of project specific formalized test data, we were glad that we could rely on a resilient specification basis.

Specifications based on a Domain Specific Formal Language bridge the gap between Customers and Software Developers.

The proven benefits of formal specifications at the comprehension level of customers encouraged us to bridge the gap in more mgm projects: we motivate more customers to introduce a formal requirement process and more engineers to a domain specific, though formalistic view of requirements so they can benefit from the improvements.

This first blog article introduces our domain specific formal language approach. The upcoming second part will focus on quality benefits derived from formal specifications.

Setting the Scene

The quality of complex interactive applications always includes a high level of conformity to the respective customer’s requirements. It is not enough to have a well-functioning system; the system also has to do what the customer expects! This holds for both, explicit and implicit (sometimes never formulated) requirements. We believe that the only way to accomplish this is to learn from the customer and to struggle for exact and comprehensive requirements consistent with the customer’s domain.

Requirements modeled by Domain-Specific Formal Languages

We believe that the need for exact requirements can be met by using formal languages to describe requirements. To model and implement what the customer needs (and not what we believe that he or she needs), the specification must be formulated using the terms of the respective domain and be comprehensible for the customer. We achieve this through the adaptation and extension of our existing language family to support the customer’s particular domain.

Requirements modeled for Frontends – at least

It is common sense to separate front-end aspects (such as input and output handling for forms) from the full business logic modeled somewhere in the back-end. The main purpose of front-ends is to deliver to the back-end information which is guaranteed to be sound and consistent. The back-end implementers should not be bothered by interactive aspects and user level data consistency.

Our Approach

mgm technology partners’ approach to form-centric applications was to implement a framework supporting specification languages along the full software development chain: editors, code generators, documentation and test data generators for the supported language family.

Whereever possible:

We use and promote formal specification languages for front-ends and part of the business logics.
We involve customers in the requirement process, especially through including formal specifications for their domains.
We tailor the specification framework to each of the customer’s specific application domain.

This yields a high return (for customers and mgm) in terms of delivery time and quality and, in addition, reduces the implementation and quality assurance effort.

Technical Benefits

The benefits of using formal front-end specification techniques are manifold:

Consistency of the customer requirements: It becomes very likely, that the system accepts and denies exactly what the customer expected (including implicit requirements which would have never been formulated in absence of formal specifications).
Reduction of programming effort and risk: Since formal specifications allow for automatic code generation, a great deal of programming effort and risk simply vanishes.
Increasing functional quality standards for the front-end: Obviously, generated code is consistent to specifications (once the code generator is mature and tested). Moreover, due to the formal description of legal inputs, test suites describing valid inputs are automatically generated.
Driving the tests of the back-end: Since the front-end specifications define the set of correct inputs, they serve as basis for tests for the back-end. Automatically generated test suites can be run which prove the quality of the back-end in a well defined setting. Test coverage goals for the back-end can be formulated in terms of the existing formal front-end specifications for the front-end. Test coverage becomes measurable in terms of front-end data and front-end use cases.

In this blog post we focus on the topics 1) and 2) described above. We do so by presenting a flavor of the used specification languages. Aspects 3) and 4) will be discussed in a second blog post.

Specifications supporting customer-related formal Requirements

In the following we will demonstrate how to derive a formal specification using mgm’s specification language.

An User Interface Example

Imagine a simple bill writing system based on a simple (e.g. web graphical) user interface where we will also need to consider both, calculations and consistency constraints.

Let us assume that a number of bill positions with a net unit price can be typed in, each of them with its own multiplicity (quantity) of at least 1. The system calculates the net price for each position as well as the baseline including the default or specific VAT (value added tax).

The input form might look as follows (we ignore GUI details in this example):

Sample form with input fields (yellow) and calculated fields (blue).

Input fields are marked yellow and fields which are to be calculated by the system (and thus are “read-only” for the user) are marked blue.

A completed form for two positions, with reduced VAT would look like follows:

Filled form with automatically calculated net and gross amounts.

Formal Specification for the Example

The specification language is now used to describe the properties of the fields, i.e. their types, the relations between their values and other constraints regarding consistency and completeness in a formal way. This approach is the core of the formalization of requirements.

Let us look at some formal specifications for the example above.

Types

Depending on the domain, fields have domain-specific types at user level. These types can be specified as numbers, currencies, date data, strings, enumerations and truth values. Most of them also include a specification of the allowed field length. For instance AlternativeVat is a positive numeric value with 2 digits which leads to the specification:

AlternativeVat: PositiveNumberDigits(2)

Some fields (e.g. all position related fields in the example) might have multiple instances. This is also specified along with the type definition. Multiplicity is specified as follows by using multi:

multi Position:     String(25)
multi UnitPrice:    EurosAndCentsDigits(8)
multi Quantity:     PositiveInteger(3)
multi PosFullPrice: EurosAndCentsDigits(10)

Fields values which are either subject to calculation by the system or which are given or by the specification are marked as calc or constant, respectively. Both kinds are not editable by the user (they are “readonly”).

calc       NetAmount:    EurosAndCentsDigits(10)
constant   NormalVat:    PositiveNumberDigits(2) = 19
calc       AllVat:       EurosAndCentsDigits(10)
calc multi PosFullPrice: EurosAndCentsDigits(10)

Functional Rules

Functional rules specify values in a functional setting.

For the fields AllVat and GrossAmount one gets straight-forward specification formulas:

AllVat = If FieldValueSpecified(AlternativeVat)
            then  AlternativeVat/100*NetAmount
            else  NormalVat/100*NetAmount
GrossAmount = AllVat + NetAmount

The semantics of these rules is intended to be functional rather than imperative, i.e. a field value is not influenced by any state aside from the occurring field values (Similar to formulas in spreadsheets or functional languages). Note that functional rules can also be used to specify mappings within the user interface, e.g. from drop-downs to textual representations.

Constraint Rules

Constraint rules describe constraints which have to be satisfied to ensure consistent inputs. They consist of

a conditional clause specifying the constraint, which the field values have to satisfy, and of
a fail-clause including a message which shall be issued if the constraints are not satisfied.

In this example, only specific VATs can be considered: normal VAT, half normal VAT or no VAT at all.

constraint
AlternativeVat == 0
   or AlternativeVat == NormalVat
   or AlternativeVat == NormalVat/2
   => failed: "VAT can only be normal, half normal or zero"

Note that the semantics is similar to assert statements: the failed-clause expresses feedback in case the conditional clause is not fulfilled.

Note further the differences between functional and constraint rules:

Unlike functional rules, constraint rules specify constraints (operationally expressed: checks) rather than computations. For syntactic differentiation, we use “==” here rather than “=“.
Functional rules do not have fail-clauses since they enforce values for fields rather than checking their relationship.

Rules for Multiple Instances

The language supports multiple instances of fields (and rules therefore) along two multiplicity dimensions – “All” and “Each”.

All-multiplicity for functional rules

For computations such as for the field NetAmount multiple instances have to be considered

NetAmount = Sum(PosFullPrice.all)

The “.all” next to PosFullPrice stands for an “all instances” semantics. We call this “all” multiplicity.

Each-multiplicity functional rules

Each instance of PosFullPrice is calculated in a homogenous way by multiplying the price with the quantity.

PosFullPrice.each = UnitPrice.each * Quantity.each

This functional rule yields for each row (i.e. instance), respectively and is denoted with the postfix “.each“. We call this each multiplicity.

This defines that the rule holds for each multiple instance of involved fields. Intuitively, one can view this as multiple copies of the rule for each instance.

Each-multiplicity for constraint rules

Consistency constraints for multiple instances of fields are expressed here as well.

In the example, it must be guaranteed, that each position (row) is fully specified. This is expressed with the specific predicate FieldsCommonlyDefined (using “each” multiplicity).

constraint
FieldsCommonlyDefined(Position.each, UnitPrice.each, Quantity.each)
    ==> failed: "All fields (Position , UnitPrice, Quantity) must be specified if one is specified "

All-multiplicity for constraint rules

Obviously, “all” multiplicity is usable in constraint rule as well. In the example, since the system should not print empty bills, one has to specify multiplicity greater than zero at least for one of the fields referring to positions.

constraint
AtLeastOneInstanceExists(Position.all)
    ==> failed: "Please specifiy at least one position"

This completes the example showing some of the specifications means. The full specification is given in the appendix. Since it is complete it can be used for automatic code generations for computations and constraint checking.

The aim of this short example is neither syntactic accuracy nor completeness. It is merely an illustration of important aspects. Please remember that each language of the Specification Language family is tailored specifically anyhow.

Summary: Characterization of the Specification Language Family

In a nutshell, the specification language family described above defines valid inputs and front-end computations for web applications or other form based systems. The formalism can be characterized as a subset of typed predicate calculus defined in terms of the customer domain. For the sake of simplicity and comprehensibility, we do not extend to full predicate calculus or to higher order logic. The pragmatic expressiveness of the language family is more important than the theoretical power of predicate calculus.

Here is a summary of the aspects which can be described.

Typed field: Valid and invalid field value using field description.
Field-value-constraints: valid and invalid values for related fields.
Existence-constraints: validity and invalidity of existent and non-existent input value depending on values or existence of input value for other fields.
Both kinds of constraints can be interwoven.
Computation of field values based on other field values. This is expressed by rules including:
- mapping of external presentations to internal ones (such as mapping drop down selections to values),
- constant values which show up in the user interface,
- conditional values.
Multiplicity: fields may be defined to occur in several instances, controlled by the specification. In terms of constraint control this allows to express iterative aspects on a higher level than for single fields. There are multiplicity aspects expressible by the specification language family (not needed in this example). This, however, is beyond the scope of this paper.

And here’s the full specification example:

# Fields and Types:
multi      Position: String(25)
multi      UnitPrice: EurosAndCentsDigits(8)
multi      Quantity: PositiveInteger(3)
multi      PosFullPrice: EurosAndCentsDigits(10)
           AlternativeVat: PositiveNumberDigits(2)
constant   NormalVat: PositiveNumberDigits(2) = 19
calc       NetAmount: EurosAndCentsDigits(10)
calc       AllVat:  EurosAndCentsDigits(10)
calc multi PosFullPrice: EurosAndCentsDigits(10)

# Functional Rules:
AllVat = If FieldValueSpecified(AlternativeVat)
            then AlternativeVat/100*NetAmount
            else NormalVat/100*NetAmount
GrossAmount       = AllVat + NetAmount
NetAmount         = Sum(PosFullPrice.all)
PosFullPrice.each = UnitPrice.each * Quantity.each

# Constraints:
AlternativeVat == 0  or  AlternativeVat == NormalVat
      or  AlternativeVat == NormalVat/2
      => failed: "VAT can only be normal, half normal or zero"
FieldsCommonlyDefined(Position.each UnitPrice.each, Quantity.each)
      => failed: "All fields (Position , UnitPrice, Quantity) must be specified if one is specified "
AtLeastOneInstanceExists(Position.all)
     => failed: "Please specifiy at least one position"

Development and Testing issues

Due to formal specifications, both, software development and quality assurance become less cumbersome, more comprehensible, easier to track, more scalable and safer. We conclude by shortly sketching these aspects.

Avoiding Implementation Efforts and Risks through Code Generation

Similar to programming languages, specification languages substantially simplify software development. Code generated from specifications eliminates a great deal of complexity and leads to less error-prone systems. Both functional rules and constraint rules can be used as input for generators to generate fully operational code. This is a highly efficient way to automatically produce components for the validation of data in a complex solution environment.

Once the code generators are well tested there is not much need to test for each front-end application again. mgm technology partners developed code generators that generate code for Java, C++ and Javascript, each of them running in a variety of environments.

Test Data Generation and Test Coverage

Since the used specification languages describe well defined inputs they are an ideal prerequisite for test data generation: consistent test cases are generated directly from the specification due to

the existence of type definitions for fields,
the existence of constraint rules describing the relationship between fields,
and the existence of calculation formulas for calculated fields values.

Test data generation occurs with few exceptions fully automatically. For specific test cases it is also possible to automatically generate inconsistent data by deliberately enforcing wrong data. This is done by negating constraints and re-running the test data generator.

mgm technology partners has developed a test data generator suite based on the used formal languages. The tool is used for the generation of big and complex test cases allowing for extensive and well defined test coverage. Some insights can be found in our blog articles “Form Validation with Rule Bases“, and in “Producing High-Quality Test Data“. Test coverage and other quality assurance topics issues will be highlighted in the upcoming second blog article.

(c) 2013 mgm technology partners. This posting "Using Domain Specific Languages to Implement Interactive Frontends - Software Quality driven by Formal DSLs, Part 1" is part of the mgm technology blog. The author of the posting is Dr. Jürgen Knopp.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Ultra-Performant Dynamic Websites with Varnish

Dr. Christian Winkler — Mon, 30 Jan 2012 11:41:25 +0000

This article describes how we configured and used the Varnish web cache for the popular German online shop www.lidl.de. Varnish gave us a tremendous performance boost. With this new caching setup, we easily achieve request rates of several thousand pages per second, which are quite common during marketing campaigns like special offers.

In a typical non-caching setup of a web application as illustrated in the figure below, Apache handles static requests for images, scripts, etc. and forwards requests for the HTML pages to an application server like Tomcat or Glassfish. There the dynamic content is generated and then sent back to Apache and finally to the user. In this scenario, the database access is the most critical bottleneck. Even worse, each page request can cause multiple database requests, i.e. SQL statements.

Initial setup without our caching solution: the slow components are shown in red. (Load balancing, which could be done by Apache, is not considered here.)

Let’s assume that without caching, an application server can serve up to 100 dynamic pages per second. Through a bit of vertical scaling, i.e. using two server instances (nodes) and load balancing, this can be increased to about 200 dynamic requests. However, this scalability is not perfect and once it grows to three and more nodes, it already starts to get worse as the sessions have to be distributed among the nodes in the cluster.

The system can of course handle many more simultaneous users than the number 200 suggests, as users do not permanently access links. So the number of users did not really pose a problem during normal operation. However, the situation immediately got critical when newsletters with special offers were sent, as the application server instances were now under “siege”. An overload of the instances led to slower and slower responses and decreasing customer satisfaction. Another reason a shop would want to be responsive, is that search engines consider measured response times during crawling for ranking search results.

So the question we had to solve was: How can we keep the system responsive (ideally with a response time of 1-2 seconds) during high load and peak situations? Please be aware that in the case of online shops, the highest turnover occurs in these situations.

When we analyzed the server log of the www.lidl.de online shop, we noticed an interesting fact, which we used to our advantage later on: the behavior of users is different in these situations. Most users are just browsing and reading. Consider e.g. a newsletter sent to a few million users: most of the readers will just click a few links (which can still easily amount to several million page impressions). Taking a deeper look we found out that most users are viewing absolutely and exactly identical content which has nevertheless been produced exclusively for them. Only a small percentage used the interactive services of the website like shopping carts, ordering etc.

Introducing Varnish

The peak situation described above implies that most content (even though dynamically generated by the web application) is identical for all users. So the obvious idea for a cache is to store the most frequently requested pages. The Varnish manual describes Varnish as a lightweight, efficient reverse proxy server, meaning it is working in front of the web servers (Apache). It acts as a so-called HTTP accelerator which stores (caches) copies of the pages served by the web server (thus the synonym “web cache”). The next time the same page is requested by a user, Varnish will serve the copy instead of requesting the page from the Apache server. Varnish is blazingly fast, since it stores its cached data in memory.

The new architecture with Varnish as a web cache now looks like this:

Varnish in front of Apache acting as a Web cache. It is configured to cache only stateless page requests. Stateful page requests (session) and static resources are forwarded to Apache.

Performance Improvements

Caching with Varnish removes the need for the web application to regenerate the same page over and over again, resulting in a tremendous performance boost. Varnish can easily handle 10,000 requests/s on a single node. Especially in high load situations the hit rate is easily above 90% (and almost 100% for the mostly clicked homepage) so that the setup described above can now handle 50 times the original volume. However, this high performance will only hold for stateless users. Any user with a session will fall back to the 100 requests/s class.

As most of the load is now taken by the Varnish cache servers, the load on the application servers has dropped considerably. Even in high load situations where the Varnish servers handle several thousand requests per second, most of the content comes from the cache and the application servers can concentrate on re-creating expired content (which is then kept in the cache for s-maxage seconds) and handling users with a session (who are hopefully going to order).

Our setup leads to a significantly improved end-to-end performance of the system – even during normal operation. This is interesting as it creates an advantage for users during normal operation and saves money for the website owner at the same time.

Using less hardware means investing less money initially. However, an even more important fact is, that the operating costs will also be much lower. These operating costs are caused by permanent maintenance of the system, like powering servers around the clock, updating, applying patches etc. Since these costs are the main drivers for the total cost of ownership (TCO), the potential savings are also largest in this regime.

Using fewer servers also means consuming less power. By reducing the energy bill this “green IT” approach therefore leads to lower operating costs. Compared to extending the existing system without a cache, an enormous amount of money was saved both in hardware and operating costs, while introducing a “performance buffer” for situations with even higher loads at the same time.

Another effect is that the shop’s marketing division can now act freely without having to keep technical constraints in mind: new campaigns can be planned to increase the turnover significantly, like sending more frequent newsletters, using special offers etc.

Challenges

Before we dive into the details of our Varnish configuration, let’s first discuss three problems we had to solve, specifically handling stateful users, keeping users stateless w.r.t. caching as long as possible, and caching pages with changing content.

Problem: Websites are Stateful

Most websites nowadays are stateful, e.g. a server-side session is created when a user logs in. In case of an online shop, the session might contain the shopping cart, login information etc.

The problem is that as soon as the session contains personalized information, caching must immediately stop. But, as long as state information does not have an effect on the content of generated pages, it can be ignored. This is what we call a stateless or browsing user, and our first objective should be to cache pages suitable for this user class.

Thus, our solution is to classify users, i.e. to carefully distinguish between stateless and stateful users. As the web application did not originally take care of that, it had to be changed in two fundamental ways:

The application must only generate and send cookies if it has created some internal state for a user.
This state transition can happen at any time. So a user who has not even touched the application server and is completely unknown to the application must be able to become a stateful user at any time.

Two classes of users are distinguished by certain attributes. A user should stay stateless as long as possible. Stateful (red) users will need contact to the application server and experience slower performance.

Fortunately, the web application was already obeying the REST paradigm. HTTP GET requests were used for all content that was just shown to the users. In contrast to this, all user actions which were actually creating some state on the server side were already modeled in HTTP POST requests. This proved to be extremely helpful when we started to configure the cache software.

Keeping Users Stateless

The general goal must be to keep users stateless, at least as long as possible. In a first naive approach, only this facilitates caching.

Keeping users stateless means that the server should never send a session cookie unless really necessary. On the other hand, a lot of web applications require some basic personalization. This dilemma can be solved by using cookies which will be evaluated on the client side only. For example, let’s assume that users can change the background color of the website as a very simple form of personalization. This can be performed by Javascript and, for the sake of caching (and achieving a high hit rate), this should be the preferred way of doing simple personalization. Of course, a server-side cookie for personalized background color could be used to get the same result. But the cache hit rate would then suffer considerably (to be exact, by a factor identical to the number of background colors, since exactly the same amount of cached copies has to be saved).

So one recipe for staying stateless is to keep simple state on the client-side and never send it to the server. This state does not necessarily have to reside in a cookie – you can also use the browser local storage for that, as described in Smashing Magazin’s “Using Local Storage In HTML5-Capable Browsers” article.

Dealing with Content that is Changing

Even if now all stateless users can see the same cached content, this content is changing over time. In an online shop, for example, some products might run out of stock and become unavailable or need to be replaced by other products. Unfortunately, this does not only affect the product pages themselves but sometimes also pages that reference them; e.g. links and thumbnail images will have to be changed or removed. Similar situations often occur in online publishing and in nearly all websites which change over time.

Thus, another requirement for the cache is its ability to partially expire content. And of course, the bookkeeping must be performed externally so that the affected pages can be removed individually.

For the cache to work properly and perform automatic expiration of content, it needs to know how long the currently cached content should be kept (i.e. its maximal age). The web application therefore has to generate this so-called time-to-live (TTL) information.

The HTTP specification has defined HTTP response header fields such as Cache-Control for exactly this purpose a long time ago. These are set by the web application itself, since it knows best how long the content will be considered “current”/”valid”. This setting could even be dynamic , e.g. giving a shorter time-to-live to a product page if stock is low. The Cache-Control directive most suitable for this purpose is s-maxage as it specifies the maximum age of the object in seconds that the response is allowed to be kept in the web cache.

Determining Cacheable Candidates

Not all content can be or even should be cached. Caching on completely static websites is easier by far, however, these tend to be very unattractive, could be pre-generated and then moved to the web server. As the cache will sit in front of the web server, all requests will go to the cache first. It does not make much sense to store pages in the cache which are kept statically in the web server’s file system anyway.

On the other hand, only GET URLs can be candidates for caching. As a POST request transmits information from the browser to the server, it cannot be cached and must always be handled by the application server. This might sound like a big constraint at first but is actually a feature that can be nicely utilized: all URLs which are candidates for performing the state transition of a user from stateless to stateful will be POST requests. And consequently, the application itself can decide whether the POST requests actually qualify for making a user stateful or whether s/he can remain stateless, for example when a wrong login/password combination is entered.

Anatomy of Varnish’s Request Processing

Varnish distinguishes three stages when processing a request:

The request is received from the browser (vcl_recv).
At this stage, Varnish calls the subroutine vcl_recv in the configuration file (VCL). Here, the request header can be manipulated e.g. by removing cookies. It can be decided whether the content should be looked up in the cache or be propagated to the backend server.
The response is received from the backend (vcl_fetch).
This function is only executed when the content is not delivered from the cache. In this phase, response headers from the backend can be modified (either for delivery or for saving in the cache). The request attributes are also still available and can be used for manipulating several settings.
The response is sent to the browser (vcl_deliver).
This stage is passed by all requests and can be used to add headers (like TTL), change cookies etc. The request parameters are available for reading.

Different stages of Varnish's request processing. Everything related to the cache is in red, i.e. all cacheable content is looked up in the cache and possibly delivered; if it's not in the cache, the web server will be asked via vcl_fetch.

Varnish defines additional subroutines which also hook into the Varnish workflow, but they are not as important. See also the VCL tutorial and the VCL reference.

A Sample Varnish Configuration (VCL)

This section contains a simple Varnish configuration that provides caching as required. The challenge is to keep the user stateless as long as possible. In order to achieve this, a simple trick is used: if a request does not contain a JSESSIONID cookie, it is a stateless request and even if the (uneducated) backend wants to set a cookie, it will be removed. Only POST requests will set necessary cookies. Manipulating the TTL compliments the configuration. A lot of logging is used in the example; this is not just for illustrative purposes but also practical for debugging and optimizing the configuration.

import std;

backend default {
    .host = "localhost";  # Varnish is running on same server as Apache
    .port = "80";
}

sub vcl_recv {
  # remove unnecessary cookies
  if (req.http.cookie ~ "JSESSIONID") {
    std.log("found jsessionid in request, passing to backend server");
    return (pass);
  } else {
    unset req.http.cookie;
  }
}

sub vcl_fetch {
  if (req.http.cookie ~ "JSESSIONID" || req.request == "POST") {
    std.log("not removing cookie/passing POST, url " + req.url);
    return (pass);
  } else {
    # remove all other cookies and prevent backend from setting any
    std.log("removing cookie in url " + req.url);
    unset beresp.http.set-cookie;
    set beresp.ttl = 600s;
  }
}

sub vcl_deliver {
  # send some handy statistics back, useful for checking cache
  if (obj.hits > 0) {
    set resp.http.X-Cache-Action = "HIT";
    set resp.http.X-Cache-Hits = obj.hits;
  } else {
    set resp.http.X-Cache-Action = "MISS";
  }
}

Notice the C-like syntax in the Varnish configuration. This is no accident; in fact, the whole configuration code is compiled to a binary shared object at startup and when reloading the script to optimize for performance. As the subroutines in this configuration are called for each request, this helps immensely in creating a fast cache server. Moreover, it is possible to add C code directly to the configuration.

It might seem strange at first to define the configuration in a procedural language, but it proved to be extremely valuable as it enables us to be flexible and to formulate how exactly to handle the requests. Overall, this leads to a much more readable configuration than a declarative approach.

Notice the different “top level” objects in the configuration file:

req is the request (i.e. the URL including all headers) coming from the browser,
resp is the response before it is sent to the client, i.e. when it can still be manipulated.
beresp: The response which Varnish gets from the backend (if the object is not cacheable or not cached) is also available as beresp and can be evaluated.

On a side note, Varnish can use ACLs to restrict the access to certain resources. The same ACLs can also be used to (declaratively) tell Varnish what to cache and what not. This technique is the sometimes used “banning”. Varnish can also (atomically) delete certain elements from the cache. This is accomplished via a “purge” command through the HTTP interface and should be restricted to IP addresses (which is the standard configuration together with a secret).

Configuration Details and Tips

Now that we have seen the basic VCL file and understood how a request is usually processed, let’s dive in even further and discuss the details and lessons learned.

Improving the Hit rate with Header Normalization

Varnish has to be told which HTTP request header fields it should use as a cache index. The index is organized as a hash, thus these selected header fields are often referred to as the hash key.

On a side note, you can select the header fields to be used as a hash by implementing the subroutine vcl_hash. If you don’t implement it, Varnish uses the full URL plus the Host request header field by default. In addition to the hash key computed in vcl_hash, the Vary header field is always automatically added to the hash key . For further information on the hash key, see “What Varnish Does” and “Varnish and http header” on Stackoverflow.

To improve the cache hit-rate, it is crucial that you clean up the request header fields used for the hash key. Cleaning up means to change them to a common denominator (so-called header normalization). Another very good candidate is of course the Host header field, where a normalized version (like “www.sitename.com”) should be used even if “sitename.com” is sent in the request header. In addition to that, removing unnecessary headers is always a good idea.

Be careful that the application server does not send a Vary header field for the user agent as this effectively means that there has to be a distinct copy for each user agent. There are so many different browsers (http://panopticlick.eff.org/) that this will basically make caching useless. See also “Understanding the HTTP Vary Header and Caching Proxies (Squid, etc.)” and the
Varnish Documentation on Vary.

Compression

The Accept-Encoding request header field plays an important role: it can have different values like “plain”, “gzip” or “deflate”. Unfortunately, Internet Explorer prefers the deflate encoding while all other browsers favor gzip. Without intervention, this leads to different copies of the same content in the cache, one in deflate format, the other in gzip format.

Since the request header can be modified on the fly in the vcl_recv subroutine, we can effectively control that only one variant of the content is cached. In your VCL you can modify the request header field and use gzip exclusively if it is available (which is true for both Internet Explorer and others). This technique is presented in detail in the article “Normalize Accept-Encoding header”. Since both browser families have a market share of roughly 50%, this simple change effectively doubles the hit rate.

Please note that beginning with Varnish 3.0, Varnish supports gzip natively and can modify the Accept-Encoding field by itself, so the measures discussed in the previous paragraph can be skipped.

Handling Cookies

Cookies basically fall into different categories:

Cookies relevant for caching: These should be kept and their values can be used as part of the hash key for cache index.
Cookies irrelevant for caching: These should be discarded and not considered by the cache.
Cookies partially relevant for caching: These should be modified and the irrelevant parts should be removed. The remaining cookie should then be used as part of the hash key for the cache index.
Session cookies: These cookies must be treated differently as they basically make caching impossible. If such cookies are detected, Varnish should not cache anything but work as a proxy only sending data from the backend server directly to the client.

Consistent Values for TTL and the Expires Field

Varnish has to decide whether and how long to keep elements in the cache. As we have already learned, the Cache-Control header field is utilized here. More specifically, the s-maxage directive part (or maxage as a fallback if s-maxage is not present) is examined to determine the specified maximum lifetime of a cacheable object. Of course, this only works as long as the cache is not full; in the latter case the LRU algorithm is used.

If the web application was not designed with a web cache in mind, it might have conflicting values in s-maxage and the Expires response header field. (See the HTTP specification for a discussion of the Expires versus the maxage field.) This might lead to the bizarre situation that the cached content is sent by Varnish with an Expires header field value that lies in the past if s-maxage has a larger value than Expires.

This weird behavior can be fixed in several ways, e.g. by statically setting the Expires header in Varnish for each request to s-maxage seconds into the future during “vcl_fetch”. This will increase the cache efficiency on the browser side and lead to a more responsive website.

File Descriptors

In our first tests the solution performed well, but not excellently. But even more critical were the many dropped connections, i.e. requests from browsers that did not even reach Varnish.

The reason and the fix were easy – the number of file descriptors had to be increased. This is even more important in real-life situation where connections tend to be slow, as each TCP connection consumes one file descriptor. It does not hurt to allow 32768 descriptors for Varnish.

Monitoring

If you have setup a web cache solution with Varnish, it is important to measure its performance and especially monitor the hit rate of the cache. This turns out to be a bit complicated since the Varnish log files are not written to disk for performance reasons; instead of this, Varnish logs to a circular buffer residing in a shared memory segment. The circular buffer can be read at any time but past values will vanish forever. Since we wanted a monitoring solution that would also allow us to perform a post-mortem analysis in case of a problem, we configured the logging to write the circular buffer to a persistent file.

The most relevant tools for monitoring Varnish are:

varnishlog: This shows current requests from the logging ring buffer. Usually request phases will be shown in chronological order which mixes up the requests themselves. This can be fixed by using appropriate options though.
varnishtop: This shows the CPU distribution inside the varnish process and can be used to optimize the configuration if too much time is spent in only a few functions.
varnishhist: This is easily the most intuitive and graphical tool for analyzing Varnish. It shows a (text) histogram of the response time distribution and thus gives a good overview how the whole system is performing.
varnishstat: This shows important statistical information about hit rates, total cache hits, accepted connections from clients etc.

Why Varnish is the best Caching Solution (for us)

When we began to investigate ways to speed up the www.lidl.de site, our first choice was to add the Apache mod_cache caching module to the Apache web server already in use. The first hurdle was the declarative configuration; it is well-suited for a web server but not perfect for modeling a caching behavior. After some fiddling around, it was working smoothly. But more serious problems arose from the fact that certain cookies had to be considered and others had to be neglected. It was impossible to find a viable solution, so the cookie was filtered out by the load balancer. Cache invalidation is performed lazily in Apache, i.e. an outdated resource is removed from the cache only after it is requested. Consequently, outdated resources which are not requested will stay in the cache forever and can only be expired externally. As all cached components are distributed in single files, this expiry is slow and the whole process complicated. For our situation, Apache was not a good solution (although it was in use for quite some time) and hit rates were also rather disappointing.

So our search continued. Via dedicated proxy servers, which are more suitable for large client-side installations like Squid, we finally encountered Varnish, an HTTP accelerator specially built for caching purposes on the server-side. Varnish is already used by many big websites like Facebook, Twitter (Search), Hulu.

Varnish is very flexible as it offers procedural configuration of all request stages in a C-like language (which is actually translated to C and compiled at start time to be as efficient as possible). This enables creative cookie handling and all kinds of other tricks which are usually needed in such a scenario. Varnish was specially designed to run on servers with a VM subsystem, so all cached objects live in a single memory-mapped file and can be accessed extremely fast. Varnish handles expiry automatically and correctly and is even much faster than Apache. So the decision was made to go with Varnish.

Other HTTP accelerators were also considered, but proved to be not feasible, like Oracle Web Cache, a commercial software package from Oracle Inc.; the problem here is that the cache cannot grow easily, and that the manipulation of requests and responses is limited. A hardware-based solution is e.g. F5’s BIG-IP WebAccelerator.

Further Optimizations

Below is a discussion of measures that build on a Varnish setup and would speed-up the page delivery even further.

Using a CDN to increase Scale, Reach & Performance

CDNs take care of delivering the static content while the dynamic content is served via the usual stack. They work in an inherently distributed way and have clever algorithms to select the topologically nearest server for each user. Static and dynamic content can be separated by using virtual webservers with different hostnames. The PDF article “Globally distributed content delivery” from Akamai provides an excellent introduction.

Most CDNs offer an API for invalidating all or partial content and respect the expires header field sent from the originating servers. So the Varnish server can work as a central content repository and will be the upstream server for refreshing the CDN.

Almost all traffic would then be served by the CDN. This saves a lot of bandwidth on the Varnish server and the Gigabit interface will not so easily be overloaded. Moreover, as traffic costs in the CDN are negligible, money can be saved as the hosting company does not have to increase its own upstream link. For more information on how to build a CDN see “How to build your own CDN using BIND, GeoIP, Nginx, and Varnish”.

ESI: Caching Page Fragments with diverse TTL

From a technical point of view, only pages which are requested by the GET method can be cached at all. This is due to the fact that – by definition – POST requests change state on the server which then necessarily needs to reach the application server.

However, the solution described above performs less “aggressive” caching since it just stops caching as soon as a session cookie is present. The effect is that stateful users never get cached pages and therefore might have to wait longer for the page to render completely. On the other hand, it does not make sense to cache pages for individual users since it is quite unlikely that the same user will come back to the exactly same page. Even if the user would come back, it would not be safe to assume that the page is still up-to-date (e.g. since the shopping cart might have changed in the meantime).

To speed things up again, a compromise needs to be found between caching invariant fragments of a page and producing personalized content on the fly for stateful users. Fortunately, Varnish offers the correct arsenal to perform exactly this decomposition by leveraging Edge Side Include (ESI).

When Varnish processes ESI tags, the page assembly (out of fragments) is done by Varnish. As these fragments are separate web resources (requested through GET or POST) they can be assigned their own cache settings and handling information. For example, a cache time-to-live (TTL) of several days could be appropriate for the template, but a fragment containing a frequently-changing story or ad may require a much lower TTL. Some fragments may have to be marked uncacheable.

It must be carefully analyzed how the decomposition of the page might look like as getting it right is essential to achieve a high hit-rate and a low overhead. In case of an online shop, the page could e.g. consist of different (graphical) fragments:

Decomposition of a typical page into user-specific, dynamic (red) and static (blue) fragments.

The shopping cart and the login details would then be transferred directly from the application server via an appropriate ESI fragment, whereas the rest of the page is identical for all users and can be stored in the cache. To minimize the number of requests from Varnish to the application server, both fragments can be transferred in one part and integrated in different locations on the page on the client side or via CSS.

Compared to the performance numbers above, the stateful performance is much higher when using ESI. Rates of about 500 stateful requests per second are now easily possible.

Memcached: Caching Session-specific Page-Fragments

If you examine the page diagram above, you might notice that even though the shopping cart and login details are user-specific elements on the page, they are not very dynamic, i.e. they change infrequently.

This leads to an opportunity for further optimization: the user-specific fragments can also be stored, but must of course be associated with the session of the corresponding user. As the information is not persistent (as it becomes invalid with an invalidated session) it can be stored in memory. Memcached is just made for this scenario and therefore a perfect fit, see e.g. the article “Storing Sessions in Memcache”.

Any change in the shopping cart or login details will trigger a regeneration of the HTML fragments which will then be stored in memcached. (This can be done in the same POST request by the application server.) Varnish will include the fragment from Memcached (either via direct integration, via Apache or via Nginx). A SessionListener within Tomcat can take care of removing stale sessions from Memcached.

Memcached is extremely fast. Even for stateful users this leads to a performance of well above 5,000 GET requests/s. POST requests are a different story as they still have to be handled by the application server. As they perform only internal tasks and write both to the database and Memcached, a rate of 500 requests/s is nonetheless realistic.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.

Practical Customer Participation in JIRA Workflows - JIRA beyond Bug Tracking, Part 2

Alexander Weiss — Thu, 08 Dec 2011 15:43:19 +0000

This second part of our blog series continues with the topic of direct involvement of customers and gives some practical examples of when, where and how to introduce and include your customer into JIRA. We will then discuss two of mgm’s proven real-world workflows and use them as case studies about appropriate modes for successful customer participation. You will also learn about our recommended ways of keeping the complexity of huge JIRA projects from the customer.

Let’s begin with how JIRA can be utilized during the initial project phases. The main steps here are to prepare a more detailed business modeling and to complete the technical and business concepts. These steps are tightly connected with the compilation of the requirements and the requirement management phase. The requirement analysts of the project and the responsible project manager will interview all the necessary stakeholders to get a complete picture of the required solution that the business modelers and architects need for their work.

Capturing Requirements as JIRA Tickets

During this requirement management phase all the collected functional and non-functional requirements will already be stored as JIRA tickets to control their content and impact and to prioritize them with respect to the solution and its implementation order (planning process). And exactly this phase can be used to create a first contact point for customers with JIRA: Involvement in the compilation of new requirements and detailing of already filed items.

But as the customer is not yet very familiar with JIRA in this very early stage, we typically choose to create all the new requirements tickets ourselves instead of the customer. This is not just to unburden the customer: we also want to avoid the additional work of correcting imprecisely formulated requirements.

The descriptions of requirement tickets should always be unambiguous and complete. Thus, the responsibility to verbalize requirements usually remains with us. But the customer can be involved at any time to contribute details and he can (and should) be an active part during the elaboration phase and deliver his input and expertise through comments to the respective tickets.

Another very important point in requirement management is the used terminology. It is very important to always talk (and to write) the customers’ domain specific language. Use only terms that can be understood by the customer! We find it very helpful to maintain a glossary of all domain specific words and terms together with the customer.

Customer Involvement in the JIRA Requirement Process

In addition to detailing the content of requirements and ensuring their correctness, the customer can take over two other important tasks in the requirement process:

Assignment: Once a requirement is elaborated, the effort estimated and it is ready for realization, it has to be assigned to the supplier (us) for release planning and implementation.
Approval: When the requirement is implemented and approved by the development team and our internal quality assurance, the realized requirement is ready for approval by the customer.

Both of these steps (assignment and approval) can be realized as workflow steps for the issue type “Requirement”. Dependent on the character of the project and customer, mgm runs projects with different levels of integration.

Proven Workflow Implementations

Let’s take a look at two requirement workflows that we designed for our projects, each with a different integration level of the mentioned steps.

Workflow 'Requirement' with dedicated customer steps for assignment and approval (Variant 1).

This first workflow (shown above) contains a dedicated step to alert the customer that the requirement is “READY TO ASSIGN”. On his dashboard the customer has a portlet listing all these ‘marked’ requirements as a working queue for assignments!

It is not strictly necessary that the customer himself executes the transition “assign” in JIRA. We have projects where the requirement assignment is officially sent via mail or e-mail by the customer. In these cases, our requirement manager performs the transition on behalf of the customer. But we also have projects where the customer himself pushes the “assign” button in JIRA.

Following the implementation part with the steps “IN PROGRESS”, “RESOLVED” and “CODE-REVIEWED”, the requirement workflow contains the steps “READY FOR TESTING” and “VERIFIED”. During the software approval stage the customer can use these dedicated steps to manage his testing and approval tasks. Once again, the needed filters are integrated into the customer dashboard. The development team will explicitly hand over all implementations that passed internal quality assurance to the customer. The approval transition “VERIFY ISSUE” will then be executed by the customer himself. Usually we convince the customer to do this directly in JIRA.

In this first example, the step “REVISION” of the requirement (the elaboration phase) is separated from the step “ESTIMATE”, thus the customer will keep the control of ordering the effort estimations.

Now let us consider a second workflow example as depicted below:

Workflow 'Requirement' with dedicated customer steps for assignment and approval (Variant 2).

The interesting parts here are the initial step “DRAFT”, the step “ANALYSIS” (before “REVISION”) and the approval step “SIGNED OFF”. The “DRAFT” step is especially useful if customers create requirement tickets by themselves. The distinct step “ANALYSIS” is an independent elaboration and phrasing phase for the customer (typically when they have a dedicated operations department) whereas the step “REVISION” is an elaboration phase for the project team (development). At the end of the whole implementation process the customer can use the step “SIGNED OFF” for the approval process.

Overview: Where and How to Involve the Customer

Requirement management is an obvious area for direct participation of customers, but more traditional areas like “bug tracking” and “change management” are also potential candidates for customer involvement.

Below is a collection of areas where we constantly try to convince our customers to participate directly within our established JIRA processes:

Requirement management
- Input of new requirement tickets
- Direct participation in the elaboration phase (optionally with additional workflow steps)
- Assignment for realization (workflow steps)
- Testing and approval of implemented requirements (workflow steps)
Change management
- Input of new change request tickets
- Direct participation in the elaboration phase (optionally with own workflow steps)
- Assignment for realization (workflow steps)
- Testing and approval of implemented change requests (workflow steps)
Bug tracking
- Input of new bug tickets
- Testing and approval of fixed bugs (workflow steps)
Software approval process
- Execution of dedicated testing tickets
- Approval of all individual development tickets (requirements, change requests and bugs) (workflow steps)
- Issue the final software (or release) acceptance (workflow steps)

The “Change Management” process has to be aligned with the customers’ organization structure and change process. We experienced that especially change management is in most cases an already well defined process at the customer side. However, for “Change Management” we can typically apply the same workflow as for “Requirements”.

“Bug tracking” nowadays follows standard workflows. But bug tickets are also development tasks, i.e. changes to the product/source code. Thus, we extended the bug workflows with steps representing the approval and quality assurance parts (“READY FOR TESTING”, “VERIFIED” and “SIGNED OFF”) as well. This applies to all issue types leading to development activities where requirements and change requests just represent the controlling/management part and not the realization part, e.g. Requirements, Change Requests, Bugs and dedicated implementation tasks.

Dedicated JIRA Projects for the Customer and Development

Sometimes the periodic amount of JIRA tickets (e.g. needed for a software release) exceeds the “pain” threshold (typically > 300 per release) and the customer is beginning to loose the project overview and feels lost in the overwhelming amount of requirements, change request, bugs, QA tasks and tasks in general. Our recommendation for these cases is to split it up and create 2 dedicated JIRA projects:

Customer facing project: Used for all operational bugs and incidents (source: customer and end-user), comprises the complete requirement and change management and the software approval process.
Development facing project: Used for all bugs during the development phase, all implementation tasks derived from requirements and change requests, development internal quality assurance tasks, all tasks that are related to the project in general, etc.

Splitting up a JIRA project into a dedicated JIRA project for the customer and another one for the development.

The ticket handling is very easy: Assigned requirements within the customer project are just cloned and moved to the development project. The original and the cloned requirements are then automatically linked by JIRA. In the development project you can then create the appropriate division into implementation tasks needed for your team and component diversity. The status update of the customer’s source tickets (linked tickets) has to be done manually.

The development project is typically only visible for the development team and not for the customer. When we did this in the past, the customer’s initial doubts that we just want to hide information from him could always be resolved by simply opening the development project to him and showing him the hundreds of (open) tickets. Normally he would loose interest in this project very quickly because he is not getting any additional benefits out of it. On the contrary, he will be getting rather confused by the amount of information.

We’ve made really good experiences with the concept of 2 dedicated JIRA projects for the customer and the development, respectively. But there is a second way to remove redundant information from an overstrained customer. You can use JIRA’s security level concept. This way you can keep all tickets in one JIRA project. But you will then have to cope with the maintenance of security settings at ticket level due to the fact that security levels have to be set manually for each required ticket. To set a default security level is counterproductive because then every customer created ticket will be automatically hidden from the customer directly after creation.

Conclusion

In our experience the advantages obtained through direct participation of customers in JIRA exceed the disadvantages of for example the increased efforts necessary for JIRA configuration. A well informed customer who is directly involved in his project feels much more comfortable even if something goes wrong or the progress of the project gets stuck. Transparency is the magical keyword.

But you have to accept that every project has its own characteristics. It will be mainly influenced by the customer’s character, organization and stakeholders. You have to find the most appropriate and fitting level for a customer’s direct participation. Try to get the most accurate picture of the stakeholders you have to work with and then decide how they could fit into the process. And keep in mind that the process can always be adapted afterwards in order to achieve the greatest efficiency in project progress and customer satisfaction.

In keeping with agile practice apply continuous improvement to your project management processes: Change something – find out how it went – learn from it – change something again!

Summary of the Key Success Factors

Let customers create tickets directly in JIRA: requirements, change requests, support inquiries, bugs.
Incorporate customers’ duties and responsibilities (e.g. assignments, approvals) directly into the issues workflow as dedicated steps.
Prepare specific filters and dashboards for the customer
- for his duties (detailing, assignments, approval)
- for overviews
- for status
Split projects with an overwhelming amount of implementation tasks into two separate instances – one for the customer and one for development.
Give customers a short JIRA training covering all standard actions as well as how to use and adapt dashboards and how to interpret the data and analysis reports.
Tailor every project set-up individually and don’t try to compress it into the same template.

If you keep all this in mind, you have a good chance that JIRA will become customer’s ’sweetheart’!

There are tons of other interesting topics around JIRA. I will continue to provide you with further ideas, suggestions and mgm experiences. And of course if you have additional questions, ideas, and suggestions around JIRA I would really appreciate any comments and input from you.

(c) 2013 mgm technology partners. This posting "Practical Customer Participation in JIRA Workflows - JIRA beyond Bug Tracking, Part 2" is part of the mgm technology blog. The author of the posting is Alexander Weiss.

We are hiring! mgm technology partners is looking for good software engineers for all our offices. Check out www.mgm-tp.com/karriere.