Brushing up on C++

Leave a reply

It has been a couple of years since I last wrote C++ regularly and a lot have happened with the C++ standard since I wrote C++ for realtime embedded systems running on VxWorks or OpenGL glass-smashing-simulating ball-throwing fun.

C++11 have added a bunch of nice changes to the language, both with new features as lambdas, range-based for-loops and the changed auto-keyword, language-’fixes’ like uniform object initialization and nullptr constant and performance-improvements with move-semantics as well as many other improvements.

Following all these changes I’ve been brushing up on my C++ in the last couple of weeks by watching the excellent videoes by Kate Gregory on pluralsight.com as well as reading the third edition of Scott Meyers classic Effective C++ (even if some of the things aren’t as relevant in C++11 as in C++98 and C++03) which he’s working on a fourth edition of.

But what better way to brush up on a programming language than to actually write something in it? That is why I decided to port my professor solver to C++, if you don’t remember it’s a solver for a board puzzle game called ‘Professor Spillet’ and is implemented with a branching depth-first search through all valid “configurations” of the board.

Since C++ is all about raw power and great control I were curious to find how much a straight translation from C# to C++ would net in a performance improvements. At first I were horrified to find that my C++ implementation were much much slower… that was until I remembered just how horrible performance debug-builds in Visual Studio have, after I changed it to release it ran in around 500 msecs compared to the 5 seconds of C# – ten times faster – and that’s with C++ written by someone who hasn’t really written C++ in a couple of years!!

The code for my C++ implementation is up on github at ssboisen/ProfessorSolveCpp.

Git hook to prevent unsaved modified files

Leave a reply

When working with Visual Studio and git it happens quite often that you create a git commit and later realize that you had unsaved modified files – this is annoying and potentially problematic if you pushed your code in the meantime. It typically happens when you add a new file to a project – modify the file and save it but forget to save the project.

In order to solve this annoying problem I created umf-hook – the unsaved modified files git-hook which uses a pre-commit hook written in bash along with a c# application that communicates with Visual Studio through COM in order to discover any unsaved modified files.

Installation is easy, all you have to do is to write the following when located in the root of your repository

curl -L http://tinyurl.com/umf-hook | bash

Check out the repository at github for additional information.

Silverlight, GZip and ServiceStack

Leave a reply

One of the many things that were cut from .NET when Microsoft created Silverlight was the GZipStream class which is available from the System.IO.Compression namespace in the BCL. This means that Silverlight does not have built-in support for GZip compression when working with http. Normally one can instead delegate this to the browser by using the WebRequestCreator.BrowserHttp property which returns a IWebRequestCreate which again can be used to create WebRequests handled by the browser.

This would have been all fine and dandy if it wasn’t for a problem which I’ve encountered while using ServiceStack together with Silverlight. When using the build-in browser-support exception deserialization doesn’t work because the stream being returned from the WebException.Response.GetResponseStream() is null when it should have contained the response stream which contains a serialized version of the serverside exception-details.

This means that without figuring out a solution we effectively have a choice between compression or exception serialization support. How can we solve this? By doing the compression ourself which as it turns out is rather easy because luckily a modified version of DotNetZip supports GZipStreams on Silverlight – however it’s not an official build so YMMV.

On the client we create a compression-decorator that inherit from the JsonServiceClient which comes with ServiceStack and we simply wrap the response-streams in either a compressing or decompressing gzip stream based on whether your serializing or deserializing.

public class GzipJsonServiceClient : JsonServiceClient { public GzipJsonServiceClient(string baseUri) : base(baseUri) { } public GzipJsonServiceClient(string syncReplyBaseUri, string asyncOneWayBaseUri) : base(syncReplyBaseUri, asyncOneWayBaseUri) { } public override void SerializeToStream(IRequestContext requestContext, object request, Stream stream) { using (var memStream = new MemoryStream()) { base.SerializeToStream(requestContext, request, memStream); var zipped = GZipStream.CompressBuffer(memStream.ToArray()); stream.Write(zipped, 0, zipped.Length); } } public override StreamDeserializerDelegate StreamDeserializer { get { return UnZipper;} } private object UnZipper(Type type, Stream fromStream) { using (var unzipped = new GZipStream(fromStream, CompressionMode.Decompress)) return base.StreamDeserializer(type, unzipped); } }

One problem we encounter now is handling the compression on the serverside. Since we can’t modify Accept-Encoding and many other http-headers in Silverlight we need some other way to tell ASP.NET that what we’re sending is in gzip and that it should reply to us with content encoded in gzip. The best way that I’ve come up with for now is to rely on the fact that we can host our ServiceStack services on e.g. the /api/ path. We then add the following to our Global.asax.cs file. This will ensure that both requests and responses are compressed using the build in .NET GZipStream class. Since both DotNetZip and .NET GZipStream are RFC 1952 compliant they can work together without problems.

protected void Application_BeginRequest(object sender, EventArgs e) { if (this.Request.Url.AbsolutePath.Contains("/api/")) { this.Request.Filter = new System.IO.Compression.GZipStream(this.Request.Filter, System.IO.Compression.CompressionMode.Decompress, true); this.Response.Filter = new System.IO.Compression.GZipStream(this.Response.Filter, System.IO.Compression.CompressionMode.Compress, true); } }

We now reached our goal and have both compression and exception serialization support while using Silverlight with a ServiceStack service.

Huffman coding in Clojure

Leave a reply

Lately I’ve been reading Functional Programming for the Object-Oriented Programmer which is a book by Brian Marick that I discovered when Uncle Bob recommended it on the 8thlight blog. It’s a great introduction to functional programming and I especially enjoyed the chapters on Monads and embedding a object-oriented language in Clojure in which he quite brilliantly demonstrates how to implement a rather complex object-system (similar to rubys) using nothing but maps with functions, data and meta-data as well as a few utility functions.

Reading the book reignited my interest in Clojure. I’ve been meaning to dive into a lisp-dialect for a long time since it has been 3 years since I looked at Scheme and that was only briefly as part of a functional-programming course which I never completed. I’ve also been listening to Mostly λazy - a podcast about Clojure and while you won’t learn any concrete Clojure from listening to it, it’s a great introduction to what is happening in the Clojure community as well as a great enthusiasm booster since everyone on the podcast is so passionate.

There is a lot of great material available for learning Clojure, there’s the official casts, Full Disclojure casts, a free course on udemy.com, a bunch of great books, several different community resources aswell as 4clojure.com.

To get my hands dirty I decided to reimplement my huffman encoding solution in Clojure. It’s probably not the most idiomatic Clojure code since it’s pretty much the first significant piece of lisp-code I ever wrote. Tips for improvements are much welcome!

(defn branch? [node] (= (:type node) :branch)) (defn get-chars [node] (if (branch? node) (:chars node) [(:char node)])) (defn leaf [char weight] {:char char :weight weight :type :leaf}) (defn branch [left right] {:left left :right right :chars (sort (into (get-chars left) (get-chars right))) :weight (+ (:weight left) (:weight right)) :type :branch}) (defn create-code-tree [text] (letfn [(combine-trees [trees] (let [[fst snd & r] trees] (if (nil? snd) trees (recur (sort-by :weight (cons (branch fst snd) r))))))] (first (combine-trees (->> (frequencies text) (sort-by second) (map #(leaf (first %) (second %)))))))) (defn decode [tree bits] (loop [_tree tree bits bits chars []] (if (branch? _tree) (let [bit (first bits) v (if (= bit 0) :left :right)] (recur (v _tree) (rest bits) chars)) (let [chars (into chars (get-chars _tree) )] (if (empty? bits) chars (recur tree bits chars)))))) (defn encode [tree text] (letfn [(has-char? [tree c] (some #(= c %) (get-chars tree)))] (loop [_tree tree chars text bits []] (if (empty? chars) bits (if (branch? _tree) (let [v (if (has-char? (:left _tree) (first chars)) :left :right) bits (conj bits (if (= v :left) 0 1))] (recur (v _tree) chars bits)) (recur tree (rest chars) bits)))))) (defn fast-encode [tree] (let [code-map (into {} (map #(hash-map % (encode tree (str %))) (get-chars tree)))] (fn [text] (reduce (fn [s c] (into s (get code-map c))) [] text))))

Huffman coding in F#

Leave a reply

I’m enrolled in an excellent course at coursera.org in functional programming with Professor Martin Odersky as instructor. Each week we the students have to complete an assignment and this week was to implement Huffman encoding. The course is using Scala as implementation language for obvious reasons considering who the instructor is. Due to the honor code at cousera I’m not allowed to make my solutions to the assignments available for anyone else which is why I decided to reimplement Huffman encoding in F#.

I’ve embedded my implementation in a gist in the bottom of the post so jump ahead if that’s all your after.

The implementation consists of three functions createCodeTree, decode and encode each containing one or more helper functions, there’s also a fastEncode which is creates a map of the alphabet where the values for each key is the bit encoding for that char, it then returns a function which closes over this map and uses it to encode any text conforming to the alphabet of the codetree.

I think this small piece of code is a great example of some of the strengths of F#:

Datastructures: Descriminated Unions are awesome for expressing recursive data structures like trees and graphs but also for any other kind of choice structure – it’s like enums on steroids.
Conciseness and expressiveness: You can pack a lot of functionality in very little space while the code remains very readable and understandable. Compare this to C# where the size of the code implementing the classes hierarchy to express the binary Huffman tree would probably be larger than the hole solution in F#.
Type inference: The code looks almost dynamic because so little type information has to be embedded in the code due to the fantastic type inference in F# – compare this to C# where you have to put types on pretty much everything.
Pattern matching: Don’t you just love pattern matching? It makes working with all sorts of data incredibly easy. I’m not even using advanced pattern matching techniques like active patterns.

Using the implementation is straight forward – first you construct a coding tree which is then used for both encoding and decoding, below is an example. If you have any questions about my implementation please don’t hesitate to ask on this blog, on twitter or in person if you happen to bump into me.

let ct = createCodeTree "abcdefghijklmnopqrstuvxyz " let encoded = fastEncode ct ("simon says fsharp rocks" |> List.ofSeq) let decoded = decode ct encoded printfn "%A" encoded printfn "%A" decoded

type CodeTree = | Branch of CodeTree * CodeTree * list<char> * int | Leaf of char * int let chars tree = match tree with | Branch(_,_,chars,_) -> chars | Leaf(char,_) -> [ char ] let weight tree = match tree with | Branch(_,_,_, weight) | Leaf(_, weight) -> weight let createCodeTree text = let rec combineTrees trees = let makeCodeTree l r = Branch(l,r, chars l @ chars r, weight l + weight r) match trees with | fst :: snd :: rest -> combineTrees (makeCodeTree fst snd :: rest |> List.sortBy weight) | _ -> trees let orderedLeafList = text |> Seq.countBy id |> Seq.sortBy snd |> Seq.map (fun f -> Leaf(fst f, snd f)) |> List.ofSeq orderedLeafList |> combineTrees |> List.head let decode tree bits = let rec doDecode _tree bits chars = match _tree with | Branch(l, r, _, _) -> match bits |> List.head with | 0 -> doDecode l bits.Tail chars | 1 -> doDecode r bits.Tail chars | _ -> raise (ArgumentOutOfRangeException "Invalid bit in bits") | Leaf(c, _) when bits.IsEmpty -> c :: chars | Leaf(c, _) -> doDecode tree bits (c :: chars) doDecode tree bits [] |> List.rev let encode tree text = let hasCharInBranch tree c = match tree with | Branch(_, _, cs, _) -> cs |> List.exists (fun _c -> _c = c) | Leaf(char, _) -> char = c let rec doEncode _tree (chars : list<char>) bits = if chars.IsEmpty then bits else match _tree with | Branch(left, right, _, _) -> if hasCharInBranch left chars.Head then doEncode left chars (0 :: bits) else doEncode right chars (1 :: bits) | Leaf(c, _) -> doEncode tree chars.Tail bits doEncode tree text [] |> List.rev let fastEncode tree = let codeMap = chars tree |> Seq.map (fun c -> (c, encode tree [c])) |> Map.ofSeq fun text -> List.foldBack (fun c s -> Map.find c codeMap @ s) (text |> List.ofSeq) []

Colon in powershell

Leave a reply

In powershell the colon has a special meaning as a variable scoping mechanism. When you want to execute a command that include a colon as a regular colon you have to work around this. One case where this will happen is if you try to automate the deletion of remote branches in git since the syntax for deleting a branch featureX at the remote origin is git push origin :featureX. The solution to this problem is to either use string concatenation into a variable and then use that variable or simply escaping the colon by surrounding it with open and closed curly brackets.

Here i’m selecting all remote branches which have been merged into my current local branch (e.g. master) and which matches a regular expression and then i delete those branches at the remote called origin.

Day two of GOTO Aarhus 2012

Leave a reply

Another day with awesome talks is over and here are again my summary of and comments to the talks that I chose to attend on the second day of GOTO Aarhus 2012.

Again I want to start with the Keynote which this time around was by Scott Hanselman from Microsoft. I was actually pleasantly surprised by how good the talk was – he managed to make it very little about how cool Microsoft is though I still don’t quite agree with all of the points he made and think he could have used his time better considering it was a keynote – I don’t need to see a demo of an editor.

Scott Hanselman talked at length about how he thought that people needed to free themself from some of the frameworks like jquery and instead just write proper javascript – while I totally agree with the sentiment that developers should master their basic tools – I think it’s a bit off considering his main points. Those seemed to be that javascript were assembly of the web (which to me means something you build abstractions on top of to gain productivity) and that vendors needed to supply better tooling case in point what Microsoft were doing with Web essentials package and TypeScript. If jQuery isn’t a productivity enhancing tool that handles some of the problems in javascript by abstractions I don’t know what the hell it is – so to me it seemed like jQuery is an example of exactly what Scott were asking for.

Array Thinking – Escaping the Groove?

When I initially looked at the schedule for GOTO Aarhus 2012 I didn’t give this talk by David Leibs much thought but by chance I ended up on APLs wikipedia-page the other day and thought the language looked really interesting, really weird and potentially mindblowing. Then when I were reading through the program this morning trying to decide which talk I wanted to attend I noticed that it were about APL so I just had to see this talk – and boy it did not dissapoint. To me this was one of those talks where you feel really lucky that you were there – where the speaker catches you by surprise and introduces you to a wonderful new world that you did not even know exist. While I must agree it made my head hurt it was in a good way.

David Leibs, who worked at both NASA and at the Xerox Labs, started by describing how he imagines the human mind a bit like a groove generated by continues drops of water – much like how rainfall over thousands of years generates canyons. When we learn something it shapes who we are and to explore the other canyons of knowledge we need to make an effort – this is especially true if the grooves are formed early in our life. When we do learn something radically new it expand our minds – case in point Array-programming. This rain-drop metaphore is an example of path dependence.

He then continued to describe the history of APL how it started with Keat Iverson who were looking for a better mathematical notations where precedence didn’t matter and how he created APL at IBM. The great idea in APL was that data is multidimentional and that you should be able to express this easily in code allowing for both 0-cell data which is just scalars aswell as e.g. 3×4 frames of rows. APL became tremendiously popular in the 70′s for various reasons but declined in the 80′s though it’s still being used in e.g. the financial domain (which is evident from this job-post at SimCorp). APL2 is highly parallizable which is a property it has due to the nature of array-programming which encourage loopless big thinking.

David Leibs then went on to display some examples of APL which even though he tried hard to help the audience with animations were sometimes hard to follow. Having done this aswell as made the audience have some good laughs based on the fact that this were so radically different and to new-commers quite incomprehensible he shifted the talk into dealing with how we can aid learning by making the computer a part of the physical environment by getting the computing of the computers and down on the floor. He displayed what seemed to be mockups of an APL inspired iPad puzzle-game where one could see the flow of the data using continues evaluation as one added and modified the operators and inputs – this reminded me of Light Table - it seemd like something which could be a great introduction to the array-programming way of thinking. He ended the talk like any good talk by comming back to the initial premise and said roughly that we have been using computers for 50 years and almost everyone is thinking in terms of loops – in 50 years we will still be using computers – so let’s get of the path dependant by carving a new groove.

Sex and Violence: Social and Technical Lessons from the Perl 6 Project

In this talk by Damian Conway he described eight lessons learned from running the perl 6 project for more than a decade. It was a great and funny talk which also gave may concrete lessons and examples on the improvements that have happened from perl 5 to 6 and how it’s almost another language now.

Lesson #1: Have pithy goals. Since it’s far too easy to stray from the objectives you should encode your project goals in catch phrases which you compare the decisions you make against. Hoffmanize (that is make short) keywords that are used the most since it increases readability.

Lesson #2: Optimize for the common case. They analyzed the many gigabytes of code in CPAN and found the common cases of patterns and optimized those patterns away by making build-in syntax that replace those patterns. Many tiny improvements which leeds to stress reduction.

Lesson #3: Ignore the haters, stay zen. More people will not know about your project and like it if they did than who know it and hate. Never try to teach a pig to whizzle, it waste your time and annoys the pig. Do however sometimes evaluate the criticism since your not perfect.

Lesson #4: When a system grows organically it tend to become incomprehensible so take your time and design it properly

Lesson #5: Stay humble and throw away enough prototypes. Larry Wall is smart enough to know he’s not smart enough.

Lesson #6: Less is more. Handy way to handle feature creep: to add a feature you have to take out two excisting or the new thing should do two things

Lesson #7: Listen to the market.. and ignore them in general but consider suggestions and examinate them.

Lesson #8: Avoid single point of failure by backing up the knowledge and expertise of developers – if a project has a benevolent dictator back him up

Runaway complexity in Big Data systems… and a plan to stop it

In this talk Nathan Marz presented his Lambda Architecture – it was another great talk where he addressed concrete problems. Other than describing his Lambda Architecture which I also described here he started the talk by saying how in order to lower human fault-tolerance we need to make the data immutable so CRUD becomes CR. First he stated that denormilization gives hard problems as data grows and evolves over time but it is necessary for optimization – but you should still keep your data normalized in the back-back-end. He then went on to say something that can almost be considered controversial in this day and age which was that schemas have a bad rap but that schemalessness is a bad overreaction. Schmas is basicly function(data) : validation. Some of the values of of schemas are structural integrity and safeguarding against corruption. We need to create better schma tools that among others help us with evolving the schema over time, which give fast and space efficient serialization. Nathan Marz believes that as times go by RDBMS will become a footnote because of the fundamental problems with mutability.

Component Programming in D

Walter Bright described how he had been writing software for 35 years but even though he tried he had created very little truely reusable code. He describes how his abstractions become leaky and how components often work for type T but not for type U. He described how component programming have previously been tried solved in C++ by the STL but it still evolved around loops and not streams and transformations as is the case of the unix pipeline. He then presented D which implements a variation of what is know from functional programming languages, the unix pipeline and LINQ in C# but for an unmanged native close-to-the-metal language. He gave some examples on how some of the operators worked and it was all somewhat similar to what is done in Haskell, F#, Scala, LINQ etc. etc. It was an enjoyable talk but I think I would have been able to appreciate it more if I were walking in the C++ treanches every day and wasn’t so spoiled from having written these sort of abstractions in functional programming languages as well as many many lines of LINQ in C#.

Implementing Continuous Delivery

A great talk by Jez Humble on how to implement Continuous Delivery where his main point was that it’s almost always the people and the organization that is the problem and not the code – and how there is no excuse for not being able to implement continuous integration due to complaints about complexity. He had a great example with HP who introduced CI in their printer-firmware devision. I won’t go in to any more detail but instead point you to his book at amazon which covers everything in detail.

Day one of GOTO Aarhus 2012

Leave a reply

First day of GOTO Aarhus 2012 is over and I’m pretty happy overall. I did change up which talks I decided to watch compared to what I originally had planned. This is my summary of and experience from each of the talks I saw.

First of all I want to quickly mention the Keynote by Rick Falkvinge from the Swedish Pirate Party, it was a great talk with some great points though I think it’s fair to accuse Rick Falkvinge of simplifying the problems a bit – especially when he mentioned how you could get infinate space for you email for free – it’s not really free when it’s in exchange for ads and privacy.

The challenges of connected data

Jim Webber started his talk by giving a short history of databases and how it had all started with Edgar F. Codds paper entitled “A Relational Model of Data for Large Shared Data Banks” where not much changed and everybody though of data as squares with relations between them for some twenty years. It wasn’t until Tim Bernard Lee, being the lonely physicist he was, invented the web to move fleshy colored data around, the world began to think of data as interconnected webs of verticies.

After then having introduces three of the four main types of NoSQL datastores i.e. key/value (Riak), column-stores (Cassandra) and document (MongoDB) united under Martin Fowlers Aggregate Oriented Databases he presented Neo technologies graph-database Neo4j and gave a short introduction to the Cypher query language using the Dr. Who univers as an outset. For more information about cypher see the documentation.

Lastly he described some of the nice use-cases of a graph-database mainly for looking for patterns in datasets for e.g. doing retail analytics or real-time upselling and mentioned some of the customers they had like Adobe Creative Cloud and Cisco Network Management and sales.

Overall it was a very nice and very fun talk in large part due to Jim Webbers … communication style. I would however have prefered if less time had been used on database history and more on the query language and how Neo4j handles horizontal scaleability.

My Agile journey: XP, Scrum, Lean, Kanban and back again

My collegue Mogens and I arrived a few minutes late to this talk and had to sit on the flor which ment that I unfortunately couldn’t take many notes.

Jesper Boeg described how his attitude toward agile and the different methodologies have changed over time changing from very enthusiastic about scrum to very enthusiastic about lean and kanban to embracing both. He also touched on some of the problems different teams face when trying to be agile. It was very enlightning for me since I don’t have that much experience with doing either properly other than from studying and doing it in small projects at the university.

All in all Jesper Boeg concluded that whether you choose one or the other depends on the organization in which you try to introduce it. Scrum is best suited for teams and organizations which are ready for change and won’t work against it where Kanban is less invasive and can be easier to implement if the organization is not ready for a revolutionary change.

Big Data OLTP with Apache Cassandra

I have no doubt that Matt Dennis is a very skilled Cassandra engineer who understand the underlying data model to perfection and who know how to tune all of the knots and bolts in Cassandra, align the data just right, but I’m afraid his talk about Cassandra were not very good for a Cassandra-newbie and I feel he failed to explain the basics of Cassandra which left some in the audiance, myself and two colleagues included, somewhat unsatisfied and confused.

While the results he were able to display in term of adoption-rate, scalability and availability characteristics where very impressive I think atleast mentioning the basics of the data-model would have been appropriate considering the audience.

Having said that I think Cassandra looks to be a great proposition if you have the needs that it serves – it’s a shame it didn’t get a better introduction at GOTO Aarhus 2012. For additional talks about Cassandra see the homepage of Cassandra Summit 2012.

Scaling for Humongous amounts of data with MongoDB

I really liked the talk that Alvin Richards gave on MongoDB and I can’t help but compare it to Matt Dennis’ talk. One of the things Alvin Richards mentioned was that one of the primary reasons why many developers choose NoSQL databases often were to get more flexibility for rapid development compared to the world of RDBMS - having experienced the dread of constant schema-changes in a SQL-database I really think he’s right!

After having given a very short introduction to the reasoning behind MongoDB in relation to HW-price-changes, deployment stories and the CAP theorem Alvin Richards quickly described the three main factors that MongoDB solves i.e. Agility, Flexibility and Cost, three very important but in some of the other NoSQL talks somewhat overlooked factors.

The next part of the talk was based on the premise that we should let our use-cases influence our decisions about how we design our schemas and he presented different ways one could structure the schema in MongoDB to best solve the Twitter use-case. He touched on when you would want to use Partioning or linking versus embedded and buckets. Basicly partitioning (much like an rdbms) is not very good for performance because of the many random reads and seeks it requires in order to load all from, embedded has the problem of large sequential reads and buckets which provides great performance because of small sequential reads.

With a bucket you add an extra dimension to your schema (in this case a temporal one), so a bit like sharding, in the sense that you store e.g. all tweets per user per day in one single document allowing you to quickly load the latest tweets for each user. While this sound wonderful I’m not sure what to think of the influence that this has on the data model if you want to consider other views of the data due to e.g. use-case changes – but maybe that’s just a matter of building up indexes – atleast that’s how Alvin Richards explained it to me when I asked him aftwards.

In the rest of the talk Alvin Richards talked about how to use sharding, replication and mongodbs five different durability-modes to solve the scalability, availability and partition-tolerance problems you might face with MongoDB.

The People vs NOSQL DB’s

While an amusing talk due in part to the bantering I don’t really think it helped much in clearifying when one would choose one NoSQL-strategy over the other – obviously it’s about tradeoffs, I specifically think that Martin Fowler should have mentioned some of the reasons why ThoughWorks had recommended one over the other – something he eluded to, without naming names, in one of his comments.

In the end it came down to a discussion of the CAP theorem and where each of the NoSQL-databases where placed in relation to each of the guarentees. I think it would have been nice if they had also discussed how ease of use and general usability of the database and its APIs affected the market – something which only Chris Anderson from Couchbase mentioned briefly.

In light of the CAP theorem discussion I though it appropriate to include an image by Nathan Hurst from his blogpost Visual Guide to NoSQL Systems. For a discussion of different use-cases for different types of NoSQL databases see 35+ Use Cases For Choosing Your Next NoSQL Database.

All in all a great day at GOTO Aarhus 2012!!

The Lambda Architecture

1 Reply

In Nathan Marz and James Warrens forthcomming book Big Data (now scheduled for fall 2013) they describe some of the problems which one runs into when trying to deal with Big Data with traditionel technologies like relational databases. The complexity of the system grows tremendously when you move data-logic such a sharding-key information to the application layer while maintenance becomes a greater burden leading to a system which lacks human fault-tolerance.

When designing an alternative and better solution it’s necessary to remember that supporting adhoc queries is important since nearly every large dataset has unanticipated value within it which gives businesses an opportunity to optimize its processes and products.

In order to limit the complexity as well as support arbitrary functions on arbitrary datasets and having the functions return its results with low latency Marz and Warren propose what they have called The Lambda Architecture which is a layerede architecture consisting of a Batch layer, a Serving layer and a Speed layer.

The Batch layer

In this layer which is in the bottom of the stack the system computes the arbitrary functions on an constantly growing immutable dataset in order to present batch views which reflects the ad hoc queries. This is where systems like Hadoop would be used since it’s the canonical example of a batch processing system. Another problem is that the data that the batch layer produces is often just flat-file indexes which maps e.g. an url and an hour to a number of views for that hour. In order to make these indexes queryable we need another layer. The batch layer runs in a loop updating the batch views as often as the batch-query completes.

The Serving layer

The job of the serving layer is to index the batch views to support effective queries for particular values of the batch view. This layer will be hosted in a distributed database that only needs to support random reads and batch updates, this allows the serving layer to be relatively simple – in the book they use ElephantDB which is a database that specializes in exporting key/value data from Hadoop developed by Nathan Marz.

The problem with the MapReduce cluster architecture of Hadoop however is that it were never designed for real-time data processing and thus introduces a great deal of latency since the computations even if scaled to many nodes can take quite a lot of time. We need another layer to support real-time analysis of the data.

The Speed layer

In order to support ad-hoc queries in real-time we need the speed layer to deal with the data which our system receives while the batch-layer is running. In order to do this it updates the real-time view of the data as it receives the data in incremental updates and only present an analysis of the most recent data and not the complete dataset as is the case with the batch layer. Once data previously only processed by the speed layer has been processed by the batch and serving layer it is discarded from the speed layer. In order to make the data it processes available the speed layer needs an database which supports both random reads and random writes which increases the complexity of the layer and thus gives a higher chance of something going wrong. However since only data which is a few hours old is present in the speed layer (depending on how long the batch processing takes) if something does go wrong one can discard the state for entire speed layer and everything will be back to normal within a few hours.

When querying the data from the application we query against both the speed layer and the serving layer in order to take all the data into account, this means that we have to merge the results of the two layers and depending on the data in question this merge-processing will be more or less difficult.

Nathan Marz will be presenting at GOTO with his talk Runaway complexity in Big Data systems… and a plan to stop it where he will be presenting the Lambda Architecture.

GOTO Aarhus 2012

Leave a reply

For the first time I’ll be attending the international GOTO conference which is being held in Aarhus from the 1st to the 3rd of october. My colleagues Mogens and Rasmus had already been invited as technical bloggers and I were so fortunate that they secured me a spot aswell. So thanks to those guys and especially thanks to Trifork for inviting me.

I’ve wanted to go the last couple of years but were never able to so I’m very exited about finally going to GOTOcon because it’s an awesome conference for a polyglot programmer since they offer such a broad range of topics in various languages.

The conference has a bunch of great things to offer – first and foremost are the talks. There are five keynotes, 85 sessions in 25 tracks ranging from user-interface techniques over cloud-application-architecture to programming-languages, the speakers count such prominent names as Martin Fowler, Anders Hejlsberg, Dan North and Nathan Marz just to name a few. Unfortunately the ever so awesome Erik Meijer won’t be speaking but will be hosting a training session about the principles of pure lazy functional programming.

Other than providing a wealth of different interesting talks GOTOcon offer a conference party, an exhibitor reception and user group events all of which are great opportunities to network which is one of the reason I attend conferences.

The curse of a multi-track conference is that you can only attend a fraction of the sessions which means that you have to pick and choose exactly which of the many great sessions you think will be the most interesting to you.

I’m quite interested in talks about Big Data since I have a passion for machine learning and data mining and I’m involved in the Raptor Smart Advisor product from my employee d60. Luckily GOTO has a bunch of talks on big data and many of which are scheduled for monday. I will be attending The challenge of connected data by Jim Webber, Go Simple, Fast, Elastic with Couchbase Server and Document-oriented Data management by Chris Anderson, Big Data OLTP with Apache Cassandra by Matt Dennis, Splunk in operations by Karsten Thygesen and The People vs NOSQL DB’s with Martin Fowler et al.

I still havn’t settled for my exact schedule for tuesday and wednesday but I know that I want to attend Building Distributed Systems with Riak Core by Steve Vinoski and Runaway complexity in Big Data systems… and a plan to stop it by Nathan Marz.

See you at GOTO Aarhus 2012!