Java to the Limit

How Could it go so Bad?

2013-05-21T16:22:09+02:00

This past weekend I’ve been reading Roubini and Mihm’s Crisis Economics, a worthwhile read if you’d like to understand what went wrong.

I’m “just an ordinary guy” when it comes to international-scale economics; and like most people probably — I’ve been baffled by what the financial crisis that peaked in the fall of 2008 was really about. This book is a great and neutral exposition of what really happened and what we should do about it.

What Happened?

The first two thirds of the book is a history lesson on what happened, a parallel tale of 1929 and 2008. The last part talks about what we should do about it, and how the concequences of the US’s enoumous current trade deficit may unfold.

The latter part is the more interesting of course. The authors make it very clear that the crisis is not directly the fault of the individual actors in the financial system; it’s the system itself that is fundamentally broken.

One central principle that was broken in the recent crisis was that central banks bailed out (a) financial institutions that were not just illiquid but they were also insolvent, and (b) they also bailed out non-banks. Both represent moral hazards, as it may cause people to expect such bail outs in the future; even in non-bank financial institutions, which is likely to make them take risks they would not otherwise undertake.

What should be done?

The crisis is an eminent opportunity to change legislation. Generally, the legislation need to guide system actor’s motivations and increase transparency.

Compensation in the financial sector should be restructured so as to value long-time gains rather than quick wins. The authors make it an explicit point to say that it is not necessarily the size of compensation which is the problem; it’s the structure. There needs to be more skin in the game.
The fact that rating are payed for by the very institutions that are selling financial products, is fundamentally broken. IMO, ratings should be provided to the public free of charge by truly independent bodies — national or supernational, and the more the merrier. Until then, never trust an AAA rating again.
Derivatives need to be controlled. It’s absurd that the system alows anyone to buy CDS’s “bankrupcy insurance” for a any 3rd party; even without having an equity interest in that party. It’s like buying fire insurance for your neighbours house ... which might motivate me to play around with some matches ...
Too-big-to-fail oriented legislation is bullshit; rules should apply to everyone. If anything, corporations that are too large to fail should be split up.

The book contains many more suggestions for what could be done, the above are some of the more important ones it seems.

What’s Next?

According to the authors it is inevitable that soon, the US’s status as the world’s primary economy will fade, and likely be replaced with a century with Chinese dominance. The US Dollar cannot continue to be the reference currency. Hopefully this shift will happen in an orderly fashion, but if the US tries to devaluate the dollar by inducing too much inflation (reducing the value of treasury bonds) we might see a “run on the bank” out of the ordinary.

Conclusions

Great book. There’s a lot of “doom day” books out there, this is not one of them. It provides a solemn and trustworthy account of what happend and argues what we need to do.

Consistency Eventualis

2012-10-22T23:47:29+02:00

Here is just a short note on the unfortunate choice of name for the concept Eventual Consistency. To many non-native speaking people, it sounds like Maybe Consistent.

Many languages have a word derived from the latin word eventualis (German: eventuell, French: éventuel, Danish: eventuelt, …) which in these languages literally means possibly or perhaps - a word used to denote something which may happen, or maybe not. For instance, we would use it in phrases such as [replace underlined word with with "our" version of eventual]:

Could you perhaps do me a favour?
What do you think of the possibly fatal outcome?

To an average Dane, for instance, eventually fatal doesn't necessarily sound bad; likewise eventually wonderful is not necessarily good.

This is of course very unfortunate us who want to promote eventual consistency as a tool to provide better scalability and availability in large-scale distributed systems. The term makes it sound flaky, or "perhapsy". "If you are lucky - and the planets all line up correctly - yes, then it will eventually be consistent." It just rings wrong.

So, from now on I propose that we all call it delayed consistency, which at least to my ear sounds much more right. It sounds like we will eventually get there :-)

Erlang is not a Concurrent Functional Programming Language

2011-05-24T01:14:24+02:00

Modern distributed data stores such as CouchDB and Riak, use variants of Multi-Version Concurrency Control to detect conflicting database updates and present these as multi-valued responses.

So, if I and my buddy Ola both update the same data record concurrently, the result may be that the data record now has multiple values - both mine and Ola's - and it will be up to the eventual consumer of the data record to resolve the problem. The exact schemes used to manage the MVCC differs from system to system, but the effect is the same; the client is left with the turd to sort out.

This led me to an idea, of trying to create a data structure which is by it's very definition itself able to be merged, and then store such data in these kinds of databases. So, if you are handed two versions, there is a reconciliation function that will take those two records and "merge" them into one sound record, by some definition of "sound".

From what I have seen, the "thing" stored is often itself a collection like a list or a hash map, and say that Ola and I both add new elements to the collection and store the results, the resulting multiple records are - with proper definitions - naturally mergeable; namely the list or map that contains the original entries plus both mine and Ola's.

So, this is the presentation of my idea: A vector map, which is a data structure that is designed to be used in this context. It also has other interesting applications as we shall discuss towards the end of this post.

Vector Maps

A vector map is defined as a set of assignment events, Key=Value, each such event being time stamped with a vector clock (hence the name). From a high-level point of view, a vector map can be seen as a hash table i.e., a collection key/value pairs.

Two vector maps can be reconciled (VectorMap₁ ⊕ VectorMap₂), so that for each key, the "most recent assignment event" wins. If assignment events are in conflict (vector-clock wise concurrent), then the resulting value is multivalued.

The reconciliation function for vector maps is defined so that it is commutative i.e., it can be applied in any order i.e.,

A ⊕ B = B ⊕ A,

It is also associative,

A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C,

which means that reordering done inside the database store, is insignificant to the resulting usage.

In fact, Riak itself (the distributed key/value store) is just a big distributed and redundant version of this; which just goes to prove the versatility of the idea. So in a sense, a vector map is just a recursion over the Riak (Dynamo) concepts applied to a data structure.

In the following we will define things a little more rigorously and provide some examples; and towards the end there is a discussion of how vector maps can be used.

Assignments as Vector Clocked Events

For the purposes of this discourse, we will model an assignment event as

a Key,
a Set of values, and
a vector clock, VC, describing when the assignment happened,

so an assignment event has the following form:

Assignment :: VC: Key = [Value, Value, ...]

We will let the set contain multiple values in case a conflict has been observed, but to start off with our sets will be single-valued.

Our system will use the vector clock to determine "who wins". Let's see what happens ...

To begin with, I do an assignment "X" = 4, and record this event:

Assignment₁ = (krab:1) : "X" = [4]

Reading: at krab's time 1, "X" is bound to 4.

Later, after observing my assignment, a colleague Ola, at his time 2, defines "X" to be 5

Assignment₂ = (ola:2,krab:1) : "X" = [5]

Now, the immediate beauty is that because each assignment is time stamped with a vector clock, we can easily determine that Assignment₂ happened after Assignment₁ (the vector clock says that Ole did indeed observe Assignment₁ before creating his own), and so if we see both we can discard the earlier one without loss.

Conflict happens

Now, what happens if Jens comes in, and based on only observing my original assignment, he reassigns "X" to be 7. We'll describe this with the following event:

Assignment₃ = (jens:3,krab:1) : "X" = [7]

To Jens, this is not problematic, but if someone observes both Assignment₂ and Assignment₃ they'll know that Jens did not observe Ola's time 2.

To make some kind of sense out of this, we define the reconciliation operator ⊕, describing the aggregation of knowledge we have when combining the known events.

Assignment₂ ⊕ Assignment₃ = (krab:1,ola:2,jens:3) : "X" = [5,7]

I.e., we describe that "X" has conflicting values 5 and 7 at a point in time which is after both Assignment₂ and Assignment₃.

Deleting values

A further complication is what happens when we want to delete a binding, but this is handled quite simply by making a new assignment to a unique tombstone value which is somehow outside scope of other possible values; and then reconciling that into the current event set. This does have some interesting properties, because there is an observable difference between a binding that was never there, and a binding that was removed.

Defining Reconciliation

In the example above, we can see from the vector clocks that Jens had not observed Ola's assignment, and so we reconciled the two conflicting events by

creating an artificial vector clock (krab:1,ola:2,jens:3) which is logically after both (ola:2,krab:1) and (jens:3,krab:1), and
combining the bound values [5] and [7] into a set of values [5,7].

Had it been obvious that one assignment happened before the other, we would simply had thrown one of them away, but because the two vector clocks were in conflict we have to recognize the conflict.

So the actual definition of reconciliation for two assignment events with the same key is as follows:

VC₁:Key=Set₁ ⊕ VC₂:Key=Set₂ ≡
VC₁ ≤ VC₂ → VC2 : Key = Set₂;
VC₂ ≤ VC₁ → VC₁ : Key = Set₁;
otherwise → lub(VC₁,VC₂) : Key = (Set₁ ∪ Set₂)

The reconciliation operator (o-plus) is commutative (just like good old addition), so we can use it to reconcile assignment events in any order and we'll always arrive at the same result in the end. Which makes it perfect for making decisions in a distributed system; because it means that even if we get to know about events in different order, the state will eventually reconcile to the same value (eventually meaning when we've seen all the events).

The definition uses the lub (least upper bound) on two vector clocks, which combines two such by taking the maximum local time stamp for each agent present in two sets of vector clocks:

lub( VC₁, VC₂ ) ≡
∀ a ∈ agents(VC₁) ∪ agents(VC₂)
a : max( time(VC₁,a), time(VC₂,a) )

Where time(VC,a) is 0 (zero) if VC does not list an agent a. For example

lub( (b:3), (a:1, b:2) ) = (a:1, b:3)

What is this good for?

You may rightly say that this doesn't solve the problem, it just pushes the problem one level down. And that's right; but ... it does solve an interesting range of problems, and with some care you can often structure your usage of keys in vector maps so that you can avoid conflicts all together.

Further, since your favorite data store already does this for you ... you may say that you can just split your map into individual key/value bindings and store those in the database. But that comes at a price of network round trips and data locality.

Use case: Modeling Relationships in MVCC data stores

Vector maps are really nice for modeling relationships inside MVCC databases.

Assuming you want to store a one-to-many relationship in Riak (say, order - order-item), you run into the problem on the one-side that it is likely to be concurrently updated if multiple items are added to the same order.

With vector maps, you can easily model the entire relationship as one order object which is just a vector map, where each item is stored with a distinct key. If that key is e.g. a sufficiently large random number, making it very unlikely that order-item-id's conflict, then you're pretty much home free. Alternatively, you can devise a mechanism so that each client of the system is able to construct globally unique keys (agent + sequence number).

For this use case, you'll see much improved performance also, because of the improved locality of reference. If your data store needs to go and fetch each individual order-item on the disk somewhere, then performance will be seriously hampered.

Use case: off-line data

Vector maps are great for off-line data, because they give a well defined meaning to the concept of synchronization (something I would really like my iCal to do :-) Synchronization is simply defined as the exchange of vector maps, storing the result of the reconciliation on both sides.

Such synchronization can happen in near-real time (peer-to-peer update) or as a delayed synchronization whenever there is contact to a server/peer.

This is perhaps the most interesting use case, because it an be used as a simple foundation for making data available to e.g. mobile clients in an "occasionally connected" system, in a way that makes sense for both online and offline mode.

Implementation Issues

Since it is a little complicated to manipulate a vector map, we need implementations in the most common languages out there to get it off the ground. I'm currently hacking on an Erlang and a Java version.

Working on this, and I have come to the conclusion that it would be great if vector maps have a well defined binary representation so that they can be meaningfully manipulated in a number of different contexts, easily stored and transmitted, etc. So, a special mime-type that lets multiple parties consume vector maps independent of programming languages.

If vector maps had it's own mime type and well defined data representation, data stores such as Riak or CouchDB could even do the reconciliation automatically before serving the data to a client.

So, right now I am working with a protocol buffers definition that looks like this on the wire, to be encoded as Content-Type application/x-protobuf;proto=vectormap, and likely a also a JSON representation application/json;schema=vectormap.

message VectorMap {
   repeated Entry entries    = 1;
}

message Entry {
   required string key       = 1;
   repeated Clock  vclocks   = 2;
   repeated Value  value     = 3;
}

message Value {
   optional string mime_type = 1 [ default = "application/json;charset=utf-8" ];
   optional bytes  content   = 2;
   optional bool   deleted   = 3 [ default = false ];
}

message Clock {
  required string node       = 1;
  required uint32 counter    = 2; 
  required uint64 utc_millis = 3;
}

Conclusions

The Dynamo idea of using vector clocks to time stamp data is great, but I think the power of the idea goes quite a bit further if the logic is brought all the way to the client.

CouchDB tries to do this by suggesting that client devices (mobile devices) should have a full fledged CouchDB running there. But I think that exposing data this way makes the mobile client model much more manageable. This entire idea can be wrapped up in a single Java class which is easily deployed in a Android app; and it is sufficiently simple to be implementable in a range of programming languages.

What do you think?

About Version Vectors (a.k.a. Vector Clocks)

2011-01-26T19:53:11+01:00

The last few weeks I've been working on understanding vector clocks (or rather, version vectors). When working with distributed data stores like Riak and Voldemort which are using this to manage consistency, it is important to have a deep understanding of what kind of consistency they provide, and how to design systems that work well with these structures.

So, without further ado; here's my story. We'll start somewhere else though.

Versions of shared spreadsheets

Adam and Eve are working on a shared Excel spreadsheet, and they have devised a clever scheme for versioning it, so they can detect conflicting edits.

Their idea is that the document has two version numbers embedded in the file name. When Adam saves a new version, he increments his number; and likewise for Eve. After some exchanges and edits, the document is now called doc_adam3_eve4.xls (Adam in version 3, Eve in version 4). The rules of the game are thus:

If Adam updates the document, he shall increment from adam3 to adam4, and so name the next version doc_adam4_eve4.xls, whereas
if Eve updates the same document she shall increment eve4 to eve5 and call the result doc_adam3_eve5.xls.

Because both Adam and Eve have their own version scheme, they can make edits and when they share their updated documents they can easily detect if they have made concurrent edits. Eve will bring her maximum eve-numbered version, and Adam will bring his maximum adam-numbered version. Then a mechanism depicted in this diagram can be used to detect a conflict:

Given version {adam=3,eve=4} (represented by the white square in the middle), you can see which versions are logially "after" and "before" that version. Versions colored yellow are in conflict with doc_adam3_eve4.xls, representing logically "concurrent" edits.

The great thing is that this scheme extends to any number of participants. It's just easier to depict in a two-dimensional way, but the same mechanism works for any number of vector dimensions. Missing participants are assumed to have version 0.

Vector Time. The numbering scheme above is an example of a vector clock which can be used to describe temporal relations between events in a distributed system. Generally speaking, a vector clock is a list of (place, version) pairs, in which each place occurs at most once.

Really, we should perhaps talk about version vectors because the time-notion does not exactly refer to our intuitive notion of time, but to some monotonous increasing series of "versions" issued at each "place".

version vectors and version vectors have a partial ordering, which captures the idea of before/after a given point in vector time. It's partial because there exists pairs of version vectors so that one is neither before nor after the other; they are "concurrent".

If you have a set of version vectors, there is thus a subset hereof which are "maximal" (most recent). This set contains only one element if there is no conflict.

If you use version vectors to give versions to documents, then it is obviously great if there is only one such "most recent" document. If there is more than one "most recent" then at least you have narrowed it down to the versions to take a closer look at.

Assembling the Jigsaw

Regardless of their cleverness, Adam and Eve are often in trouble, because often they have more than one "most recent" Excel spreadsheet when they get together (say, doc_adam4_eve4.xls and doc_adam3_eve5.xls mentioned before), and so they have to sit there and take their spreadsheet apart, resolve the conflicts, and put it back together. Once they have resolved their conflicts they can name the new version doc_adam4_eve5.xls which is "after" both of the aforementioned ones and be back on track.

Now Justin (he's a really smart programmer) comes along to help them write a new spreadsheet application called Schemix that solves their issues. Schemix represents spreadsheets such that each cell value in the spreadsheet has it's own version number using version vectors.

Here's a document in Schemix

And here is how Schemix represents this data after Adam and Eve have been working on it for a while.

A1, ["Anders"],                 { adam:3, eve:4 }
B1, ["anders@somewhere.com"],   { adam:1        }
A2, ["Brandon"],                { adam:2, eve:5 }
B2, ["brandon@elsewhere.com"],  {         eve:4 }

The right-most column is the version vector timestamp for the corresponding cell. So, in stead of giving the entire document a single version, each cell in the spreadsheet has its own independent version number. Whenever Adam saves his document, the cells he has modifies will have their version number bumped up one.

This versioning scheme allows any two such Schemix documents to be merged, by comparing the cells individually using the scheme Adam and Eve were using above. Assume the aforementioned document was merged with this:

A1, ["Andy"],                   { adam:4, eve:3 }
B1, ["anders@somewhere.com"],   { adam:1        }
A2, ["Bill"],                   { adam:3, eve:5 }
B2, ["brandon@elsewhere.com"],  {         eve:4 }

Merging two Schemix documents is like assembling a jigsaw puzzle from two sets of jigsaws puzzle pieces:

For some pieces, there will be two identically versioned ones (such as cells B1 and B2) and so you just choose any one and throw the other away.
For some pieces, one is "newer" than the other (for cell A2); and so you just keep the most recent one and discard the other.
but, but, but for some there may be a conflict, and so the cell becomes multi-valued. Say, both Adam and Eve concurrently change the cell A1, but to distinct values. Then you're in trouble; but luckily much less so than before because the conflict only pertains to that single cell.

The merged document look like this:

A1, ["Andy", "Anders"],         { adam:4, eve:4 }
B1, ["anders@somewhere.com"],   { adam:1        }
A2, ["Bill"],                   { adam:3, eve:5 }
B2, ["brandon@elsewhere.com"],  {         eve:4 }

When cells are in conflict as a result of merging two Schemix documents, they are allowed to have multiple values. In Schemix, this is obviously just represented as a multi-values GUI element (a drop-down), so that once you have a merged document, you can easily edit it to resolve the conflict.

Inremental Updates

Version vectors are really nice, because you don't need entire documents to be able to do consistent merges. If Adam and Eve can see each other via a peer-to-peer channel, they can just as well send updates to each other by sending the cell values incrementally. The fact that each cell carries it's own consistency structure makes this scheme applicable to bulk- or incremental merges alike.

Relation to NoSQL

As mentioned above, this idea of version vectors is important because it is a fundamental notion underlying many of the new distributed NoSQL data stores, such as Voldemort, and Riak. The cell-names A1, B2, and so on are similar to the keys used in these systems, and the notion of version vectors described here is close to what they do. A Riak store is really just one giant version of the Schemix spreadsheet I described above.

The interesting thing is that even though they do provide automatic reconciliation, there is no guarantee about the referential integrity of the result. Two independent edits to two distinct key/values can always be merged; but they could easily break some external invariant which is not expressed explicitly.

What kinds of strategies should we then employ if we want to maintain integrity anyway, say for something simple like a one-to-may relationship?

Erlang User of the Year 2010

2010-11-19T12:09:09+01:00

At the Erlang User Conference in Stockholm, I received the thirteenth "Erlang User of the Year" award, and was presented with the traditional gift, a beautiful hand-carved Erlang logo made in wood by Kanevad in Gamla Linköping.

I have to admit that I did not even know this award existed, but I am honored to join the ranks of Chris Piro and Eugene Letuchy (Facebook chat, 2009), Damien Katz (CouchDB, 2008), John Hughes (QuickCheck, 2007), Alexey Shchepin (ejabberd, 2006), The HiPE team members 2005, Michaël Rémond (ejabberd, 2004).

The award is given by the Erlang community for technical contribution; in this case my work on Erjang - A JVM-based Erlang VM. I was quite surprised (pleasantly of course) by this since I am by no stretch an Erlang old-timer. I wrote my first line of Erlang code a little over a year ago during JAOO 2009 when Francesco Cesarini was giving an Erlang tutorial.

The Erjang project is doing really well. For many systems, Erjang is roughly twice as fast as Open Source Erlang (BEAM). Recently, we've been working on completing more of the core functionality, and we're already at a level where we can boot and run complex systems like Riak and RabbitMQ.

Since I did not really have time to prepare an acceptance speech, I'm sorry I did not get around to thanking all the people that have been supporting this project. Most importantly I should thank Erik Søe Sørensen, who was the first guy to stand up and contribute code to this lunatic project, my family (for living with my lunacy on a daily basis for a year now), and also the entire Erlang community for being surprisingly helpful and positive to this (literally) bastard project.

Once again, Thank you all!

Kresten Krab Thorup

Erjang - Interpreted Mode

2010-11-04T22:09:17+01:00

Erik has been hacking the interpreter the last few weeks, and now we're finally at a state where it is useful (though there are still some issues).

Interpreter??

Yep, now Erjang has two modes of operations.

The default is the Eager JIT mode, meaning that modules are compiled from .beam to .jar-with-class-files eagerly as they are encountered as OTP boots up. This results in relatively slower start-up time, but fast execution.
The new option ej +i lets you run Erjang with the byte-code interpreter execution mode; which starts up faster, uses less memory, but runs slower.

One effect of this can be seen from the launch time of Erjang. Look at this

prompt$ rm .erj/*   ## delete class cache
prompt$ echo 'erlang:halt().' | time ej
Eshell V5.8  (abort with ^G)
1>        13.96 real        14.45 user         1.86 sys

Wow, that took 14 seconds to launch the Erjang REPL. Now, doing the same thing again should speed things up because now the .beam files have been compiled; see here:

prompt$ echo 'erlang:halt().' | time ej
Eshell V5.8  (abort with ^G)
1>         4.67 real         4.61 user         0.29 sys

Wow! the second launch was much faster because the Eager JIT does not have to pay the price of the up-front compilation.

So, running the interpreted Erjang (notice the +i there) gives you:

prompt$ echo 'erlang:halt().' | time ej +i
Eshell V5.8  (abort with ^G)
1>         2.47 real         2.64 user         0.20 sys

Wow, its only ~55% of the execution time.

You might be puzzled why this is faster than the pre-compiled case above. The reason is that Java byte code loading is fairly slow, and that case ends up loading a lot of java code. And the Java JIT has not yet had a chance to optimize the code.

Unfortunately, running BEAM (the erl command) yields...

prompt$ echo 'erlang:halt().' | time ej +i
Eshell V5.8  (abort with ^G)
1>         0.24 real         0.11 user         0.02 sys

10 times faster! Urgh. Fortunately for most erlang systems, launch time is not significant... but still. Over time (when the Java JIT kicks in) the performance of Erjang and BEAM are currently at-par.

Memory Usage

Having the interpreter provides two new interesting possibilities. First, it brings Erjang within reach of running on an Android machine, because (a) this execution mode does not involve runtime generation of code, and (b) the memory load is much smaller. Lets try to launch mnesia and inspect memory usage. see:

First, look at an interpreted mode...

prompt$ ej +i
1> mnesia:start().
ok
2> 'java.lang.System':gc().
ok
3> erlang:system_info(allocated_areas).
[{'non_heap:CMS Perm Gen',134217728,10628584},
 {'heap:CMS Old Gen',50331648,7618216},
 {'heap:Par Survivor Space',1638400,0},
 {'heap:Par Eden Space',13500416,1790200},
 {'non_heap:Code Cache',2560000,2529664}]

Next, compiled mode...

prompt$ ej
Eshell V5.8  (abort with ^G)
1> mnesia:start().
ok
2> 'java.lang.System':gc().
ok
3> erlang:system_info(allocated_areas).
[{'non_heap:CMS Perm Gen',134217728,35051856},
 {'heap:CMS Old Gen',50331648,13346696},
 {'heap:Par Survivor Space',1638400,0},
 {'heap:Par Eden Space',13500416,416592},
 {'non_heap:Code Cache',2494464,2483520}]

To make it more readable, here is a table ...

	compiled	interpreted
Old Gen	13,346,696	7,618,216
Survivor Space	0	0
Eden Space	416,592	1,790,200
Perm Space (Java byte code)	35,051,856	10,628,584
Code Cache (native code)	2,483,520	2,529,664

With the compiled mode, memory adds up to ~55MB, in interpreted mode, ~20MB. Over time when the Java JIT kicks in, this difference is going to be even more evident.

Another interesting measure, is the memory usage before and after starting mnesia. With ej +i starting mnesia adds ~1MB total memory usage (similar to BEAM); but with compiled mode, starting mnesia adds ~9MB memory usage. So, while the baseline for a booted OTP is higher with Erjang +i than BEAM (~19MB vs ~3MB), the incremental memory usage when loading code and running is the same order of magnitude.

HotSpot Erjang

Another interesting potential would be to combine the Erjang interpreter an the Erjang JIT, so that code starts up interpreted and then if something is used "enough" it will get JIT'ed to java byte code. This is similar to how HotSpot Java does it (but is also one of the things that Oracle has patented and was recently suing Google over ...).

In such a scenario, there are some more interesting optimizations that would make sense; because if we have more information then it might well make sense to do more agressive optimizations and trade off some extra byte code generated for more speed.

Getting there...

As I hinted above, there are still issues with the interpreted mode; one is that interpreted mode uses more stack stack space; another is that there are some still some bugs lurking in there. At lease when running rabbitmq, something doesn't boot correctly. So, there is still some wat to go.

GOTO Top 20 Talks

2010-10-11T12:02:03+02:00

It's been quiet on Erjang for a while, and I've been busy with other things. Going to JavaZone two weeks ago however, got me all psyched up again on my little Erlang on the JVM project.

I met some guys from VMWare/SpringSource and we talked about RabbitMQ, so I spent some late nights these past weeks getting things working. The prospects of this? How about a SpringSource developer wanting to use RabbitMQ? Eventually, this would be a great option as an integrated part of a pure Java development environment for say, Eclipse.

It's at the point now where I can run a good deal of the unit tests, though many still fail. You can read more about the progress below.

The major improvements are

Mnesia is much more stable now
TCP/IP error handling is much improved

It's great to work specifically on something like RabbitMQ because it already has a large base of existing test cases. Further, RabbitMQ is plain erlang i.e., no NIFs or linked-in drivers, so it is a perfect candidate for Erjang.

Looking forward to demo/talk about this next week at JAOO. Feel free to follow Erjang at GitHub if you want to stay in the loop on this.

Additions/Fixes...

To get to this point, I added a number of new BIFs, and fixed various bugs. You can see the glory details in the commit log here, but here is an outline of the most important fixes/additions:

Implement erlang:hibernate which is used in gen_server2 and a lot of the other infrastructure modules that come with RabbitMQ. Hibernating is implemented as an exception which is caught at the top-level of the process so as to remove the call stack before going to sleep.
Fix a couple of issues with the tcp_inet driver. Connections shutdown procedures didn't work completely, and rabbit depends on the owner dying to close connections. Further, rabbit uses the tcp option {exit_on_close, false} to allow outgoing communication to flush before the actual tcp socket is closed, and Erjang had some issues with that too.
Improve the driver select mechanism.
Implement a few more options for the efile driver. Rabbit uses the FILE_SETOPT driver option to configure read-ahead strategies for file usage, and also depends on the integer (file descriptor) returned by FILE_OPEN.
In ETS, I had to implement a few more bif used specifically by Rabbit/Mnesia, such as ets:repair_continuation, ets:update_counter/3 (the 4-tuple variant).
Various fixes to the BEAM -> JVM compiler that I stumbled upon when running Rabbit. There were some cases where the type inference was slightly off, and I optimized the cases when erlc uses {x,1023} as a scratch register.

I still have an issue with some of the functions in io_lib being non-tail recursive, causing stack overruns. The problem is that this often happens when Erjang tries to print an error message, and so it doesn't print the reason why it dies. And in some cases, the error_logger process itself dies from a stack overrun, bringing down the entire VM.

Going forward, it looks like the issues yet-to-be-fixed are either simple bugs like variants of arguments that are not supported by my BIF implementations, and (more tricky) some cleanup issues with processes.

Stay tuned! I'll talk more about these things at JAOO next week, QCon/SF and ErlangFactory Lite LA in November, YOW! Australia in December. If you want me to come and speak please let me know.

Booting RabbitMQ on Erjang

Booting rabbit right now happens with the following command line

ej -boot /var/lib/rabbitmq/mnesia/rabbit@renaissance/plugins-scratch/rabbit \
   -pa ./ebin -name rabbit2@renaissance.local \
   -sasl sasl_error_logger '{file,"sasl.log"}'

The bootup sequence looks like this (running the latest rabbitmq 0.9.1 build from hg) on Erjang/OTP R14.

=INFO REPORT==== 29-Sep-2010::12:03:51 ===
    alarm_handler: {set,{{disk_almost_full,"/"},[]}}

=INFO REPORT==== 29-Sep-2010::12:03:51 ===
    alarm_handler: {set,{{disk_almost_full,"/Volumes/StockMeter"},[]}}

=INFO REPORT==== 29-Sep-2010::12:03:51 ===
    alarm_handler: {set,{{disk_almost_full,"/Volumes/Flash"},[]}}
|
=INFO REPORT==== 29-Sep-2010::12:03:51 ===
    alarm_handler: {set,{system_memory_high_watermark,[]}}
+---+   +---+
|   |   |   |
|   |   |   |
|   |   |   |
|   +---+   +-------+
|                   |
| RabbitMQ  +---+   |
|           |   |   |
| v%%VSN%%  +---+   |
|                   |
+-------------------+
AMQP 0-9-1 / 0-9 / 0-8
Copyright (C) 2007-2010 LShift Ltd., Cohesive Financial Technologies LLC., and Rabbit Technologies Ltd.
Licensed under the MPL.  See http://www.rabbitmq.com/

node           : rabbit2@renaissance.local
app descriptor : /Users/krab/Projects/rabbitmq-server/ebin/rabbit.app
home dir       : /Users/krab
cookie hash    : pIGTBl0W0HD2xiNguwnLoQ==
log            : tty
sasl log       : sasl.log
database dir   : /Users/krab/Projects/rabbitmq-server/Mnesia.rabbit2@renaissance.local
erlang version : 5.8

starting file handle cache server                                     ...
=INFO REPORT==== 29-Sep-2010::12:04:05 ===
Limiting to approx 10140 file handles (9124 sockets)
done
starting worker pool                                                  ...done
starting codec correctness check                                      ...done
starting database                                                     ...found mnesia running id=<2.0.592>
Sep 29, 2010 12:04:05 PM erjang.EModuleManager$FunctionInfo$1 invoke
INFO: MISSING mnesia_sup:prep_stop/1

=INFO REPORT==== 29-Sep-2010::12:04:05 ===
    application: mnesia
    exited: stopped
    type: permanent

=INFO REPORT==== 29-Sep-2010::12:04:06 ===
Process <2.0.2031> exited abnormally without links/monitors
exit reason was: shutdown
erjang.ErlangExit: shutdown
    at erjang.m.erlang.ErlProc.exit(ErlProc.java:468)
    at erjang.m.mnesia_bup.mnesia_bup.install_fallback_master__2(mnesia_bup.S:207)
    at erjang.m.mnesia_bup.mnesia_bup$FN_install_fallback_master__2.go(Unknown Source)
    at erjang.EProc.execute(EProc.java:498)
    at kilim.Task._runExecute(Task.java:400)
    at kilim.WorkerThread.run(WorkerThread.java:47)

done
-- external infrastructure ready
starting logging server                                               ...done
starting exchange type registry                                       ...done
starting exchange type direct                                         ...done
starting exchange type headers                                        ...done
starting exchange type topic                                          ...done
starting exchange type fanout                                         ...done
starting statistics event manager                                     ...done
-- kernel ready
starting guid generator                                               ...done
starting cluster delegate                                             ...done
starting alarm handler                                                ...done
starting memory monitor                                               ...done
starting node monitor                                                 ...done
-- core initialized
starting empty DB check                                               ...
=INFO REPORT==== 29-Sep-2010::12:04:07 ===
Memory limit set to 1535MB.
done
starting queue supervisor and queue recovery                          ...
=INFO REPORT==== 29-Sep-2010::12:04:07 ===
Added vhost <<"/">>

=INFO REPORT==== 29-Sep-2010::12:04:07 ===
Created user <<"guest">>

=INFO REPORT==== 29-Sep-2010::12:04:07 ===
Set user admin flag for user <<"guest">> to true

=INFO REPORT==== 29-Sep-2010::12:04:07 ===
msg_store_transient: using rabbit_msg_store_ets_index to provide index

=INFO REPORT==== 29-Sep-2010::12:04:07 ===
msg_store_persistent: using rabbit_msg_store_ets_index to provide index

=ERROR REPORT==== 29-Sep-2010::12:04:07 ===
msg_store_persistent: rebuilding indices from scratch
done
starting exchange recovery                                            ...done
-- message delivery logic ready
starting error log relay                                              ...done
starting networking                                                   ...
=INFO REPORT==== 29-Sep-2010::12:04:07 ===
started TCP Listener on 0.0.0.0:5672
done
-- network listeners available

broker running
Eshell V5.8  (abort with ^G)
(rabbit2@renaissance.local)1>

Running the tests from `rabbitmq-java-client`

And we can now run some unit tests. I've been poking around in the rabbit-java-client unit tests. Here are some screen shots...

The main tests for rabbitmq-java-client gets most of the way there, but currently dies with a bug in Erjang's ETS implementation when running the 500 producers/consumer test. Well well, can be fixed.

/com/rabbitmq/examples/TestMain.class
com.rabbitmq.examples.TestMain : javac v50.0 on 1.6.0_20
Channel 0 fully open.
Got message (4 left in q): (0) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Got message (3 left in q): (1) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Got message (2 left in q): (2) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Got message (1 left in q): (3) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Got message (0 left in q): (4) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Drained, remaining in batch = 0.
com.rabbitmq.examples.TestMain$BatchedTracingConsumer@6db3f829.handleConsumeOk(amq.ctag-jM3S9gxr4aSTUqoQC71+lA==)
com.rabbitmq.examples.TestMain$BatchedTracingConsumer@42698403.handleConsumeOk(amq.ctag-lL8JbFN2bq2oWxUgeDTuFQ==)
Async message (0,noack): (5) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (0,ack): (6) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (1,noack): (7) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (1,ack): (8) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (2,noack): (9) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (2,ack): (10) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (3,noack): (11) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (3,ack): (12) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (4,noack): (13) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Async message (4,ack): (14) On the third tone, the time will be Wed Sep 29 12:13:33 CEST 2010
Acking batch.
com.rabbitmq.examples.TestMain$BatchedTracingConsumer@6db3f829.handleCancelOk(amq.ctag-jM3S9gxr4aSTUqoQC71+lA==)
com.rabbitmq.examples.TestMain$BatchedTracingConsumer@42698403.handleCancelOk(amq.ctag-lL8JbFN2bq2oWxUgeDTuFQ==)
About to publish to topic queues
About to drain q1
Got message (2 left in q): B
Got message (1 left in q): C
Got message (0 left in q): D
Drained, remaining in batch = 7.
About to drain q2
Got message (0 left in q): C
Drained, remaining in batch = 9.
About to drain q3
Got message (1 left in q): C
Got message (0 left in q): D
Drained, remaining in batch = 8.
About to try mandatory/immediate publications
Handling return with body one
Returned: #method(reply-code=312,reply-text=NO_ROUTE,exchange=mandatoryTestExchange,routing-key=)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: one
Handling return with body two
Returned: #method(reply-code=312,reply-text=NO_ROUTE,exchange=mandatoryTestExchange,routing-key=)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: two
Handling return with body three
Returned: #method(reply-code=313,reply-text=NO_CONSUMERS,exchange=mandatoryTestExchange,routing-key=)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: three
Handling return with body four
Returned: #method(reply-code=313,reply-text=NO_CONSUMERS,exchange=mandatoryTestExchange,routing-key=)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: four
Got message (0 left in q): five
Drained, remaining in batch = 0.
Completed basic.return testing.
Got message (4 left in q): (15) On the third tone, the time will be Wed Sep 29 12:13:34 CEST 2010
Got message (3 left in q): (16) On the third tone, the time will be Wed Sep 29 12:13:34 CEST 2010
Got message (2 left in q): (17) On the third tone, the time will be Wed Sep 29 12:13:34 CEST 2010
Got message (1 left in q): (18) On the third tone, the time will be Wed Sep 29 12:13:34 CEST 2010
Got message (0 left in q): (19) On the third tone, the time will be Wed Sep 29 12:13:34 CEST 2010
Drained, remaining in batch = 0.
Handling return with body mandatory
Returned: #method(reply-code=312,reply-text=NO_ROUTE,exchange=,routing-key=bogus)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: mandatory
Handling return with body immediate
Returned: #method(reply-code=313,reply-text=NO_CONSUMERS,exchange=,routing-key=bogus)
 - props: #contentHeader(content-type=null, content-encoding=null, headers=null, delivery-mode=null, priority=null, correlation-id=null, reply-to=null, expiration=null, message-id=null, timestamp=null, type=null, user-id=null, app-id=null, cluster-id=null)
 - body: immediate
Got message (1 left in q): normal
Got message (0 left in q): mandatory
Drained, remaining in batch = 8.
Closing.
Leaving TestMain.run().
WON'T write statistics.
WILL use server-side auto-acking.

Java to the Limit

How Could it go so Bad?

What Happened?

What should be done?

What’s Next?

Conclusions

Consistency Eventualis

Erlang is not a Concurrent Functional Programming Language

Vector Maps

Assignments as Vector Clocked Events

Conflict happens

Deleting values

Defining Reconciliation

What is this good for?

Use case: Modeling Relationships in MVCC data stores

Use case: off-line data

Implementation Issues

Conclusions

About Version Vectors (a.k.a. Vector Clocks)

Versions of shared spreadsheets

Assembling the Jigsaw

Inremental Updates

Relation to NoSQL

Erlang User of the Year 2010

Erjang - Interpreted Mode

Interpreter??

Memory Usage

HotSpot Erjang

Getting there...

GOTO Top 20 Talks

Additions/Fixes...

Booting RabbitMQ on Erjang

Running the tests from rabbitmq-java-client

Running the tests from `rabbitmq-java-client`