Google AppEngine Disappointment

I was eager to try out Google’s AppEngine for Java, but I was soon disappointed to find out that the AppEngine is just a partial implementation of the Java APIs. The biggest problem with the missing APIs is that a lot of 3rd party software and libraries simply won’t work, which means that you loose all the benefits of the mature Java ecosystem. Porting an existing Java application to AppEngine is simply out of question.

Another major problem is persistence. You cannot deploy your favourite DBMS on AppEngine, you have to use Google’s Datastore, which is not a common relational DB. Google makes available JDO and JPA interfaces to access the Datastore. However, these are also partial implementations which provide just a familiar syntax for a substantially different persistence mechanism and create a false sense of familiarity. This is particularly true when you try to refer to the JDO documentation for troubleshooting, but you discover that the semantics of Google’s JDO implementation are quite different. It would have been much better to stick with a proprietary persisntece API and not pretend to fill the gap to reach JDO or JPA semantics.

Another important missing feature are Threads, which makes AppEngine a poor choice for massive computations since paralellization of subtasks is not possible, at least until Google implement the AppEngine Map/Reduce service.

Lastly the overall sense of a finished product is not there. Things that one would expect to work, fail for some obscure reason. Error messages are often cryptic. Apart from an introductionary tutorial, documentation is quite scarce. I guess this is justifiable since AppEngine is still a beta release, but I would rather consider it a pre-alpha. I was expecting much more considerate choices from the smart Google engineers, who have amazed us many times so far.

There were a few things I did like about the app engine. For example, the Eclipse plugin  simplifies configuration, testing and deployment. Integration with other Google services are a promissing factor. All in all, Google AppEngine is an interesting toy, but compared to other solutions it’s remains just a toy. If you want to play with it, I suggest you should read this.

Parallel For Loop in C#: Part 2

In the previous part we have implemented a ThreadPoolExecutor that accepts tasks and executes them in parallel. In this part we will implement a parallel for loop.
The parallel for needs to iterate over a collection of items and invoke the specified closure on every item. It has to perform these invocations in parallel and the next instruction should be executed only after all the elements have been processed. When used, it should look something like this:

ForEach(distributionList, (destination) => {
   Message msg = new Message(destination.Address);
   msg.Content = Encrypt(Content, destination.PublicKey);
   msg.Send();
   Console.WriteLine("sent message to" + destination.Name);
}

So the signature of the method should be:

public static void ForEach(ICollection<T> collection, Action<T> action)

We know that we need to use the ThreadPoolExecutor, enqueue all the actions and execute them and then wait for the executor to finish. But we have a mismatch. The ForEach() method takes a parameterized action, while the thread executor takes an action without any arguments. What we need to do is construct a set of parameterless actions by adding each element of the collection as the parameter of the parameterized action.

action(x) -> action1, action2, action3… actionN

We can do it with one simple line of code:

Action parameterlessAction = (() => parameterizedAction.Invoke(element));

This was first invented in lambda calculus, and it was called a closure, because the function gets closed over the free parameter. Hence the (slightly misnamed) term closure that the rest of us programmers use. Most of the programmers would be more familiar with the term currying to define this operation.

Our code would take the following form:

public static void ForEach(ICollection<T> collection, Action<T> action) {
            ThreadPoolExecutor executor = new ThreadPoolExecutor();

            foreach (T element in collection) {
                Action parameterlessAction = (() => parameterizedAction.Invoke(element));
                executor.AddTask(parameterlessAction);
            }

            executor.Finish();
   }

   executor.Finish();
}

However, this code has a well hidden and nasty bug. The bug is caused by a certain property of closures, which makes them dangerous in the wrong hands. This is also one of the major reasons why many Java developers don’t want closures. Don’t you see it? Hmmm… Are you ready for using closures?
Closures require that their free variables have an extent at least as long as the lifetime of the closure itself.
In our scenario we are referring to element inside the parameterlessAction, but the value of element changes with each iteration. So by the time we invoke the closure unexpected results can happen. Fortunately enough, in our case, Visual Studio was able to detect this situation through static analysis and shyly display a warning in the form of a blue squiggly underline. The solution is to assign element to a temporary variable, and the compiler will be smart enough to allocate that variable on the heap instead of the stack, so that the variable has a longer lifetime than the method invocation.
So here’s the final version of the code:

public static void ForEach(ICollection<T> collection, Action<T> action) {
            ThreadPoolExecutor executor = new ThreadPoolExecutor();

            foreach (T element in collection) {
                T parameter = element;
                Action parameterlessAction = (() => parameterizedAction.Invoke(parameter));
                executor.AddTask(parameterlessAction);
            }

            executor.Finish();
   }

   executor.Finish();
}

Parallel For Loop in C#: Part 1

This is the first of the two posts that shows you how to build a parallel for loop in C#.

In this part we will start building a rudimentary ThreadPoolExecutor that will be the core of the parallel execution. It will have has 2 methods:

• AddTask(Action a) – it queues up a task to be executed one of the threads in the pool.
• Finish() – signals the executor to stop accepting any other tasks and wait till all tasks are completed.

The implementation is based on the BlockingQueue implemented in the previous post. It uses 10 worker threads that constanty get tasks from the queue and execute them. Since it is a blocking queue, the workers will block untill someone puts a task in the queue. The queue is thread safe, so every task will be processed only by one worker.

We will start by implementing the logic that queues up the tasks and the worker threads that execute the tasks, later we will thing about termination.

    public class ThreadPoolExecutor {
        private readonly BlockingQueue tasks = new BlockingQueue();
        private readonly Thread[] workers;

        public ThreadPoolExecutor() {
            workers = new Thread[10];
            for (int i = 0; i < workers.Length; i++) {
                workers[i] = new Thread(run);
                workers[i].Start();
            }
        }

        public void AddTask(Action task) {
            tasks.Enqueue(task);
        }

        private void run() {
             while (true) {
                 tasks.Get().Invoke();
             }
        }
    }

Now we need to add the termination condition. Let’s start by just not accepting new threads, and later we will think about waiting for the tasks to be processed. We will use a boolean that indicates whether the ThreadPoolExecutor is open or closed. If it is open, it can accept new tasks. Once the Finish() method gets called, the ThreadPoolExecutor becomes closed and doesn’t accept any new task.

    
public class ThreadPoolExecutor {
        private bool open = true; // open to accept new tasks
        private readonly BlockingQueue tasks = new BlockingQueue();
        private readonly Thread[] workers;

        ...

        public void AddTask(Action task) {
             if (open) {
                 tasks.Enqueue(task);
             } else {
                 throw new Exception("Queue is closed");
             }
        }

        public void Finish() {
             open = false;
        }

        private void run() {
             while (true) {
                 tasks.Get().Invoke();
             }
        }
    }

The problem with this implementation is that the Finish() method doesn’t wait for all tasks to be processed, but returns immediately. The tasks to be processed include the ones in the queue along with the ones being currently processed by the workers. We will introduce a counter to keep track of this number. The Finish() method will block until that counter reaches 0. For blocking we will use System.Threading.Monitor and we will synchronize on “this”. Moreover, once all the tasks have been processed, we’ll interrupt all the worker threads that are blocked on the queue.

using System;
using System.Collections.Generic;
using System.Threading;

namespace Concurrent {
    public class ThreadPoolExecutor {
        private bool open = true; // open to accept new tasks
        private readonly BlockingQueue tasks = new BlockingQueue();
        private readonly Thread[] workers;
        private int pendingTasks; // the number of tasks in the queue

        public ThreadPoolExecutor() {
            workers = new Thread[10];
            for (int i = 0; i < workers.Length; i++) {
                workers[i] = new Thread(run);
                workers[i].Start();
            }
        }

        public void AddTask(Action task) {
            lock (this) {
                if (open) {
                    tasks.Enqueue(task);
                    pendingTasks++;
                } else {
                    throw new Exception("Queue is closed");
                }
            }
        }

        public void Finish() {
            lock(this) {
                open = false;

                // wait till all tasks are finished
                while (pendingTasks > 0) {
                    Monitor.Wait(this);
                }

                // kill the workers waiting for more tasks
                foreach (Thread worker in workers) {
                    worker.Interrupt();
                }
            }
        }

        private void run() {
            try {
                while (true) {
                    lock (this) {
                        if (!open && pendingTasks == 0)
                            break; // if we're not open anymore and there are no tasks in queue, break the loop
                    }

                    // don't block other threads while processing the task
                    tasks.Get().Invoke();

                    lock (this) {
                        pendingTasks--;
                        Monitor.PulseAll(this); // notify waiting threads that the tasks are all processed
                    }
                }
            } catch(ThreadInterruptedException) {}
        }
    }
}

In order to parallelize your program, divide it in concurrently executable tasks and wrap every task in an Action object. For convenience you can also use closures. Add all the tasks to the ThreadPoolExecutor and wait for them to finish by calling the Finish() method.

In the next post we will be adding some syntactic sugar to implement a parallel for construct.

Time Tracking Tools

Have you ever asked yourself how much time during the day in the office do you spend looking at funny youtube videos, reading emails, taking coffee or doing some boring administrative task that keeps you from getting your work finished? I’ve actually been asking myself that for what it feels my entire life. I always tought that a well organized and productive 3 hours could be more valuable than a whole day of distractions. I always wanted to measure that productivity in detail and see what things I’m spending my time on and how much. Now I finally can.

A few months ago I found out on Lifehacker about this software called RescueTime that tracks how you spend your time on a computer. It’s free and you run it in the background. It categrorizes your activities in Communication, Development Tools, Reference/Search etc. If you are using a browser it is smart enough to distinguish which sites are you accessing, so reading The Server Side and Failblog.org are considered two different activities.

 

One downside of RescueTime is that it posts your usage statistics to their servers, so if you don’t want anyone to see how much time you spent… watching porn in the office, you might choose to disable RescueTime for a couple of hours. On the other side, your usage statistics are accessible only by you, so your boss can’t detract from your salary every 5 mins you spent checking your private mail.

Another downside is that it doesn’t show you when exactly did you start working with a particular program and when were you AFK. So you can’t distinguish between a meeting and a lunch break.

Both of these problems are solved by ManicTime. Manic time works only locally and gives you information on what did you do at an exact moment of the day: 

 

 

The only downside of ManicTime is that it is too fine grained so you don’t get the quick overview that you can get in RescueTime. Currently I’m using both of them until I decide which one is better or one of them implements the functionalities of the other.

Active and Passive Replication in Distributed Systems

In the distributed systems research area replication is mainly used to provide fault tolerance. The entity being replicated is a process. Two replication strategies have been used in distributed systems: Active and Passive replication.

In active replication each client request is processed by all the servers. Active Replication was first introduced by Leslie Lamport under the name state machine replication. This requires that the process hosted by the servers is deterministic. Deterministic means that, given the same initial state and a request sequence, all processes will produce the same response sequence and end up in the same final state. In order to make all the servers receive the same sequence of operations, an atomic broadcast protocol must be used. An atomic broadcast protocol guarantees that either all the servers receive a message or none, plus that they all receive messages in the same order. The big disadvantage for active replication is that in practice most of the real world servers are non‐deterministic. Still active replication is the preferable choice when dealing with real time systems that require quick response even under the presence of faults or with systems that must handle byzantine faults.  

In passive replication there is only one server (called primary) that processes client requests. After processing a request, the primary server updates the state on the other (backup) servers and sends back the response to the client. If the primary server fails, one of the backup servers takes its place. Passive replication may be used even for non‐deterministic processes. The disadvantage of passive replication compared to active is that in case of failure the response is delayed.

Webapp stacks comparison update 1

We have received measurements from one of the remaining level 3 applications. It’s Immo‘s implementation based on Ruby + Ramaze + MySQL. Here are the updated results:

As soon as we confirm the measurements and get the numbers for the ASP implementation we will publish the updated point chart.

Webapp stacks comparison

Ever wondered what is the best technology stack for building web applications? I’m sure you have.

Last week my company went on a workshop, during which we tried to answer that question. I wrote a requirements specification for a simple web application. Everyone had to choose the technology stack they’re most familiar with and implement the application. Everyone received a benchmark script for the application and at the end of the day we compared the performance results. The application was just enough complex to require at least a day to implement. In the end we multiplied the performance by the level of functionality implemented.

The Application

The webapp I chose is the same one for the couldspeed project. It is based on the model of social networking applicatins. Once registered and logged in, users can add other users as friends and submit posts. The homepage will display the 20 most recent posts from all user’s friends including the user himself.

There are 2 entities each with 2 attributes:

• users(email, password)
• post(date, content)

and there are 2 relationships

• users are friends with other users (n to n)
• each post is written by a user (1 to n)

there are 2 web pages: login and home.

From the login page, users can register themselves or log in.

The home page displays the number of friends, the 20 most recent posts (for each post, the date, author and content) and allows users to add posts, friends or logout.

Information has to be persisted somehow.

The Benchmark

Each developer got a copy of JMeter and 3 scripts. The 3 scripts excercized 3 different levels of functionality:

1. Register Users – registered a number of users (100)
2. Make Friends – created around 10 friends per user
3. Post Stuff – posted messages

For the first level of functionality, the developer had to implement the functionality behind the Register button. Registered users had to be persisted. This level had a multiplier of 1.

For the second level of functionality, developers had to implement logging in, keeping session information, and the friendship relationship. The homepage should have shown the number of friends. This level had a multiplier of 3.

For the third level of functionality, developers had to implement everything: posting messages and showing the messages from all friends. Since this functionality included a complex query that ate a lot of processing power, the multiplier was 50.

The Contenders

Ben: Erlang + CouchDB

Team 2: Java + Spring + Hibernate + Postgres

Team 3: Java + Spring + Hibernate

Team 4: Ruby On Rails + MySQL

Team 5: ASP with Visual Basic + SQLServer

Immo: Ruby + Ramaze + MySQL

The Results

Only three of the contenders implemented level 3 of functionality, but we were able to measure the performance only for the erlang implementation. The other 2 that made it to the 3rd level were ASP+SQLServer and Ramaze. We will soon publish the results of the two missing level 3 implementations. 

The winner was Ben with 1111.1 points. Erlang + CouchDB proved to be quite fast and productive in the right hands.

Conclusions

Allthough just one day of development is not nearly enough to measure productivity, we noticed that choosing a particular language that promised a high level of productivity wasn’t as important as choosing the language you’re most familiar with.

Alltough Level 1 of functionality does not provide a meaningful scenario to measure performance, we can see that most of the implementations had the same performance, including Ruby, which has been measured to be 100 times slower than C++, but in our scenario it actually showed the best performance.

Allthough we must point out that both ruby implementations and the ASP implementation showed instability. Errors ranging from 15% to 30% were reported during the benchmarks.

As a comparison, I have done some java implementations before the competition. They all provide level 3 functionality. They all use Servlets in the web tier, but the DAO tier changes: we have JDBC with MySQL, EJB3 with MySQL and pure in memory.

Compared to the Erlang implementation wich serves 15 req/s I have similar results for the JDBC (15 req/s). A “heavyweigth” stack such as EJBs actually manages to produce 38 req/s, but by far the fastest solution is keeping everything in memory that brings us to an impressive 2000 req/s. Obviously the in memory solution cannot be compared to the others because it doesn’t satisfy the persistence requirement. But can still be used as a comparison to see how much performance do we loose on the persistence layer.

Future Work

We have had requests from other people that were not taking part of the competition to submit their implementations. Since we have no way to measure productivity, all submissions now require level 3 of functionality. All implementations will be published on the cloudspeed website. If you wish to contribute by improving an implementation or submitting your own just send me an email or leave a comment here.

Currently the benchmark is adapted to quickly give a very aproximative measure. 100 users is not a realistic number even for a small website. Our next goal is to create a benchmark that will register up to millions of users, have an average of 100 friends per user and post several million messages.

The final goal is to port these implementations to the cloud and measure their scalability. We don’t only want to see the performance on a single machine, but also how will the performance be when we reach the limits of a single server. Ideally we want to try to run these applications on clusters as big as we can get.

Stay tuned for updates…