Tuesday, December 12, 2006

Using Java bytecode in clustering technique

When I first heard of clustering Java objects, I immediately thought about object serialization. As someone just got out of school, it's an educated deduction :) I soon learned it's not always the case when speed and scalability are taken into account. Serialization of a plain ol' java object is rather slow when you have lots of transactions, and lots of objects. So how else then you would maintain the object integrity across cluster?

For Terracotta DSO, we choose to go one level down, the JVM bytecode (as opposed to the application level) There's like a whole new world of Java when you decide to look into it. As it turns out, every time you set or get values to variables, the opcodes for them are "getfield" and "putfield". DSO looks for these opcodes and record the mutation of an object in one JVM, then replay that "tape" in another JVM on the same clustered object. The final effect is that we can replicate object data in multiple JVMs on the field level.

Let take a look at a simple class: Person.java
To create the byte code, run these commands:

$> javac Person.java
$> javap -c Person > Person.bc

Person.java



public class Person {
private String name;

public Person(String aName) {
name = aName;
}

public String getName() {
return name;
}

public void setName(String aName) {
name = aName;
}
}


Person.bc



Compiled from "Person.java"
public class Person extends java.lang.Object{
public Person(java.lang.String);
Code:
0: aload_0
1: invokespecial #1; //Method java/lang/Object."":()V
4: aload_0
5: aload_1
6: putfield #2; //Field name:Ljava/lang/String;
9: return

public java.lang.String getName();
Code:
0: aload_0
1: getfield #2; //Field name:Ljava/lang/String;
4: areturn

public void setName(java.lang.String);
Code:
0: aload_0
1: aload_1
2: putfield #2; //Field name:Ljava/lang/String;
5: return

}


Voila, the gut of our class is exposed. For DSO, this is what we work on. So as you can see, the DSO claim about only sending the deltas (the changes) of an object across network, makes sense. The magic is in the bytecode instrumentation, using ASM framework.

Similarly, locking by using "synchronized" blocks can be observed by the tell-tales "monitorenter", "monitorexit" bytecodes. Don't take my words for it, try it out yourself. I've learned a great deal since I start studying Java bytecode.

One good source I found is: Java bytecode:
Understanding bytecode makes you a better programmer

Ari Zilka talk at Google is another great source.

Have fun-

Sunday, October 08, 2006

Share precious heap memory across multiple JVM's

I've written some puzzle solvers for fun during college. Among them was for Boggle board. One annoying thing about it is the startup time. It took a while to load up a 4 MB English dictionary into memory. Some of my other puzzle solvers also use the same dictionary. Wouldn't it be cool if you only need to load this dictionary once and all of the apps could use it? It would stay resident in the heap and ready to be used in different applications and between runs.

One other solution is to use a database but this is not always preferable, mostly due to speed, and of course it is not as elegant. I wanted to use the dictionary object as a native Java object. The idea was shelved for awhile until I came to work with Terracotta, whose distributed shared objects (DSO) might just pull off the resident-heap-memory idea nicely.

First, let's take look at the puzzle solver. Given a 4 by 4 board, the main objective is to find as many words as possible that can be constructed from the letters of sequentially adjacent cubes. The board I’m solving in the game has the content as follows:
c  a  t  d
l i n e
m a r o
p e t s

Some obvious words are: calm, line, mine, and dent.

The program will use the dictionary to scan for all possibilities. A recursive algorithm works great in solving this puzzle. For every possible path, it will look up the current word in dictionary. So let's see how we get the dictionary loaded into memory.

In the Terracotta world, that would mean loading the data into a root (shared object). That shared object will be transparently clustered and made available to any other JVM in the cluster.

The dictionary is implemented as a Trie for fast retrieving. The dictionary loader will read words from a file, one word per line and insert into the trie’s structure. For efficiency, we'll batch the inserts. Here I choose the batch size to be 50. Adjusting this number will affect the load time.


package dictionary;

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.List;
import java.util.Vector;


public class DictionaryLoader {

private Dictionary dictionary = new Dictionary();

public void load(File dictFile) {
int batchSize = 50;
List<String> batchOfWords = new Vector<String>();

BufferedReader reader = null;
try {
reader = new BufferedReader(new FileReader(dictFile));
String word;
while ((word = reader.readLine()) != null) {
batchOfWords.add(word);

if (batchOfWords.size() == batchSize) {
synchronized (dictionary) {
dictionary.add(batchOfWords);
batchOfWords.clear();
}
}
}

/* add the rest of the words left in the batch */
if (batchOfWords.size() > 0) {
synchronized (dictionary) {
dictionary.add(batchOfWords);
}
}

System.out.println("size = " + dictionary.size());

} catch (Exception e) {
e.printStackTrace();
}

finally {
try {
if (reader != null) reader.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}

public static void main(String[] args) {
DictionaryLoader loader = new DictionaryLoader();
long elapsed = System.currentTimeMillis();
loader.load(new File("dict.txt"));
elapsed = System.currentTimeMillis() - elapsed;
System.out.println("Time took to load the dictionary (ms): "
+ elapsed);
}
}



In the Terracotta configuration file, tc-config.xml, we declare the dictionary field to be a shared "root." The entire graph of objects referenceable by this root automatically becomes clustered by Terracotta. We also give this root field a cluster-wide name ("dictionary") with the root-name tag. This is very important because this is how other applications get access to this same root.


<root>
<field-name>dictionary.DictionaryLoader.dictionary</field-name>
<root-name>dictionary</root-name>
</root>



To test our little dictionary, I wrote the DictionaryLookup app. It also declares a dictionary object, but names it differently.


package dictionary;

public class DictionaryLookup {

private static final Dictionary dict = new Dictionary();


public void checkWord(String word) {
if (dict.isWord(word)) {
System.out.println("'" + word + "' is a word" );
}
else if (dict.isPrefix(word)) {
System.out.println("'" + word + "' is a prefix");
}
else {
System.out.println("'" + word + "' is NOT found");
}
}


public static void main(String[] args) {

DictionaryLookup dl = new DictionaryLookup();
String[] words = {"eat", "my", "shorts", "homer", "crapola", "dict",
"config", "configuration", "sweet", "abracadabra"};

for (int i = 0; i < words.length; i++) {
dl.checkWord(words[i]);
}
}
}


The field "dict" is declared as root in tc-config.xml but that doesn’t mean the server will have 2 roots (namely two clustered versions of dictionary objects). The trick is the root-name tag. It tells the server to treat these two roots as one, interchangeably.

<root>
<field-name>dictionary.DictionaryLoader.dictionary</field-name>
<root-name>dictionary</root-name>
</root>
<root>
<field-name>dictionary.DictionaryLookup.dict</field-name>
<root-name>dictionary</root-name>
</root>


The interesting thing about the DictionaryLookup is how it assumes the dictionary content is already there and available for use. All it does is to declare a Dictionary field and Terracotta automatically assigns the same “dictionary” shared root to that field.

DictionaryLookup has proven that this approach works correctly and as I wanted. I can go ahead and attach the dictionary to our puzzle solver:

<root>
<field-name>dictionary.DictionaryLoader.dictionary</field-name>
<root-name>dictionary</root-name>
</root>
<root>
<field-name>dictionary.DictionaryLookup.dict</field-name>
<root-name>dictionary</root-name>
</root>
<root>
<field-name>games.boggle.Board.theDictionary</field-name>
<root-name>dictionary</root-name>
</root>



If you look at Board.java, you'll see how the game can focus on its main logic without having to worry about loading up the dictionary in memory. This eliminates huge amount of time if you choose to use a really big size dictionary. And not only just one application can use dictionary at a time; multiple applications from multiple networks can take advantage of this network attached memory.

Source code available here.