Saturday, December 31, 2011

Goodbye 2011!

I don't usually write a year-end retrospective blog post but I thought 2011 was a pretty interesting year with many noteworthy events we should all take notice of and keep in mind. The events were of a sort that several science fiction authors, particularly of the cyberpunk variety, have been writing about since the '80s, and now it feels like their visions are materializing.

Let's start with the Japan earthquake disaster and Fukushima. I'm something of a Japanophile, so it was very saddening to see the devastation wrought by the earthquake and the ensuing tsunami. The Fukushima nuclear disaster was very sad to see for many reasons. First because of all the people it hurt/killed, particularly all the volunteers who selflessly exposed themselves to radiation trying to keep the nuclear reaction occurring in the broken remains of the reactor's core under control. I'm also saddened by the devastating effect this will have on public opinion about nuclear power, at a time when liquid thorium nuclear reactors seem like a promising near-term solution to the world's energy problems. The Fukushima disaster reminded me of the Miyazaki-animated music video for Chage and Aska's "On Your Mark," which takes place in the shadow of an entombed nuclear reactor.

To me at least, "Wikileaks" was the story of the year. Bradley Manning managed to sneak confidential diplomatic cables out of a secured government facility by burning them onto a CD-RW previously filled with Lady Gaga. Wikileaks began disclosing them, Julian Assange rose to celebrity because of it, and Freenet failed to fulfill its goal of being a useful platform for exactly this use case. I included the photo above which I took on the way to work one day (complete with tacky Instagram filters), which really makes me remark, "why not 'Free Bradley Manning?'"

The collateral damage the Wikileaks disclosure had on the world as a whole was absolutely remarkable. I think the disclosure of the diplomatic cables is the catalyst for the Arab Spring, in which dictators fell like dominoes. As terrible as the atrocities that occurred during these struggles were, I can't help but feel that some positive progress was made in the world, even when the future seems incredibly uncertain such as in Egypt.

BitCoin certainly caught my attention. The world now has a workable p2p currency scheme using crypto-coins as in the Cryptonomicon (except sans the gold backing). It's anyone's guess as to where it will go at this point, but it's a remarkable demonstration of the power p2p systems have to solve large-scale general problems in theoretical terms. Whether BitCoin proves to be a practical real-world currency remains to be seen. Critics have equated the value of the currency to the hype surrounding it, comparing it to things like beanie babies.

Both Anonymous and LulzSec made this year extra surreal. If nothing else, 2011 will be remembered as a year that many institutions started paying a hell of a lot more attention to infosec. It's a lesson Sony will certainly remember after the entire PlayStation Network was hacked and taken down. I thoroughly enjoyed the techno-anarchist spin that LulzSec originally put on their hacks, claiming quite ostensibly that they did it "for the lulz," and was somewhat disappointed to see them turn political after that. Still, the entire experience of having them in the world certainly felt like something out of a cyberpunk novel.

Steve Jobs died. It's really hard to imagine the scope of the effect the guy had on my life. Love him or hate him, Steve Jobs created the company that made the first home computer I ever used. WindowMaker, the window manager I used for nearly a decade before switching to OS X, was inspired by NeXTstep. At the end of 2011, I have a computer, tablet, and phone all running evolutions of NeXT's OS. The software I'm writing, DCell, also follows in NeXT's footsteps. I have a half-written blog post about that I hope to get published soon.

The IPv4 address space was exhausted. It seems like IPv6 will actually become a reality soon, forced by the increasing costs of obtaining IPv4 addresses when they're scarce due to the technology's limitations.

I saw an entire string of announcements in cancer and AIDS research this year that sounded extremely promising. The announcements spanned everything from using HIV to cure cancer to a vaccine for HIV comparable to the polio vaccine. The ability for modern medicine to cure disease never ceases to astound me and I hope that we will see bona fide generalized cures for both cancer and AIDS quite soon.

One of the craziest things I saw this year was a NOVA special on immortality (available on Netflix, btw). They had footage of human organs grown in vitro, first by taking an organ from a donor (which could be an animal), using a special chemical to wash away everything but the cartilage, then using someone's own stem cells to grow a replacement organ from the cartilaginous skeleton of a particular organ. The special showed lungs that breathe and a heart that beats. The future of organ replacement will be growing you a brand-new replacement from your own cells, using the cartilage structure from a dead animal (or potentially in the future constructing the cartilage from a 3D blueprint).

The Large Hadron Collider supposedly found the Higgs boson. We'll see what future experiments say, but it seems like the standard model has been validated and the particles we expected to be there exist.

Oh yes, we got Osama. AMERICA! Fuck yea!

Occupy Wall Street emerged, almost a liberal reaction to the Tea Party, a movement whose anger wasn't centered directly on the government, but on the financial institutions who made out like bandits with TARP money. No major financial reform has taken place, and the institutions which were too big to fail are still too big to fail, and getting back to the same tricks which tanked our economy in the first place. I'm not sure when the US government is going to eventually make the decision to try to better regulate Wall Street, but I can't see it happening before the 2012 election.

Speaking of 2012, happy 2012 everyone! The Mayans and Terrence McKenna believed that the world is going to end on December 21st. Let's hope humanity has many, many more years ahead of it :)

As for myself, I had quite the crazy year. I went to Switzerland and got back home to find my basement flooded. I lost two jobs and got two new jobs after half a decade of job security. I created Celluloid, stopped working on Reia (guess I should update my blog header). I moved to San Francisco, where I met Jose Valim, the scumbag who started working on a language just like Reia (just kidding Jose) who threw it away and started working on a much cooler version of the same language. I also met Chris Bertels, Steve Dekorte, Yehuda Katz, Carl Lerche, Ben Reesman, Tom Dale, Colin Campbell, Majd Taby, and Slava Pestov. I stuck it to Erlang as a language and Node as a community. And I happened to have about 4 months of time spent unemployed where I practically worked on Celluloid, DCell, and surrounding projects full-time. It was pretty nice.

Happy new year everyone!

Tuesday, October 4, 2011

Node.js has jumped the shark

I've been trying to understand this whole Node.js thing that's been going on for the past few days. It's taught me a lot about how the Node.js community tries to reason about problems, and perhaps what's the real problem with Node.

It began with a relatively short rant by Ryan Dahl. Ryan talk's about how he's mad at complex software, which is at least an arguable position. I liked his rant, but Ted Dziuba did not.

Ted Dziuba wrote a brilliant troll post which lambasted Ryan and the concept of Node.js in general. I'm a huge fan of Ted's previous trolling, especially his parody TechCrunch site uncov, which trolled TechCrunch before TechCrunch became a parody of itself. Except in the case of uncov, it would be a few years before TechCrunch became a parody itself. With Node.js, the reaction was almost instantaneous.

Ted's argument centered around the problem of doing non-trivial computation within the event loop of a system like Node, and how that would affect the performance of the system. To illustrate this point, he gave an intentionally deoptimized Fibonacci function, along with the boldface caveat "Yes, I know there's a closed form solution. Shouldn't you be in front of a mirror somewhere, figuring out how to introduce yourself to her?"

Reading through the lines of Ted's trolling, his point is "I'm not specifically talking about Fibonacci. I'm talking about non-trivial computation as a general problem in Node." He specifically chose a slow algorithm to illustrate his point. However, what was the Node community's reaction?

One reaction was to go out and implement Ted's intentionally-retarded Fibonacci algorithm in a bunch of different languages and benchmark how fast the VM could optimize away a crappy algorithm. Based on several benchmarks, V8 actually does a comparatively good way of optimizing away the retarded algorithm compared to a lot of other languages. Cool story bro!

In the Reddit comments for this story I first truly gazed into the abyss of Node.js insanity. Node provides a way to schedule an anonymous function to run the next time it's event loop iterates using a function called nextTick. EventMachine (ugh) users may be familiar with this same pattern with EM.next_tick (which needs to die for most use cases, but that's the subject of another blog post)

Redditor "headzoo" suggests that we provide a "non-blocking solution" by unrolling the Fibonacci loop and execute one iteration of the Node.js event loop, calculating one iteration for each I/O multiplexing system call Node is making. When Ted Dziuba asked "Have you taken epoll into your heart?," I think he had no idea of the depths Node people actually have.

I don't really get what's going on in Node people's heads here. I think they seriously believe that throwing computation into the middle of an event loop is a good idea, because Node's event loop is FAST!!#$#! funroll-loops + nextTick = LUDICROUS SPEED!!

This crap is absolutely insane. For each iteration of the loop, Node is making an expensive system call. It's also defeating all of the mechanisms that V8's impressive JIT would use to optimize this problem, as substantiated by the previously mentioned Nodian's roflbenchmark. Clearly this is a very bad idea. But wait, it gets worse!

It wouldn't take long before another Node.js fan put together a Github project for this technique, which also added an "optimization": memoization! In addition to unrolling each iteration of the Fibonacci function to run within the event loop, it now caches the nth result. Now let's throw ApacheBench at it and see how fast Node can serve the precomputed result where n = 100.

Holy balls, it does 5390.22 requests per second serving a memoized value when I ask ApacheBench to request the same memoized value over and over!!#$! TAKE THAT TED DZIUBA! Is it any good? One word: yes. Did we miss the point that this isn't about Fibonacci? One word: yes. (Side note: I second raganwald in adding "Is it any good? Yes." to the top of all my READMEs)

Memoizing each member of the Fibonacci sequence makes this algorithm O(n) in memory. For shits and grins I installed Node-fib and asked it for the 1 millionth Fibonacci number. Node ground away (on a single core of my quad core i7 MacBook) for about a minute before running out of memory, crashing the entire VM.

Okay, so mistakenly implementing an algorithm this pathologically bad when you're trying to prove a point to someone who's just trolling you is pretty bad, right? But it gets worse. 

After pointing this out, a member of the Node.js community (post now deleted) suggested I might have an obsolete version of Node with a 1GB heap limit (because Node uses a VM targeted at client-side JavaScript where 1GB heaps are an uncommon use case, but hey, let's throw it on the server!) and that I recompile without the 1GB restriction so that this retarded algorithm can continue eating up all my system RAM. He says this as if this is a good idea instead of, I dunno, using a better algorithm.

Clearly the next logical steps are to store previously computed Fibonacci numbers in MongoDB. Or you could build a system with Socket.IO which caches previously computed Fibonacci numbers client-side using a distributed hash table. Then you'd be well on your way to a multimillion dollar cloud-based Fibonacci number service. Eventually you'll probably want to build in an OpenMP C++ native extension to calculate Fibonacci numbers across multiple CPU cores. That way you'll have a truly roflscale Fibonacci web service.

Wednesday, September 28, 2011

Object Oriented Concurrency: A Deep Dive into Celluloid (Part 1)

There's a quote from Alan Kay I've often cited as a source of inspiration in my various projects, from Revactor to Reia to Celluloid:
"I thought of objects being like biological cells and/or individual computers on a network, only able to communicate with messages"--Alan Kay, creator of Smalltalk, on the meaning of "object oriented programming"
This conception of objects likens them to things in the world which are very much concurrent. Every cell in your body is running at the same time, and cells communicate with each other using chemical signals. Computers on a network are all running at the same time, sending each other messages via network protocols.

In Alan Kay's conception of object oriented programming, it should be a natural model for concurrency. However, most languages that describe themselves as "object oriented" today bolt on concurrency as an afterthought, just a thin abstraction layer around the concurrency primitives provided by the operating system, such as threads, conditions, and mutexes. The hardware and OS people went through the herculean effort of abstracting hardware-level concurrency into threads, and from there, for the most part the programming language people haven't done much, at least in mainstream object oriented languages.

The exception lies in the functional language domain, in languages like Haskell, Clojure, and Erlang. Erlang, in part inspired by Alan Kay's language Smalltalk, has abstracted concurrency in such as way that users of the language are able to reason about it intuitively, something which can't be said for most users of threads. The key to Erlang's success, its secret sauce, lies in its message-based concurrency system, a system inspired by Smalltalk.

Smalltalk is generally considered to be the forerunner of all object oriented programming languages, but when it comes to taking to heart Alan Kay's conception of a message-based system, Erlang beats the mainstream object oriented languages hands down. Erlang has also incorporated the idea of communicating sequential processes, first seen in languages like Occam. By combining the ideas of Smalltalk with those of communicating sequential processes, Erlang created a system where concurrency is baked into the core of how the language operates, enabling fully isolated processes that talk to each other with asynchronous messages.

If this idea works so well in Erlang, can it be added to other languages in a way that makes sense?

From Actors to Concurrent Objects

Given Erlang was vicariously inspired by Smalltalk, an object oriented language, is there any reason why Erlang's ideas can't be applied to present-day object oriented languages to give them concurrent objects? The way Alan Kay describes objects they should inherently be concurrent, but the way we're used to working with objects is inherently sequential.

A whole slew of projects, including one of mine, have tried to implement Erlang's concurrency model in Ruby. None of them have been popular. In my opinion, this is because these projects (including my own project Revactor) have stuck far too close to Erlang, trying to write an Erlang DSL in Ruby instead of trying to reimplement these concepts in a Ruby-like manner. This makes trying to learn them pretty confusing, to the point where the best way to learn them is to first learn Erlang, then after you understand how Erlang works, you can translate in your head from Erlang into these Erlangy Ruby DSLs. Seems bad...

I read a blog post recently about how in the Smalltalk objects that end in "-er" (e.g. Manager, Controller, Builder, Worker, Analyzer) are "bad." For a long time I've thought much the opposite, that there are fundamentally two different types of objects: those which are inanimate and represent objects in the world, and those which are animate and active and manipulate the inanimate objects. I see the programming world as consisting of two very distinct things: actors, and the objects which they act upon. It's not that objects that end in -er are inherently bad, it's simply that OOP languages (including Smalltalk) have never contained the proper primitive for modeling their behavior.

Celluloid is a new kind of concurrency library. It allows you to model concurrent (i.e. thread-backed) actors in a system but still interact with them as if they were plain old Ruby objects. All you need to do to create concurrent objects in Celluloid is to include the Celluloid module in any Ruby class:

That's it! Just by doing "include Celluloid" all instances of this class you create will not be normal Ruby objects, but instead fully concurrent Celluloid-powered objects. These objects will continue to function just like any other object in Ruby. When you call methods on them they return values. If a method raises an exception, the method call aborts and the exception will continue to propagate up the stack.

I want to emphasize this because I think it's incredibly important: users of concurrent objects should not need to be aware that they're concurrent. They should work as closely as possible to any other plain old sequential objects.

Concurrent Objects in Celluloid

I'm going to help you understand how Celluloid works by first starting from a diagram of normal Ruby object interactions and building up from there. Let's start with a diagram of one method calling another:

Hopefully this diagram is easy to understand. Calls come in, responses go out, never a miscommunication! A call consists of the name of a method to invoke and arguments. The response consists of a value to return, or an exception to be raised. Object oriented dogma would have you think of a call as the caller sending a message to the receiver, which in turn sends a response back.

Now let's look at a concurrent object as implemented by Celluloid:
A quick overview: the caller and proxy objects function like normal Ruby caller and receiver objects in the previous diagram. However, the actor circle (i.e. the giant olive-looking thing) represents Celluloid's encapsulation of concurrency. Each actor runs in a separate thread, and exchange messages with proxy objects through their mailboxes, which are thread-safe message queues. Let's dive in!

All communication between regular Ruby objects and Celluloid's actors passes through a proxy object which intercepts the calls. This proxy is responsible for the central illusion that makes Celluloid's concurrent objects as easy to use as any other object, despite them being off in a distant actor somewhere that you must communicate with via messages through thread-safe mailboxes. The proxy object abstracts that all away, and gives you the familiar object-dot-method syntax that you know and love.

The proxy object translates the method call from a normal invocation into a Celluloid::SyncCall object. This object contains the method to be invoked and the parameters. This message is sent from the proxy to the recipient actor by way of its mailbox (which is an object of the Celluloid::Mailbox class).

Mailboxes work like thread-safe message queues, allowing several pending method invocations that the actor can process one-at-a-time. After a method has been invoked on the receiver object, the return value is sent back to the proxy in the form of a Celluloid::Response object. This value is then returned from the original method call made to the proxy.

This gives us the same behavior as a normal method call. However, normal Ruby objects aren't concurrent. To gain concurrency, we need to go beyond the normal method call pattern.

Adding Concurrency: Async Calls and Futures

Celluloid provides two methods for breaking out of the typical request/response call pattern:

  • Asynchronous calls: send a Celluloid::Call to a recipient actor, but doesn't wait for a response. The method call to the proxy returns immediately. To make an async call, add "!" to the end of any method.
  • Futures: allow the value a method returns to be obtained later, while that method computes in the background. To make a future call to an actor, use the #future(:method_name, arg1, arg2... &block) syntax. This returns a Celluloid::Future object, whose value can be obtained by calling Celluloid::Future#value
Let's look at these both to see how they actually work. First an asynchronous call, as we'd do it from Ruby code:

Even though ScarlettJohansson doesn't have an #oops! method, things are continuing to work as if you made two calls to the normal ScarlettJohansson#oops method, but no value is returned. Here's a diagram of what happens when you make an asynchronous call:

Asynchronous calls do not wait for responses, but forward a request for a method to execute, immediately returning back to the caller. No mechanism is provided to obtain a response to this call; async calls are a strictly fire-and-forget type of affair.

What if we want to invoke a method asynchronously but obtain the value the method returns at some point in the future? Enter futures!

Let's imagine we have a small army of Scarlett Johansson clones leaking photos on the Internet. Each one of them takes a little while drinking booze and fumbling around with their phone before they're actually able to post a nude photo. How can we tell them all to start doing this then reaping the results instantaneously when they're done? Let's use Celluloid::Actor#future to accomplish this task:

Our Scarlett Johanssons are now leaking photos to the Internet in parallel, and the wall clock time needed to have all of them get drunk and fumble around with their phone in order to post their nude photos is now barely more than the time each individual Scarlett took to post a couple photos. We're able to get the return value from ScarlettJohansson#oops after asynchronously requesting it be computed. How does this work exactly?

Celluloid implements futures through the Celluloid::Future object. Futures represent the result of a method which may or may not have finished executing before its result is requested. To obtain the result of a given future, call Celluloid::Future#value, but you need to be aware that Celluloid::Future#value will block until the method the future is associated with has finished executing.

Obtaining the value of a pending future is, like always, synchronized through a Celluloid::Mailbox object, which is used to provide a thread-safe interaction point for receiving the result of a method call if it hasn't already completed.

More to come!

I'd originally hoped for this blog post to contain a lot more, but honestly it's been sitting around half-finished for so long I thought I'd break it apart into a series.

In Part II, I'd like to cover what makes Celluloid truly unique (to my knowledge) among similar systems: "reentrant" method dispatch. This post will cover problems in existing RPC systems, including Erlang's gen_server, and discuss why Celluloid provides a more natural object abstraction. It will also explain why and how Celluloid uses Fibers to solve this problem, and the additional features that can be built upon Celluloid's reentrant method dispatch.

Part III (if I get that far) will provide a more in-depth look into some of the Erlangier features of Celluloid such as linking and supervision, and also discuss the roadmap for integrating some additional Erlang features into the Celluloid framework such as OTP-style applications and distributed actor systems. Stay tuned!

Tuesday, August 9, 2011

Erlang's biggest missing feature: globals

There's one problem with Erlang I didn't touch upon in my previous rant, whose symptom can be found in some Erlang code called mochiglobal.erl. To understand what mochiglobal does we can read the description found in the source code's header:

Abuse module constant pools as a "read-only shared heap"

Erlang has a global centralized "code server" which maps module names to the corresponding BEAM bytecode containing all of the functions in a given module (including a limited number of previous versions, so it has some MVCC properties). The code server stores the state which represents the functions of a given module in a separate shared heap. The code server has pretty decent semantics for changing its contents, which all focus on the specific case of managing the actual Erlang code behind a particular application and allowing hot deploys.

What mochiglobal does is flip the old Lisp aphorism of "code is data" on its head. As the Erlang "code server" is exclusively focused on managing Erlang modules, if you want to use it to store a global value, you must convert it into Erlang code, compile it, and put it into the code server.  This is exactly what mochiglobal does.

It's not as if mochiglobal is some arcane hack. It's used by some prominent Erlang applications, including Riak. Global shared state, something the Erlang VM has specifically been designed to exclude, is necessary in some real-world problems that are otherwise highly conducive to the Erlang VM. How many prominent Erlang applications have "mochiglobal" or some other "mochi*" code in them to provide features which really should be included in OTP?

Erlang could've done better here by providing some mechanism for managing global shared state. The Erlang code server is just one specific case where global shared state is needed, and that's the only one the language designers tackled.

A common Erlang reaction to the suggestion that the Erlang VM should support shared state is "how do you tolerate faults?" I don't think tolerating faults is particularly hard. We can look at one model for how to tolerate faults in this case: the Erlang code server itself. If you crash the Erlang code server, it brings down the entire VM. This probably isn't the best solution, but it's one solution. Let's do better.

Another solution would be to treat the global state as a sort of database, or perhaps more specifically a key-value store. This store can contain the code which implements a particular module in addition to shared global values. Programs could modify its contents in atomic sections, which are committed when they complete or aborted and rolled back if an exception is raised. I don't know about you, but it's beginning to sound a lot like STM.

I think shared-nothing systems like actors and STM are two ways of managing state which together build a more complete picture of how you can build general purpose programs. Code should just be another kind of global state, and global state needs some kind of concurrency story, which STM addresses. Like peanut butter and chocolate, a language which combined actor-like ideas with STM ideas has a good way to manage not just code, but global shared data.

Tuesday, July 26, 2011

The Trouble with Erlang (or Erlang is a ghetto)

This is a blog post I have been meaning to write for quite some time. I lament doing so because I've made a considerable time investment into the Erlang infrastructure and really love some of its ideas. Erlang has done a great and still unique job of synthesizing a number of concepts in a very interesting way. But after using the platform in various capacities for some 4 years now, there are some glaring issues I think need to be called out.

Records suck and there's no struct/map data structure

Erlang has a feature called "records" which uses the preprocessor to give you something akin to a struct or map, i.e. a way to access named fields of a particular object/term within the system. As far as I can tell, there's pretty much universal agreement within the community that this is a huge limitation, and several proposals have been made to remedy the problem. The requested feature has typically been referred to as a "frame", and several proposals for implementing frames have been floating around for several years. Yet no action has been taken on the problem.

So why doesn't Erlang have frames? While Erlang is an open source project, its implementation and release cycle are managed by Ericsson, the company that created it, and Ericsson just doesn't seem to care. I'm not sure what Ericsson's priorities are when it comes to adding features to Erlang, but in my opinion they're doing a worse job of engaging the community than Oracle has been doing with Java. I hate Oracle as a company, but so far it feels like they've actually done a fairly good job managing Java development and moving Java forward. I can't say that at all with Ericsson, and frames are the quintessential example of this.

Erlang sucks at managing memory

Once upon a time I looked upon BEAM's design as the future pattern all virtual machines would follow. I strongly encourage you to read that post before taking issue with anything I have to say in regard to this matter. I have completely reversed my opinion since the time I write that post.

The other night I tweeted "If you're looking for a language that gets multicore concurrency right, look at how Azul implemented Java on their Vega architecture" and I definitely stand by that. Azul is a company that got a lot of smart hardware and software people together and had them work on designing a custom system which would scale to hundreds of CPU cores (up to 768 of them), heaps that topped 500 GB (up to 768GB), and had the GC pause only 10-20ms at a time. The realtime performance characteristics Azul managed to eek out of their system lead them to often describe their GC as "pauseless".

Where Azul was scaling up to 768 CPUs in 2007, Erlang was crapping out around 15 CPUs in 2009. For everything Erlang had to say about the importance of immutability and messaging in concurrent systems, and despite Joe Armstrong's promise that "your Erlang program should just run N times faster on an N core processor," it turns out that on the Erlang VM the N core processor promise had an upper bound of around 15.

Why is this? Erlang implements its own memory allocator and can't take advantage of libraries like tcmalloc to provide better multithreaded heap management. I can't fault a language VM like BEAM for doing this save for the fact that what Erlang provides is relatively crappy.

Erlang has done a fairly decent job given the constraints it was working within. Erlang wanted to provide a soft realtime system, and managed to create one that works on commodity architectures, unlike the Azul Vega appliances which require custom hardware. However, Azul has managed to port their version of the JVM to x86 hardware with their Zing Architecture, which wraps the JVM in a separate runtime container which uses software transactional memory to replace the hardware transactional memory found on the Vega appliances. It's higher overhead but provides similar guarantees. Java also provides the RTSJ specification for building realtime systems in Java.

Both Zing and RTSJ demonstrate that Erlang's approach to building a realtime garbage collected system, using separate heaps per process, isn't necessary to still provide realtime characteristics. Erlang's approach of using separate heaps is nonstandard and comparatively hard to optimize because most other systems are using a shared heap model. Azul's Vega architecture shows that shared heaps can scale up to hundreds of CPU cores and hundreds of gigabytes of heap while still providing realtime characteristics. Even more exciting is that AMD's Fusion architecture, which they're implementing in conjunction with ARM, provides read and write barriers at the hardware level necessary to provide a system like Azul using commodity hardware.

However, I think everything I just said is moot for the majority of applications. People building messaging systems want the best performance possible but don't typically have software realtime constraints. The Erlang VM's approach to soft realtime made a design decision which hampers its messaging speed, namely the use of separate heaps, which requires messages be copied from one heap to another. This means the Erlang VM does not provide zero-copy messaging. Every time you send a message from one Erlang process to another, some amount of data must be copied.

Erlang has partly mitigated this problem by providing a separate shared heap for binaries, which are the Erlang type for arbitrary blobs of binary data. This means if you ensure the majority of data you move around doesn't contain anything of significant size except binaries, perhaps this won't be a problem. However, if you're moving large collections of numbers around (Erlang's strings-as-lists-of-integers come to mind), messaging will be comparatively slow compared to a zero copy system.

Various solutions to this have been proposed for BEAM, such as switching from a shared-nothing heap to a shared heap or a hybrid heap (where message-passed objects are copied once), however the Erlang garbage collector is not suitable for managing shared/hybrid heaps and would need to be rewritten for the task, and nobody has managed to get the shared/hybrid heaps working with Erlang's SMP scheduler, or rewritten the garbage collector to be more suitable to the task of managing a shared/hybrid heap.

A potential solution to this? Erjang, an implementation of Erlang on the JVM, provides zero copy messaging using the Kilim library for lightweight threads.

JIT? What JIT?

Erlang has a "JIT" compiler called HiPE, which is mostly hype. I put JIT in quotes because HiPE is mostly an Erlang-to-native-code compiler with a limited set of backends which does a pretty bad job of optimizing and can't use runtime profiling information to improve the quality of the native code it generates in the way JIT compilers like HotSpot are able to. Calling HiPE a just-in-time compiler is a stretch as it is for most part an ahead-of-time native compiler for Erlang. The quality of native code produced by HiPE can be so poor that it's often outperformed by the userland bytecode interpreter implemented in BEAM.

HiPE can perform a very limited set of optimizations. In particular, Erlang code is factored into modules, and HiPE's inliner is unable to inline natie code across modules. This is due to HiPE's lack of a deoptimizer (a.k.a. deopt), or a way to translate JITed code back into bytecode, which is necessary in general but particularly necessary in Erlang for cases like hot code swapping. Deopt support is a feature of many JIT compilers in languages more popular than Erlang, most notably the HotSpot compiler on the JVM. Google's V8 virtual machine for JavaScript added deoptimization support as part of their "Crankshaft" compilation infrastructure.

Erlang isn't general purpose

Erlang hates state. It especially hates shared state. The only facility provided by the language for dealing with shared state in Erlang is called "Erlang Term Storage" and provides a Judy array that several Erlang processes can talk to. The semantics of ETS are fairly awkward and using it directly is difficult. Erlang has a baked-in database called Mnesia which is built on ETS. Mnesia's performance characteristics aren't great but it provides a friendlier face for ETS. These are the only solutions to shared state baked into the language.

What should you do if you want to deal with a shared-state concurrency program in Erlang? The general advice is: don't. Erlang isn't designed for solving shared-state concurrency problems. If you encounter a shared state concurrency problem while developing your Erlang program, sorry, you picked the wrong language. Perhaps you should move along... and Clojure offers you some great ways to tackle shared state concurrency problems.

The syntax is atrocious

I think this one goes without saying. That said...

Let me come at this from a different angle than you're probably expecting: I've recently started working with Clojure, and I have to say, I really think Erlang would've been a lot better off with a Lisp-like syntax than a Prolog-inspired syntax. To-date Erlang is the only popular language with a Prolog inspired syntax and all of the awkward tokens and gramatical constructions make me wish it just had a simple Lispy syntax. This has been implemented in Robert Virding's Lisp Flavoured Erlang, which is very cool and worth checking out.

That opinion might come as a surprise, because the main project I was developing in Erlang was Reia, a Ruby-like syntax and runtime for Erlang. I've discontinued this project, for many reasons, one of which is because it's been surpassed in features and documentation by a similar project, José Valim's Elixir. After years of working on Reia, I've really grown to believe I'd rather spend my time working on a language which incorporates Erlang's ideas, but on the JVM with mutable state.

The Erlang cargo cult would love to hang me out to dry for even saying that... so let me address it right now.

Immutable state sucks and isn't necessary for Erlang-Style Concurrency

Immutable state languages force object creation whenever anything changes. This can be partially mitigated by persistent data structures, which are able to share bits and pieces of each other because they're immutable. This works, for example, when attempting to create a sublist that consists of the last N elements of a list. But what if you want the first N elements? You have to make a new list. What if you want elements M..N? You have to make a new list.

In mutable state languages, performance problems can often be mitigated by mutating local (i.e. non-shared) state instead of creating new objects. To give an example from the Ruby language, combining two strings with the + operator, which creates a new string from two old ones, is significantly slower than combining two strings with the concatenating >> operator, which modifies the original string. Mutating state rather than creating new objects means there's fewer objects for the garbage collector to clean up and helps keep your program in-cache on inner loops. If you've seen Cliff Click's crash course on modern hardware, you're probably familiar with the idea that latency from cache misses is quickly becoming the dominating factor in today's software performance. Too much object creation blows the cache.

Cliff Click also covered Actors, the underpinning of Erlang's concurrency model, in his Concurrency Revolution from a Hardware Perspective talk at JavaOne. One takeaway from this is that actors should provide a safe system for mutable state, because all mutable state is confined to actors which only communicate using messages. Actors should facilitate a shared-nothing system where concurrent state mutations are impossible because no two actors share state and rely on messages for all synchronization and state exchange.

The Kilim library for Java provides a fast zero-copy messaging system for Java which still enables mutable state. In Kilim, when one actor sends a message, it loses visibility of the object it sends, and it becomes the responsibility of the recipient. If both actors need a copy of the message, the sender can make a copy of an object before it's sent to the recipient. Again, Erlang doesn't provide zero-copy (except for binaries) so Kilim's worst case is actually Erlang's best case.

The limitations of concurrent objects in Reia were solved using mutable state in my Celluloid concurrent object library for Ruby, but that deserves a blog post in and of itself.

Single assignment is just as problematic as destructive assignment

Erlang doesn't allow destructive assignments of variables, instead variables can only be assigned once. Single assignment is often trotted out as a panacea for the woes of mistakenly rebinding a variable then using it later expecting you had the original value. However, let me show you a real-world case that has happened to me on several occasions which wouldn't be an error in a language with destructive assignment and pattern matching (e.g. Reia).

There exists a complimentary case of mistaken variable usage to the afforementioned problem with destructive assignment. In single-assignment programs, it involves mistakenly using the same variable name twice excepting the variable to be unbound the second time:

The first pattern matching expression binds the Foo variable to something. In the second case, we've mistakenly forgot Foo was already bound. What's the result?

exception error: no match of right hand side... 

We get no compiler warning in this case. This is the type of error you only encounter at runtime. It can lay undetected in your codebase, unless you're writing tests. Know what other problem writing tests solves? Mistaken destructive assignments.

Single assignment is often trotted out by the Erlang cargo cult as having something to do with Erlang's concurrency model. This couldn't be more mistaken. Reia compiled destructive assignments into Static Single Assignment (SSA) form. This form provides versioned variables in the same manner as most Erlang programmers end up doing manually. Furthermore, SSA is functional programming. While it may not jive with the general idealism of functional programming, the two forms (SSA and continuation passing style) have been formally proven identical.

The standard library is inconsistent, ugly, and riddled with legacy

Should module names in the standard library be plural, like "lists"? Or should they be singular, like "string"? Should we count from 1, as in most of the functions found in things like the lists module, or should we count from 0 like the functions found in the array module? How do I get the length of a list? Is it lists:length/1? No, it's erlang:length/1. How do I get the Nth element of the tuple? Should I look in the tuple module? Wait, there is no tuple module! Instead it's erlang:element/2. How about the length of a tuple? It's erlang:tuple_size/1. Why is the length of a list just "length" whereas the length of a tuple is "tuple_size"? Wouldn't "list_length" be more consistent, as it calls out it works on lists?

When we call erlang:now() to get the current time, it returns {1311,657039,366306}.  What the hell does that mean? It's a tuple with three elements. How could time possible need three elements? A quick look at the documentation reveals that this tuple takes the form {Megaseconds, Seconds, Microseconds}. Separating out Microseconds makes sense... Erlang has no native decimal type so using a float would lose precision. But why split apart Megaseconds and Seconds?

Once upon a time Erlang didn't support integers large enough to store the combination of Megaseconds and Seconds, so they were split apart. The result is a meaningless jumble of three numbers, which you have to run through the confusingly named calendar:now_to_local_time/1 function to get a human meaningful result, which doesn't tell you what time it is now, but instead takes the tuple that erlang:now/0 returns as an argument and will spit back meaningful {Year, Month, Day} and {Hour, Minute, Second} tuples.

Legacy in the grammar

Try to use "query" as an atom in Erlang, e.g. {query, "SELECT * FROM foobar"}. What happens?

syntax error before: ','

This is because 'query' is a reserved word which was reserved for Mnemosyne queries. Never heard of Mnemosyne? That's because it's an archaic way of querying Erlang's built-in database, Mnesia, and has been replaced with Query List Comprehensions (QLC). However, it remains around for backwards compatibility.

You can't use "query" as a function name. You can't tag a tuple with "query". You can't do anything with "query" except invoke a deprecated legacy API which no one uses anymore.

Strings-as-lists suck

Erlang provides two ways of representing strings. One is as lists of integers, which is the traditional way that most of the library functions support. Another is binaries. Erlang has no way of differentiating lists of integers that represent strings from lists of integers that are actually lists of integers. If you send a list of integers in a message to another process, the entire list of integers is copied every time. On 64-bit platforms, every integer takes up 64-bits.

The obvious solution here is to use binaries instead of lists of integers. Binaries are more compact and exist in a separate heap so they aren't copied each time they're sent in a message. The Erlang ecosystem seems to be gradually transitioning towards using binaries rather than strings. However, much of the tooling and string functions are designed to work with list-based strings. To leverage these functions, you have to convert a binary to a list before working with it. This just feels like unnecessary pain.

The abstract concept of lists as strings isn't inherently flawed. In many ways it does make sense to think of strings as lists of characters. Lists as strings would probably make a lot more sense if Erlang had a native character type distinct from integers which was more compact and could avoid being copied each time a string is sent in a message like a binary. Perhaps in such a system it'd be possible to avoid transcoding strings read off the wire or completely transforming them to a different representation, which is costly, inefficient, and often times unnecessary (yes, this is a problem with Java too).

There's no "let"

Want a local binding in Erlang? Perhaps you've used let for this in a Lisp. What happens when you try to do this in Erlang? Even attempting to use "let" in Erlang just yields: syntax error before: 'let'

Once upon a time Erlang was supposed to get let bindings, and the "let" keyword was set aside for this purpose. But much like frames, it never happened. Instead, let is now an unimplemented reserved word which just breaks your programs.

There's no "nil"

In Clojure, I can write the following: (if false :youll-never-know).  This implicitly returns "nil" because the condition was false. What's the equivalent Erlang?

Erlang forces you to specify a clause that always matches regardless of whether you care about the result or not. If no clause matches, you get the amazingly fun "badmatch" exception. In cases where you don't care about the result, you're still forced to add a nonsense clause which returns a void value just to prevent the runtime from raising an exception.

Where do I go from here?

Again, I want to emphasize that I have a great deal of respect for Erlang conceptually. But at this point I'd like to take what I've learned and go elsewhere with it. One direction I've gone is the Celluloid concurrent object library for Ruby. You can read more about it in the original blog post I wrote about Celluloid, which is a bit out-of-date at this point. I have a forthcoming blog post which should dive a bit deeper into Celluloid's guts and how it can do things which aren't possible in Erlang.

As you've probably guess from the references sprinkled throughout this post, I'm learning Clojure. I'm a fan of the JVM and Clojure provides a great functional language for leveraging the JVM's features. I think the sort of things that I'd be writing in Erlang I'll try writing in Clojure instead. Clojure has elegant Lisp syntax. Clojure has maps. Clojure has powerful facilities for dealing with concurrent shared state problems. Clojure has great semantics for safely managing mutable state in a concurrent environment. Clojure has real strings. Clojure has let. Clojure has nil. Clojure runs on the JVM and can leverage the considerable facilities of the HotSpot JIT and JVM garbage collectors.

I'd also like to try my hand at creating a JVM language, especially with the impeding release of Java 7 this Thursday. Java 7 brings with it InvokeDynamic, a fast way to dispatch methods in dynamic languages, and considerably eases the difficulty of implementing dynamic languages on the JVM. Stay tuned for more details on this.

Wednesday, June 29, 2011

Why I'm stopping work on Reia

Some of you may have seen Elixir, a Ruby-inspired language for the Erlang VM, created by
José Valim. Whenever I see posts on HN or proggit about Elixir, I check out the comments, and almost every time someone asks about Reia, specifically how the two languages compare.

Reia and Elixir are extremely similar. If you check out their respective codebases, there's an almost bizarro world similarity between them. The project layout is almost identical, as is the build process and associated scripts to drive various parts of the language like the compiler and REPL. My impression of the code after looking over it was we were using largely the same mechanisms, and where they differed, José's solutions were something I had been thinking of changing, or something entirely new I hadn't thought of which seemed pretty cool.

At this point, in all respects Elixir is farther along than Reia and a better implementation. I think it's pretty bad to have two competing niche languages with nearly identical features.

So I'll be discontinuing work on Reia. The codebase and the web site will remain up on Github for however long Github wants to host them. Celluloid is Reia's spiritual successor. The main feature I always wanted out of Reia was a concurrent object system, and Celluloid implements that on top of Ruby.

Wednesday, May 11, 2011

Introducing Celluloid: a concurrent object framework for Ruby

I've spend a lot of time recently working on a new concurrency library for Ruby called Celluloid. In short, its goal is to make working with threads as easy as working with Ruby objects in most cases, while still remaining loaded with all sorts of power user features for the edge cases. It's heavily inspired by Erlang and the actor model (hence "celluloid") and represents my best effort to port as many of these concepts over while making them more Ruby-like. This is the first in what I hope will be a series of blog posts describing various concurrency problems you might encounter in Ruby and how Celluloid can help solve them.

If you're already sold on using threads in Ruby, feel free to skip the next section of this post. However, as threads have remained a perpetual pariah in Ruby as a language, I feel some explanation is in order as to why you might actually consider using them.

Ruby and Threads

Rubyists generally don't like threads. There's plenty of good reasons to dislike threads: they're error prone for end users and the original implementation of threads in the Matz Ruby Interpreter was pretty crappy and broken in multiple ways. Even with the latest YARV interpreter found in Ruby 1.9, a global lock prevents multiple threads from running concurrently.

On the flip side, if you need multicore concurrency Ruby processes are cheap and there are some pretty good libraries like DRb for allowing Ruby VMs to work together. But even then most people are using Ruby to write stateless webapps that store all state in a database, so you can just run multiple Ruby VMs which all have the same application loaded to leverage multiple CPUs in a machine.

I used to be in the thread-hater camp, having cut my teeth on multithreaded C programs which left a bitter taste in my mouth, but recently I've changed my tune. This is mainly due to the great work of the JRuby and Rubinius teams to add true multicore concurrency to their Ruby implementations. JRuby has supported multicore concurrency via threads for awhile, and Rubinius is adding it in their hydra branch. With these Ruby interpreters, you can run one virtual machine per host and the threads you create will be automatically load balanced among all available CPU cores.

This has immediate benefits for things like Rails applications which enable thread safe mode. Rails will automatically create a new thread per request, allowing one VM to service multiple requests simultaneously. On interpreters like JRuby and Rubinius Hydra, this means you can run just a single VM per host and your application will utilize all available CPU cores. All the memory overhead of loading multiple copies of your application is mitigated, and as an added benefit you can take advantage of the better garbage collection these VMs (particularly the JVM) offer.

There is a catch: libraries can't share state across threads without using some form of thread synchronization. This is often trotted out as a persistent worry of those who prefer to run their Rails apps in the standard single threaded mode. Those gem authors, who knows what they're doing? Maybe they're using global variables!  People don't think about this sort of stuff in Ruby, so shouldn't we just assume that 100% of Ruby libraries aren't thread safe per default?

The truth, at least for things like Rails apps, is that the general way they operate typically eschews thread safety issues. Ruby as a language favors object creation over mutating existing objects, and webapps generally create a new set of objects per request and don't provide mechanisms for sharing state between connections due to their stateless nature. In general, webapps are stateless and don't do things which will share state between threads.

If you do intend to go thread safe on your Rails app, you should certainly do your due diligence for auditing the libraries you use for unsafe usage of global and class variables, but in general I think the worries about running Rails apps in multithreaded mode are overblown. Ruby has much better semantics for promoting thread safety than other languages that have made the leap from single threaded to multithreaded (e.g. C/C++), and those languages have managed to make the transition with countless applications running in a multithreaded mode.

In the two years I've been deploying thread safe Rails applications, I've encountered exactly one thread safety bug, and that was in a library that originally claimed to have a specific thread safe mode but removed it from later releases and I unfortunately didn't catch that they had done so. The fix was simple: just create a thread-specific instance of an object I needed rather than sharing one across all threads. I won't say finding the bug was easy peasy, but all in all I don't think one bug was a bad price to pay for all the benefits of moving to a multithreaded deployment.

Concurrent Objects: How do they work?

Celluloid's concurrent objects work like a combination of normal Ruby objects and threads. You can call methods on them just like normal Ruby objects. To create a concurrent object, declare a class that includes the Celluloid::Actor module:

Then call the spawn method on the class:

This creates a new concurrent Charlie Sheen object. Calling the current_status method on it returns the normal value we'd expect from a method call. If an exception is raised, it will likewise be raised in the scope of the caller. But behind the scenes, all these things are happening in a separate thread.

Let's say things aren't going so well for Charlie. Instead of winning, Charlie is fired:

How can we help Charlie win again?

Calling Sheen#win! here does something special: it executes the method asynchronously. Adding a ! to the end of any method name sends a message to a concurrent object to execute a method, but doesn't wait for a response and thus will always return nil. You can think of this like signaling an object to do something in the background, and perhaps you'll check on the result later using normal synchronous method calls.

Using a ! to call a method asynchronously follows the Ruby convention of predicate methods with a bang on the end being "dangerous." While there are certain dangers of asynchronous methods (namely in how errors are handled), providing thread safe access to instance variables is not one of them. Charlie is running in his own thread, but there's no need to synchronize access to his private variables. This is where Celluloid's secret sauce comes in.

Charlie maintains a queue of pending method calls and executes them one at a time in sequence. Celluloid uses and asynchronous messaging layer that you can communicate with using normal Ruby method call syntax. However, when you call a method on a concurrent object in Celluloid, the "message" you send is quite literal and takes the form of a request object which waits for a response object (instances of Celluloid::Call and Celluloid::Response respectively).

This approach is largely inspired by the gen_server abstraction within the Erlang/OTP framework. For you Erlang nerds who might be worried Celluloid tries to jam everything into gen_server-shaped boxes, let me say right away that isn't the case, but you will have to wait for a further installment of my blog to find out why.

Celluloid by Example: Parallel Map

Let's start with a simple, practical, real-world example. If you're interested in digging deeper into the guts of Celluloid before starting this, I'd suggest you check out the README. That said, let's start with a simple problem: how can we implement a parallel map? That is to say, how can we reimplement Enumerable#map such that all of the map operations are performed in parallel rather than sequentially?

As this is a contrived and relatively simple problem, I'll go ahead and share with you how you might do it using Ruby threads as opposed to using Celluloid:

This version alone winds up being all you need to accomplish simple parallel map operations in Ruby. Here are some examples of using it from irb:

This pmap implementation behaves just like we'd expect map to. It returns the value of the block for each element if everything succeeds correctly, and raises an exception if anything goes wrong along the way.

Now I'd like to show you how to refactor this code to fit into the concurrent object pattern Celluloid uses. Let's start by trying to represent this same code using an object to perform the computation:

To turn this into a concurrent object, we first need to include Celluloid::Actor. To achieve concurrency, we need to make the method that performs the computation callable asynchronously. The initialize method is called synchronously by spawn (in case something goes wrong during initialization), so we'll need to create a separate method that actually calls the given block:

After that we can rewrite Enumerable#pmap using this class:

This creates a new Mapper actor for each element and calls Mapper#run asynchronously on each of them. After every one of them is executing they're iterated again, this time checking the return value. Since actors can only process one method call at a time, the call to Mapper#value will block until Mapper#run has completed, even though Mapper#run was called asynchronously.

This approach of allowing a value to be computed in the background and then only blocking when the value is requested is called a future. You've now seen how to implement a future, but it's also baked directly into Celluloid itself. Here's how to implement Enumerable#pmap using Celluloid::Futures:

Like Mapper, Celluloid::Future takes arguments, passes them to a block, then runs that block in the background asynchronously. Only when the value is requested does it block the current thread.

Now that we have a pmap function, what can we do with it? How about we compare the time it takes to do a bit of Google Image Search screen scraping for different color images for a particular search term using regular map vs. pmap?

The performance metrics vary across Ruby implementations, but in general, the parallel version goes approximately 3.5x faster, and the Celluloid version is 5-10ms slower than the version written using raw Ruby threads.

While this example is fairly trivial, in the next installment of this blog I'd like to demonstrate how to write a Sinatra-based chat server similar to node_chat.

What does this mean for Revactor?

In 2008 I wrote another actor library called Revactor, based on Fibers and evented I/O. While those ideas have grown increasingly popular, Revactor never did. I attribute this largely to Revactor's API, which was a fairly literal translation of Erlang's APIs into Ruby form with too little focus on putting an easy and accessible face on things. If you saw Mike Perham's recent article on actors in Rubinius (Revactor used a mostly identical API, as did MenTaLguY's Omnibus library), the code can be a little daunting, to the point you might need to learn a little Erlang just to figure out how to use it.

Celluloid is the official successor to Revactor. While Celluloid is primarily based on thread-based actors, it's been designed from the ground up with the idea of eventually incorporating event-based actors as well which can interoperate with an event library like EventMachine or I know I originally dissed Scala for having both thread-based and event-based actors, but short of an Erlang-like process abstraction, it's not a bad compromise.

What about Reia?

One of the projects I've been working on the longest is Reia, a Ruby-like programming language for the Erlang VM. Today happens to be Reia's third birthday, and I do have to say after three years it's not where I thought it would be. It's generally usable but still missing some big features I feel are needed to make it a "complete" language. The main thing I feel is missing from Reia is a concurrent object model, and you can think of Celluloid as being an in-Ruby prototype of how it would work. I started to work on this in the legacy branch of Reia, but felt like it was too big of a project to tackle until I had fleshed out some of the other fundamentals of the language.

After I feel comfortable with how Celluloid is working I would like to try reimplementing in Reia. After that I think Reia will evolve into a truly useful language which bridges the gap between object oriented languages and Erlang-style concurrency.

I think Celluloid has the potential to be a truly useful library in Ruby on its own, however. It provides most of the underpinnings needed for more Erlang-like concurrent applications without having to switch to a different language.

Tuesday, April 5, 2011

Reia: Now with a PEG parser

I haven't blogged about Reia in so long. Mea culpa! It's about this time that people start to think "I haven't heard about Reia in awhile. It must be dead." No, Reia is very much alive my friends, and making some pretty interesting progress... I hope to be able to announce some important new features around Reia's 3rd birthday. Stay tuned for that, but first a preview of things to come...

An experimental branch of Reia is now available which uses Neotoma to generate its parser thanks to some pretty impressive contributions by Graeme Defty. Neotoma is a Parsing Expression Grammar (PEG) based parser generator for Erlang, inspired by Packrat. Neotoma's author Sean Cribbs has also released Neotoma 1.5 with contributions by Graeme Defty which uses Erlang binaries internally and is substantially faster than the previous version.

Why does a PEG matter? PEGs make short work of problems that are extremely complex to handle when you attempt to subdivide the problem of parsing into separate scanning and parsing steps, such as how a traditional lex/yacc (or in Reia's case, leex/yecc) parser would operate. If you've ever attempted to look at the source code of the Ruby parser, you'll find some strange and confusing feedback between the lexer and the parser.

What's this for? Well the foremost reason is: interpolated strings. Ruby allows you to embed arbitrary Ruby code inside of any string using the #{...} syntax. This is a really great feature and one I managed to half-assed implement in Reia because I strongly believe in its awesomeness. However, Reia's implementation is a bit brittle and has a lot of implementations. Just recently I switched to the latest greatest version of leex which ships with the Erlang runtime and had to make some rather arcane changes to some code that uses leex internals, just to continue to support a partially functioning string interpolation mechanism.

Now, toss in some more fun complexities: the awesome /.../ regex literal syntax. We all love it, but why doesn't every language have it? What you may not realize is that this syntax is ambiguous in certain cases with the / and /= operators like it is in other languages like JavaScript. Now, for added fun, toss in the fact that regular expressions can interpolate just like strings, and you're beginning to see the makings of a gramatical nightmare.

All of these things are easy with a PEG. PEGs blend tokenization with parsing and allow comprehension of a much wider range of languages than is possible without pulling your hair out using lex/yacc-like tools, and much more than that, it's a very natural process with PEGs. PEGs are also by nature right-recursive, something that works quite well in immutable state languages like Erlang that have to build their syntax trees from right-to-left due to the nature of immutable singly linked lists. These lists only let you append elements on the left.

This sounds well and good, but unfortunately I have some bad news. Even after a few rounds of performance tuning, using an experimental branch of Neotoma that uses binaries internally instead of lists, the PEG parser is still about an order of magnitude slower than the leex/yecc version. Talking to Neotoma's author Sean Cribbs, it sounds like Neotoma might be doing an excessive amount of unnecessary copying internally. If PEGs pique your interest and you know a bit of Erlang you might take a peek at Neotoma and see if you can find some potential performance optimizations.

I would still like to merge the peg branch of Reia, and the PEG grammar fixes a lot of quirks in the present yecc grammar, but I'm still holding out until the performance is improved to closer to the leex/yecc speeds.

Tuesday, March 22, 2011

Distributed systems and dynamic typing

There's a very good blog post by Robert Harper, a CMU CS professor, called "Dynamic languages are static languages." It's very enlightening and I strongly encourage you to read it. If I understand it correctly, which I freely admit I may not, the general idea is that dynamic languages can be thought of as static languages that have a single all-encompassing type. In that regard, dynamic languages are a proper subset of static languages. If you think I misinterpreted his post and I'm confused, please flame me in the comments.

In a previous post, called "Parallelism is not concurrency", he opines on a pet peeve of mine, namely how the terms parallelism and concurrency are nonchalantly and incorrectly interchanged. Parallelism applies to deterministic operations that operate on similar data in similar time. Some examples of parallel operations include rendering of 3D scenes on GPUs, or encoding/decoding blocks of compressed video. Concurrency, on the other hand, refers to the nondeterministic manner in which distributed systems operate, particularly ones where CPUs are separated over an unreliable network which can lose connectivity at any time.

In a third blog post, "Teaching FP to freshmen", Robert says he'll be teaching Standard ML to freshmen, and further argues he won't be teaching Object Oriented Programming because it's "both anti-modular and anti-parallel by its very nature, and hence unsuitable for a modern CS curriculum."

Three very interesting blog posts by the same person, clearly a well-educated computer science professor who knows more than I do. I mean, I like programming languages and I'm working on my own dynamically typed functional programming language, but Robert Harper wrote a book, one I certainly couldn't write. So who am I to judge?

Parallelism and Concurrency are Both Important

What I see missing from Robert Harper's writing is any attention paid to concurrency. He pays intense attention to parallelism, recognizes parallelism as important for the future, and strongly advocates functional languages as a great way to address the problems of parallelism. I have absolutely no bone to pick with him here and wish him great luck with his courses at CMU which address this problem domain.

However, my interests primarily lie in the realm of concurrent computing, and particularly in the area of distributed computing. In the area of distributed computing I find dynamic languages particularly important and think Robert Harper's article on static vs. dynamic languages omits some of the advantages of dynamic languages which make them work better in distributed systems.

This is a weighty subject, and one in which I don't think my own ideas alone make a particularly cogent argument. For some opening remarks, I will defer to Joe Armstrong, creator of the Erlang programming language, and his opinion from the book "Coders at Work" by Peter Seibel. As a bit of context to this quote, Joe is discussing the potential advantages that a static type system might confer upon Erlang. But then he gets to the disadvantages...
...the static type people say, "Well, we really rather like the benefits of dynamic types when we're marshaling data structures." We can't send an arbitrary program down a wire and reconstruct it at the other end because we need to know the type. And we have—Cardelli called it a system that's permanently inconsistent. We have systems that are growing and changing all the time, where the parts may be temporarily inconsistent. And as I change the code in a system, it's not atomic. Some of the nodes change, others don't. They talk to each other—at certain times they're consistent. At other times—when we go over a communication boundary—do we trust that the boundary is correct?
Type Systems and the CAP Theorem

There are two particularly sticky problems when it comes to the use of type in distributed systems. The first is the issue of serialization, or marshaling, of particular states. One way or another this is a solvable problem, both for statically typed and dynamically typed languages. I really don't want to delve too deep into this issue as it distracts from the larger point I'm trying to make, but in general, I think this is an easier problem to solve in dynamic type systems. I would also like to note that serialization formats which vomit their types all over the protocol and the codebase are outgrowths of static type systems. I'm looking at you, CORBA, SOAP, Protocol Buffers, and Thrift. On the flip side, systems which choose a minimal, semi-universal type system, such as JSON, BSON, BERT, and Msgpack, are all outgrowths of dynamic type systems. If I have a point to make here, I think it's that these systems are outgrowths of two very different ways of thinking about the same problem.

Marshaling is still a very important topic in distributed systems. Erlang largely abstracts this problem away from the programmer, allowing distributed nodes to exchange Erlang "terms" between processes on distributed nodes in the exact same way one would exchange messages between two processes located on the same host. The process of serializing that data, transmitting it over the network, receiving it via TCP, decoding it, and sending it to the appropriate Erlang process, is completely transparent to the end user. This is an extraordinarily powerful abstraction.

While statically typed languages can attempt to marshal data in a minimalistic JSON-like type system, this typically isn't the case. Instead, statically typed languages generally seem to prefer to vomit their types all over the protocol. The boilerplate code needed to marshal/unmarshal particular types can be generated automatically by a declaration of the types and methods of a particular protocol, such as the WSDL files used by SOAP. Again, users of statically typed languages could reduce the state of particular entities in their system to one which could fit into a minimalistic type system, but for static languages this is still a manual process, or one which requires manual code generation. In a language like Erlang which is built from the ground up to be distributed, dynamic, and operate around a minimalistic type system, serialization and deserialization can happen completely automatically.

Why is this important in a distributed system? Because, to paraphrase Joe Armstrong, distributed systems are messy. Imagine an Erlang-like distributed system that's statically typed. In order for such a system to work effectively, all nodes in the system must have the exact same code loaded and therefore have a universal consensus on what the types in the system are. This has huge implications on the theoretical properties on such a system. In order for a distributed system to agree on the nature of all types, it must be consistent.

However, if you're familiar with the CAP theorem, you may recognize the inherent problem this may cause. The CAP theorem gives you three options: a consistent fault-tolerant system, a highly available fault-tolerant system, or a consistent highly available system which breaks at the first sign of a fault. Only two of these options provide the consistency needed to ensure universal agreement on the types in the system such that automatic marshaling/unmarshaling of static types is even possible. In a distributed system, you either must give up universal agreement on the types, or sacrifice availability.

To quote Joe again, distributed systems are composed of parts which are "growing and changing all the time" with "parts may be temporarily inconsistent." While there aren't any guarantees that distributed systems built around dynamic type systems will work, inconsistent statically typed systems with disagreements about types are guaranteed not to work. Dynamic systems not only provide the possibility that your system may continue to function with different versions of the code loaded at the same time, but the ability for the programmer to plan for this contingency and offer ways to mitigate it. It's possible this may result in errors, but it may work, whereas incompatible type definitions are universally guaranteed to create errors. In a distributed environment, dynamic type systems provide extensibility, whereas static type systems actively seek to preclude it.

Something I've seen time and time again in systems like SOAP and even Thrift and Protocol buffers is attempts by programmers to escape the constraints of the type system, which almost universally fall into proprietary ways to store key/value pairs. One SOAP API I'm working with now provides "Maps" with "Entry" tags that have a key attribute and an associated value. Another implementation provides an array of "NameValuePair" objects. These solutions seem ugly, but in my opinion, their intentions are not. These are people seeking to extend running systems without the need to completely redefine the protocol. That's very much a practical concern.

Distributed Applications Must Be Flexible

In order for distributed programming to work effectively, nodes need to be able to call functions on each other without the need for programmers to write custom marshaling/demarshaling code for each type. The marshaled data needs to work extensibly, so that nodes running different versions of the code can still talk to each other in a forwards and backwards compatible manner.

Protocols will change over time. Older versions of the code need to work with a newer protocol, and vice versa, older versions of the protocol need to work with newer code. Nodes should be upgraded as practicality dictates. Perhaps your system administrator begins an upgrade and you lose access to a datacenter, because a janitor at your upstream ISP spilled a bucket of mopwater all over their datacenter's raised floor and caused a huge electrical disaster. Now your distributed application is running two different versions of the code, and it's suffered a network partition. Does this mean it should just break when the network partition is fixed?

Erlang has shown us it's possible to recover from these kinds of conditions. Even when we can't change code atomically across the entirety of a distributed application, it should still continue to operate without breaking. Distributed systems should be able to grow and change all the time without rigid boundaries.

Tuesday, March 15, 2011

Relativity for Programmers (A.K.A. Oh CAP!!!)

When you first start to learn physics you typically learn Newtonian Mechanics. Objects have inertia. Force is mass times acceleration. For every action there is an equal and opposite reaction. These all seem straightforward.

Albert Einstein turned the world on its head. Everything is relative. Time is relative. Simultaneity is relative. There is no universal clock.

The same thing happened in the computer science world, not with a bang or the attention that was given relativistic physics, but with a small crowd paying attention. CAP Theorem has the same implications for computer scientists as relativity had for physicists, but no one is really paying attention.

Computer scientists may dream of a fully consistent database distributed across a network, capable of two-phase commit and typical consistency guarantees. Not many think about the implications of such a database.

Imagine you had your database split across two datacenters. Let's call them Foo and Bar. While at one point in time, Foo and Bar could talk, now they can't. Perhaps a clumsy janitor spilled the bucket for his mop, and it destroyed all of your routing hardware between your datacenters. Some customers are accessing Foo and some are accessing Bar. If they want to perform a read, they'll get data that's possibly stale. If they want to perform a write, what happens?

CAP Theorem

CAP Theorem is possibly the most important property of distributed systems that you can possibly understand. It's been motherfucking proven by computer scientists, bitches! So what does it state? The core idea is that consistency which is both instantaneous and global is impossible, except on a single node. As soon as you have more than node storing data for you, you either have to sacrifice availability or consistency. Much like how you can only infer the state of the universe from old light beams hitting your light cone in relativistic physics, distributed systems can only infer the state of other nodes via the protocols they communicate with. These protocols can fall into one of three different forms per the CAP theorem:
  • CP: we have masters you have to listen to, bitch slaves. You can try to change the cluster state but all changes have to go through the masters, and if your master is split, you can't modify any state you bitch submissive node
  • AP: sure, we'll accept reads and writes. We'll try to eventually resolve any conflicts in the event of a netsplit. If we're cool we'll let you specify your own conflict resolution mechanism in the event of conflicting writes, otherwise we'll just do last writer wins.
  • CA: the network broke? Whoa. I was totally not expecting that. I was just happily doing bongrips until you barged in. I'm so high I don't even know what's going on.
If you're writing a datastore you consider to be "CA", you're doing it wrong. Fortunately, most datastores that claim to have "CA" properties are actually CP. That is to say, in the event of a network partition, they sacrifice availability. Reads to the cluster hopefully work, but writes shouldn't. Writes should error or time out for a consistent system. Any system that functions this way is in fact "CP". That is to say: it provides consistency, but in the event of a netsplit, you lose availability, at least for writes. Ideally these systems still provide stale reads.

Calling your system CA is an admission of the fact that if a partition separation occurs, and due to writes each partition has a separate view of the world, when the netsplit resolves your partitions have no mechanism for resolving conflicting states between partitions and thus your datastore is just fucked. Short of a system administrator picking which view of the world they consider to be the best and blowing away the state on the other nodes, the system state is going to be inconsistent and irresolvable.

So what are the alternatives which are partition tolerant and don't break in the event that the janitor spills mopwater on the router that routes packets between your datacenters?

Option #1: sacrifice consistency for availability

This option lets clients read and write from any partition. When connectivity between partitions is restored, there's a plan for resolving all of the writes into a consistent world state. The simplest plan is last writer wins, which is used by Cassandra. Whoever was the last one to alter the cluster state provided the definitive cluster state, simply by virtue of writing last.

In an eventual consistency model, clients may have inconsistent views of the world. This is unfortunately a fact of life. State may unexpectedly change by a particular client's view, because it's being modified on a different partition and those partitions managed to sync up. The road ahead of you may be a beach, but after syncing up with another part of the world, it may turn into a cactus. Such is life.

Option #2: sacrifice availability for consistency

Say you have a master/slave data store, and someone writes to a slave. Wat do? Slave can't talk to master. What's the most obvious option? Error.

This is a "CP" system. Slaves can serve stale state, but if you want to change the state, you have to talk to the master for that state. State can be partitioned/shareded/durr between multiple masters, but if the master for the particular state a slave wants to modify isn't available, sorry, that's a paddlin', or rather an error.

Option #3: highly available, and consistent at the partition level, netsplit fixed wat???

The only other option, the "CA" option, is that each partition pretends that writes to that partition are consistent, but when the netsplits are resolved, there's no consistent way to resolve that state. That is to say, if netsplits occur, each partition is highly available and allows writes, but as soon as the netsplit resolves, the cluster state is broke and irreconcilable.

In a quick survey of NoSQL datastores, Membase, MongoDB, and the hypothetical Redis Cluster all claim to be "CA". Are they really? Or do they just sacrifice availability in the event of a netsplit? If that's true, they're actually "CP", not "CA".

You really don't want to sacrifice partition tolerance. In fact, some might go as far as to say you CAN'T sacrifice partition tolerance. If you think your system is "CA" you probably understand the the CAP theorem and its implications.

CAP is the law, and AP or CP are the only reasonable options 

If you're running an app on a distributed network, things are going to go wrong. You might idealistically claim that you can provide both consistency and availability, sacrificing partition tolerance. You can't.

Can you pick "CA"? Sure, if you're content with losing all your data if the network had any errors. That's probably not what you mean. If you're building software for a fault-tolerant world, it's probably either going to be:
  • Consistent but unavailable during netsplits (CP)
  • "Eventually" consistent but available during netsplits (AP)
The only other option is "broken after netsplits". The best option is probably AP: this is the approach was pioneered by the Amazon Dynamo system which powered Amazon's shopping cart, and by copycat open source systems like Riak and Cassandra, not that Riak and Cassandra aren't awesome too.