Carl Hewitt, the inventor of the Actor model has a blog.
Tag Archive for 'concurrency'
One of the most visible presentations from last weeks RailsConf was Avi Bryant’s demonstration of MagLev, which is a RubyVM that is based on Gemstone’s S/64 VM for Smalltalk. This caused a stir because the micro benchmark performance of MagLev looks really good because S/64 has been out in production for a while and because it appears to have some really interesting features (an OODB, shared VM’s, etc). MagLev is a reminder that the world of production quality, high-performance virtual machines is bigger than many of us remember at times.
I believe that over the next few years we will see a flourishing of virtual machines, as well as languages atop existing virtual machines. Take for example Reia, a Ruby/Pythonesque experiment atop Erlang’s BEAM VM. As we return to a multi language world, we will also necessarily return to a multiple implementation world. Before Java, there were many languages and many implementations of those languages. You could argue that there were probably too many, and I think that’s probably true. I would argue that we need to enter a new period of language and runtime experimentation. A big driver, but not the only driver, for this is the approaching multi-core world. When you don’t know how to solve something, more attempts at solutions is better.
Joe Armstrong wrote a paper for last year’s HOPL-III conference on the history of Erlang. For some reason, I didn’t get a paper copy of those proceedings, and was too busy to notice their absence. Fortunately Lambda the Ultimate picked it up and supplied links to the paper and the accompanying presentation. Digging into the history of something like Erlang is always fascinating, and Armstrong has done a good job of explaining how Erlang came to be.
Here are a bunch of quotes on topics that I found interesting. I’ve grouped them into categories, but searching the PDF of the paper shouldn’t be hard if you want to know where they originated.
Sources of inspiration
Those familiar with Prolog will not find it at all surprising that Erlang has its roots in Prolog (mostly due to implementation reasons). What I did find interesting was the origin/history/viewpoint on the concurrency model
The explanations of what Erlang was have changed with time:
1. 1986 – Erlang is a declarative language with added concurrency.
2. 1995 – Erlang is a functional language with added concurrency.
3. 2005 – Erlang is a concurrent language consisting of communicating components where the components are written in a functional language.
…
Today we emphasize the concurrency.
Note that the word actor never appears in those descriptions. Indeed, the word actor does not appear in the paper at all. So for all the discussion about Erlang’s usage of the actor model, it appears that the Erlang folks independently duplicated many of the ideas for Hewitt’s Actors. I think that is kind of interesting.
Lisp and Smalltalk are cited as inspirations, but more for the implementation of the runtime than for any features in the language. I came away from the paper with the impression that Armstrong and his colleagues are not paradigm ideologues. They are trying to get the job done.
Reliability
There is a huge emphasis on reliability throughout the paper, supporting Steve Vinoski’s remarks about Erlang. I’l just include a series of quotes, which you can interpret as you see fit:
Erlang was designed for writing concurrent programs that “run forever”
At an early stage we rejected any ideas of sharing resources between processes because of the difficulty of error handling. In many circumstances, error recovery is impossible if part of the data needed to perform the error recovery is located on a remote machine and if that remote machine has crashed.
In order to make systems reliable, we have to accept the extra cost of copying data structures between processes and always make sure that processes have enough data to continue by themselves if other processes crash
The key observation here is to note that the error-handling mechanisms were designed for building fault-tolerant systems, and not merely for protecting from program exceptions. You cannot build a fault-tolerant system if you only have one computer. The minimal configuration for a fault-tolerant system has two computers. These must be configured so that both observe each other. If one of the computers crashes, then the other computer must take over whatever the first computer was doing.
This means that the model for error handling is based on the idea of two computers that observe each other. Error detection and recovery is performed on the remote computer and not on the local computer.
Links in Erlang are provided to control error propagation paths for errors between processes.
It was about this time that we realized very clearly that shared data structures in a distributed system have terrible properties in the presence of failures. If a data structure is shared by two physical nodes and if one node fails, then failure recovery is often im-possible. The reason why Erlang shares no data structures and uses pure copying message passing is to sidestep all the nasty problems of figuring out what to replicate and how to cope with failures in a distributed system.
In our world, we were worried by software failures where replication does not help.
Design criteria
Here are some quotes related the design criteria for Erlang.
Changing code on the fly was an initial key requirement
the notion that three properties of a programming language were central to the efficient operation of a concurrent language or operating system. These were:
1) the time to create a process
2) the time to perform a context switch between two different processes
3) the time to copy a message between two processes
The performance of any highly-concurrent system is dominated by these three times.
One of the earliest design decisions in Erlang was to use a form of buffering selective receive
Pipes were rejected in favor of messages
In the concurrent logic programming languages, concurrency is implicit and extremely fine-grained. By comparison Erlang has explicit concurrency (via processes) and the processes are coarse-grained.
The final strategy we adopted after experimenting with many different strategies was to use per-process stop-and-copy GC. The idea was that if we have many thousands of small processes then the time taken to garbage collect any individual process will be small.
…
Current systems run with tens to hundreds of thousands of processes and it seems that when you have such large numbers of processes, the effects of GC in an individual process are insignificant.
The BEAM compiler compiled Erlang programs to BEAM instructions.
On functionalness
This next series of quotes will probably make the pure functional language people shake their heads, but i think that it’s important to understand Erlang in contrast with pure functional languages.
Erlang is not a strict side-effect-free functional language but a concurrent language where what happens inside a process is described by a simple functional language.
Behaviors in Erlang can be thought of as parameterizable higher-order parallel processes.
… the status of Erlang as a fully fledged member of the functional family is dubious. Erlang programs are not referentially transparent and there is no system for static type analysis of Erlang programs. Nor is it relational language. Sequential Erlang has a pure functional subset, but nobody can force the programmer to use this subset; indeed, there are often good reasons for not using it.
An Erlang system can be thought of as a communicating network of black boxes.
In the Erlang case, the language inside the black box just happens to be a small and rather easy to use functional language, which is more or less a historical accident caused by the implementation techniques used.
History and Usage
One thing that I was looking for in the paper was more details on how long Erlang had been around (besides before Java), how big the largest programs/systems were, and so forth. Here is what I found.
This history spans a twenty-year period…
(The history starts in 1986)
The largest ever system built in Erlang was the AXD301. At the time of writing, this system has 2.6 millions lines of Erlang code.
…
The AXD301 is written using distributed Erlang. It runs on a cluster using pairs of processors and is scalable up to 16 pairs of processors.
…
In the analysis of the AXD reported in [7], the AXD used 20 supervision trees, 122 client-server models, 36 event loggers and10 finite-state machines. All of this was programmed by a team of 60 programmers.
…
As regards reliability, the AXD301 has an observed nine-nines reliability [7]—and a four-fold increase in productivity was observed for the development process [31].
The AXD 301 is circa 1998.
Perhaps the most exciting modern development is Erlang for multicore CPUs. In August 2006 the OTP group released Erlang for an SMP.
This corroborates something that David Pollak told me at the RedMonk unconference during CommunityOne, namely that SMP support in Erlang had not been there very long. Of course, Erlang was running on systems with 16 physical (pairs, no less) of processings in a distributed environment. So while the runtime might not be that mature on SMP, the overall runtime for concurrency is probably a bit more mature than that. Nonetheless, worthwhile to know the precise facts.
All in all, I found the paper to be a very worthwhile read - (and a nice change from my usual intake of blog posts and tweets). One of my pet peeves about the computer business is the lack of awareness of the history of the field. At least I’ve removed a bit of my own ignorance as relates to Erlang.
Over the last week or two there’s been a bit of commotion with various parties in the blogosphere making the case for Scala against Erlang or for Erlang against Scala. Here’s a see spot run summary of the main writers and their positions / content:
Ted Neward (1, 2) - Ted (how confusing) is in the Scala camp, and thinks that the library approach of Scala’s actor library is preferable to Erlang’s VM (BEAM). He cites managability as a major concern. He also thinks that adapting a process style model into the JVM would be easier than adding SNMP monitoring to BEAM. The length of the Barcelona project bibliography suggests otherwise, but we’ll never know unless some brave soul goes and tries to do this. Fortunately, the JDK is open source now. One has to wonder whether such a change could make its way through the JCP, though. Unfortunately for Ted, I found that many of his arguments were weakened by his lack of knowledge about Erlang.
Steve Vinoski (1, 2, 3) - Steve’s articles are more about the reliability aspects of Erlang, and he’s mostly trying to correct Ted’s facts on Erlang. He thinks that Erlang had proven its reliability chops by running for years non-stop. Given the frequency with which Java app servers need to be (or are) bounced, this doesn’t seem that incredible to me.
Patrick Logan (1, 2, 3) - Patrick piled on after Steve and has spent most of his writing trying to correct/challenge Ted’s assertions about Erlang. Patrick thinks that the conventional (i.e. JVM and CLR) runtimes will have problems implementing an Erlang style shared-nothing model, since the pre-existing libraries for those runtimes are not engineered in a shared-nothing manner.
Barry Kelly was an observer of the Neward-Vinosk-Logan discussion, and added some commentary on the impact of VM primitives on things like lift. This is a point which resonates with me, because it seems to me that both languages and language runtimes will need some work to meet the challenges of large scale multicore computing.
Yariv Sadan has done a pile of stuff in Erlang, and supplied his own summary of the differences between Scala and Erlang. There is a very informative exchange between Yariv and lift author David Pollak in the comments of this one.
That’s the short rundown. This is a very interesting problem space — before I turned into database programming language guy in graduate school, I was angling to be a concurrent programming language guy. Along the way to that I got pretty good doses of functional and logic programming, as well as actor programming. That work was in the context of people planning to build (for the day) highly concurrent computers, on the order of 1000’s of processors. Today, multicore hardware is not quite up to that level, but it is approaching it pretty quickly. If there is any force in computing that is likely to precipitate the need for a new programming ecosystem (language, runtime, libraries), I think concurrent programming is it. I also think there is just not enough experience with this problem to have a real sense of what is really going to work. Cliff Click and Brian Goetz were right when they said that we just don’t have a good programming model for this stuff. Absent a model, I don’t know how we can think that we really understand what the runtime needs to deliver.
I stayed around in San Francisco for one more day after JavaOne, in order to attend the Scala liftoff. The liftoff was an open space style conference (which has a more specific meaning than “unconference”, at least to me). My friend Kaliya Hamlin did a great job of facilitating the day.
Scala has steadily been gaining attention, and hasn’t yet hit (at least in my eyes) the hype part of the classic Gartner hype cycle. I’ve been poking about with Scala, mostly because of the type inferencing, the Actor library, and lift. I have great respect for the work that Martin Odersky has done over the years, which also has me interested. Couple that with what I learned about closures in Java at JavaOne, and the list of reasons to look more deeply at Scala is getting long, especially if you are determined to have a statically typed languages.
I wasn’t able to make it to any of sessions on lift. It just worked out that other sessions overlapped them in a pathological way. While this is unfortunate, I am sure that I’ll be able to pick up anything that I need from the mailing lists and other documentation. I was able to attend two sessions on actors. One of the sessions had people with questions about actors, but no Scala actor experts were in that group. There was some discussion of Pi-calculus and the join calculus, but no discussion of the actual actor theory.
Steve Yen’s session on actor-d was pretty useful. Steve set out to build a version of memcached using Scala’s actors. He spent most of his slot talking about Scala/Java isms that he ran into - this was important since he was comparing to the C memcached. By the time he got to the actor related stuff, he was almost out of time. Steve found that he had to remove actors from the main loop of his server in order to get sufficient performance. He wanted to get statistics from the server in the background and discovered that he main loop actor was always processing messages and was never idle long enough to report statistics. He ended up replacing the actor with plain old Java Threads (POJT?). This was in addition to all the fact that he ran into many of the standard Java problems as well. I’m not sure what to conclude from this. I don’t recall what kind of hardware he was on, and I am not convinced that he had the right architecture for an actor based system. Some of his experience also seemed contrary to what the lift folks have been claiming. I think that we are in for a decent amount of investigation here. One of Martin’s statements about Scala is that it is possible (and better) to extend the language via libraries than via actual language constructs. For the most part, I agree with this, but there are certain extensions which have interactions with the runtime - like concurrency. In those cases, I don’t see how the library approach allows taking advantage of runtime features. The current version of Scala actors is implemented as a library.
One of the things that I am currently working on is support for Python in NetBeans, so I dropped into the session on IDE support for Scala. With the exception of IntelliJ, none of the IDE plugin principals were present, so it was hard to have a really productive discussion. Martin did attend the session and we talked about the possibiliy of getting hooks into the existing Scala compiler, particularly the parser and the type inferencer. That could yield some big dividends for people working on IDE support. One IDE feature that I would like to see is the ability to hit a key, and have the IDE “light up” all the inferred types, overlaid on the existing program code. This would allow developers to see if their intuition about the types actually matched that of the type inferencer. I’d like a feature like this for Python/Ruby/Groovy/Javascript code as well. Further discussion was deferred to the scala-tools mailing list.
The other session that I participated in was the session on Scala community and governance. Several people wondered about this during Kaliya’s “What questions do you have about Scala” portion of the schedule building. When nobody else put up a session in this area, I grabbed a slot, hoping to spur some conversation - if for no other reason than my own education. Fortunately, Martin had already been thinking about the problem. He is going to adopt a Python style governance, with him (and EPFL) having the final say on language design matters. There will be Scala Enhancement Proposals (SEPs), like the Python PEPs. I’m very happy with this. I think that Python has done very well at maintaining the balance between (lots) of community input on the language design, while still retaining that “quality without a name”. One of the things that I said during the CommunityOne general session panel was that particular individuals in the right place, at the right time, matter at great deal. After watching Martin for the day, and seeing his interactions on the mailing list over the last few months, I think that the design of Scala is in very good hands.
We also talked about the evolution of the Scala libraries. The Scalax project is working to build a set of utility libraries for Scala. Martin views scalax as a place where anyone can submit a library, have it tested, vetted, reworked, etc. Eventually some code in scalax would be candidates for addition to the Scala standard libraries. This also seems like a sane approach to me. I like the idea of having a place for libraries to shakeout before going into the standard libraries. Martin also mentioned a LINQ in Scala project. I need to track that one down too.
It is good to be in a multi-language world again. There’s room for Scala, Python, Ruby, and others. Another language that I am keeping my eye on is Newspeak.
Jay Nelson, in the comments to Damien Katz’s Lisp as Blub:
The two relevant issues are system granularity and garbage collector behavior (if it is related to memory and garbage collection).
Erlang encourages an architecture of many small-granularity processes. To the extent that this approach is followed, failures are localized. It is possible to do this with other languages, but erlang does encourage the approach more so than other languages.
The other difference is that erlang uses a single-threaded garbage collector per process. This makes the garbage collection process simpler, more finely grained and distributed. Smaller processes mean less complicated memory structures, and thus the language encourages a simpler model with localized garbage collection failure. Determining the cause of overburdened memory usage (or any other resource because of the localized nature of small processes) becomes easier.
An erlang system can get wedged, but following the principle of many small processes makes it less likely to happen than in other languages which encourage large processes with shared memory structures.
It strikes me that this is a sort of CGI’ish view of the world (well except for the garbage collector). CGI scripts run, use (non-shared) resources, release them all and die. The entire post and comment thread is worth some pondering.
Matt Croydon Didn’t agree with my commentary on the Erlang community, and he’s partially right. I shouldn’t have said “we need a community” because there is an Erlang community, and I knew that. I have never been a fan of Java, and I don’t want to be stuck using the moral equivalent of Java when the multicore/concurrency thing shakes out. So if I want to be able to use Erlang (and I’ve not totally made that decision), then it needs to have a bigger, more diverse, and easier to find community.
Sam Ruby is writing about Russell Beattie writing about Java and Erlang.
Russell thinks Java needs an overhaul. I think that Java has reached the point where technical, community, and business forces well exert pressure on the language to evolve in a uniformly bad manner.
Russell wrote:
The reason people are looking at Erlang is not because its beautiful syntax, great documentation, or up-to-date libraries. Trust me. It’s because the Erlang VM can run for long periods of time, scaling linearly across cores or processors filling the same niche that Java does right now on the server.
Actually, I am looking at Erlang as a solution for anywhere, (including the client) where concurrency will be an issue. By the way, it is not VM’s that scale linearly, but computational problems. And there are some problems which just can’t scale linearly, no matter what VM we put them on.
Sam goes on to make the point which is the title of this post.
Next, to dispel a few myths. Slashdot is written in Perl, seems to handle the load, and also seems to stay up. While there are a number of BitTorrent implementations, the original and (to the best of my knowledge) the most pervasive version is written in Python. Yahoo is a mix, but a good portion of it is written in PHP, with critical functions written in C. Twitter is written in Ruby, had early scalability issues, but seems to be past them. These are all examples of massively scalable applications.
Scalability is not the same thing as concurrency. It is certainly possible to scale a program written in any language - that’s a given. Especially when scaling = throwing more hardware at it. But there’s got to be a better way of doing it. Question is whether the better way is worth the price of admission.
But as far as Erlang vs Java, the real kicker is here:
Unlike the CLR which was designed to be multi-language, and unlike the JVM which is in the process of being repurposed to be multi-language also, Erlang’s VM is designed from the ground up assuming that objects typically are immutable and serializable.
Which is what makes the situation with Java so bad. Not only is the language bad, the VM is fatally flawed when it comes to actor style concurrency (which is why for all its niceties, Scala will suffer the same problems as Java). There’s a real problem here — ask yourself why there is a market for these things, if all that is needed is to throw even more boxes at the problem.
In the comments, Sam wrote;
The biggest problem I have with Erlang is clearly an addressable one: the documentation of the libraries, and the lack of good samples that can be quickly found by Google/MSN-Live/Yahoo!/Ask searches. And many of the libraries appear to be abandoned at 0.n versions.
This is actually 2 problems. There’s the issue with the libraries, and there’s the issue with the community that did/didn’t produce the libraries. We don’t just need a technology, we need a community. Hmm, Erlang lab, anyone?
Our reading group on Bainbridge Island has been working its way through Programming Erlang. Actually we’re technically not done yet, but since I spent a fair amount of time on the ferry recently, I went ahead and finished it off. There’s been quite a bit of writing about Erlang recently, and I wanted to at least have finished the book before jumping in. Looking at Joe Armstrong’s PhD thesis is probably soonish on my list too.
Basics
Erlang is a functional language which incorporates a concurrency model based on very lightweight processes communicating via messages. I’ll cover the concurrency model a bit more below. Since many people have not really been exposed to functional programming, there are things in Erlang which seem odd when compared to more mainstream languages. In addition, Erlang relies heavily on pattern matching as a flow of control construct, and it takes some time to get used to it. Some people liken the pattern matching aspects of Erlang to Prolog, but this is not entirely accurate because Prolog uses unification, which works in “both directions” and not pattern matching, which only works in “one direction”. I can’t say that I care for the syntax of Erlang, but after using Python, there are very few syntaxes that I really like. Erlang supports higher order functions, so closure based control flow structures are included. There is a fairly usual set of basic data types which are provided. Probably the biggest problem with the basics of Erlang is the way that strings are handled. In reality there are no strings in Erlang, and strings are just lists of integers. More on that below.
Concurrency
Much of the current interest in Erlang is due to its concurrent programming capabilities. The foundations of these capabilities are the availability of processes at the language level. Erlang allows a programmer to create and destroy processes quickly and cheaply (in terms of resources). Processes can only communicate with each other by sending each other unidirectional messages. Every process has a mailbox, which is where messages for it are delivered. The messages are queued there until the process explicitly “receives” them.
The code that implements a process typically consists of a tail recursive loop which explicitly “receives” messages and uses pattern matching to examine the messages and dispatch to the correct behavior. Replying to the sender of a message must be handled by the programmer, but it is easy to code up simple rpc style message passing. Two (or more) processes can be linked to each other so that when one process dies, the other is sent a signal. The preferred mode of handling errors in processes is to kill them and restart them. This signaling forms the basis of the supervision tree concept in OTP. The basic concurrency model of Erlang is a version of the Actor model developed by Carl Hewitt at MIT. I took Hewitt’s class while I was an undergraduate, so the concepts were familiar to me. Erlang is relatively blind to where a process might be running - in the same VM, in a different hardware thread on the same VM, or on a VM on different computer altogether. This makes it easy to write programs that can grow easily when you want to add hardware, whether that is processors or computers.
OTP/Mnesia/ETS/DETS
The folks at Ericsson have also provided a bunch of libraries to raise the level of abstraction for concurrent programming in Erlang. There are 3 major libraries. OTP (Open Telecom Platform) helps a programmer to write scalable, fault-tolerant code. It takes advantage of Erlang’s hot code update facilities to allow processes to be upgraded in place. The basic abstractions to do this are very simple to work with. OTP includes the notion of supervision trees, which is an abstraction for managing networks of processes.
Mnesia is a (potentially) distributed database written in Erlang. It provides an easy mechanism for storing Erlang terms. While it is not an RDBMS, it does provide a query mechanism based on list comprehensions. It also supports transactional behavior and has the ability to duplicate Erlang tables on other machines
Runtime
One thing that isn’t discussed enough are the features of the Erlang runtime/VM. The runtime is very efficient at managing processes, much more so that languages like Python, Ruby, or Java. Erlang programs have been deployed in telephone switching products for years, with extremely long uptimes - due in part to Erlang’s hot code swapping capabilities. Java’s hot code replacement or Python’s reload are substantially weaker than Erlang’s hot code swapping. So while libraries that provide an actor like model can help people learn a good programming model for concurrency, it’s less clear to me that the languages (and the implementations of those languages) hosting the libraries will be as good as Erlang when it comes to highly concurrent applications. Of course, if an application isn’t that concurrent it might not matter.
Conclusion
Semantically, there is a lot to like about Erlang - the actor based concurrency model, hot code swapping, higher order functions, and (once one gets used to it) pattern matching. The OTP libraries have been refined by many years of production usage in demanding, commercial applications.
At the same time, there are number of issues which I think are real barriers to Erlang adoption. The syntax will prove difficult for many people, which is a big issue. I’ve already mentioned the problems with string handling, and really that generalizes to a lack of libraries for performing 21st century / web computing tasks. The nice thing about telephone switches is that you don’t really have to talk to the world. But if Erlang is to be viable as a solution for mainstream programming as it moves to more concurrency, Erlang programs must be able talk to the environments around them.
I am aware of several projects where Erlang is being used to do the heavy server lifting and then data is being passed off to programs written in more familiar languages like Python, Ruby, or Java. Certainly this is one way that people could begin to exploit the benefits of Erlang without converting wholesale. It would also give the Erlang community some time to improve Erlang to the point where it could be adopted by a larger audience.
Recent Comments