When storing any large collection of data, one of the most critical decisions one has to make is when to normalize and when to denormalize.  Normalized data is good for flexibility — you can write queries to recombine things in any combination.  Denormalized data is more efficient when you know, in advance, what the queries will be.  There’s a maxim, “normalize until it hurts, denormalize until it works.”

In the past two years, I’ve become a big fan of three software paradigms:

1. RDF and the Semantic Web
2. RESTful architectures
3. Hadoop and MapReduce

The first two were made for each other — RDF is the ideal data format for the Semantic Web, and Semantic Web applications are (ideally) implemented with RESTful architectures.

Unfortunately, as I discovered through painful experience, RDF is an inefficient representation for large amounts of data.  It’s the ultimate in normalization — each triple represents a single fact — and in flexibility, but even simple queries become prohibitively slow when each item of interest is spread across dozens of triples.

At the other end of the spectrum, MapReduce programming forces you into an entirely different way of thinking.  MapReduce offers exactly one data access mechanism: read a list of records from beginning to end.  No random access, do not pass GO, do not collect $200.  That restriction is what enables Hadoop to distribute a job across many machines, and to process data at the maximum rate supported by the hard disk.  Obviously, to take full advantage of these optimizations, your MapReduce program needs to be able to process each record in isolation, without referring to any other resources.  In effect, everything has to be completely denormalized.

For my work on AltLaw, I’ve tended to use fully denormalized data, because anything else is too slow.  But I want to be working with normalized data.  I want to have every datum — plus information about its derivation — stored in one giant RDF graph.  But I also want to be able to process this graph efficiently.  Maybe if I had a dozen machines with 64 GB of memory apiece, this wouldn’t be a problem.  But with one desktop, one server, and occasional rides on EC2, that’s not an option.

The ideal design, I think, would be a hybrid system which can do efficient bulk processing of RDF data.  There are some pilot projects to do this with Hadoop, and I’m interested to see how they pan out.  But until then, I’ll have to make do as best I can.

Update: The projects I remebered were HRDF and Heart, which turn out to be the same thing: http://code.google.com/p/hrdf/ and http://wiki.apache.org/incubator/HeartProposal

RDF is seductive.  I can’t get away from it.  Something about the ability to represent anything and everything in one consistent model just tugs at my engineer’s heartstrings.

The problem with RDF, as I’ve discovered through painful experience, is that the ability to represent everything sacrifices the ability to represent anything efficiently.  Certainly that is partly the fault of existing toolkits, but it’s still a fault.

But maybe I’m simply missing the point of RDF.  Its stated design goals do not include “efficient storage and retrieval.”  The W3C’s RDF recommendations make no mention of performance.  Tim Berners-Lee doesn’t mention it in his Semantic Web talks, except in airy references to future general purpose RDF engines.

RDF, it seems, is intended not as so much as a data storage model but as a communication model.  In short, it’s a protocol.  One of the goals Berners-Lee does talk about is exposing the information currently trapped inside relational databases.  So maybe I shouldn’t think about storing RDF and think instead about presenting it as a view of my own domain-specific data structures.

There are still some benefits to be had from storing and analyzing data in a graph-like structure.  But RDF is not necessarily the be-all and end-all of graphical models either.

I dropped in to hear Rich Hickey talk about Clojure at the New York Semantic Web meetup group.  Some highlights:

• Some programs, like compilers or theorem provers, are themselves functions.  They take input and produce output.  Purely functional languages like Haskell are good for these kinds of programs.  But other programs, like GUIs or automation systems, are not functions.  For example, a program that runs continously for months or years is not a function in the mathematical sense.  Clojure is mostly functional, but not purely functional.

• Most Clojure programmers go through an arc.  First they think “eww, Java” and try to hide all the Java.  Then they think “ooh, Java” and realize that Clojure is a powerful way to write Java code.  Rich frowns upon “wrapper” functions in Clojure that do nothing but wrap a Java method.  Calling the Java method directly is faster and easier to look up in JavaDoc.

• Rich recommended a paper, Out of the Tar Pit, for a discussion of functional and relational techniques to manage state.

• Clojure’s data structures are persistent.  This isn’t persistent in the stored-in-a-database sense.  It refers to immutability.  For example, adding an element to a vector creates a new vector that shares structure with the old one.  Because all data structures are immutable, this is both safe and efficient.  Clojure’s hash maps, for example, have time complexity of log-base-32, which is so small it’s practically constant.

• The first thing Rich did when experimenting with the semantic web was to pull data out of the Jena API and get it into Clojure data structures.  That allows him to leverage the full power of Clojure’s data manipulation functions.  This opens up a world of possibilities that he wouldn’t have if he stuck with Jena objects.  Basically, having your data trapped inside objects is bad, because you’re limited to whatever methods those objects provide.  With generic data structures, you can re-use and compose all the functions that Clojure already provides.

Screencasts and code from the talk should appear soon — watch clojure.org or the Clojure Google group for an announcement.

Update September 22, 2008: I have abandoned this model.  I’m still using Hadoop, but with a much simpler data model.  I’ll post about it at some point.

…

Gosh darn, it’s hard to get this right.  In my most recent work on AltLaw, I’ve been building an infrastructure for doing all my back-end data processing using Hadoop and Thrift.

I’ve described this before, but here’s a summary of my situation:

1. I have a few million files, ~15 GB total.
2. Many files represent the same logical entity, sometimes in different formats or from different sources.
3. Every file needs 5-10 steps of clean-up, data extraction, and format conversion.
4. The files come from ~15 different sources, each requiring different processing.
5. I get 20-50 new files daily.

I want to be able to process all this efficiently, but I also want to be able to change my mind.  I can never say, “I’ve run this process on this batch of files, so I never need to do it again.”  I might improve the code, or I might find that I need to go back to the original files to get some other kind of data.

Hadoop was the obvious choice for efficiency.  Thrift is a good, compact data format that’s easier to use than Hadoop’s native data structures.  The only question is, what’s the schema?  Or, more simply, what do I want to store?

I’ve come up with what, for want of a better term, I call the Document-Blob Model.

I start with a collection of Documents.  Each Document represents a single, logical entity, like a court case or a section of statute.  A Document contains an integer identifier and an array of Blobs, nothing more.

What is a Blob?  Good question.  It’s data, any data.  It may represent a normal file, in which case it stores the content of that file and some metadata like the MIME type.  It may also represent a data structure.  Because unused fields do not occupy any space in Thrift’s binary format, the Blob type can have fields for every structure I might want to use now or in the future.  In effect, a Blob is a polymorphic type that can become any other type.

So how do I know which type it is?  By where it came from.  Each Blob is tagged with the name of its “provider”.  For files downloaded in bulk, the provider is the web site or service where I got them.  For generated files, the creator is a class or script, with a version number.

So I have a few hundred thousand Documents, each containing several Blobs.  I represent each conversion/extraction/processing step as its own Java class.  All those classes implement the same, simple interface: take one Blob as input and return another Blob as output.

Helper functions allow me to say things like, “Take this Document, find the Blob that was generated by class X.  Run  class Y on that Blob, and append result to the original Document.”  In this way, I can stack multiple processing steps into a single Hadoop job, but retain the option of reusing or rearranging those steps later on.

Will this work?  I have no idea.  I just came up with it last week.  Today I successfully ran a 5-step job on ~700,000 documents from the public.resource.org federal case corpus.  It took about an hour on a 10-node Hadoop/EC2 cluster.

The real test will come when I apply this model to the much messier collection of files we downloaded directly from the federal courts.

Google recently released its Protocol Buffers as open source. About a year ago, Facebook released a similar product called Thrift. I’ve been comparing them; here’s what I’ve found:

Overall, I think Thrift wins on features and Protocol Buffers win on
documentation. Implementation-wise, they’re quite similar. Both use
integer tags to identify fields, so you can add and remove fields
without breaking existing code. Protocol Buffers support
variable-width encoding of integers, which saves a few bytes. (Thrift
has an experimental output format with variable-width ints.)

The major difference is that Thrift provides a full client/server RPC
implementation, whereas Protocol Buffers only generate stubs to use in
your own RPC system.

Update July 12, 2008: I haven’t tested for speed, but from a cursory examination it seems that, at the binary level, Thrift and Protocol Buffers are very similar. I think Thrift will develop a more coherent community now that it’s under Apache incubation. It just moved to a new web site and mailing list, and the issue tracker is active.

I’m sure I’m not the first to suggest this, but here goes.

Ever since somebody first thought of applying the Model-View-Controller paradigm to the web, we’ve had this:

The View is a conflation of HTML and JavaScript.  JavaScript is an afterthought, a gimmick to make pages “dynamic.”  All the real action is in the Controller, which talks to the database, processes the internal application logic, and renders templates before sending complete pages back to the client.

But what if we implement the Controller entirely in JavaScript?

Now we can put the Controller on the client, and build a RESTful HTTP interface to communicate with the database.

Obviously there are many issues to consider.  First and foremost is making sure that rogue clients cannot do anything to the database they’re not supposed to.  But that’s a manageable problem — Amazon S3 is a good example.  Apps that run entirely in the client can even be made more secure than their server-based counterparts, because encryption can be implemented entirely in the client, so that the server never sees the unencrypted data.  (Clipperz, an password-storage service, calls this a zero-knowledge web app.)

There are some interesting possibilities.  For example, the entire application, including the current state of the model, can be downloaded as a single web page for off-line use.  (Clipperz supports this.)  Also, the same application could connect to multiple data sources.  And as with any RESTful architecture, back-end scaling is relatively easy.

Update July 10, 2008: I’m always amazed when one of my posts show up on Reddit.  Maybe it was the diagrams.  In any case, thanks to everyone who sent in comments.  A couple responses:

1. Yes, in a sense I’ve described Ajax.  But most Ajax-related code around the web these days is still in the “dynamic view” mode rather than the “client-side controller” mode.
2. I like Sun’s MVC diagram in which the View takes an active role in rendering the model rather than being just a template.  It’s actually quite similar to what I’m suggesting here.
3. Some MVC frameworks, such as Ruby on Rails, insist that logic in the View is bad, but then they include all these Ajax view helpers, so it’s a bit of a mixed message.
4. I’m not insisting that all business logic be implemented client-side.  Rather, I’m assuming some kind of “smart” database, with a RESTful front-end, that’s capable of containing business logic.  Back in the day, these were SQL stored procedures.  Now it’s probably something like CouchDB.
5. Yes, this design is bad for search engines, bookmarks, and deep linking.  But there are plenty of cases where those don’t matter.  Look at Google Mail, for example.  It basically follows the design I’ve laid out here: the entire app is one HTML page (or a very few pages) with behavior implemented in client-side JavaScript.

Update August 7, 2008: This is an example of the code-on-demand style described in Roy Fielding’s REST thesis.  Link from Joe Gregorio.

Just when you thought the A.I. Winter would last forever, up pops Brainhat with an open-source inference engine that uses natural language as its primary interface.  Cool!

I dropped by the Java Users’ Group meeting last week since Rich Hickey was there to talk about Clojure.

I expected a bit of carping from the Java guys, and at first they were all “efficiency this” and “security that.”  But by mid-way through the talk I think they were getting it.  A few even got excited about macros.

If I didn’t make it clear in my first post about Clojure, I like this language.  Here’s some more reasons why:

1. All binding constructs — let, defn, and the like — perform destructuring.
2. Universal data structures — vector, list, map, set.
3. Built-in java.util.regex support.
4. Sixty squintillion Java libraries.
5. A small but growing number of Clojure libraries, some written by yours truly.
6. You can generate Java .class files that run Clojure code.
7. Lightning-fast bug fixes from the author.

Cool fact: All valid JSON is also valid YAML.  So any YAML parser can also parse JSON.  Long live the mighty list/map data structure!

I just did my first test-run of a Hadoop cluster on Amazon EC2. It’s not as tricky as it appears, although I ran into some snags, which I’ll document here. I also found these pages helpful: EC2 on Hadoop Wiki and manAmplified.

First, make sure the EC2 API tools are installed and on your path. Also make sure the EC2 environment variables are set. I added the following to my ~/.bashrc:

export EC2_HOME=$HOME/ec2-api-tools-1.3-19403
export EC2_PRIVATE_KEY=$HOME/.ec2/MY_PRIVATE_KEY_FILE
export EC2_CERT=$HOME/.ec2/MY_CERT_FILE
export PATH=$PATH:$EC2_HOME/bin

I also copied my generated SSH key to ~/.ec2/id_rsa-MY_KEY_NAME.

You need authorizations for the EC2 security group that Hadoop uses. The scripts in hadoop-*/src/contrib/ec2 are supposed to do this for you, but they didn’t for me. I had to do:

ec2-add-group hadoop-cluster-group -d "Group for Hadoop clusters."
ec2-authorize hadoop-cluster-group -p 22
ec2-authorize hadoop-cluster-group -o hadoop-cluster-group -u YOUR_AWS_ACCOUNT_ID
ec2-authorize hadoop-cluster-group -p 50030
ec2-authorize hadoop-cluster-group -p 50060

The first line creates the security group. The second line lets you SSH into it. The third line lets the individual nodes in the cluster communicate with one another. The fourth and fifth lines are optional; they let you monitor your MapReduce jobs through Hadoop’s web interface. (If you have a fixed IP address, you can be slightly more secure by adding -s YOUR_ADDRESS to the commands above.)

These authorizations are permanently tied to your AWS account, not to any particular group of instances, so you only need to do this once. You can see your current EC2 authorization settings with ec2-describe-group, it should look something like this:

GROUP   YOUR_AWS_ID    hadoop-cluster-group    Group for Hadoop clusters.
PERMISSION      YOUR_AWS_ID    hadoop-cluster-group    ALLOWS  all                     FROM    USER    YOUR_AWS_ID    GRPNAME hadoop-cluster-group
PERMISSION      YOUR_AWS_ID    hadoop-cluster-group    ALLOWS  tcp     22      22      FROM    CIDR    0.0.0.0/0

With additional lines for ports 50030 and 50060, if you enabled those.