Micrometer with Dynamic Tags

 With Micrometer, it is easy to create a counter with Builder:

Counter okCounter = Counter.builder("http.status.count")
        .tag("status", "200")
        .description("The number of OK count")
        .register(meterRegistry);

Counter notFoundCounter = Counter.builder("http.status.count")
        .tag("status", "404")
        .description("The number of not found count")
        .register(meterRegistry);

However, it is not feasible to create counter for every HTTP status.  We can use Java HashMap to cache the creation dynamically by leveraging the method computeIfAbsent

import io.micrometer.core.instrument.Counter;
import io.micrometer.core.instrument.MeterRegistry;
import java.util.concurrent.ConcurrentHashMap;
import java.util.Map;
import org.springframework.http.HttpStatus;

public class HttpStatusCounter {
    private static final String HTTP_STATUS_COUNT = "http.status.count";
    private final MeterRegistry meterRegistry;
    private Map<Integer, Counter> httpStatusCounterMap;

    public HttpStatusCounter(MeterRegistry meterRegistry) {
        httpStatusCounterMap = new ConcurrentHashMap<>();
        this.meterRegistry = meterRegistry;
    }

    public void increment(HttpStatus status, int amount) {
        Counter statusCounter = httpStatusCounterMap.computeIfAbsent(
                status.value(), k -> Counter.builder(HTTP_STATUS_COUNT)
                        .tag("status", String.valueOf(status.value()))
                        .register(meterRegistry));
        statusCounter.increment(amount);
    }
}

Spring with Spark Framework for Microservices

Recently, my team decided to use Spark to build our new REST api.  Spark seems easy with less coding.  We still wanted to use Spring for dependency injection.  We also wanted to use Tomcat as the standalone web container.  After some research, we figured out how to build the REST api with Spring, Spark and Tomcat.

1. Create class SpringSparkFilter which extends SparkFilter. Override method getApplication:
2. Create class MySparkApplication, which implements SparkApplication. Implement init method:
3. Configure web.xml to use SpringSparkFilter:

Then either build a war file, and deploy it to tomcat or use tomcat7-maven-plugin for test run.  I usually use tomcat7-maven-plugin for fast development.  Here is the command:

mvn tomcat7:run

Then access http://localhost:8080/current-date.  The complete example can be found here.

Creating JaxContext is slow

Recently, I need to create xml or json from a POJO.  I used JAXB and jettison to do the job.  At the beginning, I create the following class:

import java.io.Writer;

import javax.xml.bind.*;
import javax.xml.stream.XMLStreamWriter;

import org.codehaus.jettison.mapped.*;

public class BadJaxbPrinter {
    /**
     * To print an object to xml format
     * @param writer
     * @param jaxbAnnotedObj the object to be printed.  The class must be annoted with @XmlRootElement
     * @throws JAXBException
     */
    public void toXml(Writer writer, Object jaxbAnnotedObj) throws JAXBException {
        JAXBContext context = JAXBContext.newInstance(jaxbAnnotedObj.getClass());
        Marshaller marshaller = context.createMarshaller();
        marshaller.marshal(jaxbAnnotedObj, writer);
    }

    /**
     * To print an object to json format
     * @param writer
     * @param jaxbAnnotedObj the object to be printed.  The class must be annoted with @XmlRootElement
     * @throws JAXBException
     */
    public void toJson(Writer writer, Object jaxbAnnotedObj) throws JAXBException {
        Configuration config = new Configuration();
        MappedNamespaceConvention convention = new MappedNamespaceConvention(config);
        XMLStreamWriter xmlStreamWriter = new MappedXMLStreamWriter(convention, writer);
       
        JAXBContext context = JAXBContext.newInstance(jaxbAnnotedObj.getClass());
        Marshaller marshaller = context.createMarshaller();
        marshaller.marshal(jaxbAnnotedObj, xmlStreamWriter);
    }
}

However, the above implementation is really slow.  The reason is that it is slow to create JAXBContext because it uses reflection to parse the object's annotation.  Since JAXBContext is thread safe, it should be only created once and reuse it.  Here is the new version of implementation:

public class JaxbPrinter {
    private final MappedNamespaceConvention convention;
    //creating JaxbContext seems expensive, do NOT recreate it
    private final JAXBContext context;
   
    public JaxbPrinter(Class<?> clazz) throws JAXBException {
        Configuration config = new Configuration();
        convention = new MappedNamespaceConvention(config);
        context = JAXBContext.newInstance(clazz);
    }
    /**
     * To print an object to xml format
     * @param writer
     * @param jaxbAnnotedObj the object to be printed.  The class must be annoted with @XmlRootElement
     * @throws JAXBException
     */
    public void toXml(Writer writer, Object jaxbAnnotedObj) throws JAXBException {
        Marshaller marshaller = context.createMarshaller();
        marshaller.marshal(jaxbAnnotedObj, writer);
    }

    /**
     * To print an object to json format
     * @param writer
     * @param jaxbAnnotedObj the object to be printed.  The class must be annoted with @XmlRootElement
     * @throws JAXBException
     */
    public void toJson(Writer writer, Object jaxbAnnotedObj) throws JAXBException {
        XMLStreamWriter xmlStreamWriter = new MappedXMLStreamWriter(convention, writer);
        Marshaller marshaller = context.createMarshaller();
        marshaller.marshal(jaxbAnnotedObj, xmlStreamWriter);
    }
}

It is 25 times faster than the previous version with 10000 executions of  toXml.  Note that Marshaller and Unmarshaller are not thread safe and it is cheap to recreate them.

Also, toJson is 5 times slower than toXml.  Since the response time meets SLA, I didn't bother to use other JSON implementation (like jackson).

Create Singleton in Java

A singleton is simply a class that is instantiated exactly once.  There are two approaches to create a singleton class.

1. Early initialization,
2. Lazy initialization.

 There are several ways to create singleton in each approach.

For early initialization:

1. Singleton with public final field

public class Singleton {

      public static final Singleton INSTANCE = new Singleton();

      private Singleton() {

         //do something

      }

      public void someMethod() {

         // do something

      }

    }

     2. Singleton with static factory

public class Singleton {

     private static final Singleton INSTANCE = new Singleton();

     

     private Singleton() {

         //do something

     }

     public static Singleton getInstance(){

       return INSTANCE

     }

     public void someMethod() {

         // do something

     }   
   }
  

      3. Singleton with enum

public enum Singleton {

      INSTANCE;

            

      private Singleton() {

         //do something

      }

      public void someMethod() {

         // do something

      }    
    }


For lazy initialization:

  However unless you absolutely need it, don't use lazy initialization.

     1. Lazy initialization holder class idiom for static fields (a class will not be initialized until it is used)

public class LazySingleton {

     private static class SingletonHolder {

       static final LazySingleton INSTANCE = new LazySingleton();

     }

     

     private LazySingleton() {

         //do something

     }

     public static LazySingleton getInstance(){

       return SingletonHolder.INSTANCE;

     }

     public void someMethod() {

         // do something

     }
    }

 2. Double-check idiom for lazy initialization

   class LazySingleton {
     private static volatile LazySingleton instance;
     private LazySingleton(){
        //do something
     }

     public static LazySingleton getInstance() {
        if (instance == null) {
            synchronized (LazySingleton.class) {
                if (instance == null) {
                    INSTANCE = new LazySingleton();
                }
            }
        }
        return instance;

     }
   }

Weak Reference in Java

Today, during a phone interview, I was asked a question about WeakReference in Java.  I only knew that the weak referenced object can be garbage collected by JVM, and nothing more.  I did a little research, and realized that there are 4 types of references in Java:

1. Strong Reference
2. Soft Reference
3. Weak Reference
4. Phantom Reference

They are in the order from strong to weak references.  3 classes, SoftReference, WeakReference, and PhantomReference are for the last 3 references.  For strong reference, just use new operator. Below is a great blog talking about all 4 references:

Understanding Weak References

Print a sequence of Fibonacci number

The trick is that you should use BigInteger instead of long.  Otherwise, you will get overflow pretty soon.  Here is the code:

import java.math.BigInteger;

public class Fibonacci {
    /**
     * print out a list of Fibonacci sequence to n places.
     * if n = 0, no number will be printed out.  if n = 1, print the first Fibonacci number.
     *
     * @param n the number of Fibonacci to be printed out
     */
    public static void print(int n) {
        BigInteger f0 = BigInteger.ZERO;
        BigInteger f1 = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
           
            System.out.print(f0);
            if (i != n - 1) {
                System.out.print(", ");
            }
            BigInteger temp = f1;
            f1 = f1.add(f0);
            f0 = temp;
        }
    }
}

Update: Another thing to consider is that don't use recursive method to compute Fibonacci number because it is too expensive.  The run time is 2^n to recursively compute Fibancci number.

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).

Implementation of the procedure RANDOM(a, b) that only makes calls to RANDOM(0, 1).  This is the question asked in book "Introduction to Algorithm."  I spent some time figuring out the following solution implemented in Java.  The assumption is that we can get random number 0 and 1 which I use Java class Random to generate.

import java.util.Random;
public class RandomGenerator {
    private static Random rand = new Random();

    /**
     * generate a random nubmer between a (inclusive) and b (exclusive)
     */
    public static int random(int a, int b) {
        if (a >= b) {
            throw new UnsupportedOperationException("2nd param must be greater than 1st param");
        }
        return a + generate(b - a);
    }
    /**
     * generate the random between 0 to a (exclusive)
     */
    private static int generate(int a) {
        int run = leastPowerOfTwo(a);

        while (true)  {
            int power = 1;
            int sum = 0;
            for (int i = 0; i < run; i++) {
                sum += random01() * power;
                power *= 2;
            }
            if (sum < a) {
                return sum;
            }
        }
    }

    /**
     * find the least power of 2 which is greater than or equal to the given input a
     */
    private static int leastPowerOfTwo(int a) {
        int power = 0;
        int temp = a;
        while (temp > 0) {
            temp >>>= 1;
            power++;
        }
        //if a is a power of 2
        if ((a & (a - 1)) == 0) {
            power--;
        }
        return power;
    }

    /**
     * a method to randomly generate 0 or 1
     * @return 0 or 1
     */
    private static int random01() {
        return rand.nextInt(2);
    }
}

The trick is to use the binary representation for the generated random number.  For example, to generate a random within [0, 5),  we need to call random(0, 1) 3 times since 2 ^ 3 = 8.  If call random(0, 1) 2 times, we only have 2 ^ 2 = 4 random numbers.  We only need to keep random number less than 5, and if we get a number is greater than 4, we just retry until we get the number is less than 5.   Below is the binary representation for 3 runs of random(0, 1)

#run #3   #2   #1
          0    0     0        0
          0    0     1        1
          0    1     0        2
          0    1     1        3
          1    0     0        4
          1    0     1        5
          1    1     0        6
          1    1     1        7


The informal proof of the above algorithm is that the chance to generate each number is same (1/8).  Since we only keep the number from 0 to 4, the chance to generate the number from 0 to 4 is still same.  Then the above algorithm does generate the correct random numbers.  I ran this program on my machine to generate random number from 7 to 12 (exclusive) for 10 million times, and here is the result:

7:   1997855
8:   2000311
9:   2000140
10: 2000369
11: 2001325

Maximum subarray

This is an interview question:

Given an integer array, find the max sum in any contiguous sub-array.  If all elements are negative, then the sum is 0. The following code just finds the max sum without returning the start and end indexes:

public class MaxSubArray {
    public static int maxSum(int[] input) {
        int currentSum = 0;
        int maxSum = 0;
        for (int i = 0; i < input.length; i++) {
            currentSum = Math.max(currentSum + input[i], 0);
            maxSum = Math.max(maxSum, currentSum);
        }
        return maxSum;
    }
}

The following code returns max sum with starting and ending indexes. If all elements are negative, return start and end indexes as 0 and -1, respectively.

public class MaxSubArray {
    public static MaxSubArrayResult compute(int[] input) {

        MaxSubArrayResult result = new MaxSubArrayResult(0, -1, 0);
        int currentSum = 0;
        int currentStart = 0;
        for (int currentEnd = 0; currentEnd < input.length; currentEnd++) {
            currentSum += input[currentEnd];
            if (currentSum > result.maxSum) {
                result.start = currentStart;
                result.end = currentEnd;
                result.maxSum = currentSum;
            } else if (currentSum < 0){
                currentStart = currentEnd+ 1;
                currentSum = 0;
            }
        }
        return result;
    }

    public static class MaxSubArrayResult {
        public int start;
        public int end;
        public int maxSum;

        public MaxSubArrayResult(int start, int end, int sum) {
            super();
            this.start = start;
            this.end = end;
            this.maxSum = sum;
        }

        @Override
        public String toString() {
            return String.format("start = %d, end = %d, maxSum = %d", start, end, maxSum);
        }
    }
}

The run time for both method is linear (O(n)).