Web λ.0 - Functional programming for the Web

Gomemcache with multiget support

2011-11-02T10:05:00.003+01:00

It's my pleasure to announce that gomemcache already has six contributors that have supplied changes and fixes to the original code base. A recent patch by Arbo von Monkiewitsch adds GetMulti() function that allows fetching values for multiple keys with one function call.
As a side note, one thrid of patches, as well as a few of my commits, are purely compatibility fixes for subsequent Go releases. I think that at the moment frequent changes to the standard libraries and the language core are the main blocker preventing wide adoption of Go by the IT industry.

Human factor

2011-09-16T14:29:00.009+02:00

Having recently moved to a netbook, I realized again how important performance is for software development. I realized it even more when my Android phone became almost unusable after another software upgrade. As a kid I was a big fan of a computer demoscene where gifted coders showed to the world how to make the hardware do things unimaginable even by its creators (like a famous Commodore 64 FLI graphic mode). Now when the number of small devices connected to the Internet exceeds the number of computers and laptops wired to the global network, writing efficient software is a must: Facebook developes HipHop for PHP (written in C++), Google releases Native Development Kit for Android and makes Go the first compiled programming language available for the Google App Engine platform.

It is commonly argued that ANSI C is the "fastest programming language" that exists. No it's not. The language itself is neither slow nor fast, it's the implementations that are (compare Ruby and JRuby for example). However, it's true that software written in C can be usually compiled to the most efficient executable code (excluding pure assembly). No wonder that the most efficient pieces of software, like operating system kernels (Linux, BSD, Solaris, Windows, etc) or programming language VMs (Common Lisp, Python, PHP, Ruby, and even Java) are all written almost exclusively in C (not even C++).

Out of curiosity I started to look around for web software written in C and found a wonderful web server called G-Wan. It's very small and its performance looks really amazing as compared to other web servers - some enthusiastic reviews even call it The Future of the Internet and wonder why such a brilliant software is not popular. Well, G-Wan is not popular, because there is a problem. A big problem. And the name of the problem of G-Wan is Pierre Gauthier, its author. If you browse through the G-Wan's website and forum you can learn that he is a man with a really huge ego (he calls himself one of the best engineers available), who loves to criticize other people's work (like Poul-Henning Kamp's, the author of Varnish). But at the same time he does not want to publish his own source code nor make it open source, because he perceives other developers as inferior idiots, who would surely break it or at least bring nothing interesting to the existing code base. Moreover, evil government agents will try to introduce backdoors into his software and you are more secure when Pierre hides his code deep under his bed and tells you that you should trust him. And of course you do, don't you? And if you invest your time and money in G-Wan you don't have to worry at all about future development and maintenance, because even though the source code is closed, Pierre also gives you his word that he will not drop the software, and that he will never get hit by a bus (I'm not exaggerating, just read this post). I will not go deeper into his paranoia of his website being constantly attacked by Microsoft and NSA servers, because you already should have an idea about the way the guy thinks.

On the other pole there is a true pearl called Tiny C Compiler created by Fabrice Bellard. It's so insanely fast (it can compile the typical Linux kernel in less than 15 seconds!) that it can be used to write scripts or servlets in ANSI C (guess what is used internally by G-Wan to compile the servlets). With another open source project, libmicrohttpd, it can become a good alternative if you want to build a small, fast web server that can use ANSI C servlets (for example as an embedded router software). Libmicrohttpd is fully HTTP 1.0 and 1.1 compliant, and it offers several threading models, so you can tune your software and choose which one suites you best in your environment. If I was supposed to build a tiny embeddable web server, I would definitely choose open source libmicrohttpd + tcc + some personal coding over G-Wan.

Another one bites the dust

2011-09-02T21:41:00.007+02:00

A few days ago I found an interesting post on Ken Shirriff's blog, entitled Why your favourite language is unpopular. It summarizes a talk by Erik Meijer who provided a simple, yet very accurate, explanation why some programming languages gain popularity, while some other (often better in many aspects) don't. I thought about this formula in context of Reia, a very promising language for Erlang platform I mentioned about back in 2008 in my post Scripting Erlang. The author of Reia has just announced that he drops development of Reia in favour of Elixir. It seems that with the amount of software existing today there is very little space for another programming language, even if it addresses problems hard to solve with mainstream languages. With existing army of programmers at its disposal, the IT industry can deal with most of its problems using existing tools, without the need of inventing another language to rule them all. A good example of such philosophy is Cilk Plus, which originates from Cilk and allows to scale C/C++ code easily on multicore CPUs. With Cilk you can improve your existing software without rewriting it from scratch with a new computer language, which in the long run can create more problems than it actually solves.

Running Scala via Nailgun

2011-08-30T18:13:00.003+02:00

Recently a friend of mine got me interested in Scala, a modern programming language for JVM. Scala reached a wide audience in 2009 when Twitter announced that they use Scala in the most critical elements of their backend. It became popular for its efficiency and scalability, and for joining in a very pragmatic manner the concepts of functional and object oriented programming. It also implements some very powerful constructs, like foldLeft, which allows you to compose your own reduction methods operating on lists (see this page for some very interesting examples).
I decided to give it a try on my Acer Aspire One netbook, which I use often to do some daily tasks. Unfortunately, with 1.6 GHz Intel Atom and 1GB RAM running Fedora 14 it took Scala REPL almost 20 seconds to start. I was wondering if I could make it faster and found out that some people recommended Nailgun for this task. In short, Nailgun preloads the whole JVM into the memory and than uses its own bootstrap loader to connect your programs to it, so that they load much faster, without JVM startup overhead. However, besides some good advice I couldn't find any working example how to do it, so I decided to do it myself. Fortunately it turned out to be a quite easy task. First, I copied nailgun-0.7.1.jar to Scala's lib directory, then I took the original bin/scala script and created a modified version. I changed line 161 from

scala.tools.nsc.MainGenericRunner "$@"

com.martiansoftware.nailgun.NGServer "$@"

and line 113 from

CPSELECT="-Xbootclasspath/a:"

CPSELECT="-cp "

The last change was necessary for Nailgun to load properly. Then I started regular Scala REPL through

ng scala.tools.nsc.MainGenericRunner

just to learn that it still takes 20 seconds to start. Conclusion? Modern JVM loading overhead is so small that reducing it further makes little sense, even on slow machines.
Lessons learned:
1) Using Nailgun to speed up Scala won't get you anywhere.
2) Don't listen to forum "experts" who recommend solutions which they have obviously never tried in practice.

Need for speed

2011-03-26T21:53:00.009+01:00

Working as a web developer maintaining a big web service can quickly make you understand that "everything counts in large amounts", and identifying and eliminating bottlenecks eventually becomes part of your daily routine. There are many ways to optimize your web application: from migrating to faster hardware platform, through reducing the number of network requests and extensive use of various caching layers, to refactoring of the code and optimizing your algorithms. Some very interesting performance tips can be found at Yahoo Developer Network - but sometimes it's just not enough, and you have to reach deep into the core of your software engine.

One way is to rewrite your application using either Java or C/C++. Another way, especially when your code base is so huge that it does not pay to rewrite it (even partially) is to try to compile the scripts to machine code. The best known engines implementing this technique are PyPy for Python, developed as a followup to the Psyco project, and HipHop for PHP, developed at Facebook. What is especially interesting about the HipHop story is that it has been announced shortly after Koen Deforche stated on his blog, that Facebook could reduce the power consumption in their data centers by 75% only by using C++ instead of PHP. What is not surprising, Koen Deforche is an author of Wt, a C++ toolkit designed for building web applications.

What makes Wt stand out among its alternatives is that it completely masks all underlying web technologies and makes Wt development look more like Qt than web. However, developing regular web services with Wt is not easy. For a last few days I tried to create a fairly simple application with Wt and I simply gave up. For me it was just like playing with Lego Technic for Aliens. Maybe it's because Wt, as its author admits, is not a toolkit for porting an existing website to C++, but a toolkit for porting an existing desktop application to the web, and I'm primarily a web developer. Or maybe it's because there is too little useful real life examples out there and the community seems to be almost non existing. In my opinion Wt is rather a niche product, best suited for developing highly scalable intranet applications for big companies.

At the opposite pole there is KLone, a lightweight web framework that at first glance looks like JSP. KLone allows creating dynamic content by embedding C++ code into HTML, much like JSP does with Java. It also provides all necessary mechanisms to deal with sessions, requests, etc. The application is of course compiled to native code and can distributed as a standalone executable, since it includes its own embedded http server. At the moment it's definitely my choice if you want to write a web service based on C++, no matter if it's because your hardware is too poor for Java or you just don't want to hog your system resources with Tomcat.

More fun with Io

2010-11-11T20:41:00.003+01:00

One of Io's distinguishing features is an ability to extend its own syntax. Suppose that for some reason (for example to improve the readability of your code) you need unless keyword, similar to the one used in Ruby. You can define it as follows:


Object unless := method(if(call evalArgAt(0) not, call evalArgAt(1), call evalArgAt(2)))

That's it. You can now use a new keyword in your scripts:


Io> x := 15; unless(x < 10, "passed", "failed")
==> passed
Io> x := 5; unless(x < 10, "passed", "failed")
==> failed

In Common Lisp a similar effect can be achieved by using a macro like this:


(defmacro unless (condition &rest body) `(if (not ,condition) ,@body))

but in contrast to Common Lisp, Io does not use separate constructs to extend the language - what you can do in Lisp using macros, you can do in Io using only its own introspective features.

Language of the year 2011

2010-11-06T23:27:00.004+01:00

Probably the biggest programming language hit of the last year was Go - it was also (according to Tiobe) the fastest growing language in 2009. Year 2008 belonged to Erlang: Amazon started their SimpleDB based on Erlang, and Facebook announced their Erlang powered chat application.
For some time I was wondering if the incoming year can bring another player entering the game, and I came to a conclusion that a good candidate is Io. It's a prototype-based programming language, which is amazing in many aspects: it combines very simple grammar with incredible power, provides an interactive shell and a rich set of libraries out of the box, it also allows hundreds of thousands of concurrent processes through actor based model. Io is surprisingly mature as for a language with so few Internet resources and is definitely worth trying - it has been recommended even by some renowned hackers like _why and Ruby's creator Matsumoto Yukihiro. You can find a few Io example routines here.
Give Io a try if you have a minute, I can guarantee that you won't be sorry.

Scale up your skills, not the hardware

2010-10-30T09:17:00.009+02:00

It is not a big secret that good programmers keep their saws sharp all the time. If you want to improve your mental skills a good place to start is Project Euler. I found it while browsing other programmers' blogs and immediately got hooked up. Project Euler is a place where you can challenge yourself (and others) in solving various mathematical and computer programming problems. The collection of problems is constantly growing and you can find them ranging from very easy to really difficult. When you provide the correct solution to a problem, a forum dedicated to it becomes revealed and you can see how other people managed to solve it. Sometimes you can also get a bonus in a form of paper explaining the problem and the best known solutions in details. You can learn a lot from these forums since people share there both their ideas and source code written in different programming languages; some of them don't even use a computer, all they need to find a solution is paper and pencil.
What I particularly like about Project Euler is that most of the problems cannot be solved by brute force. They can make you check hundreds or thousands of possible combinations, but still require a more clever approach. A classic example are problems 18 and 67, where you need to find a path from the top of the number pyramid to the bottom, so that the total sum of numbers on the path is the largest. While the pyramid in problem 18 is rather small and you can find the solution by trying every of 16384 possible paths, it is impossible to solve problem 67 the same way. To solve it you need to turn the problem upside down - literally, since you can easily get the correct solution if you start searching for the best path from the bottom of the pyramid to the top, reducing the number of combinations with every step.

You may wonder how mathematics can help you in facing every day challenges as a programmer. Imagine you work for an on-line store with millions of CD records on stock, and you provide a browser with a dynamic list of products based on different criteria, such as genre, year and price. Now you want to show to your customers the most popular product within the range they choose. Getting all items satisfying the selected criteria from a database and finding the most popular one every time someone browses the list will quickly kill your back-end. On the other hand, it is impossible to generate such data in advance for every possible combination of search parameters. You can either expand your server farm (and possibly move to the cloud to reduce costs) or you can use some statistical tools to help you do the job. The trick is to find a representative sample size for a given population of products. Assuming that N is a total population, z is a statistical factor for desired confidence level, p is an estimated proportion of a given variable within the population, and d is admissible error level, we can get sample size n with the following formula:


x = z^2 * (p * (1 - p))
n = N * x / ((N - 1) * d^2 + x)

The z factor is constant and equals 1.96 for the 95% confidence level and 2.58 for the 99% confidence level. Assuming that a selected range of CD records contains one million uniformly distributed products and you can tolerate a 5% error, it turns out that in 95% cases you get the most popular one correctly by analysing only 385 randomly chosen items from the list, since:


x = 1.96^2 * (0.5 * (1 - 0.5)) = 0.9604
n = 1000000 * 0.9604 / ((1000000 - 1) * 0.05^2 + 0.9604) =~ 384.013

To be 99% sure that no more than 1% results are incorrect, you'd need to analyse 16369 records.
You can learn more about calculating sample sizes from this article at Quirks - I took the above formula from it. And remember: while it's true that machine cycles are cheap and people cycles are not, never forget that people cycles are worth billions of machine ones.

MapReduce with Gambit Scheme & Termite

2010-07-31T22:29:00.008+02:00

Termite is a library that runs on top of Gambit Scheme and implements concurrency model inspired by Erlang (there is also a Chicken Scheme port, but it's so far incomplete). Since I have already posted about Termite some time ago, I will not go into details how to write distributed applications with it. Instead, I want to show you how to use Termite to implement a simple MapReduce algorithm.

A trivial implementation uses a simple worker process that executes some code, and a pmap function which spawns multiple workers and collects the results:


(define (worker)
  (let* ((msg (?)) (pid (car msg)) (fun (cadr msg)) (arg (caddr msg)))
    (! pid (fun arg))))

(define (pmap fun lst)
  ; spawn workers
  (for-each 
    (lambda (x) (let ((p (spawn worker))) (! p (list (self) fun x))))
    lst)
  ; collect results
  (let loop ((i (length lst)) (result '()))
    (if (= 0 i) (reverse result) (loop (- i 1) (cons (?) result)))))

So far it works similar to its Erlang equivalent. However, this version does not guarantee (just like the Erlang one) that you get the results in the same order as the arguments passed to pmap. Let's consider function f, which holds execution of the current thread for a given number of seconds:


(define (f x) (thread-sleep! x) x)

If you run the following code:


(pmap f (list 1 2 3 2 1))

The result will be:


(1 1 2 2 3)

Since the first results on the list will come from the processes that finished first.

A solution to this problem is to make a single worker process using a sequencer to mark spawned threads. Numbers generated by the sequencer are then used to sort the results to achieve the correct order of the result list:


(define (worker)
  ; init sequencer
  (let loop ((n 0))
    (let ((msg (?)))
      ; terminate worker on request
      (if (not (eqv? 'exit (car msg)))
        (let ((pid (car msg)) (fun (cadr msg)) (arg (caddr msg)))
          ; start a new thread
          (spawn (lambda () (! pid (cons n (fun arg)))))
          ; increase sequencer
          (loop (+ n 1)))))))

(define (pmap fun args)
  ; start worker
  (let ((p (spawn worker)) (result '()))
    ; send data to the worker
    (for-each (lambda (x) (! p (list (self) fun x))) args)
    ; collect results
    (let loop ((i (length args)) (lst '()))
      (if (= 0 i)
        (set! result lst)
        (loop (- i 1) (cons (?) lst))))
    ; terminate worker
    (! p (list 'exit))
    ; sort results
    (let loop ((in (qsort result <)) (out '()))
      (if (null? in)
        out
        (loop (cdr in) (cons (cdar in) out))))))

You can use any function you wish to sort the results. I used a modified version of quicksort found at Rosetta Code:


(define (qsort l gt?)
  (let q ((l l))
    (if (null? l)
      l
      (let ((s (split-by (cdr l) (lambda (x) (gt? (car x) (caar l))))))
        (append (q (car s)) (list (car l)) (q (cdr s)))))))

(define (split-by l p)
  (let loop ((low (list)) (high (list)) (l l))
    (if (null? l)
     (cons low high)
     (if (p (car l))
       (loop low (cons (car l) high) (cdr l))
       (loop (cons (car l) low) high (cdr l))))))

Now when you run the test again, you get the result list in the same order as the argument list, no matter what the execution time of single processes was:


(pmap f (list 1 2 3 2 1))

(1 2 3 2 1)

Using trampolines in C

2010-07-19T20:09:00.008+02:00

In my previous post I presented my implementation of trampoline code in newLISP. Since this technique is also used in non-functional programming languages, I prepared an example in C.
Let's assume we have two mutually recursive functions f1 and f2:


#include <stdio.h>

void f1(int n);
void f2(int n);

void f1(int n) {
  printf("%d\n", n);
  if (n == 0)
    printf("Blastoff!\n");
  else
    f2(n);
}

void f2(int n) {
  f1(n-1);
}

int main() {
  f1(1000000);
}

When you compile this code without any optimizations provided by a compiler and try to run it you will most probably quickly get a segmentation fault (or similar error, depending on your platform). What happens here is the application running out of stack for storing function callbacks.

In Lisp you can solve this problem by rewriting functions to return continuations instead of values. In C you can simulate continuations by the following means:
1. Making functions to operate on pointers to variables instead of actual variables, which allows the application to preserve their values between function calls.
2. Returning a pointer to the next function to be called instead of calling it directly, which makes the use of application stack unnecessary.

So rewritten f1 and f2 can be presented in the following form:


#include <stdio.h>

typedef void *(*Fun)(int *n);

void *f1(int *n);
void *f2(int *n);

void *f1(int *n) {
  printf("%d\n", *n);
  if (*n == 0) {
    printf("Blastoff!\n");
    return NULL;
  } else {
    return f2;
  }
}

void *f2(int *n) {
  *n = *n - 1;
  return f1;
}

int main() {
  int n = 1000000;
  Fun f = f1;
  while (f != NULL) {
    f = (Fun)f(&n);
  }
  return n;
}

Now the main function iteratively goes through subsequent function calls until the halting condition (NULL) is met. At the end of iteration variable n holds 0.

As a side note, gcc is able to optimize the code of mutually recursive functions quite effectively. If you compile the first example with gcc -O2 the resulting code will not crash, because the compiler replaces all call instructions with jmp.

P.S. I would like to thank Johnny, my colleague and true programming expert, who inspired me to write this post. I was also inspired by Carlos Oliveira's post on trampolines.

Advanced recursion in newLISP

2010-07-15T21:43:00.018+02:00

In my recent post about newLISP I mentioned that it does not support tail call optimization. In fact, many Lisps don't. As Bill Six pointed out even the ANSI standard of Common Lisp standard does not mandate (unlike Scheme) tail-call elimination provided by the language implementation, although it seems that all well-known ANSI Common Lisp compilers do it anyway.

I was wondering if there is a way to circumvent this problem and the first solution I found was to use memoize macro described in an excellent online documentation for newLISP, Code Patterns in newLISP:


(define-macro (memoize mem-func func)
  (set (sym mem-func mem-func)
    (letex (f func  c mem-func)
      (lambda ()
        (or (context c (string (args)))
        (context c (string (args)) (apply f (args))))))))

You can apply this macro to any function with any number of arguments. The trick here is that each time a function is called its result is cached in memory for another call. It can speed up your application tremendously, which can be observed by comparing the execution time of these example Fibonacci functions:


(define (fibo n)
  (if (< n 2) 1
    (+ (fibo (- n 1)) (fibo (- n 2)))))

(memoize fibo-m
  (lambda (n)
    (if (< n 2) 1
      (+ (fibo-m (- n 1)) (fibo-m (- n 2))))))

(time (fibo 35))
(time (fibo-m 35))

On my laptop (fibo 35) took 12,98 seconds to execute, while (fibo-m) executed in 0,016 miliseconds.

Unfortunately the memoize macro cannot help you to handle mutual recursion. A classic example of such recursion looks as follows:


(define (f1 n)
  (println n)
    (if (= n 0)
      (println "Blastoff!")
      (f2 n)))

(define (f2 n)
  (f1 (- n 1)))

You can easily make newLISP run out of stack by running (f1 1000), not to mention bigger numbers. What happens if we define a "memoized" version of f1 and f2? Let's see:


(memoize f1
  (lambda (n)
    (println n)
    (if (= n 0)
      (println "Blastoff!")
      (f2 n))))

(memoize f2
  (lambda (n)
    (f1 (- n 1))))

Again, running (f1 1000) immediately exhausts newLISP's stack.

A solution to this problem is using a technique called trampolining. Bill Clementson on his blog not only explained in an excellent way the concept of using trampolines, but also provided a Common Lisp implementation, which became my inspiration to write a newLISP version:


(define (trampoline fun arg)
  (catch
    (while true
      (let ((run (apply fun arg)))
        (setf fun (first run) arg (rest run)))) 'result)
  result)

A trampoline iteratively executes code thunks returned by a function, and this way avoids blowing out application stack. However, in order to use trampoline, the function must return continuation (a pointer to the next step) instead of value. Below is a version of beforementioned functions modified to use the trampoline:


(define (f1 n)
  (println n)
  (if (= n 0)
    (throw "Blastoff!")
    (list f2 n)))

(define (f2 n)
  (list f1 (- n 1)))

Now you can test it with:


(trampoline f1 '(1000))
(trampoline f1 '(10000))
(trampoline f1 '(100000))
...

Have fun!

newLISP - Lisp for the masses

2010-06-03T18:03:00.007+02:00

There is a popular phrase among Lisp hackers: Plant a tree, write a book, create your own dialect of lisp. Although there aren't many popular Lisps out there and even the mainstream Common Lisp has never been massively used, it seems that just like in case of various Linux distributions, often more means simply better. A good example of such success story is Clojure, and here comes another candidate to take the lead.
newLISP is a modern dialect of Lisp, designed by Lutz Mueller to be (as he says himself) "quick to learn and to get the job done". I must say that this sentence couldn't be more true - solving Euler Problem 10 (finding the sum of all primes below 2 million) after just two days of fiddling with newLISP took me less than 3 minutes, including designing, writing, testing and executing the following code:

(println (apply + (filter (fn (n) (= 1 (length (factor n)))) (sequence 2 2000000))))

In spite of being an interpreted language, programs created with newLISP run amazingly fast. The code above is a purely brute force solution, yet it executes in less than 10 seconds on Core 2 Duo 1.66GHz.
However, simplicity comes for a price. If you try to use a more sophisticated approach, like classic sieve of Eratosthenes, you might get a bit surprised:


(define (sieve seq out)
  (let ((n (first seq)))
    (setf seq (filter (fn (x) (!= 0 (mod x n))) seq))
    (push n out)
    (if (not seq) out (sieve seq out))))
(print (apply + (sieve (sequence 2 2000000))))

In this code function sieve, although properly tail recursive, will make newLISP to quickly run out of stack or (if you provide enough space for the stack) of all available memory. It's because newLISP does no tail recursion optimization. If for some reason you cannot live with it, you can still use Common Lisp for implementing such recursions:


(defun range (min max) (loop for i from min to max collect i))
(defun sieve (seq &optional out)
  (let ((n (car seq)))
    (setf seq (delete-if #'(lambda (x) (= 0 (mod x n))) seq))
    (push n out)
    (if (not seq) out (sieve seq out))))
(print (apply #'+ (sieve (range 2 2000000))))

As you can see, the code of function sieve is very similar, so it's fairly easy to switch to newLISP if you already have some Common Lisp background. Differences to other Lisp dialects are well documented, as well as the language itself. Documentation is another strength of newLISP: you can learn how to solve different real life problems using newLISP code patterns or browse through many interesting code snippets.
What I personally like about newLISP in comparison to other Lisps is its really tiny footprint. You can create a standalone executable containing an embedded newLISP engine which is 200kB small, using two simple steps:

(load "/usr/share/newlisp/util/link.lsp")
(link "/usr/bin/newlisp" "mycode.bin" "mycode.lsp")

Despite being so small, newLISP provides a surprising amount of functionalities out of the box: regular expressions, TCP/IP networking (including FTP and HTTP protocols), database access (through external libraries), OpenGL, XML and XML-RPC handling, matrices, statistics (including Bayesian formulas), unicode support and a set of C/C++ modules that extend its abilities even more.
newLISP also supports parallel processing through Cilk-like API, and distributed computing through a built-in function net-eval.
newLISP is definitely not a New Common Lisp, and in some points (such as the beforementioned tail recursion) is still inferior. But newLISP is a perfect example that in the IT industry sometimes worse is better.

Web Sockets: a new era for the Web

2010-01-05T01:05:00.011+01:00

The Web Sockets API is a part of HTML 5 specification and is to the Web what TCP is to the IP protocol. It allows full-duplex, bidirectional communication between the server and the client browser - no more polling, no more busy waiting, and no more problems with keep-alive HTTP connections. Web Sockets allow to leverage Web applications to an absolutely new level, where they can finally operate like any other network software, without crippled overlays like AJAX or Comet. With Web Sockets you can push data to the client just as you would do it with XMPP.
One of the first browsers to support Web Sockets is Google Chrome. And, of course, one of the first languages natively supporting Web Sockets is Go. Here is a simple server application which sends time information to the browser in one second intervals:


package main

import (
  "http"
  "io"
  "strconv"
  "time"
  "websocket"
)

func ClockServer(ws *websocket.Conn) {
  ch := time.Tick(100000000)
  t1 := <- ch
  t := t1 / 1000000000
  for {
    t2 := <-ch
    td := (t2 - t1) / 1000000000
    if td != t {
      io.WriteString(ws, strconv.Itoa64(td))
      t = td
    }
  }
}

func main() {
  http.Handle("/clock", websocket.Handler(ClockServer))
  err := http.ListenAndServe(":12345", nil)
  if err != nil {
    panic("Error: ", err.String())
  }
}

When you compile and start the server, create a web page with the following content and save it to your disk:


<html>
<head>
<title>WebSocket</title>
<script type="text/javascript">
function init() {
  var tick = document.getElementById("tick");
  if ("WebSocket" in window) {
    var ws = new WebSocket("ws://localhost:12345/clock");
    ws.onmessage = function (evt) {
      tick.innerHTML = evt.data;
    };
  } else {
    tick.innerHTML = "The browser doesn't support WebSocket.";
  }
}
</script>
</head>
<body onload="init()">
<span>Seconds elapsed: </span><span id="tick">0</span>
</body>
</html>

If you open the page in Google Chrome, you will see seconds ticking. There is no AJAX, no long-polling or any other fancy stuff - the server pushes data directly to the client. If you open more Chrome instances, you will see that each of them has its own connection with the server with its own clock (however, beware opening many connections in the same window, but in different tabs - this can occasionally crash your browser).
You can also use Erlang to make use of Web Sockets technology. Joe Armstrong has recently posted an article on his blog with full source code of both Web Sockets client and server.
Have fun!

Go memcache client package

2009-12-30T22:06:00.010+01:00

Recently I needed to access Memcached from Go. I couldn't find a suitable package anywhere on the web, so I created one. Gomemcache provides basic operations to store, retrieve and delete data using memcache text protocol. You can download the package from its Github repository.

Edit: Gomemcache is now distributed under the terms of LGPL license with static linking exception. It means that you can link it statically with independent modules to produce an executable, regardless of the license terms of these independent modules, and to copy and distribute the resulting executable under terms of your choice, provided that you meet the terms and conditions of LGPL for the package itself. Originally GNU Lesser General Public License does not allow unproblematic static linking with proprietary source code.

Go Programming Language Resources

2009-12-27T14:21:00.002+01:00

Go is a fairly new programming language, so at the moment it is hard to find interesting projects associated with it. Go Programming Language Resources is a web site that tries to gather them in one place. It also contains links to mailing lists, discussion groups and IRC archives, as well as Go ports to different operating systems. You can also find there a few interesting development tools and syntax highlighting for the most popular programmer's editors. If you are interested in Go, this site is definitely worth adding to your bookmarks.

Go - a new programming language from Google

2009-12-24T00:46:00.015+01:00

Go is a new programming language developed at Google, which according to its FAQ "was born out of frustration with existing languages and environments for systems programming". Some people ask if the world needs another programming language, but those who know that among Go authors are Ken Thompson and Rob Pike, famous Unix hackers, usually don't. If there is a language that has a chance to replace plain C in system programming, Go is a perfect candidate. It features a syntax derived from the C tree (which makes learning curve fairly easy for most of the programmers), fast compilation to native machine code, and fast execution of compiled binaries. Additionally, Go provides a built-in garbage collector and language constructs that simplify parallel programming, especially the concept of goroutines, which are regular program functions executed concurrently. Goroutines can communicate with each other and the main thread through channels, that can also be used for synchronization purposes.
I have prepared a few simple programs to compare Go with C in terms of speed and to play with concurrent programming in Go. First, let's have a look at a typical recursive Fibonacci example. Below is a C version:


#include <stdio.h>
#include <stdlib.h>

int fib(int n) {
  if (n < 2) {
    return(n);
  }
  return(fib(n-2) + fib(n-1));
}

int main(int argc, char *argv[]) {
  int n = atoi(argv[1]);
  printf("%d\n", fib(n));
  return(0);
}

and here is a Go version:


package main

import (
  "flag"
  "fmt"
)

var f = flag.Int("f", 1, "Fibonacci number")

func fib(n int) int {
  if n < 2 {
    return n
  }
  return fib(n-2) + fib(n-1)
}

func main() {
  flag.Parse()
  fmt.Println(fib(*f))
}

A quick test shows that a single threaded Go program is actually faster than the C one:


$ gcc -O2 -o fib fib.c
$ time ./fib 40
102334155

real 0m1.987s
user 0m1.980s
sys 0m0.004s

$ 8g fib.go; 8l fib.8
$ time ./8.out -f=40
102334155

real 0m1.934s
user 0m1.932s
sys 0m0.004s

I also prepared a program in Go to calculate a sum of subsequent Fibonacci sequences up to a given number in parallel. It uses run function as a goroutine to calculate each sequence independently and a shared channel ch to gather the results, that are finally summed up (so we don't care about the order in which they appear in the channel):


package main

import (
  "flag"
  "fmt"
  "runtime"
)

var n = flag.Int("n", 1, "Number of CPUs to use")
var f = flag.Int("f", 1, "Fibonacci number")

func fib(n int) int {
  if n < 2 {
    return n
  }
  return fib(n-2) + fib(n-1)
}

func run(n int, ch chan int) {
  ch <- fib(n)
}

func main() {
  flag.Parse()
  runtime.GOMAXPROCS(*n)
  ch := make(chan int)
  for i := 0; i <= *f; i++ {
    go run(i, ch)
  }
  sum := 0
  for i := 0; i <= *f; i++ {
    sum += <-ch
  }
  fmt.Println(sum)
}

The program takes additional parameter -n to indicate the number of CPUs to use. According to Go runtime package documentation the call to GOMAXPROCS is temporary and will go away when the scheduler improves. Until then you have to remember to use this call, otherwise your application will use only one CPU by default.
I ran the program for 40 Fibonacci sequences on dual Intel Xeon L5420 2.50GHz using from single up to all available CPU cores. The execution time improved most dramatically between -n=1 (5.073s) and -n=2 (3.141s), than it gradually slowed down from -n=3 (2.574s) to -n=8 (2.013s).

What I like about Go is that it gives a set of powerful tools into programmer's hands, but at the same time does not try to hide the complexity of parallel programming behind bloated libraries or awkward language constructs. It nicely follows the KISS principle and borrows some good ideas from Unix design (like channels, which work similar to Unix pipelines). If you think seriously about future system programming, I think Go is definitely a language worth learning. Not only because it's Google ;-)

Funding Clojure 2010

2009-12-15T21:36:00.004+01:00

There is no such thing as a free lunch - everybody knows that. But when it comes to software, we tend to think that it is (or should be) free. Free as in free beer, not as in speech, quite contrary to what free software philosophy says. But software is not grown like crops in the field, it requires long hours of work from people who create it. Many people write software and release it under one of open source licenses in hope that some day it becomes popular; but when it finally does, it turns out that its development takes so much time that you either have to drop it or start working on it full-time.
This is what recently happened to Clojure. Rich Hickey, the creator and main developer of this fascinating programming language announced his financial expectations towards individuals and businesses who benefit from it to fund its further development. I hope Rich gets enough financial funding to continue his work on Clojure. If you use Clojure in your development, maybe you should also think about donating.

MagLev public alpha

2009-11-22T23:33:00.006+01:00

Gemstone has just announced an alpha version of their concurrent Ruby engine, MagLev, available for download. MagLev is based on Gemstone's Smalltalk virtual machine and supports 64-bit Linux, Mac OS X and Solaris x86 operating systems. There are no plans for 32-bit version of MagLev.
MagLev does not support Rails yet, but so does not Fabio Kung's JMagLev. However, the advantage of MagLev over Fabio's machine is that Gemstone is determined to create an enterprise-class product, and JMagLev was just a demonstration of the power of Terracotta and does not seem to be developed any further. It seems that the next step for Gemstone will be to implement Rails functionality and allow RoR applications to run in a clustered enviornment, just as Grails ones can run on Terracotta.

Erlang project crawler

2009-11-20T22:26:00.004+01:00

Today I received an email from Erlang Training and Consulting Ltd. - the owner of popular Erlang Community Site Trapexit - announcing its own Erlang open source project crawler. Crawler gathers information on open source Erlang projects from a number of code repositories such as GitHub, Bitbucket, SourceForge and Google Code. At the time when I am writing this post it includes information on 1228 projects. The number may not be impressive, but it is good to have information about the most interesting open source Erlang projects gathered in one place.

Top gear(man)

2009-09-06T14:29:00.009+02:00

Gearman is an open source project providing a flexible and universal framework for writing distributed applications. It differs from similar projects in easiness of use and the number of bindings for programming languages it provides: C, C++, Java, Perl, PHP and Python. In fact, Gearman has a simple command line client, that allows you to start jobs using any language you want - all you need to do is to provide the client with input data and then fetch the client's output. Gearman API is very simple, consistent, and makes writing distributed applications really easy, quick and fun.

Gearman architecture is equally simple: it consists of job servers, that accept task requests from clients and forward them to workers, and send results back to clients. Each worker can be connected to many job servers, and a client can choose which job server to use - this way there is no single point of failure that could break down the whole cluster. Job servers have their own queues and in case of worker failure they can reassign tasks to other workers. According to High Scalability Gearman has been successfully used by LiveJournal, Yahoo!, and Digg (which claims to run 300000 jobs a day through Gearman without any issues).

I decided to try out Gearman at home, and I must say that it was a really pleasant experience. I wrote a simple C++ worker and even simpler Python client. The worker recursively finds Fibonacci number for given n:


#include <cstring>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <libgearman/gearman.h>
#include <libgearman/worker.h>

using namespace std;

void *fib_worker(gearman_job_st *job, void *cb_arg, size_t *result_size, gearman_return_t *ret_ptr);
long fib(long n);
static void usage(char *name);

int main(int argc, char *argv[])
{
  int c;
  char *host = "127.0.0.1";
  in_port_t port = 0;
  gearman_worker_st worker;

  while ((c = getopt(argc, argv, "h:p:")) != -1) {
    switch(c) {
      case 'h':
        host = optarg;
        break;
      case 'p':
        port = (in_port_t) atoi(optarg);
        break;
      default:
        usage(argv[0]);
        exit(1);
    }
  }

  if (argc != optind) {
    usage(argv[0]);
    exit(1);
  }

  gearman_worker_create(&worker);
  gearman_worker_add_server(&worker, host, port);
  gearman_worker_add_function(&worker, "fib", 10, fib_worker, NULL);
  while (1) {
    gearman_worker_work(&worker);
  }

  return 0;
}

void *fib_worker(gearman_job_st *job, void *cb_arg, size_t *result_size, gearman_return_t *ret_ptr) {
  char ch[256];
  ostringstream os;
  int size = gearman_job_workload_size(job);
  strncpy(ch, (char *) gearman_job_workload(job), size);
  ch[size] = 0;
  long n = atol(ch);
  os << fib(n);
  string s = os.str();
  *result_size = s.size();
  *ret_ptr = GEARMAN_SUCCESS;
  return strdup(s.c_str());
}

long fib(long n) {
  if (n < 2) {
    return 1;
  } else {
    return fib(n - 2) + fib(n - 1);
  }
}

static void usage(char *name) {
  cout << "Usage: " << name << " [-h <host>] [-p <port>] <string>" << endl;
  cout << "\t-h <host> - job server host" << endl;
  cout << "\t-p <port> - job server port" << endl;
}

Python client prepares a set of jobs for a sequence of n numbers, runs them simultaneously through a job server and sums up the result:


import optparse
from gearman import *

parser = optparse.OptionParser()
parser.add_option('--host', help = "Specifies gearman job server")
parser.add_option('-n', '--num', help = "Amount of Fibonacci numbers to compute")
(opts, args) = parser.parse_args()

client = GearmanClient([opts.host])

ts = Taskset()
for i in range(1, int(opts.num)):
  t = Task(func = "fib", arg = i)
  ts.add(t)

client.do_taskset(ts)

sum = 0
for task in ts.values():
  sum += int(task.result)

print sum

You can download the source code of both worker and client here. After you compile and install Gearman with traditional:

./configure
make
sudo make install
sudo ldconfig

Install Python extension with:

easy_install gearman

And compile the C++ example with:

make

Then you can run a job server as a daemon:

gearmand -d -L 127.0.0.1

or in debug mode:

gearmand -vv -L 127.0.0.1

Next, run a couple of Gearman workers:

./GearmanWorker -h 127.0.0.1

And the Python client:

python GearmanClient.py --host 127.0.0.1 -n 45

For a single machine, it makes sense to run at most as many workers as there are CPUs (or CPU cores) available. For a network cluster, you can run more job servers and workers (and clients) respectively.

I've made some tests with the client and worker above. using my home laptop and an Intel Atom based net-top running together in a local network. For only one laptop worker, computing the sum of 45 Fibonacci numbers took 66.955 seconds, for two laptop workers it took 35.702 seconds, and adding a remote worker reduced the total time to 25.593 seconds. Adding more workers didn't reduce computation time, it even slightly slowed the cluster down - which is quite understandable, as the number of workers exceeded the number of free CPUs (Intel Atom in fact has only one physical core, although applications see it as dual-core CPU).

Jabase: Jabber cluster on HBase

2009-07-05T20:53:00.009+02:00

Java has often been compared with Erlang by Erlang advocates, who emphasize its advantage over Java in thread creating and message passing. Some even claim that Erlang can be Java successor in concurrent programming. Of course such comparisons and benchmarks have some value, but the truth is that Erlang has never been, and never will be, Java competitor. The reason for this is simple, and was perfectly explained by Dennis Byrne in his article "Integrating Java and Erlang":

Java and Erlang are not mutually exclusive, they complement each other. I personally have learned to embrace both because very few complex business problems can be modeled exclusively from an object oriented or functional paradigm.

Integration and interoperability are now the key words that make modern IT business go round. It is also understood very well by the Erlang team, who created Jinterface - a set of Java classes for communicating with Erlang.

Jinterface is also the key element that allowed me to build a highly scalable Jabber cluster based on ejabberd as XMPP server and HBase distributed database as a storage. Ejabberd is a distributed Jabber server written in Erlang, but unfortunately Erlang native storage, Mnesia, can't handle large amount of data. To overcome this limitation, ejabberd provides ODBC drivers for MySQL, MS SQL and PostgreSQL, but it's only a partial solution to the scalability problem. First, the whole ejabberd cluster still uses a single database instance as data storage, and second, user sessions are still kept in Mnesia.

Jabase is a middleware set of components written in Erlang and Java providing communication layer between ejabberd XMPP server and HBase distributed database. While ejabberd ensures communication between users and server instances, HBase provides highly scalable, distributed database to store large amount of data and serve them efficiently. Additionally, Java instances are responsible for caching user sessions and providing efficient methods of serving and searching for session data, while Erlang code ensures session data integrity among Jabber server instances. Jabase architecture looks like this:

The source code of Jabase has been released under GPL and the project website contains a manual how to compile and set up a simple Jabber cluster based on Jabase. However, technical support is served exclusively by Division-by-Zero, for which I built this software. If you have any questions or are interested in using Jabase in your company, please contact Division-by-Zero.

Incoming Revolution: Clojure + Terracotta

2009-03-04T11:16:00.007+01:00

For some time I have been working quite extensively with Java and Java-related technologies in addition to all that Erlang and functional stuff I do every day, and I must say that I am really impressed with what is going on in the area where both worlds overlap. A few months ago I was experimenting with JScheme running on Terracotta, but as I told Ari from Terracotta Inc., who became interested in the project, much more interesting would be combining their product with Clojure. I knew that some people had already been thinking about it.
Not much time has passed since then, and guess what. Paul Stadig announced on his blog that he managed to run Clojure code on Terracotta. Today the same guy just made me looking for my jaw on the floor: he made the whole Clojure environment (together with REPL) work on Terracotta! Now imagine Clojure concurrent applications, using Software Transactional Memory distributed across computer network through Terracotta: you can build massive software clusters that can work with incredible performance; you can add Hadoop (distributed file system) and Hbase (distributed database) and be able to build a system that can handle hundreds of thousands of parallel operations and store petabytes of data; you can scale your system up and and down just by adding or removing machines from the cluster. And with modern cloud computing services, like AWS, you can build a large computation cluster or a social networking website with a relatively small budget.
Basically, you don't need much money to start another Facebook. Your imagination and programming skills are your only limit. Good luck!

JMagLev: Terracotta based MagLev for Ruby

2008-11-13T20:45:00.005+01:00

In one of my previous posts I wrote about clustering solutions for Ruby. One of them was MagLev, based on Gemstone's Smalltalk virtual machine, the second one was based on Terracotta. The latter solution seems more appealing, since Terracotta is open source, and lets you do some own experiments (like this, or this, or even this). Unfortunately, all solutions I have seen so far (including my own) for JVM based languages other than Java depended on a special library that interfaced Terracotta through com.tc.object.bytecode.ManagerUtil class instances, and were not transparent to the programmer. Until now.
Recently, Fabio Kung took a step further and patched JRuby to behave like MagLev, transparently sharing objects across multiple JRuby runtimes. It seems that MagLev got a strong competitor before it even managed to hit the market. Have a look at the demo, it looks equally impressive to what Avi Bryant from Gemstone showed at RailsConf 2008.

Distributed processing with JScheme and Terracotta

2008-11-06T22:25:00.015+01:00

In my post about clustering JScheme with Terracotta I presented how to share Java objects through Terracotta using JScheme. But clustering is not only about sharing data. It is also about parallel (and possibly distributed) task processing.

One of the fundamental assumptions of Scheme (and other Lisps) is that code is data. Programs are just collections of evaluable expressions and thus you can represent data as code, and vice versa. This is exactly what you need when you want to distribute code over a system designed primarily to share data.

I prepared a simple system based on JScheme that allows distributed, concurrent code processing over a Terracotta cluster. It uses a concept of independent nodes (borrowed from Erlang). Each node polls a shared list to find a new expression to evaluate. Once it finds a job to be done, it evaluates the expression using a JScheme evaluator (instance of jscheme.JScheme class) and writes a result back on the list. The client process which initiated the task, reads back the result and returns it.
Since all nodes are independent entities, you can start as many of them as you need and use them concurrently. But in most cases the optimal number of nodes is equivalent to the number of CPUs (or CPU cores) to be used on each machine connected to Terracotta. So if you have 2 computers with a quad core CPU and want to use only half of their power, you can start 2 nodes on each of them. If you want to use them to the full, you should use 8 nodes, 4 per each machine, and so on. You can start the nodes on single machine using a single or multiple JScheme shells, it's up to you. For me, a single Scheme REPL seems to be the most convenient option.
Client jobs are started through tc-map. It's a function that is similar to the standard map, but it takes an additional argument - a list of nodes to use for the job. Unfortunately, the system is not fault tolerant, so if one of the nodes dies during doing the job, the whole processing task hangs up. The only way out then is either to restart the dead node or evaluate the whole tc-map expression again.

OK, enough for the theory, let's do some real work. First you need to download the library. The online folder contains the library itself (jstc.scm), sample Terracotta configuration (tc-config.xml) and some tests. After you get the library and the configuration file, you should start the Terracotta server (I described the whole procedure in detail previously). If you run the Terracotta server on a remote machine, you should also edit the tc-config.xml file and change server host to the IP of the Terracotta host. Now you can start JScheme through the Terracotta bootstrap:

java -Xbootclasspath/p:[terracotta boot jar] -Dtc.config=tc-config.xml -Dtc.install-root=[terracotta install dir] -jar jscheme.jar

You can to find the boot jar in lib/dso-boot folder of your Terracotta installation directory. If it isn't there, you can generate it with Terracotta make-boot-jar.sh script.
Now you can load the library with:

(load "jstc.scm")

and start playing with it. For starters, let's run two nodes:

(start-node "test1")
(start-node "test2")

and define a helper function to generate a list of integers from a specified range:

(define (range min max) (let loop ((x max) (l '())) (if (< x min) l (loop (- x 1) (cons x l)))))

Now we need to "teach" running evaluators the Fibonacci function:

(tc-load (list "test1" "test2") "(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))" )

and we are ready to spread a test job across the nodes:

(tc-map (list "test1" "test2") "fib" (range 1 20))

After a few seconds you should receive the following list:

(1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765)

You can use time function to compare computation times with results received by using a single node or a regular, sequential map:

(time (tc-map (list "test1" "test2") "fib" (range 1 20)))
(time (tc-map (list "test1") "fib" (range 1 20)))
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
(time (map fib (range 1 20)))

Take note that a function passed to map is a regular Scheme expression, while with tc-map it must be a string.

It is quite possible that you get no gain over sequential processing using less than 3 nodes running on 3 cores with this library. The main reason is that Terracotta introduces some overhead itself. The second one is that nodes poll Terracotta for job lists in 20ms intervals. Those intervals are necessary if you don't want to consume the whole CPU power just for loops and leave none for jobs. You can adjust them by changing the value of JSTC_EVAL_DELAY.

I did some tests and I must say that the results surprised me. On my home laptop (Core2 Duo T5450 1.66 Ghz, 2 cores, 2GB RAM) the results looked like this:

(time (map fib (range 1 25))) - 17234 msec
(time (tc-map (list "test1") "fib" (range 1 25))) - 29020 msec
(time (tc-map (list "test1" "test2") "fib" (range 1 25))) - 19620 msec

while on three servers (dual Xeon E5430 2.66 Ghz, 8 cores, 8GB RAM each):

(time (map fib (range 1 25))) - 12687 msec
(time (tc-map (list "test1") "fib" (range 1 25))) - 22502 msec

but:

(time (tc-map (list "test1" "test2") "fib" (range 1 25))) - 25256 msec
(time (tc-map (list "test1" "test2" "test3") "fib" (range 1 20))) - 22355 msec

when I ran the tests on a single machine, and:

(time (tc-map (list "test1" "test2") "fib" (range 1 25))) - 14216 msec
(time (tc-map (list "test1" "test2" "test3") "fib" (range 1 20))) - 11538 msec

when each node was on a different machine.
On my laptop I got almost 150% speedup by using two Terracotta nodes instead of one, but on a server machine two nodes actually slowed the tasks down. I could get faster job processing only by spreading nodes across different machines. Adding new nodes to the machines seemed to have no impact on the results, so I couldn't get past 250% speedup factor.
Weird, isn't it?

Clustering Kawa with Terracotta

2008-10-27T19:30:00.013+01:00

In my recent post I described a method of building a cluster of JScheme instances using Terracotta object management system. I also prepared a small library for JScheme that makes using Terracotta in JScheme easy - it is LGPL licensed and free for download. Today I tried the same trick with Kawa, which is not only a full-featured Scheme implementation in Java, but also a complete framework for implementing other programming languages to run on Java platform. Knowing how to cluster JScheme, making Kawa work with Terracotta was a piece of cake.
First you start a Terracotta server. Then you run a Kawa shell through the following command:

java -Xbootclasspath/p:[terracotta boot jar] -Dtc.config=tc-config.xml -Dtc.install-root=[terracotta install dir] -jar kawa.jar

Just as with JScheme, boot jar is is a stub jar file that starts a Terracotta client before the main application and tc-config is a Terracotta configuration file (see the post about JScheme for details).
Next, you load the Terracotta library:

(load "kwtc.scm")

and define an object (for example an ArrayList) to share across the cluster:

(define ob (create-root "list" (make <java.util.ArrayList>)))

Now you can put values on the list:

(sync-write (lambda () (ob:add 1)) ob)

and read them back synchronously:

(sync-read (lambda () (ob:get 0)) ob))

or simply with:

(ob:get 0)

The library for Kawa can be downloaded from here.
Happy coding!

Clustering JScheme with Terracotta

2008-10-26T15:06:00.013+01:00

In one of my previous posts I mentioned Terracotta, an open source clustering solution for Java. Its main advantage over traditional Java solutions in use (like RMI) is that it works as middleware between a JVM and an application, enabling transparent sharing of Java objects across the network. The only requirement for a programmer is to execute operations on shared objects in synchornized context, which allows you to build distributed applications or refactor already existing ones quickly.
Inspired by Jonas Bonér's experiments with JRuby I decided to give it a try with JScheme, an open source Scheme implementation running on JVM. I chose JScheme over other Scheme implementations (like Kawa or SISC) because of its very simple, clear and elegant interface to Java objects. In fact, since Terracotta operates on the JVM level, you can use it to cluster any application written in any language, as long as it compiles to Java bytecode and provides an interface to communicate with Java objects and classes.
First, you need to download and install Terracotta (current stable version is 2.7.0). Then, you have to start a server with start-tc-server.sh script. In Linux, if you encounter any strange errors running any of the scripts in the bin directory of your Terracotta installation, change the header of a problematic script from #!/bin/sh to #!/bin/bash - this should help to solve the problem. The server manages all the shared objects in Terracotta cluster and needs to be started before any client applications are run.
Next, you need to prepare a client configuration in the form of an XML file. I used a configuration provided by Jonas and stored it in tc-config.xml:


<?xml version="1.0" encoding="UTF-8"?>
<tc:tc-config xmlns:tc="http://www.terracotta.org/config">
  <servers>
    <server name="localhost"/>
  </servers>
  <clients>
    <logs>%(user.home)/terracotta/jtable/client-logs</logs>
    <statistics>%(user.home)/terracotta/jtable/client-logs</statistics>
  </clients>
  <application>
    <dso>
      <instrumented-classes>
        <include>
          <class-expression>*..*</class-expression>
        </include>
      </instrumented-classes>
    </dso>
  </application>
</tc:tc-config>

Now you can start JScheme interpreter hosted by Terracotta:

java -Xbootclasspath/p:[terracotta boot jar] -Dtc.config=tc-config.xml -Dtc.install-root=[terracotta install dir] -jar jscheme.jar

Boot jar is a stub jar file that starts a Terracotta client and connects to the server before the main application is started. You should be able to find it in lib/dso-boot folder of your Terracotta installation directory. If it isn't there, you can generate it with make-boot-jar.sh script found in Terracotta bin folder.
Now when the whole working environment has been set up, you can use com.tc.object.bytecode.ManagerUtil class to create a shared root object. Unfortunately Jonas's method which uses LOCK_TYPE_WRITE static field of com.tc.object.bytecode.Manager class to perform a write lock during this operation fails to work. It causes some strange error about missing com.tc.object.event.DmiManager class, which seems to be a problem even with Jonas's JRuby example itself. A quick solution to this problem is to define locks in a way they are defined in com.tc.object.lockmanager.api.LockLevel class:

(define TC_READ_LOCK 1)
(define TC_WRITE_LOCK 2)

Now let's define a sample object to share. It can be, for example, an ArrayList:

(define l (ArrayList.))

Next you need to create a shared root object named "list" that will hold the l object:

(import "com.tc.object.bytecode.ManagerUtil")
(ManagerUtil.beginLock "list" TC_WRITE_LOCK)
(define ob (ManagerUtil.lookupOrCreateRoot "list" l))
(ManagerUtil.commitLock "list")

Terracotta provides a great debugging tool called Terracotta Administrator Console to analyze the objects held by the server. Start the console by running admin.sh script found in bin folder of the Terracotta installation directory, then connect to localhost and go to Cluster object browser. You should see an empty ArrayList on the object list.
Now let's add a new value to the shared object:

(ManagerUtil.monitorEnter ob TC_WRITE_LOCK)
(.add ob 1)
(ManagerUtil.monitorExit ob)

Go back to Terracotta Administrator Console, select the shared ArrayList and press F5 to refresh the view. You should see that now it holds a single value: 1.
Now start another scheme shell instance and try to read the first list value on the shared list:

(define TC_READ_LOCK 1)
(define TC_WRITE_LOCK 2)
(import "com.tc.object.bytecode.ManagerUtil")
(ManagerUtil.beginLock "list" TC_WRITE_LOCK)
(define ob (ManagerUtil.lookupOrCreateRoot "list" (ArrayList.)))
(ManagerUtil.commitLock "list")
(.get ob 0)

The return value is 1. Sweet!
I wrote a small library for JScheme that allows you to perform the basic operations of creating shared root objects in Terracotta and modifying them with read and write locks. You can download it from this location.
To do the list operations described above you can simply do:

(load "jstc.scm")
(define ob (create-root "list" (ArrayList.)))
(sync-write (lambda () (.add ob 1)) ob)

in one shell and then read the list value in another shell:

(load "jstc.scm")
(define ob (create-root "list" (ArrayList.)))
(.get ob 0)

Have fun!

Erlang tips and tricks: records

2008-10-23T23:30:00.004+02:00

The most awkward thing I ran into while programming in Erlang are things called records. I call them "things" since they are neither Erlang primitives nor data structures. In fact, records are not even understood by Erlang VM itslef (try to define a record in interactive shell). They are some kind of macros (they remind me the ones used in ANSI C) that are translated by the compiler into Erlang native data structures.
The biggest problem with records is that you cannot dynamically modify them. For example, suppose you want to create a table in Mnesia, but you don't know at the moment how many columns your table will have. With records, you have to provide all record declarations for all tables you plan to generate on compilation time, which sometimes is simply impossible.
I did some research on the topic while writing Mnapi, and I must say it wasn't that easy if you don't know where to start. Finally, I managed to decipher Erlang records secrets mostly by analyzing Mnesia source code. One more reason for using open source software, by the way :-)
It turns out that records are in fact wrappers for tuples. So a record defined as:

-record(book, {isbn, author, title}).

gets translated internally into:

{book, isbn, author, title}.

Thus, an equivalent of:

mnesia:write(#book{isbn = I, author = A, title = T}).

is:

mnesia:write({book, I, A, T}).

The only advantage of such crippled structure is that the compiler knows the positions of all elements in the record, so it can always put them in a valid tuple in correct order and find possible errors instantly at the compilation stage. No matter if you write:

#book{isbn = I, author = A, title = T}.
#book{author = A, isbn = I, title = T}.
#book{title = T, author = A, isbn = I}.

the #book record will eventually end up in Erlang as:

{book, I, A, T}.

Records try to make accessing data easier. To get an author from the tuple above you would have to use element function:

X = element(3, {book, I, A, T}).

which can become problematic if you shift fields in the tuple. With record you can do the same simply with:

X = #book.author.

no matter what the order of the record is. But it's still cumbersome and static.
Fortunately, Erlang allows you to build dictionaries, which can be used to store Key - Value pairs dynamically. For example:

D = dict:new(),
D1 = dict:store(isbn, 1234, D),
D2 = dict:store(author, myAuthor, D1),
D3 = dict:store(title, myTitle, D2),
Book = dict:store(book, D3, D3),
dict:find(author, Book).

Personally, I don't use records, unless I really have to. I use dictionaries instead, they are much more powerful and elegant. And you can evaluate them on runtime.

Mnapi 1.2

2008-10-23T20:19:00.012+02:00

I tweaked a bit my Java/PHP API for Mnesia by adding memory caching for auxiliary table structures used by the API. My tests have shown that it speeds up fetching single rows for tables where data are kept in disc_only_copies by about 2%. Much less than I expected, I must say. But since the changes are really little and work seamlessly with data created with Mnapi 1.1 and earlier, I decided to leave them in the code. If anyone is interested in the new version, here it is.

Mnapi 1.1

2008-10-05T16:30:00.014+02:00

Today I released a new version of my Mnesia API for Java and PHP. The main change is merging main code trunk with the Tokyo Cabinet branch and adding the ability to select storage type when creating a table. You can now choose one of the following:
* ram - for RAM only based storage,
* disc - for disc based storage with RAM copy of the table for improved performance (this is the default),
* disc_only - for disc only based storage (much slower, but uses a lot less memory),
* tokyo - for use with Tokyo Cabinet storage engine.
The API does not support table fragmentation and as for now I don't plan to introduce this feature (you can always use tokyo as a storage for data exceeding 2GB limit). But, since the library code is licensed under LGPL, you are free to extend it or modify it if you lack any feature.
You can get Mnapi 1.1 here.
Happy coding!

LFE: Lisp Flavoured Erlang

2008-09-29T02:08:00.006+02:00

Today Robert Virding released a new version of his Lisp syntax front-end to the Erlang compiler, which he called LFE (Lisp Flavoured Erlang). I saw the previous versions of his work, and I must say that it is the first version that looks really mature to me now.

LFE is not an implementation of Lisp or even Scheme. Its syntax reflects some specific constructs and limitations of Erlang, since it compiles programs to Erlang bytecode and runs them directly on Erlang VM.

Is a new trend for Erlang coming on?

Cilk: C that scales

2008-09-27T22:32:00.008+02:00

Do you like C? I do. I used to write software for embedded devices, where resources are priceless and each CPU cycle and every byte of RAM counts. I enjoyed it a lot, mostly because it was a real challenge and it reminded me of good old 8-bit computer times, when if your program was not fast enough you had to optimize its code or find a smarter solution instead of buying a better CPU, expanding memory, or building a home data center. Even today few people question using C to speed up the most critical parts of software, not to mention some obvious examples like Linux kernel, written almost entirely in ANSI C. Two years ago NVidia announced its CUDA platform, which allows developers to write software in C that can run concurrently on many GPUs, outperforming applications using standard CPUs.

For those who don't own NVidia hardware, there is an alternative called Cilk. Cilk is a language for multithreaded parallel programming based on ANSI C. It extends standard C with new keywords like cilk (identifying parallel function), spawn (which spawns a new computation thread) and sync (which gathers job results from all threads started with spawn).

I ran an example Cilk application that finds Fibonacci numbers of a given value:


#include <cilk-lib.cilkh>
#include <stdlib.h>
#include <stdio.h>

cilk int fib(int n)
{
     if (n < 2)
          return (n);
     else {
          int x, y;
          x = spawn fib(n - 1);
          y = spawn fib(n - 2);
          sync;
          return (x + y);
     }
}

cilk int main(int argc, char *argv[])
{
     int n, result;

     if (argc != 2) {
          fprintf(stderr, "Usage: fib [] <n>\n");
          Cilk_exit(1);
     }
     n = atoi(argv[1]);
     result = spawn fib(n);
     sync;

     printf("Result: %d\n", result);
     return 0;
}

As you can see it looks almost like an ordinary C program. You can run it with --nproc argument to determine the number of CPUs (or CPU cores) that are supposed to be used by the application.

As I expected, the Cilk program turned out to be faster than its Erlang equivalent. The speedup was from 5.110972 to 0.689607 seconds on dual Xeon E5430 2.66 Ghz (8 cores total), comparing to 25.635218 and 10.017358 seconds of Erlang version respectively. But what struck me the most about the results was that the Cilk code scaled in almost linear manner:

Wall-clock running time on 1 processor: 5.110972 s
Wall-clock running time on 2 processors: 2.696646 s
Wall-clock running time on 4 processors: 1.355353 s
Wall-clock running time on 8 processors: 689.607000 ms

Cilk code performance boost was approximately 740%, comparing to Erlang 250%. On 8 cores Cilk code outperformed Erlang code by more than an order of magnitude. This is something that should make Erlang developers feel respect for.

Living in a concurrent world

2008-09-26T22:38:00.008+02:00

Erlang is a great platform for writing concurrent, distributed, fault-tolerant applications. But it's not the only one. Some of the popular programming languages also have tools that help developers build concurrent, highly scalable web services.

Java

One of the main sources of Java power is that it has libraries to do almost anything you can imagine. And there are of course libraries that offer various solutions to the scaling out problem, like JMS with JCache or Scala Actors library.
But the real killer application in my opinion is Terracotta. It's an open source clustering solution for Java that works beneath the application level. It uses transactional memory to share objects between applications running on different JVM instances, most notably on different physical machines. Object pool is stored on a master server, which can have multiple passive backups. As a result you receive a clustering solution transparent for the applications you write (you only need to define objects you want to share in Terracotta configuration files). What's more, you can use Terracotta to cluster applications created in languages other than Java, but running on JVM - like JRuby or Scala.

Python

Python programmers can use Disco. It's an open source map-reduce framework written in Erlang that allows you to scale your application easily. Unfortunately, it does not allow neither sharing any data between different application instances (like Terracotta), nor passing messages (like Erlang itself).

Ruby

Ruby looks much better than Python in this aspect. First, there is JRuby, which you can cluster with Terracotta. Second, there is soon-to-come MagLev by Gemstone. It's a Ruby implementation running on a Smalltalk virtual machine, and the first public presentation of MagLev at RailsConf 2008 was quite impressive.

PHP

Not much to say here... You cannot expect much from a language created to produce dynamic HTML pages. You can only rely on external libraries like memcached to store and retrieve objects, but it's by no means an extension to the language itself.

If you know of any other interesting projects providing transparent (or almost transparent) concurrency and distribution to already existing programming languages, you are welcome to tell me about it!

Scripting Erlang

2008-09-26T15:48:00.005+02:00

Today I came across an interesting post about new scripting language Reia for Erlang virtual machine. It seems that some people within the Erlang community started to realize what .NET developers always knew and Java programmers understood a few years ago: that you have to distinguish between the language and the runtime. People who were tired with Java limitations or just wanted to introduce their own ideas started to develop things like JRuby, Jython, Groovy, Scala or Clojure, just to name a few. Erlang has already developed a strong position as middleware. Now it's time to make it scriptable.

You can read more about Reia on this blog. It discusses Reia design principles and goals, as well as some controversial ideas, like introducing classes and objects or multiple variable assignment. It is true that it goes up the stream against Erlang philosophy, but I think that there is nothing inherently stupid about any idea until you can prove it wrong. This is why I don't agree with Joe Armstrong's thesis that Object Oriented programming sucks. There are programming languages that succesfully combine OO and functional paradigms (OCaml, Scala, CLOS), which prove just the opposite. It would be nice to see a modern object system in Erlang, and ALGOL based syntax could convince more people to use this excellent platform. Or, at least, possibly alleviate some already exising Erlang pains.

Mnapi for Tokyocabinet

2008-09-26T02:36:00.013+02:00

Finally, I found some time to patch Mnapi to work with tcerl. Now you can use it to build your web service with this highly promising Mnesia storage backend.

You can download the new Mnapi here.

Due to the nature of Tokyocabinet, remember to always stop Mnapi via

mnapi:stop().

before closing or shooting Erlang shell, so it could gracefully flush all RAM buffered data to disk before stopping Mnesia. Yeah, I know I could use gen_server behaviour to handle it, but I just cannot convince myself to Erlang behaviourism ;-)

Sky is the limit for Mnesia

2008-09-21T17:45:00.002+02:00

Until recently the biggest Mnesia flaw was its storage limit. It is not the fault of the database system, since Mnesia itself can handle data of virtually infinite size. The main problem lays in an outdated Erlang term storage engine called DETS, which is slow and uses 32-bit offsets (it limits single file size to 2GB). DETS could be a perfect fit for the famous AXD301 ATM switch, but is certainly not for modern web development. A few times I had to drop Mnesia in favour of Hbase to serve data and use Jinterface to make it communicate with Erlang code, which served application logic.

But those times are finally over. Thanks to Joel Reymont and the Dukes of Erl you can now use Tokyocabinet engine as a storage for Mnesia. What is the most exciting about this solution is that it is completely transparent to your application - only creating a table looks a bit different:


Table = testtab,
mnesia:create_table(Table, [{type, {external, ordered_set, tcbdbtab}},
                            {external_copies, [node()]},
                            {user_properties, [{deflate, true},
                                               {bucket_array_size,
                                               10000}]}]).

You also need to start tcerl before running Mnesia:

tcerl:start().

and synchronize table data with disk before closing Erlang, if you don't want to loose some of your data:

Port = mnesia_lib:val({Table, tcbdb_port}),
tcbdbets:sync(Port).

To sync all existing Mnesia tables you can use the following function:


F = fun(T) ->
            case catch mnesia_lib:val({T, tcbdb_port}) of
                {'EXIT', _} ->
                    skip;
                Port ->
                    tcbdbets:sync(Port)
            end
    end,
Tabs = mnesia_lib:val({schema, tables}),
lists:foreach(F, Tabs).

All other common operations, like reading and writing data, transactions, etc., don't need to be changed. You can learn more by looking at example provided with the library.

I managed to make ejabberd (one of the best Jabber/XMPP servers around) to run on Tokyocabinet, only with changing a few lines of its code. Now I'm on my way to make Mnapi work with it. Thank you guys!!!

Clojure is here

2008-08-21T18:30:00.007+02:00

Clojure is a Lisp family, dynamic, functional programming language targeting the Java Virtual Machine, with excellent support for concurrent programming. Rich Hickey, Clojure author, prepared a few impressive presentations about the language, which are definitely worth watching. They are not only about Clojure itself, but also give a deep insight into computer language design and concurrent programming in general.

There have been some attempts to compare Clojure with Erlang, although both of the languages address different problem classes. Erlang has strong telecommunication background - starting with the language name itself. It features its own, highly efficient virtual machine, which allows spawning hundreds of thousands of processes and soft real-time performance. Most of its syntax comes from Prolog, since initially Erlang emerged as its dialect - everyone who programmed in Prolog before (like me) will feel at home with Erlang. Finally, Erlang supports programming model based on transparent distribution, which means that you can spawn processes throughout one or several machines without making any changes to the software. Processes (also called actors) share no common memory or data and communicate purely through message passing.

Clojure does not provide its own virtual machine with ability to handle millions of soft realtime processes. Instead, it compiles directly to JVM bytecode, which immediately gives you access to all Java classes and to thousands of libraries written for the Java platform. Clojure is based on Lisp, which is much more popular for programming real-life applications than Prolog. Therefore, despite of its (Lots (of Irritating (and Superfluous (Parentheses)))) syntax, Clojure may be faster to learn and adapt by regular software developers than Erlang. As regards concurrency, Clojure does not support distributed programming. Instead, it uses Software Transactional Memory model. Clojure agents, unlike Erlang actors, use actions instead of message passing to change their state. Actions can be committed inside transactions, which allows for example to read the state of all agents within one transaction, and this way obtain a consistent snapshot of a whole system (pretty tough to achieve in distributed enviornment).

Erlang has a 20-year success story in telecommunication industry and is especially suitable for building highly scalable, fault tolerant, distributed application clusters that are expected to work under very heavy load. It is also ready to work on multiprocessor machines out of the box. However, when finally multi-core CPUs became standard in home computers, Erlang did not sweep away other anachronic programming languages, despite its obvious advantages. I think it is because most home applications don't need many of the features Erlang has to offer. Users don't need 99,98% uptime, as they usually turn off their machines overnight. They don't need soft real-time processing, since they can easily tolerate a few second delay in data processing. Finally, they don't need high scalability, as very few of them are geeks who connect their machines in clusters (who needs it anyway, if you have more and more cores in one box?). As Rich Hickey, Clojure author, said in his discussion on STM:

"Scalability is not a universal problem - some systems need to handle thousands of simultaneous connections - most don't, some need to leverage hundreds of CPUs in a single application - most don't."

Clojure seems to meet the needs of desktop programmers slightly better than Erlang. It provides easy concurrency and all qualities of functional programming, allows you to take advantage of vast set of Java libraries, and lets you to run your software without modification on every platform for which the Java runtime exists. Erlang is unbeatable on server platform, but leaves a lot of space for its desktop counterparts. Clojure is just the first of them. I am sure there will be more.

MapReduce in Erlang

2008-08-14T19:15:00.001+02:00

MapReduce is a Java framework for parallel computations, designed and developed by Google. It is often referred to not only as a platform, but also more general as an algorithm (or a "programming model", as Google calls it itself). The main idea behind MapReduce is to spawn computations on a set of data to many single processes (map), and then gather their results (reduce).

Implementing MapReduce in Erlang is unbelievably trivial. Joe Armstrong, Erlang inventor and main architect, published a sample pmap/2 function, which can be used as a parallel equivalent of standard Erlang lists:map/2:


pmap(F, L) ->
    S = self(),
    Pids = lists:map(fun(I) ->
                         spawn(fun() -> do_f(S, F, I) end)
                     end, L),
    gather(Pids).

gather([H|T]) ->
    receive
        {H, Ret} -> [Ret|gather(T)]
    end;
gather([]) ->
    [].

do_f(Parent, F, I) ->
    Parent ! {self(), (catch F(I))}.

Joe didn't provide any particular examples of using pmap, so I wrote a test function that makes a sequence of Fibonacci numbers. First, let's start an Erlang shell with -smp flag, that enables it to use many CPUs and many CPU cores:

erl -smp

Now define a Fibonacci function:

fib(0) -> 0;
fib(1) -> 1;
fib(N) when N > 0 -> fib(N-1) + fib(N-2).

and generate a test list as a sequence of numbers (for example from 0 to 40):

L = lists:seq(0,40).

To make every element of the list L to be processed by fib/1 function we use lists:map/2:

lists:map(fun(X) -> fib(X) end, L).

To do a parallel computation we need to use pmap/2 instead of lists:map/2:

pmap(fun(X) -> fib(X) end, L).

On my laptop with Core2 Duo T5450 1.66 Ghz running the parallel version of fib/1 function reduced execution time from 53.405534 to 31.354125 seconds (as measured by timer:tc/3). On dual Xeon E5430 2.66 Ghz (8 cores total) the speedup was from 25.635218 seconds to 10.017358. It is less than Joe Armstrong managed to achieve (he probably used more sophisticated test functions and different hardware than a regular PC), but it clearly shows how easy it is to parallelize an Erlang program - just replace every instance of map/2 with pmap/2 and you're done.

I prepared a modified version of pmap/2, which spawns processes not only on local machine, but also on all nodes in a cluster:


pmap(F, L) ->
    S = self(),
    Nod = [node()|nodes()],
    {Pids, _} = lists:mapfoldl(
        fun(I, {N1, N2}) ->
            case N1 == [] of
                true -> N = N2;
                false -> N = N1
            end,
            [H|T] = N,
            {spawn(H, fun() -> do_f(S, F, I) end), {T, N2}}
        end, {Nod, Nod}, L),
    gather(Pids).

Using the modified pmap/2, I got similar results with a cluster of two Erlang shells running on a single Core2 Duo machine as with Joe's function on a single shell started in smp mode. This version of pmap/2 also allows you to rebalance computations by starting as many Erlang shells as there are CPUs (or CPU cores) on multiple machines, and joining them in one cluster.

Scheme & Termite: Erlang alternative?

2008-08-11T19:17:00.003+02:00

Gambit-C is a renowned Scheme interpreter and compiler, which can generate fast and portable C code. It features Termite library written in Scheme, which implements Erlang-like concurrency model for distributed programming. Let's see how it works.

First, create two nodes on two separate machines. Suppose machine one IP address is 192.168.1.101 while machine two is 192.168.1.102. Start a Scheme REPL on the first machine through tsi script shipped with Termite (it enhances standard Gambit gsi shell with Termite functions) and init it as node1:

(node-init (make-node "192.168.1.101" 4321))

Now start tsi on the second machine and init it as node2:

(node-init (make-node "192.168.1.102" 4321))

Stay at node2 shell and define an expression to identify node1:

(define node1 (make-node "192.168.1.101" 4321))

Now you can remotely spawn a process on node1:


(define p (remote-spawn node1
  (lambda ()
    (let loop ()
      (let ((x (?)))
        (! (car x) ((cdr x)))
        (loop))))))

The code above remotely spawns procedure p on node1, which waits for a signal in an infinite loop. When it receives signal x as a pair of sender and expression to evaluate, it evaluates the expression, sends its result back to the sender, and loops back. To see it in action evaluate the following expression in node1 REPL:

(! p (cons (self) host-name))

It causes command host-name to be sent to process p on node1. Now you can display received result with:

(?)

Erlang equivalent would look like this:


-module(p).

-export([start/0,loop/0]).

start() ->
    register(p, spawn(node1, p, loop, [])).

loop() ->
    receive
        {Pid, F} ->
            Pid ! (catch F()),
            loop()
    end.

You would call it with:

{p, node1} ! {self(), fun() -> N = node(), N end}.

and read its result with:

receive X -> X end.

So far so good. Now let's halt the Termite shell on node1:

,q

And try to invoke procedure p from node2 again:

(! p (cons (self) host-name))

The shell will segfault. Oops...

This is not the only problem with Termite. Gambit-C comes with gsc, a Scheme to C compiler, which I used to compile the sample script above. First, I had to go to /usr/local/gambc/current/lib/termite and compile Termite itself:

gsc termite

Then I prepared a sample file remote.scm:


(##include "~~/lib/gambit#.scm")
(##include "~~/lib/termite/termite#.scm")

(node-init (make-node "192.168.1.102" 4321))
(define node1 (make-node "192.168.1.101" 4322))

(define p (remote-spawn node1
  (lambda ()
    (let loop ()
      (let ((x (?)))
        (print (cdr x))
        (! (car x) ((cdr x)))
        (loop))))))

(! p (cons (self) host-name))
(print (?))
(newline)

And compiled it to executable binary code:

gsc -c remote.scm

gsc -link /usr/local/gambc/current/lib/termite/termite.c remote.c

gcc -o remote /usr/local/gambc/current/lib/termite/termite.c remote.c remote_.c -lgambc -lm -ldl -lutil -I/usr/local/gambc/current/include -L/usr/local/gambc/current/lib

Now I started node1 on 192.168.1.101 again:

(node-init (make-node "192.168.1.101" 4321))

and tried to run remote binary code from 192.168.1.102:

./remote

Kaboom! Another segfault... Seems like compiled binary cannot handle message passing correctly, although it works in tsi interpreter.

I tried to create a bit more sophisticated Gambit-C/Termite application, but unfortunately I failed to find more useful documentation on Termite than its initial paper. There are also very few examples on Termite, and the most interesting I found come from Dominique Boucher's blog (my test script is based on those examples).

On the other hand, a great advantage of Gambit-C over Erlang is that it can translate Scheme applications to plain C, which than can be compiled to standalone executables using gcc. Thanks to this feature I managed to compile a few Gambit examples with OpenWRT-SDK and ran it on my home Linksys WRT54GL router with OpenWRT firmware - the only thing I had to do was to replace gcc command with mipsel-linux-gcc while compiling gsc output files.

To sum up, Termite is a very interesting and ambitious project, and its authors deserve applause for their job. Unfortunatelly, it seems that it is still in its experimental stage, and is not ready for production use yet. However, when finally done, it can be very useful Erlang alternative (thanks to the Gambit-C compiler) for programming embedded devices and systems, where Erlang VM does not exist. I think this post is also a good comment on Erlang and Termite.

Web services need balance

2008-08-07T19:19:00.007+02:00

So we already have a nice and fast web service based on PHP and Yaws or not so fast, but still nice, service powered by Java and Tomcat. We also have a powerful Mnesia storage back-end we can communicate with through a dedicated api. Now we are ready to scale.

There's a lot of ways for balancing a web cluster. You can use one of many software load balancers, configure a front-end web server as a reverse proxy or even use a dedicated hardware load balancer. But hey, we have Erlang, so why bother with complicated software or spend money for expensive hardware? Writing a simple load balancer in Erlang took me about an hour, including testing, and I am not a very experienced Erlang programmer. This can give you some picture of how functional programming can improve your performance as a developer.

What the balancer actually does is checking the system load on all nodes in a cluster and returning a name of the least loaded one. The software is GPL licensed and can be downloaded from here. You should compile it with:

erlc balancer.erl

and deploy it to all machines you want to monitor. Now you can check the system load of the current node:

balancer:load().

all of the nodes you are connected to:

balancer:show(nodes()).

all of the nodes including current node:

balancer:show([node()|nodes()]).

pick the least loaded one with:

balancer:pick(nodes()).

or with:

balancer:pick([node()|nodes()]).

Due to Erlang nature, dead nodes are instantly removed from the nodes() list, so they are not queried. Additionally, the balancer filters out all nodes that returned an error, so you always get valid results, with no timeouts, deadlocks, etc. However, the result only says that a machine is up, so if a web server dies for some reason, and the machine itself did not crash, the node will still appear on the list (which is quite obvious).

Since the balancer is written in Erlang, it seems natural to deploy Yaws as a front-end web server and use it to redirect users to the servers that are least loaded at the moment. Suppose we have each web server running on different sub-domain (s1.host.domain, s2.host.domain, etc.), and each of them runs a single Erlang node. In this case our index.yaws on http://host.domain/ can look like this:


<html>
<erl>
out(Arg) ->
    {Node, _} = balancer:pick(nodes()),
    [_|[Host|_]] = string:tokens(atom_to_list(Node), "@"),
    Url = string:concat("http://", Host),
    {redirect, Url}.
</erl>
</html>

Connecting to http://host.domain/ will now automatically redirect you to the fastest server. It is your choice if you want to keep users bound to the back-end server or refactor links on your web site to make them go through the redirector each time they click on a link. In the latter case, if you provide dynamic content, you can use Mnesia to store user sessions so they would not get logged out if they suddenly switch from one back-end server to another.

Mnapi: Mnesia API for Java and PHP

2008-08-07T16:21:00.009+02:00

Mnesia is a scalable database system designed to work as a storage system for large, distributed applications. In my previous post I showed you how to set up a Mnesia cluster using Erlang shell. Unfortunately, Mnesia cannot be easily accessed from languages other than Erlang. If you are a web developer, there is even an MVC framework for you - Erlyweb. But what if you are a mainstream programmer who would like to use the power of Mnesia, but is not willing to learn another language and change the whole way of thinking in order to understand the functional programming philosophy?

This is why I created Mnapi - API for Java and PHP, which provides basic methods to create, fetch, update and delete records in Mnesia. It is licensed under LGPL, which means that you can get it and use it in any commercial or non-commercial applications, and you are only obliged to publish only the source code of Mnapi if you extend it or modify it (the license does not affect an application which makes a use of it). You can download Mnapi here.

Please bear in mind that Mnesia does not support creating multiple databases or schemas within one instance, joining tables, etc. - and the API reflects those restrictions. You can learn more about it reading documentation attached to the source code and running example applications, so I will not be describing it here in detail. What you need to start using Mnapi is to compile Erlang driver for Mnesia:

erlc mnapi.erl

then start an Erlang shell:

erl -sname erl -setcookie mysecretcookie

and run Mnapi server from the shell:

mnapi:start().

Now you can use Java or PHP to talk to Mnesia through Mnapi libraries.

Note that to use Mnapi from PHP you first need to install and configure Erlang extension for PHP. Read instructions provided with the extension to learn how to configure you PHP installation.

To compile Java api you need Jinterface. If you cannot find Jinterface in lib folder of your standard Erlang installation, you can either download Erlang source code distribution or install it as a package from CEAN.

Have fun!

Erlang tips and tricks: Mnesia

2008-08-07T09:51:00.000+02:00

Mnesia is one of Erlang killer applications. It's a distributed, fault tolerant, scalable, soft real-time database system which makes building data clusters really easy. It is not designed as a fully blown relational database, and it should not be treated as its replacement. Although Mnesia supports transactions (in a much more powerful way than traditional databases, as any Erlang function can be a transaction), it does not support SQL or any of its subsets. Mnesia is best suitable for a distributed, easily scalable data storage, which can be shared by a large cluster of servers. One of the most notably known examples are ejabberd - a famous distributed jabber/xmpp server - and cacherl - a distributed data caching system compatible with memcached interface.

Setting up a cluster of Mnesia nodes is easy. First you need to set up a cluster of Erlang nodes as I described in my post Erlang tips and tricks: nodes. Start Mnesia instances on all of them:

mnesia:start().

Now choose one of the nodes as initial Mnesia server node. It can be any node, as Mnesia works in peer-to-peer model and does not use any central management point. Go to a chosen Erlang shell and move the database schema to disc to make it persistent:

mnesia:change_table_copy_type(schema, node(), disc_copies).

You can now create a new table, for example:

mnesia:create_table(test, [{attributes, [key, value]}, {disc_copies, [node()]}]).

which creates table test with two columns: key and value. Attribute disc_copies means that a table will be held in RAM, but its copy will be also stored on disc. If you don't store any persistent data in your table, you can use ram_copies attribute for better performance. On the other hand, if you want to spare some of your system memory, you can use disc_only_copies attribute, but at the cost of reduced performance.
Now let's add a second node to Mnesia:

mnesia:change_config(extra_db_nodes, [node2@host.domain]).

Of course replace node2@host.domain with the name of a node you want to add (or a list of nodes: [node2@host.domain, node3@host.domain, ...]).
Now switch to Erlang shell at the node you have just added and move its schema to disc, so Mnesia remembers it's a part of the cluster:

mnesia:change_table_copy_type(schema, node(), disc_copies).

You can now create a copy of table test on this node:

mnesia:add_table_copy(test, node(), disc_copies).

Now you can add a third node, a fourth node, etc. in the same way as you added the second one. When you have many nodes in the cluster you can keep tables as disc_copies only on some nodes as backup, and use ram__copies on other nodes to improve their performance. It generally makes sense to keep tables on disc only on one of the nodes per single machine.

To remove node@host.domain from the cluster stop Mnesia on that node:

mnesia:stop().

Now switch to any other node in the cluster and do:

mnesia:del_table_copy(schema, node@host.domain).

Mnesia is strongly fault-tolerant, which means that generally you don't need to worry when one of your nodes crashes. Just restart it and reconnect it to the cluster - Mnesia node will synchronize itself and fix all broken and out-of-date tables. I really like to imagine Mnesia as a database equivalent of T-1000, which even heavily damaged or broken into pieces, every time reassembles itself to its original form.

Unfortunately Mnesia has its limits. A storage limit seems to be the most troublesome of them.

Erlang tips and tricks: interactive shell

2008-08-05T00:30:00.001+02:00

In my previous post I described issues you can run into when configuring an Erlang cluster. Now let's move a step further.

One of the most impressive Erlang features is its unique ability to do a hot code swapping. It means you can exchange the code of a running system without stopping it! Pretty neat, huh? Let's have a look at a very simple server, that just loops and displays its status when asked:


-module(test).
-export([start/0, loop/0]).
start() ->
    register(test, spawn(test, loop, [])).
loop() ->
    receive
        status ->
            io:format("~n Status OK ~n"),
            loop();
        reload ->
            test:loop();
        quit ->
            ok;
        _ ->
            loop()
    end.

The main loop waits for signals from clients and according to the signal does one of the following:
1) On status it displays a text "Status OK" and continues to loop.
2) On reload it hot swaps the server code.
3) On quit it quits with finishes with ok.
4) On any other signal it just loops.
After saving this code as test.erl and compiling with:

erlc test.erl

you can start a REPL shell and run the server with:

test:start().

The start() function spawns a new Erlang process and registers it on the currently running node, so you can call it through a name instead of through its process ID like this:

test ! status.

If you play around with Erlang you already know that. But how about calling test from another node? When you connect another node to the cluster and try to call it you will get an error saying that test is not a registered name. The answer is simple, but unfortunately not so easy to find in Erlang documentation. You need to call it with a tuple (pair) containing both node name and process name:

{test, test1@host.domain} ! status.

So now comes the time for hot swapping. You can edit the source file, change "Status OK" to any other text of your choice and recompile - of course without leaving the interactive shell, since our server is supposed to have 100% uptime :-)
Afterwards you switch back to REPL, do

test ! reload.

than

test ! status.

and you see... no change whatsoever. Why? Because Erlang shell caches executable code. If you want to load the modified version of the code you just compiled into REPL, you need to tell it to do so with:

l(test).

Suppose you have more nodes in your cluster where the code exists and you want to refresh Erlang cache on all of them, you should use:

nl(test).

You can also use the latter command to distribute your code across the cluster, without the need of sending the compiled binary test.beam to all of them through FTP or SCP.
Sweet, isn't it?

Erlang tips and tricks: nodes

2008-08-04T19:51:00.004+02:00

The title might be a bit exaggerated, but if you have just started your adventure with Erlang I would like to provide you with a couple of hints that can spare you a serious headache.

The basic tool to work with Erlang is its REPL shell, started in terminal mode with erl command. The name REPL comes from read, eval, print, loop cycle and among functional languages is a commonly used term for interactive shell. Since Erlang has been developed with distributed programming in mind, you can start as many shells as you like and make them communicate with each other. The basic rule you have to remember about is that you can interface only shells that share the same cookie. A cookie is simply a string that acts as a shared password to all nodes in a cluster, whether they run on the same computer or different machines across the network. You can set it either from the command line when starting REPL using -setcookie parameter or from the Erlang shell itself:

erlang:set_cookie(node(),mysecretcookie).

You can also edit .erlang.cookie file in your home directory so you don't have to set it up every time you start the shell. However, this method has some nasty side effects and that's why it is not recommended. The first one is that all Erlang applications you start from your user account, including all REPLs, will share the same cookie, which not always is a desired behaviour. Secondly, it is very likely that you forget to edit this file on another machine where you move your Erlang application to (or will not have enough permissions to do it), and your application will not work in environment other than yours.

So now when you have started your shells and set up a shared cookie you may want to check the connectivity between them. But first you need to know how to call them - now here's where the real fun begins. Erlang allows you to call a node (shell instance) with either a short or a long name ("-sname" and "-name" command line parameters respectively). A short name is a common name like "test" while a long name is a fully qualified domain name like "test@host.domain". Short names are shared across machines in the same domain, while FQDN names can be used (theoretically) across the whole Internet. So you start a short name REPL with:

/usr/bin/erl -sname test1 -setcookie mysecretcookie

So far so good. Now try another one within the same domain:

/usr/bin/erl -sname test2 -setcookie mysecretcookie

And now you want to ping test2 from test1 to check if everything is OK. So you input the following command in test1 REPL:

net_adm:ping(test2).

And you see "pang", which means that something went wrong. So you start to tear your hair out until you realize that test1 is not a node name in Erlang! Now go back to your REPL again and look carefully at the prompt. You will probably see something like:

(test1@localhost)1>

Now try to ping test2 again, but this time use a full name as displayed in REPL prompt:

net_adm:ping(test2@localhost).

And what you should now see is "pong", which means that the nodes can now see each other. Note that test2@localhost, although doesn't seem so is still a short name, not a fully qualified domain name (it lacks a domain part).

You can always see a list of all other hosts in the cluster after issuing command:

nodes().

in REPL. But remember about one important thing: new hosts are not seen by Erlang automatically. If you start a new Erlang instance and want it to show on the nodes() list, you have to ping one of the hosts already existing in the cluster. Information about a new node will be automatically propagated among all other nodes. To avoid it, you can use .hosts.erlang file in your home directory, which role is similar to the role of .erlang.cookie (including side effects) - it holds the list of all nodes which will be automatically informed about every new Erlang instance started on your user account, for example:

'test1@localhost'.
'test2@localhost'.

You need to have one empty line at the file end (look here for more information about the syntax).

So here are the basic things you should remember about when building an Erlang cluster:
1) Choose carefully between short and fully qualified domain names, since the first cannot communicate with the latter ones (to make it simple: you cannot mix short and long named nodes across one Erlang cluster).
2) When using more than one machine in your cluster, make sure all DNS records on all machines are set up properly to avoid communication problems.
3) Use the same cookie for all Erlang instances you want to put in a cluster.
4) When you start a new node always inform the cluster about it by pinging one of the running nodes.
5) Open port 4369 TCP/UDP on your firewall for all clustered machines - it is used by epmd daemon, which handles inter-nodes Erlang communication.

PHP Zend Framework on Yaws

2008-08-04T16:02:00.008+02:00

Web developers looking for an efficient web server should definitely give a chance to Yaws, a lightweight and very fast open source web server developed in Erlang. For those who do some work in Erlang, this should be enough for a recommendation, since Erlang has been designed with high performance and scalability in mind. Those who haven't heard of Yaws and Erlang should have a look at this Yaws vs Apache comparison to get the idea.

Unfortunately, Yaws is not as mature as Apache in terms of available functionality. The one thing I missed particularly about it was the lack of easily definable rewrite rules, which would allow me to set up my favourite PHP framework (namely Zend Framework) to work under control of Yaws. Browsing through Yaws Wiki I found a post explaining how to use rewrite feature in Yaws. I used it as a starting point for my own rewriting module, which allowed me to run ZF on Yaws. I published it on Trapexit as a free code under no particular licence, beacuse - as I said - I didn't write it from scratch, but used a public domain work. Here's how it works (I assume you already have Erlang and Yaws installed in your system):

First you need to configure your MVC enviornment. I suggest following a manual at Akra’s DevNotes to create the basic directory structure. Suppose your Yaws document directory is /opt/yaws, you'll have to create folders /opt/yaws/application, /opt/yaws/library and /opt/yaws/public. Also create /opt/yaws/log folder for web server logs. Then create /opt/yaws/ebin and put there rewriter.erl. Compile the rewriter module from the command line with

erlc rewriter.erl

Create yaws configuration file yaws.conf and inform the web server to use php scripts and the rewrite module


php_exe_path = /usr/bin/php-cgi
ebin_dir = /opt/yaws/ebin
logdir = /opt/yaws/log

<server localhost>
    port = 8080
    listen = 0.0.0.0
    docroot = /opt/yaws/public
    allowed_scripts = yaws php
    arg_rewrite_mod = rewriter
</server>

Finally, run your web server

yaws --conf yaws.conf

and go to http://localhost:8080 to see if it works.

From now on, all client requests to localhost will be redirected through a bootstrap file /opt/yaws/public/index.php. Make sure all paths in your PHP scripts lead to correct locations.

Tested on Erlang R11B with yaws 1.68 on Linux Mint 4.0 32-bit and yaws 1.73 on Ubuntu Server 8.04 64-bit with Zend Framework 1.5.

Good luck!