Twitter tutorial (druid with Sql)

This post has been moved.

A first look at druid with Sql

This post has been moved .

BMDiff - Bentley and Mclroy's compression of long common strings

       A java implementation inspired from BigTable paper[1] description about Bentley and McIlroy’s long string compression scheme[2].

[1] - http://static.googleusercontent.com/media/research.google.com/en/us/archive/bigtable-osdi06.pdf

[2] - http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.11.8470&rep=rep1&type=pdf

Source Code

Github project BMDiff.

Dry run performance numbers

•  JITed version maximum speed Encoding - 35MB/s
  Decoding - 330MB/s
  The speeds reported above are due to tests with following parameters
  a) 3Gz dual core iMac (8GB RAM) with 1GB allotted to the VM(JDK 1.8 preview).
  b) Block length = 32
  c) UTF-8 text file sizes 150KB and 7MB.
  The speed changes when block length changes(smaller block lengths decrease the speed, larger block length decreases compression).
  
• There is scope for speed improvement which is the target for next version as this version the target was to produce correct enc/dec.
• There is a slight twist to the original algorithm in the implementation which is when repeated string occur together then still they are chained and represented using notation but for the decoder to decipher this properly for such cases the encoding is instead.

Related Bugs in the open:

HBASE - https://issues.apache.org/jira/browse/HBASE-2655
Hadoop - https://issues.apache.org/jira/browse/HADOOP-5793

TapTime, a selective profiler

About TapTime :

          A very light weight mechanism based on byte code injection to get method wall clock times and basic metrics like call count, lowest and max CPU times. Why not dynamic proxy ?(Reflection calls overhead and requirement to rewrite the Monitored Class to implement and enforce interface which is painful as you may only want to trace 1 method but when more methods have to tapped the interface has to be changed. Not practical at all. How is this different from any other profiling tool ? It is suitable for selective profiling unlike most profilers which instrument the entire application, this  tool allows the developer to select only interesting parts of the application to be profiled.

 How to use the utility:

1.  Include javassist.jar and TapTime.jar in the build path /class path.
2.  To trace methods at runtime annotate them with @Tap

Usage:

TapTime.init("package");
1) This has to be the very first line(preferably in a static initializer)
2) Do not maintain any static roots in the main class of those classes whose methods you want to tap.

The utility methods users may invoke

1) printStats();
Method avg,min,max time clocked including independant counts.

2) printMethodsTracked();
All the tapped methods are listed out.

3) printCallStackSimple();
Ex: prints like following CALL STACK(SIMPLE)
0(1) 1(1) 1(0) 2(1) 3(1)  3(0) 3(1) 3(0) 2(0) 1(1) 1(0) 0(0)
n(m) - where n = methodId and m = 0/1 where 1 = entered into method, 0 = left from method.

4) printCallStackHierarchy();
Same as printCallStackSimple() but prints in a tree like format for methods traced instead  of mundane numbers.

5) generateCommonCallSequences(); // This is the flagship method for statistics. Prints the 1 ,2 3 upto deepest level of all possible call sequence counts.

Ex:
abhi->1
snowy->1
arjun->1
tintin->snowy->1
arjun->abhi->1
tintin->2

Deep dive:

         We initially created a TapClassLoader with a custom findClass() implemented which injected instrumentation code on specific classes whose methods are annotated for Tap. Though this can do the inverse delegation of class loading it had to use reflection to instantiate objects of classes under Tap. This is cumbersome from user’s perspective and transfers the burden onto user. We can also make this the System class loader through -Djava.system.class.loader=taptime.TapClassLoader ,unfortunate reality is that all your classes still will be loaded by the parent class loader because of delegation model and not by your TapClassLoader. This applies even when you do 

      Thread.currentThread().setContextClassloader(tapClassLoader).
       Though you can say that this is my context class loader java will delegate the call to parent and if parent class loader is able to load the class then thats it. But if you have some weird location from which you are loading classes which are not visible to the parent class loader then you are lucky and can load the classes from the current class loader which is again because of delegation model(This is how class loaders in web containers like tomcat work). So we chose an alternate way - got rid of class loader, instead relied on temporal facts of class loading to modify and persist the bytecode. The only obvious disadvantage of this approach is we need to do a clean rebuild every time you want to run the program which is acceptable considering the smaller build time for java. This way we can be agnostic of existence of multiple threads in your program.
      Currently we support specifying root package whose sub packages will be searched for Tapped methods. Plan to support multiple root packages in the future. This has not gone through rigorous testing, please let me know if you find any bugs. I hope this tool will be helpful.

Source Code:

• Hosted as TapTime at Github .Import into Netbeans and run build to generate artifacts. 

Feel free to leave your feedback. Hope this tool is of some use to some one.

TrieMap - A Trie for Java

         Trie is a very simple data structure in concept, however the implementation is a little involved. Suppose you want to have the trie accept entries like
             [ {1,3,4},1 ] ,  [{1}, 3],  [{3,4}, 6] ....
where the values within {} form the keys and the lone value outside it corresponding values then this TrieMap comes in handy for such situations. We can think of behaviors like
1) Adding/updating existing value  
        Ex: {1,3,4}’s value set to supplied value
2) Incrementing prefix partial key’s corresponding values  
        Ex: {3,4},6 will update {3}’s value as well as {3,4}’s value
3) Incrementing prefixes of all suffixes of whole key.
        Ex:{1,3,4} will update {1} {3} {4} {1,3} {3,4} and {1,3,4}’s values respectively .
4) Iterate through all the possible <K,V> combinations.
     Find the open source implementation at github here.  This implementation accepts list of numbers(can be int, byte, double etc).


      A HashMap could have been used as well. The beauty with Trie is say you have a set of keys
{2,3,4,5}
{2,3}
{2,3,4}
  then in a Trie 2  3  and 4 are stored only once because they all belong to same level(if you imagine a Trie as a tree) but a HashMap stores them as many number of times as they appear. There is also a test case within to showcase the usage. Feel free to leave a feedback.