On Copyright and Open Source

Copyright is a key part of an Open Source or Free Software project. It may sound like copyright is antithetical to Free and Open software, but if Richard Stallman, President of the Free Software Foundation (FSF) thinks that ownership of copyright is an important part of Free Software, then we should believe him. A couple of things have led me to these conclusions. Firstly, at the February meeting of the Business Intelligence SIG, Ian Fyfe discussed the business of Open Source suites and how Pentaho is able to offer a suite of Open Source projects as a commercial produce by controlling the Open Source projects, and in particular copyright to the code.

The other clue to the importance of copyright came by accident as I was looking at the difference between the emacs editor and the XEmacs editor. Emacs was an open software project that forked in the early 1990's before the terms Free Software and Open Source had even been invented. One of the criticisms that Stallman, speaking for the emacs project levels against the XEmacs project is that they have been sloppy about the ownership of the code and not always got the "legal papers" that assign ownership of the contribution to the project. On this web page about XEmacs versus emacs, Stallman says:

"XEmacs is GNU software because it's a modified version of a GNU program. And it is GNU software because the FSF is the copyright holder for most of it, and therefore the legal responsibility for protecting its free status falls on us whether we want it or not. This is why the term "GNU XEmacs" is legitimate.

"But in another sense it is not GNU software, because we can't use XEmacs in the GNU system: using it would mean paying a price in terms of our ability to enforce the GPL. Some of the people who have worked on XEmacs have not provided, and have not asked other contributors to provide, the legal papers to help us enforce the GPL. I have managed to get legal papers for some parts myself, but most of the XEmacs developers have not helped me get them."

Note that GNU is the FSF "brand" for its software. The legal papers that Stallman references assign ownership and copyright of a code contribution to the FSF. Because the FSF owns the code it can enforce its right as owner on anyone who breaks its license. Also it can change the terms of the license, and license the code to another party under any other license that it sees fit. The FSF has changed the license terms of the code that it owns. As new versions of the GNU Public License (GPL) have emerged the FSF have upgraded the license to the latest version.

Copyright and Open Source is a study in contradictions. On the one hand, Richard Stallman has "campaigning against both software patents and dangerous extension of copyright laws". On the other hand, he uses ownership of copyright to push his agenda through the GNU Public License which has a viral component so that the source code of any software that is linked with GNU licensed software must be published as open source software. I will write more about this issue.

A good Open Source project needs to make sure that everyone who contributes code to the project signs a document that assigns copyright of their contribution to the project. Unless care is taken to make all the code belong to a single entity, each person who has contributed to the code owns their contribution. If the project wants to be able to do anything with the code other than passively allow its distribution under its existing license, the code must be owned by a single entity. As Stallman says, the project may not be able to defend its own rights unless the code has clear ownership.

Actors and Concurrent Computation

Carl Hewitt was in fine form when he spoke about the Actor model of concurrent computation at the SDForum SAM SIG meeting on "Actor Architectures for Concurrent Computation". The meeting was a panel with three speakers. Carl Hewitt, Emeritus Professor in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. Hewitt and his students invented Actors in the 1970's. Frank Sommers of Artima Software, is an active writer in the area of information technology and computing and is currently writing a book on Actors in the Scala programming language. Robey Pointer is a software engineer at Twitter, and is an enthusiastic user of Scala and Actors at Twitter. Bill Venners is president of Artima Software and an author of a book on Scala moderated the proceedings.

Hewitt had retired when the advent of multi-core processors and distributed parallelism renewed interest in the Actor model. He has come out of retirement and is currently visiting Stanford. Hewitt described the genesis of the Actor methodology in the Alan Kay's Smalltalk 72, where every object was autonomous and you acted on an object by sending it messages. Later versions of Smalltalk moves in a different direction. The most important aspect of the Actor model is that it decouples the sender from the communications. In practice this allows the Scala implementation to scale to millions of Actors engaged in concurrent communication (more on this later).

Hewitt spoke with great flourish on a number of other topics, including his determination that the Actor model should be properly represented on Wikipedia and spooks and the internet archive. He spent some time with the unbounded non-determinism in the Actor model versus other concurrency formalisms that only support bounded non-determinism. An audience member challenged him to explain this better and citing Map-Reduce. Amusingly, Hewitt answered by describing the parallelism in Map-Reduce as like Stalin. Stalin has three deputies and each of those deputies has three deputies. Stalin tells his deputies what to do, and those deputies tell their deputies what to do and so on. Thus the business of the state can proceed in parallel. Map-Reduce is a sequential algorithm which is speeded up by parallelism. There is no non-determinism. This is parallelism as opposed to concurrency.

Next Frank Sommers spoke on how Actors are used in Scala. The good news is that Actors are implemented in Scala and Hewitt much preferred the Scala implementation over the Erlang implementation of Actors. The bad news is that there are a number of issues with the Scala implementation. For example, a Scala program cannot exit from a "receive" statement. Another issue is that messages are supposed to be immutable, however the current implementation may not ensure this. These and other issues are being worked on, and the next version of Actors in Scala will be much better.

Finally, Robey Pointer talked about how he is using Scala. He implements message queuing systems that deals with large numbers of long lived connections where each connection is mostly idle but has sporadic bursts of activity. Robey has implemented this system in many different ways. For example, a straight thread implementation and a lot of tuning got up to 5000 thread based connections working at one time, however this fell well short of his goal of supporting millions of connections. A thread pool implementation with a few hundred threads worked better but the code became unwieldy and more complicated than it should have been. Now he has an Actor based implementation in Scala that does scale to the millions of connections and yet the code remains straightforward and small.

He also showed us how Actors can be mixed-in with thread based synchronization to solve problems for which even Actors are too heavyweight. I am in two minds about this. On the one hand, there are legitimate uses for this low level synchronization (as discussed in my PhD thesis). On the other hand, thread based concurrency is awful as I keep promising to explain in another post. Also to do it safely, you need to understand is great detail how Actors are implemented in Scala, and one reason for adopting a high level construct like Actors is that it should hide gory implementation details.

After the meeting I spoke with Carl Hewitt. We agreed that sending a message needs to have a low overhead. It should have a similar costs to calling a procedure. Computers have specialized instructions to support procedure calls and they need specialized instructions to support message passing. We did this for the Tranputer, although that was before its time, and it is eminently possible for Actors. All we need is for a high level concurrency formalism like Actors to get enough traction that the chip manufacturers become interested in supporting it.

Ruby versus Scala

An interesting spat has recently emerged in the long running story of Programming Language wars. The Twitter team, who had long been exclusively a Ruby on Rails house, came out with the "shock" revelation that they were converting part of their back end code to use the Scala programming language. Several Ruby zealots immediately jumped in saying that the Twitter crew obviously did not know what they were doing because they had decided to turn their backs on Ruby.

I must confess to being amused by the frothing at the mouth from the Ruby defenders, but rather than laughing, lets take a calm look at the arguments. The Twitter developers are still using Ruby on Rails for its intended purpose of running a web site. However they are also developing back-end server software and have chosen the Scala programming language for that effort.

The Twitter crew offer a number of reasons for choosing a strongly typed language. Firstly, dynamic languages are not very good for implementing the kind of long running processes that you find in a server. I have experience with writing servers in C, C++ and Java. In all these languages there are problems with memory leaks that cause the memory footprint to grow over the days, weeks or months that the server is running. Getting rid of memory leaks is tedious and painful, but absolutely necessary. Even the smallest memory leak will be a problem with heavy usage and if you have a memory leak, the only cure is stopping and restarting the server. Note that garbage collection does not do away with memory leaks, it just changes the nature of the problem. Dynamic languages are designed for rapid implementation and hide the boring details. One detail that is missing is control over memory usage and memory usage left on its own tends to leak.

Another issue is concurrency. Server software needs to exploit concurrency, particularly now in the era of multi-core hardware. Dynamic languages have problems with concurrency. There are a bunch of issues, too many to discuss here. Sufficient to say that in the past Guido van Rossum has prominently argued against putting threads into Python, another dynamic language, and both Python and Ruby implementations suffer from poor thread performance.

A third issue is type safety. As the Twitter crew say, they found themselves building their own type manager into their server code. In a statically typed language, the type management is done at compile time, making the code more efficient and automatically eliminating the potential for a large class of bugs.

Related to this, many people commented on the revelation that the Twitter Ruby server code was full of calls to the Ruby kind_of method. It is normally considered bad form to have to use kind_of or its equivalent in other languages like the Java instanceof operator. After a few moments thought I understood what the kind_of code is for. If you look at any real server like a database server's code, it is full of assert statements. The idea is that if you are going to fail, you should fail as fast as you can and let the error management and recovery system get you out of trouble. Failing fast reduces the likelihood that the error will propagate and cause real damage like corrupting persistent data. Also with a fast fail it is easier to figure out why the error occurred. In a language with dynamic typing, checking parameters with a kind_of method is the first type of assert to put in any server code.

So the Twitter developers have opted to use Ruby on Rails for their web server and Scala for their server code. In the old days we would have said "horses for courses" and everyone would have nodded their heads in understanding. Nowadays , nobody goes racing, so nobody knows what the phrase means. Can anyone suggest a more up to date expression?

Map Reduce Sort Benchmark

In November Google posted in a blog that they had beaten the Terabyte Sort Benchmark with a time of 68 seconds. I waited to comment on the result until it was confirmed on the Sort Benchmark Home Page and to see the technical details, but this has not happened, so here are some preliminary thoughts.

The Sort Benchmark Home Page has several results for for different races. The big division is between Daytona and Indy, where Daytona is for general purpose software like Map Reduce while Indy is for code specially written for the task. The other dimension is how much is sorted. There are competitions for how many records can be sorted for a penny, and in a minute. Then there is the big Kahuna prize, sorting a Terabyte, that is 10 Billion 100 byte records in the shortest time.

Map Reduce can be used to sort data. (See this previous post for a simple explanation of Map Reduce.) Most of the sorting work is done by the partitioning function that sits between between the map part of the process and the reduce part. Normally the partitioning function uses hashing to get reasonably even partition sizes in the face of skewed data. Map Reduce allows you to supply a custom partitioning function and for sorting, the default partitioning function is replaced by a range partitioning function so that each reduce process gets a set of results in the same range. The reduce process then sorts and outputs its group of results.

Here we come to a little issue. The Sort Benchmark uses artificial data with a randomly generated key that is guaranteed to be evenly distributed throughout the range. Range partitioning is fine for partitioning this synthetic data, however it will not work so well with real world skewed data. Thus, while the results are impressive they should be taken with a pinch of salt.

The Google result seems particularly impressive, because last summer Yahoo had used Hadoop, their Open Source implementation of Map Reduce to officially win the Terabyte Sort Benchmark with a time of 209 seconds. There has been plenty of speculation about why Google result is much faster the the Hadoop result. Here are some thoughts:

• Bigger iron. Google have not disclosed the details of their sort (from what I can find), but their post suggests that they used 12 disks per system, as opposed to Yahoo with 4 disks per system. The total time is short so the difference in IO capacity could make a big difference. The Google systems may have had more memory and other resources per node as well.
• Misconfigured Hadoop. The Hadoop Sort benchmark disclosure says "I configured the job with 1800 maps", on a 910 node system where each node has 4 dual core processors! The Hadoop pages says "The right level of parallelism for maps seems to be around 10-100 maps per-node, although it has been set up to 300 maps for very CPU-light map tasks." The map part of sorting with Map-Reduce is a very CPU light task.
• Yahoo did not try very hard. They handily beat the previous record of 268 seconds. The benchmark disclosure says "Although I had the 910 nodes mostly to myself, the network core was shared with another active 2000 node cluster, so the times varied a lot depending on the other activity."
• SSL Communication. Hadoop uses SSL to communicate between nodes. SSL provides good network security, however it has some setup time for each node in a communication intensive task. It is not clear what Google uses for communication between nodes.

Here are a couple of final comments. Firstly Hadoop is still the official world record holder for the Terabyte Sort. Secondly, a Terabyte is small amount of data these days. The real point of the Google post was to say that they had sorted a Petabyte in 6.8 hours. Now that is a real sort benchmark.

Map-Reduce versus Relational Database

In the previous post I said that Map-Reduce is just the old database concept of aggregation rewritten for extremely large scale data. To understand this, lets look at the example in that post, and see how it would be implemented in a relational database. The problem is to take the World Wide Web and for each web page count the number of different domains that reference that page in links on the other web pages.

As a starting point, let us consider using the same data structure, a two column table where the first column contains the URL of each web page and the second column contains the contents of that web page. However, this immediately presents a problem. Data in a relational database should be normalized, and the first rule of normalization is that each data item should be atomic. While there is some argument as to exactly what atomic means, everyone would agree that the contents of a web page with multiple links to other web pages is not an an atomic data item, particularly if we are interested in those links.

The obvious relational data structure for this data is a join table with two columns. One column, called PAGE_URL, contains the URL of the page. The other column, called LINK_URL, contains URLS of links on the corresponding page. There is one row in this table (called WWW_LINKS) for every link in the World Wide Web. Given this structure we can write the following SQL query to solve the problem in the example (presuming a function called getdomain that returns the domain from a URL):

SELECT LINK_URL, count(distinct getdomain(PAGE_URL))
FROM WWW_LINKS
GROUP BY LINK_URL

The point of this example is to show that Map-Reduce and SQL aggregate functions both address the same kind of data manipulation. My belief is that most Map-Reduce problems can be similarly expressed by database aggregation. However there are differences. Map-Reduce is obviously more flexible and puts less constraint on how the data is represented.

I strongly believe that every programmer should understand the principals of data normalization and why it is useful, but I am willing to be flexible when it comes to practicalities. In this example, if the WWW_LINKS table is a useful structure that is used in a number of different queries, then it is worth building. However if the only reason for building the table is to do one aggregation on it, the Map-Reduce solution is better.

Understanding Map-Reduce

Map-Reduce is the hoopy new data management function. Google produced the seminal implementation. Start-ups are jumping on the gravy train. The old guard decry it. What is it? In my opinion it is just the old database concept of aggregation rewritten for extremely large scale data as I will explain in another post. But firstly we need to understand what Map-Reduce does, and I have yet to find a good clear explanation, so here goes mine.

Map Reduce is an application for performing analysis on very large data sets. I will give a brief explanation of what Map Reduce does conceptually and then give an example. The Map Reduce application takes three inputs. The first input is a map (note lower case). A map is a data structure, sometimes called a dictionary. A tuple is a pair of values and a map is a set of tuples. The first value in a tuple is called the key and the second is called the value. Each key in a map is unique. The second input to Map-Reduce is a Map function (note upper case) . The Map function takes as input a tuple, (k1, v1) and produces a list of tuples (list(k2, v2)) from data in its input. Note that the list may be empty or contain only one value. The third input is a Reduce function. The Reduce function takes a tuple where the value is a list of values and returns a tuple. In practice it reduces the list of values to a single value.

The Map Reduce application takes the input map and applies the Map function to each tuple in that map. We can think of it creating an intermediate result that is a single large list from the lists produced by each application of the Map function:
{ Map(k1, v1) } -> { list(k2, v2) }
Then for each unique key in the intermediate result list it groups all the corresponding values into a list associated with the key value:
{ list(k2, v2) } -> { (k2, list(v2)) }
Finally it goes through this structure and applies the Reduce function to the value list in each element:
{ Reduce(k2, list(v2)) } -> { (k2, v3) }
The output of Map Reduce is a map.

Now for an example. In this application we are going to take the World Wide Web and for each web page count the number of other domains that reference that page. A domain is the part of a URL between the first two sets of slashes. For example, the domain of this web page is "www.bandb.blogspot.com". A web page is uniquely identified by its URL, so a URL is a good key for for a map. The data input is a map of the entire web. The key for each map element is the URL of the page, and the value is the corresponding web page. Now I know that this is a data structure on a scale that is difficult to imagine, however this is the kind of data that Google has to process to organize the worlds information.

The Map function takes the URL, web page pair and adds an element to its output list for every URL that it finds on the web page. The key in the output list is the URL found on the web page and the value is the domain from the key value in the input URL. So for example, on this page, our Map function finds the link to the Google paper on Map Reduce and adds to its list of outputs the tuple ("research.google.com/archive/mapreduce.html", "www.bandb.blogspot.com"). Map-Reduce reorganizes its intermediate data so that for each URL it collects all the domains that reference that page and stores them as a list. The Reduce function goes through the list of domains and counts the number of different domain values that it finds. The result of Map-Reduce is a map where the key is a URL and the value is a number, the number of other domains on the web that reference that page.

While this example is invented, Google reports that they use a set of 5 to 10 such Map-Reduce steps to generate their web index. The point of Map Reduce is that a user can write a couple of simple functions and have them applied to data on a vast scale.

The Scala Programming Language

These days feel like the 1980's as far as programming languages are concerned with new programming languages springing up all over the place. Then, the prolific Nicklaus Wirth invented a new programming language every other year. Now, the center of language design in Switzerland has moved to Lausanne where Martin Odersky at EPFL has conceived Scala. Bill Venners of Artima introduced the Scala Programming Language at the October meeting of the SDForum Java SIG.

Scala is a functional language, in the sense that is every "statement" produces a value. Also, Scala is a statically typed language although programs look like a dynamic language. The trick is that variables are declared by a 'var' declaration, and the type variable is the type of the initial value assigned to the variable. Contrast this with a dynamic language where the data type is associated with the data value and every operation on data has to look at the data types of the operands to decide what to do.

Getting the data type from the value assigned reduces the need to over specify type as is typical of statically typed languages like Java. Bill recalled the discussion of Duh typing that a group of us had after the last time he spoke to a SFDForum SIG. The other thing that Scala makes easy is declaring invariant variables. They are like 'var' variables except they are introduced by the keyword 'val'. Contrast this with Java where you put final before the declaration or C++ where you put const before the declaration. Thus a constant in Java is declared something like this:

final static String HELLO_WORLD = "Hello World";

while in Scala the declaration looks like this:

val HELLO_WORLD = "Hello World"

This leads to a more declarative style of programming, which is a good thing. Bill reported that while in Java 95% of declarations are variables and the other 5% are constants, in Scala, 95% of declarations are constant and only 5% are variables. I have used a similar style of programming in C++ when using APIs that make heavy use of const, so you have to declare variables that you are going to pass to the API as const. The only time that this is an problem is where you have to create const objects that can throw in their constructor. Then you can end up with heavily indented try blocks as you create each const object safely so that you can pass it to the API.

Finally, Scala, like many other languages these days, compiles to the Java Virtual Machine. That way, it is broadly portable, and developers have access to the vast Java libraries.

Open Source 10 Years Later

April 7 2008 marks 10 years since the landmark Freeware Summit that signaled the opening of the Open Source movement. By coincidence I recently read the manifesto of the Open Source movement, "The Cathedral and The Bazaar" by Eric S Raymond. The book, published in 1999 and revised in 2001, contains the namesake essay several others including "Revenge of the Hackers" which describes the events leading up to and following the Freeware Summit from an insiders point of view. The essay is valuable as a history of Open Source however its veracity is slightly marred because it dates summit meeting as happening on March 7.

One thing that the Revenge of the Hackers does not shy away from is explaining why Richard Stallman and the Free Software Foundation was not present at the Freeware Summit. In the past I have written on the distinction between Open Source and Free Software. Raymond is tactful but firm in explaining why creating a separation between these two ideas was essential to getting Open Source accepted by the mainstream.

On the other hand, the end of the essay that looks into the future of Open Source does suffer in hindsight. Open Source has advanced by leaps and bounds in the last 10 years. However it is still not in the position of ruling the world as the Revenge of the Hackers suggests it might. Lets give it at least another 10 years.

Tao of Software Engineering

Scott Rosenberg's latest book "Dreaming in Code" contains a very readable history of Software Engineering. I will review the book in another post. Here, I want to talk about a couple of papers that are not mentioned in Scott Rosenberg's history that are parts of my Tao of Software Engineering.

The first is Melvin Conway's paper from 1968 called "How do Committees Invent". Fred Brooks references the paper in "The Mythical Man Month" and gave it the name "Conway's Law", however, only recently that my good friend Roger Shepherd pointed me to the original. The thesis of the paper is: "Any organization that designs a system (defined more broadly here than just information systems) will inevitably produce a design whose structure is a copy of the organization's communication structure."

While Conway's paper gives examples from several different branches of engineering, it is more applicable to Software Engineering which is the most plastic of the engineering arts. After all, a building has to have a floor, walls and a roof; a semiconductor chip is laid out on a flat surface; most mechanical devices start with a rotary power source and after that it is a question of packaging. On the other hand, software can take on any structure so it is absolutely natural that it should take of the structure of the organization producing it, whatever unsightly skew the organization may place on the software's structure.

It is not only the structure of the organization that influences a software architecture, it is the way the project is put together. For example, I have recently been working on a software project that started as a GUI demonstration. Because the GUI came first, it defined the client-server API and the data structures that passed through the API which then defined the database storage structure. We recently had to make significant changes to the API and data structures which has been extremely painful at such a late stage in the project.

This brings me to the second paper, Butler Lampson's "Hints for Computer System Design" from 1983. Like Conway's paper, it is not a difficult read. The paper is a collection of simple aphorisms on computer system design and examples to back up those aphorisms. While the aphorisms are still relevant to this day, some of the examples are creaky. For example, who remembers PL/1 or the SDS 940?

I reread this paper every few years and compare with my recent experience to see what I have done right and what could be done better next time. For example, one aphorism is "Keep basic interfaces stable". Several years ago, my very first act in a project to add a significant new feature to a large system was to go through the entire code base and change some basic APIs for the new feature. In my most recent project we have gone through months of pain because we decided to change the API just as the project was coming together.

Save Time, Generate Code

I mentioned the after party in the previous post, now is time to talk about the SDForum SAM SIG meeting "Writing Code Generators For Quality, Productivity, and Fun" by Bill Venners of Artima. In short, Bill's talk was about designing domain specific languages and using code generation to solve programming problems. Code generation can build better, more reliable code faster, particularly in situations where you find yourself doing a lot of cut and paste style .

As befits the technique, Bill got the audience to do a lot of the lifting by describing how they had solved various programming problems through code generation. I have used it a couple of times as well as some real language design, and I shared one of my experiences along with several other audience members. It was definitely encouraging to hear that many audience members had successfully used code generation.

Bill characterized a number of situations where code generation is useful and showed us a specific example of a domain specific language that he had designed. From my experience language design is comparable to API design except that there are more degrees of freedom so there are more ways to go wrong. Designing a real programming language is hard. There are issues at the lexical level, problems with keywords and extensibility, the need to make the language regular and unsurprising while dealing with special case and a thousand other little details to get right.

On the other hand, if a domain specific language can be kept simple enough, it can skirt these problems. Bill's example language was simple. Each statement consisted of a set of keywords followed by a name. In my opinion, domain specific languages are a great technique provided that you firstly design a clean simple language and secondly remember the principals of API design.