Riak and Monotable

The Imikimi Monotable project has been placed on indefinite hold. Unfortunately we don't have the manpower. It is an excellent solution to our back-end data-store needs, and probably for many others as well. However, it is still going to require a lot of work to bring to production-ready.

Instead, we are looking seriously at Riak for our back-end store. We hope to put all our Kimi-data and most of our Sql-data in two separate Riak clusters. Riak has several benefits that Monotable was designed to solve:

1. no central server - every node is the same and any node can respond to any request
2. scales easily by adding one node at a time 
3. can configure replication levels on a per-bucket basis
4. supports map-reduce
5. can store binary data - up to 16 megabytes per record (this our requirement, not Riak's exact max size)

However, Riak has some down-sides:

1. Riak's "eventually consistent" system only makes progress on a record's consistency when it is read. It is not clear that any progress is made if the record is never read after a write or consistency failure. This means the latest version of a record could go under-replicated indefinitely.
2. Riak's scaling is limited by your initial "ring-size". My hazy understanding is we need to set our ring-size to 20x our max expected server-count.
3. Riak has a lot of cross-talk between nodes. There is potentially an upper limit of 300 servers before performance degrades.
4. Riak does not allow range-selects on the primary key
5. The behavior and scalability of secondary indexes is not clear to me. Typically distributed hash tables can't do secondary indexes. Riak has secondary indexes, but there is probably a catch that we don't understand yet.
6. I don't think Riak has "live" map-reduce. 

Monotable is designed to achieve all of the above goals and scale to very large sizes. However, we are a long ways from needing >300 servers. As long as Riak's indexes work reasonably well and we can do off-line map-reduce jobs without disrupting site performance, it should be good enough for us for now.

Monotable and Map-Reduce

Live map-reduce was not an original requirement for Monotable. However, it is a very powerful feature. It would bring Monotable from being a simple key-value store with basic range-selects to a system with powerful indexing and querying capabilities. It turns out the core of Monotable is well suited for it.

In an offline map-reduce, each chunk can be stream-processed by the mapper and fed into the reducer. Once a chunk has been reduced to a single output, the results of all chunks can be merged until a single overall result is output. If the reducer can write data back to Monotable, you can use this to generate secondary indexes. 

These indexes are more powerful than SQL indexes which have a 1-to-1 mapping between source and index records. With the reduce step we can arbitrarily choose to index at any level of reduction. In fact we can store the result of every reduction if we wish. This allows us to generate an index + aggregate hybrid. With this data structure we can compute the map-reduce result over any sub-range in O(ln n) time.

This much was already a possibility within the original Monotable requirements. Just take the Monotable core and add a standard map-reduce system over top. The question becomes how can we make it live-updating?

Acknowledgment: Live-Map-Reduce is not new. I believe CouchDB does this already. CouchDB, however, doesn't scale easily to large distributed clusters. 

Live-Updating Map-Reduce in Monotable

Anytime a source-record is changed, the off-line generated index will become out-of-date. Using normal map-reduce, we'd have to delete all the old data and re-run the map-reduce. Deleting a large range of records is fast in Monotable, but re-running the map-reduce will be slow. Since we are already storing the entire reduce-tree, couldn't we re-map the changed record and then update only the O(ln n) reduce steps which depend on it?

Structure Definitions

First, I need to briefly describe the structure of Monotable. The entire Monotable stores all records, sorted by key. Monotable is logically partitioned into "ranges" which are similar to separate "tables" in other stores. Each range is broken up into one or more 64 meg "chunks". Each chunk exclusively covers a sub-range of the overall Monotable. All records in Monotable with keys >= the chunk's start key and < it's end key are stored in that chunk.

To keep things simple, let's separate out map-reduce. Each range in Monotable can have zero or more mappers or reducers. A mapper takes each record and transforms it and then writes the results back into Monotable in a different range. Each reducer takes all records in one chunk and reduces them down to one record which is written, again, to a different range. In both cases, the new range can in turn have a mapper or reducer. 

To configure a standard map reduce, we would apply a mapper to our data-range which write records to another range we'll call the "index". The index-range would have a reducer which write records to a meta-index-range. This meta-index-range would in turn have the same reducer step to yet another meta-meta-index-range. This continues until the meta-meta-meta-*-index-range fits within one chunk.

Live Updating

Now that we have a sense of our data-structure, how do we keep it up to date? Due to the nature of distributed data, we can't afford to do it synchronously. Monotable guarantees atomic operations within a chunk, but provides no guarantees across chunk boundaries. 

When a record changes, the first step is to mark it's chunk as "dirty" with respect to all mappers and reducers applied to that chunk. Asynchronously, the master server for each chunk can later initiate the process of "cleaning" the chunk by updating all effected maps and reductions.

Unfortunately, simply re-applying the map or reduce step for the chunk doesn't work. The mapper may generate arbitrary output based on the record's data. If we naively insert the new value in the index we may be forgetting to remove the old value, which may be anywhere else in the index. We must have both the old and the new value so we can delete the old value before inserting the new one. Note that if the mapped old and mapped new values are identical, we can skip the rest of the update. 

Keeping the old value of a record adds complexities, particularly since we want to allow more than one active mapper or reducer. For every mapper/reducer we need to be able to access the version of every  changed records as they were the last time that mapper/reducer ran. 

A New Chunk Data Structure with Versioning

I believe the answer is similar to how CouchDB stores its entire database - as a continually appending log representation of a b-tree. This format keeps a complete revision history of all changes. Each mapper or reducer just needs to track the offset of the snapshot when it was last run. 

If we limit this to each individual chunk, then we avoid the main problem of CouchDB: it is painful to compact large databases. Since chunks are limited in size, we always have relatively small files which will be fast to compact. We have to be a bit careful when we compact chunks to ensure that we don't lose any of the snapshots that the map/reducers need. However, if they are kept up-to-date at roughly the same rate as our compaction schedule they should usually be fairly up-to-date and we only need to keep the most recent few snapshots. We just need a compaction algorithm that takes into account a list of snapshots that must be maintained after compaction.

Keep in mind that all this snapshotting and revision tracking is managed within one server. No synchronization needs to happen with other servers in the cluster. 

As a side-effect, Monotable gains a general snapshotting system. On a chunk-by-chunk bases we could establish any arbitrary history tracking plan up to tracking all history.

Chaining

Now we know how on map/reduce step will stay up to date. The rest of the system falls out automatically. The mapper will dump its outputs into a separate range of Monotable which in turn will become "dirty" and trigger a reducer step. The reducer will write to yet another range triggering another reducer step. This will continue until the source range is reduced down to <= 1 chunk.

Chaining will add some latency to the system. Each step invokes an asynchronous delay between being marked "dirty" and the master-server for that chunk scheduling the map/reducer action. The good news is we are effectively working with a tree with very high branching factor. Pessimistically, given the minimum chunk size of 32megabytes and a large, 1k record size, we have a branching factor over 32,000. A two-level tree can address 1 billion records. Four levels can track 1 quadrillion records.

My other concern is how much work this might involves if there are random changes happening all over the source range all the time. Due to the asynchronous nature of the system, though, the answer is good. In the worse case, at the leaf level, there may be as many as one map operation per record change. This could be bad, but the mapper algorithm could be designed to run in time proportional to the number of changes. One change will only require a small amount of work to update.

As we chain "dirty" updates up the reduction tree, the story gets better. If several leaf nodes of one parent change at the same time, they will all mark their parent node as "dirty", but they won't each trigger a new reducer step. When the parent node's server schedulers the mapper step it will integrate all changes from its leaf nodes in one pass.

Brilliant!

The result is quite elegant. Each individual record change would trigger approximately 'k' steps of work reading/writing only approximately 'k' records - where 'k' is the depth of the reduction tree <= log(n) / log(32000) - n == number of records in the source range. K is <= 2 for n <= 1,000,000,000 records, and K is <= 4 for n <= 1,000,000,000,000,000,000 records. If records are changing faster than the reduction steps can propagate up the tree, k will become smaller since updates up the tree can cover more than one child-node per update. K will approach 1 as the speed of record updates increases. The system gets more efficient as it becomes more loaded.

Parsing JSON the Not-So-Hard Way

Aaron Patterson recently posted this article on Parsing JSON the hard way using Racc. I think he did an excellent job explaining Racc. However, it was painful. Racc is an LALR(1) parser-generator similar to Yacc. While Yacc was fun to learn in school, it's also painful to use. LALR is hard to debug ("shift-reduce conflict" - !@#$% - if you know what I mean), and the parser generation steps are tedious to set up and maintain. There is a better way...

Enter Parsing Expression Grammars. I learned about PEGs from Treetop. Think of PEGs as greedy regular expressions with recursion. Being greedy, they don't try every possible pattern-match. This turns out to be a good thing; it makes them much easier to understand and debug. Adding recursive rule-matching to regular expressions makes PEGs approximately as expressive as LALR(1) parsers (though not identical). Treetop got me excited to work with parsers again, but sadly it still had some of the awkwardness of Yacc-style parser-generators. You have to build "treetop" files into ruby files before you can use them. There is yet an even better way...

Enter Babel Bridge (github). I wanted a PEG based parser-generator that allowed me to use 100% ruby with no extra build steps, so I built Babel Bridge. I've been evolving BB for over 2 years now. It is a powerful tool for building easy-to-understand parsers.

Here is how to write a JSON parser using the Babel Bridge gem. If you want to skip to the punch-line, here is the JSON parser source code.

Writing a JSON parser with Babel Bridge

First, install the babel_bridge gem:

gem install babel_bridge

With Babel Bridge you can create many different parsers and have many instances of each in one runtime. To define a new parser, create a class and inherit from BabelBridge::Parser.

 
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  # define the parser here
end

The main component for defining your parser is the "rule". A rule is a named pattern for matching strings of characters. The first parameter of the "rule" method is the name of the rule. The remaining parameters specify one or more patterns to match. For more detailed info, please see the readme.

There are five literal values that are allowed with JSON: string, number, true, false and null. Let's start by making rules for each of them. (Credit: I used Aaron Patterson's regular expressions he derived from json.org.)

 
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  rule :value, any(:number, :string, :true, :false, :null)

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"
end

BabelBridge::Shell.new(JsonParser.new).start

In addition two the five rules for the literals, I added two more lines of code. First, I added a general rule called :value. It matches any of the five literals. Babel-Bridge starts matching using the first rule you declare. That "root rule" must include everything you want to match. JsonParser will now match any of the JSON literals.

Second, I added a "shell". It is a Babel-Bridge tool to help make parser-testing easier. Try running the above code and typing in some JSON literals at the prompts.

 
> "string literal"

Parse tree:
  ValueNode1 > StringNode1 > "\"string literal\""

> 123

Parse tree:
  ValueNode1 > NumberNode1 > "123"

> null

Parse tree:
  ValueNode1 > NullNode1 > "null"

We are halfway done. There are two more important patterns for JSON: objects (hashes) and arrays. Arrays consist of 0 or more :values, delimited by "," and wrapped in "[]". Objects consist of 0 or more :pairs, again delimited by "," and wrapped in "{}". Pairs consist of a :string, then a ":", then a :value.

 
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  rule :value, any(
    :object, :array, :number,
    :string, :true, :false, :null
  )

  rule :array,  '[', many?(:value, ','), ']'
  rule :object, '{', many?(:pair,  ','), '}'

  rule :pair, :string, ':', :value

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"
end

BabelBridge::Shell.new(JsonParser.new).start

You can try out the new rules:

 
> ["my string",123,true]

Parse tree:
  ValueNode1 > ArrayNode1
    "["
    ValueNode1 > StringNode1 > "\"my string\""
    ValueNode1 > NumberNode1 > "123"
    ValueNode1 > TrueNode1 > "true"
    "]"

> {"my key":"my value"}

Parse tree:
  ValueNode1 > ObjectNode1
    "{"
    PairNode1
      StringNode1 > "\"my key\""
      ":"
      ValueNode1 > StringNode1 > "\"my value\""
    "}"

If JSON allowed literals to stand alone, we'd be done. Unfortunately JSON is a little more restrictive, so we have to add a new root-rule to ensure there is an array or object at the top-most level.

There is one other thing we need to add. Parsing-Expression-Grammars match every character or fail. Right now we are not handling white-space, so any white-space character in our string will cause our parsing to fail. BB makes this easy. Just call "ignore_whitespace" in your class declaration.

Below is the complete JSON parser. It should match any legal JSON and reject anything illegal. However, it just returns the parse-tree when it succeeds. In the next section we'll add the same functionality Aaron did in his blog post.

 
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  ignore_whitespace

  rule :document, any(:object, :array)

  rule :array,  '[', many?(:value, ','), ']'
  rule :object, '{', many?(:pair,  ','), '}'

  rule :pair, :string, ':', :value

  rule :value, any(
    :object, :array, :number,
    :string, :true, :false, :null
  )

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null"
end

BabelBridge::Shell.new(JsonParser.new).start

source

Adding Functionality to The Parse Tree

Every rule you define creates a node class. Every time an instance of that rule is parsed, an instance of that node class is created. With Babel-Bridge you can easily define methods on the parse-tree nodes for each rule you declare. When calling the rule method, just open up a do-block. The code inside the do-block is executed inside the class for that node.

Our goal now is to convert the resulting parse-tree from our JSON parser into the equivalent Ruby Hashes, Arrays and Strings etc. We are going to add an "evaluate" method to our nodes which returns the correct Ruby data-structures. For example, here is how we can add the evaluate method to our :null rule.

 
  rule :null, "null" do
    def evaluate; nil end
  end

To evaluate the remaining JSON literals we can leverage the fact that Ruby's literals are nearly identical. In fact, "null" is the only one which is different. To avoid duplicating code (DRY!), I'm going to insert an extra rule called :ruby_compatible_literal. Calling to_s on a node just returns the source string that node matched. Using Ruby's "eval" method, we can evaluate that string and get the Ruby object back.

 
require "babel_bridge"
class JsonParser < BabelBridge::Parser
  ignore_whitespace

  rule :document, any(:object, :array)

  rule :array, '[', many?(:value, ','), ']'

  rule :object, '{', many?(:pair,  ','), '}'
  rule :pair, :string, ':', :value

  rule :value, any(:object, :array, 
    :ruby_compatible_literal, :null
  )

  rule :ruby_compatible_literal, any(:number, 
    :string, :true, :false
  ) do
    def evaluate; eval(to_s); end
  end

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null" do
    def evaluate; nil end
  end
end

BabelBridge::Shell.new(JsonParser.new).start

Next, let's add the evaluate method to array. When there are nested rules, you can access them by name. If that sub-rule can be matched more than once, it will return an array of the child nodes which were matched with that rule. Here, the #value method returns a :value nodes in matched in the array. We just need to convert that array to the #evaluated versions of each :value node.

 
  rule :array, '[', many?(:value, ','), ']' do
    def evaluate; value.collect {|v| v.evaluate}; end
  end

Evaluating Objects takes two steps. The :pair rule returns a 2-element array of the form: [key, value]. Then the :object rule uses the Hash[] constructor for the final result.

 
  rule :object, '{', many?(:pair,  ','), '}' do
    def evaluate; Hash[ pair.collect {|p| p.evaluate } ] end
  end

  rule :pair, :string, ':', :value do
    def evaluate; [ eval(string.to_s), value.evaluate ] end
  end

Here is the full source-code for parsing JSON and generating Ruby data structures.

 
require "babel_bridge"

class JsonParser < BabelBridge::Parser
  ignore_whitespace

  rule :document, any(:object, :array)

  rule :array, '[', many?(:value, ','), ']' do
    def evaluate; value.collect {|v| v.evaluate} end
  end

  rule :object, '{', many?(:pair,  ','), '}' do
    def evaluate; Hash[ pair.collect {|p| p.evaluate } ] end
  end

  rule :pair, :string, ':', :value do
    def evaluate; [ eval(string.to_s), value.evaluate ] end
  end

  rule :value, any(:object, :array, :ruby_compatible_literal, :null)

  rule :ruby_compatible_literal, any(:number, :string, :true, :false) do
    def evaluate; eval(to_s); end
  end

  rule :string, /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/
  rule :number, /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/
  rule :true,   "true"
  rule :false,  "false"
  rule :null,   "null" do
    def evaluate; nil end
  end
end

BabelBridge::Shell.new(JsonParser.new).start

source

You'll notice that we didn't have to define evaluate on every node. Babel-Bridge has some intelligent defaults to help minimize code-size. Now run the code and enter some JSON values:

 
> [null]
 => [nil]

> {"my key":"my value"}
 => {"my key"=>"my value"}

Notice that the shell stopped printing our parse-tree. The shell looks for the "evaluate" method on the root node. If it exists, it prints out root_node.evaluate.inspect.

You might also try inputing some illegal values. This shows off one of Babel-Bridge's powerful debugging tools - the parser-failure-info.

 
> [nil]
Parsing error at line 1 column 2 offset 1

Source:
...
[<HERE>nil]
...

Parse path at failure:
  DocumentNode1

Expecting one of:
  "["                                                ArrayNode1
  "]"                                                ArrayNode1
  "false"                                            FalseNode1
  "null"                                             NullNode1
  "true"                                             TrueNode1
  "{"                                                ObjectNode1
  /"(?:[^"\\]|\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4}))*"/ StringNode1
  /-?(?:0|[1-9]\d*)(?:\.\d+)?(?:[eE][+-]?\d+)?/      NumberNode1

If you want to use your parser in real code, you probably won't want to use the shell. Here's how:

 
json_parser = JsonParser.new

parse_tree = json_parser.parse "[null]"

if parse_tree
  ruby_data_structure = parse_tree.evaluate
  puts ruby_data_structure.inspect
else
  puts "ParsingError: " + json_parser.parser_failure_info
end

For further reading, you might be interested in my earlier blog post: How to Create a Turing Complete Programming Language in 40 Minutes (and 70 lines of code).

Don't Learn a New Programming Language Every Year. Write one!

Don't learn a new language every year

Programmers often recommend learning a new programming language every year. I don't agree. I've studied many languages by reading their specs and dabbling with some code until I feel like I've got the basics, but I don't think I really learned them. My path to really "learning" Ruby showed me why.

Ruby was not a challenging language to learn. I picked up the Pragmatic Programmers book and read it end to end (an endorsement to both the language and the book). When the time came to start Imikimi, I chose Rails to do the web-side. However, I discovered that I hadn't really learned to *think* in the language until after several years of continuous professional use.

I was a C++ programmer before I was a Ruby programmer. A lot of my early Ruby code looks and feels a lot like C++ code. There were constructs in Ruby that I wasn't comfortable with, so I simply didn't use them. Over time I re-discovered language features I "learned" in my first reading of the Pragmatic book. Over time I learned how to program in Ruby-style from the community. By studying the Rails source and other gems I learned how to better use the language and how to write clean, readable code.

Learning a language by reading a book and writing a few small sample apps is equivalent to learning the grammar and a few phrases of spoken language. It's a shallow understanding which only broadens your perspective in shallow ways. I don't think you can claim to really know a language, spoken or programming, until you are conversant in it. It's a long, slow, but ultimately rewarding processes.

Here's my recommendation: To get started, do learn a few extra languages, shallowly. The second and third language you learn will broaden your horizons even if you don't dive too deep into them. After that, though, you need to focus on deepening your understanding either of your current language of choice, or a new one, through hours and hours of work on real projects, OR through my second recommendation:

Write a Toy language every few years

I'm writing a programming language. I've spent more than a decade thinking about programming languages and PL design. From 2001 until 2006 I worked on new language ideas full-time. Unfortunately none of that work saw the light of day, so I'm circling around again. I've learned a lot since then, primarily from Ruby and the Ruby community.

My current project, the River programming language, is an attempt to build the simplest Prototype-Based core language that can support a Ruby-like class-system on-top, written in the language itself. I've learned more about Ruby in the past few months than I have in the past few years.

You learn a lot about programming when you write a language implementation. It forces you to examine all the edge cases you normally ignore. And it happens fast. You are immediately forced into uncomfortable areas of programming languages you were unaware of. There are trade-offs to be made at every level. There are boot-strapping issues to resolve, and there are a host of subtle semantics in your host language that you never thought about.

How to get started

If you decide to follow this path, here are a few tips.

• Use a flexible, agile host language. You will make many major refactors along the way, and you don't want to get bogged down in irrelevant details. This is true for any project, but especially true when working on something as meta as writing one language inside another. I'd recommend Ruby, but Python or even Javascript would work well.
• Use a well-designed parser-generator (resource: my Babel-Bridge parser-generator gem)
• Don't worry about performance at first, even if that is your primary goal.
• Target Turing-complete functionality before all else. This will give you a solid base-camp to build out from as you explore the rest of your language. (resource: my How to write a Turing-Complete Programming Language in 40 minutes video)

You can follow my design progress on Twitter: #riverlang / @shanebdavis

Happy PL design!

Essence of MVC

The Model-View-Controller pattern (MVC) was first described at Xerox PARC by Trygve Reenskaug in 1979:

MVC was conceived as a general solution to the problem of users controlling a large and complex data set. The hardest part was to hit upon good names for the different architectural components. Model-View-Editor was the first set. After long discussions, particularly with Adele Goldberg, we ended with the terms Model-View-Controller.

Trygve Reenskaug

Since then it has become the central pattern of virtually every application framework from the desktop to the web to mobile. I learned MVC from frameworks such as Rails and Cocoa, but my understanding lacked clarity. I wanted to reach beyond these artifacts and understand the essence of MVC, so I went in search of answers. After considerably more effort than I expected, I think I found some. This page is my current, best understanding of what MVC is and why it matters.

What is MVC?

Let's start with a simple, visual definition.

MVC is a pattern for taking a program...

and pulling it apart...

into modules with three well-defined roles:

The structure of a well organized MVC system is usually fairly simple. In general, there can be any number of model, view and controller modules. The communication channels between modules are restricted by an important rule: connections are only allowed between controllers and other modules. Non-controller modules should never talk directly to each other. Though not a rule, one more restriction is typically observed. Usually each view has only one controller associated with it.

NOTE: Advanced systems might use MVC hierarchically.

Now that we have a high-level idea of the structure of a MVC program, let's look at the three roles in detail.

The Model Role

A model's job is to hide and protect the user's important data. This is the data the user might want to access in 10 years - the data that has real-world significance. The model role draws a line between the data the user cares about preserving and the data that is temporary or can be re-generated from the models.

The internals of a model are responsible for storing the actual bytes that represent the user's data. Models are also responsible for ensuring the integrity and consistency of their data. Last, a model must provide efficient methods for querying and altering its data.

More than any other part of the system it is important to maintain a well defined API for each model. In order for a model to do its job properly, all methods of extracting and altering its data must be well defined, understood and respected.

The View Role

Views are the public face of a system. They determine how a user feels about the system. The attributes that make a view great are as much determined by psychology and aesthetics as engineering and science. A view's primary job is to communicate data to the user as effectively as possible. Their secondary job is to communicate the interactive nature of the interface.

Views encompass all aesthetic concerns of their system. All presentation assets, such as images, fonts, styles and layouts, belong in a view. Code that transforms data into pixels also belongs in the views. The view may even have hooks for specifying which elements are to receive user inputs, but all input processing should be done in the controller. The focus of the view is letting the UX designer worry about how the data and interface are presented.

The Controller Role

A controller's job is to process user inputs and coordinate the relevant views and models. In the simple case, it starts by extracting information from a models, doing some preliminary processing and then handing the processed data to a view to be presented. When new user inputs arrive, the controller validates them, performs alterations to the model on the user's behalf and updates the view.

The controller role's modular boundary is not as well defined as the view or model roles. Controllers do everything models and views don't. However, they tend to have a structure which is well defined by the system's use-cases. Controllers are organized around how the system will be used. They provide the glue between any number of views and any number of ways to extract and alter data from the models and align them to fulfill the user's needs.

MVC Roles and Relationships Diagram

This diagram summarizes the MVC pattern, each of the roles and their relationships:

Why use MVC?

With the roles of MVC defined, the next question is why do they matter. What are the benefits of MVC? How do we make use of MVC most effectively to realize those benefits?

There are three main benefits I have discovered.

Separation of Concerns

"The central idea behind MVC is code reusability and separation of concerns."

yiiframework.com

MVC identifies a very specific set of concerns that are repeated in virtually every programming project:

MVC concerns by function:

• Model: safely and consistently store the data that matters to the user
• View: present all, a subset or summarization of the data to the user
• Controller: respond to user inputs and events, update the view and model appropriately

MVC concerns by expertise:

• Model: data reliability, data consistency, query efficiency, update efficiency and storage-size efficiency
• View: graphic design, information presentation and UX
• Controller: expertise in the problem domain and coordinating the other concerns

MVC concerns by people:

• Model: algorithm and data-engineers
• View: designers and artists
• Controller: experts in what the system needs to do

These are very different people. Sometimes we are forced to wear more than one of these hats, but ideally we would have different people responsible for each concern. MVC lets people with different expertise focus on what they do best.

Managing Complexity and Mental Modes

MVC is an abstraction, and like many abstractions it adds complexity. However, like good abstractions, it compartmentalizes complexity. MVC can dramatically reduce the complexity of each part of the system.

MVC is a special case of the general concept of modularity, and is a surprisingly good first-pass for designing a system's modularity. Why is it better than the alternatives? The core reason is the concerns MVC uses to define module boundaries are exceptionally well aligned with the real-world.

The MVC concerns closely parallel how we learn and think and the kind of specialists society produces. The model reflects a highly analytical mindset whereas the view requires the most creative thinking. The controller is the most political because it must balance the needs of many potentially conflicting concerns.

MVC is a good modularization pattern because it isolates three major modes of thinking. All the hard-analytical work of the system is isolated in models and can be done while ignoring everything else. The creative, intuitive and emotional work of a view can be done without worrying about any analytical concerns. The only sane way to make sure every user's needs get met is to ignore the details and instead focus on the big picture. That happens in controllers. Good MVC design not only modularizes code but it also compartmentalizes our mental modes for working on the code.

Decoupling & Evolution

Perhaps the most important aspect of MVC concerns the long term maintainability of code. MVC decouples the system's three main components allowing them to evolve independently.

In a monolithic system there are many opportunities for coupling artifacts. Changes to the visual layout, data-hiding or visual encoding are much more likely to effect data on disk. They may even break file backward compatibility. In the other direction, changes in how data is stored such as adding or removing fields, or restructuring for increased reliability, consistency or efficiency are in danger of breaking views or being exposed directly to the end user. Not only do changes anywhere in the system potentially effect all other parts of the system, but because of those large scale implications, in large projects any number of people may need to be consulted before making those changes.

MVC creates a strongly decoupled system. By minimizing the interface between each part and making sure each concern is handled by the right component, most changes only effect the component being changed. Decoupled views, for example, can change their presentation and even present new slices and summations of the data with no change to any models and little change to its controller.

Decoupling the model allows all kinds of changes to be made without touching controllers or views. It is nearly trivial to maintain backward compatibility when changing a file format: make two models, one for each version. It is much easier to add or remove information from a decoupled model. Placing all model related code inside a well defined module also makes it easy to make powerful changes to its performance. For example, it becomes much easier to add indexes for accelerating queries.

Sometimes it is impossible to make changes in a monolithic system that are trivial in a well modularized MVC system. Decoupling can make the impossible possible. Changes which were previously difficult can become easy, and programmer productivity typically skyrockets. The bottom line is model, view and controller modules can evolve much faster independently than they can as a monolithic whole.

An Alternative Description

Many great people have contributed to MVC over the past 30+ years. Apple has been a strong proponent of MVC design since 2002 with the introduction of OSX. The modern Macintosh operating system is based strongly on Objective-C which in turn is a marriage of C and SmallTalk. Since MVC was the "SmallTalk way", it's only natural for OSX to follow. Apple has a nice description of MVC:

The Model-View-Controller design pattern (MVC) is quite old. Variations of it have been around at least since the early days of Smalltalk. It is a high-level pattern in that it concerns itself with the global architecture of an application and classifies objects according to the general roles they play in an application. It is also a compound pattern in that it comprises several, more elemental patterns.

Object-oriented programs benefit in several ways by adapting the MVC design pattern for their designs. Many objects in these programs tend to be more reusable and their interfaces tend to be better defined. The programs overall are more adaptable to changing requirements - in other words, they are more easily extensible than programs that are not based on MVC.

Objective-C & Cocoa Documentation

The Essence of MVC

The question is not if you should modularize your system but how. Model-View-Controller is an excellent first pass. If you are programming in an object-oriented language you almost certainly should be using it.

The gospel of MVC as I've come to understand it comes down to three carefully chosen definitions with three key benefits:

Definitions of MVC

MVC is a modularization pattern that classifies all modules in the system into three roles:

• Model: consistently store, query and alter the important data
• View: communicate model data and user interface to human or computer clients
• Controller: receive, interpret, validate, act on and respond to client inputs or other events

Benefits of MVC

• MVC allows data-engineers, UX designers and system experts to focus on what they do best.
• MVC is an excellent way to compartmentalize complexity and isolate mental modes.
• The model, view and controller can evolve much faster independently than they could as a monolithic whole.

This work is licensed under a Creative Commons Attribution 3.0 Unported License. Copyright (c) Shane Brinkman-Davis, December 2012

Literate Randomizer

Yesterday I was seeding my database for a new Rails project. This project has profile pages with large free-form text fields. In order to get a good sense of how the site layout feels with real data, I needed some decent fake profiles. The existing tools we were using just weren't cutting it.

There are several gems available to help with this task.

Here is a quick-link to Literate Randomizer's readme and source.

Faker

Faker is great for generating fake names and addresses, but when it comes to generating fake prose, it follows the Loren Impsum model of obvious nonsense. This was not going to cut it:

Mollitia id adipisci. A voluptatum et veritatis quas enim veniam consectetur. Id perferendis quia eum et. Rerum consequatur harum quisquam impedit sit et.

Qui est qui autem inventore esse laboriosam. Vitae expedita numquam eveniet repudiandae voluptatibus est in. Ratione eos maxime ut debitis illo. Voluptatibus ea molestiae et quas non est.

Et ut distinctio qui nihil consequatur odio. Labore voluptas magni sapiente totam. Sed sed est nobis quia temporibus pariatur. Nihil accusamus molestiae qui occaecati ut. Sed consequatur nobis quis consequatur rerum.

random_data

RandomData was next. RD did generate some more convincing prose, but if you glance the source you'll see it is simply randomly selecting from 23 fixed sentances

Soaring through all the galaxies in search of Earth flying in to the night. Every stop I make I make a new friend; Can't stay for long just turn around and I'm gone again. Hey there where ya goin, not exactly knowin'. Excepteur sint occaecat cupidatat non proident sunt in culpa qui officia deserunt mollit anim id est laborum. He just keeps on movin' and ladies keep improvin'.

Lorem ipsum dolor sit amet consectetur adipisicing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. He's going everywhere, B.J. McKay and his best friend Bear. Ulysses, fighting evil and tyranny with all his power and with all of his might. Ulysses, fighting evil and tyranny with all his power and with all of his might. Every stop I make I make a new friend; Can't stay for long just turn around and I'm gone again.

Literate Randomizer

If you want to generate a lot of random prose, neither of the above options work well. With a little googling I ran across this post by Tim Riley. In it he shows some code for using Markov-Chains to generate plausible prose generated based on a source text. Using that source text, we can get a probability distribution of which words follow which words. Given that we can generate some near-english truly random sentences.

Note: RandomData has a Markov tool, too, but it is very limited. I found another gem that just copy-pasted Tim's code into a gem-file, but it wasn't properly packaged nor usable.

I was bummed to realize Tim hadn't made a gem of his wonderful little insight, so I thought I'd dive in and do it for him. I thought I could just copy Tim's code, give him credit, and release a nice clean gem. Turns out it wasn't that simple, or perhaps I just had too much fun with this problem. Another problem with all the tools above is they don't give you much control over the randomly generated output. I wanted control over the length and number of sentences as well as the number of paragraphs. I wanted interesting punctuation. With Markov chaining, you end up with a lot of sentences that end in prepositions (the, and, of, etc...).

The result, is a nice little gem called literate_randomizer. Here is a simple example. For more, please go to the literate randomizer source/readme.

 require 'literate_randomizer'  
 LiterateRandomizer.word  
 # => "frivolous"   
 LiterateRandomizer.sentence  
 # => "Muscular arms round opening of sorts while Lord John Roxton."   
 puts LiterateRandomizer.paragraphs  

The last line outputs:

Memory at the narrative may have already as I could be reflected upon. Society in a dozen. Headquarters for the stream. Stream which if we. Iguanodon's hide and admirably the right line of Project Gutenberg-tm electronic. Forgive me down hull-down on every detail which! Until they were. Mantelpiece in front of a necklace and that same scene. Eighteen of a creature beside his white merchant or hope.

Rain must be. Falls the paths which may have opened out we limped homewards sadly mauled and no. AGREE THAT THE CHAIRMAN. Twentieth century and horrible havoc. Train of Crayston Medal for canoes we are the scent and they. Swooped something which had a purpose than the envelope but if this. Entirely sir why this book. All these creatures that on through the rope dangled down the dinosaurs. Exhaust of the vertebrate stage of them and it began amid shouting gesticulating. Worthy of the old volcanic vents and distribute it away and under the prevailing. Assured that they took into line of the cliff. Unloosed a frugal breakfast of it run to the chasm which with. Loosened our thwarted wishes of dark until they took one's heart to win through. Cotton jacket which you can exhibit to gain a refund of hers outlined.

Novelist could have a jacket which communicated with its wing. Colliery explosion and stroking. Town was justified if ever moved upon his remarks had returned to bring. XIII A Sight which the plateau and many small Japanese tray of fairyland. Sadly mauled and flitted about that all turning these lumps of such. Cutting a sentiment. Grieved for us give. Whites our largest I should be confuted if animals then the prospect of the risk? Camberwell tram with a sheet of language is our zareba.

LiterateRandomizer.paragraphs options:

• :first_word => nil - the first word of the paragraph
• :words => range or int - number of words in sentence
• :sentences => range or int - number of sentences/paragraph
• :punctuation => nil - punction to end the paragraph with
  (nil == randomly selected from punctuation_distribution)
• :paragraphs => range or int - number of paragraphs
• :join => "\n\n" - join the paragraphs
  If :join => false, returns an array of the paragraphs

Learnable Programming

More great stuff from Bret Victor: http://worrydream.com/LearnableProgramming/

Start by jumping through and watching the embedded videos. They are self explanatory. Watch them right now. It'll only take a few seconds each.

I started working along a similar line about a decade ago. I called it "interactive execution". The key idea is the program is re-run with every single change you make. All values are logged. You can see the actual inputs and outputs of every function for the entire run. You can see them update in realtime as you edit your code. It is easy to dismisses these ideas as non-applicable in "real-world-code":

These design principles were presented in the context of systems for learning, but they apply universally. An experienced programmer may not need to know what an "if" statement means, but she does need to understand the runtime behavior of her program, and she needs to understand it while she's programming.

A frequent question about the sort of techniques presented here is, "How does this scale to real-world programming?" This is a reasonable question, but it's somewhat like asking how the internal combustion engine will benefit horses. The question assumes the wrong kind of change.

Here is a more useful attitude: Programming has to work like this. Programmers must be able to read the vocabulary, follow the flow, and see the state. Programmers have to create by reacting and create by abstracting. Assume that these are requirements. Given these requirements, how do we redesign programming?

I believe it isn't that hard to imagine how to apply "interactive execution" to real-world code. Two simple tricks allow you to achieve useful application of these ideas in any sized (single-threaded) code-base:

1. Allow the programmer to select a function as the start-point. Execute the program up to the start of that function and start a transaction against the entire running state of the code. Then, roll back the transaction with every change and restart execution from that start function.
2. Run the execution in a separate thread from the editing thread. Every character typed aborts the execution and restarts it. If the execution takes a second or two, that's OK. When the programmer wants to see the current outputs, they just stop typing for a bit. If it takes minutes or hours, the programmer is in charge of picking a better start point for her transactional, interactive-execution session.

This is really powerful stuff. I've often noticed that the skill level of a programmer is proportional to how long they can go between coding and executing their code to see if it works. The key skill here is being able to simulate the computer in your head. What a waste! The computer can simulate itself much better than your head can. Let the computer do what it's good at, and leave the human mind open to being creative.

I liked this quote about OO:

Bob Barton [said] "The basic principle of recursive design is to make the parts have the same power as the whole." For the first time I thought of the whole as the entire computer, and wondered why anyone would want to divide it up into weaker things called data structures and procedures. Why not divide it up into little computers... Why not thousands of them, each simulating a useful structure?

I think I'll start calling objects "little computers".

How to Create a Turing Complete Programming Language in 40 Minutes

Using a programming language is cool. Writing a programming language is cooler. Writing one in 40 minutes rocks! I just released a screencast on how to create a Turing Complete programming language in 40 minutes and 70 lines of code using my Babel Bridge parser generation gem and Ruby.

In this example I use my Babel Bridge parser-generator gem: homepage / github

Here is the 70-line-source-code from the screencast.

We continue to need fresh minds and new approaches to programming. There are many great challenges facing us in improving programmer productivity and supporting programming in our massively parallel age. I hope this screencast wets your appetite to pick up a parser-generator and play around with your own language. Maybe you'll invent the next Ruby, Java or Javascript!