In a semi-recent post we looked at how we might define actors in JRuby using a combination of Akka and code blocks. That post was very focused on the process of creating actors; we didn't necessarily consider how to build systems with actors and/or whether Ruby might be helpful in doing so. There are plenty of issues to ponder here, but before we dig in let's take a step back and talk briefly about some of the characteristics of actors.
Actors implement a shared-nothing model for concurrency. Mutable system state should be contained by one or more actors in the system. This state is not exposed to external entities directly; it can only be accessed or modified via messages sent to the actor. Since the actor is the only player in this drama that can access the state it contains there is no need to lock or synchronize state access. It should be fairly clear that an actor consists of some amount of mutable system state and some logic for handling incoming messages... and not much more.
Okay, sounds great... but how does it work in practice? We'll consider this question by way of an alogrithm that by now should be pretty familiar: prime number generation using the Sieve of Eratosthenes. We considered this chestnut (or perhaps you prefer "war horse" at this point) in a previous post discussing an implementation of this algorithm in the Go language. Let's review that implementation and see what else we can do with it.
The support of lightweight goroutines in Go encouraged a pipeline implementation with one goroutine per discovered prime. We can think of the "state" of this system as the total set of discovered primes. Each goroutine knows only about the prime it contains and the channel where candidates should be sent if they "pass" (i.e. do not divide evenly into it's prime number). Once the goroutine is created it's state doesn't change. New state is added by creating a new goroutine for a newly-discovered prime. State is never deleted; once a prime is discovered removing it from consideration is non-sensical. As a consequence state is completely distributed; no entity in the system knows about all discovered primes.
We also note that the algorithm described here isn't very friendly to parallel decomposition [1]. Candidate values are compared to previously discovered primes one at a time: if the candidate passes the test it's allowed to move on, otherwise no further evaluation occurs. This technique is referred to as "fail-fast" behaviour; if a value fails a test it doesn't lead to any wasteful extra work. The concurrent approach is quite different: compare the candidate to all discovered primes at once and return success only if all tests pass. Comparisons are done independently, so even if the "first" [2] comparison fails all other comparisons still execute. We lose our fail-fast behaviour but gain the ability to decompose the entire process into smaller jobs that can execute in parallel. A trade-off in engineering... surprising, I know.
We'll set out to implement the Sieve of Eratosthenes in Ruby using JRuby and Akka. Our new implementation will have more of a bias towards parallelism; this time we're okay with throwing away some work. Clearly we'll need an actor to compare a candidate to one or more discovered primes; that is, after all, why we're here. We can think of these actors as maintaining the state of our system (just like the goroutines in the Go implementation) so we'll borrow a term from MVC and call these "model" actors. Concurrently evaluating candidates against these models implies an organizing actor that is aware of all models; it seems natural to call this the "controller" actor. To keep things simple we don't want to support an unlimited number of models so we create a fixed-size "pool" and distribute system state (i.e. the set of discovered primes) between these models. When a new prime is discovered the controller will be responsible for adding that prime to an existing model.
The implementation in Ruby looks like this:
Ruby offers a number of features which help us out here. As shown in this implementation messages can be as simple as a list with a leading symbol (used to indicate the message "type") and a payload contained in the remainder of the list. This follows a similar convention found in Erlang, although that language uses tuples rather than lists. Support for destructuring/multiple assignment makes working with these messages quite simple.
Our previous work building actors from code blocks doesn't apply here due to an implementation detail so we define both the controller and model actors as distinct classes. As it turns out this change isn't much of a problem; we're able to implement both classes, a helper Enumerable and a second Enumerable wrapping the controller in less than 140 lines with comments. Full code (including tests) can be found on github.
Spend a little time with JRuby and Akka and it becomes clear that they work well together and form a good basis for building concurrent applications in Ruby.
[1] This is a bit of a loaded statement; you will get some parallelism as multiple candidates move through the "stages" (i.e. goroutines) of the pipeline. That said, this notion of parallelism applies to the system as a whole. The process of determining whether a single candidate is or is not a prime number is still very sequential.
[2] "First" here means nothing more than "whichever test happens to complete and return a value first"
Thursday, January 5, 2012
Friday, November 25, 2011
Musings on List Comprehensions, Functional Programming and Python
For simplicity and elegance in your programming constructs the list comprehension is hard to beat. [1] A list comprehension can filter an input list, transform it or do both, all in a single expression and with very readable syntax. At it's best a list comprehension is "beautiful code" distilled: very clear and expressive with no unnecessary noise. You can, of course, make list comprehensions "ugly" but at least you have to try a bit to do so.
List comprehensions have their roots in functional programming and several modern functional languages include support for them. We'll see comprehensions in Haskell, Clojure and Scala. [2] Python also includes support for comprehensions; in fact the basis for Guido's argument to remove the map and filter functions from py3k was that expressions using these functions could be easily re-written as comprehensions. We also consider comprehensions in Python, including differences between the Python implementation and those in other languages and what effect those differences may have.
Let's consider a fairly straightforward problem problem: given a list of (x,y) coordinates in some two-dimensional space provide a list of the coordinates that are within some fixed distance of the origin of (0,0). Our application also requires that results be displayed in polar coordinates, so for extra bonus points we should return our results in that notation. We can solve the problem quite easily in Haskell and Clojure using list comprehensions:
In Scala we use for expressions to accomplish something very similar:
And finally, a straightforward solution in Python:
Note that in each of these solutions we're doing a bit more work than we need to. Our implementation computes the distance from the origin twice, once when filtering values and again when generating the final output of the transformation process. This seems unnecessary; a better option would be to somehow define this value as intermediate state. This state could then be available to both filter and transform expressions. Haskell and Clojure support the introduction of intermediate bindings in their comprehension syntax:
Scala also allows for intermediate bindings within a for expression:
What about Python? It turns out we cannot solve this problem in Python using a single comprehension; the syntax doesn't allow for the introduction of intermediate state which can be used in either the predicate or transform expression. On the face of it this seems a bit odd; the language encourages the use of comprehensions for filtering and/or transformation while providing a less robust version of that very construct. To some degree this discrepancy reflects differing language goals. Guido's post on the history of list comprehensions seems to indicate that the motivation for adding these features was pragmatic; the syntax is an elegant way to express most filter and transform operations. Functional languages use list comprehensions as "syntactic sugar" for monadic effects [3] that don't really have an equivalent in standard Python usage. The syntax may look the same, but if you're coming from a functional perspective they can feel just a bit off. The same is true for a few other common functional idioms:
A couple things should be noted here. First, let us clearly state that Python is not and does not claim to be a functional programming language. While absolutely true, this fact doesn't change the underlying point. Moving from functional concepts back into Python can be a bit jarring; some things look similar but don't behave quite like you'd expect.
It's also worth noting that the inability to solve this problem with list comprehensions in Python doesn't mean that this problem cannot be solved in idiomatic Python. We wish to return our intermediate state as well as filter results based on it's value; this dual use allows us to solve the problem with nested comprehensions. The inner comprehension will generate the final representation (including the intermediate state) and the outer comprehension will filter results based on that representation. In Python this looks something like:
This works only because the intermediate state is also returned in the final result. If that state were not explicitly returned (i.e. if it's values were used as input to a conditional expression which returned, say, a string value describing the distance) this solution would not apply.
We can also solve this problem using generators. Using the state maintained by the generator we can iterate through the list, compute the intermediate state and yield a value only when we've satisfied our predicate. A generator-based solution would look something like:
Finally, none of these comments should be construed as a criticism of Python, the design choices that went into the language or the inclusion of list comprehensions generally. The pragmatic case for inclusion of this feature seems very strong. This post is interested only in the interplay between these features and similar features in other languages.
[1] Some languages (perhaps most notably Scala) use the term "for comprehension" or "for expression", and in some of these languages (Scala again) these constructs are more flexible than a list comprehension. That said, it's fairly straightforward to make Scala's for expressions behave like conventional list comprehensions.
[2] A purist might object that Scala is designed to mix features of object-oriented and functional languages, but the bias in favor of functional constructs justifies Scala's inclusion here.
[3] As an example, note that in Haskell list comprehensions can be replaced with do-notation. See the Haskell wiki for details.
List comprehensions have their roots in functional programming and several modern functional languages include support for them. We'll see comprehensions in Haskell, Clojure and Scala. [2] Python also includes support for comprehensions; in fact the basis for Guido's argument to remove the map and filter functions from py3k was that expressions using these functions could be easily re-written as comprehensions. We also consider comprehensions in Python, including differences between the Python implementation and those in other languages and what effect those differences may have.
Let's consider a fairly straightforward problem problem: given a list of (x,y) coordinates in some two-dimensional space provide a list of the coordinates that are within some fixed distance of the origin of (0,0). Our application also requires that results be displayed in polar coordinates, so for extra bonus points we should return our results in that notation. We can solve the problem quite easily in Haskell and Clojure using list comprehensions:
In Scala we use for expressions to accomplish something very similar:
And finally, a straightforward solution in Python:
Note that in each of these solutions we're doing a bit more work than we need to. Our implementation computes the distance from the origin twice, once when filtering values and again when generating the final output of the transformation process. This seems unnecessary; a better option would be to somehow define this value as intermediate state. This state could then be available to both filter and transform expressions. Haskell and Clojure support the introduction of intermediate bindings in their comprehension syntax:
Scala also allows for intermediate bindings within a for expression:
What about Python? It turns out we cannot solve this problem in Python using a single comprehension; the syntax doesn't allow for the introduction of intermediate state which can be used in either the predicate or transform expression. On the face of it this seems a bit odd; the language encourages the use of comprehensions for filtering and/or transformation while providing a less robust version of that very construct. To some degree this discrepancy reflects differing language goals. Guido's post on the history of list comprehensions seems to indicate that the motivation for adding these features was pragmatic; the syntax is an elegant way to express most filter and transform operations. Functional languages use list comprehensions as "syntactic sugar" for monadic effects [3] that don't really have an equivalent in standard Python usage. The syntax may look the same, but if you're coming from a functional perspective they can feel just a bit off. The same is true for a few other common functional idioms:
- Lazy evaluation - List comprehensions in Python are not lazily evaluated. Generator expressions, which look very similar to list comprehensions, are lazily evaluated.
- Higher-order functions - Anonymous functions are supported in Python but these functions are famously limited to a single expression. Functions can return functions but for non-trivial functions a named function must be declared and returned.
A couple things should be noted here. First, let us clearly state that Python is not and does not claim to be a functional programming language. While absolutely true, this fact doesn't change the underlying point. Moving from functional concepts back into Python can be a bit jarring; some things look similar but don't behave quite like you'd expect.
It's also worth noting that the inability to solve this problem with list comprehensions in Python doesn't mean that this problem cannot be solved in idiomatic Python. We wish to return our intermediate state as well as filter results based on it's value; this dual use allows us to solve the problem with nested comprehensions. The inner comprehension will generate the final representation (including the intermediate state) and the outer comprehension will filter results based on that representation. In Python this looks something like:
This works only because the intermediate state is also returned in the final result. If that state were not explicitly returned (i.e. if it's values were used as input to a conditional expression which returned, say, a string value describing the distance) this solution would not apply.
We can also solve this problem using generators. Using the state maintained by the generator we can iterate through the list, compute the intermediate state and yield a value only when we've satisfied our predicate. A generator-based solution would look something like:
Finally, none of these comments should be construed as a criticism of Python, the design choices that went into the language or the inclusion of list comprehensions generally. The pragmatic case for inclusion of this feature seems very strong. This post is interested only in the interplay between these features and similar features in other languages.
[1] Some languages (perhaps most notably Scala) use the term "for comprehension" or "for expression", and in some of these languages (Scala again) these constructs are more flexible than a list comprehension. That said, it's fairly straightforward to make Scala's for expressions behave like conventional list comprehensions.
[2] A purist might object that Scala is designed to mix features of object-oriented and functional languages, but the bias in favor of functional constructs justifies Scala's inclusion here.
[3] As an example, note that in Haskell list comprehensions can be replaced with do-notation. See the Haskell wiki for details.
Monday, September 12, 2011
Ruby and Concurrency: The Mechanics of Akka and JRuby
I'm interested in concurrency. I'm also interested in Ruby. There doesn't seem to be much reason to keep these two guys apart anymore.
This post marks the beginning of an occasional series on the topic of using Ruby to write concurrent code. Ruby doesn't yet have a big reputation in the world of concurrent and/or parallel applications, but there is some interesting work being done in this space. And since problems in concurrency are notoriously difficult to reason about we could probably do a lot worse than attempt to address those problems in a language designed to make life easier for the developer.
We begin with Akka, an excellent library designed to bring actors, actor coordination and STM to Scala and, to a slightly lesser degree, the JVM generally. Our initial task is simple: we wish to be able to define an Akka actor by providing a message handler as a code block. We'll start by attempting to implement the actor as a standalone class and then abstract that solution into code which requires the input block and nothing else.
A simple initial implementation looks something like this:
Well, that didn't work very well. Apparently the class we defined in JRuby is being exposed to the Java lib as a proxy object and that proxy's class is unknown to the Akka runtime. No problem; Akka supports a factory model for actor creation, and by using that approach the underlying class of our actor should become a non-issue. With a few simple changes we're ready to try again:
We now have a working actor, but we still have some work to do; remember, we want to be able to define arbitrary actors by supplying just a code block. We need a few additional pieces to make this work:
A first cut at this concept might look something like this:
What went wrong here? UntypedActor is a concrete class with a defined no-arg constructor. That constructor is being called in favor of the one we've provided, and as a consequence our block never gets into the mix. There's almost certainly a cleaner way to solve this using JRuby, but for the moment we can get around the problem (in an admittedly ugly way) by providing a setter on our generic actor class:
We now have what we wanted.
If you're interested in this topic note that Nick Sieger has covered similar ground (including the interaction between JRuby and Akka) here. Nick's article draws on some very good work done by Daniel Ribeiro late last year. The code referenced in Daniel's article is available on Github. I didn't come across Daniel's post until my own was nearly done but there is quite a bit of overlap between his code and mine. That said, I recommend taking a look at both articles, if for no other reason than the fact that both authors are much better at writing Ruby code than I am.
This post marks the beginning of an occasional series on the topic of using Ruby to write concurrent code. Ruby doesn't yet have a big reputation in the world of concurrent and/or parallel applications, but there is some interesting work being done in this space. And since problems in concurrency are notoriously difficult to reason about we could probably do a lot worse than attempt to address those problems in a language designed to make life easier for the developer.
We begin with Akka, an excellent library designed to bring actors, actor coordination and STM to Scala and, to a slightly lesser degree, the JVM generally. Our initial task is simple: we wish to be able to define an Akka actor by providing a message handler as a code block. We'll start by attempting to implement the actor as a standalone class and then abstract that solution into code which requires the input block and nothing else.
A simple initial implementation looks something like this:
[@varese ruby]$ ruby --version
jruby 1.6.2 (ruby-1.8.7-p330) (2011-05-23 e2ea975) (OpenJDK Client VM 1.6.0_22) [linux-i386-java]
[@varese ruby]$ ruby akka_sample1.rb
ArgumentError: Constructor invocation failed: ActorRef for instance of actor [org.jruby.proxy.akka.actor.UntypedActor$Proxy0] is not in scope.
You can not create an instance of an actor explicitly using 'new MyActor'.
You have to use one of the factory methods in the 'Actor' object to create a new actor.
Either use:
'val actor = Actor.actorOf[MyActor]', or
'val actor = Actor.actorOf(new MyActor(..))'
(root) at akka_sample1.rb:20
Well, that didn't work very well. Apparently the class we defined in JRuby is being exposed to the Java lib as a proxy object and that proxy's class is unknown to the Akka runtime. No problem; Akka supports a factory model for actor creation, and by using that approach the underlying class of our actor should become a non-issue. With a few simple changes we're ready to try again:
[@varese ruby]$ ruby akka_sample2.rb
Received message: foo
We now have a working actor, but we still have some work to do; remember, we want to be able to define arbitrary actors by supplying just a code block. We need a few additional pieces to make this work:
- A generic actor implementation whose state includes a block or Proc instance. The onReceive method of this actor could then simply call the contained block/Proc, passing the input message as an arg.
- An ActorFactory implementation which takes a code block as an arg, stores it in internal state and then uses that block to build an instance of the generic actor described above on demand.
A first cut at this concept might look something like this:
[@varese ruby]$ ruby akka_sample3.rb
ArgumentError: wrong number of arguments for constructor
create at akka_sample3.rb:29
(root) at akka_sample3.rb:37
What went wrong here? UntypedActor is a concrete class with a defined no-arg constructor. That constructor is being called in favor of the one we've provided, and as a consequence our block never gets into the mix. There's almost certainly a cleaner way to solve this using JRuby, but for the moment we can get around the problem (in an admittedly ugly way) by providing a setter on our generic actor class:
[@varese ruby]$ ruby akka_sample4.rb
Message recieved: foo
We now have what we wanted.
If you're interested in this topic note that Nick Sieger has covered similar ground (including the interaction between JRuby and Akka) here. Nick's article draws on some very good work done by Daniel Ribeiro late last year. The code referenced in Daniel's article is available on Github. I didn't come across Daniel's post until my own was nearly done but there is quite a bit of overlap between his code and mine. That said, I recommend taking a look at both articles, if for no other reason than the fact that both authors are much better at writing Ruby code than I am.
Friday, September 2, 2011
Cassandra and Clojure: Things To Bytes And Back Again
In a previous post we briefly discussed the idea of using idiomatic Clojure to access data contained in a Cassandra instance, including transparent conversion to and from Clojure data. We'll explore an implementation of this idea, although we won't address the question of laziness, in part because there are sizable trade-offs to consider. For example, any solution that provides lazy evaluation must do so while also attempting to minimize the number of trips to the underlying data store. This question may be picked up in yet more future work, but for now we'll continue on. We've upgraded to Cassandra 0.8.2 and Clojure 1.2, and we're using a new data model (see below), but for the most part we'll try to pick up where we left off.
At the core the Cassandra data model is centered around columns. Each of these columns contains both a name and a value, both of which are represented as binary data. This model is very simple, and while it may appear limiting it is in reality quite flexible. The lack of any pre-defined data types avoids any "impedance mismatch" resulting from structured data being shoehorned into data types that don't really fit. We're free to represent column values in any way we see fit; if we can convert it into bytes it's fair game. Our problem thus devolves into a question of serialization, and suddenly there are many suitors vying for our attention. Among the set of well-known serialization packages we find Google's Protocol Buffers, Thrift and Avro. And since we're working in a language with good Java interop we can always have Java's built-in serialization (or something similar like Kryo) available. Finally we're always free to roll our own.
Let's begin by ruling out that last idea. There are already well-tested third-party serialization libraries so unless we believe that all of them suffer from some fatal error it's difficult to justify the risk and expense of creating something new. We'd also like our approach to have some level of cross-platform support so native Java serialization is excluded (along with Kryo). We also need to be able to encode and decode arbitrary data without defining message types or their payload(s) in advance, a limitation that rules out Protocol Buffers and Thrift. The last man standing is Avro, and fortunately for us he's a good candidate. Avro is schema-based but the library includes facilities for generating schemas on the fly by inspecting objects via Java reflection. Also included is a notion of storing schemas with data, allowing the original object to be easily reconstructed as needed. The Avro data model includes a rich set of basic types as well as support for "complex" types such as arrays and maps.
We'll need to implement a Clojure interface into the Avro functionality; this can be as simple as methods to encode and decode data and schemas. At least some implementations of Avro data files use a pre-defined "meta-schema" (consisting of the schema for the embedded data and that data itself) for storing both items. Consumers of these files first decode the meta-schema then use the discovered schema to decode the underlying data. We'll follow a similar path for our library. We'll also extend our Cassandra support a bit in order to support the insertion of new columns for a given key and column family.
Our core example will be built around a collection of employee records. We want to create a report on these employees using attributes defined in various well-known columns. We'd like to access the values in these columns as simple data types (booleans, integers, perhaps even an array or a map) but we'd like to do so through a uniform interface. We don't want to access certain columns in certain ways, as if we "knew" that a specific column contained data of a specific type. Any such approach is by definition brittle if the underlying data model should shift in flight (as data models are known to do).
After finishing up with our Clojure libraries we implement a simple app for populating our Cassandra instance with randomly-generated employee information:
We're now ready to create our reporting application. Using Avro and a consistent meta-schema this comes off fairly easily:
And in order to verify our assumptions about simple cross-platform support we create a Ruby version of something very much like our reporting application:
This code meets our basic requirement, but as always there were a few stumbling blocks along the way. Avro includes strings as a primitive type, but unfortunately the Java API (which we leverage for our Clojure code) returns string instances as a Utf8 type. We can get a java.lang.String from these objects, but unfortunately we need another toString() method call that (logically) is completely unnecessary. We also don't fully support complex types. The Avro code maps the Clojure classes representing arrays and maps onto a "record" type that includes the various fields exposed via getters. Supporting these types requires the ability to reconstruct the underlying object based on these fields, and doing so reliably is beyond the scope of this work. Finally, we were forced to use Ruby 1.8.x for the Ruby examples since the Avro gem apparently doesn't yet support 1.9.
Full code can be found on github.
At the core the Cassandra data model is centered around columns. Each of these columns contains both a name and a value, both of which are represented as binary data. This model is very simple, and while it may appear limiting it is in reality quite flexible. The lack of any pre-defined data types avoids any "impedance mismatch" resulting from structured data being shoehorned into data types that don't really fit. We're free to represent column values in any way we see fit; if we can convert it into bytes it's fair game. Our problem thus devolves into a question of serialization, and suddenly there are many suitors vying for our attention. Among the set of well-known serialization packages we find Google's Protocol Buffers, Thrift and Avro. And since we're working in a language with good Java interop we can always have Java's built-in serialization (or something similar like Kryo) available. Finally we're always free to roll our own.
Let's begin by ruling out that last idea. There are already well-tested third-party serialization libraries so unless we believe that all of them suffer from some fatal error it's difficult to justify the risk and expense of creating something new. We'd also like our approach to have some level of cross-platform support so native Java serialization is excluded (along with Kryo). We also need to be able to encode and decode arbitrary data without defining message types or their payload(s) in advance, a limitation that rules out Protocol Buffers and Thrift. The last man standing is Avro, and fortunately for us he's a good candidate. Avro is schema-based but the library includes facilities for generating schemas on the fly by inspecting objects via Java reflection. Also included is a notion of storing schemas with data, allowing the original object to be easily reconstructed as needed. The Avro data model includes a rich set of basic types as well as support for "complex" types such as arrays and maps.
We'll need to implement a Clojure interface into the Avro functionality; this can be as simple as methods to encode and decode data and schemas. At least some implementations of Avro data files use a pre-defined "meta-schema" (consisting of the schema for the embedded data and that data itself) for storing both items. Consumers of these files first decode the meta-schema then use the discovered schema to decode the underlying data. We'll follow a similar path for our library. We'll also extend our Cassandra support a bit in order to support the insertion of new columns for a given key and column family.
Our core example will be built around a collection of employee records. We want to create a report on these employees using attributes defined in various well-known columns. We'd like to access the values in these columns as simple data types (booleans, integers, perhaps even an array or a map) but we'd like to do so through a uniform interface. We don't want to access certain columns in certain ways, as if we "knew" that a specific column contained data of a specific type. Any such approach is by definition brittle if the underlying data model should shift in flight (as data models are known to do).
After finishing up with our Clojure libraries we implement a simple app for populating our Cassandra instance with randomly-generated employee information:
[varese clojure]$ ~/local/bin/clojure add_employee_data.clj
Added user gFc0pVnLKPnjrrLx: [158 true [77 73 99 58 31 64 1 37 70 69]]
Added user 5gGh9anHwFINpr5t: [459 true [34 71 28 1 2 84 11 33 37 28]]
Added user pGRMeXBTFoBIWhud: [945 true [45 83 51 45 11 4 80 68 73 27]]
...
We're now ready to create our reporting application. Using Avro and a consistent meta-schema this comes off fairly easily:
[varese clojure]$ ~/local/bin/clojure get_employee_data.clj
Found 10 users
Username: 5gGh9anHwFINpr5t
Userid: 459
Userid is greater than zero
Active: true
User is active
...
And in order to verify our assumptions about simple cross-platform support we create a Ruby version of something very much like our reporting application:
[varese 1.8]$ ruby get_employee_data.rb
Username: 5gGh9anHwFINpr5t, user ID: 459, active: true
User ID is greater than zero
User is active
Username: 76v8iEJcc79Huj9L, user ID: 469, active: false
User ID is greater than zero
User is not active
...
This code meets our basic requirement, but as always there were a few stumbling blocks along the way. Avro includes strings as a primitive type, but unfortunately the Java API (which we leverage for our Clojure code) returns string instances as a Utf8 type. We can get a java.lang.String from these objects, but unfortunately we need another toString() method call that (logically) is completely unnecessary. We also don't fully support complex types. The Avro code maps the Clojure classes representing arrays and maps onto a "record" type that includes the various fields exposed via getters. Supporting these types requires the ability to reconstruct the underlying object based on these fields, and doing so reliably is beyond the scope of this work. Finally, we were forced to use Ruby 1.8.x for the Ruby examples since the Avro gem apparently doesn't yet support 1.9.
Full code can be found on github.
Tuesday, August 2, 2011
A Short Folding Note
Or maybe that's "a short note on folding"
While reading through Real World Haskell a short code snippet got me thinking about folds. Chapter 4, devoted to functional programming in general, uses a brief example built around the tails function to illustrate Haskell's as-patterns. This function makes it's home in the Data.List module and, given an input string s, will return a list of all results of tail x where x is a sublist of s. It's a bit convoluted to describe in prose, but the example offered by O'Sullivan et. al. makes it clear:
Maybe it was the fact that this function was introduced just after a lengthy discussion on left and right folds in the same chapter. Maybe it was due to an uptick in my use of folds when working with Scala. Whatever the cause, a thought grabbed hold of me: this function should be easy to implement by folding, shouldn't it? Unfortunately my previous attempt to sit down with Haskell code didn't quite work out as expected. Throw in a new FC 15 install (and all the goodies it contains) and there was no end of temptation for the unfocused. Fortunately good sense prevailed: GHC was installed, Chicken Scheme was not and it was time to start.
My intuition turned out to be correct; a version using foldl came together fairly quickly:
The overall algorithm used here is fairly straightforward. Beginning with an empty list we move left to right and do two things with every character c we find:
Visualizing the "left to right" evaluation of foldl gives us something like the following:
The result is exactly what we expect:
So we now have foldl... what about foldr? At this point I must offer a confession; left folds have always seemed intuitive to me while right folds most definitely have not. A left fold appears to be equivalent to a simple traversal of a list from "start" to "finish", gathering data as you move along. A right folds seems artificial somehow, like some kind of inside-out list traversal. And while a simple mental model for right folds remains somewhat elusive working through this sample did ease the pain somewhat. It took a bit of work, but after getting a handle on the order of evaluation a working implementation emerged:
This algorithm is a mirror image of the one used with foldl; since we're moving right to left we have to build member strings from back to front. For every new character c we build a new string by appending c to the largest string in the accumulator. We then return a new list with the new string for a head and the old accumulator for a tail. Note that we have to account for the empty list case when evaluating the first expression. Using this version on our test string we get:
Interestingly, while struggling to come to terms with right folds a related function presented itself. Taking the algorithm used in the left fold case and applying it directly to a right fold yields a function that might be called antitails. More precisely, for an input string s this function returns a list of strings (s - t) for every t in tails s.
The logic behind this operation looks something like the following:
Finally, it should be noted that the actual implementation of tails in GHC appears to be a recursive definition built around... as-patterns.
While reading through Real World Haskell a short code snippet got me thinking about folds. Chapter 4, devoted to functional programming in general, uses a brief example built around the tails function to illustrate Haskell's as-patterns. This function makes it's home in the Data.List module and, given an input string s, will return a list of all results of tail x where x is a sublist of s. It's a bit convoluted to describe in prose, but the example offered by O'Sullivan et. al. makes it clear:
[@varese ~]$ ghci
...
*Main> :m +Data.List
*Main Data.List> tails "foobar"
["foobar","oobar","obar","bar","ar","r",""]
Maybe it was the fact that this function was introduced just after a lengthy discussion on left and right folds in the same chapter. Maybe it was due to an uptick in my use of folds when working with Scala. Whatever the cause, a thought grabbed hold of me: this function should be easy to implement by folding, shouldn't it? Unfortunately my previous attempt to sit down with Haskell code didn't quite work out as expected. Throw in a new FC 15 install (and all the goodies it contains) and there was no end of temptation for the unfocused. Fortunately good sense prevailed: GHC was installed, Chicken Scheme was not and it was time to start.
My intuition turned out to be correct; a version using foldl came together fairly quickly:
The overall algorithm used here is fairly straightforward. Beginning with an empty list we move left to right and do two things with every character c we find:
- Create a new string in our accumulator list containing c
- Add c to every string already in the accumulator
Visualizing the "left to right" evaluation of foldl gives us something like the following:
- r1 = append 'f' to every string in [] and add string 'f'
- r2 = append 'o' to every string in r1 and add string 'o'
- r3 = append 'o' to every string in r2 and add string 'o'
The result is exactly what we expect:
*Main> mytailsl "foobar"
["foobar","oobar","obar","bar","ar","r",""]
So we now have foldl... what about foldr? At this point I must offer a confession; left folds have always seemed intuitive to me while right folds most definitely have not. A left fold appears to be equivalent to a simple traversal of a list from "start" to "finish", gathering data as you move along. A right folds seems artificial somehow, like some kind of inside-out list traversal. And while a simple mental model for right folds remains somewhat elusive working through this sample did ease the pain somewhat. It took a bit of work, but after getting a handle on the order of evaluation a working implementation emerged:
This algorithm is a mirror image of the one used with foldl; since we're moving right to left we have to build member strings from back to front. For every new character c we build a new string by appending c to the largest string in the accumulator. We then return a new list with the new string for a head and the old accumulator for a tail. Note that we have to account for the empty list case when evaluating the first expression. Using this version on our test string we get:
*Main> mytailsr "foobar"
["foobar","oobar","obar","bar","ar","r",""]
Interestingly, while struggling to come to terms with right folds a related function presented itself. Taking the algorithm used in the left fold case and applying it directly to a right fold yields a function that might be called antitails. More precisely, for an input string s this function returns a list of strings (s - t) for every t in tails s.
*Main> reverse (antitails "foobar")
["","f","fo","foo","foob","fooba","foobar"]
*Main> mytailsl "foobar"
["foobar","oobar","obar","bar","ar","r",""]
The logic behind this operation looks something like the following:
Finally, it should be noted that the actual implementation of tails in GHC appears to be a recursive definition built around... as-patterns.
Wednesday, July 27, 2011
Min, max and MongoDB
What else can we say about MongoDB? Sure, we could talk about built-in map-reduce or the expressive query language or
journaling and sharding improvements in 1.8. But all of this is by now well-travelled territory, and that's a good thing. In addition to the features in the database itself 10gen and the community have done yeoman work in producing a rich collection of documentation describing MongoDB. This collection includes the MongoDB cookbook, and within that cookbook is a recipe illustrating how to find the maximum and minimum values of a field within a MongoDB collection using map-reduce. And that's where the problem started.
Solving this problem with map-reduce seems like entirely the wrong approach to me, although admittedly I'm new here. A solution using map-reduce must (almost by definition) access every document within the collection. This kind of approach makes sense if we're interested in max and min values for every key in the collection. But if we're only interested in one key (or some small subset of keys) this approach has us doing more work than we need to. MongoDB has strong support for indexes within a collection; we should be able to leverage these indexes to increase efficiency by reviewing only the keys we're interested in.
In order to make this work we need to be able to retrieve a max or min using only MongoDB's query language. We begin by finding all documents that match the target key or keys. We then sort these documents in descending or ascending order depending on whether we're after the max or min (respectively). We then limit our search results to contain no more than one element: this element must be the max or min value for the specified field.
To try this out, we expand upon the example (used in the cookbook) of blog posts, each of which has an author field, some content and a page_count field for tracking hits on each article. To make things interesting we create a large sample data set: 10,000 distinct authors, each of whom have written 100 posts. Each post has been viewed less than 2000 times. We want to compute the max and min page views for a given author.
The following Ruby script generates a set of random data for us, storing that data in a set of YAML files to enable repeated load operations:
We use the following Ruby script to load the data in these YAML files into our MongoDB instance:
Now that the data's loaded we move on to our queries. Let's start with the map-reduce approach, just to verify that it behaves as we expect. We'll start off with the mongo shell and re-use the map and reduce functions defined in the cookbook entry:
We expect this operation to access every document in the database. To provide a reference point we execute a query to count all documents before performing the map-reduce:
As expected we get the max and min values for all authors. And also as expected we have to look at every document to do it. Can we do any better with queries? Not right off the bat:
A simple index on authors does help us out:
We're now evaluating only the documents representing blog posts by the named author. This approach is clearly more performant for gathering per-author max and min values. In fact, at 64 ms per authors we're only four times slower than the map-reduce approach if we wished to gather values for all 10,000 authors. But we can do better. MongoDB's support for compound key indexes offers an additional speedup:
Clearly for any single author (or reasonably small subset of authors) this is the approach to use. For that matter 6 ms/author is approximately three times faster than the map-reduce operation over the entire collection. That said, the comparison isn't as clear cut as it appears. Any attempt to replace the map-reduce approach would have to find the set of all distinct authors, and any such query would also have to evaluate all documents in the collection.
Of course we don't get this speedup for free. Index maintenance does impose some overhead, although it's not as bad as you might think. Loading the generated data to a MongoDB instance with no indexes looks something like the following:
If we add the indexes in advance and then load the data we see this instead:
Samples above use MongoDB 1.8.2 and MRI 1.9.2p180 (via RVM) on FC 13.
journaling and sharding improvements in 1.8. But all of this is by now well-travelled territory, and that's a good thing. In addition to the features in the database itself 10gen and the community have done yeoman work in producing a rich collection of documentation describing MongoDB. This collection includes the MongoDB cookbook, and within that cookbook is a recipe illustrating how to find the maximum and minimum values of a field within a MongoDB collection using map-reduce. And that's where the problem started.
Solving this problem with map-reduce seems like entirely the wrong approach to me, although admittedly I'm new here. A solution using map-reduce must (almost by definition) access every document within the collection. This kind of approach makes sense if we're interested in max and min values for every key in the collection. But if we're only interested in one key (or some small subset of keys) this approach has us doing more work than we need to. MongoDB has strong support for indexes within a collection; we should be able to leverage these indexes to increase efficiency by reviewing only the keys we're interested in.
In order to make this work we need to be able to retrieve a max or min using only MongoDB's query language. We begin by finding all documents that match the target key or keys. We then sort these documents in descending or ascending order depending on whether we're after the max or min (respectively). We then limit our search results to contain no more than one element: this element must be the max or min value for the specified field.
To try this out, we expand upon the example (used in the cookbook) of blog posts, each of which has an author field, some content and a page_count field for tracking hits on each article. To make things interesting we create a large sample data set: 10,000 distinct authors, each of whom have written 100 posts. Each post has been viewed less than 2000 times. We want to compute the max and min page views for a given author.
The following Ruby script generates a set of random data for us, storing that data in a set of YAML files to enable repeated load operations:
We use the following Ruby script to load the data in these YAML files into our MongoDB instance:
Now that the data's loaded we move on to our queries. Let's start with the map-reduce approach, just to verify that it behaves as we expect. We'll start off with the mongo shell and re-use the map and reduce functions defined in the cookbook entry:
We expect this operation to access every document in the database. To provide a reference point we execute a query to count all documents before performing the map-reduce:
[@varese mongo_ruby]$ ~/local/mongodb/bin/mongo
MongoDB shell version: 1.8.2
connecting to: test
> use indexing
switched to db indexing
> db.indexing.count()
1010000
> db.indexing.mapReduce(map,reduce,{out: {inline:true}})
...
{
"_id" : "Zzxpnsnqjskpvpfwtpyeexpr",
"value" : {
"min" : {
"page_views" : 16,
"_id" : ObjectId("4e2fa865e8f06a08850b5735")
},
"max" : {
"page_views" : 1974,
"_id" : ObjectId("4e2fa865e8f06a08850b5709")
}
}
}
],
"timeMillis" : 177968,
"counts" : {
"input" : 1010000,
"emit" : 1010000,
"output" : 10000
},
"ok" : 1,
}
As expected we get the max and min values for all authors. And also as expected we have to look at every document to do it. Can we do any better with queries? Not right off the bat:
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':-1}).limit(1)
{ "_id" : ObjectId("4e2fa865e8f06a08850b5709"), "author" : "Zzxpnsnqjskpvpfwtpyeexpr", "page_views" : 1974, "content" : "The quick brown fox jumped over the lazy dog" }
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':1}).limit(1)
{ "_id" : ObjectId("4e2fa865e8f06a08850b5735"), "author" : "Zzxpnsnqjskpvpfwtpyeexpr", "page_views" : 16, "content" : "The quick brown fox jumped over the lazy dog" }
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':-1}).limit(1).explain()
{
"cursor" : "BasicCursor",
"nscanned" : 1010000,
"nscannedObjects" : 1010000,
...
"millis" : 1774,
...
}
A simple index on authors does help us out:
> db.indexing.ensureIndex({'author':1})
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':-1}).limit(1).explain()
{
"cursor" : "BtreeCursor author_1",
"nscanned" : 101,
"nscannedObjects" : 101,
...
"millis" : 64,
...
}
We're now evaluating only the documents representing blog posts by the named author. This approach is clearly more performant for gathering per-author max and min values. In fact, at 64 ms per authors we're only four times slower than the map-reduce approach if we wished to gather values for all 10,000 authors. But we can do better. MongoDB's support for compound key indexes offers an additional speedup:
> db.indexing.ensureIndex({'author':1,'page_views':-1})
> db.indexing.ensureIndex({'author':1,'page_views':1})
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':-1}).limit(1).explain()
{
"cursor" : "BtreeCursor author_1_page_views_-1",
"nscanned" : 1,
"nscannedObjects" : 1,
...
"millis" : 6,
...
}
Clearly for any single author (or reasonably small subset of authors) this is the approach to use. For that matter 6 ms/author is approximately three times faster than the map-reduce operation over the entire collection. That said, the comparison isn't as clear cut as it appears. Any attempt to replace the map-reduce approach would have to find the set of all distinct authors, and any such query would also have to evaluate all documents in the collection.
Of course we don't get this speedup for free. Index maintenance does impose some overhead, although it's not as bad as you might think. Loading the generated data to a MongoDB instance with no indexes looks something like the following:
[@varese mongo_ruby]$ time ruby load_data.rb
Loading data from file random_data_part01.yaml
...
Loading data from file random_data_part20.yaml
real 7m11.191s
user 0m6.410s
sys 4m25.909s
[@varese mongo_ruby]$ ~/local/mongodb/bin/mongo
MongoDB shell version: 1.8.2
connecting to: test
> use indexing
switched to db indexing
> db.indexing.count()
1010000
If we add the indexes in advance and then load the data we see this instead:
[@varese mongo_ruby]$ ~/local/mongodb/bin/mongo
MongoDB shell version: 1.8.2
connecting to: test
> use indexing
switched to db indexing
> db.indexing.count()
0
> db.indexing.ensureIndex({'author':1})
> db.indexing.ensureIndex({'author':1,'page_views':1})
> db.indexing.ensureIndex({'author':1,'page_views':-1})
> bye
[@varese mongo_ruby]$ time ruby load_data.rb
Loading data from file random_data_part01.yaml
...
Loading data from file random_data_part20.yaml
real 8m39.601s
user 0m4.208s
sys 4m18.249s
[@varese mongo_ruby]$ ~/local/mongodb/bin/mongo
MongoDB shell version: 1.8.2
connecting to: test
> use indexing
switched to db indexing
> db.indexing.count()
1010000
> db.indexing.find({'author':'Zzxpnsnqjskpvpfwtpyeexpr'}).sort({'page_views':-1}).limit(1).explain()
{
"cursor" : "BtreeCursor author_1_page_views_1 reverse",
"nscanned" : 1,
"nscannedObjects" : 1,
...
"millis" : 3,
...
}
Samples above use MongoDB 1.8.2 and MRI 1.9.2p180 (via RVM) on FC 13.
Sunday, June 19, 2011
First steps from node.js to concurrent JavaScript
I've always been somewhat ambivalent about node.js.
The project has received praise for advancing the idea of event-based server development. This argument never seemed terribly persuasive; Twisted and Event Machine (among others) have been plowing that soil for some time now and it's not clear that node.js adds anything new in this space. This does not mean that the project has made no contribution. The most impressive accomplishment of node.js has been to show what JavaScript can do when let out of it's browser-shaped cage. Crockford and others have put in a considerable amount of work to demonstrate that there's a fully-formed programming language hiding behind the event handlers and DOM manipulation. node.js provides further evidence that they were right all along.
The functional side of JavaScript (anonymous functions and/or closures specifically) lends itself to asynchronous network programming. But what about other paradigms? Suppose we're writing a concurrent application with multiple synchronous "threads" [1] of control. Let's further suppose that these "threads" implement a share-nothing architecture and communicate via messaging. Does JavaScript have anything to offer our application? We would expect the answer to be "yes"; in addition to anonymous functions/closures serving as message handlers we might also lean on the easy creation of arbitrary objects to achieve something resembling Erlang's tuples. But that's just speculation. In order to know for sure we should try our model on an actual concurrent problem or two.
But let's not get too far ahead of ourselves. Before we dig into any samples we should probably define our framework. We'll start with the Go language. Go's support for lightweight processes (i.e. goroutines) maps naturally onto the "threads" we refer to above so it's a natural match for our problem space. We can also easily define our goal in terms of goroutines: we wish to create the ability to implement a goroutine in JavaScript. Finally, Go's built-in support for native code should facilitate interaction with our JavaScript engine. While we're on that subject, we'll follow the lead of node.js and use v8 as our JavaScript implementation.
The ability to implement goroutines in JavaScript requires at least three components:
We begin with the execution of JavaScript from within Go. The language supports good integration with C code, but v8 is written in C++. A few previous efforts work around this mismatch by way of a C shim into the C++ code. This works but seems somewhat artificial. Go now supports the use of SWIG to interact with C++; in fact it's the recommended method for interacting with C++ code. We'll start there and see where it takes us.
Initially we try to expose the various C++ structures referenced in the v8 sample documentation to Go via SWIG, but this approach rapidly runs aground for a couple of reasons. First, the v8 API includes a few stack-allocated data structures which won't persist across SWIG calls. Second, the API also makes some use of nested C++ classes, a feature not yet supported by SWIG [2]. So we shift gears a bit; we should be able to define a set of classes and/or static functions which can do the heavy lifting for us. This approach enables us to execute JavaScript, but unfortunately we can't easily bind Go objects or expose Go code in the JS environment. v8 does allow us to define C++ functions that can be made available to that environment, but unfortunately SWIG can only expose C/C++ code to higher level languages; it can't do the inverse. As a consequence there's no way to make any C++ function we inject aware of the Go code that's interacting with it. JavaScript code thus cannot interact with channels, so at the moment the best we can do is to return a value from our JavaScript function which can then be accessed from within the Go code.
The above code was built with SWIG 2.0.4. Full code can be found on github.
This technique works but isn't very satisfying. We don't have communication via channels, which in turn prevents us from having long-running JavaScript as our goroutine. We're also constrained to returning strings from our JavaScript functions, hardly a general purpose solution. We'll try to move past these limitations in future work.
[1] Think "thread of execution" rather than something your operating system might recognize
[2] There are some workarounds but nothing that seemed viable for our purposes
The project has received praise for advancing the idea of event-based server development. This argument never seemed terribly persuasive; Twisted and Event Machine (among others) have been plowing that soil for some time now and it's not clear that node.js adds anything new in this space. This does not mean that the project has made no contribution. The most impressive accomplishment of node.js has been to show what JavaScript can do when let out of it's browser-shaped cage. Crockford and others have put in a considerable amount of work to demonstrate that there's a fully-formed programming language hiding behind the event handlers and DOM manipulation. node.js provides further evidence that they were right all along.
The functional side of JavaScript (anonymous functions and/or closures specifically) lends itself to asynchronous network programming. But what about other paradigms? Suppose we're writing a concurrent application with multiple synchronous "threads" [1] of control. Let's further suppose that these "threads" implement a share-nothing architecture and communicate via messaging. Does JavaScript have anything to offer our application? We would expect the answer to be "yes"; in addition to anonymous functions/closures serving as message handlers we might also lean on the easy creation of arbitrary objects to achieve something resembling Erlang's tuples. But that's just speculation. In order to know for sure we should try our model on an actual concurrent problem or two.
But let's not get too far ahead of ourselves. Before we dig into any samples we should probably define our framework. We'll start with the Go language. Go's support for lightweight processes (i.e. goroutines) maps naturally onto the "threads" we refer to above so it's a natural match for our problem space. We can also easily define our goal in terms of goroutines: we wish to create the ability to implement a goroutine in JavaScript. Finally, Go's built-in support for native code should facilitate interaction with our JavaScript engine. While we're on that subject, we'll follow the lead of node.js and use v8 as our JavaScript implementation.
The ability to implement goroutines in JavaScript requires at least three components:
- Obviously we require the ability to execute arbitrary JavaScript from within a Go program
- We'll also need to add bindings to the v8 environment from within Go. This allows us to pass channels and other objects into the JavaScript code
- JavaScript code running in v8 should be able to interact with Go code. Our JavaScript goroutines must be able to send and receive messages from Go channels
We begin with the execution of JavaScript from within Go. The language supports good integration with C code, but v8 is written in C++. A few previous efforts work around this mismatch by way of a C shim into the C++ code. This works but seems somewhat artificial. Go now supports the use of SWIG to interact with C++; in fact it's the recommended method for interacting with C++ code. We'll start there and see where it takes us.
Initially we try to expose the various C++ structures referenced in the v8 sample documentation to Go via SWIG, but this approach rapidly runs aground for a couple of reasons. First, the v8 API includes a few stack-allocated data structures which won't persist across SWIG calls. Second, the API also makes some use of nested C++ classes, a feature not yet supported by SWIG [2]. So we shift gears a bit; we should be able to define a set of classes and/or static functions which can do the heavy lifting for us. This approach enables us to execute JavaScript, but unfortunately we can't easily bind Go objects or expose Go code in the JS environment. v8 does allow us to define C++ functions that can be made available to that environment, but unfortunately SWIG can only expose C/C++ code to higher level languages; it can't do the inverse. As a consequence there's no way to make any C++ function we inject aware of the Go code that's interacting with it. JavaScript code thus cannot interact with channels, so at the moment the best we can do is to return a value from our JavaScript function which can then be accessed from within the Go code.
[@varese v8-golang]$ make buildshell
swig -c++ -go v8wrapper.i
g++ -c -I/home/fencepost/svn/v8/include -fpic v8wrapper.cc
g++ -c -I/home/fencepost/svn/v8/include -fpic v8wrapper_wrap.cxx
g++ -shared -L/home/fencepost/svn/v8 v8wrapper_wrap.o v8wrapper.o -o v8.so -lv8
8g v8.go
8c -I/home/fencepost/hg/go/src/pkg/runtime v8_gc.c
gopack grc v8.a v8.8 v8_gc.8
8g -I. v8shell.go
8l -L . -r . -o v8shell v8shell.8
[@varese v8-golang]$ more fib.js
// Simple accumulator-based Fibonacci implementation
function fib(a,b,count) {
function _fib(_a,_b,_count,_accum) {
if (_count <= 0) {
return _accum;
}
var n = _a + _b;
return _fib(_b,n,(_count - 1),_accum + "," + n);
}
return _fib(a,b,(count - 2),a + "," + b);
}
fib(0,1,10);
[@varese v8-golang]$ ./v8shell -script=fib.js
Using JavaScript file: fib.js
Result: 0,1,1,2,3,5,8,13,21,34
The above code was built with SWIG 2.0.4. Full code can be found on github.
This technique works but isn't very satisfying. We don't have communication via channels, which in turn prevents us from having long-running JavaScript as our goroutine. We're also constrained to returning strings from our JavaScript functions, hardly a general purpose solution. We'll try to move past these limitations in future work.
[1] Think "thread of execution" rather than something your operating system might recognize
[2] There are some workarounds but nothing that seemed viable for our purposes
Subscribe to:
Posts (Atom)