My name is Guido

I have been playing around with meteor, an open-source platform for building web apps. The result is a 200 LOC game ladder with a live demo.

The platform is built on top of nodejs, what is great. In my opinion, it is not yet ready for production environments, but I am really impressed with how fast you can create simple web applications with live page updates, automatic data synchronization and many other niceties I have never seen before in any other web framework.

ELO algorithm

There is an open issue with the ranking algorithm. I am looking for a javascript implementation of the ELO algorithm. I am waiting for your pull requests!

Instant Servers is the infrastructure as a service (IaaS) system I have been working on during the last months in Telefónica Digital.

The service offers a public REST API (Cloud API) that is super simple to use. However, in this post I will show you how to manage your infrastructure using a Java client, without dealing with HTTP requests.

Build the Cloud API client

Man does not live by nodejs alone. There is an instantservers project at github you can easily clone and compile (pull requests are also welcome). In the future it will be published as a proper maven artifact, so you can skip this point.

git clone https://github.com/telefonicaid/instantservers.git
cd ./instantservers/instantservers-api-client
mvn install


That will generate an instantservers-api-client-1.0.0.M1.jar library you can use in your own applications.

Deploy your first virtual machine

To deploy a virtual machine on Instant Servers cloud you only need to choose a name for the machine, a package that corresponds to the hardware configuration (cpu, mem, disk) you need, and a dataset that represents the image or template you want to use (i.e. ubuntu 12.04, mongodb, smartos, etc).

Let’s code speak.

package net.guidogarcia;

import com.tdigital.instantservers.model.cloud.Machine;

public class InstantServersExample {
    // there are several datacenters, I use Madrid "eu-mad" in this example
    private static final String CLOUDAPI_URL =
            "https://api-eu-mad-1.instantservers.telefonica.com";

    public static void main(String[] args) throws Exception {
        CloudAPIClient client =
                new CloudAPIClient("username", "password", CLOUDAPI_URL);

        Machine machine = new Machine();
        machine.setName("smallmachine");
        machine.setPackage("g1_standard_1cpu_512mb");
        machine.setDataset("sdc:sdc:smartos64:1.6.3");

        Machine deployed = client.createMachine(machine);
        System.out.printf("Machine id is %s", deployed.getId());
    }
}

You will notice that virtual machines are up and running in a matter of seconds. This is due to the fact that the virtualization is based on rock solid Solaris zones.

You will need a username and a password to authenticate API calls, but you can sign up for Instant Servers for free (machines are still not free but you can try it for something like 6 cents per hour).

If anyone is interested in other API operations or about cloud computing in general, leave a comment and I will be happy to write more posts about it.

Few weeks ago I could not resist the temptation to buy a Raspberry Pi, the super-cheap 35$ computer that comes with 256MB of RAM and a ARM CPU running at 700MHz and fits in your pocket (more information in wikipedia).

See how nice it looks. I am more of a software guy, so the first thing I did was to install node.js (v0.6.19) develop the simplest web server you can create in node (5 lines, it simply returns a 200 HTTP response code without any contents) and put the beast to work.

var http = require('http');
http.createServer(function (req, res) {
  res.writeHead(200);
  res.end(); 
}).listen(1337);

The benchmark

I was interested in testing the number of requests per second the application was able to handle running on the Raspberry in the most optimistic scenario. After having some problems running httperf and autobench on Mac OS, I finally went with apachebench (ab), that can be used to do simple load testings.

These are the results of sending 5120 requests to the node web server, at different concurrency levels, using the following command:

ab -n 5120 -c <concurrency> http://192.168.1.36:1337/

Additional information: Each concurrency level has been executed three times from my laptop and using a wifi connection; the graph shows the average value. The Raspberry Pi was running the Raspbian “wheezy” image (downloads).

Open points

Almost 200 requests per second in this non real world application that does nothing. It is not bad, enough to develop and try the ideas I have in mind. To be honest, I still do not know why the performance drops so much when the concurrency is 512, or which part (my laptop vs the raspberry) is the bottleneck and why. Any ideas?

I have to measure other aspects like CPU and memory usage. In a quick glance, it seems that the CPU quickly goes over 90% usage even with small concurrency leves. I still appreciate this piece of hardware, but in the future I will try to overclock the processor. The memory was under 10%, what is not strange in this simple application.

I am also waiting for the Java Virtual Machine, that is supposed to be included in the default file system in future releases, to repeat the benchmarks (and probably see how it eats the memory).

It seems interesting, from a research point of view, to build a cluster and see how it scales. Donations for this purpose are highly appreciated :)

Fraud detection is a topic applicable to many sectors (financial, insurance, etc). The method explained in this post is applied in the market research field by Gather Precision (a great market research tool developed by Gather Estudios, BTW), as an early signal to detect frauds in opinion polls.

Imagine you have four field workers (Peter, John, Mary, Ann) taking surveys on the street. They spend different times gathering the data, and we want to discover if there are significant differences on the average levels. That would mean that at least one of them is taking too few or too much time completing the surveys.

Field worker = { Times in seconds for each survey he completes }
Peter = { 150, 200, 180, 230, 220, 250, 230, 300 }
John  = { 200, 240, 220, 250, 210, 190, 240 }
Mary  = { 100, 130, 150, 180, 140, 200, 110, 120 }
Ann   = { 200, 230, 150, 220, 210 }

This is one case where ANOVA comes to the rescue. According to wikipedia, in its simplest form, “ANOVA provides a statistical test of whether or not the means of several groups are all equal”, and that is exactly what we are looking for.

We can use Apache Commons Math to perform some statistical tests. It is an interesting Java library, not really focused on statistics, but pretty easy to use and that luckily contains ANOVA.

import java.util.ArrayList;
import java.util.List;

import org.apache.commons.math.*;

public class FraudDetector {
    private static final double SIGNIFICANCE_LEVEL = 0.001; // 99.9%

    public static void main(String[] args) throws MathException {
        double[][] observations = {
           { 150.0, 200.0, 180.0, 230.0, 220.0, 250.0, 230.0, 300.0 },
           { 200.0, 240.0, 220.0, 250.0, 210.0, 190.0, 240.0 },
           { 100.0, 130.0, 150.0, 180.0, 140.0, 200.0, 110.0, 120.0 },
           { 200.0, 230.0, 150.0, 220.0, 210.0 }
        };

        final List<double[]> classes = new ArrayList<double[]>();
        for (int i=0; i<observations.length; i++) {
            classes.add(observations[i]);
        }

        OneWayAnova anova = new OneWayAnovaImpl();
        boolean rejectNullHypothesis =
                    anova.anovaTest(classes, SIGNIFICANCE_LEVEL);

        if (rejectNullHypothesis) {
            System.out.println("Significant differences were found");
        }
    }
}

The question I asked in stackoverflow includes some discussion and additional information about how to determine the rare cases.

One final thought. Despite I am not an expert in this field, I definitely think we should study more about statistics at the University.

This week I have been participating in the 2nd edition of the Tuenti Programming Challenge. I felt a little rusty on my return to top-level competition, but despite I started the competition three days late, I was able to reach level 14 (stats). Not so bad.

The problems I prefer are those with an obvious brute force solution, but that can take advantage of a particular algorithm or data structure. Most of the problems in this edition belong to this category except, perhaps, the challenge 12 which I did not like because I found it too much tricky.

The crazy croupier

The challenge I enjoyed the most was the number 13, the crazy croupier. It is kind of a classical problem with minor variations, where you have to determine how many shuffles you need in a deck of N cards in order to come back to the original position if you cut it at the position L.

The easy -brute force- solution is to iterate and count until the cards are in their original positions, which can be a time-consuming task when the number of the cards is big (up to 10^6 in this case).

The second approach is to convert it to a permutations problem. Once you know where the card 1..N is located after the first shuffle, you can determine the number of shuffles each individual card needs to come back to its location. The least common multiple of the individual results is the total number of shuffles needed.

Show me the code

Here it is (download). I do not know how many participants chose Java to solve the problems. What I have seen so far are solutions in Python (here, here) that seem more compact and PHP (here). It is a pity that the official ranking does not show the execution times :)

/**
 * Crazy Croupier - 2nd Tuenti Challenge - 12
 * 
 * Example:
 * Number of cards: N = 10
 * Number of cards in the first set: L = 3
 * Cards: 10 1 4 2 8 5 6 7 3 9
 * 
 * First set: 10 1 4
 * Second set: 2 8 5 6 7 3 9
 * 
 * Shuffled set: 4 9 1 3 10 7 6 5 8 2
 */
public static void main(String[] args) {
  Scanner scanner = new Scanner(System.in);

  // read number of cases
  int cases = Integer.parseInt(scanner.nextLine());

  for (int i=1; i<=cases; i++) {
    // read N L, for example 10 6
    String line = scanner.nextLine();
    String[] arguments = line.split(" ");

    // N = cards in the deck
    int N = Integer.parseInt(arguments[0]);

    // L cards in the first bunch (where to cut the deck)
    int L = Integer.parseInt(arguments[1]);

    long result = processCase(N, L);
    System.out.printf("Case #%d: %d\n", i, result);
  }
}

/**
 * Returns the number of shuffles required to return the deck
 * to its original order.
 * The algorithm will calculate the number of iterations that
 * each individual card need to come back to its position. The
 * solution will be the least common multiple (lcm) of the
 * individual results.
 */
private static long processCase(int n, int cut) {
  int[] deck = new int[n]; // first deck shuffling result

  shuffleDeck(n, cut, deck);

  // cache source -> target positions for O(1) access
  final Map<Integer, Integer> permutations = new HashMap<Integer, Integer>();
  for (int i=0; i<deck.length; i++) {
    permutations.put(deck[i], i+1);
  }

  // cache to avoid multiple lcd calculations of the same num, O(1) access
  Set<Long> calculatedLcm = new HashSet<Long>();
  long lcm = 0;
  for (int i=0; i<deck.length; i++) {
    long numberPermutations = 1; // we already did the first shuffling
    int currentPosition = i+1;

    // still no at the original position
    while (currentPosition != deck[i]) {
      numberPermutations++;
      currentPosition = permutations.get(currentPosition);
    }

    if (calculatedLcm.contains(numberPermutations) == false) {
      lcm = lcm(lcm, numberPermutations);
      calculatedLcm.add(numberPermutations);
    }
  }

  return lcm;
}

/**
 * Shuffles the deck one time according to the algorithm.
 */
private static void shuffleDeck(int n, int cut, int[] deck) {
  int min = Math.min(cut, n-cut); // number of cards shuffled

  // shuffle two bunch of cards
  for (int i=0; i<min; i++) {
    deck[2 * i] = cut - i;   // 1st bunch
    deck[2 * i + 1] = n - i; // 2nd bunch
  }

  // put the rest of the cards in proper order, at the end
  for (int i=0; i<n - 2 * min; i++) {
    if (cut >= n / 2) { // first bunch is bigger
      deck[n - 1 - i] = i + 1;
    } else { // second bunch is bigger or equal
      deck[2 * min + i] = n - min - i;
    }
  }
}

/**
 * Least common multiple. Probably a more efficient approach can be
 * found but it is good enough.
 */
private static long lcm(long a, long b) {
  if (a == 0 || b == 0) {
    return Math.max(a, b);
  }
  return a * b / gcd(a, b);
}

/**
 * Greatest common divisor, see also {@link BigInteger#gcd(BigInteger)}
 */
private static long gcd(long a, long b) {
  long mod = a % b;
  return mod == 0 ? b : gcd(b, mod);
}

What do you think about it?

Talent is out there

I like these competitions (Google Code Jam, ACM ICPC, etc) a lot and I think it is a great (and cheap) opportunity for technological companies to attract and recruit talent. There are a lot of great coders hidden out there.

Some time ago I wrote a post about how to implement a REST API with Java (spanish). Today I am going to write about how to consume a REST API as a client. More specifically, I am going to use Digg API (probably not the best REST API out there) to search stories by a given keyword.

Show me the code

As it is a third party REST API, I am going to use the client framework provided by RESTEasy, that I find extremely easy to use.

You only have to add one dependency to your pom.xml:

  <dependency>
      <groupId>org.jboss.resteasy</groupId>
      <artifactId>resteasy-jaxrs</artifactId>
      <version>2.3.1.GA</version>
  </dependency>

And you are now ready to start coding. I think the Java code is self explanatory, so here it goes:

import org.jboss.resteasy.client.ClientRequest;
import org.jboss.resteasy.client.ClientResponse;

public class DiggClient {
    private static final String DIGG_SEARCH_ENDPOINT =
            "http://services.digg.com/{version}/search.search";

    public static void main(String[] args) throws Exception {
        ClientRequest req = new ClientRequest(DIGG_SEARCH_ENDPOINT);
        req
            .pathParameter("version", "2.0")
            .queryParameter("query", "health");

        ClientResponse<String> res = req.get(String.class);
        System.out.println(res.getEntity());
    }
}

But I do not want to parse a String…

You might have noticed that the response is converted to a String. In most cases an API will return a XML or a JSON representation of the data as response to the request. In these cases it is great to automatically convert the response into the objects in your Java data model.

For example, these are the domain classes representing (partially) the Digg search results:

class SearchResult {
    private int total;
    private Story[] stories;
    // ... getters/setters
}

class Story {
    private String id;
    private String title;
    // ... getters/setters
}

Digg results are offered as JSON, so you only need to add a Maven dependency to include the providers RESTEasy uses to handle JSON:

  <dependency>
      <groupId>org.jboss.resteasy</groupId>
      <artifactId>resteasy-jackson-provider</artifactId>
      <version>2.3.1.GA</version>
  </dependency>

The resulting Java code remains almost the same:

import org.jboss.resteasy.client.ClientRequest;
import org.jboss.resteasy.client.ClientResponse;

public class DiggClient {
    private static final String DIGG_SEARCH_ENDPOINT =
            "http://services.digg.com/{version}/search.search";

    public static void main(String[] args) throws Exception {
        ClientRequest req = new ClientRequest(DIGG_SEARCH_ENDPOINT);
        req
            .pathParameter("version", "2.0")
            .queryParameter("query", "health");

        ClientResponse<SearchResult> res = req.get(SearchResult.class);
        SearchResult result = res.getEntity();
        System.out.println(result.getTotal() + " matching stories found");
    }
}

Note: you need to annotate your domain Java classes as @JsonIgnoreProperties(ignoreUnknown=true) if the server returns any field that is not present in your domain Java classes.

What if you are using your own API?

If you already have developed your JAX-RS resources, I would suggest to use a proxy-based approach. Take a look at the JAX-RS client factory in Apache CXF, or how to share interfaces between client and server with RESTEasy. This way you reuse more code and makes your code maintenance easier.

Comments about other alternatives (Jersey, etc) are welcome.

In a recent project we had the need to keep a record of the changes made in every domain entity. That is, we need to insert a new record on an audit table every time an entity is created/updated/deleted.

This is not the first time this problem arises. I think this is a the case of a cross-cutting concern, that fits well into the aspect-oriented programming area. I have seen this very same problem in many different projects I have worked on, always solved with one variant of these two approches:

• Use a database trigger, that fires with every change in the entities you need to track.
• Manage it programmatically, a painful solution that contaminates your code.

Hibernate Envers to the rescue

The Envers project “aims to enable easy auditing of persistent classes. All that you have to do is annotate your persistent class or some of its properties, that you want to keep track of, with @Audited. For each audited entity, a table will be created, which will hold the history of changes made to the entity”.

The Envers project is now a Hibernate core module (since 3.5+), so it is really easy to include it in your projects. As promised, you only need to annotate your entities:

@Entity
@Audited
public class MyEntity {
   ...
}

If you are using Hibernate Hibernate 3.x, add the following properties to your persistence.xml, to configure the listeners that need to be called when a persistence related event is fired:

<property name="hibernate.ejb.event.post-insert" value="org.hibernate.ejb.event.EJB3PostInsertEventListener,org.hibernate.envers.event.AuditEventListener" />
<property name="hibernate.ejb.event.post-update" value="org.hibernate.ejb.event.EJB3PostUpdateEventListener,org.hibernate.envers.event.AuditEventListener" />
<property name="hibernate.ejb.event.post-delete" value="org.hibernate.ejb.event.EJB3PostDeleteEventListener,org.hibernate.envers.event.AuditEventListener" />
<property name="hibernate.ejb.event.pre-collection-update" value="org.hibernate.envers.event.AuditEventListener" />
<property name="hibernate.ejb.event.pre-collection-remove" value="org.hibernate.envers.event.AuditEventListener" />
<property name="hibernate.ejb.event.post-collection-recreate" value="org.hibernate.envers.event.AuditEventListener" />

And last, if you are using Maven, include it as a dependency in your pom.xml (the dependency scope is “provided” if you use JBoss AS 7.0.2):

<dependency>
    <groupId>org.hibernate</groupId>
    <artifactId>hibernate-envers</artifactId>
    <version>${envers.version}</version> <-- i.e. 3.6.8.Final -->
</dependency>

That is all. Every change in an entity will be audited in an automatically generated “player_aud” table. This is the simplest and, most important, cleanest way I currently know to solve the aforementioned problem.

The official docs include other features such as logging, querying historical data, advanced configuration and some unsupported features (bags).

Any critics?

Hibernate Envers is so simple that the only improvement I can think about is to see it standardized as part of the next version of JPA, and to include a single configuration property covering 90% of the cases (or even better, discover if the entities are marked as auditable at runtime):

<property name="hibernate.auditable" value="true" /> 

Any comment is welcome.

UPDATE: With Hibernate 4.x it is no longer necessary to add the event listeners to your Hibernate configuration. All you need is to put hibernate-envers on your classpath and annotate your entities.

Gephi is a really cool open-source (GPL) project for visualizing and analyzing network graphs.

Getting started

If you want to start using Gephi you have two choices:

• The blue pill, a simple GUI, pretty easy to use, that offers many network metrics, statistical algorithms (clustering, etc) to analyze your own graphs. The story ends.
• The red pill, the Gephi Toolkit. The toolkit is a standard Java library that can be integrated with your own code if you need to analyze graphs. That is what we need.

Both of them are really modular, and can also be extended with big variety of available plugins, contributed by third party developers.

Crawling your Twitter network

Twitter offers a REST API. In this case I have used Spring Social, an extension of the Spring Framework that simplifies the connection with social networks such as Linkedin, Facebook or Twitter (docs).

For example, obtaining the list of followers of a given user is something as simple as:

TwitterTemplate twitter = new TwitterTemplate();
List<TwitterProfile> result =
        twitter.friendOperations().getFollowers("palmerabollo");

The bad news is that the API is rate limited to 150 requests/hour, and you can increase it if you use OAuth to authenticate your requests. This limit is too low (I think Twitter is trying to protect their data from being extracted) and forced me to introduce a basic cache layer (just a Map) to save some requests. The cache is coupled with the application code, it could be certainly improved.

Final result

You can find the code at github. Remember that this is a proof of concept, so it can be improved a lot. I am waiting for your pull requests.

Lessons learned and future work

• Twitter API is very restrictive. A cache tries to solve this problem but it is still not possible to retrieve the deepest levels of your network. It would be fun to use a NOSQL graph database such as neo4j, that even has a Gephi plugin available, to store the data. This question I asked in the Gephi Forum is a good starting point if you are interested on it.
• Gephi Toolkit and its plugins are not available from a Maven repository, so I included them as system libraries in my pom.xml. This is the first time I do it, and it is probably a bad practice. I would like to hear your opinion about this.
• Gephi is a really interesting and powerful project, but the documentation and examples could be improved.
• It would be very interesting to play with other Gephi advanced features such as filtering, clustering. For example, to detect “communities” or to detect the most influential nodes in your network.
• Spring Social simplifies your life, offering a common interface to work with different social networks, saving you the pain and hassle of dealing with every different API out there.

By the way, if anyone else is interested in offering this service through a web interface, please let me know.

ACRA (Application Crash Report for Android) is a extremely helpful Android library that allows your mobile application to send a report to different destinations when it crashes -miserably-.

It is both powerful/configurable and very easy to use at the same time, allowing:

• Different kind of notifications (silent, toast, status bar, etc)
• Detailed crash reports (stack traces, device model, system versions)
• Many targets (email, shared google spreadsheet, etc)

In my example I have used a shared google document as the target where the notifications are sent, and I have chosen not to show anything to de user when the application crashes (silent mode).

Once you download and add the acra-x.x.x.jar file to your project, you simply need to annotate your Application class:

import org.acra.ACRA;
import org.acra.ReportingInteractionMode;
import org.acra.annotation.ReportsCrashes;
import android.app.Application;

@ReportsCrashes(
		formKey = "<my_google_doc_key>",
		mode=ReportingInteractionMode.SILENT)
public class MyApplication extends Application {
	@Override
	public void onCreate() {
		super.onCreate();		
		ACRA.init(this);
	}
}

It is important to add the permissions required to use the Internet connection in your AndroidManifest:

<uses-permission android:name="android.permission.INTERNET" />

A crash report

Once your application crashes (it will crash), you receive a lot of useful information such as the device status:


locale=es_ES
hardKeyboardHidden=HARDKEYBOARDHIDDEN_YES
keyboard=KEYBOARD_NOKEYS
keyboardHidden=KEYBOARDHIDDEN_NO
fontScale=1.0
mcc=214
mnc=7
navigation=NAVIGATION_TRACKBALL
navigationHidden=NAVIGATIONHIDDEN_NO
orientation=ORIENTATION_PORTRAIT
screenLayout=SCREENLAYOUT_SIZE_NORMAL+SCREENLAYOUT_LONG_YES
seq=5
touchscreen=TOUCHSCREEN_FINGER
uiMode=UI_MODE_TYPE_NORMAL+UI_MODE_NIGHT_NO
userSetLocale=false

width=480
height=800
pixelFormat=1
refreshRate=60.0fps
metrics.density=x1.5
metrics.scaledDensity=x1.5
metrics.widthPixels=480
metrics.heightPixels=800
metrics.xdpi=254.0
metrics.ydpi=254.0


And the stacktrace, in a transparent way for the user:


java.lang.NullPointerException
at java.util.Collections.sort(Collections.java:1971)
at net.guidogarcia.SelectActivity$a$1.run(SourceFile:197)
at android.os.Handler.handleCallback(Handler.java:587)
at android.os.Handler.dispatchMessage(Handler.java:92)
at android.os.Looper.loop(Looper.java:144)
at android.app.ActivityThread.main(ActivityThread.java:4937)
at java.lang.reflect.Method.invokeNative(Native Method)
at java.lang.reflect.Method.invoke(Method.java:521)
at com.android.internal.os.ZygoteInit$MethodAndArgsCaller.run(...)
at com.android.internal.os.ZygoteInit.main(ZygoteInit.java:626)
at dalvik.system.NativeStart.main(Native Method)


In my case the output seems pretty cryptic because I was also trying to integrate Proguard in the application.

Open points

I am far from being an Android expert, so I would like to know if there is another way to submit this kind of reports that does not need an external library (please use the comments if you know how to do it).

The version I have used is ACRA 3.1.1, so this article might be outdated with the release of ACRA 4.x.

For those who are not familiar with it, Spring Roo is an open source tool that provides rapid application development of Java applications, using standard Java technologies underneath.

Last week I gave a presentation (slides) about how to start using Spring Roo to some co-workers in Telefónica Digital. I have recorded a video with captions for those who couldn’t attend (use fullscreen mode and 720p).

The video does not cover some interesting aspects about Spring such as Spring Data (I will write a post about it), or how to completely remove Spring Roo from your project (right button > Refactor > Push In and that is all).

If you are planning to give it a try, I strongly recommend to use Spring Roo 1.2.x in order to create layered architectures (controller + service + repository), instead of using the Active Record pattern (in words of Martin Fowler, “An object that wraps a row in a database table or view, encapsulates the database access, and adds domain logic on that data”)

When would I use Spring Roo

Spring Roo is a relativly young project (Q4 2009), it is evolving really fast, and I think it is especially useful:

• To create your Spring project structure. Roo generates a typical Maven + Spring project. I think it is a good idea to use a proven structure and keep it consistent in every new project you start. Remember that you can remove Roo at any time, so you are not tied to it.
• To develop domain-intensive applications, that fit well with a CRUD user interface. Even administrative web interfaces to your existing applications seem good candidates to be developed with the help of Spring Roo.

Comments are open. Where are now the Ruby on Rails guys?