Build your own operating system

Ten years ago (around the year 2001) I wrote a simple x86 protected-mode OS just to find out how operating systems work. That was really great fun and I learned very much about OS concepts and paradigms (and also a lot of stuff about computer hardware, programming, software architecture, data structures etc.). Ever since the gathered experience and knowledge by building my own operating system has been extremely valuable.

I began by reading Andrew Tanenbaum's book "Operating Systems: Design and Implementation" during which I studied a lot of Minix source code. Later I also read his other books about modern operating systems and structured computer organization.
To get started with this challenging task, one needs some profound knowledge of the memory-management-unit (MMU) of the x86 CPU and its protected mode. To me, the best known tutorial on the web is the "Protected Mode Tutorial" by Jens Hohmuth of the Westsächsische Hochschule Zwickau. Sadly, this tutorial is only available in german. If you do not speak german you may try to translate it with Google Translate. The best parts of the tutorial are its great assembly language examples for Borland's TASM and Microsoft's MASM. I typed in all the examples by hand and played with them until I understood every single line of code :-). What is also helpful to understand the MMU and protected-mode of the x86 CPU is Intels Architecture Software Developer’s Manual and Hans-Peter Messmer's book The Indispensable PC Hardware Book.

The protected-mode tutorial starts by explaining how virtual addresses are mapped to physical addresses using the x86 MMU's two-level page table. Thus one will understand how a modern OS implements the process address spaces and how it protects processes from each other. You should also get the idea about how the OS lays out executables and shared libraries within the process address space and how it creates shared memory regions.
Two core abstractions of every modern OS are processes and threads. The multitasking chapter of the tutorial will give you some insights on how an OS may implement them for the x86 CPU. Therefor, the examples of the tutorial use segment descriptors and task state segments. The Global Descriptor Table (GDT) contains segment descriptors for the code, data and stack segments of a process. A Task State Segment (TSS) is used by the examples to implement a process (with one thread) on the x86 CPU. Each process or thread has a context which includes the code, data and stack segments, its program counter, a reference to its page table, etc.
Be aware, that modern OSes do not use disjoint segments anymore. They use a flat memory model where all x86 segments refer to the same virtual address space. The virtual address space is build using the MMU's two-level page table as explained above. Also be aware that e.g. Linux or Windows do not do hardware context switches using different task state segments. Instead they just create one TSS per CPU and do the switching stuff by themselves (see [1] and [2]). But if you understand the tutorial examples you will also get what Linux and Windows are doing and how they are doing it.
A modern OS kernel securely offers its features to user space programs via the system call interface. Since the system calls are the only valid entry points into the kernel for user space programs it is only possible to call them using special CPU features. Depending on the CPU architecture this may be done by call gates, special assembler instructions like syscall, or software interrupts.
Monolithic operating systems usually have a lot of system calls to offer a bunch of features to user mode programs while microkernel operating systems normally only have a minimal set of system calls. Hence, microkernel operating systems implement a lot of features by supplementary user mode OS services and provide them to user mode programs using inter-process communication (IPC) mechanisms.
Interrupts and exceptions are managed and handled on the x86 CPU using the Interrupt Descriptor Table (IDT). E.g. the timer interrupt triggers the scheduler from time to time to switch from one process to another to achieve true multitasking. Another example is the page-fault exception which is the starting point for the paging mechanism available in every modern desktop or server OS. This exception is risen every time a program tries to access a memory page that is currently swapped out to disk. The OS handles it by mapping the missing memory page back into the process address space before it executes the process again.

The protected-mode tutorial closes with a really great multitasking example where four processes draw pretty cool animations onto the display in VGA graphics mode (click here for the source code). Here is how this example x86 protected-mode OS looks like by running it from the MS-DOS mode of Windows 98 SE:

With the profound knowledge about the x86 protected-mode you should be able to start writing your own hobby OS or to understand what is going on under the hood of a Linux, Mac OS X, Windows or QNX Neutrino operating system.
I have put all the source code from the protected-mode tutorial and a simple boot sector (bootloader) program into my blog repository.
Modern operating systems offer lots of other features we haven't touched yet like dynamic memory management, dynamic linking, file systems, networking protocol stacks, etc. But once you have understood and implemented the core OS concepts you could evolve your OS step by step or you may start developing code for one of the well-known operating systems.

To dig deep into modern OS design and architecture I suggest the QNX Neutrino OS Architecture Guide. It provides a lot of insights into microkernel operating systems, IPC, the process manager, dynamic linking, resource managers and device drivers, networking, priority inheritance and much more interesting stuff. You may also take a look at Microsoft's Singularity research OS.
If you want to get familiar with the Linux operating system I recommend the books Professional Linux Kernel Architecture by Wolfgang Mauerer and Linux Kernel Development by Robert Love.
For Mac OS X enthusiasts I would suggest Mac OS X Internals by Amit Singh. People who are interested in Windows might like Windows Internals from Mark Russinovich and David A. Solomon.
You should also take a look at Google's Android operating system. It has a neat and scalable architecture where a monolithic Linux kernel is extended by a really nice inter-process communication (Binder IPC) and software component framework. Above the Linux kernel Google's Android looks very much like a microkernel OS that is similar to the QNX Neutrino RTOS. Another microkernel OS that is very interesting is Miray's Symobi. I worked at Miray Software on the Symobi project some years ago where I build the networking protocol stacks and the USB device management OS services from scratch. So I really like the Symobi OS which is similar to the QNX Neutrino RTOS.

Oh, by the way you now also know how the two OS security concepts Data Execution Prevention (DEP) and Address Space Layout Randomization (ASLR) work. The DEP is a feature of the x86 MMU where each page table entry has an additional NX bit, e.g. to mark stack and data pages as not executable.
The ASLR feature affects the layout of executable programs and shared libraries within the process address space.


Some more links about operating systems and related topics:
My Blog Repository
OSDev.org
Assembler Programming Topics
"Get into protected mode, enable paging, do something useful, get out again" by David Lindauer
Protected Mode Basics by Robert Collins
The LOADALL Instruction by Robert Collins
A Memory Allocator by Doug Lea
Doing a Kernel in C++
Making plain binary files using a C compiler (i386+)
Skelix OS Tutorial (Protected Mode)
Intel Architecture Software Developer’s Manual
i386 Atomic Operations
Semaphores
Mixing Assembly and C
NASM Docs
Writing a Kernel in C
Writing Your Own Toy OS (Part I)
Writing Your Own Toy OS (Part II)
Writing Your Own Toy OS (Part III)
BareMetal OS
MMURTL aka Developing Your own 32-Bit Operating System by Richard A. Burgess
Miray Symobi
Can We Make Operating Systems Reliable and Secure? by Andrew S. Tanenbaum
Executable and Linkable (ELF) File Format
Portable Executable (PE) File Format
ARM Architecture Reference Manual
ARM Processor MMU

TED Talks: How great leaders inspire action

The author of the open letter to the BlackBerry bosses linked to this superb video about how great leaders inspire action.

See also: The surprising truth about what motivates us.

Purpose (in The surprising truth about what motivates us) == Why are you doing what you do (in How great leaders inspire action).

Hidden Champions

Als Heimliche Gewinner oder besser bekannt unter dem englischen Begriff Hidden Champions werden relativ unbekannte kleine oder mittelständische Unternehmen, die in ihrem Markt jedoch Marktrührer sind, verstanden. Aus dem Buch "Hidden Champions des 21. Jahrhunderts: Die Erfolgsstrategien unbekannter Weltmarktführer" von Hermann Simon hier einige (wenige) Auszüge:


Hidden Champions (im Bereich Softwareentwicklung):

• Brainlab AG
• SAP AG
• Lauterbach GmbH
• QNX Software Systems

Wachstum und Marktführerschaft

• Ambitionierte Ziele sind das Fundament, auf dem große Erfolge aufbauen.
• Hidden Champions wissen nicht nur was sie wollen, sondern haben auch die Willensstärke und Energie, manchmal auch die Besessenheit, ihre Ziele in Taten umzusetzen.
• Die hierzu erforderliche Einsatzbereitschaft und das Durchhaltevermögen sind in unserer Wohlstandsgesellschaft und in manchen Firmen die wahren Begrenzungsfaktoren des Wachstums, nicht die fehlenden Marktchancen.
• "Wenn du ein Schiff bauen willst, dann trommle nicht Leute zusammen, um Holz zu beschaffen, Aufträge zu vergeben und Arbeit zu verteilen, sondern lehre sie die Sehnsucht nach dem weiten, endlosen Meer."
• Vision ist das gerade noch Machbare!
• Die Ziele sind auf lange Fristen, eher auf Generationen als auf Quartale ausgerichtet.
• Den diversifizierten Konzern der Zukunft stelle ich mir als Gruppe von Unternehmen vor, die sehr wenige Schlüsselressourcen (z. B. Finanzen, Managemententwicklung, Marke) gemeinsam nutzen, die jedoch darüber hinaus ihre Einheiten wie unabhängige Hidden Champions operieren lassen.

Markt und Fokus

• Die Hidden Champions definieren ihre Märkte in der Regel eng und bauen in diesen Märkten starke Marktpositionen auf.
• Normalen Menschen und Unternehmen, die etwas erreichen wollen, kann man nur dringend raten, sich auf ein Gebiet zu konzentrieren. "Nur das, das aber richtig."
• Nur wenn man seine Ressourcen fokussiert, wird man ambitionierte Ziele realisieren.

Globalisierung

• Die Globalisierung ist die zweite Säule der Strategie der Hidden Champions. Sie macht die engen Märkte groß.
• Nichts wird in unserer Zeit und in den nächsten Jahrzehnten die Welt stärker verändern als die Globalisierung.

Kunden und Leistungsangebote

• Die enge und interaktive Kundenbeziehung ist häufig durch komplexe Produkte, die für Hidden Champions typisch sind, bedingt.
• Ein Projekt wird wie ein kleines, relativ autonomes Unternehmen geführt.
• Die Hidden Champions lehren uns, dass Kundenorientierung wichtiger ist als Wettbewerbsorientierung.

Innovation

• Innovation ist das auf Dauer einzig wirksame Mittel, um sich im Wettbewerb mit Erfolg zu behaupten. Innovation ist in erster Linie eine Frage der Kreativität und der Qualität, keineswegs nur eine Sache des Geldes.
• Eitelkeiten und Machtspielchen zwischen Abteilungen sind nicht erlaubt.

Wettbewerb

• Die gleichzeitige Erfüllung der drei Kriterien "wichtig für den Kunden", "vom Kunden tatsächlich wahrgenommen", und "dauerhaft/nicht leicht imitierbar" bilden eine große Herausforderung.
• Die Märkte der Hidden Champions sind überwiegend oligopolistisch.

Finanzierung, Organisation und Umfeld

• Die Selbstfinanzierung ist und bleibt die wichtigste Finanzierungsquelle.
• Die funktionale Organisation ist für viele Hidden Champions die natürliche Organisationsform.
• Die dünne Besetzung der Hidden Champions wirkt als erheblicher Prozessvereinfacher.
• Optimale Wertschöpfungstiefe: Hinter der Präferenz der Hidden Champions für das Selbermachen steckt eine tiefe, allgemeine Wahrheit: Einzigartigkeit und Überlegenheit im Wettbewerb können nur intern geschaffen werden. Alles, was man auf dem offenen Markt zukauft, ist auch anderen zugänglich und begründet insofern keine Sonderstellung.
• Einzigartigkeit erfordert deshalb Tiefe und eine gewisse Zurückhaltung gegenüber Outsourcing.
• Hidden Champions reagieren auf Geschäftsfelderweiterungen konsequent und schnell mit Dezentralisierung der Bereiche. Nur kleine, dezentrale Einheiten gewährleisten eine optimale Kundennähe und bilden damit eine Basis für die erfolgreiche Umsetzung der Hidden Champions-Strategie.

Mitarbeiter

• Hochleistung erreicht man nur mit einer Mannschaft, die eine starke Motivation und Identifikation mit dem Unternehmen aufweist.
• Hohe Leistung erfordert Intoleranz gegenüber Drückebergerei und die frühe Trennung von Mitarbeitern, die nicht mitziehen.
• Die Hidden Champions achten darauf, dass sie "mehr Arbeit als Köpfe" haben. Diese Bedingung minimiert unproduktive Tätigkeiten und Blindleistung und erweist sich als äußerst effektiver Produktivitätstreiber. Das Umgekehrte gilt ebenso: Überbesetzung wirkt als Produktivitätskiller und Treiber von Unzufriedenheit.
• Aufgrund ihres Wachstums sind die Hidden Champions große Arbeitsplatzschaffer im Inland wie im Ausland.
• Die Menschen sind immer weniger bereit, nur des Geldes wegen zu arbeiten. Sie suchen in der Arbeit vermehrt Sinn, Spaß und Erfüllung übergeordneter Ziele und Werte. Siehe dazu auch "The surprising truth about what motivates us".
• Die Auswahl der richtigen Mitarbeiter ist wichtiger als alle Organisations-, Prozess- und Ausbildungsmaßnahmen.

Führung

• Die Unternehmer des Aufbaus zeichnen sich durch eine Einheit von Person und Aufgabe, einer fokussierten Zielstrebigkeit, Furchtlosigkeit, Vitalität und Ausdauer sowie durch Inspiration für andere aus.
• Unternehmensgründer leben, was sie sind und was sie sein wollen. Diese Einstellung zur Arbeit bedeutet, dass Geld nicht die Hauptantriebskraft dieser Menschen ist. Die Hauptmotivation resultiert aus der Identifikation mit dem Unternehmen und aus der Befriedigung durch ihre Arbeit, ökonomischer Erfolg dürfte demgegenüber eine sekundäre Rolle spielen. Die volle Hingabe und Verantwortung verleiht solchen Führern bei Mitarbeitern und Kunden eine enorme Glaubwürdigkeit.
• "They exemplify to me the importance of being single-minded. The single-minded ones, the monomaniacs, are the only true achievers. The rest, the ones like me, may have more fun, but they fritter themselves away. The achievers carry out a mission; the rest of us have interests. Whenever anything is being accomplished, it is being done by a monomaniac with a mission." (Peter Drucker)
• "Nothing energizes an individual or a company more than clear goals and a grand purpose."
• Die Führungsstile der Hidden Champions sind ambivalent. Die Führung ist sowohl autoritär als auch partizipativ.
• Zur Schaffung eines Weltmarktführers braucht man viele Mitstreiter - und zwar aus aller Welt. Der Unternehmer muss das Feuer, das in ihm brennt, in vielen Menschen unterschiedlicher Kulturen entzünden. Das ist Führung!
• Die Unternehmensführer der Hidden Champions haben nicht die gleichen Hemmungen und Befürchtungen, die normale Menschen empfinden. Daher können sie ihre Fähigkeiten wirkungsvoller einsetzen.
• Vermutlich gehen Hidden Champions bei der Korrektur eingetretener Fehler schneller und entschiedener vor als andere Unternehmen.
• Die Aufgabe des Managements besteht darin, sich zwischen Umsatz und Kosten zu stellen und dafür zu sorgen, dass die beiden Abstand voneinander halten.

Strategieentwicklung

• Strategieentwicklung ist keine Einmalentscheidung, sondern ein Prozess, der sowohl Top-down als auch Buttom-up verlaufen sollte. Nur Kreativität, Originalität und Querdenken produzieren überlegene Strategien.
• "Find out what everybody else is doing, then do it differently."

"Die Hidden Champions beweisen, dass Management auch im 21. Jahrhundert vor allem dem gesunden Menschenverstand folgt. Indem man viele kleine Dinge etwas besser tut, kann man sogar Weltmarktführer werden." (Reinhold Würth)

Beim Lesen dieses faszinierenden Buchs habe ich einige weitere Hidden Champions, wie beispielsweise die Lauterbach GmbH oder QNX Software Systems ausgemacht.
Außerdem finde ich, dass Apple sehr viele Merkmale eines Hidden Champion aufweist und somit zu den Big Champions zählt.
Auch Google führt wohl das Android-Projekt wie unter "Kunden und Leistungsangebote" beschrieben wie ein kleines, relativ autonomes Unternehmen.

Build your own internet search engine - Part 2

After having started to build my own internet search engine as described in a previous blog post, I now have read some papers and books about web search engine architecture and information retrieval to complete my hobby project. Here is a list of papers and books that I highly recommend to anybody who is interested in this topic:

1. Google: data structures and algorithms by Petteri Huuhka
2. The Anatomy of a Large-Scale Hypertextual Web Search Engine by the Google founders Sergey Brin and Lawrence Page
3. Introduction to Information Retrieval by Christopher D. Manning, Prabhakar Raghavan and Hinrich Schütze
4. Effect of inverted index partitioning schemes on performance of query processing in parallel text retrieval systems by B. Barla Cambazoglu, Aytul Catal and Cevdet Aykanat
5. Distributed Web Crawling, Indexing, and Search by Ricardo Baeza-Yates and B. Barla Cambazoglu
6. Web Search for a Planet by Luiz André Barroso, Jeffrey Dean and Urs Hölzle
7. Building a Search Engine by David Evans and Sebastian Thrun

As described in my previous blog post I build the whole search engine using Erlang technologies. This worked out extremely well for the search bots. But using CouchDB for storing all the web documents, the forward search index and the inverted search index was a bad idea.
A NoSQL database like CouchDB is great for building a web store like Amazon but it is definitely not good at building a highly scalable web search engine.
The problem is that CouchDB is simply not specialized enough for this task. E.g. for every search query you have to look at millions of documents and rank them appropriately. But if you use something like CouchDB (which has a JSON interface) you just need too much resources of everything (CPU time, memory and network bandwidth) while merging and ranking the documents for multiple search keywords. Now I know that :-).

So I have to remove CouchDB from my search engine software stack and implement the required data structures and algorithms by myself, just as explained in [1] and [2].
One extremely important thing is to have compact data structures for storing the web documents, the lexicon, the forward index and the inverted index. This is because you have to keep a lot of data structures in memory for efficiency reasons. It also makes merging the documents of multiple search keywords by DocID much easier and faster.
My data structures will be similar to those in [1] and [2]. There will be an inverted search index which is sorted by WordID (keyword). For every keyword the inverted index contains a list of matching documents which are sorted by DocID. The lexicon contains an entry for every searchable word and links to the list of appropriate documents in the inverted index. The lexicon and inverted index are generated from the web documents using a MapReduce framework.
If the inverted index is queried for the keywords "earth" and "energy" the lexicon is first asked for the two lists of documents containing these words. Then these two listes are merged using mergesort. The mergesort phase generates a new temporary search result index that is sorted by the page rank of the contained documents. E.g. when a document (DocID) is included in both lists it gets a higher page rank in the temporary search result index for that search query. So it may appear further ahead in the list of search results than documents that only match a single keyword. Besides the number of matching keywords, also some other informations like proximity of keywords are used for calculating the final ranking.
The temporary index for the search keywords is then used to generate the search results page and therefore does not need to be larger than 1000 documents. It may also make sense to cache the temporary index of a search query for some minutes.

Now I have put together all data structures and algorithms to build a working web search engine. However, to build a highly scalable and fast search engine I have to distribute the lexicon and the inverted search index across multiple computers. Therefore, each computer gets a part of the lexicon and the inverted search index. To achieve this, one may either do a term-based partitioning of the inverted index or a document-based partitioning of the inverted index, as described in [3], [4] and [5]. I will use the document-based partitioning approach. The overall search result quality must not suffer from partitioning the inverted search index and thus the partitioning algorithm is a little tricky.
With a distributed inverted search index a single search query is performed on multiple computers simultaneously. E.g. when the complete inverted index is distributed across thousands of computers, one search query may be executed on hundreds of them. Thereby each computer is able to perform the search query on its local part of the inverted index (as explained above) very quickly. The temporary search result index (e.g. containing the top-ranked 1000 local documents) of each worker computer is sent to some master computer afterwards. This only requires minimal network bandwidth. The master computer then merges the temporary search result indexes of all worker computers participating in that search query and generates the overall list of best matching documents. This architecture makes the search engine very fast and fault tolerant.

What is really interesting is that processing a single search query gets highly concurrent within the search engine backend to achieve low response times and utilize the available hardware resources efficiently.
I found a website that quotes Marissa Mayer that a single search query on Google is performed by up to 1000 computers. This website also contains the Google I/O 2008 keynote of Marissa Mayer about "How Google Works" which gives some interesting insights into the Google search engine.

One interesting question that comes to my mind is if one could save energy by using Erlang technologies instead of Python and C++ for the search engine backend. Of course Erlang will not help to save energy for the I/O-bound tasks of the search engine backend. But maybe by using Erlang technologies one could achieve the same degree of distribution and concurrency that is needed to run the internet search engine backend with some less computers and therefore less energy. I really don't know if that is possible, but it would be nice to try that out...

Scaling the Social Graph: Infrastructure at Facebook

There was a really interesting talk about Facebook's infrastructure at InfoQ some days ago. Jason Sobel presented the evolution of Facebook’s infrastructure over time, from the original LAMP stack to the present multi-datacenter configuration, the challenges faced and plans for the future.

Scaling the Social Graph: Infrastructure at Facebook @ InfoQ

The most interesting part of the talk is about Facebook's fbobj and assoc abstractions. Facebook places all information in Facebook objects (fbobj) that have IDs and then they interlink them using typed associations (assoc). E.g. there are associations (typed links) to friends, events, photos, etc.. That is really great when doing queries. I think HTML <a href> links should also be extended to allow for types and maybe properties. This would help building the semantic web a lot!

Build your own internet search engine

If you are interested in how to really build a web search engine I suggest to read the second part of this article ("Build your own internet search engine - Part 2") and the section about Apache's search engine software stack at the end of this article.
The CouchDB attempt for the web search engine backend didn't work out, but nevertheless I think this article is quite interesting :-).

A few weeks ago I started building my own (naive) internet search engine using Erlang technologies. I have chosen Erlang projects for that because I think they are perfectly suited for internet backend systems. Now I am stuck at ranking the search results. I will have to read some papers about that before going on :-). Though, up to this point in time everything worked out extremely well.
The first part of the puzzle was to build the search bots that bring home the websites for generating the search index. The search bots were build using the Erlang OTP, ibrowse, mochiweb, mochiweb_xpath and couchbeam projects.
The search engine starts by sending out the first search bot to some website, e.g. http://www.nytimes.com. A search bot downloads a website, forks off new search bots for any links that are found on it and then processes the website. After processing a website each search bot creates (or updates) a CouchDB document that represents the original website along with some keywords, a page rank, etc.. This process is repeated over and over again by each search bot (and for each website). You may imagine that the whole thing gets massively parallel in a very short time.
This massive parallelism caused some headaches to my home router because it was only able to handle a few thousand concurrent HTTP connections. So I limited the concurrency using an Erlang supervisor process. Maybe I will try out Amazon's EC2 in the future. I'm pretty sure they will perform better at this point :-).
The next part of the puzzle was to build the search index from the CouchDB documents that were brought home by the search bots. This is done using a CouchDB design document. Here is a simplified design document that shows how to generate the search index:

"map": "function(doc) {
    var tokens;
    if (doc.keywords) {
        tokens = doc.keywords.split(/[^A-Z0-9_]+/i);
        tokens.map(function(token) {
            for (i = 1; i <= token.length; i += 1) {
             emit(token.slice(0, i), doc);
            }
        });
    }
}"
"reduce": "function(keys, values, rereduce) {
    var output = {};
    if (!rereduce) {
        for (var i in values) {
            output[i] = values[i].url;
        }
    }
    return output;
}"

Now, I was able to query the search index using HTTP requests. For example, the following HTTP POST request queries the search index for the keywords "earth" and "energy". As result you get links to all documents that match these keywords.

curl -X POST http://127.0.0.1:5984/search_index/_design/search_queries/_view/query?group=true -d '{"keys": ["earth", "energy"]}' -H "Content-Type: application/json"

At that point in time I got stuck due to insufficient knowledge about how to appropriately merge and rank the documents that are retrieved from the CouchDB inverted search index. But exactly this ranking is the crux of a good search engine. My idea is to first sort the suggested websites by the number of matching keywords and second by a page rank that is derived from Albert-Laszlo Barabasi's book "Linked": The more links refer to a specific website the higher the page rank for that website.

The web interface for the search engine will simply be a little Couch app.

One thing that I have learned from this hobby project up till now is that scalability really means specialism if you build huge systems like search engines. That is exactly what CouchDB does in order to be fast and scalable. I am sure that the same is true for Google's search engine infrastructure.

This story goes on in this blog post containing part II on the topic.


Update: The Apache search engine software stack
Before going on with the Erlang approach to build a search engine I now have looked at the Apache software stack to build search engines. It looks pretty complete and scalable. The information below is taken from Apache's project websites.

Apache Lucene is a high-performance, full-featured text search engine library written entirely in Java.

The Apache Hadoop project develops open-source software for reliable, scalable, distributed computing. It includes the HDFS, which is a distributed file system that provides high throughput access to application data. It also provides a MapReduce software framework for distributed processing of large data sets on compute clusters. The MapReduce framework can work on top of the HDFS. Check this link for a Hadoop MapReduce example.
Hadoop also contains the Hive framework which provides a mechanism to project structure onto data and query the data using a SQL-like language called HiveQL. It does so by transforming the HiveQL statements to algorithms for Hadoop's MapReduce framework. Hive was developed by Facebook.

Apache Nutch is a highly scalable and relatively feature rich (web) crawler. It contains search bots and other stuff. E.g. Nutch offers features like politeness (obeys robots.txt rules), robustness and scalability (Nutch runs on Apache Hadoop, so you can run Nutch on a single machine or on a cluster of 100 machines), quality (you can bias the crawling to fetch “important” pages first) and extendability. One of the most important single feature Nutch provides out of the box is a link database. Therefore Nutch tracks links between pages so that the relevancy of search results within a collection of interlinked documents goes well beyond the naive case where you index documents without link information and anchor texts.

Apache Solr is an enterprise search platform from the Apache Lucene project. Its major features include powerful full-text search, hit highlighting, faceted search, dynamic clustering, database integration, rich document (e.g., Word, PDF) handling, and geospatial search. Solr is highly scalable, providing distributed search and index replication, and it powers the search and navigation features of many of the world's largest internet sites. Solr is written in Java and runs as a standalone full-text search server within a servlet container such as Tomcat. Solr uses the Lucene Java search library at its core for full-text indexing and search, and has REST-like HTTP/XML and JSON APIs that make it easy to use from virtually any programming language.

When combining Nutch with Solr, Solr will be used as the only source for serving search results (including snippets). This way you can totally decouple your search application from Nutch and still use Nutch where it is at its best: crawling and extracting the content. Using Solr as the search backend, on the other hand, allows you to use all of the advanced features of a Solr server – like query spell checking, “more like this” suggestions, data replication and easy query time relevancy tuning, etc..
So Nutch collects the data and Solr serves it via its search index.
See also this blog entry by Sami Siren for more details.

The Music of Life

What is Life? This is the question asked by Denis Noble in this very personal and at times deeply lyrical book. Nobel, a renowned physiologist and pioneer of the field of systems biology, argues that we must look beyond the reductionist gene's eye view of life to answer the question. The genome is not life itself. To understand what life is, we must make a radical switch of perception and view it at a variety of different levels, with interaction and feedback between gene, cell, organ, system, body and environment. It emerges as a process, no more and no less than the ebb and flow of activity in this intricate web of connections. This, Noble argues, is the music of life. [Noble, The Music of Life]

The Evolution of the Erlang VM

The Evolution of the Erlang VM @ InfoQ
A really really great talk about the internals of the Erlang VM and how it has evolved over time.
That's Joe Armstrong all over :-).

The Problems with the Browser

InfoQ: The Problems with the Browser

Why are we building so much software technologies that will eventually fail?

Modular systems share some key features to achieve the characteristics that are shown above. They are build around a message-passing architecture for communicating between components, they are highly concurrent and they often provide the ability to do late binding of modules in various ways. These features encapsulate the components of modular systems very well and when done right also help minimizing the dependencies between modules. Furthermore, existing dependencies are specified using protocols and sometimes the message flow is described by state machines as well [1]. This makes such systems very comprehensible and maintainable.
Modular systems are also reliable and fault tolerant by design. If some component fails only one specific piece of software with known dependencies is crashing. It does not bring the whole thing to a grinding halt. Other components that are depending on the faulty component will be informed thereof and the faulty component may be restarted. Thereafter all the other components are able to recover from the fault and go on.
Thus one can really say that the whole is more than the sum of the parts.
Some good examples of modular systems are Erlang, QNX Neutrino RTOS, Microsoft's Singularity research project, Google's Android, modern web browsers (like Google's Chrome), all the popular internet backends as Google's search engine and Facebook's social network and of course the internet as a whole.

Monolithic systems do not rely on a message-passing architecture at its core. They are made up of coarse-grained building blocks that have much more shared state than the fine-grained components of modular systems. Hence, monolithic systems do very much (on the same machine) in the same address space on the same thread context using the same call stack and therefore have much less concurrency build right into them. To sync the threads that cross the building blocks of monolithic systems there are very complex locking patterns.
Monolithic systems also encapsulate the details of building blocks quite good when done right. The management of dependencies may be also quite good when done right but the monolithic architecture often tempts people to do more hacks. Another problem with dependencies in monolithic system is that it is often not very clear which threads may cross the border from one component to the other (it is not only a message that crosses the border as in modular systems). Because of that reasons you often need much more knowledge of the building blocks that interfere with each other to understand and maintain them (e.g. keep them thread safe during their evolvement). A building block or component cannot be considered a 'black box' as in modular systems. This complicates the maintainability of such systems a lot.
Some good examples of monolithic systems are Microsoft Windows, traditional Linux systems, the Eclipse IDE and a lot of proprietary frameworks that power phones, TVs, cars, medical devices, etc.

So why are we building so much software technologies that will eventually fail? Well, also the modular systems had its drawbacks. Especially one big drawback: performance. It was simply not affordable to build highly modular systems with the hardware resources and software tools of former times. In the 1960s it started with monolithic operating systems like Multics, but there also was LISP which showed that we can do better.
Later in the 1980s we still built very bad systems like MS-DOS, but there also was Smalltalk which got it right. Smalltalk was just too fat for the emerging PC era.
Later in the 1980s QNX started working on their microkernel OS. Also Joe Armstrong started working on Erlang. They all needed some time to get this kind of systems to the scalability and performance they have today. And it took some time until the hardware resources of the average computer got to a level you could work with. If you do not have much resources why do you need high scalability?
A modular message-passing architecture is nice but also has its cost. For operating systems it required some features form the CPU to do context switches really really fast and from their MMU (memory management unit) and TLB (translation lookaside buffer) to do message passing efficiently. For programming languages and their high-level language virtual machines it required some investigations until they got the right paradigms and high-performance implementations for message-passing, concurrency, reliability, maintainability (e.g. software updates), etc.
But now we crossed the turning point as shown in the image above. Thanks to today's hardware resources that allow for modular systems in internet backends, embedded devices like smartphones and desktop computers and thanks to today's software tools that facilitate the building of more and more complex software technologies we should start building modular systems and refactor or throw away the old monolithic stuff.

But this is not that easy. As Bell Labs tried to replace UNIX with their far better successor Plan 9 they learned an important lesson, as Eric S. Raymond put it:
The long view of history may tell a different story, but in 2003 it looks like Plan 9 failed simply because it fell short of being a compelling enough improvement on Unix to displace its ancestor. Compared to Plan 9, Unix creaks and clanks and has obvious rust spots, but it gets the job done well enough to hold its position. There is a lesson here for ambitious system architects: the most dangerous enemy of a better solution is an existing codebase that is just good enough.

And also Linus Torvalds' commentary at LinuxCon 2009 makes clear that it is not that easy to maintain monolithic systems:
The Linux kernel has become "bloated, huge and scary" and it isn't "the streamlined, hyper-efficient kernel I envisioned when I started writing Linux."

Happily this is not true for new fields of technology. Yes, it is really hard (if not impossible) to establish new desktop computer systems on the market. But for new areas like smartphones or tablets new modular systems are spreading and also prevail against their monolithic counterparts. The interesting thing is that they are superior to our desktop systems in many ways :-).
The most interesting area today are the internet backends. Here new technologies (like Erlang) that share the modular design principles and reduce the complexity and effort needed to get the systems up and running are used more and more.

Some links:

Plan 9: The Way the Future Was

Can We Make Operating Systems Reliable and Secure?

Building a dependable Operating System: Fault Tolerance in MINIX 3

QNX System Architecture Guide

Microsoft Singularity

Linux Kernel Architecture

Erlang

LLVM

Virtual Machines: Versatile platforms for systems and processes

Google Chrome

Representational State Transfer

...

Pid ! Message

Some tenets from Joe Armstrong (a.k.a. the philosophy behind Erlang):

• The world is concurrent.
• Things in the world don't share data.
• Things communicate with messages.
• Things fail.

The Internet of Things

Now, after Facebook has brought the social network to the web, it's time for the internet of things :-).

I think Google is one of the few companies that are able to start building the internet of things, with all their server farms, smartphones, TVs and some self-driving cars ;-).

Then you no longer need to query Google's search engine for timetables or nearby shops and restaurants. The internet of things just tells you everything you need to know.

It is really interesting which technologies will clear the way for the interconnected mesh of systems. Thereby Erlang will hopefully find its way to more and more backend systems :-).