Some distributed computing news: cuddly elephans, pigs, nymphs and couch computing

As I did some distributed computing research in my previous life, and then tried to get involved with Google, I'm still somehow interested in the subject. If you are into distributed computing, you'd know that Google is using a distributed C++ system called MapReduce* for indexing of the crawled webpages. It happens that there's an open-source Java implemenation of Google's system (based on published Google's research papers) called Hadoop . Up to now I didn't know about any serious usage of Hadoop in big distributed systems, but as it comes, I learned that Yahoo! is using Hadoop internally** for spam detection!

Yahoo's researchers have also designed a new language called PIG Latin (?!)*** for distributed programming on the Hadoop platform. The idea is rather an interesting one: they pointed out that the existing way of writing programs for the mapper and reducer part of a distributed application is too low-level and not reusable, but somehow familiar to programmers. In contrast, a declarative language like SQL poses some problems, so the paradigm there is completely diffrent:

At the same time, the transformations carried out in each step are fairly high-level, e.g.,filltering, grouping, and aggregation, much like in SQL. The use of such high-level primitives renders low-level manipulations (as required in map-reduce) unnecessary.
...
To experienced system programmers, this method is much more appealing than encoding their task as an SQL query, and then coercing the system to choose the desired plan through optimizer hints.

So it provides a middle ground, where we can avoid SQL and write down the computation steps, but can do that at higher level!

Unsuprisingly, Microsoft already has a proprietary distributed computing platform called Dryad, which tries to do something like this as well, but is using C# and LINQ (i.e. an SQL-like query language):

DryadLINQ generates Dryad computations from the LINQ Language-Integrated Query extensions to C#.

But I don't know how much this is a research project and if it's really used internally. On the other side, Microsoft recently aquired a search company called Powerset, which is using Hadoop at its core, and as the gossip runs, should be used to bring Microsoft's LiveSearch up to speed.

Facebook, in their turn, are using Hadoop, but added a Business Intelligence tool called Hive (now released as open source!) on top of it. It uses an SQL-like query language, as BI-users understand it best. Beneath the surface Hive leverages Hadoop and translates SQL-like imperatives into MapReduce jobs.


Not bad, cuddly elephant! It seems everyone is loving you!


Accidentally, when speaking about SQL and non-SQL: there's a non-SQL database by Apache called Couch DB. It is written in Erlang (we reported already**** ;-)) and implements a distributed document database. It's designed for lock-free concurrency using Erlang's "share-nothing" philosophy. To my mind it resembles Linus' Thorvalds git source configuration system, as it holds all the versions of documents determining the "winner" to be visible in defined views. Hear, hear! Erlang's alive, distributing and kicking!

Another thing worth noticing is that's not only SQL anymore, there are attempts to do things differently, athough others are sticking with the ol 'n reliable. Paradigm change on its way? It's interesting times I think.

PS (6 Okt. 2009): Look, look, now even the Big Blue has jumped the wagon too! They offer the M2 enterprise data analysis platform, based on Hadoop and using PIG. See: http://www.sdtimes.com/link/33808. So it seems Hadoop is definitely mainstream and business analyst thingie now, and as such it has lost much of its appeal, as far as I'm concerned.

---
* Jeffrey Dean, Sanjay Ghemawat: "MapReduce: Simplified Data Processing on Large Clusters", OSDI 2004, http://labs.google.com/papers/mapreduce.html
** unfortunately it's a two-parts video: http://developer.yahoo.net/blogs/hadoop/2009/03/using_hadoop_to_fight_spam_-_part_1.html
*** Christopher Olston et al: "Pig Latin: A Not-So-Foreign Language for Data Processing", SIGMOD 2008, http://www.cs.cmu.edu/~olston/publications/sigmod08.pdf
**** http://ib-krajewski.blogspot.com/2007/08/erlangs-change-of-fortunes.html

Erlang and Map-Reduce

I was a fan of Google's Map-Reduce for a quite long time, as I was first doing my PhD research in distributed systems and then was working in some high-availability projects, so such interest emerged somehow naturally.

Their (i.e. Google's) achievements quite impressed me: first the whole infrastructure (lot of C++ coding - they simple wrote their own filesystem and database!!!), but equally the level of abstraction used when working with distributed data. I wrote about the superiority of that model over the SOA model before, although the SOA model is probably the best you can achieve in a heterogenous environment (and I was probably wrong there...).

So every time I see a map-reduce implementation I can't help reading about it: Hadoop is the most known open source implementation, but there's the QtConcurrent::mappedReduced algorithm in the new Qt 4.5* as well. You see, the idea seems to be catching on.

Now to the news: there is a Map-Reduce implementation in Erlang (!!!)** which runs Python scripts (!!!) and it's called Disco***! And if you don't have a massive parallel cluster at home, you can run it in the Amazon's Elastic Computing Cloud! I don't like Nokia very much, but I must admit that this one is rather cool: you simply write scripts to manipulate your data, much in the vein of UNIX shell programming, only infinitely scalable! And we know that scripting languages are much better for data manipulations than Java or C++. According to its homepage, Disco is quite a success too:

This far Disco has been succesfully used, for instance, in parsing and reformatting data, data clustering, probabilistic modelling, data mining, full-text indexing, and log analysis with hundreds of gigabytes of real-world data. ***

Wow! I like te idea of Erlang and Python working unisono!

---
* Qt 4.5 docs: http://doc.trolltech.com/main-snapshot/threads.html#qtconcurrent
** a small itroduction to Erlang: http://ib-krajewski.blogspot.com/2007/08/erlangs-change-of-fortunes.html
*** Disco's homepage: http://discoproject.org/

Web Services, SOA, and the (r)REST

OK, it's time to talk about SOAP and web-services (and many other things ;-). Why now? Well, I want to write about it before I start reading Nicolai Josuttis' book about SOA, just to record my current (and possibly superficious) impressions.

Beacause Nicolai is known to me as author of fine C++ books, I expect rather much from this one, and suspect that its lecture will shutter some of my safe and secure beliefs. If thad be so, I'l write a new blog to restore the honour of SOAP. But now, ad rem! Down to business!

I remember as a couple of years ago I was receiving one email after another: new SOAP-based protocol A invented, new SOAP-based protocol B approved, new SOAP-based protocol C proposed. And I was wondering - why are the people inventing the wheel for the n-th time afte RPC, DCE and CORBA? Why so much protocols? One is daunted by the sheer number of needed specs, regulative bodies, and documents. Wasn't is supposed to be about simplicity? It's Web! Here I'll cite my first source - "Dave Podnar’s 5 Stages of Dealing with Web Services"*:

1. Denial - It's Simple Object Access Protocol, right?
2. Over Involvement - OK, I'll read the SOAP, WSDL, WS-I BP, JAX-RPC, SAAJ, JAX-P,... specs. next,I'll check the Wiki and finally follow an example showing service and client sides.
3. Anger - I can't believe those #$%&*@s made it so difficult!
4. Guilt - Everyone is using Web Services, it must be me, I must be missing something.
5. Acceptance - It is what it is, Web Services aren't simple or easy.

So, at it seems it was about simplicity in the beginnings,and then it got more and more complicated. Why? As a SOAP book author** said: "Web Services are hard because they are a form of distributed computing and distributed computing is just about the hardest problem in computer science"!

Well, of course it's about distributed computing, but let me make my point here: web-services are got so complicated because they are too low-level a model of distributed computing! SOAP is basically RPC done with XML, and PRC deals with location-transparent procedure calls. This paradigm never had a lot of success - look at the demise of IIOP and RMI - because it's too fine-grained. Compare this remote call model to other model of distrinuted computing - Google's Map-Reduce system (to my mind the most successful distributed computing system today)***. It works at totally different level: it's about gathering and transforming information in a distributed manner, hiding away details like remote calls and node failures!

Now enter REST (representational state transfer)****, one another model for distributed computing. Let's explain it to those of you doing embedded programming or databases: REST is the principle the Internet is acting upon. There is a set of ressources which we can acces using URL's, i.e. only knowing their location. So, instead of using UDDI+WSDL+SOAP we just send:

• an HTTP GET request for an URI like: www.marek-here.de/mareks_blog?title=first%20blog
• or, as Ruby on Rails uses it: : www.marek-here.de/mareks_blog/1
• or a POST with: www.marek-here.de/mareks_blog?&title=new%20post&text=bla%20bla%20bla

and we'll get the data (usually XML) in response, or we'll create a new blog entry. Simple? Yes, it is! Compare it to the 5 stages of web services!

Well, one must admit, there's a lot of public SOAP interfaces in the Web at the moment: look at Google's and Yahoo's maps, Amazon's bookstore and Ebay auctions. But these interfaces are increasingly perceived as old-fashioned, because RESTful services scale better and are simpler to use. For example Google discontinued its SOAP-based search API and is rumored to be striving to get away from SOAP-based APIs entirely. As for Yahoo and Amazon, which offer SOAP and REST based API in parallel, 85% of their users allegedly choose REST.

It is perhaps a good place now for some well-known citation. It has aleady made its round over the Web, but I'll use it here nevertheless, as it is simultaneously fun and instructive*****:

"WS-* is North Korea and REST is South Korea. While REST will go on to become an economic powerhouse with steadily increasing standards of living for all its citizens, WS-* is doomed to sixty years of starvation, poverty, tyranny, and defections until it eventually collapses from its own fundamental inadequacies and is absorbed into the more sensible policies of its neighbor to the South.

The analogy isn’t as silly as it sounds either. North Korean/Soviet style “communism” fails because it believes massive central planning works better than the individual decisions of millions of economic actors. WS-* fails because it believes massive central planning works better than the individual decisions of millions of web sites."

Let me close this post with a little story. At the BEA's Arch2Arch Summit in Frankfurt, Germany, this summer I attended the panel discussion about SOA with some of high-level BEA people. BEA is a middleware company, Java-centric and very much into web-services. Of of the questions at the panel discussion was the simple and succint: "Why do you think SOA is so good?". The answer of the president of the German subsidiary was: "Because it's about customer orientation!". The answer of BEA's chief architect was: "Because there's no programming language binding (as in CORBA) - the protocol is language-neutral!".
After hearing that I asked myself: is that something really new? Isn't industry repeating itself? It was the same feeling I described at the start of this post, when I heard about new SOAP protocols: are the people trying to solve something, or to generate more buzz and revenues? But my gut feeling may be wrong - admittedly SOAP is too low level as an abstraction, but SOA is building a layer on top of it. On the other hand SOA is normally implemented using SOAP. So SOA=SOAP=WS* in the end? And why is corporate world loving it? Is it doomed to failure like North Corea? Could we do SOA with RESTful services?

PS: I updated my August-07 "iPhone Presentation" post. After I've read Nicolai's book, I'll probably update this one too.

---
* see http://rmh.blogs.com/weblog/2006/04/dave_podnars_5_.html and discussion http://www.theserverside.com/news/thread.tss?thread_id=40064
** books homepage (http://soabook.com/), and excerpt http://soabook.com/blog/?p=5
*** for example see the presentation: "Using mapreduce on Large Geographic Datasets (Barry Brumitt, Google)", http://video.google.com/videoplay?docid=6202268628085731280 "
**** defined in Roy Fielding's dissertation: "Architectural Styles and the Design of Network based Software Architectures, 2000", www.ics.uci.edu/~fielding/pubs/dissertation/top.htm
***** see here for the post and discussion: http://cafe.elharo.com/xml/north-and-south/

Erlang's change of fortunes

Today morning I had a conversation with my distinguished colleague Stefan Z. while hanging out at the coffee-vending machine in the tea-kitchen at our client's office. As we are both working for the telecom industry, we came to discuss Erlang. No, not that celebrated guy, but a rather obscure programming language designed at the Ericsson Corporation.

For the fun of it, let's first look at some snippets of Erlang code!

define a data structure:

  Student={person,{name,{first,yakkety},{last,yak}},{footsize,1}}.

access a member of data struct (by pattern matching, cool!!!):

  {_,{_,{_,HisName},_},_} = Student.

printing yakkety:

  io:fwrite("his name is: ~w~n", [HisName]).

define a list:

  Fruits = [{apples,10},{pears,6},{prunes,3}].

append something to a list:

  Fruits1 = [{oranges,4},{lemons,1}  Fruits].

get the head of the list (by pattern matching, cool!!!):

  [ListHeadFruits2] = Fruits1.

simple function:

  incr(Num) -> Num + 1.

recursive function:

  fac(0) -> 1;
  fac(Num) when Nun > 0 -> N * fac(Num-1).

infinite loop receiving messages (by pattern matching, cool!!!) and sending responses back (by the !operator):

  loop() ->
      receive
          {From, {request, Param1, Param2}} ->
              From ! {self(), Param1 + Param2},
              loop();
       end.

a foreach loop (note the lambda function definition between fun and end!):

  extract2ndElements(List) ->
      lists:map(fun({_,Second}) -> Second end, List).

Ok, it was fun, but we mustn't digress too much...

Erlang in itself is rather a paradox: you normally associate Telco equipment programming with the lowest of the lowest: asm, C99 or EC++ (castrated C++). Now, there come some guys in the 80-ties and to the corporate management they can sell a functional language for this task! This alone is incredible! But wait, there's more! Up to now Erlang was a niche language used quite exclusively at Ericsson. Now this seems to be changing. But first we need some history.

In the 80-ties Erlag was designed to be slow but reliable. This is due to the very nature of the functional languages: you don't have shared state, no side effects, all data is copied between functions. For safety's sake even the variables can be assigned only once! If you apply that to parallel computing, you don't have to worry about synchronization and critical sections - the "share nothing semantics". But it will be rather slow. In this case it was a deliberate decision: they wanted not simply a reliable language, but a "highly reliable language"! And a distributed one. So to speak a natural fit for the Telco environment. As an example: the AXD301 switch achieved the incredible 99,9999999% realiability! It's 9 nines availability! And we were struggling to achieve 5 nines* availability with C++ on CarrierGrade, High Avalability (HA) Linux and a custom HA-middelware platform in my last project! By the way, the AXD301 software has 1.7 million lines of Erlang, making it the largest functional program ever written**! Really impressive stuff IMHO.

I guess you have read (or heard about) Herb Sutter's article titled "The free lunch is over"***. So you know that the "next big thing" in software is supposed to be multicore scalability. So hear up now: as the multicores are comming pretty cheap now, Erlang can be at last both fast and reliable as it can be easily distributed on several cores! It's definitely good news! We've seen the incredible reliability which can be achieved, and have a natural programming model for distributed computation. Why? In short, as there is no shared data:

1. programs are easily distributable,


2. easily made fault tolerant by composing them from worker and observer processes,


3. easily made scalable (because of 1. we simply add more processors).**

So could distributed computing be the saviour of the functional programming? Think about Google's MapReduce!

---
* For those not working with HA systems:

      Availability%   Downtime per year
      99.9999            30 seconds !!!!
      99.999              5 minutes
      99.99                50 minutes
      99.9                  9 hours

** says Phillip Wadler: http://wadler.blogspot.com/2005/05/concurrency-oriented-programming-in.html

*** on DDJ or www.gotw.ca/publications/concurrency-ddj.htm