JMS, ActiveMQ, JGroups

JMS(Java Message Service) api is a Java message oriented middleware api provided by Java Platform Enterprise Edition for sending messages between two or more clients.

The following are JMS elements:^[3]

JMS provider

An implementation of the JMS interface for a Message Oriented Middleware (MOM). Providers are implemented as either a Java JMS implementation or an adapter to a non-Java MOM.

JMS client

An application or process that produces and/or receives messages.

JMS producer/publisher

A JMS client that creates and sends messages.

JMS consumer/subscriber

A JMS client that receives messages.

JMS message

An object that contains the data being transferred between JMS clients.

JMS queue

A staging area that contains messages that have been sent and are waiting to be read. Note that, contrary to what the name queue suggests, messages don't have to be delivered in the order sent. A JMS queue only guarantees that each message is processed only once.

JMS topic

A distribution mechanism for publishing messages that are delivered to multiple subscribers.

ActiveMQ is one of the implementation of the JMS provider. 

ActiveMQ topic :

By definition, a topic message remains on the topic until it is consumed by all the currently available non-durable subscribers, and all the registered durable subscribers, irrespective of whether they are currently available or not. Once a topic message is consumed by any given subscriber, it becomes pending and remains so, until it has been consumed by all of these subscribers. 

JGroups is a toolkit for reliable multicast communication.It can also use JMS as one of the

protocol.

The most powerful feature of JGroups is its flexible protocol stack, which allows developers to adapt it to exactly match their application requirements and network characteristics.

Applications are even free to write their own protocols (or extend an existing one), and add them to the configuration. It might be useful for example, to add a protocol which keeps track of all messages sent and received over a cluster, for auditing or statistics purposes.

An Example of How Things Can Go Wrong

It is tempting to believe that it suffices to use JMS in order to achieve fully reliable messaging, but this is not true.

Let's consider the following example of where things can go wrong. Assume that a message comes in on the JMS queue (say, a payment order) and we want to process the payment in the database.

1. The message is taken off the queue
2. The message is processed by our Java program
3. The results are put in the database

Let's now focus on the following questions:

• Can messages be lost?
• Can messages be received twice?

The answer to each question will depend on the acknowledgement mode for JMS. Again, the possible values are: automatic, explicit and transactional.

With automatic acknowledgement, the JMS message is deleted from the queue as soon as it is taken off. Clearly, this allows message loss if our program crashes in step 2. In that case, the payment order is lost forever. Hence, we have message loss.

With explicit acknowledgement, the JMS message is not deleted from the queue until our program tells it to do so. When could we tell the JMS to delete the message? If done before step 2, then a crash in 2 means message loss again. If done during step 2, then a crash will also lose the message since the database has not been changed. If done after step 3, then a crash could happen between 3 and before we can delete the message. In that case, the message will be redelivered upon restart and will be re-processed and re-posted to the database. That is: duplicates.

With transactional acknowledgement, there are two possibilities: connector-level JMS and JDBC transactions or JTA/XA. When JMS is used in transactional mode, the deletion of a message is only done if and only if the transaction commits. JDBC implies that the database is updated only if the transaction commits.

For connector-level transactions, we will have two distinct transactions: one for JMS and one for JDBC. So the question is: how should the commits be ordered to avoid message loss and duplicates?

If the JMS transaction is committed first, a crash can happen before we commit the JDBC transaction. Consequence: message loss; the payment will never be in the database.

If the JDBC transaction is committed first, a crash can happen before we commit the JMS transaction. Consequence: duplicate message; the message is not deleted from the queue and will be redelivered later. The application will re-process it and re-post it in the database.

The only remaining possibility is: joint commit of both the JMS and the JDBC transaction, and this is exactly what JTA/XA do for you. For reliable, exactly-once messaging you really need JTA/XA.

Dynamic Programming: Longest common substring

Note: This is different from longest common subsequence. Longest common string is continuous while
the longest common subsequence is not.

A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements. For example, the sequence  is a subsequence of .

Given two sequences X and Y, a sequence G is said to be a common subsequence of X and Y, if G is a subsequence of both X and Y. For example, if

 and

then a common subsequence of X and Y could be

This would not be the longest common subsequence, since G only has length 3, and the common subsequence  has length 4. The longest common subsequence of X and Y is .

 public class LCS{  
      public static String getLCS(String str1, String str2) {  
           StringBuilder sb = new StringBuilder();  
           if (str1 == null || str1.isEmpty() || str2 == null || str2.isEmpty())  
                return "";  
           // ignore case  
           str1 = str1.toLowerCase();  
           str2 = str2.toLowerCase();  
           // java initializes them already with 0  
           int[][] c = new int[str1.length()][str2.length()];  
           int maxlen = 0;  
           int lastSubsBegin = 0;  
           for (int i = 0; i < str1.length(); i++) {  
                for (int j = 0; j < str2.length(); j++) {  
                     if (str1.charAt(i) == str2.charAt(j)) {  
                          if ((i == 0) || (j == 0))  
                               c[i][j] = 1;  
                          else  
                               c[i][j] = 1 + c[i - 1][j - 1];  
                          if (c[i][j] > maxlen) {  
                               maxlen = c[i][j];  
                               int thisSubsBegin = i - c[i][j] + 1;  
                               if (lastSubsBegin == thisSubsBegin) {  
                                    //if the current LCS is the same as the last time this block ran  
                                    sb.append(str1.charAt(i));  
                               } else {  
                                    //this block resets the string builder if a different LCS is found  
                                    lastSubsBegin = thisSubsBegin;  
                                    sb = new StringBuilder();  
                                    sb.append(str1.substring(lastSubsBegin, i + 1));  
                               }  
                          }  
                     }  
                }  
           }  
           System.out.println("The DP table is: ");  
           for (int i=0; i<c.length; i++) {  
                for (int j=0; j<c[i].length; j++) {  
                     System.out.print(" " + c[i][j]);  
                }  
                System.out.println("");  
           }  
           return sb.toString();  
      }  
      public static void main(String args[]){  
           LCS m = new LCS();  
           System.out.println("The LCS is "+m.getLCS("complexity","xiterty"));  
      }  
 }  

Dynamic Programming : Making coin change
1) I have  used "-1" to represent infinity. Hence I have an extra check to avoid the condition when "1 +(-1) = 0", because I want to treat "-1" as infinity and not number -1.

 public class MakeChange{  
      int[][] c;  
      public int[] a;  
      int sum;  
      int numCoins;  
      public MakeChange(int targetSum, int[] coins){  
           sum = targetSum;  
           numCoins = coins.length;  
           a = coins;  
           c = new int[numCoins][sum + 1];  
      }  
      public int getMinCoins(){  

           c[0][0] = 0;
           for(int i = 1; i <= sum; i++){  
                c[0][i] = -1; //This indicates infinite value, bcoz one cannot make sum of n using coin of value "0"  
           }  
           for(int i = 1; i < numCoins; i++){  
                for(int j = 1; j <= sum; j++){  
                     System.out.println("Trying to make change for "+j+" using coin "+a[i]);  
                     if(j < a[i]){ //sum to be made is less than coin value  
                          System.out.println("Assign value of coin "+c[i-1][j]+" which is "+c[i-1][j]);  
                          c[i][j] = c[i-1][j];  
                     }else{ //Make sum j using coin i or without using coin i and select the one with min coins  
                          int n = c[i][j-a[i]];  
                          if(n < 0){ //This check is required as I am using -1 for infinity  
                               c[i][j] = c[i-1][j];  
                          }else{  
                               System.out.println("Min of "+c[i-1][j]+" and "+(1+n));  
                               int min = findMin(c[i-1][j],1+n);  
                               c[i][j] = min;  
                          }  
                     }  
                }  
           }  
           System.out.println("The DP table is: ");  
           for (int i=0; i<c.length; i++) {  
                for (int j=0; j<c[i].length; j++) {  
                     System.out.print(" " + c[i][j]);  
                }  
                System.out.println("");  
           }  
           return c[numCoins - 1][sum];  
      }  
      private int findMin(int i, int j){  
           if(i < 0 && j < 0) {  
                return -1; //return infinity  
           }else if(i < 0 && j >=0){  
                return j;  
           }else if(j < 0 && i >=0){  
                return i;  
           }else if(i < j){  
                return i;  
           }else{  
                return j;  
           }  
      }  
      public static void main(String args[]){  
           int[] a = {1,2,4,8};  
           MakeChange m = new MakeChange(8,a);  
           System.out.println("The min # of coins are "+m.getMinCoins());  
      }  
 }