Saturday 25 January 2014

Locking Management in JPA

Why Locking is required?
When two concurrent users try to update database row simultaneously, there are absolute chances of losing data integrity. Locking comes in picture to avoid simultaneous updates and ensure data integrity.

Types of Locking
There are two types of locking, Optimistic and Pessimistic. In this post optimistic locking is described with example.
  • Optimistic Locking: This locking is applied on transaction commit. If entity (database row) is fetched by two users simultaneously, where first user updates and commits the row and second user tries to update row with an old version. Second user will get an exception as row is already updated and version is changed. A version number is associated for entity object to achieve optimistic locking. Whenever entity object is changed, its version number is automatically increased by one. If any transaction is performed on older version of entity, transaction is failed and application throws optimistic locking exception.
  • Pessimistic Locking: Pessimistic locking explicitly restricts shared resources until the transaction completed. To get more detail about pessimistic locking refer this link .  

How to Implement Optimistic Locking in JPA 2.0?
Let’s take an example; there are two Tables Company and Employee:

Table: Company
Company_Id
Company_Name
Address
Survey_Sequnce
Version
1
AirTel
xyz
110
20
2
Reliance
abc
230
40

Table: Employee
Employee_Id
Employee_Name
Company_Id
Employee_Survey_No
1
Narendra
1
111
2
Vinay
1
112
3
Ranu
2
231
4
Rinku
2
232

Whenever, employee joins the company, he is asked to complete the company specific survey and after completion of the survey, 'Employee_Survey_No' is generated based on SURVEY_SEQUENCE from company table. To generate the survey number below steps are performed:
  1.   Read the current sequence value specific to a company from company table   (SURVEY_SEQUENCE)
  2.      Increment the sequence count by 1
  3.      Update the incremented value in company table (SURVEY_SEQUENCE)
  4.      Use this incremented value to log into employee table as 'Employee_Survey_No'
In this use case, there are absolute chances that two parallel surveys are performed for same company, where two employees get same survey sequence. This scenario can be handled with the help of optimistic locking in JPA to avoid sequence update collisions for same company.
Let’s implement optimistic locking in JPA. JPA facilitates easy approach to handle optimistic locking.
Define the company entity and annotate version column property with @Version to enable optimistic locking for entity.
@Entity
@Table(name = "Company", schema = "MyDB")
public class Company {
    private Long companyId;
    private String companyName;
    private String address;
    private Long surveySequence;
    private Long version;
   
    @Id
    @SequenceGenerator(name = "company_seq", sequenceName = "MyDB.company_seq")
    @GeneratedValue(generator = "company_seq")
    @Column(name = "COMPANY_ID", unique = true, nullable = false)
    public Long getCompanyId() {   
        return companyId;
    }   
    public void setCompanyId(Long companyId) {   
        this.companyId = companyId;
    }   
    @Column(name = "COMPANY_NAME")
    public String getCompanyName() {   
        return companyName;
    }   
    public void setCompanyName(String companyName) {   
        this.companyName = companyName;
    }   
    @Column(name = "ADDRESS")
    public String getAddress() {
        return address;
    }   
    public void setAddress(String address) {   
        this.address = address;
    }   
    @Column(name = "SURVEY_SEQUENCE")
    public Long getSurveySequence() {   
        return surveySequence;
    }   
    public void setSurveySequence(Long surveySequence) {   
        this.surveySequence = surveySequence;
    }   
    @Column(name = "VERSION_ID")
    @Version
    public Long getVersion() {   
        return version;
    }   
    public void setVersion(Long version) {   
        this.version = version;
    }  
   
}

Now create the company DAO method to fetch the survey sequence, increment and update incremented value into company table. As we have annotated company table column with @Version, JPA will take care about parallel company entity updates. If any transaction is performed with older version of entity, transaction is failed and this method will throw ‘OptimisticLockingFailureException’.

@Repository("companyDAO")
public class CompanyDAO {

    public Long getNextSurveySequence(Long companyId) {
      
        //Fetch company entity based on companyId
        Company company = entityManager.findById(Company.class, companyId);
      
        // Get the current survey sequence
        Long surveySeq = company.getSurveySequence();
      
        // Increment current sequence by 1
        Long nextSurveySeq = surveySeq + 1L;

        // Set new sequence in company entity
        Company.setSurveySequence(nextSurveySeq)
       
        // Update company with new sequence
        entityManager.merge(company);

        return nextSurveySeq;
  }
}

Now create the service method to fetch the next survey sequence and handle optimistic locking exception. With maximum try count approach, you can retry data base operation for failed transactions.

@Service("companyService")
public class CompanyService {

   public Long getNextSequenceForOrgId(Long companyId) throws Exception {
   
    Long surveySequence = null;

   //If any transaction is performed on older version of entity,
   //transaction is failed and application throws the ‘OptimisticLockException’

    for (int maxTryCount = 1; maxTryCount <= 3; maxTryCount++)
    {
       try {
             surveySequence = companyDao.getNextSurveySequence(companyId);

             break;

       } catch (OptimisticLockingFailureException e) {
           
           if (maxTryCount == 3) {                       
                throw new Exception(e);
            }
       }
     }
    return surveySequence;
   }
}

I hope this post helps you understanding and implementing optimistic locking with JPA. If you would like to share your thoughts on it, you are most welcome to comment.

Friday 10 January 2014

Coding Contest - Arranging numbers from 1 to 71 in a sequence such that sum of any 2 adjacent numbers in the sequence adds up to a prime number

I have got a problem in coding contest. In this post, I would like to share the approach to solve this problem. I would definitely not say that I have invented something new and I am not trying to reinvent the wheel again. I just described the end to end approach that I followed to solve this problem.It was really a great brain storming activity.

Problem Statement

"Arrange numbers from 1 to 71 in a sequence such that sum of any 2 adjacent numbers in the sequence adds up to a prime number.”For e.g :  7,6,5,2,1,4,3 is a valid one sequence for arranging 1..7"

Theory: How to Solve?
Let's take an example, we want to find all series from 1 to 5 such that sum of any 2 adjacent numbers in the sequence adds up to a prime number. For this problem, there should be below no. of possible combinations.

1, 4, 3, 2, 5 
3, 4, 1, 2, 5 
5, 2, 1, 4, 3 
5, 2, 3, 4, 1

Now, lets talk about the approach to get above combinations.

Firstly, for each number, check all possible numbers in series such that sum should be a prime number. Let's take number 1 and check which sum is prime number out of 1+2 = 3, 1+3=4, 1+4=5, 1+5=6.  So, we have got 1+2 = 3 and 1+4=5 that means 2 and 4 are the numbers that can be connected to number 1. Now apply the same logic for all remaining numbers 2,3,4,5. You will get below combinations.

1 --> 2, 4
2 --> 1, 3, 5
3 --> 2, 4
4 --> 1, 3
5 --> 2


Secondly, create a graph that connects any two numbers that has a prime number sum. If you take number 1 that is connected to 2 and 4, the graph must represent link between connected numbers. In graph's terminology you can say each number is a vertex and each connected link is an edge.



Till now you are half done. You have graph that connects any two numbers that has a prime number sum.

Thirdly, you just need to  find out the unique cycles in graph where you visit each vertex exactly once. This is kind of calculating Hamiltonian Paths (also refer this).

Below graph shows two cycles:
1, 4, 3, 2, 5
5, 2, 3, 4, 1


Below graph shows two cycles:
3, 4, 1, 2, 5 
5, 2, 1, 4, 3 


Theoretically you have achieved what you wanted to achieve. You have all 4 possible combinations for given problem from 1 to 5.

Now let's convert above theory into computer programming and ask computer to get combinations for any given number. Well, I am a Java Techie and I would prefer to convert this theory into java programming. If you are a Java Techie you have prepared solution in your hand. In case you are not, you have to struggle converting my program into your required language.

Programmatic Approach: How to Solve?
Before jumping into the programming, you have to think first how you can represent this graph in java. This is bit complex. But once you get into this; it will be easy to understand and apply.

I took help from here to represent the graph in two dimensional array. To get combinations from 1 to 5, graph can be represented in 2D array like below:


Action Points for Programming
  • Populate 2D array that connects any two numbers that has a prime number sum.
  • Implement recursive function to find out the path that visits each connected number exactly once 
  • Print the path if path length equals to the provided last number

Solution in Java

Program



import java.io.File;
import java.util.ArrayList;
import java.util.Date;
import java.util.List;

import org.apache.log4j.Appender;
import org.apache.log4j.DailyRollingFileAppender;
import org.apache.log4j.FileAppender;
import org.apache.log4j.Level;
import org.apache.log4j.Logger;
import org.apache.log4j.PatternLayout;

/**
 * Coding Contest
 *
 * Arrange numbers from 1 to n in a sequence such that sum of any 2 adjacent
 * numbers in the sequence adds up to a prime number. For e.g : 7,6,5,2,1,4,3 is
 * a valid one sequence for arranging 1..7
 *
 *
 * @author NarendraVerma
 */
public class PrimeSequenceSolution {

               /** The pattern layout. */
               private static PatternLayout patternLayout = new PatternLayout("%d{ISO8601}\t%m%n");

               /** Logger instance. */
               private static final Logger LOGGER = Logger
                                             .getLogger(PrimeSequenceSolution.class);
              
               /** Matrix that holds all prime numbers . */
               public static int[][] inputArray = null;

               /** Matrix[1][n] hat connects any two numbers that has a prime number sum. */
               public static int inputArrayLength;

               /** The total sequences count. */
               public static int totalCount = 0;

               /** Maximum Sequences to be generated. */
               public static long maxSeq = 1000000000;

               /** The start time. */
               public static long startTime;

               /** The logging flag. */
               public static boolean loggingFlag = true;

               /**
                * Find prime sequences.
                */
               public static void findPrimeSequences() {

                              traverseVertexes(new ArrayList<Integer>());
               }
              

               /**
                * Populate 2D array that connects any two numbers that has a prime number sum
                *
                * For example: If last No is 5, matrix is populated like below
                * 
                *        1 --> 2, 4
                *        2 --> 1, 3, 5
                *        3 --> 2, 4
                *        4 --> 1, 3
                *        5 --> 2
                *
                * 2D Array:
                *
                *      1  2  3  4  5
                *   1 [0  1  0  1  0]             
                *   2 [1  0  1  0  1]
                *   3 [0  1  0  1  0]
                *   4 [1  0  1  0  0]
                *   5 [0  1  0  0  0]
                * 
                * @param lastNo the last no
                */
               public static void prepareInputMatrix(int lastNo) {

                              inputArray = new int[lastNo][lastNo];

                              for (int i = 1; i <= lastNo; i++) {

                                             for (int j = 1; j <= lastNo; j++) {
                                                            if (i == j) {
                                                                           inputArray[i - 1][j - 1] = 0;
                                                            } else {                                                               
                                                                           inputArray[i - 1][j - 1] = isPrime(i + j);
                                                            }
                                             }
                              }
               }

               /**
                * Checks if given number is prime number
                *
                * @param number
                *            the number
                * @return the int
                */
               public static int isPrime(int number) {
                              // check if number is a multiple of 2
                              if (number % 2 == 0)
                                             return 0;
                              // if not, then check the odd numbers
                              for (int i = 3; i * i <= number; i += 2) {
                                             if (number % i == 0)
                                                            return 0;
                              }
                              return 1;
               }

               /**
                * The recursive function to find out the path that visits each connected number exactly once  
                *
                * @param traversedPath
                *            the path so far
                * @return the list
                */
               public static List<Integer> traverseVertexes(List<Integer> traversedPath) {

                              inputArrayLength = inputArray.length;
                              if (traversedPath.size() == inputArrayLength) {
                                             printSequences(traversedPath);
                                             return traversedPath;
                              } else if (traversedPath.size() == 0) {
                                             for (int i = 0; i < inputArrayLength; i++) {
                                                            traversedPath.add(i);
                                                            traverseVertexes(traversedPath);
                                                            traversedPath.remove(traversedPath.size() - 1);
                                             }
                              } else {
                                             int currentNode = traversedPath.get(traversedPath.size() - 1);
                                             for (int i = 0; i < inputArrayLength; i++) {
                                                            if (!traversedPath.contains(i) && inputArray[currentNode][i] != 0) {
                                                                           System.out.println("I am here:" + traversedPath );
                                                                           traversedPath.add(i);
                                                                           traverseVertexes(traversedPath);
                                                                           traversedPath.remove(traversedPath.size() - 1);
                                                            }             
                                             }
                              }
                              return traversedPath;

               }

               /**
                * Prints the solution.
                *
                * @param pathSoFar
                *            the path so far
                */
               public static void printSequences(List<Integer> pathSoFar) {

                              StringBuffer sb = new StringBuffer(" -- ");
                              sb.append(" [ SeqNo."+ (totalCount + 1 )+"] -- ");
                             
                              for (Integer number : pathSoFar) {

                                             sb.append(number + 1).append(", ");

                              }
                             
                              if (loggingFlag)
                                             LOGGER.info(sb.toString());
                              else
                                             System.out.println(new Date() + " " + sb.toString());

                              if (maxSeq != 1000000000 && totalCount > maxSeq - 2) {
                                            
                                             LOGGER.info("Maximum sequences [ " + maxSeq
                                                                           + " ]  have been generated.  Total-Elapsed-Time [ "
                                                                           + (System.currentTimeMillis() - startTime) + " msec ] ");
                             
                                             System.out.println("Maximum sequences [ "
                                                                           + maxSeq
                                                                           + " ] have been generated.  Total-Elapsed-Time [ "
                                                                           + (System.currentTimeMillis() - startTime) + " msec ]");

                                             System.exit(1);
                              }

                              ++totalCount;
               }
              
               /**
                * Creates the log file.
                *
                * @param lastNo the last no
                * @return the file
                */
               public static File createLogFile(int lastNo){
                             
                              String fileName = "271962_primeseq_"+ lastNo + ".log";
                             
                              File logFile = new File(fileName);
                             
                              //Remove existing log file if exists
                              if(logFile.exists()){
                                             logFile.delete();
                              }
                             
                              FileAppender fa = new FileAppender();
                              fa.setName("FileOut");
                              fa.setFile(fileName);
                              fa.setLayout(patternLayout);
                              fa.setThreshold(Level.DEBUG);
                              fa.setAppend(true);
                              fa.activateOptions();
                              LOGGER.setAdditivity(false);

                              LOGGER.addAppender(fa);
                             
                              return new File(fileName);
               }

               /**
                * The main method.
                *
                * @param args the arguments
                * @throws Exception the exception
                */
               public static void main(String[] args) throws Exception{
                             
                              int lastNo = 0;
                             
                              try{
                                             // Fetch second argument - The number for which the sequence to be generated
                                             lastNo = Integer.parseInt(args[1]);
                                            
                                             // Create log file
                                             File logFile = createLogFile(lastNo);
                                            
                                             startTime = System.currentTimeMillis();
              
                                             // Fetch first argument - This is log level flag. If 'true' write to log
                                             // file, if false print to the console
                                             String logFlag = args[0];
                                             if ("true".equals(logFlag)){
                                                            System.out.println("\nPrime sequences are logged into file ["+logFile.getAbsolutePath()+"]");
                                                            loggingFlag = true;
                                             }             
                                             else
                                                            loggingFlag = false;
                                                           
                                             // Fetch third argument - Maximum Sequences to be generated
                                             if(args.length == 3){
                                                            maxSeq = Integer.parseInt(args[2]);             
                                             }
                              }             
                              catch(Exception e ){
                                             String errorMessage = "\nPlease provide the valid arguments \n"   
                                             System.out.println(errorMessage);
                                             System.exit(1);
                              }
                             
                              // Populate 2D array
                              prepareInputMatrix(lastNo);

                              // Find the sequences
                              findPrimeSequences();

                              long end = System.currentTimeMillis();
                              long totalTimeSpend = end - startTime;
                             
                              if(!loggingFlag){
                                             LOGGER.info("Since logging flag (first argument of the program) is false, sequences are printed to the console");
                              }
                             
                              LOGGER.info("Total-Elapsed-Time [ " + totalTimeSpend
                                                            + " msec ] and No. of total sequences found [ "
                                                            + totalCount + " ]");
              
                              System.out.println("\nCongratulations !! Sequences generated successfully.");

                              System.out.println("\nTotal sequences generated [ "+ totalCount + " ],  Elapsed Time [ " + totalTimeSpend + " msec ]");

               }

}

How to Execute Program?

You can use below command to execute above program.
java PrimeSequenceSolution <logging_Flag> <last_number> <max_sequences>


  • <logging_Flag>  : If 'true' sequences are written in log file, if 'false' print to the console
  • <last_number>   : The number for which the sequence to be generated
  • <max_sequences> : Maximum sequences to be generated. This is optional. Default value is 1000000000

Example:
java PrimeSequenceSolution  true 5 
java PrimeSequenceSolution  false 7 

java PrimeSequenceSolution  false 15 100000

Execution Statistics
Below are the captured execution statistics for above program.



Conclusion

Above approach is one of the solutions for given problem. I am sure there can be other approaches to solve this problem. If you notice the execution statistics, execution time is drastically increased if last number is increased. What about if program gets executed to get combinations for last number say 70, 80, 100 etc. This program will definitely take much time to get combinations or it may prompt out of memory error. Generating the expected result can be one of the aspect to solve a problem but efficiency is most important aspect that must not be ignored. Though, this solution gives the expected result but it may not be considered as efficient as it should be. This execution statistics left me thinking about what can be the other approaches? How can I make this program efficient? Can I think about parallel processing? etc.Well, I still need to get answers of my own questions. If you know the better solution; your comments are greatly appreciated.

Additionally, I tried to find out the real world problems related to this mathematical problem. TSP
is one of the most famous problems. This is just to get into the real world problems. isn't it?