The CAP theorem made simple

The basic idea of the CAP theorem is that in a distributed system, you must sacrifice either data consistency, availability, or partitioning support.  Here I'm going to make my attempt to show how the trade-off between these three goals quickly emerges in designing a simple distributed key-value store.

First, why do we want the key-value store to be distributed in the first place?  One good reason is performance -- we want to have multiple nodes available to service read requests on items in the data store. So fast performance is a fourth design goal, one that is not always highlighted.

Let's suppose clients are connected to each node in the cluster and, for each request, a server is chosen at random. Our first consistency requirement is that, in general, it should not matter which node receives a read request, the same value should still be returned.  One way to satisfy this is to require that nodes propagate write requests to other nodes in the cluster.  When a write request is received, the node writes the new value to its local copy of the store, and then forwards the request to the other nodes in the cluster.  After some period of time, barring node failure or loss of network connectivity, the updated value should be present on all nodes.

However, this leads to another consistency problem.  Suppose two clients write different values to the same key at nearly the same time, and these two write requests are processed by different nodes in the cluster.  The system can easily end up in an inconsistent state, where some nodes have one value for the key and other nodes have a different value, and the value that is returned for a given read request is unpredictable.

One way to address this consistency challenge is to impose the constraint that, at any point in time, only a single node is allowed to modify the store.  All writes must first be routed to this master node, which updates the store and then forwards the request to the rest of the cluster. Write requests which are concurrent will be serialized through the master, ensuring that the later request takes precedence.  A protocol like Paxos can be used to satisfy the requirement that only a single master is ever active, and that if this master goes down, a new one will be elected.

So now we have a system that has good consistency and read performance.  Requiring that all writes go through a single node means that we have had to sacrifice a little bit of write performance.  What about availability and partitioning?  Well, as long as network connectivity is good and no nodes fail, we have no problems with availability -- write and read requests should continue to be processed. We have C and A, but we have not yet explored what happens when P occurs.  Let's consider the case where a network partition takes place and the cluster is divided in to two groups of nodes which cannot communicate with each other.

Now we have a decision to make.  Will we allow a master to be elected on both sides of the partition?  In that case writes sent to either side of the partition will be processed, preserving both read and write availability.  However, we will quickly get in to an inconsistent state, where values on one side differ from those on the other.  We have A and P, but not C.

Another approach would be to say that on the side containing a minority of the system nodes, no writes or reads will be accepted.  Then our consistency requirements are met, but we have sacrificed some performance.  Also, for clients on the minority side of the partition, we have lost read and write availability. Here we have C and P, but not A.

Hope this post helps some folks get a better grasp of CAP.  Feedback welcome on how this description could be improved!

Git and Gerrit workflows for long-running topic branches

At Optemo, we frequently have a topic branch that runs for days or weeks before we are ready to merge it in to master and deploy it to the production site. When we are finally ready to merge such a branch, we would like to have a code review in Gerrit which captures all of the changes that will be added to master.  This page describes two possible approaches we have found for achieving this.  The approach we prefer, especially when multiple programmers are working on the same topic branch, is Workflow 1. However, if only a single programmer is working on the topic branch and the branch is not expected to be very long-lived, Workflow 2 is also an option.

We are by no means Git and Gerrit experts yet, so let me know if you have any comments or alternative approaches to suggest.

Workflow 1: Using merge

In this workflow, you use merge when you need to update the topic branch with the latest changes in master:

1. git checkout <topic branch>
2. git fetch origin
3. git merge origin/master

You follow the same process when you need to update your topic branch with changes made to this branch by another programmer:

1. git checkout <topic branch>
2. git fetch origin
3. git merge origin/<topic branch>'''

When you are ready to push the changes for code review, you merge your topic branch in to master and use the --squash option to create one big commit.

1. git checkout master
2. git pull origin
3. git checkout -b <temp branch>
4. git merge --squash <topic branch>
5. git push origin HEAD:refs/for/master

Note that once the change has been submitted by the reviewer and merged in to master, you should stop using the old topic branch. New work should happen in a new topic branch created off the latest version of master.

Workflow 2: Always rebase on top of master

In this approach, whenever you need to update the topic branch with the latest changes in master, you follow the following steps:

1. git checkout <topic branch>
2. git fetch origin
3. git rebase origin/master

This takes the changes in the topic branch and applies them on top of master's HEAD.

When you are ready to submit the topic branch for code review, you follow a similar process. You rebase the topic branch on master, then push the changes in the topic branch for code review. You can do an interactive rebase using the -i option, which will allow you to squash all the commits on the topic branch together in to one big commit:

1. git checkout <topic branch>
2. git fetch origin
3. git rebase -i origin/master
4. git push origin HEAD:refs/for/master

Note: If you are following this workflow, it is important that you do not use merge to update the topic branch with the contents of master. If you do, and you later perform a rebase prior to submitting your changes for code review, you may find that you have to redo work you did in earlier merges. Specifically, you may have to manually resolve conflicts that you previously resolved.

Eclipse Plugins that need early startup

A pattern for Eclipse plugins that need early startup, and also have views (which may or may not be part of the active perspective on startup):

1. Implement the org.eclipse.ui.startup extension point in a separate class, as the docs recommend, but don't actually do any work in the earlyStartup() method.
2. Define a finishInit() method in your AbstractUIPlugin which is going to do the actual work of initializing your plugin. Also define an initComplete boolean field. Check this field at the start of finishInit(), and set it at the end, to ensure that the code inside finishInit() is only executed once.
3. In the start() method of your AbstractUIPlugin, first initialize your static singleton instance field.  Then invoke finishInit() on the UI thread with PlatformUI.getWorkbench().getDisplay().asyncExec(). (Why? If your view is not in the active perspective, then start() will be called by a non-UI thread. The effect of this is that the workbench is not yet fully initialized when your start() method is called.)
4. In the createPartControl() method of your views, first call finishInit() on the singleton AbstractUIPlugin instance. In the case where your view is present in the active perspective, createPartControl() will be called before the async call to finishInit() is processed on the UI thread. So you call it at the start of createPartControl() to make sure plugin initialization completes before you begin creating your views.

Reducing the effort of creating JUnit test oracles

So you've gone to the trouble of defining a set of inputs that exercise a particular path through your code. Now you need to write the oracle: the chunk of code that verifies the result is what you expect. This can often be just as much effort as carefully choosing those test inputs. It can also be quite error-prone -- if you're like me, you find a lot more bugs in your tests than in the code your testing!

Here's an approach that can save some time in certain cases. You serialize the result of the test to a text file, then verify (by inspection) that it matches your expectations. For subsequent runs of the test, your test driver reloads the previous result and compares it to the result obtained on the current run.

There are some issues, of course. The test can be a bit more fragile -- if any field of the test result changes, the test will fail. But then updating the oracle will be quick -- just need to dump the new result to a text file, verify it again, then make it the new expected result.  Diff utilities can speed up the re-verification process.

Serialization of the result can get tricky, especially if your result is a tree of objects. Some objects in the tree may not lend themselves to serialization. For others, it may not be appropriate to consider them part of the test result. In cases like this, you may need to dig in to the documentation of the serialization library you are using. The approach I am proposing here might just not be feasible in some cases.

A third concern is that in inspecting the serialized result you could miss problems that you would catch if you manually wrote the oracle. This is subjective, but after using this technique for a few months, I feel that inspection can catch most problems. And, of course, manually constructed test oracles can have bugs that go undetected too!

Here is a JUnit test driver that implements this approach using the Jackson JSON library for serialization and deserialization. Note that with the setup below, only public fields and getters will be checked (but Jackson can be configured to look at private fields as well).

import java.io.IOException;
import java.io.InputStream;
import java.io.StringWriter;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

import org.codehaus.jackson.JsonFactory;
import org.codehaus.jackson.JsonGenerator;
import org.codehaus.jackson.JsonNode;
import org.codehaus.jackson.JsonParseException;
import org.codehaus.jackson.JsonParser;
import org.codehaus.jackson.map.ObjectMapper;
import org.codehaus.jackson.util.DefaultPrettyPrinter;

import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;
import org.junit.runner.RunWith;
import org.junit.runners.Parameterized;
import org.junit.runners.Parameterized.Parameters;

@RunWith(Parameterized.class)
public class AutoGeneratedOracleExampleTest {
    private JsonNode testData;
    private String testName;
   
    @Parameters
    public static Collection<Object[]> getParameters() {
        return Arrays.asList(new Object[][]{
                { "Test1" },
                { "Test2" },
                });
    }
   
    public  AutoGeneratedOracleExampleTest (String testName ) 
            throws JsonParseException, IOException {
        this.testName = testName;
    }
   
    @Before
    public void setup() throws JsonParseException, IOException {
        InputStream testDataStream =
            CodeElementExtractorTest.class.getResourceAsStream(
                "AutoGeneratedOracleExampleTestData.json");
        if (testDataStream == null) {
            throw new IOException("Test data file not found");
        }

        try {             
            JsonFactory factory = new JsonFactory();
            JsonParser parser = factory.createJsonParser(testDataStream);
            parser.setCodec(new ObjectMapper());
            testData = parser.readValueAsTree();
        } finally {
            testDataStream.close();
        }
    }
   
    @Test
    public void runTest() throws IOException {
        Object result = ... 
       
        JsonNode expected = getExpectedResult(testName);
        assertEquals("formatted actual: " + getJsonString(result), 
            expected, getJsonNode(result));
    }
   
    private JsonNode getExpectedResult(String testKey) {
        return testData.get(testKey);
    }
   
    private JsonNode getJsonNode(Object obj) throws JsonParseException, IOException {
        JsonFactory factory = new JsonFactory();
        JsonParser parser = factory.createJsonParser(getJsonString(obj));
        parser.setCodec(new ObjectMapper());
        return parser.readValueAsTree();
    }
   
    private String getJsonString(Object obj) throws IOException {
        ObjectMapper mapper = new ObjectMapper();
        StringWriter writer = new StringWriter();
       
        JsonGenerator jsonGenerator =
            mapper.getJsonFactory().createJsonGenerator(writer);
        jsonGenerator.setPrettyPrinter(new DefaultPrettyPrinter());

        mapper.writeValue(jsonGenerator, obj);
        return writer.toString();
    }
}

Browser extensions that need to call native code

I've been working on a browser extension for Firefox and Chrome that needs to invoke some native code.  It turns out that the only way to do this in Chrome is through an NPAPI plugin (NaCl is not an option here because the native code needs to perform some privileged operations).  Luckily there is the Firebreath project which makes it pretty easy to create a cross-platform NPAPI plugin for Mac, Linux, and Windows.  You can load the plugin once in the background page of your Chrome plugin and then your content scripts can communicate with it through message passing.

In Firefox, however, there are challenges to calling an NPAPI plugin from an extension.  The two options are (a) to load the plugin in to the DOM of the browser itself; or (b) to inject the plugin in to the DOM of each page as it is loaded.  Option (a) seems like a bit of a hack, and (b) has security issues (since scripts on the page could then invoke the plugin).

A better option in Firefox is to use the js-ctypes API to call in to a shared library written in C.  The shared library only needs to be loaded once, and is not accessible to scripts on web pages.  The library is just a vanilla C shared library, you don't have all the overhead of conforming to the NPAPI plugin interface.  The drawback, of course, is that you have to create both an NPAPI plugin and a js-ctypes shared library if you want to support Chrome and Firefox.  But I felt it was worth the extra effort, given the limitations of calling NPAPI plugins from Firefox extensions.

To minimize code duplication, I created a static library which contains most of my functionality, and then linked it into the NPAPI plugin and the js-ctypes shared library.

Dynamic bookmarks for developers

Some information here on the Eclipse plugin I have been working on:

Reverb Eclipse plugin on Google Project Hosting

The idea is to automatically recommend a set of web links based on the Java code you are currently working on in the IDE. To help ensure these are links you are interested in and may actually find useful, they are drawn from your own web browsing history. We will be starting a user study soon -- I hope you will give it a try!

Tips for using EGit and GitHub

EGit is an Eclipse plugin for working with Git repositories.  Here are a few tips based on my recent experience.

• Install Egit from the Indigo update site (http://download.eclipse.org/releases/indigo), it's under the Collaboration subgroup.
• Create the repository in GitHub first.  Then use the EGit "Git Repositories" view in Eclipse to create a local clone (there's a button to do this in the upper right-hand corner of the view).  Creating the repository in GitHub first helps ensure that pushing and pulling between your local clone and the main GitHub repository is straight-forward.
• When cloning the repository, use the HTTP repository link provided in your GitHub dashboard.  If you stick with HTTP, it seems you can avoid the laborious process of installing the Git binaries on your local machine, setting up SSH keys, etc.
• You can then add an existing Eclipse project to the repository through Team > Share Project > Git.

JFace Wizard Tips and Tricks

The JFace wizard classes offer a decent, basic framework for creating user interface wizards.  However, I found it hard to figure out how to accomplish a few basic things, such as getting notifications on page changes, disabling the Back button, and changing the text on a button.  These things are not that difficult to do, as it turns out, but the API documentation is very limited.  And while there are some good tutorials out there, they do not cover these tasks -- I had to dig in to the source code to find the solutions.

First, changing the text on a button.  You need to subclass WizardDialog and override createButtonsForButtonBar():

@Override 
protected void createButtonsForButtonBar(Composite parent) {
    super.createButtonsForButtonBar(parent);
    Button finishButton = getButton(IDialogConstants.FINISH_ID);
    finishButton.setText("Submit");
}

What about getting notified when the page changes (i.e. the user clicked the Next or Back buttons)?  In your Wizard's addPages() method, you can add the necessary listeners:

public class MyWizard extends Wizard implements IPageChangingListener, IPageChangedListener {
    @Override
    public void addPages() {
        // add pages here ...
        this.addPage(new MyPage());
        
        WizardDialog dialog = (WizardDialog)getContainer();
        dialog.addPageChangingListener(this);
        dialog.addPageChangedListener(this);
    }

    @Override
    public void pageChanged(PageChangedEvent event) {
        // ...
    }

    @Override
    public void handlePageChanging(PageChangingEvent event) {
        // ...
    }
}

Disabling the back button is harder than it should be, due to non-intuitive behavior in the default implementation of WizardPage.getPreviousPage().  You can call setPreviousPage( null ), and getPreviousPage() still returns the previous page.  You need to override the implementation of getPreviousPage() in order to disable the back button:

public abstract class MyWizardPage extends WizardPage {
    private boolean backButtonEnabled = true;

    public void setBackButtonEnabled(boolean enabled) {
        backButtonEnabled = enabled;
        getContainer().updateButtons();
    }
    
    @Override
    public IWizardPage getPreviousPage() {
        if (!backButtonEnabled) {
            return null;
        }
        return super.getPreviousPage();
    }
}

Finally, if you want to choose when to enable the Finish button, you will probably be overriding the canFinish() method on your Wizard subclass.  I did this, but made the mistake of creating my own canFinish boolean field.  This shadowed a field of the same name in the parent class -- as a result, I could never get my Finish button to become enabled!  Changing the field name to myCanFinish fixed the issue.

Subclipse on Windows

I ran in to a little glitch with Subclipse (the Eclipse plugin for Subversion access) on Windows.  In general, this plugin works well, but I was using "Team > Add to svn:ignore" to exclude files from version control.  For the first file (a directory, actually), this worked fine.  For the second file, I kept getting an error from the Subversion server (Google project hosting, in my case) when I tried to commit.

I finally suspected that this might be a Windows-specific issue, since multiple entries in svn:ignore are separated with carriage return and/or linefeed. I switched the Subclipse SVN client from the pure Java SVNKit to JavaHL (under Window > Preferences > Team > SVN).  This (mostly) resolves the issue.  You still sometimes get a conflict on the project when you try to commit a change to the svn:ignore property.  This conflict can be fixed by first selecting to update the project file from the Subversion server, then committing your changes to it (that seems strange, I know, but it seems to work and I have not lost any changes yet).

Note that if you are using 64-bit Windows, switching from SVNKit to JavaHL is a little trickier.  If you are using a 64-bit JVM, you will need to separately install a 64-bit version of the JavaHL library.  More details here.

Really simple functional extensions for Java

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Util {

    public interface Predicate<T> {

        boolean check(T instance);

    }

   

    public interface Attr<T, A> {

        A get(T instance);

    }

    public static <T> List<T> truncate(List<T> list, int maxLength) {

        if (list.size() > maxLength) {

            return new ArrayList<T>(list.subList(0, maxLength));

        }

        return list;

    }

    public static <T> List<T> filter(List<T> list, Predicate<T> checker) {

        List<T> filtered = new ArrayList<T>();

        for (T item: list) {

            if (checker.check(item)) {

                filtered.add(item);

            }

        }

        return filtered;

    }

   

    public static <T> int count(List<T> list, Predicate<T> checker) {

        int count = 0;

        for (T item: list) {

            if (checker.check(item)) {

                count++;

            }

        }

        return count;

    }

   

    public static <T, A> Map<A, List<T>> rollup(List<T> list, Attr<T, A> attr) {

        Map<A, List<T>> result = new HashMap<A, List<T>>();

        for (T item: list) {

            A key = attr.get(item);

            List<T> itemList = result.get(key);

            if (itemList == null) {

                itemList = new ArrayList<T>();

                itemList.add(item);

                result.put(key, itemList);

            } else {

                itemList.add(item);

            }

        }

        return result;

    }

}

Eclipse and Maven

Tips for those getting started with Maven and Eclipse. If you're like me, you want to try using Maven for dependency management, but you prefer to leave the building of your project to Eclipse. To start with, install the m2eclipse plugin from this location.

To convert an existing Java project to Maven:

• Right-click project > Configure > Convert to Maven Project

After doing this, you may notice two issues:

• Project source folders have been converted to regular folders. Right-click the folder and select Build Path > Add to Build Path to fix this.
• The JRE system library version has changed. Go to Project Properties > Java Build Path > Libraries to make sure your JRE system library is correct.

Adding new dependencies using the plugin's cool lookup tool is straight-forward. Right-click the generated pom.xml and select Maven > Add Dependency.